From 6b9cfb34a3ed256a56571ebe3e39f5df940a16fb Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Thu, 16 Feb 2012 21:24:41 +0000 Subject: work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@3212 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/EdgeWalker.cpp | 123 +++++++++++++++++++++++++++---- 1 file changed, 109 insertions(+), 14 deletions(-) (limited to 'experimental/Intersection') diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 22db312699..b810a91ba0 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -515,7 +515,11 @@ void walk() { fWinding = winding; addEdge(); } - complete(); + if (!complete()) { + if (fCurrentEdge) { + fEdges.pop_back(); + } + } } private: @@ -790,8 +794,21 @@ static void makeEdgeList(SkTArray& edges, InEdge& edgeSentinel, QSort(edgeList.begin(), edgeCount); } + +static void skipCoincidence(int lastWinding, int winding, int windingMask, + ActiveEdge* activePtr, ActiveEdge* firstCoincident) { + if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { + return; + } + if (lastWinding) { + activePtr->fSkip = false; + } else { + firstCoincident->fSkip = false; + } +} + static void sortHorizontal(SkTDArray& activeEdges, - SkTDArray& edgeList) { + SkTDArray& edgeList, int windingMask) { size_t edgeCount = activeEdges.count(); if (edgeCount == 0) { return; @@ -805,18 +822,40 @@ static void sortHorizontal(SkTDArray& activeEdges, } QSort(edgeList.begin(), edgeCount); // 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 + // addition to removing the coincident edges, the remaining edges would need + // to have a different winding value, possibly different per intercept span. + int lastWinding = 0; + bool lastSkipped = false; ActiveEdge* activePtr = edgeList[0]; + ActiveEdge* firstCoincident = NULL; + int winding = 0; for (index = 1; index < edgeCount; ++index) { + winding += activePtr->fWorkEdge.winding(); ActiveEdge* nextPtr = edgeList[index]; - if (activePtr->fX == nextPtr->fX && activePtr->fWorkEdge.winding() - + nextPtr->fWorkEdge.winding() == 0) { + if (activePtr->fX == nextPtr->fX) { SkDebugf("%s coincident\n", __FUNCTION__); - // OPTIMIZE: remove edges? - activePtr->fSkip = true; - nextPtr->fSkip = true; + if (!firstCoincident) { + firstCoincident = activePtr; + } + activePtr->fSkip = nextPtr->fSkip = lastSkipped = true; + } else if (lastSkipped) { + skipCoincidence(lastWinding, winding, windingMask, activePtr, + firstCoincident); + lastSkipped = false; + firstCoincident = NULL; + } + if (!lastSkipped) { + lastWinding = winding; } activePtr = nextPtr; } + if (lastSkipped) { + winding += activePtr->fWorkEdge.winding(); + skipCoincidence(lastWinding, winding, windingMask, activePtr, + firstCoincident); + } } // stitch edge and t range that satisfies operation @@ -901,7 +940,7 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { addIntersectingTs(currentPtr, lastPtr); computeInterceptBottom(activeEdges, y, bottom); SkTDArray activeEdgeList; - sortHorizontal(activeEdges, activeEdgeList); + sortHorizontal(activeEdges, activeEdgeList, windingMask); stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder); y = bottom; currentPtr = advanceEdges(activeEdges, currentPtr, lastPtr, y); @@ -947,10 +986,34 @@ static void testSimplifyMulti() { 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); @@ -980,21 +1043,53 @@ static void testSimplifyAddL() { } } +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__); + } +} + void testSimplify(); void (*simplifyTests[])() = { - testSimplifyCoincidentVertical, // 0 - testSimplifyCoincidentHorizontal, // 1 - testSimplifyMulti, // 2 - testSimplifyAddL // 3 + testSimplifyCoincidentCW, + testSimplifyCoincidentCCW, + testSimplifyCoincidentVertical, + testSimplifyCoincidentHorizontal, + testSimplifyAddL, + testSimplifyMulti, }; size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); -static int firstTest = 3; +static void (*firstTest)() = 0; void testSimplify() { - for (size_t index = firstTest; index < simplifyTestsCount; ++index) { + size_t index = 0; + if (firstTest) { + while (index < simplifyTestsCount && simplifyTests[index] != firstTest) { + ++index; + } + } + for ( ; index < simplifyTestsCount; ++index) { (*simplifyTests[index])(); } } -- cgit v1.2.3