From 1577e8f9c5bc8436cc71d3438c6d0b9f02c38338 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Tue, 22 May 2012 17:01:14 +0000 Subject: [PATCH] shape ops work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@4029 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/EdgeWalker_Test.h | 2 + .../Intersection/EdgeWalker_TestUtility.cpp | 2 +- experimental/Intersection/Intersection_Tests.cpp | 2 + experimental/Intersection/Intersection_Tests.h | 3 +- experimental/Intersection/LineParameterization.cpp | 6 +- experimental/Intersection/LineUtilities.cpp | 2 +- experimental/Intersection/ShapeOps.h | 1 + experimental/Intersection/Simplify.cpp | 283 ++++++++++++--------- .../Intersection/SimplifyFindNext_Test.cpp | 81 +++++- experimental/Intersection/SimplifyFindTop_Test.cpp | 63 +++-- 10 files changed, 285 insertions(+), 160 deletions(-) diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index f30743b..e8215a3 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -7,6 +7,8 @@ class SkCanvas; //extern int comparePaths(const SkPath& one, const SkPath& two); +extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, + SkCanvas* canvas); extern void comparePathsTiny(const SkPath& one, const SkPath& two); extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths); diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index d0b82c1..8a9bcd1 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -175,7 +175,7 @@ static int scaledDrawTheSame(const SkPath& one, const SkPath& two, static int max = 0; -static int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, +int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, SkCanvas* canvas) { int errors = pathsDrawTheSame(one, two, bitmap, canvas); if (errors == 0) { diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index 4e4c8de..e0b07f9 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -7,6 +7,8 @@ void testSimplify(); #define TEST_QUADS_FIRST 0 void Intersection_Tests() { + SimplifyNew_Test(); + SimplifyFindNext_Test(); SimplifyFindTop_Test(); SimplifyAngle_Test(); QuadraticReduceOrder_Test(); diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h index 50e5600..ca7c359 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -18,9 +18,10 @@ void LineParameter_Test(); void LineQuadraticIntersection_Test(); void SimplifyAddIntersectingTs_Test(); void SimplifyAngle_Test(); +void SimplifyDegenerate4x4TrianglesThreaded_Test(); void SimplifyFindNext_Test(); void SimplifyFindTop_Test(); -void SimplifyDegenerate4x4TrianglesThreaded_Test(); +void SimplifyNew_Test(); void SimplifyNondegenerate4x4TrianglesThreaded_Test(); void SimplifyPolygonPaths_Test(); void SimplifyQuadralateralPaths_Test(); diff --git a/experimental/Intersection/LineParameterization.cpp b/experimental/Intersection/LineParameterization.cpp index 1611a31..8bf8acd 100644 --- a/experimental/Intersection/LineParameterization.cpp +++ b/experimental/Intersection/LineParameterization.cpp @@ -37,7 +37,7 @@ bool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps) { (dy1 * dy2) * dx1 / dy1 == (dy1 * dy2) * dx2 / dy2 dy2 * dx1 == dy1 * dx2 */ - int diff = UlpsDiff(oneD.x * twoD.y, twoD.x * oneD.y); + int diff = UlpsDiff((float) (oneD.x * twoD.y), (float) (twoD.x * oneD.y)); if (diff < 0 || diff > ulps) { return false; } @@ -46,8 +46,8 @@ bool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps) { dx * (y0 - x0 * dy / dx) == dx * (y1 - x1 * dy / dx) dx * y0 - x0 * dy == dx * y1 - x1 * dy */ - diff = UlpsDiff(oneD.x * one[0].y - oneD.y * one[0].x, - oneD.x * two[0].y - oneD.y * two[0].x); + diff = UlpsDiff((float) (oneD.x * one[0].y - oneD.y * one[0].x), + (float) (oneD.x * two[0].y - oneD.y * two[0].x)); return diff >= 0 && diff <= ulps; } diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp index 38e1ba0..8d229e4 100644 --- a/experimental/Intersection/LineUtilities.cpp +++ b/experimental/Intersection/LineUtilities.cpp @@ -53,5 +53,5 @@ void sub_divide(const _Line& line, double t1, double t2, _Line& dst) { // See: the January 2001 Algorithm on Area of Triangles float isLeft( _Point P0, _Point P1, _Point P2 ) { - return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y); + return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y)); } diff --git a/experimental/Intersection/ShapeOps.h b/experimental/Intersection/ShapeOps.h index 389275d..b847336 100644 --- a/experimental/Intersection/ShapeOps.h +++ b/experimental/Intersection/ShapeOps.h @@ -2,5 +2,6 @@ void contourBounds(const SkPath& path, SkTDArray& boundsArray); void simplify(const SkPath& path, bool asFill, SkPath& simple); +void simplifyx(const SkPath& path, bool asFill, SkPath& simple); extern const bool gRunTestsInOneThread; // FIXME: remove once debugging is complete \ No newline at end of file diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index 444b32d..fc83c99 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -415,7 +415,7 @@ public: // since all angles share a point, this needs to know which point // is the common origin, i.e., whether the center is at pts[0] or pts[verb] // practically, this should only be called by addAngle - void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment, + void set(const SkPoint* pts, SkPath::Verb verb, Segment* segment, int start, int end, bool coincident) { SkASSERT(start != end); fSegment = segment; @@ -441,7 +441,7 @@ public: // noncoincident quads/cubics may have the same initial angle // as lines, so must sort by derivatives as well // if flatness turns out to be a reasonable way to sort, use the below: - void setFlat(const SkPoint* pts, SkPath::Verb verb, const Segment* segment, + void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment, int start, int end, bool coincident) { fSegment = segment; fStart = start; @@ -487,7 +487,7 @@ public: SkASSERT(0); // FIXME: add cubic case } - const Segment* segment() const { + Segment* segment() const { return fSegment; } @@ -508,7 +508,7 @@ private: SkScalar fDDy; SkScalar fDDDx; SkScalar fDDDy; - const Segment* fSegment; + Segment* fSegment; int fStart; int fEnd; bool fCoincident; @@ -578,8 +578,14 @@ public: } void addAngle(SkTDArray& angles, int start, int end, - bool coincident) const { + bool coincident) { SkASSERT(start != end); + int direction = start < end ? 1 : -1; + if (fTs[start].fDone) { + SkASSERT(fTs[start].fDone == direction); + SkASSERT(fTs[end].fDone == -direction); + return; + } SkPoint edge[4]; (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); Angle* angle = angles.append(); @@ -591,11 +597,35 @@ public: fBounds.setCubicBounds(pts); } + void addCurveTo(int start, int end, SkPath& path) { + SkPoint edge[4]; + (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + switch (fVerb) { + case SkPath::kLine_Verb: + path.lineTo(edge[1].fX, edge[1].fY); + break; + case SkPath::kQuad_Verb: + path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); + break; + case SkPath::kCubic_Verb: + path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, + edge[3].fX, edge[3].fY); + break; + } + } + void addLine(const SkPoint pts[2]) { init(pts, SkPath::kLine_Verb); fBounds.set(pts, 2); } + void addMoveTo(int tIndex, SkPath& path) { + SkPoint pt; + double firstT = t(tIndex); + xyAtT(firstT, &pt); + path.moveTo(pt.fX, pt.fY); + } + // add 2 to edge or out of range values to get T extremes void addOtherT(int index, double otherT, int otherIndex) { Span& span = fTs[index]; @@ -641,7 +671,7 @@ finish: } void addTwoAngles(int start, int end, const SkPoint& endLoc, - const Span* endSpan, bool startCo, SkTDArray& angles) const { + const Span* endSpan, bool startCo, SkTDArray& angles) { // add edge leading into junction addAngle(angles, end, start, startCo); // add edge leading away from junction @@ -649,7 +679,7 @@ finish: int step = start < end ? 1 : -1; int tIndex = nextSpan(end, step, endLoc, endSpan, NULL, coincident); if (tIndex >= 0) { - lastSpan(tIndex, step, endLoc, endSpan, coincident); + lastSpan(tIndex, step, endLoc, endSpan->fT, coincident); addAngle(angles, end, tIndex, coincident); } } @@ -686,7 +716,7 @@ finish: next = other->nextSpan(oIndex, localStep, loc, otherSpan, NULL, otherCo); } - other->lastSpan(next, localStep, loc, otherSpan, otherCo); + other->lastSpan(next, localStep, loc, otherSpan->fT, otherCo); // add candidate into and away from junction other->addTwoAngles(next, oIndex, loc, span, otherCo, angles); @@ -729,33 +759,35 @@ finish: // winding -1 means ccw, 1 means cw // step is in/out -1 or 1 // spanIndex is returned - Segment* findNext(int start, int winding, int& step, int& spanIndex) const { - SkASSERT(step == 1 || step == -1); + Segment* findNext(int winding, int& startIndex, int& endIndex) { + SkASSERT(startIndex != endIndex); int count = fTs.count(); - SkASSERT(step > 0 ? start < count - 1 : start > 0); - Span* startSpan = &fTs[start]; + SkASSERT(startIndex < endIndex ? startIndex < count - 1 + : startIndex > 0); + Span* startSpan = &fTs[startIndex]; // FIXME: // since Ts can be stepped either way, done markers must be careful // not to assume that segment was only ascending in T. This shouldn't // be a problem unless pathologically a segment can be partially // ascending and partially descending -- maybe quads/cubic can do this? + int step = startIndex < endIndex ? 1 : -1; + SkASSERT(startSpan->fDone == 0); startSpan->fDone = step; SkPoint startLoc; // OPTIMIZATION: store this in the t span? xyAtT(startSpan->fT, &startLoc); SkPoint endLoc; bool startCo; - int end = nextSpan(start, step, startLoc, startSpan, &endLoc, startCo); - - // if we hit the end looking for span end, is that always an error? - SkASSERT(step > 0 ? end + 1 < count : end - 1 >= 0); + int end = nextSpan(startIndex, step, startLoc, startSpan, &endLoc, + startCo); + SkASSERT(end >= 0); // preflight for coincidence -- if present, it may change winding // considerations and whether reversed edges can be followed - int last = lastSpan(end, step, startLoc, startSpan, startCo); + int last = lastSpan(end, step, endLoc, fTs[end].fT, startCo); // Discard opposing direction candidates if no coincidence was found. Span* endSpan = &fTs[end]; - int candidateCount = abs(last - end); + int candidateCount = abs(last - end) + 1; Segment* other; if (candidateCount == 1) { SkASSERT(!startCo); @@ -764,52 +796,78 @@ finish: // this requres that the intersection is angularly sorted // for a single intersection, special case -- choose the opposite // edge that steps the same + SkASSERT(endSpan->fDone == 0); + endSpan->fDone = -step; + SkASSERT(fDone == false); + fDone = true; other = endSpan->fOther; - SkASSERT(!other->fDone); - spanIndex = endSpan->fOtherIndex; - SkASSERT(step < 0 ? spanIndex > 0 - : spanIndex < other->fTs.count() - 1); + startIndex = endSpan->fOtherIndex; + endIndex = startIndex + step; + SkASSERT(step < 0 ? endIndex >= 0 : endIndex < other->fTs.count()); return other; } // more than one viable candidate -- measure angles to find best SkTDArray angles; - SkASSERT(end - start != 0); - SkASSERT((end - start < 0) ^ (step < 0)); - addTwoAngles(start, end, endLoc, endSpan, startCo, angles); + SkASSERT(endIndex - startIndex != 0); + SkASSERT((endIndex - startIndex < 0) ^ (step < 0)); + addTwoAngles(startIndex, end, endLoc, endSpan, startCo, angles); buildAngles(end, last, step, endLoc, angles); SkTDArray sorted; sortAngles(angles, sorted); // find the starting edge - int startIndex = -1; + int firstIndex = -1; int angleCount = angles.count(); int angleIndex; const Angle* angle; for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { angle = sorted[angleIndex]; if (angle->segment() == this && angle->start() == end && - angle->end() == start) { - startIndex = angleIndex; + angle->end() == startIndex) { + firstIndex = angleIndex; break; } } - SkASSERT(startIndex >= 0); + SkASSERT(firstIndex >= 0); winding += angle->sign(); - int nextIndex = startIndex; + int nextIndex = firstIndex; const Angle* nextAngle; do { if (++nextIndex == angleCount) { nextIndex = 0; } - SkASSERT(nextIndex != startIndex); // should never wrap around + SkASSERT(nextIndex != firstIndex); // should never wrap around nextAngle = sorted[nextIndex]; // OPTIMIZATION: Figure out all connections, given the initial // winding info (e.g., accumulate winding in span for reuse) winding -= nextAngle->sign(); - } while (winding); - // FIXME: get rid of cast - return const_cast(nextAngle->segment()); - + + // start here; + // if the winding is non-zero, nextAngle does not connect to + // current chain. We may be able to deduce whether it will be + // in some future chain or ignored altogether based on winding, + // but for the first cut, just detach it from this chain. + if (!winding) { + break; + } + // but how to detach? Maybe it is correct to mark both ends + // for all of the sorted angles as done, regardless of whether we + // also compute the connectedness and/or winding for the inner ones. + + } while (true); + Segment* result = nextAngle->segment(); + startIndex = nextAngle->end(); + endIndex = nextAngle->start(); + int direction = startIndex < endIndex ? 1 : -1; + SkASSERT(result->fTs[startIndex].fDone == 0); + SkASSERT(result->fTs[endIndex].fDone == 0); + result->fTs[startIndex].fDone = direction; + result->fTs[endIndex].fDone = -direction; + // FIXME: how to mark that segment is completely done? + return result; + } + + // so the span needs to contain the pairing info found here // this should include the winding computed for the edge, and // what edge it connects to, and whether it is discarded @@ -830,8 +888,8 @@ finish: // choices to connections in the correct direction // mark found segments as done - } + // FIXME: this is tricky code; needs its own unit test void findTooCloseToCall(int winding) { int count = fTs.count(); if (count < 3) { // require t=0, x, 1 at minimum @@ -845,7 +903,13 @@ finish: match = &fTs[matchIndex]; mOther = match->fOther; moCount = mOther->fTs.count(); - } while (moCount >= 3 || ++matchIndex < count - 1); // require t=0, x, 1 at minimum + if (moCount >= 3) { + break; + } + if (++matchIndex >= count) { + return; + } + } while (true); // require t=0, x, 1 at minimum SkPoint matchPt; // OPTIMIZATION: defer matchPt until qualifying toCount is found? xyAtT(match->fT, &matchPt); @@ -869,89 +933,72 @@ finish: matchPt = testPt; continue; } - int moStart = -1; // FIXME: initialization is debugging only + int moStart = -1; + int moEnd = -1; + double moStartT, moEndT; for (int moIndex = 0; moIndex < moCount; ++moIndex) { Span& moSpan = mOther->fTs[moIndex]; if (moSpan.fOther == this) { if (moSpan.fOtherT == match->fT) { moStart = moIndex; + moStartT = moSpan.fT; } continue; } - if (moSpan.fOther != tOther) { - continue; + if (moSpan.fOther == tOther) { + SkASSERT(moEnd == -1); + moEnd = moIndex; + moEndT = moSpan.fT; } - int toStart = -1; - int toIndex; // FIXME: initialization is debugging only - bool found = false; - for (toIndex = 0; toIndex < toCount; ++toIndex) { - Span& toSpan = tOther->fTs[toIndex]; - if (toSpan.fOther == this) { - if (toSpan.fOtherT == test->fT) { - toStart = toIndex; - } - continue; - } - if (toSpan.fOther == mOther && toSpan.fOtherT == moSpan.fT) { - found = true; - break; + } + if (moStart < 0 || moEnd < 0) { + continue; + } + // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test + if (moStartT == moEndT) { + continue; + } + int toStart = -1; + int toEnd = -1; + double toStartT, toEndT; + for (int toIndex = 0; toIndex < toCount; ++toIndex) { + Span& toSpan = tOther->fTs[toIndex]; + if (toSpan.fOther == this) { + if (toSpan.fOtherT == test->fT) { + toStart = toIndex; + toStartT = toSpan.fT; } - } - if (!found) { continue; } - SkASSERT(moStart >= 0); - SkASSERT(toStart >= 0); - // test to see if the segment between there and here is linear - if (!mOther->isLinear(moStart, moIndex) - || !tOther->isLinear(toStart, toIndex)) { - continue; + if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { + SkASSERT(toEnd == -1); + toEnd = toIndex; + toEndT = toSpan.fT; } - mOther->fTs[moStart].fCoincident = -1; - tOther->fTs[toStart].fCoincident = -1; - mOther->fTs[moIndex].fCoincident = 1; - tOther->fTs[toIndex].fCoincident = 1; } - nextStart: - ; - } - } - - // find the adjacent T that is leftmost, with a point != base - int findLefty(int tIndex, const SkPoint& base) const { - int bestTIndex = -1; - SkPoint test; - SkScalar bestX = FLT_MAX; - int testTIndex = tIndex; - while (--testTIndex >= 0) { - xyAtT(fTs[testTIndex].fT, &test); - if (test == base) { + // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test + if (toStart <= 0 || toEnd <= 0) { continue; } - bestX = test.fX; - bestTIndex = testTIndex; - break; - } - int count = fTs.count(); - testTIndex = tIndex; - while (++testTIndex < count) { - xyAtT(fTs[testTIndex].fT, &test); - if (test == base) { + if (toStartT == toEndT) { continue; } - if (bestX > test.fX) { - bestTIndex = testTIndex; + // test to see if the segment between there and here is linear + if (!mOther->isLinear(moStart, moEnd) + || !tOther->isLinear(toStart, toEnd)) { + continue; } - break; + mOther->fTs[moStart].fCoincident = -1; + tOther->fTs[toStart].fCoincident = -1; + mOther->fTs[moEnd].fCoincident = 1; + tOther->fTs[toEnd].fCoincident = 1; } - SkASSERT(bestTIndex != -1); - return bestTIndex; } // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) // and use more concise logic like the old edge walker code? // FIXME: this needs to deal with coincident edges - const Segment* findTop(int& tIndex, int& direction) const { + Segment* findTop(int& tIndex, int& endIndex) { // iterate through T intersections and return topmost // topmost tangent from y-min to first pt is closer to horizontal int firstT = 0; @@ -973,6 +1020,7 @@ finish: // if there's only a pair of segments, go with the endpoint chosen above if (firstT == lastT) { tIndex = firstT; + endIndex = firstT > 0 ? tIndex - 1 : tIndex + 1; return this; } // sort the edges to find the leftmost @@ -993,11 +1041,9 @@ finish: buildAngles(firstT, lastT, 1, startLoc, angles); SkTDArray sorted; sortAngles(angles, sorted); - const Segment* leftSegment = sorted[0]->segment(); + Segment* leftSegment = sorted[0]->segment(); tIndex = sorted[0]->end(); - direction = sorted[0]->start() - tIndex; - SkASSERT(direction); - direction = direction < 0 ? -1 : 1; + endIndex = sorted[0]->start(); return leftSegment; } @@ -1059,7 +1105,7 @@ finish: } int lastSpan(int end, int step, const SkPoint& startLoc, - const Span* startSpan, bool& coincident) const { + double startT, bool& coincident) const { int last = end; int count = fTs.count(); SkPoint lastLoc; @@ -1075,7 +1121,7 @@ finish: if (lastSpan.fDone == -step) { return end; } - if (lastSpan.fT == startSpan->fT) { + if (lastSpan.fT == startT) { continue; } xyAtT(lastSpan.fT, &lastLoc); @@ -1129,8 +1175,10 @@ finish: fTs.reset(); } - // OPTIMIZATION: remove this function if it's never called + // OPTIMIZATION: mark as debugging only if used solely by tests double t(int tIndex) const { + SkASSERT(tIndex >= 0); + SkASSERT(tIndex < fTs.count()); return fTs[tIndex].fT; } @@ -1876,7 +1924,7 @@ static Segment* findTopContour(SkTDArray& contourList, // is an option, choose first edge that continues the inside. // since we start with leftmost top edge, we'll traverse through a // smaller angle counterclockwise to get to the next edge. -static void bridge(SkTDArray& contourList) { +static void bridge(SkTDArray& contourList, SkPath& simple) { int contourCount = contourList.count(); int winding = 0; // there are no contours outside this one do { @@ -1886,13 +1934,17 @@ static void bridge(SkTDArray& contourList) { } // Start at the top. Above the top is outside, below is inside. // follow edges to intersection by changing the tIndex by direction. - int tIndex, step; - const Segment* topSegment = topStart->findTop(tIndex, step); - const Segment* next = topSegment; + int tIndex, endIndex; + Segment* topSegment = topStart->findTop(tIndex, endIndex); + Segment* next = topSegment; + next->addMoveTo(tIndex, simple); do { - int spanIndex; - next = next->findNext(tIndex, winding, step, spanIndex); + SkASSERT(!next->done()); + next->addCurveTo(tIndex, endIndex, simple); + next = next->findNext(winding, tIndex, endIndex); } while (next != topSegment); + simple.close(); + } while (true); // at intersection, stay on outside, but mark remaining edges as inside // or, only mark first pair as inside? @@ -1904,7 +1956,6 @@ static void bridge(SkTDArray& contourList) { // output span // mark span as processed - } while (true); } @@ -1917,7 +1968,7 @@ static void fixOtherTIndex(SkTDArray& contourList) { } } -static void makeContourList(SkTArray& contours, Contour& sentinel, +static void makeContourList(SkTArray& contours, SkTDArray& list) { int count = contours.count(); if (count == 0) { @@ -1926,7 +1977,6 @@ static void makeContourList(SkTArray& contours, Contour& sentinel, for (int index = 0; index < count; ++index) { *list.append() = &contours[index]; } - *list.append() = &sentinel; QSort(list.begin(), list.end() - 1); } @@ -1941,13 +1991,12 @@ void simplifyx(const SkPath& path, bool asFill, SkPath& simple) { // FIXME: add self-intersecting cubics' T values to segment EdgeBuilder builder(path, contours); SkTDArray contourList; - Contour sentinel; - sentinel.reset(); - makeContourList(contours, sentinel, contourList); + makeContourList(contours, contourList); Contour** currentPtr = contourList.begin(); if (!currentPtr) { return; } + Contour** listEnd = contourList.end(); // find all intersections between segments do { Contour** nextPtr = currentPtr; @@ -1955,12 +2004,12 @@ void simplifyx(const SkPath& path, bool asFill, SkPath& simple) { Contour* next; do { next = *nextPtr++; - } while (next != &sentinel && addIntersectTs(current, next, winding)); - } while (*currentPtr != &sentinel); + } while (addIntersectTs(current, next, winding) && nextPtr != listEnd); + } while (currentPtr != listEnd); fixOtherTIndex(contourList); // eat through coincident edges coincidenceCheck(contourList, winding); // construct closed contours - bridge(contourList); + bridge(contourList, simple); } diff --git a/experimental/Intersection/SimplifyFindNext_Test.cpp b/experimental/Intersection/SimplifyFindNext_Test.cpp index 6d47a93..4e55038 100644 --- a/experimental/Intersection/SimplifyFindNext_Test.cpp +++ b/experimental/Intersection/SimplifyFindNext_Test.cpp @@ -16,13 +16,11 @@ namespace SimplifyFindNextTest { #include "Intersection_Tests.h" static const SimplifyFindNextTest::Segment* testCommon( - int start, int winding, int step, + int winding, int startIndex, int endIndex, SkTArray& contours, SimplifyFindNextTest::EdgeBuilder& builder, const SkPath& path) { SkTDArray contourList; - SimplifyFindNextTest::Contour sentinel; - sentinel.reset(); - makeContourList(contours, sentinel, contourList); + makeContourList(contours, contourList); addIntersectTs(contourList[0], contourList[0], -1); if (contours.count() > 1) { SkASSERT(contours.count() == 2); @@ -31,20 +29,31 @@ static const SimplifyFindNextTest::Segment* testCommon( } fixOtherTIndex(contourList); SimplifyFindNextTest::Segment& segment = contours[0].fSegments[0]; - int spanIndex; - SimplifyFindNextTest::Segment* next = segment.findNext(start, winding, - step, spanIndex); - SkASSERT(spanIndex == 1); + SkPoint pts[2]; + double startT = segment.t(endIndex); + segment.xyAtT(startT, &pts[0]); + SimplifyFindNextTest::Segment* next = segment.findNext(winding, + startIndex, endIndex); + double endT = next->t(startIndex); + next->xyAtT(endT, &pts[1]); + SkASSERT(pts[0] == pts[1]); return next; } static void test(const SkPath& path) { SkTArray contours; SimplifyFindNextTest::EdgeBuilder builder(path, contours); + int winding = 0; int start = 0; + int end = 1; + testCommon(winding, start, end, contours, builder, path); +} + +static void test(const SkPath& path, int start, int end) { + SkTArray contours; + SimplifyFindNextTest::EdgeBuilder builder(path, contours); int winding = 0; - int step = 1; - testCommon(start, winding, step, contours, builder, path); + testCommon(winding, start, end, contours, builder, path); } static void testLine1() { @@ -56,8 +65,60 @@ static void testLine1() { test(path); } +static void addInnerCWTriangle(SkPath& path) { + path.moveTo(3,0); + path.lineTo(4,1); + path.lineTo(2,1); + path.close(); +} + +static void addInnerCCWTriangle(SkPath& path) { + path.moveTo(3,0); + path.lineTo(2,1); + path.lineTo(4,1); + path.close(); +} + +static void addOuterCWTriangle(SkPath& path) { + path.moveTo(3,0); + path.lineTo(6,2); + path.lineTo(0,2); + path.close(); +} + +static void addOuterCCWTriangle(SkPath& path) { + path.moveTo(3,0); + path.lineTo(0,2); + path.lineTo(6,2); + path.close(); +} + +static void testLine2() { + SkPath path; + addInnerCWTriangle(path); + addOuterCWTriangle(path); + test(path, 0, 3); +} + +static void testLine3() { + SkPath path; + addInnerCWTriangle(path); + addOuterCWTriangle(path); + test(path, 3, 0); +} + +static void testLine4() { + SkPath path; + addInnerCWTriangle(path); + addOuterCWTriangle(path); + test(path, 3, 2); +} + static void (*tests[])() = { testLine1, + testLine2, + testLine3, + testLine4, }; static const size_t testCount = sizeof(tests) / sizeof(tests[0]); diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp index ade9299..3932f5a 100644 --- a/experimental/Intersection/SimplifyFindTop_Test.cpp +++ b/experimental/Intersection/SimplifyFindTop_Test.cpp @@ -17,11 +17,10 @@ namespace SimplifyFindTopTest { static const SimplifyFindTopTest::Segment* testCommon( SkTArray& contours, - SimplifyFindTopTest::EdgeBuilder& builder, const SkPath& path) { + SimplifyFindTopTest::EdgeBuilder& builder, const SkPath& path, + int& index, int& end) { SkTDArray contourList; - SimplifyFindTopTest::Contour sentinel; - sentinel.reset(); - makeContourList(contours, sentinel, contourList); + makeContourList(contours, contourList); addIntersectTs(contourList[0], contourList[0], -1); if (contours.count() > 1) { SkASSERT(contours.count() == 2); @@ -31,35 +30,45 @@ static const SimplifyFindTopTest::Segment* testCommon( fixOtherTIndex(contourList); SimplifyFindTopTest::Segment* topStart = findTopContour(contourList, contourList.count()); - int index, direction; const SimplifyFindTopTest::Segment* topSegment = topStart->findTop(index, - direction); - SkASSERT(direction == 1); + end); return topSegment; } static void test(const SkPath& path) { SkTArray contours; SimplifyFindTopTest::EdgeBuilder builder(path, contours); - testCommon(contours, builder, path); + int index, end; + testCommon(contours, builder, path, index, end); + SkASSERT(index + 1 == end); } static void test(const SkPath& path, SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { SkTArray contours; SimplifyFindTopTest::EdgeBuilder builder(path, contours); + int index, end; const SimplifyFindTopTest::Segment* topSegment = - testCommon(contours, builder, path); - const SkPoint* pts = topSegment->pts(); - SkPoint top = pts[0]; - SkPoint bottom = pts[1]; - if (top.fY > bottom.fY) { - SkTSwap(top, bottom); - } - SkASSERT(top.fX == x1); - SkASSERT(top.fY == y1); - SkASSERT(bottom.fX == x2); - SkASSERT(bottom.fY == y2); + testCommon(contours, builder, path, index, end); + SkPoint pts[2]; + double firstT = topSegment->t(index); + topSegment->xyAtT(firstT, &pts[0]); + int direction = index < end ? 1 : -1; + do { + index += direction; + double nextT = topSegment->t(index); + if (nextT == firstT) { + continue; + } + topSegment->xyAtT(nextT, &pts[1]); + if (pts[0] != pts[1]) { + break; + } + } while (true); + SkASSERT(pts[0].fX == x1); + SkASSERT(pts[0].fY == y1); + SkASSERT(pts[1].fX == x2); + SkASSERT(pts[1].fY == y2); } static void testLine1() { @@ -103,56 +112,56 @@ static void testLine2() { SkPath path; addInnerCWTriangle(path); addOuterCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine3() { SkPath path; addOuterCWTriangle(path); addInnerCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine4() { SkPath path; addInnerCCWTriangle(path); addOuterCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine5() { SkPath path; addOuterCWTriangle(path); addInnerCCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine6() { SkPath path; addInnerCWTriangle(path); addOuterCCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine7() { SkPath path; addOuterCCWTriangle(path); addInnerCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine8() { SkPath path; addInnerCCWTriangle(path); addOuterCCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testLine9() { SkPath path; addOuterCCWTriangle(path); addInnerCCWTriangle(path); - test(path, 3, 0, 0, 2); + test(path, 0, 2, 3, 0); } static void testQuads() { -- 2.7.4