From 0b7da433fe0eaa2833d1b2900715b013b36d93da Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Wed, 31 Oct 2012 19:00:20 +0000 Subject: shape ops work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@6223 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/DataTypes.cpp | 8 +- experimental/Intersection/DataTypes.h | 53 +-- experimental/Intersection/EdgeDemo.cpp | 12 +- experimental/Intersection/EdgeDemoApp.mm | 8 +- experimental/Intersection/Intersection_Tests.cpp | 3 +- .../LineQuadraticIntersection_Test.cpp | 34 ++ experimental/Intersection/QuadraticImplicit.cpp | 51 ++- .../Intersection/QuadraticIntersection_Test.cpp | 10 +- experimental/Intersection/QuarticRoot.cpp | 4 +- experimental/Intersection/Simplify.cpp | 195 ++++++---- experimental/Intersection/as.htm | 415 ++++++++++++++++++--- experimental/Intersection/op.htm | 50 +++ 12 files changed, 656 insertions(+), 187 deletions(-) (limited to 'experimental') diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index 3efffc11f8..2832ab2c85 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -48,7 +48,7 @@ union Float_t #endif }; -bool AlmostEqualUlps(float A, float B, int maxUlpsDiff) +bool AlmostEqualUlps(float A, float B) { Float_t uA(A); Float_t uB(B); @@ -62,9 +62,11 @@ bool AlmostEqualUlps(float A, float B, int maxUlpsDiff) // Find the difference in ULPs. int ulpsDiff = abs(uA.i - uB.i); - return ulpsDiff <= maxUlpsDiff; + return ulpsDiff <= UlpsEpsilon; } +// FIXME: obsolete, delete +#if 1 int UlpsDiff(float A, float B) { Float_t uA(A); @@ -78,5 +80,5 @@ int FloatAsInt(float A) Float_t uA(A); return uA.i; } - +#endif diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index e68f303d08..69bd27bf2a 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -18,46 +18,11 @@ #include #include -bool AlmostEqualUlps(float A, float B, int maxUlpsDiff); +extern bool AlmostEqualUlps(float A, float B); +// FIXME: delete int UlpsDiff(float A, float B); int FloatAsInt(float A); -#define USE_EPSILON 0 - -#if USE_EPSILON -extern const double PointEpsilon; -extern const double SquaredEpsilon; - -inline bool approximately_equal(double x, double y) { - return fabs(x - y) < PointEpsilon; -} - -inline bool approximately_equal_squared(double x, double y) { - return fabs(x - y) < SquaredEpsilon; -} - -inline bool approximately_greater(double x, double y) { - return x > y - PointEpsilon; -} - -inline bool approximately_lesser(double x, double y) { - return x < y + PointEpsilon; -} - -inline bool approximately_zero(double x) { - return fabs(x) < PointEpsilon; -} - -inline bool approximately_zero_squared(double x) { - return fabs(x) < SquaredEpsilon; -} - -inline bool approximately_negative(double x) { - return x < PointEpsilon; -} -#else -extern const int UlpsEpsilon; - #if defined(IN_TEST) // FIXME: move to test-only header const double PointEpsilon = 0.000001; @@ -84,11 +49,7 @@ inline bool approximately_zero_squared(double x) { } inline bool approximately_equal(double x, double y) { - if (approximately_zero(x - y)) { - return true; - } - // FIXME: since no other function uses ULPS, this one shouldn't either - return AlmostEqualUlps((float) x, (float) y, UlpsEpsilon); + return approximately_zero(x - y); } inline bool approximately_equal_squared(double x, double y) { @@ -159,8 +120,6 @@ inline bool between(double a, double b, double c) { return (a - b) * (c - b) <= 0; } -#endif - struct _Point { double x; double y; @@ -178,8 +137,12 @@ struct _Point { return a.x!= b.x || a.y != b.y; } + // note: this can not be implemented with + // return approximately_equal(a.y, y) && approximately_equal(a.x, x); + // because that will not take the magnitude of the values bool approximatelyEqual(const _Point& a) const { - return approximately_equal(a.y, y) && approximately_equal(a.x, x); + return AlmostEqualUlps((float) x, (float) a.x) + && AlmostEqualUlps((float) y, (float) a.y); } }; diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp index 00eac48f93..8586c2bfb4 100644 --- a/experimental/Intersection/EdgeDemo.cpp +++ b/experimental/Intersection/EdgeDemo.cpp @@ -228,20 +228,20 @@ static void tryRoncoOnce(const SkPath& path, const SkRect& target, bool show) { } static void tryRonco(const SkPath& path) { - int divMax = 17; + int divMax = 64; int divMin = 1; int xDivMin = 0; int yDivMin = 0; bool allYs = true; bool allXs = true; if (1) { - divMax = divMin = 3; - xDivMin = 0; + divMax = divMin = 64; + xDivMin = 11; yDivMin = 0; allXs = true; allYs = true; } - for (int divs = divMax; divs >= divMin; divs -= 2) { + for (int divs = divMax; divs >= divMin; divs /= 2) { SkDebugf("divs=%d\n",divs); const SkRect& overall = path.getBounds(); SkScalar cellWidth = overall.width() / divs * 2; @@ -292,7 +292,7 @@ static bool drawLetters(SkCanvas* canvas, int step, bool useOld) for (int mask = 0; mask < 1 << testStrLen; ++mask) { char maskStr[testStrLen]; #if 1 - mask = 3; + mask = 12; oneShot = true; #endif SkDebugf("mask=%d\n", mask); @@ -310,7 +310,7 @@ static bool drawLetters(SkCanvas* canvas, int step, bool useOld) } #endif paint.getPosTextPath(testStr, testStrLen, textPos, &path); -#if 1 +#if 0 tryRonco(path); SkDebugf("RoncoDone!\n"); #endif diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm index 67dc6138a6..41dea67a4b 100644 --- a/experimental/Intersection/EdgeDemoApp.mm +++ b/experimental/Intersection/EdgeDemoApp.mm @@ -12,12 +12,12 @@ public: SkSampleView() { this->setVisibleP(true); this->setClipToBounds(false); - useOld = true; + useOld = false; }; protected: virtual void onDraw(SkCanvas* canvas) { - static int step = 9658; // 17909 ; // drawLetters first error - // drawStars triggers error at 23275 + static int step = 17907; // 17907 drawLetters first error + // drawStars triggers error at 33348 // drawStars error not easy to debug last time I checked static double seconds; if (step == -1) { @@ -29,7 +29,7 @@ protected: canvas->drawColor(SK_ColorWHITE); if (DrawEdgeDemo(canvas, step, useOld)) { ++step; - if (step == 23270) { + if (step == -1) { timeval t; gettimeofday(&t, NULL); double last = seconds; diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index c379fb2d77..eae004c860 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -15,12 +15,11 @@ void cubecode_test(int test); void Intersection_Tests() { int testsRun = 0; SimplifyNew_Test(); + QuadraticIntersection_Test(); LineQuadraticIntersection_Test(); MiniSimplify_Test(); - QuadraticIntersection_Test(); SimplifyAngle_Test(); QuarticRoot_Test(); - // QuadraticIntersection_Test(); Simplify4x4QuadraticsThreaded_Test(testsRun); QuadLineIntersectThreaded_Test(testsRun); Simplify4x4RectsThreaded_Test(testsRun); diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp index 171a778cb0..69227c3a40 100644 --- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp +++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp @@ -55,7 +55,41 @@ static int doIntersect(Intersections& intersections, const Quadratic& quad, cons return result; } +static struct oneLineQuad { + Quadratic quad; + _Line line; +} oneOffs[] = { + {{{369.848602,145.680267}, {382.360413,121.298294}, {406.207703,121.298294}}, + {{406.207703,121.298294}, {348.781738,123.864815}}} + }; + +static size_t oneOffs_count = sizeof(oneOffs) / sizeof(oneOffs[0]); + + +static void testOneOffs() { + Intersections intersections; + bool flipped = false; + for (size_t index = 0; index < oneOffs_count; ++index) { + const Quadratic& quad = oneOffs[index].quad; + const _Line& line = oneOffs[index].line; + int result = doIntersect(intersections, quad, line, flipped); + for (int inner = 0; inner < result; ++inner) { + double quadT = intersections.fT[0][inner]; + double quadX, quadY; + xy_at_t(quad, quadT, quadX, quadY); + double lineT = intersections.fT[1][inner]; + double lineX, lineY; + xy_at_t(line, lineT, lineX, lineY); + assert(approximately_equal(quadX, lineX) + && approximately_equal(quadY, lineY)); + } + } +} + void LineQuadraticIntersection_Test() { + if (1) { + testOneOffs(); + } for (size_t index = firstLineQuadIntersectionTest; index < lineQuadTests_count; ++index) { const Quadratic& quad = lineQuadTests[index].quad; const _Line& line = lineQuadTests[index].line; diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp index 9960117c73..d892ae97e0 100644 --- a/experimental/Intersection/QuadraticImplicit.cpp +++ b/experimental/Intersection/QuadraticImplicit.cpp @@ -144,31 +144,74 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { assert(rootCount == rootCount2); addValidRoots(roots1, rootCount, 0, i); addValidRoots(roots2, rootCount, 1, i); + if (i.insertBalanced() && i.fUsed <= 1) { + if (i.fUsed == 1) { + _Point xy1, xy2; + xy_at_t(q1, i.fT[0][0], xy1.x, xy1.y); + xy_at_t(q2, i.fT[1][0], xy2.x, xy2.y); + if (!xy1.approximatelyEqual(xy2)) { + --i.fUsed; + --i.fUsed2; + } + } + return i.intersected(); + } _Point pts[4]; bool matches[4]; int flipCheck[4]; + int closest[4]; + double dist[4]; int index, ndex2; int flipIndex = 0; for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y); matches[ndex2] = false; } - for (index = 0; index < i.fUsed; ) { + for (index = 0; index < i.fUsed; ++index) { _Point xy; xy_at_t(q1, i.fT[0][index], xy.x, xy.y); + dist[index] = DBL_MAX; + closest[index] = -1; + for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { + if (!pts[ndex2].approximatelyEqual(xy)) { + continue; + } + double dx = pts[ndex2].x - xy.x; + double dy = pts[ndex2].y - xy.y; + double distance = dx * dx + dy * dy; + if (dist[index] <= distance) { + continue; + } + for (int outer = 0; outer < index; ++outer) { + if (closest[outer] != ndex2) { + continue; + } + if (dist[outer] < distance) { + goto next; + } + closest[outer] = -1; + } + dist[index] = distance; + closest[index] = ndex2; + next: + ; + } + } + for (index = 0; index < i.fUsed; ) { for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { - if (approximately_equal(pts[ndex2].x, xy.x) && approximately_equal(pts[ndex2].y, xy.y)) { + if (closest[index] == ndex2) { assert(flipIndex < 4); flipCheck[flipIndex++] = ndex2; matches[ndex2] = true; - goto next; + goto next2; } } if (--i.fUsed > index) { memmove(&i.fT[0][index], &i.fT[0][index + 1], (i.fUsed - index) * sizeof(i.fT[0][0])); + memmove(&closest[index], &closest[index + 1], (i.fUsed - index) * sizeof(closest[0])); continue; } - next: + next2: ++index; } for (ndex2 = 0; ndex2 < i.fUsed2; ) { diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp index 799287ddfd..32888826a8 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -59,6 +59,12 @@ static void standardTestCases() { } static const Quadratic testSet[] = { +{{369.848602,145.680267}, {382.360413,121.298294}, {406.207703,121.298294}}, +{{369.961151,137.980698}, {383.970093,121.298294}, {406.213287,121.298294}}, +{{353.2948,194.351074}, {353.2948,173.767563}, {364.167572,160.819855}}, +{{360.416077,166.795715}, {370.126831,147.872162}, {388.635406,147.872162}}, +{{406.236359,121.254936}, {409.445679,121.254936}, {412.975952,121.789818}}, +{{406.235992,121.254936}, {425.705902,121.254936}, {439.71994,137.087616}}, {{369.8543701171875, 145.66734313964844}, {382.36788940429688, 121.28203582763672}, {406.21844482421875, 121.28203582763672}}, {{369.96469116210938, 137.96672058105469}, {383.97555541992188, 121.28203582763672}, {406.2218017578125, 121.28203582763672}}, @@ -129,8 +135,8 @@ static void coincidentTest() { for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) { double tt1 = intersections2.fT[0][pt]; double tt2 = intersections2.fT[1][pt]; - // SkASSERT(approximately_equal(intersections.fT[0][pt], tt1)); - // SkASSERT(approximately_equal(intersections.fT[1][pt], tt2)); + SkASSERT(approximately_equal(1, tt1) || approximately_zero(tt1)); + SkASSERT(approximately_equal(1, tt2) || approximately_zero(tt2)); } } } diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp index f16c332c69..7a95b2468c 100644 --- a/experimental/Intersection/QuarticRoot.cpp +++ b/experimental/Intersection/QuarticRoot.cpp @@ -155,7 +155,7 @@ static int cubicRootsX(double A, double B, double C, double D, double s[3]) { double r; double* roots = s; - if (R2MinusQ3 > -FLT_EPSILON / 10 && R2MinusQ3 < FLT_EPSILON / 10 ) { + if (approximately_zero_squared(R2MinusQ3)) { if (approximately_zero(R)) {/* one triple solution */ *roots++ = -adiv3; } else { /* one single and one double solution */ @@ -216,7 +216,7 @@ int quarticRoots(const double A, const double B, const double C, const double D, s[num++] = 0; return num; } - if (approximately_zero(A + B + C + D + E)) { // 1 is one root + if (approximately_zero_squared(A + B + C + D + E)) { // 1 is one root num = cubicRootsX(A, A + B, -(D + E), -E, s); // note that -C==A+B+D+E for (i = 0; i < num; ++i) { if (approximately_equal(s[i], 1)) { diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index d5b4d9ec15..ced59bab05 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -28,6 +28,7 @@ int gDebugMaxWindValue = SK_MaxS32; #define PRECISE_T_SORT 1 #define SORTABLE_CONTOURS 0 // set to 1 for old code that works most of the time #define PIN_ADD_T 0 +#define TRY_ROTATE 1 #define DEBUG_UNUSED 0 // set to expose unused functions #define FORCE_RELEASE 0 @@ -1346,8 +1347,16 @@ public: && xyAtT(&span[-1]) == xyAtT(span)) { span[-1].fTiny = true; span[-1].fDone = true; - span[-1].fUnsortableStart = approximately_negative(newT - span[-1].fT) - && approximately_greater_than_one(newT); + if (approximately_negative(newT - span[-1].fT)) { + if (approximately_greater_than_one(newT)) { + span[-1].fUnsortableStart = true; + span[-2].fUnsortableEnd = true; + } + if (approximately_less_than_zero(span[-1].fT)) { + span->fUnsortableStart = true; + span[-1].fUnsortableEnd = true; + } + } ++fDoneSpans; } if (fTs.end() - span > 1 && !span->fDone @@ -1356,8 +1365,16 @@ public: && xyAtT(&span[1]) == xyAtT(span)) { span->fTiny = true; span->fDone = true; - span->fUnsortableEnd = approximately_negative(span[1].fT - newT) - && approximately_less_than_zero(newT); + if (approximately_negative(span[1].fT - newT)) { + if (approximately_greater_than_one(span[1].fT)) { + span->fUnsortableStart = true; + span[-1].fUnsortableEnd = true; + } + if (approximately_less_than_zero(newT)) { + span[1].fUnsortableStart = true; + span->fUnsortableEnd = true; + } + } ++fDoneSpans; } return insertedAt; @@ -4175,11 +4192,10 @@ static void debugShowQuadLineIntersection(int pts, const Work& wt, const Work& wn, const double wtTs[2], const double wnTs[2]) { if (!pts) { SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", + " (%1.9g,%1.9g %1.9g,%1.9g)\n", __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY ); + wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); return; } SkPoint wtOutPt, wnOutPt; @@ -4191,13 +4207,15 @@ static void debugShowQuadLineIntersection(int pts, const Work& wt, wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, wtOutPt.fX, wtOutPt.fY); if (pts == 2) { - SkDebugf(" wtTs[1]=%1.9g", wtTs[1]); + QuadXYAtT(wt.pts(), wtTs[1], &wtOutPt); + SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY); } SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); if (pts == 2) { - SkDebugf(" wnTs[1]=%1.9g", wnTs[1]); + LineXYAtT(wn.pts(), wnTs[1], &wnOutPt); + SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY); } SkDebugf("\n"); } @@ -4210,7 +4228,7 @@ static void debugShowQuadIntersection(int pts, const Work& wt, __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY ); + wn.pts()[2].fX, wn.pts()[2].fY ); return; } SkPoint wtOutPt, wnOutPt; @@ -4349,8 +4367,8 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kQuad_Segment: { swap = true; pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); - debugShowQuadLineIntersection(pts, wt, wn, - ts.fT[1], ts.fT[0]); + debugShowQuadLineIntersection(pts, wn, wt, + ts.fT[0], ts.fT[1]); break; } case Work::kCubic_Segment: { @@ -4375,13 +4393,13 @@ static bool addIntersectTs(Contour* test, Contour* next) { case Work::kLine_Segment: { pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); debugShowQuadLineIntersection(pts, wt, wn, - ts.fT[1], ts.fT[0]); + ts.fT[0], ts.fT[1]); break; } case Work::kQuad_Segment: { pts = QuadIntersect(wt.pts(), wn.pts(), ts); debugShowQuadIntersection(pts, wt, wn, - ts.fT[1], ts.fT[0]); + ts.fT[0], ts.fT[1]); break; } case Work::kCubic_Segment: { @@ -4695,7 +4713,8 @@ static Segment* findUndone(SkTDArray& contourList, int& start, int& en static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, int contourWinding) { while (chase.count()) { - Span* span = chase[chase.count() - 1]; + Span* span; + chase.pop(&span); const Span& backPtr = span->fOther->span(span->fOtherIndex); Segment* segment = backPtr.fOther; tIndex = backPtr.fOtherIndex; @@ -4705,10 +4724,14 @@ static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, Angle* last = angles.end() - 1; tIndex = last->start(); endIndex = last->end(); + #if TRY_ROTATE + *chase.insert(0) = span; + #else + *chase.append() = span; + #endif return last->segment(); } if (done == angles.count()) { - chase.pop(&span); continue; } SkTDArray sorted; @@ -4717,7 +4740,6 @@ static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); #endif if (!sortable) { - chase.pop(&span); continue; } // find first angle, initialize winding to computed fWindSum @@ -4781,6 +4803,11 @@ static Segment* findChase(SkTDArray& chase, int& tIndex, int& endIndex, break; } } while (++nextIndex != lastIndex); + #if TRY_ROTATE + *chase.insert(0) = span; + #else + *chase.append() = span; + #endif return segment; } return NULL; @@ -4921,7 +4948,7 @@ static bool bridgeWinding(SkTDArray& contourList, PathWrapper& simple) Segment* next = current->findNextWinding(chaseArray, active, nextStart, nextEnd, winding, spanWinding, unsortable); if (!next) { - if (active && simple.hasMove() + if (active && !unsortable && simple.hasMove() && current->verb() != SkPath::kLine_Verb && !simple.isClosed()) { current->addCurveTo(index, endIndex, simple, true); @@ -4941,7 +4968,7 @@ static bool bridgeWinding(SkTDArray& contourList, PathWrapper& simple) int min = SkMin32(index, endIndex); if (!current->done(min)) { current->addCurveTo(index, endIndex, simple, true); - current->markDone(SkMin32(index, endIndex), spanWinding); + current->markDone(SkMin32(index, endIndex), winding ? winding : spanWinding); } closable = false; } @@ -5042,7 +5069,7 @@ static void makeContourList(SkTArray& contours, } static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { - return approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY); + return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); } /* @@ -5060,78 +5087,106 @@ static void assemble(const PathWrapper& path, PathWrapper& simple) { EdgeBuilder builder(path, contours); builder.finish(); int count = contours.count(); - int oIndex; + int outer; SkTDArray runs; // indices of partial contours - for (oIndex = 0; oIndex < count; ++oIndex) { - const Contour& eContour = contours[oIndex]; + for (outer = 0; outer < count; ++outer) { + const Contour& eContour = contours[outer]; const SkPoint& eStart = eContour.start(); const SkPoint& eEnd = eContour.end(); if (approximatelyEqual(eStart, eEnd)) { eContour.toPath(simple); continue; } - *runs.append() = oIndex; + *runs.append() = outer; } count = runs.count(); + if (count == 0) { + return; + } SkTDArray sLink, eLink; sLink.setCount(count); eLink.setCount(count); + SkTDArray sBest, eBest; + sBest.setCount(count); + eBest.setCount(count); int rIndex; for (rIndex = 0; rIndex < count; ++rIndex) { - sLink[rIndex] = eLink[rIndex] = INT_MAX; + outer = runs[rIndex]; + const Contour& oContour = contours[outer]; + const SkPoint& oStart = oContour.start(); + const SkPoint& oEnd = oContour.end(); + double dx = oEnd.fX - oStart.fX; + double dy = oEnd.fY - oStart.fY; + double dist = dx * dx + dy * dy; + sBest[rIndex] = eBest[rIndex] = dist; + sLink[rIndex] = eLink[rIndex] = rIndex; } for (rIndex = 0; rIndex < count - 1; ++rIndex) { - oIndex = runs[rIndex]; - const Contour& oContour = contours[oIndex]; + outer = runs[rIndex]; + const Contour& oContour = contours[outer]; const SkPoint& oStart = oContour.start(); const SkPoint& oEnd = oContour.end(); - for (int inner = rIndex + 1; inner < count; ++inner) { - int iIndex = runs[inner]; - const Contour& iContour = contours[iIndex]; + double bestStartDist = sBest[rIndex]; + double bestEndDist = eBest[rIndex]; + for (int iIndex = rIndex + 1; iIndex < count; ++iIndex) { + int inner = runs[iIndex]; + const Contour& iContour = contours[inner]; const SkPoint& iStart = iContour.start(); const SkPoint& iEnd = iContour.end(); - if (approximatelyEqual(oStart, iStart)) { - SkASSERT(sLink[rIndex] == INT_MAX); + double dx = iStart.fX - oStart.fX; + double dy = iStart.fY - oStart.fY; + double dist = dx * dx + dy * dy; + if (bestStartDist > dist) { + bestStartDist = dist; sLink[rIndex] = ~iIndex; - SkASSERT(sLink[iIndex] == INT_MAX); sLink[iIndex] = ~rIndex; - } else if (approximatelyEqual(oStart, iEnd)) { - SkASSERT(sLink[rIndex] == INT_MAX); + } + dx = iEnd.fX - oStart.fX; + dy = iEnd.fY - oStart.fY; + dist = dx * dx + dy * dy; + if (bestStartDist > dist) { + bestStartDist = dist; sLink[rIndex] = iIndex; - SkASSERT(eLink[iIndex] == INT_MAX); eLink[iIndex] = rIndex; } - if (approximatelyEqual(oEnd, iStart)) { - SkASSERT(eLink[rIndex] == INT_MAX); - eLink[rIndex] = iIndex; - SkASSERT(sLink[iIndex] == INT_MAX); + dx = iStart.fX - oEnd.fX; + dy = iStart.fY - oEnd.fY; + dist = dx * dx + dy * dy; + if (bestEndDist > dist) { + bestEndDist = dist; sLink[iIndex] = rIndex; - } else if (approximatelyEqual(oEnd, iEnd)) { - SkASSERT(eLink[rIndex] == INT_MAX); - eLink[rIndex] = ~iIndex; - SkASSERT(eLink[iIndex] == INT_MAX); + eLink[rIndex] = iIndex; + } + dx = iEnd.fX - oEnd.fX; + dy = iEnd.fY - oEnd.fY; + dist = dx * dx + dy * dy; + if (bestEndDist > dist) { + bestEndDist = dist; eLink[iIndex] = ~rIndex; + eLink[rIndex] = ~iIndex; } - } + } } rIndex = 0; bool forward = true; bool first = true; const SkPoint* startPtr; int sIndex = sLink[rIndex]; + SkASSERT(sIndex != INT_MAX); + sLink[rIndex] = INT_MAX; + int eIndex; if (sIndex < 0) { - SkASSERT(sLink[~sIndex] != INT_MAX); + eIndex = sLink[~sIndex]; sLink[~sIndex] = INT_MAX; } else { - SkASSERT(eLink[sIndex] != INT_MAX); + eIndex = eLink[sIndex]; eLink[sIndex] = INT_MAX; } - SkASSERT(sLink[rIndex] != INT_MAX); - sLink[rIndex] = INT_MAX; + SkASSERT(eIndex != INT_MAX); do { do { - oIndex = runs[rIndex]; - const Contour& contour = contours[oIndex]; + outer = runs[rIndex]; + const Contour& contour = contours[outer]; if (first) { startPtr = &contour.start(); first = false; @@ -5145,38 +5200,35 @@ static void assemble(const PathWrapper& path, PathWrapper& simple) { contour.toPartialBackward(simple); endPtr = &contour.start(); } - if (approximatelyEqual(*startPtr, *endPtr)) { + if (sIndex == eIndex) { simple.close(); first = forward = true; break; } - int newRIndex; if (forward) { - newRIndex = eLink[rIndex]; - SkASSERT(newRIndex != INT_MAX); - SkASSERT(eLink[rIndex] != INT_MAX); + eIndex = eLink[rIndex]; + SkASSERT(eIndex != INT_MAX); eLink[rIndex] = INT_MAX; - if (newRIndex >= 0) { - SkASSERT(sLink[newRIndex] == rIndex); - sLink[newRIndex] = INT_MAX; + if (eIndex >= 0) { + SkASSERT(sLink[eIndex] == rIndex); + sLink[eIndex] = INT_MAX; } else { - SkASSERT(eLink[~newRIndex] == ~rIndex); - eLink[~newRIndex] = INT_MAX; + SkASSERT(eLink[~eIndex] == ~rIndex); + eLink[~eIndex] = INT_MAX; } } else { - newRIndex = sLink[rIndex]; - SkASSERT(newRIndex != INT_MAX); - SkASSERT(sLink[rIndex] != INT_MAX); + eIndex = sLink[rIndex]; + SkASSERT(eIndex != INT_MAX); sLink[rIndex] = INT_MAX; - if (newRIndex >= 0) { - SkASSERT(eLink[newRIndex] == rIndex); - eLink[newRIndex] = INT_MAX; + if (eIndex >= 0) { + SkASSERT(eLink[eIndex] == rIndex); + eLink[eIndex] = INT_MAX; } else { - SkASSERT(sLink[~newRIndex] == ~rIndex); - sLink[~newRIndex] = INT_MAX; + SkASSERT(sLink[~eIndex] == ~rIndex); + sLink[~eIndex] = INT_MAX; } } - rIndex = newRIndex; + rIndex = eIndex; if (rIndex < 0) { forward ^= 1; rIndex = ~rIndex; @@ -5223,6 +5275,9 @@ void simplifyx(const SkPath& path, SkPath& result) { fixOtherTIndex(contourList); #if !SORTABLE_CONTOURS sortSegments(contourList); +#endif +#if DEBUG_ACTIVE_SPANS + debugShowActiveSpans(contourList); #endif // construct closed contours if (builder.xorMask() == kWinding_Mask diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm index a6d2be9e26..43dceb4757 100644 --- a/experimental/Intersection/as.htm +++ b/experimental/Intersection/as.htm @@ -92,11 +92,89 @@ debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442 debugShowActiveSpans id=21 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=20 otherT=1 otherIndex=3 windSum=? windValue=1 +
+debugShowQuadIntersection wtTs[0]=0 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (369.863983,145.645813) wnTs[0]=1 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (412.975952,121.789818) +debugShowQuadLineIntersection wtTs[0]=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (406.236359,121.254936) wnTs[0]=0 (412.975952,121.789818 369.863983,145.645813) (412.975952,121.789818) +debugShowQuadLineIntersection wtTs[0]=0 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (406.236359,121.254936) wnTs[0]=1 (412.975952,121.789818 369.863983,145.645813) (369.863983,145.645813) +debugShowQuadIntersection no intersect (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) +debugShowQuadIntersection no intersect (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) +debugShowQuadLineIntersection wtTs[0]=0.934062756 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (403.139679,121.360977) wnTs[0]=0.17423 (439.71994,137.087616 369.970581,137.94342) (427.567535,137.236725) +debugShowQuadIntersection wtTs[0]=9.61225644e-05 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (406.236969,121.254936) wnTs[0]=0.000495996 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (406.25531,121.254944) +debugShowQuadLineIntersection no intersect (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (412.975952,121.789818 369.863983,145.645813) +debugShowQuadLineIntersection no intersect (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (412.975952,121.789818 369.863983,145.645813) +debugShowQuadIntersection wtTs[0]=0 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (369.970581,137.94342) wnTs[0]=1 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (439.71994,137.087616) +debugShowQuadLineIntersection wtTs[0]=1 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (406.235992,121.254936) wnTs[0]=0 (439.71994,137.087616 369.970581,137.94342) (439.71994,137.087616) +debugShowQuadLineIntersection wtTs[0]=0 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (406.235992,121.254936) wnTs[0]=1 (439.71994,137.087616 369.970581,137.94342) (369.970581,137.94342) +
+ +
+debugShowActiveSpans id=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) t=0 (369.863983,145.645813) other=3 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) t=0.174229721 (374.569672,137.886993) other=6 otherT=0.934062756 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=2 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) t=0 (406.236359,121.254936) other=1 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=2 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) t=0.000495995847 (406.239532,121.254936) other=5 otherT=9.61225644e-05 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (412.975952,121.789818 369.863983,145.645813) t=0 (412.975952,121.789818) other=2 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=3 (412.975952,121.789818 369.863983,145.645813) t=0.669864243 (384.096771,137.770096) other=6 otherT=0.797471908 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) t=0 (369.970581,137.94342) other=6 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=5 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) t=0 (406.235992,121.254936) other=4 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=5 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) t=9.61225644e-05 (406.239746,121.254936) other=2 otherT=0.000495995847 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0 (439.71994,137.087616) other=5 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0.797471908 (384.096771,137.770096) other=3 otherT=0.669864243 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0.934062756 (374.569672,137.886993) other=1 otherT=0.174229721 otherIndex=1 windSum=? windValue=1 +
+ +
+debugShowActiveSpans id=1 (360.416077,166.795715 370.126831,147.872162 388.635406,147.872162) t=0 (360.416077,166.795715) other=2 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=2 (388.635406,147.872162 360.416077,166.795715) t=0 (388.635406,147.872162) other=1 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=2 (388.635406,147.872162 360.416077,166.795715) t=0.00925761141 (388.374176,148.047348) other=4 otherT=0.883679938 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (353.2948,194.351074 353.2948,173.767563 364.167572,160.819855) t=0 (353.2948,194.351074) other=5 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (364.167572,160.819855 375.040314,147.872162 392.303894,147.872162) t=0 (364.167572,160.819855) other=3 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (364.167572,160.819855 375.040314,147.872162 392.303894,147.872162) t=0.883679938 (388.374176,148.047348) other=2 otherT=0.00925761141 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=5 (392.303894,147.872162 353.2948,194.351074) t=0 (392.303894,147.872162) other=4 otherT=1 otherIndex=2 windSum=? windValue=1 +
+ +
+debugShowActiveSpans id=1 (348.781738,123.864815 369.848602,123.864815) t=0 (348.781738,123.864815) other=4 otherT=1 otherIndex=4 windSum=? windValue=1 +debugShowActiveSpans id=2 (369.848602,123.864815 369.848602,145.680267) t=0 (369.848602,123.864815) other=1 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0 (369.848602,145.680267) other=2 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.258355433 (377.070221,134.709274) other=6 otherT=0.8038997 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.914354357 (402.206024,121.477142) other=4 otherT=0.0696842495 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.999082394 (406.16394,121.298317) other=5 otherT=0.998890674 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=1.0265934e-07 (406.207703,121.298294) other=5 otherT=0.999874327 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=0.0696842495 (402.206024,121.477142) other=3 otherT=0.914354357 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=0.0881931013 (401.143127,121.524643) other=5 otherT=0.883517581 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0 (369.961151,137.980698) other=6 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.883517581 (401.143127,121.524643) other=4 otherT=0.0881931013 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.998890674 (406.16394,121.298317) other=3 otherT=0.999082394 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.999874327 (406.207703,121.298294) other=4 otherT=1.0265934e-07 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=6 (406.213287,121.298294 369.961151,137.980698) t=0 (406.213287,121.298294) other=5 otherT=1 otherIndex=4 windSum=? windValue=1 +debugShowActiveSpans id=6 (406.213287,121.298294 369.961151,137.980698) t=0.8038997 (377.070221,134.709274) other=3 otherT=0.258355433 otherIndex=1 windSum=? windValue=1 +
+ +
+debugShowQuadLineIntersection wtTs[0]=0.914354357 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (402.206024,121.477142) wtTs[1]=1 (406.207703,121.298294) wnTs[0]=0.0696842 (406.207703,121.298294 348.781738,123.864815) (402.206024,121.477142) wnTs[1]=0 (406.207703,121.298294) +debugShowQuadIntersection wtTs[0]=0.999082394 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (406.16394,121.298317) wnTs[0]=0.998891 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (406.16394,121.298317) +debugShowQuadLineIntersection wtTs[0]=0.258355433 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (377.070221,134.709274) wnTs[0]=0.8039 (406.213287,121.298294 369.961151,137.980698) (377.070221,134.709274) +debugShowQuadLineIntersection wtTs[0]=0.883517581 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (401.143127,121.524643) wtTs[1]=0.999874327 (406.207703,121.298294) wnTs[0]=0.0881931 (406.207703,121.298294 348.781738,123.864815) (401.143127,121.524643) wnTs[1]=1.0265934e-07 (406.207703,121.298294) +debugShowQuadLineIntersection wtTs[0]=0 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (369.961151,137.980698) wtTs[1]=1 (406.213287,121.298294) wnTs[0]=1 (406.213287,121.298294 369.961151,137.980698) (369.961151,137.980698) wnTs[1]=0 (406.213287,121.298294) +
+ +
+debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.914354357 (402.206024,121.477142) other=4 otherT=0.0696842495 otherIndex=2 windSum=-1 windValue=1 +debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=1.0265934e-07 (406.207703,121.298294) other=5 otherT=0.999874327 otherIndex=3 windSum=-1 windValue=1 +debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.998890674 (406.16394,121.298317) other=3 otherT=0.999082394 otherIndex=3 windSum=-1 windValue=1 +
+