From cd4421df5012b75c792c6c8bf2c5ee0410921c15 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Thu, 1 Mar 2012 19:16:31 +0000 Subject: [PATCH] work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@3291 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/EdgeWalker.cpp | 200 ++++++--- .../Intersection/EdgeWalkerPolygons_Test.cpp | 423 +++++++++++++++++++ .../Intersection/EdgeWalkerRectangles_Test.cpp | 452 +++++++++++++++++++++ experimental/Intersection/EdgeWalker_Test.h | 9 + .../Intersection/EdgeWalker_TestUtility.cpp | 190 +++++++++ experimental/Intersection/TSearch.h | 42 +- 6 files changed, 1245 insertions(+), 71 deletions(-) create mode 100644 experimental/Intersection/EdgeWalkerPolygons_Test.cpp create mode 100644 experimental/Intersection/EdgeWalkerRectangles_Test.cpp create mode 100644 experimental/Intersection/EdgeWalker_Test.h create mode 100644 experimental/Intersection/EdgeWalker_TestUtility.cpp diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index fc53f63..2c1e5f5 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -16,7 +16,7 @@ static bool gShowDebugf = true; // FIXME: remove once debugging is complete static bool gShowPath = false; -static bool gDebugLessThan = false; +static bool gDebugLessThan = true; static int LineIntersect(const SkPoint a[2], const SkPoint b[2], double aRange[2], double bRange[2]) { @@ -30,11 +30,12 @@ static int LineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) { return horizontalIntersect(aLine, y, aRange); } -static SkScalar LineXAtT(const SkPoint a[2], double t) { +static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - double x; - xy_at_t(aLine, t, x, *(double*) 0); - return SkDoubleToScalar(x); + double x, y; + xy_at_t(aLine, t, x, y); + out->fX = SkDoubleToScalar(x); + out->fY = SkDoubleToScalar(y); } static SkScalar LineYAtT(const SkPoint a[2], double t) { @@ -419,10 +420,11 @@ struct InEdge { size_t tCount = intercepts.fTs.count(); for (size_t idx2 = 0; idx2 < tCount; ++idx2) { if (t <= intercepts.fTs[idx2]) { - if (t < intercepts.fTs[idx2]) { + double delta = intercepts.fTs[idx2] - t; + if (delta > 0) { *intercepts.fTs.insert(idx2) = t; - break; } + return foundIntercept; } } if (tCount == 0 || t > intercepts.fTs[tCount - 1]) { @@ -649,6 +651,12 @@ struct WorkEdge { fPts += *fVerb++; return fVerb != fEdge->fVerbs.end(); } + + SkPath::Verb lastVerb() const { + SkASSERT(fVerb > fEdge->fVerbs.begin()); + return (SkPath::Verb) fVerb[-1]; + } + SkPath::Verb verb() const { return (SkPath::Verb) *fVerb; @@ -670,16 +678,73 @@ struct WorkEdge { // always constructed with SkTDArray because new edges are inserted // this may be a inappropriate optimization, suggesting that a separate array of // ActiveEdge* may be faster to insert and search + +// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since +// as active edges are introduced, only local sorting should be required struct ActiveEdge { + // OPTIMIZATION: fold return statements into one bool operator<(const ActiveEdge& rh) const { - return fXAbove != rh.fXAbove ? fXAbove < rh.fXAbove - : fXBelow < rh.fXBelow; + if (rh.fAbove.fY - fAbove.fY > fBelow.fY - rh.fAbove.fY + && fBelow.fY < rh.fBelow.fY + || fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - fAbove.fY + && rh.fBelow.fY < fBelow.fY) { + // FIXME: need to compute distance, not check for points equal + const SkPoint& check = rh.fBelow.fY <= fBelow.fY + && fBelow != rh.fBelow ? rh.fBelow : + rh.fAbove; + if (gDebugLessThan) { + SkDebugf("%s < %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}" + " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\n", __FUNCTION__, + rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', + (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) + < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX) + ? ' ' : '!', + fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, + rh.fIndex, rh.fAbove.fX, rh.fAbove.fY, + rh.fBelow.fX, rh.fBelow.fY); + } + return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) + < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX); + } + // FIXME: need to compute distance, not check for points equal + const SkPoint& check = fBelow.fY <= rh.fBelow.fY + && fBelow != rh.fBelow ? fBelow : fAbove; + if (gDebugLessThan) { + SkDebugf("%s > %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}" + " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\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) + ? ' ' : '!', + fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, + rh.fIndex, rh.fAbove.fX, rh.fAbove.fY, + rh.fBelow.fX, rh.fBelow.fY); + } + return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) + < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); } - void calcLeft() { + bool advanceT() { + SkASSERT(fTIndex <= fTs->count()); + return ++fTIndex <= fTs->count(); + } + + bool advance() { + // FIXME: flip sense of next + bool result = fWorkEdge.advance(); + fDone = !result; + initT(); + return result; + } + + void calcLeft(SkScalar y) { // OPTIMIZE: put a kDone_Verb at the end of the verb list? - if (fDone) + if (done(y)) return; // nothing to do; use last + calcLeft(); + } + + void calcLeft() { switch (fWorkEdge.verb()) { case SkPath::kLine_Verb: { // OPTIMIZATION: if fXAbove, fXBelow have already been computed @@ -688,9 +753,10 @@ struct ActiveEdge { // If both edges have T values < 1, check x at next T (fXBelow). int add = (fTIndex <= fTs->count()) - 1; double tAbove = t(fTIndex + add); - fXAbove = LineXAtT(fWorkEdge.fPts, tAbove); + // OPTIMIZATION: may not need Y + LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); double tBelow = t(fTIndex - ~add); - fXBelow = LineXAtT(fWorkEdge.fPts, tBelow); + LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); break; } default: @@ -699,6 +765,10 @@ struct ActiveEdge { } } + bool done(SkScalar y) { + return fDone || fYBottom > y; + } + void init(const InEdge* edge) { fWorkEdge.init(edge); initT(); @@ -717,16 +787,30 @@ struct ActiveEdge { fTIndex = 0; } - bool isCoincidentWith(const ActiveEdge* edge) const { - if (fXAbove != edge->fXAbove || fXBelow != edge->fXBelow) { + // 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.fX != edge->fAbove.fX || fBelow.fX != edge->fBelow.fX) { return false; } - switch (fWorkEdge.verb()) { + uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); + uint8_t edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb() + : edge->fWorkEdge.verb(); + if (verb != edgeVerb) { + return false; + } + switch (verb) { case SkPath::kLine_Verb: { - return (fWorkEdge.fPts[0].fX - fWorkEdge.fPts[1].fX) * - (edge->fWorkEdge.fPts[0].fY - edge->fWorkEdge.fPts[1].fY) == - (fWorkEdge.fPts[0].fY - fWorkEdge.fPts[1].fY) * - (edge->fWorkEdge.fPts[0].fX - edge->fWorkEdge.fPts[1].fX); + int offset = fDone ? -1 : 1; + int edgeOffset = edge->fDone ? -1 : 1; + const SkPoint* pts = fWorkEdge.fPts; + const SkPoint* edgePts = edge->fWorkEdge.fPts; + return (pts->fX - pts[offset].fX) + * (edgePts->fY - edgePts[edgeOffset].fY) + == (pts->fY - pts[offset].fY) + * (edgePts->fX - edgePts[edgeOffset].fX); } default: // FIXME: add support for all curve types @@ -734,24 +818,27 @@ struct ActiveEdge { } return false; } - - bool advanceT() { - SkASSERT(fTIndex <= fTs->count()); - return ++fTIndex <= fTs->count(); - } - bool advance() { - // FIXME: flip sense of next - bool result = fWorkEdge.advance(); - fDone = !result; - initT(); - return result; - } - - bool done(SkScalar y) { - return fDone || fYBottom > y; + bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { + if (fBelow.fY >= bottom || fDone || edge->fDone) { + return false; + } + ActiveEdge thisWork = *this; + ActiveEdge edgeWork = *edge; + while ((thisWork.advanceT() || thisWork.advance()) + && (edgeWork.advanceT() || edgeWork.advance())) { + thisWork.calcLeft(); + edgeWork.calcLeft(); + if (thisWork < edgeWork) { + return false; + } + if (edgeWork < thisWork) { + return true; + } + } + return false; } - + double nextT() { SkASSERT(fTIndex <= fTs->count()); return t(fTIndex + 1); @@ -779,12 +866,13 @@ struct ActiveEdge { WorkEdge fWorkEdge; const SkTDArray* fTs; - SkScalar fXAbove; - SkScalar fXBelow; + SkPoint fAbove; + SkPoint fBelow; SkScalar fYBottom; int fTIndex; bool fSkip; bool fDone; + int fIndex; // REMOVE: debugging only }; static void addToActive(SkTDArray& activeEdges, const InEdge* edge) { @@ -959,8 +1047,7 @@ static void makeEdgeList(SkTArray& edges, InEdge& edgeSentinel, } edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); *edgeList.append() = &edgeSentinel; - ++edgeCount; - QSort(edgeList.begin(), edgeCount); + QSort(edgeList.begin(), edgeList.end() - 1); } @@ -977,7 +1064,8 @@ static void skipCoincidence(int lastWinding, int winding, int windingMask, } static void sortHorizontal(SkTDArray& activeEdges, - SkTDArray& edgeList, int windingMask) { + SkTDArray& edgeList, int windingMask, SkScalar y, + SkScalar bottom) { size_t edgeCount = activeEdges.count(); if (edgeCount == 0) { return; @@ -985,11 +1073,12 @@ static void sortHorizontal(SkTDArray& activeEdges, size_t index; for (index = 0; index < edgeCount; ++index) { ActiveEdge& activeEdge = activeEdges[index]; - activeEdge.calcLeft(); + activeEdge.calcLeft(y); activeEdge.fSkip = false; + activeEdge.fIndex = index; // REMOVE: debugging only *edgeList.append() = &activeEdge; } - QSort(edgeList.begin(), edgeCount); + QSort(edgeList.begin(), edgeList.end() - 1); // remove coincident edges // OPTIMIZE: remove edges? This is tricky because the current logic expects // the winding count to be maintained while skipping coincident edges. In @@ -1003,7 +1092,16 @@ static void sortHorizontal(SkTDArray& activeEdges, for (index = 1; index < edgeCount; ++index) { winding += activePtr->fWorkEdge.winding(); ActiveEdge* nextPtr = edgeList[index]; - if (activePtr->isCoincidentWith(nextPtr)) { + if (activePtr->isCoincidentWith(nextPtr, y)) { + // the coincident edges may not have been sorted above -- advance + // the edges and resort if needed + // OPTIMIZE: if sorting is done incrementally as new edges are added + // and not all at once as is done here, fold this test into the + // current less than test. + if (activePtr->swapCoincident(nextPtr, bottom)) { + SkTSwap(edgeList[index - 1], edgeList[index]); + SkTSwap(activePtr, nextPtr); + } if (!firstCoincident) { firstCoincident = activePtr; } @@ -1041,7 +1139,16 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, int lastWinding = winding; winding += wt.winding(); if (activePtr->done(y)) { - continue; + // FIXME: if this is successful, rewrite done to take bottom as well + if (activePtr->fDone) { + continue; + } + if (activePtr->fYBottom >= bottom) { + continue; + } + if (0) { + SkDebugf("%s bot %g,%g\n", __FUNCTION__, activePtr->fYBottom, bottom); + } } int opener = (lastWinding & windingMask) == 0; bool closer = (winding & windingMask) == 0; @@ -1077,6 +1184,7 @@ static void stitchEdge(SkTDArray& edgeList, SkScalar y, } outBuilder.addLine(clipped); } + activePtr->fSkip = false; } else { // FIXME: add all curve types SkASSERT(0); @@ -1119,7 +1227,7 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { addIntersectingTs(currentPtr, lastPtr); computeInterceptBottom(activeEdges, y, bottom); SkTDArray activeEdgeList; - sortHorizontal(activeEdges, activeEdgeList, windingMask); + sortHorizontal(activeEdges, activeEdgeList, windingMask, y, bottom); stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder); } y = bottom; diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp new file mode 100644 index 0000000..3ea0e0b --- /dev/null +++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp @@ -0,0 +1,423 @@ +#include "EdgeWalker_Test.h" +#include "Intersection_Tests.h" + +static void testSimplifyTriangle() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(10,10); // triangle |\ . + path.lineTo(10,30); // |_\ . + path.lineTo(20,30); + path.close(); + path.moveTo(20,10); // triangle /| + path.lineTo(10,30); // /_| + path.lineTo(20,30); + path.close(); + simplify(path, true, out); // expect |\/| + comparePaths(path, out); // |__| +} + +static void testSimplifyTriangle3() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(3, 1); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle4() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(2, 1); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle5() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 1); + path.lineTo(2, 1); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle6() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(3, 1); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle7() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 1); + path.lineTo(0, 2); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle8() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 1); + path.lineTo(1, 2); + path.lineTo(1, 3); + path.lineTo(0, 1); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle9() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 1); + path.lineTo(2, 1); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle10() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle11() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 2); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 1); + path.lineTo(2, 2); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle12() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 2); + path.lineTo(0, 0); + path.close(); + path.moveTo(2, 0); + path.lineTo(0, 3); + path.lineTo(1, 1); + path.lineTo(2, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle13() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 3); + path.lineTo(0, 0); + path.close(); + path.moveTo(3, 0); + path.lineTo(0, 3); + path.lineTo(1, 1); + path.lineTo(3, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle14() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.lineTo(0, 0); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle15() { + SkPath path, out; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(1, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(2, 2); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle16() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(1, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(1, 3); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyTriangle17() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(1, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 3); + path.lineTo(0, 1); + path.close(); + simplify(path, true, out); + comparePaths(path, out); +} + +static void testSimplifyWindingParallelogram() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(20,10); // parallelogram _ + path.lineTo(30,30); // \ \ . + path.lineTo(40,30); // \_\ . + path.lineTo(30,10); + path.close(); + path.moveTo(20,10); // parallelogram _ + path.lineTo(10,30); // / / + path.lineTo(20,30); // /_/ + path.lineTo(30,10); + path.close(); + simplify(path, true, out); // expect _ + comparePaths(path, out); // / \ . +} // /___\ . + +static void testSimplifyXorParallelogram() { + SkPath path, out; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(20,10); // parallelogram _ + path.lineTo(30,30); // \ \ . + path.lineTo(40,30); // \_\ . + path.lineTo(30,10); + path.close(); + path.moveTo(20,10); // parallelogram _ + path.lineTo(10,30); // / / + path.lineTo(20,30); // /_/ + path.lineTo(30,10); + path.close(); + simplify(path, true, out); // expect _ + comparePaths(path, out); // \ / +} // + +static void testSimplifyTriangle2() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(10,10); // triangle |\ . + path.lineTo(10,30); // |_\ . + path.lineTo(20,30); + path.close(); + path.moveTo(10,10); // triangle _ + path.lineTo(20,10); // \ | + path.lineTo(20,30); // \| + path.close(); // _ + simplify(path, true, out); // expect | | + comparePaths(path, out); // |_| +} + +static void testSimplifyNondegenerate4x4Triangles() { + char pathStr[1024]; + bzero(pathStr, sizeof(pathStr)); + for (int a = 0; a < 15; ++a) { + int ax = a & 0x03; + int ay = a >> 2; + for (int b = a + 1; b < 16; ++b) { + int bx = b & 0x03; + int by = b >> 2; + for (int c = a + 1; c < 16; ++c) { + if (b == c) { + continue; + } + int cx = c & 0x03; + int cy = c >> 2; + if ((bx - ax) * (cy - ay) == (by - ay) * (cx - ax)) { + continue; + } + for (int d = 0; d < 15; ++d) { + int dx = d & 0x03; + int dy = d >> 2; + for (int e = d + 1; e < 16; ++e) { + int ex = e & 0x03; + int ey = e >> 2; + for (int f = d + 1; f < 16; ++f) { + if (e == f) { + continue; + } + int fx = f & 0x03; + int fy = f >> 2; + if ((ex - dx) * (fy - dy) == (ey - dy) * (fx - dx)) { + continue; + } + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(ax, ay); + path.lineTo(bx, by); + path.lineTo(cx, cy); + path.close(); + path.moveTo(dx, dy); + path.lineTo(ex, ey); + path.lineTo(fx, fy); + path.close(); + if (1) { + char* str = pathStr; + str += sprintf(str, " path.moveTo(%d, %d);\n", ax, ay); + str += sprintf(str, " path.lineTo(%d, %d);\n", bx, by); + str += sprintf(str, " path.lineTo(%d, %d);\n", cx, cy); + str += sprintf(str, " path.close();\n"); + str += sprintf(str, " path.moveTo(%d, %d);\n", dx, dy); + str += sprintf(str, " path.lineTo(%d, %d);\n", ex, ey); + str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy); + str += sprintf(str, " path.close();"); + } + simplify(path, true, out); + comparePaths(path, out); + path.setFillType(SkPath::kEvenOdd_FillType); + simplify(path, true, out); + comparePaths(path, out); + } + } + } + } + } + } +} + +static void testPathTriangleRendering() { + SkPath one, two; + one.moveTo(0, 0); + one.lineTo(3, 3); + one.lineTo(0, 3); + one.lineTo(1, 2); + one.close(); + for (float x = .1f; x <= 2.9f; x += .1f) { + SkDebugf("%s x=%g\n", __FUNCTION__, x); + two.moveTo(0, 0); + two.lineTo(x, x); + two.lineTo(3, 3); + two.lineTo(0, 3); + two.lineTo(1, 2); + two.close(); + comparePaths(one, two); + two.reset(); + } +} + +static void (*simplifyTests[])() = { + testSimplifyTriangle17, + testSimplifyTriangle16, + testSimplifyTriangle15, + testSimplifyTriangle14, + testSimplifyTriangle13, + testSimplifyTriangle12, + testSimplifyTriangle11, + testSimplifyTriangle10, + testSimplifyTriangle7, + testSimplifyTriangle9, + testSimplifyTriangle8, + testSimplifyTriangle6, + testSimplifyTriangle5, + testSimplifyTriangle4, + testSimplifyTriangle3, + testSimplifyTriangle, + testSimplifyTriangle2, + testSimplifyWindingParallelogram, + testSimplifyXorParallelogram, + testSimplifyNondegenerate4x4Triangles, + testPathTriangleRendering, +}; + +static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); + +static void (*firstTest)() = 0; + +void SimplifyPolygonPaths_Test() { + size_t index = 0; + if (firstTest) { + while (index < simplifyTestsCount && simplifyTests[index] != firstTest) { + ++index; + } + } + for ( ; index < simplifyTestsCount; ++index) { + (*simplifyTests[index])(); + } +} + diff --git a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp new file mode 100644 index 0000000..a42a970 --- /dev/null +++ b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp @@ -0,0 +1,452 @@ +#include "EdgeWalker_Test.h" +#include "Intersection_Tests.h" + +static void testSimplifyCoincidentVertical() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(10, 10, 30, 30); + path.addRect(10, 30, 30, 40); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 30, 40)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } +} + +static void testSimplifyCoincidentHorizontal() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(10, 10, 30, 30); + path.addRect(30, 10, 40, 30); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 40, 30)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } +} + +static void testSimplifyMulti() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(10, 10, 30, 30); + path.addRect(20, 20, 40, 40); + simplify(path, true, out); + SkPath expected; + expected.setFillType(SkPath::kEvenOdd_FillType); + expected.moveTo(10,10); // two cutout corners + expected.lineTo(10,30); + expected.lineTo(20,30); + expected.lineTo(20,40); + expected.lineTo(40,40); + expected.lineTo(40,20); + expected.lineTo(30,20); + expected.lineTo(30,10); + expected.lineTo(10,10); + expected.close(); + if (out != expected) { + SkDebugf("%s expected equal\n", __FUNCTION__); + } + + path = out; + path.addRect(30, 10, 40, 20); + path.addRect(10, 30, 20, 40); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } + + path = out; + path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); + simplify(path, true, out); + if (!out.isEmpty()) { + SkDebugf("%s expected empty\n", __FUNCTION__); + } +} + +static void testSimplifyAddL() { + SkPath path, out; + path.moveTo(10,10); // 'L' shape + path.lineTo(10,40); + path.lineTo(40,40); + path.lineTo(40,20); + path.lineTo(30,20); + path.lineTo(30,10); + path.lineTo(10,10); + path.close(); + path.addRect(30, 10, 40, 20); // missing notch of 'L' + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } +} + +static void testSimplifyCoincidentCCW() { + SkPath path, out; + path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); + path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } +} + +static void testSimplifyCoincidentCW() { + SkPath path, out; + path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); + path.addRect(10, 10, 40, 40, SkPath::kCW_Direction); + simplify(path, true, out); + if (!out.isEmpty()) { + SkDebugf("%s expected empty\n", __FUNCTION__); + } +} + +static void testSimplifyCorner() { + SkPath path, out; + path.addRect(10, 10, 20, 20, SkPath::kCCW_Direction); + path.addRect(20, 20, 40, 40, SkPath::kCW_Direction); + simplify(path, true, out); + SkTDArray boundsArray; + contourBounds(out, boundsArray); + if (boundsArray.count() != 2) { + SkDebugf("%s expected 2 contours\n", __FUNCTION__); + return; + } + SkRect one = SkRect::MakeLTRB(10, 10, 20, 20); + SkRect two = SkRect::MakeLTRB(20, 20, 40, 40); + if (boundsArray[0] != one && boundsArray[0] != two + || boundsArray[1] != one && boundsArray[1] != two) { + SkDebugf("%s expected match\n", __FUNCTION__); + } +} + +static void testSimplifyDiagonal() { + SkRect rect2 = SkRect::MakeXYWH(10, 10, 10, 10); + for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { + for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { + for (int x = 0; x <= 20; x += 20) { + for (int y = 0; y <= 20; y += 20) { + SkPath path, out; + SkRect rect1 = SkRect::MakeXYWH(x, y, 10, 10); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + SkPath::Iter iter(out, false); + SkPoint pts[4], lastLine[2]; + SkPath::Verb verb; + SkRect bounds[2]; + bounds[0].setEmpty(); + bounds[1].setEmpty(); + SkRect* boundsPtr = bounds; + int count = 0, segments = 0; + bool lastLineSet = false; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + if (!boundsPtr->isEmpty()) { + SkASSERT(boundsPtr == bounds); + ++boundsPtr; + } + boundsPtr->set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); + count = 0; + lastLineSet = false; + break; + case SkPath::kLine_Verb: + if (lastLineSet) { + SkASSERT((lastLine[1].fX - lastLine[0].fX) * + (pts[1].fY - lastLine[0].fY) != + (lastLine[1].fY - lastLine[0].fY) * + (pts[1].fX - lastLine[0].fX)); + } + lastLineSet = true; + lastLine[0] = pts[0]; + lastLine[1] = pts[1]; + count = 1; + ++segments; + break; + case SkPath::kClose_Verb: + count = 0; + break; + default: + SkDEBUGFAIL("bad verb"); + return; + } + for (int i = 1; i <= count; ++i) { + boundsPtr->growToInclude(pts[i].fX, pts[i].fY); + } + } + if (boundsPtr != bounds) { + SkASSERT((bounds[0] == rect1 || bounds[1] == rect1) + && (bounds[0] == rect2 || bounds[1] == rect2)); + } else { + SkASSERT(segments == 8); + } + } + } + } + } +} + +static void assertOneContour(const SkPath& out, bool edge, bool extend) { + SkPath::Iter iter(out, false); + SkPoint pts[4]; + SkPath::Verb verb; + SkRect bounds; + bounds.setEmpty(); + int count = 0; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + SkASSERT(count == 0); + break; + case SkPath::kLine_Verb: + SkASSERT(pts[0].fX == pts[1].fX || pts[0].fY == pts[1].fY); + ++count; + break; + case SkPath::kClose_Verb: + break; + default: + SkDEBUGFAIL("bad verb"); + return; + } + } + SkASSERT(count == (extend ? 4 : edge ? 6 : 8)); +} + +static void testSimplifyCoincident() { + // outside to inside, outside to right, outside to outside + // left to inside, left to right, left to outside + // inside to right, inside to outside + // repeat above for left, right, bottom + SkScalar start[] = { 0, 10, 20 }; + size_t startCount = sizeof(start) / sizeof(start[0]); + SkScalar stop[] = { 30, 40, 50 }; + size_t stopCount = sizeof(stop) / sizeof(stop[0]); + SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); + for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { + for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { + for (size_t startIndex = 0; startIndex < startCount; ++startIndex) { + for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) { + bool extend = start[startIndex] == rect2.fLeft && stop[stopIndex] == rect2.fRight; + bool edge = start[startIndex] == rect2.fLeft || stop[stopIndex] == rect2.fRight; + SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 10); + SkPath path, out; + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + assertOneContour(out, edge, extend); + + path.reset(); + rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 50); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + assertOneContour(out, edge, extend); + + path.reset(); + rect1 = SkRect::MakeLTRB(0, start[startIndex], 10, stop[stopIndex]); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + assertOneContour(out, edge, extend); + + path.reset(); + rect1 = SkRect::MakeLTRB(40, start[startIndex], 50, stop[stopIndex]); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + assertOneContour(out, edge, extend); + } + } + } + } +} + +static void testSimplifyOverlap() { + SkScalar start[] = { 0, 10, 20 }; + size_t startCount = sizeof(start) / sizeof(start[0]); + SkScalar stop[] = { 30, 40, 50 }; + size_t stopCount = sizeof(stop) / sizeof(stop[0]); + SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); + for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) { + for (size_t lefty = 0; lefty < startCount; ++lefty) { + for (size_t righty = 0; righty < stopCount; ++righty) { + for (size_t toppy = 0; toppy < startCount; ++toppy) { + for (size_t botty = 0; botty < stopCount; ++botty) { + SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy], + stop[righty], stop[botty]); + SkPath path, out; + path.addRect(rect1, static_cast(dir)); + path.addRect(rect2, static_cast(dir)); + simplify(path, true, out); + comparePaths(path, out); + } + } + } + } + } +} + +static void testSimplifyOverlapTiny() { + SkScalar start[] = { 0, 1, 2 }; + size_t startCount = sizeof(start) / sizeof(start[0]); + SkScalar stop[] = { 3, 4, 5 }; + size_t stopCount = sizeof(stop) / sizeof(stop[0]); + SkRect rect2 = SkRect::MakeXYWH(1, 1, 3, 3); + for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) { + for (size_t lefty = 0; lefty < startCount; ++lefty) { + for (size_t righty = 0; righty < stopCount; ++righty) { + for (size_t toppy = 0; toppy < startCount; ++toppy) { + for (size_t botty = 0; botty < stopCount; ++botty) { + SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy], + stop[righty], stop[botty]); + SkPath path, out; + path.addRect(rect1, static_cast(dir)); + path.addRect(rect2, static_cast(dir)); + simplify(path, true, out); + comparePathsTiny(path, out); + } + } + } + } + } +} + +static void testSimplifyDegenerate() { + SkScalar start[] = { 0, 10, 20 }; + size_t startCount = sizeof(start) / sizeof(start[0]); + SkScalar stop[] = { 30, 40, 50 }; + size_t stopCount = sizeof(stop) / sizeof(stop[0]); + SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30); + for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) { + for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) { + for (size_t startIndex = 0; startIndex < startCount; ++startIndex) { + for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) { + SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 0); + SkPath path, out; + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s 1 expected rect\n", __FUNCTION__); + } + if (rect != rect2) { + SkDebugf("%s 1 expected union\n", __FUNCTION__); + } + + path.reset(); + rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 40); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + if (!out.isRect(&rect)) { + SkDebugf("%s 2 expected rect\n", __FUNCTION__); + } + if (rect != rect2) { + SkDebugf("%s 2 expected union\n", __FUNCTION__); + } + + path.reset(); + rect1 = SkRect::MakeLTRB(0, start[startIndex], 0, stop[stopIndex]); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + if (!out.isRect(&rect)) { + SkDebugf("%s 3 expected rect\n", __FUNCTION__); + } + if (rect != rect2) { + SkDebugf("%s 3 expected union\n", __FUNCTION__); + } + + path.reset(); + rect1 = SkRect::MakeLTRB(40, start[startIndex], 40, stop[stopIndex]); + path.addRect(rect1, static_cast(outDir)); + path.addRect(rect2, static_cast(inDir)); + simplify(path, true, out); + if (!out.isRect(&rect)) { + SkDebugf("%s 4 expected rect\n", __FUNCTION__); + } + if (rect != rect2) { + SkDebugf("%s 4 expected union\n", __FUNCTION__); + } + } + } + } + } +} + +static void testSimplifyDegenerate1() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.addRect( 0, 0, 0, 30); + path.addRect(10, 10, 40, 40); + simplify(path, true, out); + SkRect rect; + if (!out.isRect(&rect)) { + SkDebugf("%s expected rect\n", __FUNCTION__); + } + if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { + SkDebugf("%s expected union\n", __FUNCTION__); + } +} + +static void (*simplifyTests[])() = { + testSimplifyOverlapTiny, + testSimplifyDegenerate1, + testSimplifyCorner, + testSimplifyDegenerate, + testSimplifyOverlap, + testSimplifyDiagonal, + testSimplifyCoincident, + testSimplifyCoincidentCW, + testSimplifyCoincidentCCW, + testSimplifyCoincidentVertical, + testSimplifyCoincidentHorizontal, + testSimplifyAddL, + testSimplifyMulti, +}; + +static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); + +static void (*firstTest)() = 0; + +void SimplifyRectangularPaths_Test() { + size_t index = 0; + if (firstTest) { + while (index < simplifyTestsCount && simplifyTests[index] != firstTest) { + ++index; + } + } + for ( ; index < simplifyTestsCount; ++index) { + if (simplifyTests[index] == testSimplifyCorner) { + // testSimplifyCorner fails because it expects two contours, where + // only one is returned. Both results are reasonable, but if two + // contours are desirable, or if we provide an option to choose + // between longer contours and more contours, turn this back on. For + // the moment, testSimplifyDiagonal also checks the test case, and + // permits either two rects or one non-crossing poly as valid + // unreported results. + continue; + } + (*simplifyTests[index])(); + } +} + diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h new file mode 100644 index 0000000..3911004 --- /dev/null +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -0,0 +1,9 @@ + + +#include "SkPath.h" + +extern void contourBounds(const SkPath& path, SkTDArray& boundsArray); +extern void comparePaths(const SkPath& one, const SkPath& two); +extern void comparePathsTiny(const SkPath& one, const SkPath& two); +extern void simplify(const SkPath& path, bool asFill, SkPath& simple); + diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp new file mode 100644 index 0000000..eb1509e --- /dev/null +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -0,0 +1,190 @@ +#include "EdgeWalker_Test.h" +#include "Intersection_Tests.h" +#include "SkBitmap.h" +#include "SkCanvas.h" +#include "SkPaint.h" + +static bool gDrawLastAsciiPaths = true; +static bool gDrawAllAsciiPaths = false; +static bool gShowPath = true; + +static void showPath(const char* str, const SkPath& path) { + if (!gShowPath) { + return; + } + SkDebugf("%s\n", str); + SkPath::Iter iter(path, true); + uint8_t verb; + SkPoint pts[4]; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + SkDebugf("path.moveTo(%g, %g);\n", pts[0].fX, pts[0].fY); + continue; + case SkPath::kLine_Verb: + SkDebugf("path.lineTo(%g, %g);\n", pts[1].fX, pts[1].fY); + break; + case SkPath::kQuad_Verb: + SkDebugf("path.quadTo(%g, %g, %g, %g);\n", + pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); + break; + case SkPath::kCubic_Verb: + SkDebugf("path.cubicTo(%g, %g, %g, %g);\n", + pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, + pts[3].fX, pts[3].fY); + break; + case SkPath::kClose_Verb: + SkDebugf("path.close();\n"); + continue; + default: + SkDEBUGFAIL("bad verb"); + return; + } + } +} + +static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) { + const SkRect& bounds1 = one.getBounds(); + const SkRect& bounds2 = two.getBounds(); + SkRect larger = bounds1; + larger.join(bounds2); + SkBitmap bits; + int bitWidth = SkScalarCeil(larger.width()) + 2; + int bitHeight = SkScalarCeil(larger.height()) + 2; + bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); + bits.allocPixels(); + SkCanvas canvas(bits); + canvas.drawColor(SK_ColorWHITE); + SkPaint paint; + canvas.save(); + canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); + canvas.drawPath(one, paint); + canvas.restore(); + canvas.save(); + canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1); + canvas.drawPath(two, paint); + canvas.restore(); + for (int y = 0; y < bitHeight; ++y) { + uint32_t* addr1 = bits.getAddr32(0, y); + uint32_t* addr2 = bits.getAddr32(bitWidth, y); + for (int x = 0; x < bitWidth; ++x) { + if (addr1[x] != addr2[x]) { + return false; + break; + } + } + } + return true; +} + +static void drawAsciiPaths(const SkPath& one, const SkPath& two, + bool drawPaths) { + if (!drawPaths) { + return; + } + if (0) { + showPath("one:", one); + showPath("two:", two); + } + const SkRect& bounds1 = one.getBounds(); + const SkRect& bounds2 = two.getBounds(); + SkRect larger = bounds1; + larger.join(bounds2); + SkBitmap bits; + int bitWidth = SkScalarCeil(larger.width()) + 2; + int bitHeight = SkScalarCeil(larger.height()) + 2; + bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); + bits.allocPixels(); + SkCanvas canvas(bits); + canvas.drawColor(SK_ColorWHITE); + SkPaint paint; + canvas.save(); + canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); + canvas.drawPath(one, paint); + canvas.restore(); + canvas.save(); + 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; + char* outPtr = out; + for (x = 0; x < bitWidth; ++x) { + *outPtr++ = addr1[x] == (uint32_t) -1 ? '_' : 'x'; + } + *outPtr++ = '|'; + for (x = bitWidth; x < bitWidth * 2; ++x) { + *outPtr++ = addr1[x] == (uint32_t) -1 ? '_' : 'x'; + } + *outPtr++ = '\0'; + SkDebugf("%s\n", out); + } +} + +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); + SkPath scaledOne, scaledTwo; + one.transform(scale, &scaledOne); + two.transform(scale, &scaledTwo); + if (pathsDrawTheSame(scaledOne, scaledTwo)) { + return true; + } + drawAsciiPaths(scaledOne, scaledTwo, drawPaths); + return false; +} + +void comparePaths(const SkPath& one, const SkPath& two) { + if (pathsDrawTheSame(one, two)) { + return; + } + drawAsciiPaths(one, two, gDrawAllAsciiPaths); + for (int x = 9; x <= 33; ++x) { + if (scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths)) { + return; + } + } + if (!gDrawAllAsciiPaths) { + scaledDrawTheSame(one, two, 9, 7, gDrawLastAsciiPaths); + } + showPath("original:", one); + showPath("simplified:", two); + SkASSERT(0); +} + +// doesn't work yet +void comparePathsTiny(const SkPath& one, const SkPath& two) { + const SkRect& bounds1 = one.getBounds(); + const SkRect& bounds2 = two.getBounds(); + SkRect larger = bounds1; + larger.join(bounds2); + SkBitmap bits; + int bitWidth = SkScalarCeil(larger.width()) + 2; + int bitHeight = SkScalarCeil(larger.height()) + 2; + bits.setConfig(SkBitmap::kA1_Config, bitWidth * 2, bitHeight); + bits.allocPixels(); + SkCanvas canvas(bits); + canvas.drawColor(SK_ColorWHITE); + SkPaint paint; + canvas.save(); + canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); + canvas.drawPath(one, paint); + canvas.restore(); + canvas.save(); + canvas.translate(-bounds2.fLeft + 1, -bounds2.fTop + 1); + canvas.drawPath(two, paint); + canvas.restore(); + for (int y = 0; y < bitHeight; ++y) { + uint8_t* addr1 = bits.getAddr1(0, y); + uint8_t* addr2 = bits.getAddr1(bitWidth, y); + for (int x = 0; x < bits.rowBytes(); ++x) { + SkASSERT(addr1[x] == addr2[x]); + } + } +} + diff --git a/experimental/Intersection/TSearch.h b/experimental/Intersection/TSearch.h index 44342e0..e4c4e95 100644 --- a/experimental/Intersection/TSearch.h +++ b/experimental/Intersection/TSearch.h @@ -3,40 +3,32 @@ // FIXME: Move this templated version into SKTSearch.h template -static void QSort_Partition(T** first, T** last) +static T** QSort_Partition(T** left, T** right, T** pivot) { - T** left = first; - T** rite = last; - T** pivot = left; - - while (left <= rite) { - while (left < last && **left < **pivot) - left += 1; - while (first < rite && **pivot < **rite) - rite -= 1; - if (left <= rite) { - if (left < rite) { - SkTSwap(*left, *rite); - } - left += 1; - rite -= 1; + T* pivotValue = *pivot; + SkTSwap(*pivot, *right); + T** newPivot = left; + while (left < right) { + if (**left < *pivotValue) { + SkTSwap(*left, *newPivot); + newPivot += 1; } + left += 1; } - if (first < rite) - QSort_Partition(first, rite); - if (left < last) - QSort_Partition(left, last); + SkTSwap(*newPivot, *right); + return newPivot; } template -void QSort(T** base, size_t count) +void QSort(T** left, T** right) { - SkASSERT(base); - - if (count <= 1) { + if (left >= right) { return; } - QSort_Partition(base, base + (count - 1)); + T** pivot = left + (right - left >> 1); + pivot = QSort_Partition(left, right, pivot); + QSort(left, pivot - 1); + QSort(pivot + 1, right); } template -- 2.7.4