From 752b60e633a349c5b9f7bcc6a28b8064fc77bb41 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Thu, 22 Mar 2012 21:11:17 +0000 Subject: work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@3471 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/EdgeWalker.cpp | 235 ++++++++++++-------- .../Intersection/EdgeWalkerPolygons_Test.cpp | 143 +++++++++++- experimental/Intersection/EdgeWalker_Test.h | 2 +- .../Intersection/EdgeWalker_TestUtility.cpp | 37 +++- .../Intersection/edge.xcodeproj/project.pbxproj | 12 + experimental/Intersection/op.htm | 244 +++++++++++++++++++++ 6 files changed, 561 insertions(+), 112 deletions(-) create mode 100644 experimental/Intersection/op.htm (limited to 'experimental/Intersection') diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index e33fd94681..94d6e5a2a9 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -22,13 +22,14 @@ static bool gShowDebugf = false; // FIXME: remove once debugging is complete #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_ADD_BOTTOM_TS 0 #define COMPARE_DOUBLE 0 -#define ASSERT_ON_ULPS 0 #define DEBUG_ABOVE_BELOW 0 #define DEBUG_ACTIVE_LESS_THAN 0 #define DEBUG_SORT_HORIZONTAL 0 #define DEBUG_OUT 0 #define DEBUG_OUT_LESS_THAN 0 #define DEBUG_ADJUST_COINCIDENT 0 +#define DEBUG_BOTTOM 0 + #else static bool gShowDebugf = true; // FIXME: remove once debugging is complete @@ -36,14 +37,15 @@ static bool gShowDebugf = true; // FIXME: remove once debugging is complete #define DEBUG_ADD 01 #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_ADD_BOTTOM_TS 0 -#define COMPARE_DOUBLE 0 -#define ASSERT_ON_ULPS 0 +#define COMPARE_DOUBLE 01 #define DEBUG_ABOVE_BELOW 01 -#define DEBUG_ACTIVE_LESS_THAN 0 +#define DEBUG_ACTIVE_LESS_THAN 01 #define DEBUG_SORT_HORIZONTAL 01 #define DEBUG_OUT 01 #define DEBUG_OUT_LESS_THAN 0 #define DEBUG_ADJUST_COINCIDENT 1 +#define DEBUG_BOTTOM 01 + #endif // FIXME: not wild about this -- min delta should be based on size of curve, not t @@ -193,7 +195,7 @@ struct OutEdge { ? first.fX < rhFirst.fX : first.fY < rhFirst.fY; } - + SkPoint fPts[4]; int fID; // id of edge generating data uint8_t fVerb; // FIXME: not read from everywhere @@ -214,7 +216,7 @@ public: newEdge.fID = id; newEdge.fCloseCall = closeCall; } - + bool trimLine(SkScalar y, int id) { size_t count = fEdges.count(); while (count-- != 0) { @@ -349,7 +351,7 @@ public: } while (edgeIndex); } while (true); } - + // sort points by y, then x // if x/y is identical, sort bottoms before tops // if identical and both tops/bottoms, sort by angle @@ -504,7 +506,7 @@ struct Bounds : public SkRect { return a.fLeft <= b.fRight && b.fLeft <= a.fRight && a.fTop <= b.fBottom && b.fTop <= a.fBottom; } - + bool isEmpty() { return fLeft > fRight || fTop > fBottom || fLeft == fRight && fTop == fBottom @@ -519,7 +521,7 @@ public: : fTopIntercepts(0) , fBottomIntercepts(0) { } - + #if DEBUG_DUMP // FIXME: pass current verb as parameter void dump(const SkPoint* pts) { @@ -528,7 +530,7 @@ public: for (int i = 0; i < fTs.count(); ++i) { SkPoint out; LineXYAtT(pts, fTs[i], &out); - SkDebugf("%*s.fTs[%d]=%g (%g,%g)\n", tab + sizeof(className), + SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className), className, i, fTs[i], out.fX, out.fY); } SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className), @@ -553,9 +555,9 @@ struct HorizontalEdge { void dump() { const char className[] = "HorizontalEdge"; const int tab = 4; - SkDebugf("%*s.fLeft=%g\n", tab + sizeof(className), className, fLeft); - SkDebugf("%*s.fRight=%g\n", tab + sizeof(className), className, fRight); - SkDebugf("%*s.fY=%g\n", tab + sizeof(className), className, fY); + SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft); + SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight); + SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY); } #endif @@ -682,14 +684,14 @@ struct InEdge { pts += *verbs++; } for (i = 0; i < fPts.count(); ++i) { - SkDebugf("%*s.fPts[%d]=(%g,%g)\n", tab + sizeof(className), + SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className), className, i, fPts[i].fX, fPts[i].fY); } for (i = 0; i < fVerbs.count(); ++i) { SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className), className, i, fVerbs[i]); } - SkDebugf("%*s.fBounds=(%g. %g, %g, %g)\n", tab + sizeof(className), + SkDebugf("%*s.fBounds=(%1.9g. %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className), className, fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className, @@ -861,7 +863,7 @@ struct WorkEdge { fPts += *fVerb++; return fVerb != fEdge->fVerbs.end(); } - + SkPath::Verb lastVerb() const { SkASSERT(fVerb > fEdge->fVerbs.begin()); return (SkPath::Verb) fVerb[-1]; @@ -875,7 +877,7 @@ struct WorkEdge { ptrdiff_t verbIndex() const { return fVerb - fEdge->fVerbs.begin(); } - + int winding() const { return fEdge->fWinding; } @@ -903,12 +905,6 @@ public: const SkPoint& check = rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? rh.fBelow : rh.fAbove; - #if COMPARE_DOUBLE - SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) - < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)) - == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x) - < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x))); - #endif #if DEBUG_ACTIVE_LESS_THAN SkDebugf("%s 1 %c %cthis (edge=%d) {%g,%g %g,%g}" " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, @@ -920,10 +916,11 @@ public: UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX))); #endif - #if ASSERT_ON_ULPS - int ulps = UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), - (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)); - SkASSERT((unsigned) ulps == 0x80000000 || ulps == 0 || ulps > 32); + #if COMPARE_DOUBLE + SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) + < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)) + == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x) + < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x))); #endif return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX); @@ -931,32 +928,28 @@ public: // FIXME: need to compute distance, not check for points equal const SkPoint& check = fBelow.fY <= rh.fBelow.fY && fBelow != rh.fBelow ? fBelow : fAbove; - #if COMPARE_DOUBLE - SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) - < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)) - == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x) - < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x))); - #endif #if DEBUG_ACTIVE_LESS_THAN SkDebugf("%s 2 %c %cthis (edge=%d) {%g,%g %g,%g}" - " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, - fBelow.fY <= rh.fBelow.fY & fBelow != rh.fBelow ? 'B' : 'A', + " < rh (edge=%d) {%g,%g %g,%g} upls=(%d) (%d,%d)\n", __FUNCTION__, + fBelow.fY <= rh.fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX) ? ' ' : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, UlpsDiff((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), - (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX))); + (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)), + UlpsDiff(fBelow.fX, rh.fBelow.fX), UlpsDiff(fBelow.fY, rh.fBelow.fY)); #endif - #if ASSERT_ON_ULPS - int ulps = UlpsDiff((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), - (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)); - SkASSERT((unsigned) ulps == 0x80000000 || ulps == 0 || ulps > 32); + #if COMPARE_DOUBLE + SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) + < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)) + == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x) + < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x))); #endif return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); } - + // If a pair of edges are nearly coincident for some span, add a T in the // edge so it can be shortened to match the other edge. Note that another // approach is to trim the edge after it is added to the OutBuilder list -- @@ -969,7 +962,7 @@ public: addTatYInner(y); fFixBelow = true; } - + void addTatYAbove(SkScalar y) { if (fBelow.fY <= y) { return; @@ -978,12 +971,15 @@ public: } void addTatYInner(SkScalar y) { - double ts[2]; + if (fWorkEdge.fPts[0].fY > y) { + backup(y); + } SkScalar left = fWorkEdge.fPts[0].fX; SkScalar right = fWorkEdge.fPts[1].fX; if (left > right) { SkTSwap(left, right); } + double ts[2]; int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts); SkASSERT(pts == 1); // An ActiveEdge or WorkEdge has no need to modify the T values computed @@ -993,6 +989,9 @@ public: // an additional t value must be added, requiring the cast below. InEdge* writable = const_cast(fWorkEdge.fEdge); int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex()); + #if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); + #endif if (insertedAt >= 0) { if (insertedAt + 1 < fTIndex) { SkASSERT(insertedAt + 2 == fTIndex); @@ -1013,15 +1012,29 @@ public: initT(); return result; } - + + void backup(SkScalar y) { + do { + SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb); + fWorkEdge.fPts -= *--fWorkEdge.fVerb; + SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); + } while (fWorkEdge.fPts[0].fY >= y); + initT(); + fTIndex = fTs->count() + 1; + } + void calcLeft(SkScalar y) { // OPTIMIZE: put a kDone_Verb at the end of the verb list? if (fDone || fBelow.fY > y) { return; // nothing to do; use last } calcLeft(); + if (fAbove.fY == fBelow.fY) { + SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, + ID(), fAbove.fY); + } } - + void calcLeft() { switch (fWorkEdge.verb()) { case SkPath::kLine_Verb: { @@ -1036,14 +1049,19 @@ public: double tBelow = t(fTIndex - ~add); LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); SkASSERT(tAbove != tBelow); -// maybe the following is the right sort of thing to do, but it's fragile and -// it breaks testSimplifySkinnyTriangle4 -#if 0 - if (fAbove == fBelow && !add) { - tBelow = t(fTIndex - ~add + 1); - LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); + while (fAbove.fY == fBelow.fY) { + if (add < 0) { + add -= 1; + SkASSERT(fTIndex + add >= 0); + tAbove = t(fTIndex + add); + LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); + } else { + add += 1; + SkASSERT(fTIndex - ~add <= fTs->count() + 1); + tBelow = t(fTIndex - ~add); + LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); + } } -#endif #if COMPARE_DOUBLE LineXYAtT(fWorkEdge.fPts, tAbove, &fDAbove); LineXYAtT(fWorkEdge.fPts, tBelow, &fDBelow); @@ -1060,10 +1078,10 @@ public: } } - bool done(SkScalar y) const { - return fDone || fYBottom > y; + bool done(SkScalar bottom) const { + return fDone || fYBottom >= bottom; } - + void fixBelow() { if (fFixBelow) { LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow); @@ -1078,7 +1096,7 @@ public: fDone = false; fYBottom = SK_ScalarMin; } - + void initT() { const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); @@ -1089,13 +1107,13 @@ public: // but templated arrays don't allow returning a pointer to the end() element fTIndex = 0; } - + // OPTIMIZATION: record if two edges are coincident when the are intersected // It's unclear how to do this -- seems more complicated than recording the // t values, since the same t values could exist intersecting non-coincident // edges. bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const { - + if (!fAbove.equalsWithinTolerance(edge->fAbove, MIN_PT_DELTA) || !fBelow.equalsWithinTolerance(edge->fBelow, MIN_PT_DELTA)) { return false; @@ -1116,7 +1134,7 @@ public: } return false; } - + // The shortest close call edge should be moved into a position where // it contributes if the winding is transitioning to or from zero. bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const { @@ -1129,7 +1147,7 @@ public: } return false; } - + bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { if (fBelow.fY >= bottom || fDone || edge->fDone) { return false; @@ -1149,7 +1167,7 @@ public: } return false; } - + bool tooCloseToCall(const ActiveEdge* edge) const { int ulps; // FIXME: don't compare points for equality @@ -1200,7 +1218,7 @@ public: } // FIXME: debugging only - int ID() { + int ID() const { return fWorkEdge.fEdge->fID; } @@ -1288,6 +1306,9 @@ static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { InEdge** testPtr = currentPtr - 1; + // FIXME: lastPtr should be past the point of interest, so + // test below should be lastPtr - 2 + // that breaks testSimplifyTriangle22, so further investigation is needed while (++testPtr != lastPtr - 1) { InEdge* test = *testPtr; InEdge** nextPtr = testPtr; @@ -1423,7 +1444,7 @@ static SkScalar findBottom(InEdge** currentPtr, bool asFill, InEdge**& testPtr) { InEdge* current = *currentPtr; SkScalar bottom = current->fBounds.fBottom; - + // find the list of edges that cross y InEdge* test = *testPtr; while (testPtr != edgeListEnd) { @@ -1487,8 +1508,14 @@ static void skipCoincidence(int lastWinding, int winding, int windingMask, } // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? if (lastWinding) { +#if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()); +#endif activePtr->fSkip = false; } else { +#if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID()); +#endif firstCoincident->fSkip = false; } } @@ -1613,21 +1640,37 @@ static SkScalar adjustCoincident(SkTDArray& edgeList, // coincident edge, trim it back to the top of this span if (outBuilder.trimLine(y, activePtr->ID())) { activePtr->addTatYAbove(y); + #if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", + __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom); + #endif activePtr->fYBottom = y; } if (outBuilder.trimLine(y, nextPtr->ID())) { nextPtr->addTatYAbove(y); + #if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", + __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom); + #endif nextPtr->fYBottom = y; } // add missing t values so edges can be the same length SkScalar testY = activePtr->fBelow.fY; nextPtr->addTatYBelow(testY); if (bottom > testY && testY > y) { + #if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", + __FUNCTION__, activePtr->ID(), testY, bottom); + #endif bottom = testY; } testY = nextPtr->fBelow.fY; activePtr->addTatYBelow(testY); if (bottom > testY && testY > y) { + #if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", + __FUNCTION__, nextPtr->ID(), testY, bottom); + #endif bottom = testY; } } @@ -1654,7 +1697,7 @@ static SkScalar adjustCoincident(SkTDArray& edgeList, // stitch edge and t range that satisfies operation static void stitchEdge(SkTDArray& edgeList, SkScalar y, - SkScalar bottom, int windingMask, OutEdgeBuilder& outBuilder) { + SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) { int winding = 0; ActiveEdge** activeHandle = edgeList.begin() - 1; ActiveEdge** lastActive = edgeList.end(); @@ -1680,31 +1723,12 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, #endif ); } - if (activePtr->done(y)) { - if (activePtr->fCloseCall) { - // if the top has already advanced, trim the last edge add - // FIXME: not so simple - outBuilder.trimLine(y, activePtr->ID()); - activePtr->fYBottom = y; - } - // FIXME: if this is successful, rewrite done to take bottom as well - if (activePtr->fDone) { - if (gShowDebugf) { - SkDebugf("%*s activePtr->fDone\n", tab, ""); - } - continue; - } - if (activePtr->fYBottom >= bottom) { - if (gShowDebugf) { - SkDebugf("%*s activePtr->fYBottom=%1.9g >= bottom\n", tab, "", - activePtr->fYBottom); - } - continue; - } - if (0) { - SkDebugf("%s bot %1.9g,%1.9g\n", __FUNCTION__, activePtr->fYBottom, - bottom); + if (activePtr->done(bottom)) { + if (gShowDebugf) { + SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", + activePtr->fDone, activePtr->fYBottom); } + continue; } int opener = (lastWinding & windingMask) == 0; bool closer = (winding & windingMask) == 0; @@ -1748,7 +1772,8 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, dClipped = dPoints; #endif } - if (inWinding && !activePtr->fSkip) { + if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY + != clipped[1].fY : clipped[0] != clipped[1])) { if (gShowDebugf) { SkDebugf("%*s line %1.9g,%1.9g %1.9g,%1.9g edge=%d" " v=%d t=(%1.9g,%1.9g)\n", tab, "", @@ -1759,8 +1784,9 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, - activePtr->fWorkEdge.fEdge->fVerbs.begin(), currentT, nextT); } - outBuilder.addLine(clipped, activePtr->fWorkEdge.fEdge->fID, - activePtr->fCloseCall); + outBuilder.addLine(clipped, + activePtr->fWorkEdge.fEdge->fID, + activePtr->fCloseCall); } else { if (gShowDebugf) { SkDebugf("%*s skip %1.9g,%1.9g %1.9g,%1.9g" @@ -1819,8 +1845,16 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, // FIXME: initialized in sortHorizontal, cleared here as well so // that next edge is not skipped -- but should skipped edges ever // continue? (probably not) - aboveBottom = clipped[verb].fY < bottom && !activePtr->fCloseCall; // TEST: added close call - activePtr->fSkip = activePtr->fCloseCall = false; + aboveBottom = clipped[verb].fY < bottom; + if (clipped[0].fY != clipped[verb].fY) { + activePtr->fSkip = false; + activePtr->fCloseCall = false; + aboveBottom &= !activePtr->fCloseCall; + } else { + if (activePtr->fSkip || activePtr->fCloseCall) { + SkDebugf("== %1.9g\n", clippedPts[0].fY); + } + } } while (moreToDo & aboveBottom); } while ((moreToDo || activePtr->advance()) & aboveBottom); } @@ -1872,14 +1906,14 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { y = bottom; currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); } while (*currentPtr != &edgeSentinel); - + #if DEBUG_DUMP InEdge** debugPtr = edgeList.begin(); do { (*debugPtr++)->dump(); } while (*debugPtr != &edgeSentinel); #endif - + // walk the sorted edges from top to bottom, computing accumulated winding SkTDArray activeEdges; OutEdgeBuilder outBuilder(asFill); @@ -1889,13 +1923,22 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set SkScalar bottom = findBottom(currentPtr, edgeList.end(), &activeEdges, y, asFill, lastPtr); +#if DEBUG_BOTTOM + SkDebugf("%s findBottom bottom=%1.9g\n", __FUNCTION__, bottom); +#endif if (lastPtr > currentPtr) { bottom = computeInterceptBottom(activeEdges, y, bottom); +#if DEBUG_BOTTOM + SkDebugf("%s computeInterceptBottom bottom=%1.9g\n", __FUNCTION__, bottom); +#endif SkTDArray activeEdgeList; sortHorizontal(activeEdges, activeEdgeList, y); bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, outBuilder); - stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder); +#if DEBUG_BOTTOM + SkDebugf("%s adjustCoincident bottom=%1.9g\n", __FUNCTION__, bottom); +#endif + stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); } y = bottom; // OPTIMIZATION: as edges expire, InEdge allocations could be released diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp index 9a740e996b..3cc1b5d982 100644 --- a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp +++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp @@ -500,6 +500,12 @@ static void testPathTriangleRendering() { } } +static void simplify(const char* functionName, const SkPath& path, + bool fill, SkPath& out) { + SkDebugf("%s\n", functionName); + simplify(path, fill, out); +} + static void testSimplifySkinnyTriangle1() { for (int x = 1; x < 255; ++x) { SkPath path, out; @@ -518,7 +524,7 @@ static void testSimplifySkinnyTriangle1() { path.lineTo((x * 71) % 30, 2000); path.lineTo((x * 51) % 30, 3000); path.close(); - testSimplify(path, true, out); + simplify(path, true, out); } } @@ -546,7 +552,7 @@ path.lineTo(196.621033, 394.917633); //path.lineTo(289.392517, 517.138489); path.close(); #endif - testSimplify(path, true, out); + simplify(__FUNCTION__, path, true, out); } static void testSimplifySkinnyTriangle3() { @@ -561,7 +567,7 @@ static void testSimplifySkinnyTriangle3() { path.lineTo(416, 486.978577); path.lineTo(465, 430.970581); path.close(); - testSimplify(path, true, out); + simplify(__FUNCTION__, path, true, out); } static void testSimplifySkinnyTriangle4() { @@ -584,7 +590,7 @@ path.lineTo(210.344177, 437.315125); path.lineTo(197.019455, 383.794556); path.lineTo(278.742737, 508.065643); path.close(); - testSimplify(path, true, out); + simplify(__FUNCTION__, path, true, out); } static void testSimplifySkinnyTriangle5() { @@ -607,9 +613,31 @@ path.lineTo(203.059692, 441.332336); path.lineTo(195.994370, 386.856506); path.lineTo(271.998901, 521.301025); path.close(); - testSimplify(path, true, out); + simplify(__FUNCTION__, path, true, out); } +static void testSimplifySkinnyTriangle6() { + SkPath path, out; +path.moveTo(591.091064, 627.534851); +path.lineTo(541.088135, 560.707642); +path.lineTo(491.085175, 493.880310); +path.lineTo(441.082214, 427.053101); +path.lineTo(591.091064, 627.534851); +path.close(); +path.moveTo(317.093445, 592.013306); +path.lineTo(366.316162, 542.986572); +path.lineTo(416.051514, 486.978577); +path.lineTo(465.786865, 430.970581); +path.lineTo(317.093445, 592.013306); +path.close(); +path.moveTo(289.392517, 517.138489); +path.lineTo(249.886078, 508.598022); +path.lineTo(217.110916, 450.916443); +path.lineTo(196.621033, 394.917633); +path.lineTo(289.392517, 517.138489); +path.close(); + simplify(__FUNCTION__, path, true, out); +} static void testSimplifyTriangle22() { SkPath path, out; @@ -650,7 +678,107 @@ static void testSimplifyTriangle24() { testSimplify(path, true, out); } +static void testSimplifySkinnyTriangle7() { + SkPath path, out; +path.moveTo(487.502319, 550.811279); +path.lineTo(448.826050, 491.720123); +path.lineTo(410.149780, 432.628967); +path.lineTo(371.473572, 373.537781); +path.lineTo(487.502319, 550.811279); +path.close(); +path.moveTo(295.817108, 532.655579); +path.lineTo(342.896271, 485.912292); +path.lineTo(389.975433, 439.169006); +path.lineTo(437.054596, 392.425781); +path.lineTo(295.817108, 532.655579); +path.close(); +path.moveTo(239.726822, 575.025269); +path.lineTo(204.117569, 521.429688); +path.lineTo(171.275452, 454.110382); +path.lineTo(193.328583, 397.859497); +path.lineTo(239.726822, 575.025269); +path.close(); + simplify(__FUNCTION__, path, true, out); +} + +static void testSimplifySkinnyTriangle8() { + SkPath path, out; +path.moveTo(441.943115, 511.678040); +path.lineTo(408.487549, 456.880920); +path.lineTo(375.031952, 402.083801); +path.lineTo(341.576385, 347.286682); +path.lineTo(441.943115, 511.678040); +path.close(); +path.moveTo(297.548492, 557.246704); +path.lineTo(350.768494, 507.627014); +path.lineTo(403.988525, 458.007385); +path.lineTo(457.208527, 408.387695); +path.lineTo(297.548492, 557.246704); +path.close(); +path.moveTo(209.857895, 615.802979); +path.lineTo(178.249481, 534.230347); +path.lineTo(144.905640, 460.056824); +path.lineTo(192.953125, 404.972900); +path.lineTo(209.857895, 615.802979); +path.close(); + simplify(__FUNCTION__, path, true, out); +} + +static void testSimplifySkinnyTriangle9() { + SkPath path, out; +path.moveTo(439.867065, 528.291931); +path.lineTo(405.413025, 469.107178); +path.lineTo(370.958954, 409.922363); +path.lineTo(336.504883, 350.737610); +path.lineTo(439.867065, 528.291931); +path.close(); +path.moveTo(298.922455, 573.251953); +path.lineTo(356.360962, 521.905090); +path.lineTo(413.799438, 470.558228); +path.lineTo(471.237915, 419.211365); +path.lineTo(298.922455, 573.251953); +path.close(); +path.moveTo(187.200775, 643.035156); +path.lineTo(159.713165, 540.993774); +path.lineTo(126.257164, 462.198517); +path.lineTo(193.534012, 409.266235); +path.lineTo(187.200775, 643.035156); +path.close(); +path.close(); + simplify(__FUNCTION__, path, true, out); +} + +static void testSimplifySkinnyTriangle10() { + SkPath path, out; +#if 0 +path.moveTo(99.270325, 239.365234); +path.lineTo(105.967056, 173.361206); +path.lineTo(148.821381, 141.309891); +path.lineTo(159.101013, 189.235138); +path.lineTo(99.270325, 239.365234); +path.close(); +#endif +path.moveTo(213.673737, 413.292938); +path.lineTo(225.200134, 343.616821); +path.lineTo(236.726532, 273.940704); +path.lineTo(219.386414, 231.373322); +path.lineTo(213.673737, 413.292938); +path.close(); +path.moveTo(43.485352, 308.984497); +path.lineTo(122.610657, 305.950134); +path.lineTo(201.735962, 302.915802); +path.lineTo(280.861267, 299.881470); +path.lineTo(43.485352, 308.984497); +path.close(); + simplify(__FUNCTION__, path, true, out); +} + static void (*simplifyTests[])() = { + testSimplifySkinnyTriangle10, + testSimplifySkinnyTriangle9, + testSimplifySkinnyTriangle8, + testSimplifySkinnyTriangle7, + testSimplifySkinnyTriangle6, testSimplifySkinnyTriangle5, testSimplifySkinnyTriangle4, testSimplifySkinnyTriangle3, @@ -691,7 +819,7 @@ static void (*simplifyTests[])() = { static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); -static void (*firstTest)() = testSimplifySkinnyTriangle4; +static void (*firstTest)() = 0; void SimplifyPolygonPaths_Test() { size_t index = 0; @@ -703,6 +831,9 @@ void SimplifyPolygonPaths_Test() { bool firstTestComplete = false; for ( ; index < simplifyTestsCount; ++index) { (*simplifyTests[index])(); + if (simplifyTests[index] == testSimplifySkinnyTriangle2) { + SkDebugf("%s last fast skinny test\n", __FUNCTION__); + } firstTestComplete = true; } } diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index c449d1a4d8..c7f405b19d 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -5,7 +5,7 @@ extern void contourBounds(const SkPath& path, SkTDArray& boundsArray); extern bool comparePaths(const SkPath& one, const SkPath& two); extern void comparePathsTiny(const SkPath& one, const SkPath& two); -extern void drawAsciiPaths(const SkPath& one, const SkPath& two, +extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths); extern void simplify(const SkPath& path, bool asFill, SkPath& simple); extern void showPath(const SkPath& path, const char* str = NULL); diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index 84ca87fce3..fc69516c40 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -5,13 +5,14 @@ #include "SkPaint.h" static bool gShowPath = false; -static bool gDrawLastAsciiPaths = false; +static bool gComparePaths = false; +static bool gDrawLastAsciiPaths = true; static bool gDrawAllAsciiPaths = false; static bool gShowAsciiPaths = false; -static bool gComparePathsAssert = false; +static bool gComparePathsAssert = true; void showPath(const SkPath& path, const char* str) { - SkDebugf("%s\n", str ? "original:" : str); + SkDebugf("%s\n", !str ? "original:" : str); SkPath::Iter iter(path, true); uint8_t verb; SkPoint pts[4]; @@ -76,10 +77,10 @@ static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) { return true; } -void drawAsciiPaths(const SkPath& one, const SkPath& two, +bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths) { if (!drawPaths) { - return; + return true; } if (gShowAsciiPaths) { showPath(one, "one:"); @@ -90,8 +91,15 @@ void drawAsciiPaths(const SkPath& one, const SkPath& two, SkRect larger = bounds1; larger.join(bounds2); SkBitmap bits; + char out[256]; int bitWidth = SkScalarCeil(larger.width()) + 2; + if (bitWidth * 2 + 1 >= (int) sizeof(out)) { + return false; + } int bitHeight = SkScalarCeil(larger.height()) + 2; + if (bitHeight >= (int) sizeof(out)) { + return false; + } bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); bits.allocPixels(); SkCanvas canvas(bits); @@ -105,8 +113,6 @@ void drawAsciiPaths(const SkPath& one, const SkPath& two, canvas.translate(-bounds2.fLeft + 1 + bitWidth, -bounds2.fTop + 1); canvas.drawPath(two, paint); canvas.restore(); - char out[1024]; - SkASSERT(bitWidth * 2 + 1 < (int) sizeof(out)); for (int y = 0; y < bitHeight; ++y) { uint32_t* addr1 = bits.getAddr32(0, y); int x; @@ -121,20 +127,30 @@ void drawAsciiPaths(const SkPath& one, const SkPath& two, *outPtr++ = '\0'; SkDebugf("%s\n", out); } + return true; } static bool scaledDrawTheSame(const SkPath& one, const SkPath& two, int a, int b, bool drawPaths) { SkMatrix scale; scale.reset(); - scale.preScale(a * 1.21f, b * 1.11f); + float aScale = 1.21f; + float bScale = 1.11f; + scale.preScale(a * aScale, b * bScale); SkPath scaledOne, scaledTwo; one.transform(scale, &scaledOne); two.transform(scale, &scaledTwo); if (pathsDrawTheSame(scaledOne, scaledTwo)) { return true; } - drawAsciiPaths(scaledOne, scaledTwo, drawPaths); + while (!drawAsciiPaths(scaledOne, scaledTwo, drawPaths)) { + scale.reset(); + aScale *= 0.5f; + bScale *= 0.5f; + scale.preScale(a * aScale, b * bScale); + one.transform(scale, &scaledOne); + two.transform(scale, &scaledTwo); + } return false; } @@ -195,5 +211,8 @@ bool testSimplify(const SkPath& path, bool fill, SkPath& out) { showPath(path); } simplify(path, fill, out); + if (!gComparePaths) { + return true; + } return comparePaths(path, out); } diff --git a/experimental/Intersection/edge.xcodeproj/project.pbxproj b/experimental/Intersection/edge.xcodeproj/project.pbxproj index 1b520f199e..0cd951e386 100644 --- a/experimental/Intersection/edge.xcodeproj/project.pbxproj +++ b/experimental/Intersection/edge.xcodeproj/project.pbxproj @@ -26,6 +26,9 @@ FE7413AE14F689E700056D7B /* libopts.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEF87C2C13E0410900335C58 /* libopts.a */; }; FE7413D414F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7413D314F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp */; }; FE7413D814F691C200056D7B /* EdgeWalker_TestUtility.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7413D714F691C200056D7B /* EdgeWalker_TestUtility.cpp */; }; + FE99AE40151B4ED10072AA0D /* tempskinny4.txt in Resources */ = {isa = PBXBuildFile; fileRef = FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */; }; + FE99AE44151B4EE70072AA0D /* xtempskinny4.txt in Resources */ = {isa = PBXBuildFile; fileRef = FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */; }; + FE99AEBE151B64ED0072AA0D /* op.htm in Resources */ = {isa = PBXBuildFile; fileRef = FE99AEBD151B64ED0072AA0D /* op.htm */; }; FEA5F4E21498000C005052F9 /* libports.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA5F4E11497FFF6005052F9 /* libports.a */; }; FEA61B0014EF589900B736CB /* libanimator.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7268144DD3EA0059E97B /* libanimator.a */; }; FEA61B2C14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEA61B2B14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp */; }; @@ -258,6 +261,9 @@ FE7413D314F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerPolygons_Test.cpp; sourceTree = ""; }; FE7413D714F691C200056D7B /* EdgeWalker_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalker_TestUtility.cpp; sourceTree = ""; }; FE7413DB14F6926D00056D7B /* EdgeWalker_Test.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = EdgeWalker_Test.h; sourceTree = ""; }; + FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = tempskinny4.txt; sourceTree = ""; }; + FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = xtempskinny4.txt; sourceTree = ""; }; + FE99AEBD151B64ED0072AA0D /* op.htm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = op.htm; sourceTree = ""; }; FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = ports.xcodeproj; path = ../../out/gyp/ports.xcodeproj; sourceTree = SOURCE_ROOT; }; FEA61B2B14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerRectangles_Test.cpp; sourceTree = ""; }; FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SkAntiEdge.cpp; sourceTree = ""; }; @@ -386,6 +392,7 @@ 29B97314FDCFA39411CA2CEA /* edge */ = { isa = PBXGroup; children = ( + FE99AEBD151B64ED0072AA0D /* op.htm */, FEA670EF13C49D7600FE6FC1 /* views */, FEC123A7149001B20086BF1F /* AntiEdge */, 29B97315FDCFA39411CA2CEA /* Intersection */, @@ -481,6 +488,8 @@ FE71354F14D305FD0008E392 /* ShapeOps */ = { isa = PBXGroup; children = ( + FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */, + FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */, FE3DBAFD150E4A680006ADF4 /* junk.htm */, FE3DB8C9150A48320006ADF4 /* junk.txt */, FE71358514D309E90008E392 /* EdgeWalker.cpp */, @@ -899,6 +908,9 @@ 1DDD58160DA1D0A300B32029 /* MainMenu.xib in Resources */, FEED72B0144DD5710059E97B /* SampleApp.xib in Resources */, FE3DBAFE150E4A680006ADF4 /* junk.htm in Resources */, + FE99AE40151B4ED10072AA0D /* tempskinny4.txt in Resources */, + FE99AE44151B4EE70072AA0D /* xtempskinny4.txt in Resources */, + FE99AEBE151B64ED0072AA0D /* op.htm in Resources */, ); runOnlyForDeploymentPostprocessing = 0; }; diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm new file mode 100644 index 0000000000..dcfb654c35 --- /dev/null +++ b/experimental/Intersection/op.htm @@ -0,0 +1,244 @@ + + +
+
+path.moveTo(213.673737, 413.292938); +path.lineTo(225.200134, 343.616821); +path.lineTo(236.726532, 273.940704); +path.lineTo(219.386414, 231.373322); +path.lineTo(213.673737, 413.292938); +path.close(); +path.moveTo(43.485352, 308.984497); +path.lineTo(122.610657, 305.950134); +path.lineTo(201.735962, 302.915802); +path.lineTo(280.861267, 299.881470); +path.lineTo(43.485352, 308.984497); +path.close(); +
+
+ + + + + + + + -- cgit v1.2.3