From 03f970652e07c6832cae41fa374cb68ca80d472c Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Tue, 21 Aug 2012 13:13:52 +0000 Subject: [PATCH] shape ops work in progress working demo of old vs. new git-svn-id: http://skia.googlecode.com/svn/trunk@5209 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/EdgeDemo.cpp | 40 ++++--- experimental/Intersection/EdgeDemo.h | 2 +- experimental/Intersection/EdgeDemoApp.mm | 24 ++++- experimental/Intersection/EdgeWalker_Test.h | 1 + .../Intersection/EdgeWalker_TestUtility.cpp | 61 ++++++----- experimental/Intersection/Intersection_Tests.cpp | 4 +- .../Intersection/LineQuadraticIntersection.cpp | 89 ++++++---------- .../LineQuadraticIntersection_Test.cpp | 118 ++++++++++++--------- experimental/Intersection/QuadraticUtilities.cpp | 36 +++++-- experimental/Intersection/Simplify.cpp | 74 +++++++++---- experimental/Intersection/SimplifyNew_Test.cpp | 16 ++- experimental/Intersection/op.htm | 12 +++ gyp/shapeops_demo.gyp | 10 +- 13 files changed, 296 insertions(+), 191 deletions(-) diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp index b71b818..21eefee 100644 --- a/experimental/Intersection/EdgeDemo.cpp +++ b/experimental/Intersection/EdgeDemo.cpp @@ -8,7 +8,7 @@ // or five points which in turn describe a polygon. The polygon points // bounce inside the circles. The circles rotate and scale over time. The // polygons are combined into a single path, simplified, and stroked. -static bool drawCircles(SkCanvas* canvas, int step) +static bool drawCircles(SkCanvas* canvas, int step, bool useOld) { const int circles = 3; int scales[circles]; @@ -34,8 +34,8 @@ static bool drawCircles(SkCanvas* canvas, int step) x *= 3 + scales[c] / 10.0f; y *= 3 + scales[c] / 10.0f; SkScalar angle = angles[c] * 3.1415f * 2 / 600; - SkScalar temp = x * cos(angle) - y * sin(angle); - y = x * sin(angle) + y * cos(angle); + SkScalar temp = (SkScalar) (x * cos(angle) - y * sin(angle)); + y = (SkScalar) (x * sin(angle) + y * cos(angle)); x = temp; x += locs[c * 2] * 200 / 130.0f; y += locs[c * 2 + 1] * 200 / 170.0f; @@ -50,7 +50,11 @@ static bool drawCircles(SkCanvas* canvas, int step) path.close(); } showPath(path, "original:"); - simplify(path, true, out); + if (useOld) { + simplify(path, true, out); + } else { + simplifyx(path, out); + } showPath(out, "simplified:"); SkPaint paint; paint.setAntiAlias(true); @@ -69,8 +73,8 @@ static void createStar(SkPath& path, SkScalar innerRadius, SkScalar outerRadius, SkScalar angle = startAngle; for (int index = 0; index < points * 2; ++index) { SkScalar radius = index & 1 ? outerRadius : innerRadius; - SkScalar x = radius * cos(angle); - SkScalar y = radius * sin(angle); + SkScalar x = (SkScalar) (radius * cos(angle)); + SkScalar y = (SkScalar) (radius * sin(angle)); x += center.fX; y += center.fY; if (index == 0) { @@ -83,12 +87,12 @@ static void createStar(SkPath& path, SkScalar innerRadius, SkScalar outerRadius, path.close(); } -static bool drawStars(SkCanvas* canvas, int step) +static bool drawStars(SkCanvas* canvas, int step, bool useOld) { SkPath path, out; const int stars = 25; int pts[stars]; - static bool initialize = true; + // static bool initialize = true; int s; for (s = 0; s < stars; ++s) { pts[s] = 4 + (s % 7); @@ -104,13 +108,13 @@ static bool drawStars(SkCanvas* canvas, int step) const int maxInner = 800; const int maxOuter = 1153; for (s = 0; s < stars; ++s) { - int starW = width - margin * 2 + (SkScalar) s * (stars - s) / stars; + int starW = (int) (width - margin * 2 + (SkScalar) s * (stars - s) / stars); locs[s].fX = (int) (step * (1.3f * (s + 1) / stars) + s * 121) % (starW * 2); if (locs[s].fX > starW) { locs[s].fX = starW * 2 - locs[s].fX; } locs[s].fX += margin; - int starH = height - margin * 2 + (SkScalar) s * s / stars; + int starH = (int) (height - margin * 2 + (SkScalar) s * s / stars); locs[s].fY = (int) (step * (1.7f * (s + 1) / stars) + s * 183) % (starH * 2); if (locs[s].fY > starH) { locs[s].fY = starH * 2 - locs[s].fY; @@ -136,11 +140,15 @@ static bool drawStars(SkCanvas* canvas, int step) #endif #define TEST_SIMPLIFY 01 #if TEST_SIMPLIFY - simplify(path, true, out); + if (useOld) { + simplify(path, true, out); + } else { + simplifyx(path, out); + } +#endif #if SHOW_PATH showPath(out, "simplified:"); #endif -#endif SkPaint paint; paint.setAntiAlias(true); paint.setStyle(SkPaint::kStroke_Style); @@ -155,22 +163,22 @@ static bool drawStars(SkCanvas* canvas, int step) return true; } -static bool (*drawDemos[])(SkCanvas* , int) = { +static bool (*drawDemos[])(SkCanvas* , int , bool ) = { drawStars, drawCircles }; static size_t drawDemosCount = sizeof(drawDemos) / sizeof(drawDemos[0]); -static bool (*firstTest)(SkCanvas* , int) = 0; +static bool (*firstTest)(SkCanvas* , int , bool) = 0; -bool DrawEdgeDemo(SkCanvas* canvas, int step) { +bool DrawEdgeDemo(SkCanvas* canvas, int step, bool useOld) { size_t index = 0; if (firstTest) { while (index < drawDemosCount && drawDemos[index] != firstTest) { ++index; } } - return (*drawDemos[index])(canvas, step); + return (*drawDemos[index])(canvas, step, useOld); } diff --git a/experimental/Intersection/EdgeDemo.h b/experimental/Intersection/EdgeDemo.h index 21c1563..934e546 100644 --- a/experimental/Intersection/EdgeDemo.h +++ b/experimental/Intersection/EdgeDemo.h @@ -1,3 +1,3 @@ class SkCanvas; -bool DrawEdgeDemo(SkCanvas* canvas, int step); +bool DrawEdgeDemo(SkCanvas* canvas, int step, bool useOld); diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm index baae8bc..e3be2ca 100644 --- a/experimental/Intersection/EdgeDemoApp.mm +++ b/experimental/Intersection/EdgeDemoApp.mm @@ -4,6 +4,9 @@ #include "SkGraphics.h" #include "SkCGUtils.h" +#include +#include + class SkSampleView : public SkView { public: SkSampleView() { @@ -12,10 +15,27 @@ public: }; protected: virtual void onDraw(SkCanvas* canvas) { - static int step = 0; + static int step = -1; + static double seconds; + static bool useOld = true; + if (step == -1) { + timeval t; + gettimeofday(&t, NULL); + seconds = t.tv_sec+t.tv_usec/1000000.0; + step = 0; + } canvas->drawColor(SK_ColorWHITE); - if (DrawEdgeDemo(canvas, step)) { + if (DrawEdgeDemo(canvas, step, useOld)) { ++step; + if (step == 3200) { + timeval t; + gettimeofday(&t, NULL); + double last = seconds; + seconds = t.tv_sec+t.tv_usec/1000000.0; + SkDebugf("old=%d seconds=%g\n", useOld, seconds - last); + useOld ^= true; + step = 0; + } inval(NULL); } } diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index c86cefd..d0ae3a5 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -2,6 +2,7 @@ #include "ShapeOps.h" #include "SkBitmap.h" +#include "SkStream.h" #include class SkCanvas; diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index 0fb37b0..ebc6e14 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -336,9 +336,8 @@ void createThread(State4* statePtr, void* (*testFun)(void* )) { int dispatchTest4(void* (*testFun)(void* ), int a, int b, int c, int d) { int testsRun = 0; - + State4* statePtr; if (!gRunTestsInOneThread) { - State4* statePtr; pthread_mutex_lock(&State4::addQueue); if (threadIndex < maxThreads) { statePtr = &threadState[threadIndex]; @@ -381,12 +380,16 @@ int dispatchTest4(void* (*testFun)(void* ), int a, int b, int c, int d) { } pthread_mutex_unlock(&State4::addQueue); } else { - State4 state; - state.a = a; - state.b = b; - state.c = c; - state.d = d; - (*testFun)(&state); + statePtr = &threadState[0]; + statePtr->testsRun = 0; + statePtr->a = a; + statePtr->b = b; + statePtr->c = c; + statePtr->d = d; + statePtr->done = false; + statePtr->index = threadIndex; + statePtr->last = false; + (*testFun)(statePtr); testsRun++; } return testsRun; @@ -404,20 +407,18 @@ void initializeTests(const char* test, size_t testNameSize) { maxThreads = 8; } } - if (!gRunTestsInOneThread) { - SkFILEStream inFile("../../experimental/Intersection/op.htm"); - if (inFile.isValid()) { - SkTDArray inData; - inData.setCount(inFile.getLength()); - size_t inLen = inData.count(); - inFile.read(inData.begin(), inLen); - inFile.setPath(NULL); - char* insert = strstr(inData.begin(), marker); - if (insert) { - insert += sizeof(marker) - 1; - const char* numLoc = insert + 4 /* indent spaces */ + testNameSize - 1; - testNumber = atoi(numLoc) + 1; - } + SkFILEStream inFile("../../experimental/Intersection/op.htm"); + if (inFile.isValid()) { + SkTDArray inData; + inData.setCount(inFile.getLength()); + size_t inLen = inData.count(); + inFile.read(inData.begin(), inLen); + inFile.setPath(NULL); + char* insert = strstr(inData.begin(), marker); + if (insert) { + insert += sizeof(marker) - 1; + const char* numLoc = insert + 4 /* indent spaces */ + testNameSize - 1; + testNumber = atoi(numLoc) + 1; } } const char* filename = preferredFilename; @@ -441,15 +442,17 @@ void initializeTests(const char* test, size_t testNameSize) { void outputProgress(const State4& state, const char* pathStr, SkPath::FillType pathFillType) { if (gRunTestsInOneThread) { - SkDebugf("%s\n", pathStr); - } else { - SkFILEWStream outFile(state.filename); - if (!outFile.isValid()) { - SkASSERT(0); - return; + if (pathFillType == SkPath::kEvenOdd_FillType) { + SkDebugf(" path.setFillType(SkPath::kEvenOdd_FillType);\n", pathStr); } - outputToStream(state, pathStr, pathFillType, outFile); + SkDebugf("%s\n", pathStr); + } + SkFILEWStream outFile(state.filename); + if (!outFile.isValid()) { + SkASSERT(0); + return; } + outputToStream(state, pathStr, pathFillType, outFile); } static void writeTestName(SkPath::FillType pathFillType, SkWStream& outFile) { diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index 67885b3..39faad1 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -8,9 +8,10 @@ void cubecode_test(int test); void Intersection_Tests() { int testsRun = 0; - QuadLineIntersectThreaded_Test(testsRun); SimplifyNew_Test(); Simplify4x4QuadraticsThreaded_Test(testsRun); + QuadLineIntersectThreaded_Test(testsRun); + LineQuadraticIntersection_Test(); Simplify4x4RectsThreaded_Test(testsRun); SimplifyNondegenerate4x4TrianglesThreaded_Test(testsRun); SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun); @@ -33,7 +34,6 @@ void Intersection_Tests() { LineParameter_Test(); LineIntersection_Test(); - LineQuadraticIntersection_Test(); LineCubicIntersection_Test(); SimplifyQuadraticPaths_Test(); diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp index e2e712f..c3e6d23 100644 --- a/experimental/Intersection/LineQuadraticIntersection.cpp +++ b/experimental/Intersection/LineQuadraticIntersection.cpp @@ -47,15 +47,6 @@ line: } } -Numeric Solutions (5.6) suggests to solve the quadratic by computing - - Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) - -and using the roots - - t1 = Q / A - t2 = C / Q - Using the results above (when the line tends towards horizontal) A = (-(d - 2*e + f) + g*(a - 2*b + c) ) B = 2*( (d - e ) - g*(a - b ) ) @@ -125,31 +116,21 @@ bool intersect() { } double t[2]; int roots = quadraticRoots(A, B, C, t); - for (int x = 0; x < roots; ++x) { - intersections.add(t[x], findLineT(t[x])); - } - // FIXME: quadratic root doesn't find t=0 or t=1, necessitating the hack below - if (roots == 0 || (roots == 1 && intersections.fT[0][0] >= FLT_EPSILON)) { - if (quad[0] == line[0]) { - intersections.fT[0][roots] = 0; - intersections.fT[1][roots++] = 0; - intersections.fUsed++; - } else if (quad[0] == line[1]) { - intersections.fT[0][roots] = 0; - intersections.fT[1][roots++] = 1; - intersections.fUsed++; + for (int x = 0; x < roots; ) { + double lineT = findLineT(t[x]); + if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) { + if (x < --roots) { + t[x] = t[roots]; + } + continue; } - } - if (roots == 0 || (roots == 1 && intersections.fT[0][0] <= 1 - FLT_EPSILON)) { - if (quad[2] == line[1]) { - intersections.fT[0][roots] = 1; - intersections.fT[1][roots++] = 1; - intersections.fUsed++; - } else if (quad[2] == line[0]) { - intersections.fT[0][roots] = 1; - intersections.fT[1][roots++] = 0; - intersections.fUsed++; + if (lineT < FLT_EPSILON) { + lineT = 0; + } else if (lineT > 1 - FLT_EPSILON) { + lineT = 1; } + intersections.add(t[x], lineT); + ++x; } return roots > 0; } @@ -161,17 +142,7 @@ int horizontalIntersect(double axisIntercept) { D += F - 2 * E; // D = d - 2*e + f E -= F; // E = -(d - e) F -= axisIntercept; - int roots = quadraticRoots(D, E, F, intersections.fT[0]); - // FIXME: ? quadraticRoots doesn't pick up intersections at 0, 1 - if (roots < 2 && fabs(F) < FLT_EPSILON - && (roots == 0 || intersections.fT[0][0] >= FLT_EPSILON)) { - intersections.fT[0][roots++] = 0; - } - if (roots < 2 && fabs(quad[2].y - axisIntercept) < FLT_EPSILON - && (roots == 0 || intersections.fT[0][0] <= 1 - FLT_EPSILON)) { - intersections.fT[0][roots++] = 1; - } - return roots; + return quadraticRoots(D, E, F, intersections.fT[0]); } int verticalIntersect(double axisIntercept) { @@ -181,17 +152,7 @@ int verticalIntersect(double axisIntercept) { D += F - 2 * E; // D = d - 2*e + f E -= F; // E = -(d - e) F -= axisIntercept; - int roots = quadraticRoots(D, E, F, intersections.fT[0]); - // FIXME: ? quadraticRoots doesn't pick up intersections at 0, 1 - if (roots < 2 && fabs(F) < FLT_EPSILON - && (roots == 0 || intersections.fT[0][0] >= FLT_EPSILON)) { - intersections.fT[0][roots++] = 0; - } - if (roots < 2 && fabs(quad[2].x - axisIntercept) < FLT_EPSILON - && (roots == 0 || intersections.fT[0][0] <= 1 - FLT_EPSILON)) { - intersections.fT[0][roots++] = 1; - } - return roots; + return quadraticRoots(D, E, F, intersections.fT[0]); } protected: @@ -284,13 +245,19 @@ int horizontalIntersect(const Quadratic& quad, double left, double right, double for (int index = 0; index < result; ) { double x, y; xy_at_t(quad, intersections.fT[0][index], x, y); - if (x < left || x > right) { + double lineT = (x - left) / (right - left); + if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) { if (--result > index) { intersections.fT[0][index] = intersections.fT[0][result]; } continue; } - intersections.fT[1][index] = (x - left) / (right - left); + if (lineT < FLT_EPSILON) { + lineT = 0; + } else if (lineT > 1 - FLT_EPSILON) { + lineT = 1; + } + intersections.fT[1][index] = lineT; ++index; } if (flipped) { @@ -309,13 +276,19 @@ int verticalIntersect(const Quadratic& quad, double top, double bottom, double x for (int index = 0; index < result; ) { double x, y; xy_at_t(quad, intersections.fT[0][index], x, y); - if (y < top || y > bottom) { + double lineT = (y - top) / (bottom - top); + if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) { if (--result > index) { intersections.fT[0][index] = intersections.fT[0][result]; } continue; } - intersections.fT[1][index] = (y - top) / (bottom - top); + if (lineT < FLT_EPSILON) { + lineT = 0; + } else if (lineT > 1 - FLT_EPSILON) { + lineT = 1; + } + intersections.fT[1][index] = lineT; ++index; } if (flipped) { diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp index 1161d2d..e641fdc 100644 --- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp +++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp @@ -8,16 +8,47 @@ struct lineQuad { Quadratic quad; _Line line; + int result; + _Point expected[2]; } lineQuadTests[] = { - {{{2, 0}, {1, 1}, {2, 2}}, {{0, 0}, {0, 2}}}, - {{{4, 0}, {0, 1}, {4, 2}}, {{3, 1}, {4, 1}}}, - {{{0, 0}, {0, 1}, {1, 1}}, {{0, 1}, {1, 0}}}, + // quad line results + {{{1, 1}, {2, 1}, {0, 2}}, {{0, 0}, {1, 1}}, 1, {{1, 1} }}, + {{{0, 0}, {1, 1}, {3, 1}}, {{0, 0}, {3, 1}}, 2, {{0, 0}, {3, 1}}}, + {{{2, 0}, {1, 1}, {2, 2}}, {{0, 0}, {0, 2}}, 0 }, + {{{4, 0}, {0, 1}, {4, 2}}, {{3, 1}, {4, 1}}, 0, }, + {{{0, 0}, {0, 1}, {1, 1}}, {{0, 1}, {1, 0}}, 1, {{.25, .75} }}, }; size_t lineQuadTests_count = sizeof(lineQuadTests) / sizeof(lineQuadTests[0]); const int firstLineQuadIntersectionTest = 0; +static int doIntersect(Intersections& intersections, const Quadratic& quad, const _Line& line, bool& flipped) { + int result; + flipped = false; + if (line[0].x == line[1].x) { + double top = line[0].y; + double bottom = line[1].y; + flipped = top > bottom; + if (flipped) { + SkTSwap(top, bottom); + } + result = verticalIntersect(quad, top, bottom, line[0].x, flipped, intersections); + } else if (line[0].y == line[1].y) { + double left = line[0].x; + double right = line[1].x; + flipped = left > right; + if (flipped) { + SkTSwap(left, right); + } + result = horizontalIntersect(quad, left, right, line[0].y, flipped, intersections); + } else { + intersect(quad, line, intersections); + result = intersections.fUsed; + } + return result; +} + void LineQuadraticIntersection_Test() { for (size_t index = firstLineQuadIntersectionTest; index < lineQuadTests_count; ++index) { const Quadratic& quad = lineQuadTests[index].quad; @@ -27,31 +58,43 @@ void LineQuadraticIntersection_Test() { int order1 = reduceOrder(quad, reduce1); int order2 = reduceOrder(line, reduce2); if (order1 < 3) { - printf("[%d] quad order=%d\n", (int) index, order1); + SkDebugf("%s [%d] quad order=%d\n", __FUNCTION__, (int) index, order1); + SkASSERT(0); } if (order2 < 2) { - printf("[%d] line order=%d\n", (int) index, order2); + SkDebugf("%s [%d] line order=%d\n", __FUNCTION__, (int) index, order2); + SkASSERT(0); } - if (order1 == 3 && order2 == 2) { - Intersections intersections; - intersect(reduce1, reduce2, intersections); - if (intersections.intersected()) { - for (int pt = 0; pt < intersections.used(); ++pt) { - double tt1 = intersections.fT[0][pt]; - double tx1, ty1; - xy_at_t(quad, tt1, tx1, ty1); - double tt2 = intersections.fT[1][pt]; - double tx2, ty2; - xy_at_t(line, tt2, tx2, ty2); - if (!approximately_equal(tx1, tx2)) { - printf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", - __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); - } - if (!approximately_equal(ty1, ty2)) { - printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", - __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); - } - } + Intersections intersections; + bool flipped = false; + int result = doIntersect(intersections, quad, line, flipped); + SkASSERT(result == lineQuadTests[index].result); + if (!intersections.intersected()) { + continue; + } + for (int pt = 0; pt < result; ++pt) { + double tt1 = intersections.fT[0][pt]; + SkASSERT(tt1 >= 0 && tt1 <= 1); + _Point t1, t2; + xy_at_t(quad, tt1, t1.x, t1.y); + double tt2 = intersections.fT[1][pt]; + SkASSERT(tt2 >= 0 && tt2 <= 1); + xy_at_t(line, tt2, t2.x, t2.y); + if (!approximately_equal(t1.x, t2.x)) { + SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, (int)index, pt, tt1, t1.x, t1.y, tt2, t2.x, t2.y); + SkASSERT(0); + } + if (!approximately_equal(t1.y, t2.y)) { + SkDebugf("%s [%d,%d] y!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, (int)index, pt, tt1, t1.x, t1.y, tt2, t2.x, t2.y); + SkASSERT(0); + } + if (!t1.approximatelyEqual(lineQuadTests[index].expected[0]) + && (lineQuadTests[index].result == 1 + || !t1.approximatelyEqual(lineQuadTests[index].expected[1]))) { + SkDebugf("%s t1=(%1.9g,%1.9g)\n", __FUNCTION__, t1.x, t1.y); + SkASSERT(0); } } } @@ -68,37 +111,14 @@ static void testLineIntersect(State4& state, const Quadratic& quad, const _Line& str += sprintf(str, " path.lineTo(%1.9g, %1.9g);\n", line[1].x, line[1].y); Intersections intersections; - int result; bool flipped = false; - if (line[0].x == line[1].x) { - double top = line[0].y; - double bottom = line[1].y; - bool flipped = top > bottom; - if (flipped) { - SkTSwap(top, bottom); - } - result = verticalIntersect(quad, top, bottom, line[0].x, flipped, intersections); - } else if (line[0].y == line[1].y) { - double left = line[0].x; - double right = line[1].x; - bool flipped = left > right; - if (flipped) { - SkTSwap(left, right); - } - result = horizontalIntersect(quad, left, right, line[0].y, flipped, intersections); - } else { - intersect(quad, line, intersections); - result = intersections.fUsed; - } + int result = doIntersect(intersections, quad, line, flipped); bool found = false; for (int index = 0; index < result; ++index) { double quadT = intersections.fT[0][index]; double quadX, quadY; xy_at_t(quad, quadT, quadX, quadY); double lineT = intersections.fT[1][index]; - if (flipped) { - lineT = 1 - lineT; - } double lineX, lineY; xy_at_t(line, lineT, lineX, lineY); if (fabs(quadX - lineX) < FLT_EPSILON && fabs(quadY - lineY) < FLT_EPSILON diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp index 4b695df..cc15bc1 100644 --- a/experimental/Intersection/QuadraticUtilities.cpp +++ b/experimental/Intersection/QuadraticUtilities.cpp @@ -1,6 +1,19 @@ #include "QuadraticUtilities.h" #include +/* + +Numeric Solutions (5.6) suggests to solve the quadratic by computing + + Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) + +and using the roots + + t1 = Q / A + t2 = C / Q + +*/ + int quadraticRoots(double A, double B, double C, double t[2]) { B *= 2; double square = B * B - 4 * A * C; @@ -9,19 +22,24 @@ int quadraticRoots(double A, double B, double C, double t[2]) { } double squareRt = sqrt(square); double Q = (B + (B < 0 ? -squareRt : squareRt)) / -2; - double ratio; int foundRoots = 0; - if ((Q <= A) ^ (Q < 0)) { - ratio = Q / A; - if (!isnan(ratio)) { - t[foundRoots++] = ratio; + double ratio = Q / A; + if (ratio > -FLT_EPSILON && ratio < 1 + FLT_EPSILON) { + if (ratio < FLT_EPSILON) { + ratio = 0; + } else if (ratio > 1 - FLT_EPSILON) { + ratio = 1; } + t[foundRoots++] = ratio; } - if ((C <= Q) ^ (C < 0)) { - ratio = C / Q; - if (!isnan(ratio)) { - t[foundRoots++] = ratio; + ratio = C / Q; + if (ratio > -FLT_EPSILON && ratio < 1 + FLT_EPSILON) { + if (ratio < FLT_EPSILON) { + ratio = 0; + } else if (ratio > 1 - FLT_EPSILON) { + ratio = 1; } + t[foundRoots++] = ratio; } return foundRoots; } diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index eb6bda5..45f9696 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -27,7 +27,7 @@ int gDebugMaxWindValue = SK_MaxS32; #define DEBUG_UNUSED 0 // set to expose unused functions -#if 0 // set to 1 for multiple thread -- no debugging +#if 1 // set to 1 for multiple thread -- no debugging const bool gRunTestsInOneThread = false; @@ -53,7 +53,7 @@ const bool gRunTestsInOneThread = true; #define DEBUG_CONCIDENT 1 #define DEBUG_CROSS 0 #define DEBUG_DUMP 1 -#define DEBUG_MARK_DONE 0 +#define DEBUG_MARK_DONE 1 #define DEBUG_PATH_CONSTRUCTION 1 #define DEBUG_SORT 1 #define DEBUG_WIND_BUMP 0 @@ -458,23 +458,31 @@ public: if (cmp) { return cmp < 0; } - if ((fDDy < 0) ^ (rh.fDDy < 0)) { - return fDDy < 0; + SkScalar dy = fDy + fDDy; + SkScalar rdy = rh.fDy + rh.fDDy; + if ((dy < 0) ^ (rdy < 0)) { + return dy < 0; } - if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) { - return fDDx < rh.fDDx; + SkScalar dx = fDx + fDDx; + SkScalar rdx = rh.fDx + rh.fDDx; + if (dy == 0 && rdy == 0 && dx != rdx) { + return dx < rdx; } - cmp = fDDx * rh.fDDy - rh.fDDx * fDDy; + cmp = dx * rdy - rdx * dy; if (cmp) { return cmp < 0; } - if ((fDDDy < 0) ^ (rh.fDDDy < 0)) { - return fDDDy < 0; + dy += fDDDy; + rdy += rh.fDDDy; + if ((dy < 0) ^ (rdy < 0)) { + return dy < 0; } - if (fDDDy == 0 && rh.fDDDy == 0) { - return fDDDx < rh.fDDDx; + dx += fDDDx; + rdx += rh.fDDDx; + if (dy == 0 && rdy == 0 && dx != rdx) { + return dx < rdx; } - return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; + return dx * rdy < rdx * dy; } double dx() const { @@ -1029,7 +1037,9 @@ public: SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); while (oSpan->fT > otherTMatchStart - FLT_EPSILON && otherTMatchEnd - FLT_EPSILON > oSpan->fT) { + #ifdef SK_DEBUG SkASSERT(originalWindValue == oSpan->fWindValue); + #endif if (decrement) { other.decrementSpan(oSpan); } else if (track && oSpan->fT < 1 && testT < 1) { @@ -1097,7 +1107,9 @@ public: do { if (transfer) { if (decrementOther) { + #ifdef SK_DEBUG SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue); + #endif ++(end->fWindValue); } else if (decrementSpan(end)) { TrackOutside(outsideTs, end->fT, oStartT); @@ -1119,7 +1131,9 @@ public: while (oEnd->fT < oEndT - FLT_EPSILON && oEnd->fT - otherTMatch < FLT_EPSILON) { if (transfer) { if (decrementThis) { - SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue); + #ifdef SK_DEBUG + SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue); + #endif ++(oEnd->fWindValue); } else if (other.decrementSpan(oEnd)) { TrackOutside(oOutsideTs, oEnd->fT, startT); @@ -1251,6 +1265,9 @@ public: buildAngles(endIndex, angles); SkTDArray sorted; sortAngles(angles, sorted); +#if DEBUG_SORT + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); +#endif int angleCount = angles.count(); const Angle* angle; const Segment* base; @@ -1279,7 +1296,7 @@ public: winding += spanWinding; } #if DEBUG_SORT - base->debugShowSort(sorted, firstIndex, winding); + base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding); #endif int nextIndex = firstIndex + 1; int lastIndex = firstIndex != 0 ? firstIndex : angleCount; @@ -1475,7 +1492,7 @@ public: int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); #if DEBUG_SORT - debugShowSort(sorted, firstIndex, winding); + debugShowSort(__FUNCTION__, sorted, firstIndex, winding); #endif SkASSERT(sorted[firstIndex]->segment() == this); #if DEBUG_WINDING @@ -1510,8 +1527,8 @@ public: nextSegment = nextAngle->segment(); sumWinding -= nextSegment->spanSign(nextAngle); altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs - SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); #if DEBUG_WINDING + SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__, nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped); #endif @@ -1635,7 +1652,9 @@ public: if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) { break; } + #ifdef SK_DEBUG SkASSERT(firstLoop); + #endif SkDEBUGCODE(firstLoop = false;) step = -step; } while (true); @@ -1653,7 +1672,7 @@ public: int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); #if DEBUG_SORT - debugShowSort(sorted, firstIndex, 0); + debugShowSort(__FUNCTION__, sorted, firstIndex, 0); #endif SkASSERT(sorted[firstIndex]->segment() == this); int nextIndex = firstIndex + 1; @@ -1852,6 +1871,9 @@ public: buildAngles(firstT, angles); SkTDArray sorted; sortAngles(angles, sorted); + #if DEBUG_SORT + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); + #endif // skip edges that have already been processed firstT = -1; Segment* leftSegment; @@ -2051,7 +2073,9 @@ public: debugShowNewWinding(funName, span, winding); #endif SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + #ifdef SK_DEBUG SkASSERT(abs(winding) <= gDebugMaxWindSum); + #endif span.fWindSum = winding; return &span; } @@ -2362,13 +2386,13 @@ public: #endif #if DEBUG_SORT - void debugShowSort(const SkTDArray& angles, int first, + void debugShowSort(const char* fun, const SkTDArray& angles, int first, const int contourWinding) const { SkASSERT(angles[first]->segment() == this); SkASSERT(angles.count() > 1); int lastSum = contourWinding; int windSum = lastSum - spanSign(angles[first]); - SkDebugf("%s contourWinding=%d sign=%d\n", __FUNCTION__, + SkDebugf("%s %s contourWinding=%d sign=%d\n", fun, __FUNCTION__, contourWinding, spanSign(angles[first])); int index = first; bool firstTime = true; @@ -2384,9 +2408,10 @@ public: lastSum = windSum; windSum -= segment.spanSign(&angle); } - SkDebugf("%s [%d] id=%d start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" + SkDebugf("%s [%d] id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n", - __FUNCTION__, index, segment.fID, start, segment.xAtT(&sSpan), + __FUNCTION__, index, segment.fID, kLVerbStr[segment.fVerb], + start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue, lastSum, windSum, useInnerWinding(lastSum, windSum) @@ -3358,7 +3383,7 @@ static int innerContourCheck(SkTDArray& contourList, // hour after 6 o'clock sortAngles(angles, sorted); #if DEBUG_SORT - sorted[0]->segment()->debugShowSort(sorted, 0, 0); + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); #endif // walk the sorted angle fan to find the lowest angle // above the base point. Currently, the first angle in the sorted array @@ -3510,6 +3535,9 @@ static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, } SkTDArray sorted; sortAngles(angles, sorted); +#if DEBUG_SORT + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); +#endif // find first angle, initialize winding to computed fWindSum int firstIndex = -1; const Angle* angle; @@ -3529,7 +3557,7 @@ static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, winding += spanWinding; } #if DEBUG_SORT - segment->debugShowSort(sorted, firstIndex, winding); + segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding); #endif // we care about first sign and whether wind sum indicates this // edge is inside or outside. Maybe need to pass span winding diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index b708652..828da54 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -1167,12 +1167,26 @@ static void testQuadratic2() { testSimplifyx(path); } -static void (*firstTest)() = testQuadratic2; +static void testQuadratic3() { + SkPath path; + path.moveTo(0, 0); + path.quadTo(0, 0, 1, 0); + path.lineTo(0, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 0); + path.quadTo(1, 0, 0, 1); + path.close(); + testSimplifyx(path); +} + +static void (*firstTest)() = testQuadratic3; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(testQuadratic3), TEST(testQuadratic2), TEST(testQuadratic1), TEST(testLine4x), diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index b844053..b71ebbc 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -1036,11 +1036,23 @@ path.close(); path.close(); +
+ path.moveTo(0, 0); + path.quadTo(0, 0, 1, 0); + path.lineTo(0, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 0); + path.quadTo(1, 0, 0, 1); + path.close(); +
+