diff options
Diffstat (limited to 'experimental')
| -rw-r--r-- | experimental/Intersection/EdgeWalker.cpp | 4 | ||||
| -rw-r--r-- | experimental/Intersection/EdgeWalker_Test.h | 1 | ||||
| -rw-r--r-- | experimental/Intersection/ShapeOps.h | 7 | ||||
| -rw-r--r-- | experimental/Intersection/Simplify.cpp | 419 | ||||
| -rw-r--r-- | experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp | 2 | ||||
| -rw-r--r-- | experimental/Intersection/SimplifyNew_Test.cpp | 215 | ||||
| -rw-r--r-- | experimental/Intersection/SimplifyRect4x4_Test.cpp | 119 | ||||
| -rw-r--r-- | experimental/Intersection/op.htm | 122 |
8 files changed, 684 insertions, 205 deletions
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 0f624b5633..4442e9226a 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -13,7 +13,7 @@ // FIXME: remove once debugging is complete #if 01 // set to 1 for no debugging whatsoever -const bool gRunTestsInOneThread = false; +//const bool gRunTestsInOneThread = false; #define DEBUG_ACTIVE_LESS_THAN 0 #define DEBUG_ADD 0 @@ -33,7 +33,7 @@ const bool gRunTestsInOneThread = false; #else -const bool gRunTestsInOneThread = true; +//const bool gRunTestsInOneThread = true; #define DEBUG_ACTIVE_LESS_THAN 0 #define DEBUG_ADD 01 diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index b35da6d351..e07e708f46 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -26,6 +26,7 @@ struct State4 { int b; int c; int d; + char filename[256]; pthread_t threadID; SkCanvas* canvas; SkBitmap bitmap; diff --git a/experimental/Intersection/ShapeOps.h b/experimental/Intersection/ShapeOps.h index 9cd22ec5f6..728d89e775 100644 --- a/experimental/Intersection/ShapeOps.h +++ b/experimental/Intersection/ShapeOps.h @@ -4,4 +4,9 @@ void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray); void simplify(const SkPath& path, bool asFill, SkPath& simple); void simplifyx(const SkPath& path, SkPath& simple); -extern const bool gRunTestsInOneThread; // FIXME: remove once debugging is complete +// FIXME: remove this section once debugging is complete +extern const bool gRunTestsInOneThread; +#ifdef SK_DEBUG +extern int gDebugMaxWindSum; +extern int gDebugMaxWindValue; +#endif diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index 1fd818558b..7da8c133d7 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -17,39 +17,51 @@ // A Segment contains a Span array // A Span is describes a portion of a Segment using starting and ending T // T values range from 0 to 1, where 0 is the first Point in the Segment +// An Edge is a Segment generated from a Span // FIXME: remove once debugging is complete -#if 0 // set to 1 for no debugging whatsoever +#ifdef SK_DEBUG +int gDebugMaxWindSum = SK_MaxS32; +int gDebugMaxWindValue = SK_MaxS32; +#endif + +#define DEBUG_UNUSED 0 // set to expose unused functions + +#if 0 // set to 1 for multiple thread -- no debugging -//const bool gxRunTestsInOneThread = false; +const bool gRunTestsInOneThread = false; +#define DEBUG_ACTIVE_SPANS 0 #define DEBUG_ADD_INTERSECTING_TS 0 +#define DEBUG_ADD_T_PAIR 0 #define DEBUG_BRIDGE 0 +#define DEBUG_CONCIDENT 0 #define DEBUG_CROSS 0 #define DEBUG_DUMP 0 +#define DEBUG_MARK_DONE 0 #define DEBUG_PATH_CONSTRUCTION 0 -#define DEBUG_ACTIVE_SPANS 0 +#define DEBUG_SORT 0 #define DEBUG_WINDING 0 -#define DEBUG_UNUSED 0 // set to expose unused functions -#define DEBUG_MARK_DONE 0 #else -//const bool gRunTestsInOneThread = true; +const bool gRunTestsInOneThread = true; +#define DEBUG_ACTIVE_SPANS 1 #define DEBUG_ADD_INTERSECTING_TS 0 -#define DEBUG_BRIDGE 1 -#define DEBUG_CROSS 1 +#define DEBUG_ADD_T_PAIR 1 +#define DEBUG_BRIDGE 0 +#define DEBUG_CONCIDENT 1 +#define DEBUG_CROSS 0 #define DEBUG_DUMP 1 +#define DEBUG_MARK_DONE 1 #define DEBUG_PATH_CONSTRUCTION 1 -#define DEBUG_ACTIVE_SPANS 01 -#define DEBUG_WINDING 01 -#define DEBUG_UNUSED 0 // set to expose unused functions -#define DEBUG_MARK_DONE 01 +#define DEBUG_SORT 1 +#define DEBUG_WINDING 1 #endif -#if DEBUG_ACTIVE_SPANS && !DEBUG_DUMP +#if (DEBUG_ACTIVE_SPANS || DEBUG_CONCIDENT) && !DEBUG_DUMP #undef DEBUG_DUMP #define DEBUG_DUMP 1 #endif @@ -466,6 +478,10 @@ public: } return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; } + + double dx() const { + return fDx; + } int end() const { return fEnd; @@ -925,6 +941,7 @@ public: do { if (transfer) { if (decrementOther) { + SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue); ++(end->fWindValue); } else { SkASSERT(end->fWindValue > 0); @@ -958,6 +975,7 @@ public: } } } else { + SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue); ++(oEnd->fWindValue); } } @@ -975,54 +993,93 @@ public: other.addTOutsides(oOutsideTs, *this, endT); } } - + void addTOutsides(const SkTDArray<double>& outsideTs, Segment& other, - double otherEnd) { - int count = outsideTs.count(); - double endT = 0; - int endSpan = 0; - for (int index = 0; index < count; index += 2) { - double t = outsideTs[index]; - double otherT = outsideTs[index + 1]; - if (t > 1 - FLT_EPSILON) { - return; - } - if (t - endT > FLT_EPSILON) { - endSpan = addTDonePair(t, other, otherT); + 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 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) { + break; } - do { - endT = fTs[++endSpan].fT; - } while (endT - t < FLT_EPSILON); + } 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; } - addTPair(endT, other, otherEnd); + 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; + } + addTPair(tStart, other, oStart); + ++tCount; + ++oCount; + } while (tStart < 1 && oStart < 1 && oEnd - oSpan->fT >= FLT_EPSILON); } - // match the other.fWindValue to its mates - int addTDonePair(double t, Segment& other, double otherT) { - int insertedAt = addTPair(t, other, otherT); - Span& end = fTs[insertedAt]; - SkASSERT(end.fWindValue == 1); - end.fWindValue = 0; - end.fDone = true; - ++fDoneSpans; - Span& otherEnd = other.fTs[end.fOtherIndex]; - Span* match = NULL; - if (end.fOtherIndex > 0) { - match = &other.fTs[end.fOtherIndex - 1]; - } - if (!match || match->fT < otherT) { - match = &other.fTs[end.fOtherIndex + 1]; - } - otherEnd.fWindValue = match->fWindValue; - return insertedAt; - } - - int addTPair(double t, Segment& other, double otherT) { + 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); +#endif int insertedAt = addT(t, &other); int otherInsertedAt = other.addT(otherT, this); addOtherT(insertedAt, otherT, otherInsertedAt); other.addOtherT(otherInsertedAt, t, insertedAt); - return insertedAt; + Span& newSpan = fTs[insertedAt]; + if (insertedAt > 0) { + const Span& lastSpan = fTs[insertedAt - 1]; + if (t - lastSpan.fT < FLT_EPSILON) { + int tWind = lastSpan.fWindValue; + newSpan.fWindValue = tWind; + if (!tWind) { + newSpan.fDone = true; + ++fDoneSpans; + } + } + } + int oIndex = newSpan.fOtherIndex; + if (oIndex > 0) { + const Span& lastOther = other.fTs[oIndex - 1]; + if (otherT - lastOther.fT < FLT_EPSILON) { + int oWind = lastOther.fWindValue; + Span& otherSpan = other.fTs[oIndex]; + otherSpan.fWindValue = oWind; + if (!oWind) { + otherSpan.fDone = true; + ++(other.fDoneSpans); + } + } + } } void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { @@ -1037,7 +1094,7 @@ public: addAngle(angles, end, tIndex); } } - + const Bounds& bounds() const { return fBounds; } @@ -1099,6 +1156,9 @@ public: do { int start = end; end = nextSpan(start, 1); + if (fTs[start].fWindValue == 0) { + continue; + } SkPoint edge[4]; // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can // work with the original data directly @@ -1121,7 +1181,7 @@ public: if (bestY < pt.fY) { bestY = pt.fY; bestT = foundT < 1 ? start : end; - hitT = foundT; + hitT = fTs[start].fT + (fTs[end].fT - fTs[start].fT) * foundT; } } while (fTs[end].fT != 1); return bestT; @@ -1132,6 +1192,13 @@ public: return fDoneSpans == fTs.count(); } + bool done(const Angle& angle) const { + int start = angle.start(); + int end = angle.end(); + const Span& mSpan = fTs[SkMin32(start, end)]; + return mSpan.fDone; + } + // 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 @@ -1190,20 +1257,25 @@ public: int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); + #if DEBUG_SORT + debugShowSort(sorted, firstIndex, winding); + #endif #if DEBUG_WINDING SkDebugf("%s (first) winding=%d sign=%d\n", __FUNCTION__, winding, sorted[firstIndex]->sign()); #endif bool innerSwap = false; int startWinding = winding; - if (winding * sorted[firstIndex]->sign() > 0 && active) { - // FIXME: this means winding was computed wrong by caller ? - winding = 0; - innerSwap = true; + if (sorted[firstIndex]->sign() * winding > 0) { + winding -= rewind(sorted[firstIndex]); + if (active) { + innerSwap = true; + } } int nextIndex = firstIndex + 1; int lastIndex = firstIndex != 0 ? firstIndex : angleCount; const Angle* foundAngle = NULL; + bool foundDone = false; // iterate through the angle, and compute everyone's winding bool firstEdge = true; do { @@ -1216,27 +1288,37 @@ public: int windValue = nextSegment->windValue(nextAngle); SkASSERT(windValue > 0); winding -= nextAngle->sign() * windValue; + SkASSERT(abs(winding) <= gDebugMaxWindSum); #if DEBUG_WINDING SkDebugf("%s maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, maxWinding, winding, nextAngle->sign()); #endif if (maxWinding * winding < 0) { flipped = -flipped; + #if DEBUG_WINDING SkDebugf("flipped sign %d %d\n", maxWinding, winding); + #endif } firstEdge = false; if (!winding) { if (!active) { - SkASSERT(nextAngle->segment() == this); - markWinding(SkMin32(nextAngle->start(), nextAngle->end()), - maxWinding); + markDone(SkMin32(startIndex, endIndex), startWinding); + nextSegment->markWinding(SkMin32(nextAngle->start(), + nextAngle->end()), maxWinding); #if DEBUG_WINDING SkDebugf("%s inactive\n", __FUNCTION__); #endif return NULL; } - if (!foundAngle) { + if (!foundAngle || foundDone) { foundAngle = nextAngle; + foundDone = nextSegment->done(*nextAngle); + if (flipped > 0 && maxWinding * startWinding < 0) { + flipped = -flipped; + #if DEBUG_WINDING + SkDebugf("flopped sign %d %d\n", maxWinding, winding); + #endif + } } continue; } @@ -1265,8 +1347,8 @@ public: } } } while (++nextIndex != lastIndex); - sorted[firstIndex]->segment()-> - markDone(SkMin32(startIndex, endIndex), startWinding); + SkASSERT(sorted[firstIndex]->segment() == this); + markDone(SkMin32(startIndex, endIndex), startWinding); if (!foundAngle) { return NULL; } @@ -1628,6 +1710,7 @@ public: #endif span.fDone = true; SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + SkASSERT(abs(winding) <= gDebugMaxWindSum); span.fWindSum = winding; fDoneSpans++; } @@ -1644,6 +1727,7 @@ public: #endif span.fDone = true; SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + SkASSERT(abs(winding) <= gDebugMaxWindSum); span.fWindSum = winding; fDoneSpans++; } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); @@ -1658,13 +1742,14 @@ public: if (span.fDone) { continue; } - SkASSERT(span.fWindValue == 1 || winding == 0); + // SkASSERT(span.fWindValue == 1 || winding == 0); SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); #if DEBUG_MARK_DONE const SkPoint& pt = xyAtT(&span); SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); #endif + SkASSERT(abs(winding) <= gDebugMaxWindSum); span.fWindSum = winding; } do { @@ -1673,13 +1758,14 @@ public: if (span.fDone) { continue; } - SkASSERT(span.fWindValue == 1 || winding == 0); + // SkASSERT(span.fWindValue == 1 || winding == 0); SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); #if DEBUG_MARK_DONE const SkPoint& pt = xyAtT(&span); SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); #endif + SkASSERT(abs(winding) <= gDebugMaxWindSum); span.fWindSum = winding; } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); } @@ -1724,6 +1810,15 @@ public: fTs.reset(); } + int rewind(const Angle* angle) { + SkASSERT(angle->segment() == this); + const Span& span = fTs[SkMin32(angle->start(), angle->end())]; +#if DEBUG_SORT + SkDebugf("%s offset=%d\n", __FUNCTION__, angle->sign() * span.fWindValue); +#endif + return angle->sign() * span.fWindValue; + } + // OPTIMIZATION: mark as debugging only if used solely by tests const Span& span(int tIndex) const { return fTs[tIndex]; @@ -1819,6 +1914,17 @@ public: } #endif +#if DEBUG_CONCIDENT + void debugShowTs() { + SkDebugf("%s %d", __FUNCTION__, fID); + for (int i = 0; i < fTs.count(); ++i) { + SkDebugf(" [o=%d %1.9g (%1.9g,%1.9g) w=%d]", fTs[i].fOther->fID, + fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue); + } + SkDebugf("\n"); + } +#endif + #if DEBUG_ACTIVE_SPANS void debugShowActiveSpans(int contourID, int segmentIndex) { if (done()) { @@ -1846,6 +1952,42 @@ public: } #endif +#if DEBUG_SORT + void debugShowSort(const SkTDArray<Angle*>& angles, int first, int winding) { + int index = first; + int windSum = winding; + const Angle& fAngle = *angles[first]; + const Segment& fSegment = *fAngle.segment(); + SkASSERT(&fSegment == this); + const Span& fSpan = fSegment.fTs[SkMin32(fAngle.start(), fAngle.end())]; + if (fAngle.sign() * winding < 0) { + windSum += fAngle.sign() * fSpan.fWindValue; + } + do { + const Angle& angle = *angles[index]; + const Segment& segment = *angle.segment(); + int start = angle.start(); + int end = angle.end(); + const Span& sSpan = segment.fTs[start]; + const Span& eSpan = segment.fTs[end]; + const Span& mSpan = segment.fTs[SkMin32(start, end)]; + int lastSum = windSum; + windSum -= angle.sign() * mSpan.fWindValue; + SkDebugf("%s [%d] id=%d start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" + " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n", + __FUNCTION__, index, segment.fID, start, segment.xAtT(&sSpan), + segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), + segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue, + lastSum, windSum, abs(lastSum) > abs(windSum) ? lastSum : + windSum, mSpan.fDone); + ++index; + if (index == angles.count()) { + index = 0; + } + } while (index != first); + } +#endif + private: const SkPoint* fPts; SkPath::Verb fVerb; @@ -2017,6 +2159,10 @@ public: int otherIndex = coincidence.fSegments[1]; Segment& thisOne = thisContour->fSegments[thisIndex]; Segment& other = otherContour->fSegments[otherIndex]; + #if DEBUG_CONCIDENT + thisOne.debugShowTs(); + other.debugShowTs(); + #endif double startT = coincidence.fTs[0][0]; double endT = coincidence.fTs[0][1]; if (startT > endT) { @@ -2047,6 +2193,10 @@ public: } thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); } + #if DEBUG_CONCIDENT + thisOne.debugShowTs(); + other.debugShowTs(); + #endif } } @@ -2715,8 +2865,10 @@ static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { static int innerContourCheck(SkTDArray<Contour*>& contourList, Contour* baseContour, const SkPoint& basePt) { int contourCount = contourList.count(); - int winding = 0; SkScalar bestY = SK_ScalarMin; + const Segment* test = NULL; + int tIndex; + double tHit; for (int cTest = 0; cTest < contourCount; ++cTest) { Contour* contour = contourList[cTest]; if (basePt.fY < contour->bounds().fTop) { @@ -2728,58 +2880,88 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList, if (baseContour->crosses(contour)) { continue; } - int tIndex; - double tHit; - const Segment* test = contour->crossedSegment(basePt, bestY, tIndex, - tHit); - if (!test) { - continue; + const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit); + if (next) { + test = next; } - // If the ray hit the end of a span, we need to construct the wheel of - // angles to find the span closest to the ray -- even if there are just - // two spokes on the wheel. - if (tHit == test->t(tIndex)) { - SkTDArray<Angle> angles; - int end = test->nextSpan(tIndex, 1); - if (end < 0) { - end = test->nextSpan(tIndex, -1); - } - test->addTwoAngles(tIndex, end, angles); - // test->buildAnglesInner(tIndex, angles); - test->buildAngles(tIndex, angles); - SkTDArray<Angle*> sorted; - sortAngles(angles, sorted); - const Angle* angle = sorted[0]; - test = angle->segment(); - SkScalar testDx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); - if (testDx == 0) { - angle = *(sorted.end() - 1); - test = angle->segment(); - SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0); - } - tIndex = angle->start(); // lesser Y - winding = test->windSum(SkMin32(tIndex, angle->end())); - #if DEBUG_WINDING - SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding); - #endif - } else { - winding = test->windSum(tIndex); - #if DEBUG_WINDING - SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding); - #endif + } + if (!test) { + baseContour->setWinding(0); + return 0; + } + int winding, windValue; + // If the ray hit the end of a span, we need to construct the wheel of + // angles to find the span closest to the ray -- even if there are just + // two spokes on the wheel. + if (tHit == test->t(tIndex)) { + SkTDArray<Angle> angles; + int end = test->nextSpan(tIndex, 1); + if (end < 0) { + end = test->nextSpan(tIndex, -1); } - // see if a + change in T results in a +/- change in X (compute x'(T)) - SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); - #if DEBUG_WINDING - SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); - #endif - SkASSERT(dx != 0); - if (winding * dx > 0) { // if same signs, result is negative - winding += dx > 0 ? -1 : 1; - #if DEBUG_WINDING - SkDebugf("%s 3 winding=%d\n", __FUNCTION__, winding); - #endif + test->addTwoAngles(end, tIndex, angles); + test->buildAngles(tIndex, angles); + SkTDArray<Angle*> sorted; + // OPTIMIZATION: call a sort that, if base point is the leftmost, + // returns the first counterclockwise hour before 6 o'clock, + // or if the base point is rightmost, returns the first clockwise + // hour after 6 o'clock + sortAngles(angles, sorted); +#if DEBUG_SORT + sorted[0]->segment()->debugShowSort(sorted, 0, 0); +#endif + // walk the sorted angle fan to find the lowest angle + // above the base point. Currently, the first angle in the sorted array + // is 12 noon or an earlier hour (the next counterclockwise) + int count = sorted.count(); + int left = -1; + int right = -1; + for (int index = 0; index < count; ++index) { + double indexDx = sorted[index]->dx(); + if (indexDx < 0) { + left = index; + } else if (indexDx > 0) { + right = index; + break; + } } + SkASSERT(left >= 0 || right >= 0); + if (left < 0) { + left = right; + } + const Angle* angle = sorted[left]; + test = angle->segment(); + winding = test->windSum(angle); + windValue = test->windValue(angle); + #if 0 + int firstSign = angle->sign(); + if (firstSign * winding > 0) { + winding -= test->rewind(angle); + } + #endif +#if DEBUG_WINDING + SkDebugf("%s angle winding=%d windValue=%d\n", __FUNCTION__, winding, + windValue); +#endif + } else { + winding = test->windSum(tIndex); + windValue = test->windValue(tIndex); +#if DEBUG_WINDING + SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding, + windValue); +#endif + } + // see if a + change in T results in a +/- change in X (compute x'(T)) + SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); +#if DEBUG_WINDING + SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); +#endif + SkASSERT(dx != 0); + if (winding * dx > 0) { // if same signs, result is negative + winding += dx > 0 ? -windValue : windValue; +#if DEBUG_WINDING + SkDebugf("%s final winding=%d\n", __FUNCTION__, winding); +#endif } baseContour->setWinding(winding); return winding; @@ -2851,9 +3033,12 @@ static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) { angle = sorted[++firstIndex]; winding = angle->segment()->windSum(angle); } while (winding == SK_MinS32); + #if DEBUG_SORT + angle->segment()->debugShowSort(sorted, firstIndex, winding); + #endif int firstSign = angle->sign(); if (firstSign * winding > 0) { - winding -= firstSign; + winding -= angle->segment()->rewind(angle); } // SkDebugf("%s firstSign=%d\n", __FUNCTION__, firstSign); // we care about first sign and whether wind sum indicates this diff --git a/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp index 09481c385a..f70d2f8916 100644 --- a/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp +++ b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp @@ -87,9 +87,9 @@ static void testPath(const SkPath& path, const SkPoint* pts1, SkPath::Verb c1Typ SimplifyAddIntersectingTsTest::Contour& c1 = contour[0]; SimplifyAddIntersectingTsTest::Contour& c2 = contour[1]; addIntersectTs(&c1, &c2); +#if DEBUG_DUMP bool c1Intersected = c1.segments()[0].intersected(); // bool c2Intersected = c2.fSegments[0].intersected(); -#if DEBUG_DUMP SkDebugf("%s %s (%1.9g,%1.9g %1.9g,%1.9g) %s %s (%1.9g,%1.9g %1.9g,%1.9g)\n", __FUNCTION__, SimplifyAddIntersectingTsTest::kLVerbStr[c1Type], pts1[0].fX, pts1[0].fY, diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index a7c5c31fd7..b730466cea 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -9,6 +9,8 @@ #include "Intersection_Tests.h" #include "ShapeOps.h" +#define TEST(name) { name, #name } + static void testLine1() { SkPath path, simple; path.moveTo(2,0); @@ -404,63 +406,192 @@ static void testLine36() { testSimplifyx(path); } -#define TEST(name) { name, #name } +static void testLine37() { + SkPath path, simple; + path.addRect(0, 20, 20, 20, (SkPath::Direction) 0); + path.addRect(18, 24, 30, 30, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine38() { + SkPath path, simple; + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(6, 12, 18, 18, (SkPath::Direction) 0); + path.addRect(12, 12, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine40() { + SkPath path, simple; + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(12, 18, 24, 24, (SkPath::Direction) 0); + path.addRect(4, 16, 13, 13, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine41() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(18, 24, 30, 30, (SkPath::Direction) 0); + path.addRect(12, 0, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine42() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(8, 16, 17, 17, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine43() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(6, 24, 18, 18, (SkPath::Direction) 0); + path.addRect(0, 32, 9, 36, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void testLine44() { + SkPath path, simple; + path.addRect(10, 40, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 32, 27, 36, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void testLine45() { + SkPath path, simple; + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 32, 33, 36, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine46() { + SkPath path, simple; + path.addRect(10, 40, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 0, 36, 36, (SkPath::Direction) 0); + path.addRect(24, 32, 33, 36, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine47() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void testLine48() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 6, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void testLine49() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine50() { + SkPath path, simple; + path.addRect(10, 30, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 20, 36, 30, (SkPath::Direction) 0); + testSimplifyx(path); +} + + +static void testLine51() { + SkPath path, simple; + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 1); + testSimplifyx(path); +} + +static void (*firstTest)() = testLine51; static struct { void (*fun)(); const char* str; } tests[] = { - TEST(testLine1), - TEST(testLine2), - TEST(testLine3), - TEST(testLine4), - TEST(testLine5), - TEST(testLine6), - TEST(testLine7a), - TEST(testLine7b), - TEST(testLine7), - TEST(testLine8), - TEST(testLine9), - TEST(testLine10), - TEST(testLine10a), - TEST(testLine11), - TEST(testLine12), - TEST(testLine13), - TEST(testLine14), - TEST(testLine15), - TEST(testLine16), - TEST(testLine17), - TEST(testLine18), - TEST(testLine19), - TEST(testLine20), - TEST(testLine21), - TEST(testLine22), - TEST(testLine23), + TEST(testLine51), + TEST(testLine50), + TEST(testLine49), + TEST(testLine48), + TEST(testLine47), + TEST(testLine46), + TEST(testLine45), + TEST(testLine44), + TEST(testLine43), + TEST(testLine42), + TEST(testLine41), + TEST(testLine40), + TEST(testLine38), + TEST(testLine37), + TEST(testLine36), + TEST(testLine35), + TEST(testLine34), + TEST(testLine33), + TEST(testLine32), + TEST(testLine31), + TEST(testLine30), + TEST(testLine29), + TEST(testLine28), + TEST(testLine27), + TEST(testLine26), + TEST(testLine25), TEST(testLine24a), TEST(testLine24), - TEST(testLine25), - TEST(testLine26), - TEST(testLine27), - TEST(testLine28), - TEST(testLine29), - TEST(testLine30), - TEST(testLine31), - TEST(testLine32), - TEST(testLine33), - TEST(testLine34), - TEST(testLine35), - TEST(testLine36), + TEST(testLine23), + TEST(testLine22), + TEST(testLine21), + TEST(testLine20), + TEST(testLine19), + TEST(testLine18), + TEST(testLine17), + TEST(testLine16), + TEST(testLine15), + TEST(testLine14), + TEST(testLine13), + TEST(testLine12), + TEST(testLine11), + TEST(testLine10a), + TEST(testLine10), + TEST(testLine9), + TEST(testLine8), + TEST(testLine7b), + TEST(testLine7a), + TEST(testLine7), + TEST(testLine6), + TEST(testLine5), + TEST(testLine4), + TEST(testLine3), + TEST(testLine2), + TEST(testLine1), }; static const size_t testCount = sizeof(tests) / sizeof(tests[0]); -static void (*firstTest)() = 0; static bool skipAll = false; void SimplifyNew_Test() { if (skipAll) { return; } +#ifdef SK_DEBUG + gDebugMaxWindSum = 3; + gDebugMaxWindValue = 3; +#endif size_t index = 0; if (firstTest) { while (index < testCount && tests[index].fun != firstTest) { @@ -473,4 +604,8 @@ void SimplifyNew_Test() { (*tests[index].fun)(); firstTestComplete = true; } +#ifdef SK_DEBUG + gDebugMaxWindSum = SK_MaxS32; + gDebugMaxWindValue = SK_MaxS32; +#endif } diff --git a/experimental/Intersection/SimplifyRect4x4_Test.cpp b/experimental/Intersection/SimplifyRect4x4_Test.cpp index ef468068ae..0143e1a336 100644 --- a/experimental/Intersection/SimplifyRect4x4_Test.cpp +++ b/experimental/Intersection/SimplifyRect4x4_Test.cpp @@ -19,6 +19,15 @@ // same with x (3 bits, 5 values) // not included, square, tall, wide (2 bits) // cw or ccw (1 bit) +static const char marker[] = + "</div>\n" + "\n" + "<script type=\"text/javascript\">\n" + "\n" + "var testDivs = [\n"; +static const char testLineStr[] = " testLine"; +static const char filename[] = "../../experimental/Intersection/debugXX.txt"; +static int testNumber; static void* testSimplify4x4RectsMain(void* data) { @@ -27,13 +36,13 @@ static void* testSimplify4x4RectsMain(void* data) SkASSERT(data); State4& state = *(State4*) data; int aShape = state.a & 0x03; - int aCW = state.a >> 1; + int aCW = state.a >> 2; int bShape = state.b & 0x03; - int bCW = state.b >> 1; + int bCW = state.b >> 2; int cShape = state.c & 0x03; - int cCW = state.c >> 1; + int cCW = state.c >> 2; int dShape = state.d & 0x03; - int dCW = state.d >> 1; + int dCW = state.d >> 2; for (int aXAlign = 0 ; aXAlign < 5; ++aXAlign) { for (int aYAlign = 0 ; aYAlign < 5; ++aYAlign) { for (int bXAlign = 0 ; bXAlign < 5; ++bXAlign) { @@ -159,54 +168,43 @@ static void* testSimplify4x4RectsMain(void* data) dYAlign = 5; } path.close(); - SkDebugf("%s", pathStr); - if (!testSimplifyx(path, out, state.bitmap, state.canvas)) { - SkDebugf("*/\n{ %s %d, %d, %d, %d, %d, %d, %d, %d," - " %d, %d, %d, %d },\n/*\n", - __FUNCTION__, state.a, state.b, state.c, state.d, - aXAlign, aYAlign, bXAlign, bYAlign, - cXAlign, cYAlign, dXAlign, dYAlign); - SkFILEStream inFile("../../experimental/Intersection/op.htm"); - if (!inFile.isValid()) { - continue; - } - SkTDArray<char> inData; - inData.setCount(inFile.getLength()); - size_t inLen = inData.count(); - inFile.read(inData.begin(), inLen); - inFile.setPath(NULL); - SkFILEWStream outFile("../../experimental/Intersection/xop.htm"); + if (gRunTestsInOneThread) { + SkDebugf("%s\n", pathStr); + } else { + SkFILEWStream outFile(state.filename); if (!outFile.isValid()) { continue; } - const char marker[] = - "</div>\n" - "\n" - "<script type=\"text/javascript\">\n" - "\n" - "var testDivs = [\n"; - const char testLineStr[] = " testLine"; - char* insert = strstr(inData.begin(), marker); - if (!insert) { - continue; - } - size_t startLen = insert - inData.begin(); - insert += sizeof(marker); - const char* numLoc = insert + sizeof(testLineStr); - int testNumber = atoi(numLoc) + 1; - outFile.write(inData.begin(), startLen); outFile.writeText("<div id=\"testLine"); outFile.writeDecAsText(testNumber); outFile.writeText("\">\n"); outFile.writeText(pathStr); outFile.writeText("</div>\n\n"); + outFile.writeText(marker); outFile.writeText(testLineStr); outFile.writeDecAsText(testNumber); - outFile.writeText(",\n"); - outFile.write(insert, inLen - startLen - sizeof(marker)); + outFile.writeText(",\n\n\n"); + + outFile.writeText("static void testLine"); + outFile.writeDecAsText(testNumber); + outFile.writeText("() {\n SkPath path, simple;\n"); + outFile.writeText(pathStr); + outFile.writeText(" testSimplifyx(path);\n}\n"); + outFile.writeText("static void (*firstTest)() = testLine"); + outFile.writeDecAsText(testNumber); + outFile.writeText(";\n\n"); + + outFile.writeText("static struct {\n"); + outFile.writeText(" void (*fun)();\n"); + outFile.writeText(" const char* str;\n"); + outFile.writeText("} tests[] = {\n"); + outFile.writeText(" TEST(testLine"); + outFile.writeDecAsText(testNumber); + outFile.writeText("),\n"); outFile.flush(); - } + } + testSimplifyx(path, out, state.bitmap, state.canvas); } } } @@ -218,12 +216,41 @@ static void* testSimplify4x4RectsMain(void* data) return NULL; } -const int maxThreads = 1; // gRunTestsInOneThread ? 1 : 24; +const int maxThreads = gRunTestsInOneThread ? 1 : 8; void Simplify4x4RectsThreaded_Test() { +#ifdef SK_DEBUG + gDebugMaxWindSum = 3; + gDebugMaxWindValue = 3; +#endif + if (maxThreads > 1) { + SkFILEStream inFile("../../experimental/Intersection/op.htm"); + if (inFile.isValid()) { + SkTDArray<char> inData; + inData.setCount(inFile.getLength()); + size_t inLen = inData.count(); + inFile.read(inData.begin(), inLen); + inFile.setPath(NULL); + char* insert = strstr(inData.begin(), marker); + if (insert) { + insert += sizeof(marker) - 1; + const char* numLoc = insert + sizeof(testLineStr) - 1; + testNumber = atoi(numLoc) + 1; + } + } + } State4 threadState[maxThreads]; - int threadIndex = 0; + int threadIndex; + for (threadIndex = 0; threadIndex < maxThreads; ++threadIndex) { + State4* statePtr = &threadState[threadIndex]; + strcpy(statePtr->filename, filename); + SkASSERT(statePtr->filename[sizeof(filename) - 7] == 'X'); + SkASSERT(statePtr->filename[sizeof(filename) - 6] == 'X'); + statePtr->filename[sizeof(filename) - 7] = '0' + threadIndex / 10; + statePtr->filename[sizeof(filename) - 6] = '0' + threadIndex % 10; + } + threadIndex = 0; for (int a = 0; a < 8; ++a) { // outermost for (int b = a ; b < 8; ++b) { for (int c = b ; c < 8; ++c) { @@ -241,10 +268,18 @@ void Simplify4x4RectsThreaded_Test() } else { testSimplify4x4RectsMain(statePtr); } + if (maxThreads > 1) SkDebugf("."); } + if (maxThreads > 1) SkDebugf("%d", c); } + if (maxThreads > 1) SkDebugf("\n%d", b); } + if (maxThreads > 1) SkDebugf("\n\n%d", a); } waitForCompletion(threadState, threadIndex); +#ifdef SK_DEBUG + gDebugMaxWindSum = SK_MaxS32; + gDebugMaxWindValue = SK_MaxS32; +#endif } diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index a1f390c6cf..d2892b1740 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -345,6 +345,18 @@ path.close(); testSimplifyx(path); </div> +<div id="testLine19"> + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 16, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +</div> + +<div id="testLine24"> + path.addRect(0, 18, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); +</div> + <div id="testLine28"> SkPath path, simple; path.addRect(0, 6, 12, 12, (SkPath::Direction) 0); @@ -401,23 +413,129 @@ path.close(); path.addRect(4, 16, 13, 13, (SkPath::Direction) 0); </div> +<div id="testLine37"> + path.addRect(0, 20, 20, 20, (SkPath::Direction) 0); + path.addRect(18, 24, 30, 30, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 0); +</div> + +<div id="testLine38"> + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(6, 12, 18, 18, (SkPath::Direction) 0); + path.addRect(12, 12, 21, 21, (SkPath::Direction) 0); +</div> + +<div id="testLine39"> + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(12, 6, 24, 24, (SkPath::Direction) 0); + path.addRect(12, 4, 21, 21, (SkPath::Direction) 0); +</div> + +<div id="testLine40"> + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(12, 18, 24, 24, (SkPath::Direction) 0); + path.addRect(4, 16, 13, 13, (SkPath::Direction) 0); +</div> + +<div id="testLine41"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(18, 24, 30, 30, (SkPath::Direction) 0); + path.addRect(12, 0, 21, 21, (SkPath::Direction) 0); +</div> + +<div id="testLine42"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(8, 16, 17, 17, (SkPath::Direction) 0); +</div> + +<div id="testLine43"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(6, 24, 18, 18, (SkPath::Direction) 0); + path.addRect(0, 32, 9, 36, (SkPath::Direction) 1); +</div> + +<div id="testLine44"> + path.addRect(10, 40, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 32, 27, 36, (SkPath::Direction) 1); +</div> + +<div id="testLine45"> + path.addRect(10, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(18, 0, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 32, 33, 36, (SkPath::Direction) 0); +</div> + +<div id="testLine46"> + path.addRect(10, 40, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 0, 36, 36, (SkPath::Direction) 0); + path.addRect(24, 32, 33, 36, (SkPath::Direction) 0); +</div> + +<div id="testLine47"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 1); +</div> + +<div id="testLine48"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 6, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 1); +</div> + +<div id="testLine49"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 0, 9, 9, (SkPath::Direction) 0); +</div> + +<div id="testLine50"> + path.addRect(10, 30, 30, 30, (SkPath::Direction) 0); + path.addRect(24, 20, 36, 30, (SkPath::Direction) 0); +</div> + +<div id="testLine51"> + path.addRect(0, 0, 20, 20, (SkPath::Direction) 0); + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 1); +</div> + </div> <script type="text/javascript"> var testDivs = [ + testLine51, + testLine50, + testLine49, + testLine48, + testLine47, + testLine46, + testLine45, + testLine44, + testLine43, + testLine42, + testLine41, + testLine40, + testLine39, + testLine38, + testLine37, testLine36, testLine35, testLine34, testLine33, - testLine9, - testLine7, testLine30, testLine32, testLine31, testLine29, testLine28, + testLine24, + testLine19, testLine17, + testLine9, + testLine7, testSimplifyQuadratic21, testSimplifyQuadratic20, testSimplifyQuadratic19, |