diff options
author | 2012-07-25 20:59:42 +0000 | |
---|---|---|
committer | 2012-07-25 20:59:42 +0000 | |
commit | cc90505674cd845fcbebd7e0654c3ff04a2e4f25 (patch) | |
tree | 9e7242951cc0c7fc0710ef2a1aa1380c1d1f4c84 | |
parent | 777c3aab0a902b0917871080d99b0a249ec06298 (diff) |
shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@4771 2bbb7eff-a529-9590-31e7-b0007b416f81
-rw-r--r-- | experimental/Intersection/Simplify.cpp | 250 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyNew_Test.cpp | 20 | ||||
-rw-r--r-- | experimental/Intersection/op.htm | 31 |
3 files changed, 233 insertions, 68 deletions
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index ad24008467..7f1e7c7866 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -487,7 +487,7 @@ public: return fEnd; } - bool firstBump(int contourWinding, int sumWinding) const { + bool firstBump(int sumWinding) const { return sign() * sumWinding > 0; } @@ -755,6 +755,117 @@ public: angle->set(edge, fVerb, this, start, end); } + void addCancelOutsides(const SkTDArray<double>& outsideTs, Segment& other, + double oEnd) { + int tIndex = -1; + int tCount = fTs.count(); + int oIndex = -1; + int oCount = other.fTs.count(); + double tStart = outsideTs[0]; + double oStart = outsideTs[1]; + do { + ++tIndex; + } while (tStart - fTs[tIndex].fT >= FLT_EPSILON && tIndex < tCount); + int tIndexStart = tIndex; + do { + ++oIndex; + } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON && oIndex < oCount); + int oIndexStart = oIndex; + double nextT; + do { + nextT = fTs[++tIndex].fT; + } while (nextT < 1 && nextT - tStart < FLT_EPSILON); + double oNextT; + do { + oNextT = other.fTs[++oIndex].fT; + } while (oNextT < 1 && oNextT - oStart < FLT_EPSILON); + // at this point, spans before and after are at: + // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] + // if tIndexStart == 0, no prior span + // if nextT == 1, no following span + + // advance the span with zero winding + // if the following span exists (not past the end, non-zero winding) + // connect the two edges + if (!fTs[tIndexStart].fWindValue) { + if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { + #if DEBUG_CONCIDENT + SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, fID, other.fID, tIndexStart - 1, + fTs[tIndexStart - 1].fT, xyAtT(tIndexStart - 1).fX, + xyAtT(tIndexStart - 1).fY); + #endif + SkASSERT(0); // incomplete + } + if (nextT < 1 && fTs[tIndex].fWindValue) { + #if DEBUG_CONCIDENT + SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, fID, other.fID, tIndex, + fTs[tIndex].fT, xyAtT(tIndex).fX, + xyAtT(tIndex).fY); + #endif + addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT); + } + } else { + SkASSERT(!other.fTs[oIndexStart].fWindValue); + if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) { + #if DEBUG_CONCIDENT + SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, fID, other.fID, oIndexStart - 1, + other.fTs[oIndexStart - 1].fT, other.xyAtT(oIndexStart - 1).fX, + other.xyAtT(oIndexStart - 1).fY); + #endif + SkASSERT(0); // incomplete + } + if (oNextT < 1 && other.fTs[oIndex].fWindValue) { + #if DEBUG_CONCIDENT + SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", + __FUNCTION__, fID, other.fID, oIndex, + other.fTs[oIndex].fT, other.xyAtT(oIndex).fX, + other.xyAtT(oIndex).fY); + other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT); + #endif + } + } + } + + void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other, + double oEnd) { + // walk this to outsideTs[0] + // walk other to outsideTs[1] + // if either is > 0, add a pointer to the other, copying adjacent winding + int tIndex = -1; + int oIndex = -1; + double tStart = outsideTs[0]; + double oStart = outsideTs[1]; + do { + ++tIndex; + } while (tStart - fTs[tIndex].fT >= FLT_EPSILON); + do { + ++oIndex; + } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON); + if (tIndex > 0 || oIndex > 0) { + addTPair(tStart, other, oStart); + } + tStart = fTs[tIndex].fT; + oStart = other.fTs[oIndex].fT; + do { + double nextT; + do { + nextT = fTs[++tIndex].fT; + } while (nextT - tStart < FLT_EPSILON); + tStart = nextT; + do { + nextT = other.fTs[++oIndex].fT; + } while (nextT - oStart < FLT_EPSILON); + oStart = nextT; + if (tStart == 1 && oStart == 1) { + break; + } + addTPair(tStart, other, oStart); + } while (tStart < 1 && oStart < 1 && oEnd - oStart >= FLT_EPSILON); + } + void addCubic(const SkPoint pts[4]) { init(pts, SkPath::kCubic_Verb); fBounds.setCubicBounds(pts); @@ -889,13 +1000,14 @@ public: SkTDArray<double> oOutsideTs; do { bool decrement = test->fWindValue && oTest->fWindValue; + bool track = test->fWindValue || oTest->fWindValue; Span* end = test; double startT = end->fT; double oStartT = oTest->fT; do { if (decrement) { decrementSpan(end); - } else { + } else if (track && end->fT < 1 && oStartT < 1) { TrackOutside(outsideTs, end->fT, oStartT); } end = &fTs[++index]; @@ -904,7 +1016,7 @@ public: do { if (decrement) { other.decrementSpan(oTestStart); - } else { + } else if (track && oTestStart->fT < 1 && startT < 1) { TrackOutside(oOutsideTs, oTestStart->fT, startT); } if (!oIndex) { @@ -917,11 +1029,11 @@ public: } while (test->fT < endT - FLT_EPSILON); SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON); // FIXME: determine if canceled edges need outside ts added - if (false && !done() && outsideTs.count()) { - addTOutsides(outsideTs, other, oEndT); + if (!done() && outsideTs.count()) { + addCancelOutsides(outsideTs, other, oEndT); } - if (false && !other.done() && oOutsideTs.count()) { - other.addTOutsides(oOutsideTs, *this, endT); + if (!other.done() && oOutsideTs.count()) { + other.addCancelOutsides(oOutsideTs, *this, endT); } } @@ -942,13 +1054,17 @@ public: Span* test = &fTs[index]; Span* oTest = &other.fTs[oIndex]; SkTDArray<double> outsideTs; + SkTDArray<double> xOutsideTs; SkTDArray<double> oOutsideTs; + SkTDArray<double> oxOutsideTs; do { bool transfer = test->fWindValue && oTest->fWindValue; bool decrementOther = test->fWindValue >= oTest->fWindValue; Span* end = test; double startT = end->fT; + int startIndex = index; double oStartT = oTest->fT; + int oStartIndex = oIndex; do { if (transfer) { if (decrementOther) { @@ -957,6 +1073,11 @@ public: } else if (decrementSpan(end)) { TrackOutside(outsideTs, end->fT, oStartT); } + } else if (oTest->fWindValue) { + SkASSERT(!decrementOther); + if (startIndex > 0 && fTs[startIndex - 1].fWindValue) { + TrackOutside(xOutsideTs, end->fT, oStartT); + } } end = &fTs[++index]; } while (end->fT - test->fT < FLT_EPSILON); @@ -969,6 +1090,11 @@ public: } else if (other.decrementSpan(oEnd)) { TrackOutside(oOutsideTs, oEnd->fT, startT); } + } else if (test->fWindValue) { + SkASSERT(!decrementOther); + if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) { + SkASSERT(0); // track for later? + } } oEnd = &other.fTs[++oIndex]; } while (oEnd->fT - oTest->fT < FLT_EPSILON); @@ -977,67 +1103,36 @@ public: } while (test->fT < endT - FLT_EPSILON); SkASSERT(oTest->fT < oEndT + FLT_EPSILON); SkASSERT(oTest->fT > oEndT - FLT_EPSILON); - if (!done() && outsideTs.count()) { - addTOutsides(outsideTs, other, oEndT); + if (!done()) { + if (outsideTs.count()) { + addCoinOutsides(outsideTs, other, oEndT); + } + if (xOutsideTs.count()) { + addCoinOutsides(xOutsideTs, other, oEndT); + } } if (!other.done() && oOutsideTs.count()) { - other.addTOutsides(oOutsideTs, *this, endT); + other.addCoinOutsides(oOutsideTs, *this, endT); } } - - void addTOutsides(const SkTDArray<double>& outsideTs, Segment& other, - double oEnd) { - // walk this to outsideTs[0] - // walk other to outsideTs[1] - // if either is > 0, add a pointer to the other, copying adjacent winding - int tIndex = -1; + + // FIXME: this doesn't prevent the same span from being added twice + // fix in caller, assert here? + void addTPair(double t, Segment& other, double otherT) { int tCount = fTs.count(); - int oIndex = -1; - int oCount = other.fTs.count(); - double tStart = outsideTs[0]; - double oStart = outsideTs[1]; - Span* tSpan; - Span* oSpan; - do { - tSpan = &fTs[++tIndex]; - if (tStart - tSpan->fT < FLT_EPSILON) { + for (int tIndex = 0; tIndex < tCount; ++tIndex) { + const Span& span = fTs[tIndex]; + if (span.fT > t) { break; } - } while (tIndex < tCount); - do { - oSpan = &other.fTs[++oIndex]; - if (oStart - oSpan->fT < FLT_EPSILON) { - break; - } - } while (oIndex < oCount); - if (tIndex > 0 || oIndex > 0) { - addTPair(tStart, other, oStart); - // note: counts for fT, other.fT are one greater - } else { - --tCount; - --oCount; - } - tStart = fTs[tIndex].fT; - oStart = other.fTs[oIndex].fT; - do { - do { - tSpan = &fTs[++tIndex]; - } while (tSpan->fT - tStart < FLT_EPSILON && tIndex < tCount); - tStart = fTs[tIndex].fT; - do { - oSpan = &other.fTs[++oIndex]; - } while (oSpan->fT - oStart < FLT_EPSILON && oIndex < oCount); - oStart = other.fTs[oIndex].fT; - if (tStart == 1 && oStart == 1) { - break; + if (span.fT == t && span.fOther == &other && span.fOtherT == otherT) { +#if DEBUG_ADD_T_PAIR + SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", + __FUNCTION__, fID, t, other.fID, otherT); +#endif + return; } - addTPair(tStart, other, oStart); - ++tCount; - ++oCount; - } while (tStart < 1 && oStart < 1 && oEnd - oSpan->fT >= FLT_EPSILON); - } - - void addTPair(double t, Segment& other, double otherT) { + } #if DEBUG_ADD_T_PAIR SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", __FUNCTION__, fID, t, other.fID, otherT); @@ -1229,13 +1324,18 @@ public: int contourWinding, bool firstFind, bool active, const int startIndex, const int endIndex, int& nextStart, int& nextEnd, int& spanWinding) { + + start here; + // winding is a mess + // try to simplify what we got + int flipped = 1; int sumWinding = winding + spanWinding; - if (sumWinding == 0) { + if (sumWinding == 0 || (false && contourWinding && !firstFind)) { sumWinding = spanWinding; } bool insideContour = contourWinding && contourWinding * sumWinding < 0; - if (insideContour) { + if (insideContour && (true || !firstFind)) { sumWinding = contourWinding; } @@ -1280,7 +1380,7 @@ public: #if DEBUG_SORT debugShowSort(sorted, firstIndex, contourWinding, sumWinding); #endif - bool doBump = sorted[firstIndex]->firstBump(contourWinding, sumWinding); + bool doBump = sorted[firstIndex]->firstBump(sumWinding); #if DEBUG_WINDING SkDebugf("%s sumWinding=%d sign=%d (%sbump)\n", __FUNCTION__, sumWinding, sorted[firstIndex]->sign(), doBump ? "" : "no "); @@ -1343,6 +1443,10 @@ public: continue; } if (!maxWinding && innerSwap && !foundAngle) { + if (sumWinding * startWinding < 0 && flipped > 0) { + SkDebugf("%s flip?\n"); + // flipped = -flipped; + } foundAngle = nextAngle; } if (nextSegment->done()) { @@ -1951,6 +2055,18 @@ public: #endif #if DEBUG_CONCIDENT + // assert if pair has not already been added + void debugAddTPair(double t, const Segment& other, double otherT) { + for (int i = 0; i < fTs.count(); ++i) { + if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { + return; + } + } + SkASSERT(0); + } +#endif + +#if DEBUG_CONCIDENT void debugShowTs() { SkDebugf("%s %d", __FUNCTION__, fID); for (int i = 0; i < fTs.count(); ++i) { @@ -1992,7 +2108,7 @@ public: void debugShowSort(const SkTDArray<Angle*>& angles, int first, int contourWinding, int sumWinding) { SkASSERT(angles[first]->segment() == this); - bool doBump = angles[first]->firstBump(contourWinding, sumWinding); + bool doBump = angles[first]->firstBump(sumWinding); bool insideContour = contourWinding && contourWinding * sumWinding < 0; int windSum = insideContour ? contourWinding : sumWinding; int lastSum = windSum; @@ -2979,7 +3095,7 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList, SkASSERT(winding != SK_MinS32); windValue = test->windValue(angle); #if 0 - if (angle->firstBump(0, winding)) { + if (angle->firstBump(winding)) { winding -= test->windBump(angle); } #endif @@ -3083,7 +3199,7 @@ static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex, angle->segment()->debugShowSort(sorted, firstIndex, contourWinding, spanWinding); #endif - if (angle->firstBump(contourWinding, spanWinding)) { + if (angle->firstBump(spanWinding)) { spanWinding -= angle->segment()->windBump(angle); } // we care about first sign and whether wind sum indicates this @@ -3150,7 +3266,7 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { Segment* topStart = findTopContour(contourList, topContour); if (!topStart) { break; - } + } // Start at the top. Above the top is outside, below is inside. // follow edges to intersection by changing the index by direction. int index, endIndex; diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 9483b6d353..ce5934155c 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -566,12 +566,30 @@ static void testLine57() { testSimplifyx(path); } -static void (*firstTest)() = testLine57; +static void testLine58() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 1); + path.addRect(0, 12, 9, 9, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void testLine59() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(6, 6, 18, 18, (SkPath::Direction) 1); + path.addRect(4, 4, 13, 13, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void (*firstTest)() = 0; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(testLine59), + TEST(testLine58), TEST(testLine57), TEST(testLine56), TEST(testLine55), diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 2e0a44f699..73448b41a8 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -325,6 +325,16 @@ path.close(); testSimplifyx(path); </div> +<div id="testLine7b"> + path.moveTo(0,0); + path.lineTo(4,0); + path.close(); + path.moveTo(6,0); + path.lineTo(2,0); + path.lineTo(4,2); + path.close(); +</div> + <div id="testLine9"> SkPath path, simple; path.moveTo(0,4); @@ -374,6 +384,11 @@ path.close(); testSimplifyx(path); </div> +<div id="testLine22"> + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); +</div> + <div id="testLine24"> path.addRect(0, 18, 12, 12, (SkPath::Direction) 0); path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); @@ -560,11 +575,25 @@ path.close(); path.addRect(12, 0, 21, 21, (SkPath::Direction) 1); </div> +<div id="testLine58"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 1); + path.addRect(0, 12, 9, 9, (SkPath::Direction) 1); +</div> + +<div id="testLine59"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(6, 6, 18, 18, (SkPath::Direction) 1); + path.addRect(4, 4, 13, 13, (SkPath::Direction) 1); +</div> + </div> <script type="text/javascript"> var testDivs = [ + testLine59, + testLine58, testLine57, testLine56, testLine55, @@ -596,11 +625,13 @@ var testDivs = [ testLine29, testLine28, testLine24, + testLine22, testLine19, testLine17, testLine13, testLine12, testLine9, + testLine7b, testLine7, testSimplifyQuadratic21, testSimplifyQuadratic20, |