diff options
Diffstat (limited to 'src/pathops')
34 files changed, 3453 insertions, 1676 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 035a50e4aa..620842bf8c 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -424,8 +424,8 @@ void AddSelfIntersectTs(SkOpContour* test) { SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1); SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1); SkPoint point = ts.pt(0).asSkPoint(); - int testTAt = wt.addSelfT(wt, point, ts[0][0]); - int nextTAt = wt.addT(wt, point, ts[1][0]); + int testTAt = wt.addSelfT(point, ts[0][0]); + int nextTAt = wt.addSelfT(point, ts[1][0]); wt.addOtherT(testTAt, ts[1][0], nextTAt); wt.addOtherT(nextTAt, ts[0][0], testTAt); } while (wt.advance()); diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index bb734e19da..dc1063c34c 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -134,7 +134,10 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC } } } else { - double offset = precisionScale / 16; // FIME: const is arbitrary: test, refine +/*for random cubics, 16 below catches 99.997% of the intersections. To test for the remaining 0.003% + look for nearly coincident curves. and check each 1/16th section. +*/ + double offset = precisionScale / 16; // FIXME: const is arbitrary: test, refine double c1Bottom = tIdx == 0 ? 0 : (t1Start + (t1 - t1Start) * locals[0][tIdx - 1] + to1) / 2; double c1Min = SkTMax(c1Bottom, to1 - offset); diff --git a/src/pathops/SkDCubicToQuads.cpp b/src/pathops/SkDCubicToQuads.cpp index b2a9b6202c..a28564d4c2 100644 --- a/src/pathops/SkDCubicToQuads.cpp +++ b/src/pathops/SkDCubicToQuads.cpp @@ -20,7 +20,6 @@ If this is a degree-elevated cubic, then both equations will give the same answe P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 - SkDCubic defined by: P1/2 - anchor points, C1/C2 control points |x| is the euclidean norm of x mid-point approx of cubic: a quad that shares the same anchors with the cubic and has the diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index f10b440404..f1adce2100 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -76,6 +76,12 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { SkDVector ab0 = a[0] - b[0]; double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX; double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX; +#if 0 + if (!between(0, numerA, denom) || !between(0, numerB, denom)) { + fUsed = 0; + return 0; + } +#endif numerA /= denom; numerB /= denom; int used; @@ -198,7 +204,7 @@ int SkIntersections::horizontal(const SkDLine& line, double y) { int SkIntersections::horizontal(const SkDLine& line, double left, double right, double y, bool flipped) { - fMax = 2; + fMax = 3; // clean up parallel at the end will limit the result to 2 at the most // see if end points intersect the opposite line double t; const SkDPoint leftPt = { left, y }; diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 685a01f70f..14ccac6186 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -4,7 +4,6 @@ // The downside of this approach is that early rejects are difficult to come by. // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step - #include "SkDQuadImplicit.h" #include "SkIntersections.h" #include "SkPathOpsLine.h" @@ -159,10 +158,13 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD int roots = rootTs.intersect(q2, *testLines[index]); for (int idx2 = 0; idx2 < roots; ++idx2) { double t = rootTs[0][idx2]; -#ifdef SK_DEBUG +#if 0 // def SK_DEBUG // FIXME : accurate for error = 16, error of 17.5 seen +// {{{136.08723965397621, 1648.2814535211637}, {593.49031197259478, 1190.8784277439891}, {593.49031197259478, 544.0128173828125}}} +// {{{-968.181396484375, 544.0128173828125}, {592.2825927734375, 870.552490234375}, {593.435302734375, 557.8828125}}} + SkDPoint qPt = q2.ptAtT(t); SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]); - SkASSERT(qPt.approximatelyPEqual(lPt)); + SkASSERT(qPt.approximatelyDEqual(lPt)); #endif if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { continue; @@ -305,10 +307,10 @@ static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 #endif return true; } - if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); - if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); - if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); - if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); + if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep)); + if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep)); + if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep)); + if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep)); double dist[3][3]; // OPTIMIZE: using calcMask value permits skipping some distance calcuations // if prior loop's results are moved to correct slot for reuse @@ -383,7 +385,7 @@ static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, impTs.intersectRay(q1, tmpLine); for (int index = 0; index < impTs.used(); ++index) { SkDPoint realPt = impTs.pt(index); - if (!tmpLine[0].approximatelyEqual(realPt)) { + if (!tmpLine[0].approximatelyPEqual(realPt)) { continue; } if (swap) { diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index bae003c184..45daa10dbd 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -86,7 +86,6 @@ Thus, if the slope of the line tends towards vertical, we use: C = ( (a ) - g'*(d ) - h' ) */ - class LineQuadraticIntersections { public: enum PinTPoint { @@ -311,10 +310,10 @@ protected: } bool pinTs(double* quadT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { - if (!approximately_one_or_less(*lineT)) { + if (!approximately_one_or_less_double(*lineT)) { return false; } - if (!approximately_zero_or_more(*lineT)) { + if (!approximately_zero_or_more_double(*lineT)) { return false; } double qT = *quadT = SkPinT(*quadT); @@ -326,13 +325,17 @@ protected: } SkPoint gridPt = pt->asSkPoint(); if (gridPt == fLine[0].asSkPoint()) { + *pt = fLine[0]; *lineT = 0; } else if (gridPt == fLine[1].asSkPoint()) { + *pt = fLine[1]; *lineT = 1; } if (gridPt == fQuad[0].asSkPoint()) { + *pt = fQuad[0]; *quadT = 0; } else if (gridPt == fQuad[2].asSkPoint()) { + *pt = fQuad[2]; *quadT = 1; } return true; @@ -345,44 +348,6 @@ private: bool fAllowNear; }; -// utility for pairs of coincident quads -static double horizontalIntersect(const SkDQuad& quad, const SkDPoint& pt) { - LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), - static_cast<SkIntersections*>(0)); - double rootVals[2]; - int roots = q.horizontalIntersect(pt.fY, rootVals); - for (int index = 0; index < roots; ++index) { - double t = rootVals[index]; - SkDPoint qPt = quad.ptAtT(t); - if (AlmostEqualUlps(qPt.fX, pt.fX)) { - return t; - } - } - return -1; -} - -static double verticalIntersect(const SkDQuad& quad, const SkDPoint& pt) { - LineQuadraticIntersections q(quad, *(static_cast<SkDLine*>(0)), - static_cast<SkIntersections*>(0)); - double rootVals[2]; - int roots = q.verticalIntersect(pt.fX, rootVals); - for (int index = 0; index < roots; ++index) { - double t = rootVals[index]; - SkDPoint qPt = quad.ptAtT(t); - if (AlmostEqualUlps(qPt.fY, pt.fY)) { - return t; - } - } - return -1; -} - -double SkIntersections::Axial(const SkDQuad& q1, const SkDPoint& p, bool vertical) { - if (vertical) { - return verticalIntersect(q1, p); - } - return horizontalIntersect(q1, p); -} - int SkIntersections::horizontal(const SkDQuad& quad, double left, double right, double y, bool flipped) { SkDLine line = {{{ left, y }, { right, y }}}; diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h index fa1aa697c2..4e8c658ec2 100644 --- a/src/pathops/SkIntersectionHelper.h +++ b/src/pathops/SkIntersectionHelper.h @@ -46,8 +46,8 @@ public: return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT); } - int addSelfT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) { - return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT); + int addSelfT(const SkPoint& pt, double newT) { + return fContour->addSelfT(fIndex, pt, newT); } bool advance() { @@ -141,20 +141,10 @@ public: return y() != pts()[0].fY; } -#ifdef SK_DEBUG - void dump() { - SkDPoint::dump(pts()[0]); - SkDPoint::dump(pts()[1]); - if (verb() >= SkPath::kQuad_Verb) { - SkDPoint::dump(pts()[2]); - } - if (verb() >= SkPath::kCubic_Verb) { - SkDPoint::dump(pts()[3]); - } - } -#endif - private: + // utility callable by the user from the debugger when the implementation code is linked in + void dump() const; + SkOpContour* fContour; int fIndex; int fLast; diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index 53cd6feb43..c8b4b838e4 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -152,20 +152,6 @@ void SkIntersections::quickRemoveOne(int index, int replace) { } } -#if 0 -void SkIntersections::remove(double one, double two, const SkDPoint& startPt, - const SkDPoint& endPt) { - for (int index = fUsed - 1; index >= 0; --index) { - if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two) - || startPt.approximatelyEqual(fPt[index]) - || endPt.approximatelyEqual(fPt[index]))) { - SkASSERT(fUsed > 0); - removeOne(index); - } - } -} -#endif - void SkIntersections::removeOne(int index) { int remaining = --fUsed - index; if (remaining <= 0) { diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 0e3fcd1173..119ca781c1 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -210,7 +210,6 @@ public: } void append(const SkIntersections& ); - static double Axial(const SkDQuad& , const SkDPoint& , bool vertical); void cleanUpCoincidence(); int coincidentUsed() const; int cubicRay(const SkPoint pts[4], const SkDLine& line); @@ -266,8 +265,6 @@ private: void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& ); void cleanUpParallelLines(bool parallel); void computePoints(const SkDLine& line, int used); - // used by addCoincident to remove ordinary intersections in range - // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt); SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also double fT[2][9]; diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h index 04074854a8..92343c691b 100644 --- a/src/pathops/SkLineParameters.h +++ b/src/pathops/SkLineParameters.h @@ -24,48 +24,50 @@ class SkLineParameters { public: - void cubicEndPoints(const SkDCubic& pts) { + bool cubicEndPoints(const SkDCubic& pts) { int endIndex = 1; cubicEndPoints(pts, 0, endIndex); if (dy() != 0) { - return; + return true; } if (dx() == 0) { cubicEndPoints(pts, 0, ++endIndex); SkASSERT(endIndex == 2); if (dy() != 0) { - return; + return true; } if (dx() == 0) { cubicEndPoints(pts, 0, ++endIndex); // line SkASSERT(endIndex == 3); - return; + return false; } } + // FIXME: after switching to round sort, remove bumping fA if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie - return; + return true; } // if cubic tangent is on x axis, look at next control point to break tie // control point may be approximate, so it must move significantly to account for error if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) { if (pts[0].fY > pts[endIndex].fY) { - a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) + fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) } - return; + return true; } if (endIndex == 3) { - return; + return true; } SkASSERT(endIndex == 2); if (pts[0].fY > pts[3].fY) { - a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) + fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) } + return true; } void cubicEndPoints(const SkDCubic& pts, int s, int e) { - a = pts[s].fY - pts[e].fY; - b = pts[e].fX - pts[s].fX; - c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; + fA = pts[s].fY - pts[e].fY; + fB = pts[e].fX - pts[s].fX; + fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } double cubicPart(const SkDCubic& part) { @@ -77,32 +79,34 @@ public: } void lineEndPoints(const SkDLine& pts) { - a = pts[0].fY - pts[1].fY; - b = pts[1].fX - pts[0].fX; - c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; + fA = pts[0].fY - pts[1].fY; + fB = pts[1].fX - pts[0].fX; + fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; } - void quadEndPoints(const SkDQuad& pts) { + bool quadEndPoints(const SkDQuad& pts) { quadEndPoints(pts, 0, 1); if (dy() != 0) { - return; + return true; } if (dx() == 0) { quadEndPoints(pts, 0, 2); - return; + return false; } if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie - return; + return true; } + // FIXME: after switching to round sort, remove this if (pts[0].fY > pts[2].fY) { - a = DBL_EPSILON; + fA = DBL_EPSILON; } + return true; } void quadEndPoints(const SkDQuad& pts, int s, int e) { - a = pts[s].fY - pts[e].fY; - b = pts[e].fX - pts[s].fX; - c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; + fA = pts[s].fY - pts[e].fY; + fB = pts[e].fX - pts[s].fX; + fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } double quadPart(const SkDQuad& part) { @@ -111,19 +115,19 @@ public: } double normalSquared() const { - return a * a + b * b; + return fA * fA + fB * fB; } bool normalize() { double normal = sqrt(normalSquared()); if (approximately_zero(normal)) { - a = b = c = 0; + fA = fB = fC = 0; return false; } double reciprocal = 1 / normal; - a *= reciprocal; - b *= reciprocal; - c *= reciprocal; + fA *= reciprocal; + fB *= reciprocal; + fC *= reciprocal; return true; } @@ -131,7 +135,7 @@ public: double oneThird = 1 / 3.0; for (int index = 0; index < 4; ++index) { distance[index].fX = index * oneThird; - distance[index].fY = a * pts[index].fX + b * pts[index].fY + c; + distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; } } @@ -139,33 +143,33 @@ public: double oneHalf = 1 / 2.0; for (int index = 0; index < 3; ++index) { distance[index].fX = index * oneHalf; - distance[index].fY = a * pts[index].fX + b * pts[index].fY + c; + distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; } } double controlPtDistance(const SkDCubic& pts, int index) const { SkASSERT(index == 1 || index == 2); - return a * pts[index].fX + b * pts[index].fY + c; + return fA * pts[index].fX + fB * pts[index].fY + fC; } double controlPtDistance(const SkDQuad& pts) const { - return a * pts[1].fX + b * pts[1].fY + c; + return fA * pts[1].fX + fB * pts[1].fY + fC; } double pointDistance(const SkDPoint& pt) const { - return a * pt.fX + b * pt.fY + c; + return fA * pt.fX + fB * pt.fY + fC; } double dx() const { - return b; + return fB; } double dy() const { - return -a; + return -fA; } private: - double a; - double b; - double c; + double fA; + double fB; + double fC; }; diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 742a161f6c..364ab1bf1f 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -12,19 +12,14 @@ #if DEBUG_ANGLE #include "SkString.h" - -static const char funcName[] = "SkOpSegment::operator<"; -static const int bugChar = strlen(funcName) + 1; #endif /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest positive y. The largest angle has a positive x and a zero y. */ #if DEBUG_ANGLE - static bool CompareResult(SkString* bugOut, const char* append, bool compare) { - bugOut->appendf("%s", append); - bugOut->writable_str()[bugChar] = "><"[compare]; - SkDebugf("%s\n", bugOut->c_str()); + static bool CompareResult(SkString* bugOut, int append, bool compare) { + SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append); return compare; } @@ -33,7 +28,197 @@ static const int bugChar = strlen(funcName) + 1; #define COMPARE_RESULT(append, compare) compare #endif -bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ +/* quarter angle values for sector + +31 x > 0, y == 0 horizontal line (to the right) +0 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y +1 x > 0, y > 0, x > y nearer horizontal angle +2 x + e == y quad/cubic 45 going horiz +3 x > 0, y > 0, x == y 45 angle +4 x == y + e quad/cubic 45 going vert +5 x > 0, y > 0, x < y nearer vertical angle +6 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x +7 x == 0, y > 0 vertical line (to the top) + + 8 7 6 + 9 | 5 + 10 | 4 + 11 | 3 + 12 \ | / 2 + 13 | 1 + 14 | 0 + 15 --------------+------------- 31 + 16 | 30 + 17 | 29 + 18 / | \ 28 + 19 | 27 + 20 | 26 + 21 | 25 + 22 23 24 +*/ + +// return true if lh < this < rh +bool SkOpAngle::after(const SkOpAngle* test) const { + const SkOpAngle& lh = *test; + const SkOpAngle& rh = *lh.fNext; + SkASSERT(&lh != &rh); +#if DEBUG_ANGLE + SkString bugOut; + bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" + " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" + " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, + lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, + lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), + fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), + fSegment->t(fEnd), + rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, + rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); +#endif + if (lh.fComputeSector && !const_cast<SkOpAngle&>(lh).computeSector()) { + return COMPARE_RESULT(1, true); + } + if (fComputeSector && !const_cast<SkOpAngle*>(this)->computeSector()) { + return COMPARE_RESULT(2, true); + } + if (rh.fComputeSector && !const_cast<SkOpAngle&>(rh).computeSector()) { + return COMPARE_RESULT(3, true); + } +#if DEBUG_ANGLE // reset bugOut with computed sectors + bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" + " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" + " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, + lh.fSegment->debugID(), lh.debugID(), lh.fSectorStart, lh.fSectorEnd, + lh.fSegment->t(lh.fStart), lh.fSegment->t(lh.fEnd), + fSegment->debugID(), debugID(), fSectorStart, fSectorEnd, fSegment->t(fStart), + fSegment->t(fEnd), + rh.fSegment->debugID(), rh.debugID(), rh.fSectorStart, rh.fSectorEnd, + rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); +#endif + bool ltrOverlap = (lh.fSectorMask | rh.fSectorMask) & fSectorMask; + bool lrOverlap = lh.fSectorMask & rh.fSectorMask; + int lrOrder; // set to -1 if either order works + if (!lrOverlap) { // no lh/rh sector overlap + if (!ltrOverlap) { // no lh/this/rh sector overlap + return COMPARE_RESULT(4, (lh.fSectorEnd > rh.fSectorStart) + ^ (fSectorStart > lh.fSectorEnd) ^ (fSectorStart > rh.fSectorStart)); + } + int lrGap = (rh.fSectorStart - lh.fSectorStart + 32) & 0x1f; + /* A tiny change can move the start +/- 4. The order can only be determined if + lr gap is not 12 to 20 or -12 to -20. + -31 ..-21 1 + -20 ..-12 -1 + -11 .. -1 0 + 0 shouldn't get here + 11 .. 1 1 + 12 .. 20 -1 + 21 .. 31 0 + */ + lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1; + } else { + lrOrder = (int) lh.orderable(rh); + if (!ltrOverlap) { + return COMPARE_RESULT(5, !lrOrder); + } + } + int ltOrder; + SkASSERT((lh.fSectorMask & fSectorMask) || (rh.fSectorMask & fSectorMask)); + if (lh.fSectorMask & fSectorMask) { + ltOrder = (int) lh.orderable(*this); + } else { + int ltGap = (fSectorStart - lh.fSectorStart + 32) & 0x1f; + ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1; + } + int trOrder; + if (rh.fSectorMask & fSectorMask) { + trOrder = (int) orderable(rh); + } else { + int trGap = (rh.fSectorStart - fSectorStart + 32) & 0x1f; + trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1; + } + if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) { + return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder)); + } + SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0); +// There's not enough information to sort. Get the pairs of angles in opposite planes. +// If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs. + // FIXME : once all variants are understood, rewrite this more simply + if (ltOrder == 0 && lrOrder == 0) { + SkASSERT(trOrder < 0); + // FIXME : once this is verified to work, remove one opposite angle call + SkDEBUGCODE(bool lrOpposite = lh.oppositePlanes(rh)); + bool ltOpposite = lh.oppositePlanes(*this); + SkASSERT(lrOpposite != ltOpposite); + return COMPARE_RESULT(8, ltOpposite); + } else if (ltOrder == 1 && trOrder == 0) { + SkASSERT(lrOrder < 0); + SkDEBUGCODE(bool ltOpposite = lh.oppositePlanes(*this)); + bool trOpposite = oppositePlanes(rh); + SkASSERT(ltOpposite != trOpposite); + return COMPARE_RESULT(9, trOpposite); + } else if (lrOrder == 1 && trOrder == 1) { + SkASSERT(ltOrder < 0); + SkDEBUGCODE(bool trOpposite = oppositePlanes(rh)); + bool lrOpposite = lh.oppositePlanes(rh); + SkASSERT(lrOpposite != trOpposite); + return COMPARE_RESULT(10, lrOpposite); + } + if (lrOrder < 0) { + if (ltOrder < 0) { + return COMPARE_RESULT(11, trOrder); + } + return COMPARE_RESULT(12, ltOrder); + } + return COMPARE_RESULT(13, !lrOrder); +} + +// given a line, see if the opposite curve's convex hull is all on one side +// returns -1=not on one side 0=this CW of test 1=this CCW of test +int SkOpAngle::allOnOneSide(const SkOpAngle& test) const { + SkASSERT(!fIsCurve); + SkASSERT(test.fIsCurve); + const SkDPoint& origin = test.fCurvePart[0]; + SkVector line; + if (fSegment->verb() == SkPath::kLine_Verb) { + const SkPoint* linePts = fSegment->pts(); + int lineStart = fStart < fEnd ? 0 : 1; + line = linePts[lineStart ^ 1] - linePts[lineStart]; + } else { + SkPoint shortPts[2] = { fCurvePart[0].asSkPoint(), fCurvePart[1].asSkPoint() }; + line = shortPts[1] - shortPts[0]; + } + float crosses[3]; + SkPath::Verb testVerb = test.fSegment->verb(); + int iMax = SkPathOpsVerbToPoints(testVerb); +// SkASSERT(origin == test.fCurveHalf[0]); + const SkDCubic& testCurve = test.fCurvePart; +// do { + for (int index = 1; index <= iMax; ++index) { + float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY)); + float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX)); + crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2; + } + if (crosses[0] * crosses[1] < 0) { + return -1; + } + if (SkPath::kCubic_Verb == testVerb) { + if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { + return -1; + } + } + if (crosses[0]) { + return crosses[0] < 0; + } + if (crosses[1]) { + return crosses[1] < 0; + } + if (SkPath::kCubic_Verb == testVerb && crosses[2]) { + return crosses[2] < 0; + } + fUnorderable = true; + return -1; +} + +bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const { double absX = fabs(x); double absY = fabs(y); double length = absX < absY ? absX / 2 + absY : absX + absY / 2; @@ -59,280 +244,733 @@ bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) return *result == less2; } -/* -for quads and cubics, set up a parameterized line (e.g. LineParameters ) -for points [0] to [1]. See if point [2] is on that line, or on one side -or the other. If it both quads' end points are on the same side, choose -the shorter tangent. If the tangents are equal, choose the better second -tangent angle +bool SkOpAngle::checkCrossesZero() const { + int start = SkTMin(fSectorStart, fSectorEnd); + int end = SkTMax(fSectorStart, fSectorEnd); + bool crossesZero = end - start > 16; + return crossesZero; +} -FIXME: maybe I could set up LineParameters lazily -*/ -bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand - double y = dy(); - double ry = rh.dy(); -#if DEBUG_ANGLE - SkString bugOut; - bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" - " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, - fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), - rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); -#endif - double y_ry = y * ry; - if (y_ry < 0) { // if y's are opposite signs, we can do a quick return - return COMPARE_RESULT("1 y * ry < 0", y < 0); - } - // at this point, both y's must be the same sign, or one (or both) is zero - double x = dx(); - double rx = rh.dx(); - if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half - if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive - return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); - } - if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative - return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); - } - SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller - return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); - } - // at this point, both x's must be the same sign, or one (or both) is zero - if (y_ry == 0) { // if either y is zero - if (y + ry < 0) { // if the other y is less than zero, it must be smaller - return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); - } - if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller - return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); - } - // at this point, both y's are zero, so lines are coincident or one is degenerate - SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far - } - // see if either curve can be lengthened before trying the tangent - if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical - && rh.fSegment->other(rh.fEnd) != fSegment - && y != -DBL_EPSILON - && ry != -DBL_EPSILON) { // and not intersecting - SkOpAngle longer = *this; - SkOpAngle rhLonger = rh; - if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both - && (fUnorderable || !longer.fUnorderable) - && (rh.fUnorderable || !rhLonger.fUnorderable)) { -#if DEBUG_ANGLE - bugOut.prepend(" "); -#endif - return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); +bool SkOpAngle::checkParallel(const SkOpAngle& rh) const { + SkDVector scratch[2]; + const SkDVector* sweep, * tweep; + if (!fUnorderedSweep) { + sweep = fSweep; + } else { + scratch[0] = fCurvePart[1] - fCurvePart[0]; + sweep = &scratch[0]; + } + if (!rh.fUnorderedSweep) { + tweep = rh.fSweep; + } else { + scratch[1] = rh.fCurvePart[1] - rh.fCurvePart[0]; + tweep = &scratch[1]; + } + double s0xt0 = sweep->crossCheck(*tweep); + if (tangentsDiverge(rh, s0xt0)) { + return s0xt0 < 0; + } + SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; + SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; + double m0xm1 = m0.crossCheck(m1); + if (m0xm1 == 0) { + fUnorderable = true; + rh.fUnorderable = true; + return true; + } + return m0xm1 < 0; +} + +// the original angle is too short to get meaningful sector information +// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it +// would cause it to intersect one of the adjacent angles +bool SkOpAngle::computeSector() { + if (fComputedSector) { + // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51 + // -- but in general, this code may not work so this may be the least of problems + // adding the bang fixes testQuads46x in release, however + return fUnorderable; + } + SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small()); + fComputedSector = true; + int step = fStart < fEnd ? 1 : -1; + int limit = step > 0 ? fSegment->count() : -1; + int checkEnd = fEnd; + do { +// advance end + const SkOpSpan& span = fSegment->span(checkEnd); + const SkOpSegment* other = span.fOther; + int oCount = other->count(); + for (int oIndex = 0; oIndex < oCount; ++oIndex) { + const SkOpSpan& oSpan = other->span(oIndex); + if (oSpan.fOther != fSegment) { + continue; + } + if (oSpan.fOtherIndex == checkEnd) { + continue; + } + if (!approximately_equal(oSpan.fOtherT, span.fT)) { + continue; + } + goto recomputeSector; } + checkEnd += step; + } while (checkEnd != limit); +recomputeSector: + if (checkEnd == fEnd || checkEnd - step == fEnd) { + fUnorderable = true; + return false; } - SkPath::Verb verb = fSegment->verb(); - SkPath::Verb rVerb = rh.fSegment->verb(); - if (y_ry != 0) { // if they aren't coincident, look for a stable cross product - // at this point, y's are the same sign, neither is zero - // and x's are the same sign, or one (or both) is zero - double x_ry = x * ry; - double rx_y = rx * y; - if (!fComputed && !rh.fComputed) { - if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) { - return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); + fEnd = checkEnd - step; + setSpans(); + setSector(); + return !fUnorderable; +} + +// returns -1 if overlaps 0 if no overlap cw 1 if no overlap ccw +int SkOpAngle::convexHullOverlaps(const SkOpAngle& rh) const { + const SkDVector* sweep = fSweep; + const SkDVector* tweep = rh.fSweep; + double s0xs1 = sweep[0].crossCheck(sweep[1]); + double s0xt0 = sweep[0].crossCheck(tweep[0]); + double s1xt0 = sweep[1].crossCheck(tweep[0]); + bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; + double s0xt1 = sweep[0].crossCheck(tweep[1]); + double s1xt1 = sweep[1].crossCheck(tweep[1]); + tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; + double t0xt1 = tweep[0].crossCheck(tweep[1]); + if (tBetweenS) { + return -1; + } + if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 + return -1; + } + bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; + sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; + if (sBetweenT) { + return -1; + } + // if all of the sweeps are in the same half plane, then the order of any pair is enough + if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { + return 0; + } + if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { + return 1; + } + // if the outside sweeps are greater than 180 degress: + // first assume the inital tangents are the ordering + // if the midpoint direction matches the inital order, that is enough + SkDVector m0 = fSegment->dPtAtT(midT()) - fCurvePart[0]; + SkDVector m1 = rh.fSegment->dPtAtT(rh.midT()) - rh.fCurvePart[0]; + double m0xm1 = m0.crossCheck(m1); + if (s0xt0 > 0 && m0xm1 > 0) { + return 0; + } + if (s0xt0 < 0 && m0xm1 < 0) { + return 1; + } + if (tangentsDiverge(rh, s0xt0)) { + return s0xt0 < 0; + } + return m0xm1 < 0; +} + +// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup +double SkOpAngle::distEndRatio(double dist) const { + double longest = 0; + const SkOpSegment& segment = *this->segment(); + int ptCount = SkPathOpsVerbToPoints(segment.verb()); + const SkPoint* pts = segment.pts(); + for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) { + for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) { + if (idx1 == idx2) { + continue; } - if (fSide2 == 0 && rh.fSide2 == 0) { - return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y); + SkDVector v; + v.set(pts[idx2] - pts[idx1]); + double lenSq = v.lengthSquared(); + longest = SkTMax(longest, lenSq); + } + } + return sqrt(longest) / dist; +} + +bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const { + SkPath::Verb lVerb = fSegment->verb(); + SkPath::Verb rVerb = rh.fSegment->verb(); + int lPts = SkPathOpsVerbToPoints(lVerb); + int rPts = SkPathOpsVerbToPoints(rVerb); + SkDLine rays[] = {{{fCurvePart[0], rh.fCurvePart[rPts]}}, + {{fCurvePart[0], fCurvePart[lPts]}}}; + if (rays[0][1] == rays[1][1]) { + return checkParallel(rh); + } + double smallTs[2] = {-1, -1}; + bool limited[2] = {false, false}; + for (int index = 0; index < 2; ++index) { + const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; + SkIntersections i; + (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i); +// SkASSERT(i.used() >= 1); + if (i.used() <= 1) { + continue; + } + double tStart = segment.t(index ? rh.fStart : fStart); + double tEnd = segment.t(index ? rh.fEnd : fEnd); + bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd; + double t = testAscends ? 0 : 1; + for (int idx2 = 0; idx2 < i.used(); ++idx2) { + double testT = i[0][idx2]; + if (!approximately_between_orderable(tStart, testT, tEnd)) { + continue; } - } else { - // if the vector was a result of subdividing a curve, see if it is stable - bool sloppy1 = x_ry < rx_y; - bool sloppy2 = !sloppy1; - if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) - && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) - && sloppy1 != sloppy2) { - return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); + if (approximately_equal_orderable(tStart, testT)) { + continue; } + smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT); + limited[index] = approximately_equal_orderable(t, tEnd); } } - if (fSide2 * rh.fSide2 == 0) { // one is zero -#if DEBUG_ANGLE - if (fSide2 == rh.fSide2 && y_ry) { // both is zero; coincidence was undetected - SkDebugf("%s coincidence!\n", __FUNCTION__); +#if 0 + if (smallTs[0] < 0 && smallTs[1] < 0) { // if neither ray intersects, do endpoint sort + double m0xm1 = 0; + if (lVerb == SkPath::kLine_Verb) { + SkASSERT(rVerb != SkPath::kLine_Verb); + SkDVector m0 = rays[1][1] - fCurvePart[0]; + SkDPoint endPt; + endPt.set(rh.fSegment->pts()[rh.fStart < rh.fEnd ? rPts : 0]); + SkDVector m1 = endPt - fCurvePart[0]; + m0xm1 = m0.crossCheck(m1); } + if (rVerb == SkPath::kLine_Verb) { + SkDPoint endPt; + endPt.set(fSegment->pts()[fStart < fEnd ? lPts : 0]); + SkDVector m0 = endPt - fCurvePart[0]; + SkDVector m1 = rays[0][1] - fCurvePart[0]; + m0xm1 = m0.crossCheck(m1); + } + if (m0xm1 != 0) { + return m0xm1 < 0; + } + } #endif - return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2); - } - // at this point, the initial tangent line is nearly coincident - // see if edges curl away from each other - if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { - return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); - } - if (fUnsortable || rh.fUnsortable) { - // even with no solution, return a stable sort - return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); - } - if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) - || (rVerb == SkPath::kLine_Verb - && approximately_zero(ry) && approximately_zero(rx))) { - // See general unsortable comment below. This case can happen when - // one line has a non-zero change in t but no change in x and y. - fUnsortable = true; - return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); - } - if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { - fUnsortable = true; - return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); - } - SkASSERT(verb >= SkPath::kQuad_Verb); - SkASSERT(rVerb >= SkPath::kQuad_Verb); - // FIXME: until I can think of something better, project a ray from the - // end of the shorter tangent to midway between the end points - // through both curves and use the resulting angle to sort - // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive - double len = fTangentPart.normalSquared(); - double rlen = rh.fTangentPart.normalSquared(); - SkDLine ray; - SkIntersections i, ri; - int roots, rroots; - bool flip = false; - bool useThis; - bool leftLessThanRight = fSide > 0; - do { - useThis = (len < rlen) ^ flip; - const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; - SkPath::Verb partVerb = useThis ? verb : rVerb; - ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? - part[2] : part[1]; - ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); - SkASSERT(ray[0] != ray[1]); - roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); - rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); - } while ((roots == 0 || rroots == 0) && (flip ^= true)); - if (roots == 0 || rroots == 0) { - // FIXME: we don't have a solution in this case. The interim solution - // is to mark the edges as unsortable, exclude them from this and - // future computations, and allow the returned path to be fragmented - fUnsortable = true; - return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); - } - SkASSERT(fSide != 0 && rh.fSide != 0); - if (fSide * rh.fSide < 0) { - fUnsortable = true; - return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh); - } - SkDPoint lLoc; - double best = SK_ScalarInfinity; -#if DEBUG_SORT - SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n", - fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY, - ray[1].fX, ray[1].fY, "-+"[fSide > 0]); -#endif - for (int index = 0; index < roots; ++index) { - SkDPoint loc = i.pt(index); - SkDVector dxy = loc - ray[0]; - double dist = dxy.lengthSquared(); -#if DEBUG_SORT - SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", - best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY); -#endif - if (best > dist) { - lLoc = loc; - best = dist; - } - } - flip = false; - SkDPoint rLoc; - for (int index = 0; index < rroots; ++index) { - rLoc = ri.pt(index); - SkDVector dxy = rLoc - ray[0]; - double dist = dxy.lengthSquared(); -#if DEBUG_SORT - SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", - best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY); -#endif - if (best > dist) { - flip = true; + bool sRayLonger = false; + SkDVector sCept = {0, 0}; + double sCeptT = -1; + int sIndex = -1; + bool useIntersect = false; + for (int index = 0; index < 2; ++index) { + if (smallTs[index] < 0) { + continue; + } + const SkOpSegment& segment = index ? *rh.fSegment : *fSegment; + const SkDPoint& dPt = segment.dPtAtT(smallTs[index]); + SkDVector cept = dPt - rays[index][0]; + // If this point is on the curve, it should have been detected earlier by ordinary + // curve intersection. This may be hard to determine in general, but for lines, + // the point could be close to or equal to its end, but shouldn't be near the start. + if ((index ? lPts : rPts) == 1) { + SkDVector total = rays[index][1] - rays[index][0]; + if (cept.lengthSquared() * 2 < total.lengthSquared()) { + continue; + } + } + SkDVector end = rays[index][1] - rays[index][0]; + if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) { + continue; + } + double rayDist = cept.length(); + double endDist = end.length(); + bool rayLonger = rayDist > endDist; + if (limited[0] && limited[1] && rayLonger) { + useIntersect = true; + sRayLonger = rayLonger; + sCept = cept; + sCeptT = smallTs[index]; + sIndex = index; + break; + } + double delta = fabs(rayDist - endDist); + double minX, minY, maxX, maxY; + minX = minY = SK_ScalarInfinity; + maxX = maxY = -SK_ScalarInfinity; + const SkDCubic& curve = index ? rh.fCurvePart : fCurvePart; + int ptCount = index ? rPts : lPts; + for (int idx2 = 0; idx2 <= ptCount; ++idx2) { + minX = SkTMin(minX, curve[idx2].fX); + minY = SkTMin(minY, curve[idx2].fY); + maxX = SkTMax(maxX, curve[idx2].fX); + maxY = SkTMax(maxY, curve[idx2].fY); + } + double maxWidth = SkTMax(maxX - minX, maxY - minY); + delta /= maxWidth; + if (delta > 1e-4 && (useIntersect ^= true)) { // FIXME: move this magic number + sRayLonger = rayLonger; + sCept = cept; + sCeptT = smallTs[index]; + sIndex = index; + } + } + if (useIntersect) { + const SkDCubic& curve = sIndex ? rh.fCurvePart : fCurvePart; + const SkOpSegment& segment = sIndex ? *rh.fSegment : *fSegment; + double tStart = segment.t(sIndex ? rh.fStart : fStart); + SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0]; + double septDir = mid.crossCheck(sCept); + if (!septDir) { + return checkParallel(rh); + } + return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); + } else { + return checkParallel(rh); + } +} + +// Most of the time, the first one can be found trivially by detecting the smallest sector value. +// If all angles have the same sector value, actual sorting is required. +const SkOpAngle* SkOpAngle::findFirst() const { + const SkOpAngle* best = this; + int bestStart = SkTMin(fSectorStart, fSectorEnd); + const SkOpAngle* angle = this; + while ((angle = angle->fNext) != this) { + int angleEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); + if (angleEnd < bestStart) { + return angle; // we wrapped around + } + int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); + if (bestStart > angleStart) { + best = angle; + bestStart = angleStart; + } + } + // back up to the first possible angle + const SkOpAngle* firstBest = best; + angle = best; + int bestEnd = SkTMax(best->fSectorStart, best->fSectorEnd); + while ((angle = angle->previous()) != firstBest) { + if (angle->fStop) { break; } + int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); + // angles that are smaller by one aren't necessary better, since the larger may be a line + // and the smaller may be a curve that curls to the other side of the line. + if (bestEnd + 1 < angleStart) { + return best; + } + best = angle; + bestEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); + } + // in the case where all angles are nearly in the same sector, check the order to find the best + firstBest = best; + angle = best; + do { + angle = angle->fNext; + if (angle->fStop) { + return firstBest; + } + bool orderable = best->orderable(*angle); // note: may return an unorderable angle + if (orderable == 0) { + return angle; + } + best = angle; + } while (angle != firstBest); + // if the angles are equally ordered, fall back on the initial tangent + bool foundBelow = false; + while ((angle = angle->fNext)) { + SkDVector scratch[2]; + const SkDVector* sweep; + if (!angle->fUnorderedSweep) { + sweep = angle->fSweep; + } else { + scratch[0] = angle->fCurvePart[1] - angle->fCurvePart[0]; + sweep = &scratch[0]; + } + bool isAbove = sweep->fY <= 0; + if (isAbove && foundBelow) { + return angle; + } + foundBelow |= !isAbove; + if (angle == firstBest) { + return NULL; // should not loop around + } + } + SkASSERT(0); // should never get here + return NULL; +} + +/* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0 + 0 x x x + 1 x x x + 2 x x x + 3 x x x + 4 x x x + 5 x x x + 6 x x x + 7 x x x + 8 x x x + 9 x x x + 10 x x x + 11 x x x + 12 x x x + 13 x x x + 14 x x x + 15 x x x +*/ +int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { + double absX = fabs(x); + double absY = fabs(y); + double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0; + // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim, + // one could coin the term sedecimant for a space divided into 16 sections. + // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts + static const int sedecimant[3][3][3] = { + // y<0 y==0 y>0 + // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0 + {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y) + {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y) + {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y) + }; + int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1; + SkASSERT(SkPath::kLine_Verb == verb || sector >= 0); + return sector; +} + +// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side +// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side +void SkOpAngle::insert(SkOpAngle* angle) { + if (angle->fNext) { + if (loopCount() >= angle->loopCount()) { + if (!merge(angle)) { + return; + } + } else if (fNext) { + if (!angle->merge(this)) { + return; + } + } else { + angle->insert(this); + } + return; } - if (flip) { - leftLessThanRight = !leftLessThanRight; + bool singleton = NULL == fNext; + if (singleton) { + fNext = this; } - return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight); + SkOpAngle* next = fNext; + if (next->fNext == this) { + if (singleton || angle->after(this)) { + this->fNext = angle; + angle->fNext = next; + } else { + next->fNext = angle; + angle->fNext = this; + } + debugValidateNext(); + return; + } + SkOpAngle* last = this; + do { + SkASSERT(last->fNext == next); + if (angle->after(last)) { + last->fNext = angle; + angle->fNext = next; + debugValidateNext(); + return; + } + last = next; + next = next->fNext; + if (last == this && next->fUnorderable) { + fUnorderable = true; + return; + } + SkASSERT(last != this); + } while (true); } bool SkOpAngle::isHorizontal() const { - return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; + return !fIsCurve && fSweep[0].fY == 0; } -// lengthen cannot cross opposite angle -bool SkOpAngle::lengthen(const SkOpAngle& opp) { - if (fSegment->other(fEnd) == opp.fSegment) { - return false; +SkOpSpan* SkOpAngle::lastMarked() const { + if (fLastMarked) { + if (fLastMarked->fChased) { + return NULL; + } + fLastMarked->fChased = true; } - // FIXME: make this a while loop instead and make it as large as possible? - int newEnd = fEnd; - if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { - fEnd = newEnd; - setSpans(); - return true; + return fLastMarked; +} + +int SkOpAngle::loopCount() const { + int count = 0; + const SkOpAngle* first = this; + const SkOpAngle* next = this; + do { + next = next->fNext; + ++count; + } while (next && next != first); + return count; +} + +// OPTIMIZATION: can this be done better in after when angles are sorted? +void SkOpAngle::markStops() { + SkOpAngle* angle = this; + int lastEnd = SkTMax(fSectorStart, fSectorEnd); + do { + angle = angle->fNext; + int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd); + // angles that are smaller by one aren't necessary better, since the larger may be a line + // and the smaller may be a curve that curls to the other side of the line. + if (lastEnd + 1 < angleStart) { + angle->fStop = true; + } + lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd); + } while (angle != this); +} + +bool SkOpAngle::merge(SkOpAngle* angle) { + SkASSERT(fNext); + SkASSERT(angle->fNext); + SkOpAngle* working = angle; + do { + if (this == working) { + return false; + } + working = working->fNext; + } while (working != angle); + do { + SkOpAngle* next = working->fNext; + working->fNext = NULL; + insert(working); + working = next; + } while (working != angle); + // it's likely that a pair of the angles are unorderable +#if DEBUG_ANGLE + SkOpAngle* last = angle; + working = angle->fNext; + do { + SkASSERT(last->fNext == working); + last->fNext = working->fNext; + SkASSERT(working->after(last)); + last->fNext = working; + last = working; + working = working->fNext; + } while (last != angle); +#endif + debugValidateNext(); + return true; +} + +double SkOpAngle::midT() const { + return (fSegment->t(fStart) + fSegment->t(fEnd)) / 2; +} + +bool SkOpAngle::oppositePlanes(const SkOpAngle& rh) const { + int startSpan = abs(rh.fSectorStart - fSectorStart); + return startSpan >= 8; +} + +bool SkOpAngle::orderable(const SkOpAngle& rh) const { + int result; + if (!fIsCurve) { + if (!rh.fIsCurve) { + double leftX = fTangentHalf.dx(); + double leftY = fTangentHalf.dy(); + double rightX = rh.fTangentHalf.dx(); + double rightY = rh.fTangentHalf.dy(); + double x_ry = leftX * rightY; + double rx_y = rightX * leftY; + if (x_ry == rx_y) { + if (leftX * rightX < 0 || leftY * rightY < 0) { + return true; // exactly 180 degrees apart + } + goto unorderable; + } + SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier + return x_ry < rx_y; + } + if ((result = allOnOneSide(rh)) >= 0) { + return result; + } + if (fUnorderable || approximately_zero(rh.fSide)) { + goto unorderable; + } + } else if (!rh.fIsCurve) { + if ((result = rh.allOnOneSide(*this)) >= 0) { + return !result; + } + if (rh.fUnorderable || approximately_zero(fSide)) { + goto unorderable; + } } - return false; + if ((result = convexHullOverlaps(rh)) >= 0) { + return result; + } + return endsIntersect(rh); +unorderable: + fUnorderable = true; + rh.fUnorderable = true; + return true; +} + +// OPTIMIZE: if this shows up in a profile, add a previous pointer +// as is, this should be rarely called +SkOpAngle* SkOpAngle::previous() const { + SkOpAngle* last = fNext; + do { + SkOpAngle* next = last->fNext; + if (next == this) { + return last; + } + last = next; + } while (true); } void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { +#if DEBUG_ANGLE + fID = 0; +#endif fSegment = segment; fStart = start; fEnd = end; + fNext = NULL; + fComputeSector = fComputedSector = false; + fStop = false; setSpans(); + setSector(); +} + +void SkOpAngle::setCurveHullSweep() { + fUnorderedSweep = false; + fSweep[0] = fCurvePart[1] - fCurvePart[0]; + if (SkPath::kLine_Verb == fSegment->verb()) { + fSweep[1] = fSweep[0]; + return; + } + fSweep[1] = fCurvePart[2] - fCurvePart[0]; + if (SkPath::kCubic_Verb != fSegment->verb()) { + if (!fSweep[0].fX && !fSweep[0].fY) { + fSweep[0] = fSweep[1]; + } + return; + } + SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0]; + if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { + fSweep[0] = fSweep[1]; + fSweep[1] = thirdSweep; + if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { + fSweep[0] = fSweep[1]; + fCurvePart[1] = fCurvePart[3]; + fIsCurve = false; + } + return; + } + double s1x3 = fSweep[0].crossCheck(thirdSweep); + double s3x2 = thirdSweep.crossCheck(fSweep[1]); + if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors + return; + } + double s2x1 = fSweep[1].crossCheck(fSweep[0]); + // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble + // probably such wide sweeps should be artificially subdivided earlier so that never happens + SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); + if (s3x2 * s2x1 < 0) { + SkASSERT(s2x1 * s1x3 > 0); + fSweep[0] = fSweep[1]; + fUnorderedSweep = true; + } + fSweep[1] = thirdSweep; +} + +void SkOpAngle::setSector() { + SkPath::Verb verb = fSegment->verb(); + if (SkPath::kLine_Verb != verb && small()) { + fSectorStart = fSectorEnd = -1; + fSectorMask = 0; + fComputeSector = true; // can't determine sector until segment length can be found + return; + } + fSectorStart = findSector(verb, fSweep[0].fX, fSweep[0].fY); + if (!fIsCurve) { // if it's a line or line-like, note that both sectors are the same + SkASSERT(fSectorStart >= 0); + fSectorEnd = fSectorStart; + fSectorMask = 1 << fSectorStart; + return; + } + SkASSERT(SkPath::kLine_Verb != verb); + fSectorEnd = findSector(verb, fSweep[1].fX, fSweep[1].fY); + if (fSectorEnd == fSectorStart) { + SkASSERT((fSectorStart & 3) != 3); // if the sector has no span, it can't be an exact angle + fSectorMask = 1 << fSectorStart; + return; + } + bool crossesZero = checkCrossesZero(); + int start = SkTMin(fSectorStart, fSectorEnd); + bool curveBendsCCW = (fSectorStart == start) ^ crossesZero; + // bump the start and end of the sector span if they are on exact compass points + if ((fSectorStart & 3) == 3) { + fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f; + } + if ((fSectorEnd & 3) == 3) { + fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f; + } + crossesZero = checkCrossesZero(); + start = SkTMin(fSectorStart, fSectorEnd); + int end = SkTMax(fSectorStart, fSectorEnd); + if (!crossesZero) { + fSectorMask = (unsigned) -1 >> (31 - end + start) << start; + } else { + fSectorMask = (unsigned) -1 >> (31 - start) | (-1 << end); + } } void SkOpAngle::setSpans() { fUnorderable = fSegment->isTiny(this); fLastMarked = NULL; - fUnsortable = false; const SkPoint* pts = fSegment->pts(); - if (fSegment->verb() != SkPath::kLine_Verb) { - fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); - fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf); - } - // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try - // rounding the curve part to float precision here - // fCurvePart.round(fSegment->verb()); - switch (fSegment->verb()) { + SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY + = SK_ScalarNaN); + fSegment->subDivide(fStart, fEnd, &fCurvePart); + setCurveHullSweep(); + const SkPath::Verb verb = fSegment->verb(); + if (verb != SkPath::kLine_Verb + && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) { + SkDLine lineHalf; + lineHalf[0].set(fCurvePart[0].asSkPoint()); + lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint()); + fTangentHalf.lineEndPoints(lineHalf); + fSide = 0; + } + switch (verb) { case SkPath::kLine_Verb: { SkASSERT(fStart != fEnd); - fCurvePart[0].set(pts[fStart > fEnd]); - fCurvePart[1].set(pts[fStart < fEnd]); - fComputed = false; - // OPTIMIZATION: for pure line compares, we never need fTangentPart.c - fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); + const SkPoint& cP1 = pts[fStart < fEnd]; + SkDLine lineHalf; + lineHalf[0].set(fSegment->span(fStart).fPt); + lineHalf[1].set(cP1); + fTangentHalf.lineEndPoints(lineHalf); fSide = 0; - fSide2 = 0; - } break; + fIsCurve = false; + } return; case SkPath::kQuad_Verb: { - fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf)); - SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); - fTangentPart.quadEndPoints(quad); - fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only - if (fComputed && dx() > 0 && approximately_zero(dy())) { - SkDCubic origCurve; // can't use segment's curve in place since it may be flipped - int last = fSegment->count() - 1; - fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); - SkLineParameters origTan; - origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); - if (origTan.dx() <= 0 - || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match? - fUnorderable = true; - return; - } - } + SkLineParameters tangentPart; + SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart); + (void) tangentPart.quadEndPoints(quad2); + fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only } break; case SkPath::kCubic_Verb: { - double startT = fSegment->t(fStart); - fSide2 = -fTangentHalf.cubicPart(fCurveHalf); - fTangentPart.cubicEndPoints(fCurvePart); + SkLineParameters tangentPart; + (void) tangentPart.cubicPart(fCurvePart); + fSide = -tangentPart.pointDistance(fCurvePart[3]); double testTs[4]; // OPTIMIZATION: keep inflections precomputed with cubic segment? int testCount = SkDCubic::FindInflections(pts, testTs); + double startT = fSegment->t(fStart); double endT = fSegment->t(fEnd); double limitT = endT; int index; for (index = 0; index < testCount; ++index) { - if (!between(startT, testTs[index], limitT)) { + if (!::between(startT, testTs[index], limitT)) { testTs[index] = -1; } } @@ -354,82 +992,56 @@ void SkOpAngle::setSpans() { } // OPTIMIZE: could avoid call for t == startT, endT SkDPoint pt = dcubic_xy_at_t(pts, testT); - double testSide = fTangentPart.pointDistance(pt); + SkLineParameters tangentPart; + tangentPart.cubicEndPoints(fCurvePart); + double testSide = tangentPart.pointDistance(pt); if (fabs(bestSide) < fabs(testSide)) { bestSide = testSide; } } fSide = -bestSide; // compare sign only - SkASSERT(fSide == 0 || fSide2 != 0); - if (fComputed && dx() > 0 && approximately_zero(dy())) { - SkDCubic origCurve; // can't use segment's curve in place since it may be flipped - int last = fSegment->count() - 1; - fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); - SkDCubicPair split = origCurve.chopAt(startT); - SkLineParameters splitTan; - splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); - if (splitTan.dx() <= 0) { - fUnorderable = true; - fUnsortable = fSegment->isTiny(this); - return; - } - // if one is < 0 and the other is >= 0 - if (dy() * splitTan.dy() < 0) { - fUnorderable = true; - fUnsortable = fSegment->isTiny(this); - return; - } - } } break; default: SkASSERT(0); } - if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { - return; - } - if (fSegment->verb() == SkPath::kLine_Verb) { - return; - } - SkASSERT(fStart != fEnd); - int smaller = SkMin32(fStart, fEnd); - int larger = SkMax32(fStart, fEnd); - while (smaller < larger && fSegment->span(smaller).fTiny) { - ++smaller; - } - if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) { - #if DEBUG_UNSORTABLE - SkPoint iPt = fSegment->xyAtT(fStart); - SkPoint ePt = fSegment->xyAtT(fEnd); - SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, - fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); - #endif - fUnsortable = true; - return; - } - fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart - : fSegment->span(larger).fUnsortableEnd; -#if DEBUG_UNSORTABLE - if (fUnsortable) { - SkPoint iPt = fSegment->xyAtT(smaller); - SkPoint ePt = fSegment->xyAtT(larger); - SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, - smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); +} + +bool SkOpAngle::small() const { + int min = SkMin32(fStart, fEnd); + int max = SkMax32(fStart, fEnd); + for (int index = min; index < max; ++index) { + const SkOpSpan& mSpan = fSegment->span(index); + if (!mSpan.fSmall) { + return false; + } } -#endif - return; + return true; } -#ifdef SK_DEBUG -void SkOpAngle::dump() const { - const SkOpSpan& spanStart = fSegment->span(fStart); - const SkOpSpan& spanEnd = fSegment->span(fEnd); - const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd; - SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=", - fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart), - fStart, spanStart.fT, fEnd, spanEnd.fT); - SkPathOpsDebug::WindingPrintf(spanMin.fWindSum); - SkDebugf(" oppWind="); - SkPathOpsDebug::WindingPrintf(spanMin.fOppSum), - SkDebugf(" done=%d\n", spanMin.fDone); +bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const { + if (s0xt0 == 0) { + return false; + } + // if the ctrl tangents are not nearly parallel, use them + // solve for opposite direction displacement scale factor == m + // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x + // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] + // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) + // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) + // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x + // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) + // m = v1.cross(v2) / v1.dot(v2) + const SkDVector* sweep = fSweep; + const SkDVector* tweep = rh.fSweep; + double s0dt0 = sweep[0].dot(tweep[0]); + if (!s0dt0) { + return true; + } + SkASSERT(s0dt0 != 0); + double m = s0xt0 / s0dt0; + double sDist = sweep[0].length() * m; + double tDist = tweep[0].length() * m; + bool useS = fabs(sDist) < fabs(tDist); + double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist)); + return mFactor < 5000; // empirically found limit } -#endif diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index 583f5ec8b3..87a858a2db 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -8,8 +8,6 @@ #define SkOpAngle_DEFINED #include "SkLineParameters.h" -#include "SkPath.h" -#include "SkPathOpsCubic.h" class SkOpSegment; struct SkOpSpan; @@ -26,28 +24,29 @@ public: kBinaryOpp, }; - bool operator<(const SkOpAngle& rh) const; - - bool calcSlop(double x, double y, double rx, double ry, bool* result) const; - - double dx() const { - return fTangentPart.dx(); + int end() const { + return fEnd; } - double dy() const { - return fTangentPart.dy(); - } + const SkOpAngle* findFirst() const; - int end() const { - return fEnd; + bool inLoop() const { + return !!fNext; } + void insert(SkOpAngle* ); bool isHorizontal() const; + SkOpSpan* lastMarked() const; + int loopCount() const; + void markStops(); + bool merge(SkOpAngle* ); - SkOpSpan* lastMarked() const { - return fLastMarked; + SkOpAngle* next() const { + return fNext; } + SkOpAngle* previous() const; + void set(const SkOpSegment* segment, int start, int end); void setLastMarked(SkOpSpan* marked) { @@ -62,6 +61,8 @@ public: return SkSign32(fStart - fEnd); } + bool small() const; + int start() const { return fStart; } @@ -70,43 +71,78 @@ public: return fUnorderable; } - bool unsortable() const { - return fUnsortable; - } - -#ifdef SK_DEBUG - void dump() const; + // available to testing only +#if DEBUG_SORT + void debugLoop() const; // called by code during run +#endif +#if DEBUG_ANGLE + void debugSameAs(const SkOpAngle* compare) const; #endif + void dump() const; + void dumpFromTo(const SkOpSegment* fromSeg, int from, int to) const; #if DEBUG_ANGLE void setID(int id) { fID = id; } #endif +#if DEBUG_VALIDATE + void debugValidateLoop() const; +#endif private: - bool lengthen(const SkOpAngle& ); + bool after(const SkOpAngle* test) const; + int allOnOneSide(const SkOpAngle& test) const; + bool calcSlop(double x, double y, double rx, double ry, bool* result) const; + bool checkCrossesZero() const; + bool checkParallel(const SkOpAngle& ) const; + bool computeSector(); + int convexHullOverlaps(const SkOpAngle& ) const; + double distEndRatio(double dist) const; + int findSector(SkPath::Verb verb, double x, double y) const; + bool endsIntersect(const SkOpAngle& ) const; + double midT() const; + bool oppositePlanes(const SkOpAngle& rh) const; + bool orderable(const SkOpAngle& rh) const; // false == this < rh ; true == this > rh + void setCurveHullSweep(); + void setSector(); void setSpans(); + bool tangentsDiverge(const SkOpAngle& rh, double s0xt0) const; SkDCubic fCurvePart; // the curve from start to end - SkDCubic fCurveHalf; // the curve from start to 1 or 0 double fSide; - double fSide2; - SkLineParameters fTangentPart; - SkLineParameters fTangentHalf; + SkLineParameters fTangentHalf; // used only to sort a pair of lines or line-like sections const SkOpSegment* fSegment; + SkOpAngle* fNext; SkOpSpan* fLastMarked; + SkDVector fSweep[2]; int fStart; int fEnd; - bool fComputed; // tangent is computed, may contain some error - // if subdividing a quad or cubic causes the tangent to go from the maximum angle to the - // minimum, mark it unorderable. It still can be sorted, which is good enough for find-top - // but can't be ordered, and therefore can't be used to compute winding - bool fUnorderable; - mutable bool fUnsortable; // this alone is editable by the less than operator + int fSectorMask; + char fSectorStart; // in 32nds of a circle + char fSectorEnd; + bool fIsCurve; + bool fStop; // set if ordered angle is greater than the previous + mutable bool fUnorderable; // this is editable by orderable() + bool fUnorderedSweep; // set when a cubic's first control point between the sweep vectors + bool fComputeSector; + bool fComputedSector; + +#if DEBUG_SORT + void debugOne(bool showFunc) const; // available to testing only +#endif #if DEBUG_ANGLE + int debugID() const { return fID; } int fID; #endif +#if DEBUG_VALIDATE + void debugValidateNext() const; // in debug builds, verify that angle loop is uncorrupted +#else + void debugValidateNext() const {} +#endif + void dumpLoop() const; // utility to be called by user from debugger + void dumpPartials() const; // utility to be called by user from debugger + friend class PathOpsAngleTester; }; #endif diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index 874de381b1..db805a214f 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -148,6 +148,16 @@ bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherI return true; } +bool SkOpContour::calcAngles() { + int segmentCount = fSegments.count(); + for (int test = 0; test < segmentCount; ++test) { + if (!fSegments[test].calcAngles()) { + return false; + } + } + return true; +} + void SkOpContour::calcCoincidentWinding() { int count = fCoincidences.count(); #if DEBUG_CONCIDENT @@ -277,6 +287,13 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) #endif } +void SkOpContour::sortAngles() { + int segmentCount = fSegments.count(); + for (int test = 0; test < segmentCount; ++test) { + fSegments[test].sortAngles(); + } +} + void SkOpContour::sortSegments() { int segmentCount = fSegments.count(); fSortedSegments.push_back_n(segmentCount); diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 8cedab4cb1..5b92a4b071 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -25,7 +25,7 @@ class SkOpContour { public: SkOpContour() { reset(); -#ifdef SK_DEBUG +#if defined(SK_DEBUG) || !FORCE_RELEASE fID = ++SkPathOpsDebug::gContourID; #endif } @@ -77,18 +77,29 @@ public: return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT); } - int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) { + int addSelfT(int segIndex, const SkPoint& pt, double newT) { setContainsIntercepts(); - return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT); + return fSegments[segIndex].addSelfT(pt, newT); } const SkPathOpsBounds& bounds() const { return fBounds; } + bool calcAngles(); void calcCoincidentWinding(); void calcPartialCoincidentWinding(); + void checkDuplicates() { + int segmentCount = fSegments.count(); + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + SkOpSegment& segment = fSegments[sIndex]; + if (segment.count() > 2) { + segment.checkDuplicates(); + } + } + } + void checkEnds() { if (!fContainsCurves) { return; @@ -106,6 +117,26 @@ public: } } + void checkMultiples() { + int segmentCount = fSegments.count(); + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + SkOpSegment& segment = fSegments[sIndex]; + if (segment.count() > 2) { + segment.checkMultiples(); + } + } + } + + void checkSmall() { + int segmentCount = fSegments.count(); + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + SkOpSegment& segment = fSegments[sIndex]; + if (segment.hasSmall()) { + segment.checkSmall(); + } + } + } + // if same point has different T values, choose a common T void checkTiny() { int segmentCount = fSegments.count(); @@ -113,7 +144,10 @@ public: return; } for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { - fSegments[sIndex].checkTiny(); + SkOpSegment& segment = fSegments[sIndex]; + if (segment.hasTiny()) { + segment.checkTiny(); + } } } @@ -192,6 +226,7 @@ public: fXor = isXor; } + void sortAngles(); void sortSegments(); const SkPoint& start() const { @@ -242,6 +277,12 @@ public: static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList); #endif + // available to test routines only + void dump() const; + void dumpAngles() const; + void dumpPts() const; + void dumpSpans() const; + private: void calcCommonCoincidentWinding(const SkCoincidence& ); void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial); @@ -261,8 +302,11 @@ private: bool fOperand; // true for the second argument to a binary operator bool fXor; bool fOppXor; -#ifdef SK_DEBUG +#if defined(SK_DEBUG) || !FORCE_RELEASE + int debugID() const { return fID; } int fID; +#else + int debugID() const { return -1; } #endif }; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 00963403b7..727da4a5f5 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -20,8 +20,8 @@ static const bool gUnaryActiveEdge[2][2] = { static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = { // miFrom=0 miFrom=1 -// miTo=0 miTo=1 miTo=0 miTo=1 -// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 +// miTo=0 miTo=1 miTo=0 miTo=1 +// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su @@ -37,22 +37,22 @@ enum { kMissingSpanCount = 4, // FIXME: determine what this should be }; -// note that this follows the same logic flow as build angles -bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) { - if (activeAngleInner(index, done, angles)) { - return true; +const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done, + bool* sortable) const { + if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) { + return result; } double referenceT = fTs[index].fT; int lesser = index; while (--lesser >= 0 && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) { - if (activeAngleOther(lesser, done, angles)) { - return true; + if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) { + return result; } } do { - if (activeAngleOther(index, done, angles)) { - return true; + if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) { + return result; } if (++index == fTs.count()) { break; @@ -62,49 +62,65 @@ bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* a continue; } } while (precisely_negative(fTs[index].fT - referenceT)); - return false; + return NULL; } -bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) { - SkOpSpan* span = &fTs[index]; - SkOpSegment* other = span->fOther; - int oIndex = span->fOtherIndex; - return other->activeAngleInner(oIndex, done, angles); -} - -bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) { +const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done, + bool* sortable) const { int next = nextExactSpan(index, 1); if (next > 0) { - SkOpSpan& upSpan = fTs[index]; + const SkOpSpan& upSpan = fTs[index]; + if (upSpan.fUnsortableStart) { + *sortable = false; + return NULL; + } if (upSpan.fWindValue || upSpan.fOppValue) { - addAngle(angles, index, next); - if (upSpan.fDone || upSpan.fUnsortableEnd) { - (*done)++; - } else if (upSpan.fWindSum != SK_MinS32) { - return true; + if (*end < 0) { + *start = index; + *end = next; } - } else if (!upSpan.fDone) { - upSpan.fDone = true; - fDoneSpans++; + if (!upSpan.fDone && !upSpan.fUnsortableEnd) { + if (upSpan.fWindSum != SK_MinS32) { + return spanToAngle(index, next); + } + *done = false; + } + } else { + SkASSERT(upSpan.fDone); } } int prev = nextExactSpan(index, -1); // edge leading into junction if (prev >= 0) { - SkOpSpan& downSpan = fTs[prev]; + const SkOpSpan& downSpan = fTs[prev]; + if (downSpan.fUnsortableEnd) { + *sortable = false; + return NULL; + } if (downSpan.fWindValue || downSpan.fOppValue) { - addAngle(angles, index, prev); - if (downSpan.fDone) { - (*done)++; - } else if (downSpan.fWindSum != SK_MinS32) { - return true; + if (*end < 0) { + *start = index; + *end = prev; } - } else if (!downSpan.fDone) { - downSpan.fDone = true; - fDoneSpans++; + if (!downSpan.fDone) { + if (downSpan.fWindSum != SK_MinS32) { + return spanToAngle(index, prev); + } + *done = false; + } + } else { + SkASSERT(downSpan.fDone); } } - return false; + return NULL; +} + +const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done, + bool* sortable) const { + const SkOpSpan* span = &fTs[index]; + SkOpSegment* other = span->fOther; + int oIndex = span->fOtherIndex; + return other->activeAngleInner(oIndex, start, end, done, sortable); } SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const { @@ -159,30 +175,28 @@ bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask if (fOperand) { SkTSwap<int>(sumMiWinding, sumSuWinding); } - int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; - return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding, - &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); + return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding); } bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, - int* sumMiWinding, int* sumSuWinding, - int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) { + int* sumMiWinding, int* sumSuWinding) { + int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; setUpWindings(index, endIndex, sumMiWinding, sumSuWinding, - maxWinding, sumWinding, oppMaxWinding, oppSumWinding); + &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); bool miFrom; bool miTo; bool suFrom; bool suTo; if (operand()) { - miFrom = (*oppMaxWinding & xorMiMask) != 0; - miTo = (*oppSumWinding & xorMiMask) != 0; - suFrom = (*maxWinding & xorSuMask) != 0; - suTo = (*sumWinding & xorSuMask) != 0; + miFrom = (oppMaxWinding & xorMiMask) != 0; + miTo = (oppSumWinding & xorMiMask) != 0; + suFrom = (maxWinding & xorSuMask) != 0; + suTo = (sumWinding & xorSuMask) != 0; } else { - miFrom = (*maxWinding & xorMiMask) != 0; - miTo = (*sumWinding & xorMiMask) != 0; - suFrom = (*oppMaxWinding & xorSuMask) != 0; - suTo = (*oppSumWinding & xorSuMask) != 0; + miFrom = (maxWinding & xorMiMask) != 0; + miTo = (sumWinding & xorMiMask) != 0; + suFrom = (oppMaxWinding & xorSuMask) != 0; + suTo = (oppSumWinding & xorSuMask) != 0; } bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; #if DEBUG_ACTIVE_OP @@ -194,24 +208,18 @@ bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex bool SkOpSegment::activeWinding(int index, int endIndex) { int sumWinding = updateWinding(endIndex, index); - int maxWinding; - return activeWinding(index, endIndex, &maxWinding, &sumWinding); + return activeWinding(index, endIndex, &sumWinding); } -bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) { - setUpWinding(index, endIndex, maxWinding, sumWinding); - bool from = *maxWinding != 0; +bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) { + int maxWinding; + setUpWinding(index, endIndex, &maxWinding, sumWinding); + bool from = maxWinding != 0; bool to = *sumWinding != 0; bool result = gUnaryActiveEdge[from][to]; return result; } -void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const { - SkASSERT(start != end); - SkOpAngle& angle = anglesPtr->push_back(); - angle.set(this, start, end); -} - void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) { int tIndex = -1; @@ -299,10 +307,36 @@ void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, do { ++tIndex; } while (startPt != fTs[tIndex].fPt); + int ttIndex = tIndex; + bool checkOtherTMatch = false; + do { + const SkOpSpan& span = fTs[ttIndex]; + if (startPt != span.fPt) { + break; + } + if (span.fOther == other && span.fPt == startPt) { + checkOtherTMatch = true; + break; + } + } while (++ttIndex < count()); do { ++oIndex; } while (startPt != other->fTs[oIndex].fPt); - if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) { + bool skipAdd = false; + if (checkOtherTMatch) { + int ooIndex = oIndex; + do { + const SkOpSpan& oSpan = other->fTs[ooIndex]; + if (startPt != oSpan.fPt) { + break; + } + if (oSpan.fT == fTs[ttIndex].fOtherT) { + skipAdd = true; + break; + } + } while (++ooIndex < other->count()); + } + if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) { addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt); } SkPoint nextPt = startPt; @@ -378,6 +412,30 @@ void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active // return ePtr[SkPathOpsVerbToPoints(fVerb)]; } +void SkOpSegment::addEndSpan(int endIndex) { + int spanCount = fTs.count(); + int angleIndex = fAngles.count(); + int startIndex = endIndex - 1; + while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) { + ++startIndex; + SkASSERT(startIndex < spanCount - 1); + ++endIndex; + } + fAngles.push_back().set(this, spanCount - 1, startIndex); +#if DEBUG_ANGLE + fAngles.back().setID(angleIndex); + debugCheckPointsEqualish(endIndex, spanCount); +#endif + setFromAngleIndex(endIndex, angleIndex); +} + +void SkOpSegment::setFromAngleIndex(int endIndex, int angleIndex) { + int spanCount = fTs.count(); + do { + fTs[endIndex].fFromAngleIndex = angleIndex; + } while (++endIndex < spanCount); +} + void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) { init(pts, SkPath::kLine_Verb, operand, evenOdd); fBounds.set(pts, 2); @@ -400,6 +458,92 @@ void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { fBounds.setQuadBounds(pts); } +int SkOpSegment::addSingletonAngleDown(int endIndex, SkOpSegment** otherPtr) { + int startIndex = findEndSpan(endIndex); + SkASSERT(startIndex > 0); + int spanIndex = endIndex - 1; + fSingletonAngles.push_back().set(this, spanIndex, startIndex - 1); + setFromAngleIndex(startIndex, fAngles.count() + fSingletonAngles.count() - 1); + SkOpSegment* other; + do { + other = fTs[spanIndex].fOther; + if (other->fTs[0].fWindValue) { + break; + } + --spanIndex; + SkASSERT(fTs[spanIndex].fT == 1); + } while (true); + int oEndIndex = other->findStartSpan(0); + SkASSERT(oEndIndex > 0); + int otherIndex = other->fSingletonAngles.count(); + other->fSingletonAngles.push_back().set(other, 0, oEndIndex); + other->setToAngleIndex(oEndIndex, other->fAngles.count() + otherIndex); + *otherPtr = other; + return otherIndex; +} + +int SkOpSegment::addSingletonAngleUp(int start, SkOpSegment** otherPtr) { + int endIndex = findStartSpan(start); + SkASSERT(endIndex > 0); + int thisIndex = fSingletonAngles.count(); + fSingletonAngles.push_back().set(this, start, endIndex); + setToAngleIndex(endIndex, fAngles.count() + thisIndex); + int spanIndex = start; + SkOpSegment* other; + int oCount, oStartIndex; + do { + other = fTs[spanIndex].fOther; + oCount = other->count(); + oStartIndex = other->findEndSpan(oCount); + SkASSERT(oStartIndex > 0); + if (other->fTs[oStartIndex - 1].fWindValue) { + break; + } + ++spanIndex; + SkASSERT(fTs[spanIndex].fT == 0); + } while (true); + int otherIndex = other->fSingletonAngles.count(); + other->fSingletonAngles.push_back().set(other, oCount - 1, oStartIndex - 1); + other->setFromAngleIndex(oStartIndex, other->fAngles.count() + otherIndex); + *otherPtr = other; + return otherIndex; +} + +SkOpAngle* SkOpSegment::addSingletonAngles(int start, int step) { + int thisIndex = fSingletonAngles.count(); + SkOpSegment* other; + int otherIndex; + if (step > 0) { + otherIndex = addSingletonAngleUp(start, &other); + } else { + otherIndex = addSingletonAngleDown(start + 1, &other); + } + fSingletonAngles[thisIndex].insert(&other->fSingletonAngles[otherIndex]); +#if DEBUG_ANGLE + fSingletonAngles[thisIndex].setID(fAngles.count() + thisIndex); + other->fSingletonAngles[otherIndex].setID(other->fAngles.count() + otherIndex); +#endif + return &fSingletonAngles[thisIndex]; +} + +void SkOpSegment::addStartSpan(int endIndex) { + int angleIndex = fAngles.count(); + int index = 0; + fAngles.push_back().set(this, index, endIndex); +#if DEBUG_ANGLE + fAngles.back().setID(angleIndex); + debugCheckPointsEqualish(index, endIndex); +#endif + setToAngleIndex(endIndex, angleIndex); +} + +void SkOpSegment::setToAngleIndex(int endIndex, int angleIndex) { + int index = 0; + do { + fTs[index].fToAngleIndex = angleIndex; + } while (++index < endIndex); +} + // Defer all coincident edge processing until // after normal intersections have been computed @@ -408,6 +552,10 @@ void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { // add non-coincident intersection. Resulting edges are sorted in T. int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { + SkASSERT(this != other || fVerb == SkPath::kCubic_Verb); + #if 0 // this needs an even rougher association to be useful + SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt)); + #endif if (precisely_zero(newT)) { newT = 0; } else if (precisely_equal(newT, 1)) { @@ -416,10 +564,10 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { // FIXME: in the pathological case where there is a ton of intercepts, // binary search? int insertedAt = -1; - size_t tCount = fTs.count(); + int tCount = fTs.count(); const SkPoint& firstPt = fPts[0]; const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)]; - for (size_t index = 0; index < tCount; ++index) { + for (int index = 0; index < tCount; ++index) { // OPTIMIZATION: if there are three or more identical Ts, then // the fourth and following could be further insertion-sorted so // that all the edges are clockwise or counterclockwise. @@ -457,93 +605,69 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX) && approximately_equal(xyAtT(newT).fY, pt.fY)); #endif + span->fFromAngleIndex = -1; + span->fToAngleIndex = -1; span->fWindSum = SK_MinS32; span->fOppSum = SK_MinS32; span->fWindValue = 1; span->fOppValue = 0; - span->fSmall = false; - span->fTiny = false; - span->fLoop = false; + span->fChased = false; if ((span->fDone = newT == 1)) { ++fDoneSpans; } + span->fLoop = false; + span->fSmall = false; + span->fTiny = false; span->fUnsortableStart = false; span->fUnsortableEnd = false; int less = -1; - while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) { - if (span[less].fDone) { - break; - } - double tInterval = newT - span[less].fT; - if (precisely_negative(tInterval)) { - break; - } +// find range of spans with nearly the same point as this one + while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) { if (fVerb == SkPath::kCubic_Verb) { + double tInterval = newT - span[less].fT; double tMid = newT - tInterval / 2; SkDPoint midPt = dcubic_xy_at_t(fPts, tMid); if (!midPt.approximatelyEqual(xyAtT(span))) { break; } } - span[less].fSmall = true; - bool tiny = span[less].fPt == span->fPt; - span[less].fTiny = tiny; - span[less].fDone = true; - if (approximately_negative(newT - span[less].fT) && tiny) { - if (approximately_greater_than_one(newT)) { - SkASSERT(&span[less] - fTs.begin() < fTs.count()); - span[less].fUnsortableStart = true; - if (&span[less - 1] - fTs.begin() >= 0) { - span[less - 1].fUnsortableEnd = true; - } - } - if (approximately_less_than_zero(span[less].fT)) { - SkASSERT(&span[less + 1] - fTs.begin() < fTs.count()); - SkASSERT(&span[less] - fTs.begin() >= 0); - span[less + 1].fUnsortableStart = true; - span[less].fUnsortableEnd = true; - } - } - ++fDoneSpans; --less; } int more = 1; - while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) { - if (span[more - 1].fDone) { - break; - } - double tEndInterval = span[more].fT - newT; - if (precisely_negative(tEndInterval)) { - if ((span->fTiny = span[more].fTiny)) { - span->fDone = true; - ++fDoneSpans; - } - break; - } + while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) { if (fVerb == SkPath::kCubic_Verb) { + double tEndInterval = span[more].fT - newT; double tMid = newT - tEndInterval / 2; SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid); if (!midEndPt.approximatelyEqual(xyAtT(span))) { break; } } - span[more - 1].fSmall = true; - bool tiny = span[more].fPt == span->fPt; - span[more - 1].fTiny = tiny; - span[more - 1].fDone = true; - if (approximately_negative(span[more].fT - newT) && tiny) { - if (approximately_greater_than_one(span[more].fT)) { - span[more + 1].fUnsortableStart = true; - span[more].fUnsortableEnd = true; - } - if (approximately_less_than_zero(newT)) { - span[more].fUnsortableStart = true; - span[more - 1].fUnsortableEnd = true; - } - } - ++fDoneSpans; ++more; } + ++less; + --more; + while (more - 1 > less && span[more].fPt == span[more - 1].fPt + && span[more].fT == span[more - 1].fT) { + --more; + } + if (less == more) { + return insertedAt; + } + if (precisely_negative(span[more].fT - span[less].fT)) { + return insertedAt; + } +// if the total range of t values is big enough, mark all tiny + bool tiny = span[less].fPt == span[more].fPt; + int index = less; + do { + fSmall = span[index].fSmall = true; + fTiny |= span[index].fTiny = tiny; + if (!span[index].fDone) { + span[index].fDone = true; + ++fDoneSpans; + } + } while (++index < more); return insertedAt; } @@ -572,7 +696,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS SkASSERT(index < fTs.count()); ++index; } - while (index > 0 && fTs[index].fT == fTs[index - 1].fT) { + while (index > 0 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) { --index; } int oIndex = other->fTs.count(); @@ -581,7 +705,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS } double oStartT = other->fTs[oIndex].fT; // look for first point beyond match - while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) { + while (startPt == other->fTs[--oIndex].fPt || precisely_equal(oStartT, other->fTs[oIndex].fT)) { SkASSERT(oIndex > 0); } SkOpSpan* test = &fTs[index]; @@ -610,7 +734,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS } SkASSERT(index < fTs.count() - 1); test = &fTs[++index]; - } while (testPt == test->fPt || testT == test->fT); + } while (testPt == test->fPt || precisely_equal(testT, test->fT)); SkDEBUGCODE(int originalWindValue = oTest->fWindValue); do { SkASSERT(oTest->fT < 1); @@ -628,7 +752,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS break; } oTest = &other->fTs[--oIndex]; - } while (oTestPt == oTest->fPt || oTestT == oTest->fT); + } while (oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT)); } while (endPt != test->fPt && test->fT < 1); // FIXME: determine if canceled edges need outside ts added int outCount = outsidePts.count(); @@ -643,14 +767,119 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS } } -int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) { +int SkOpSegment::addSelfT(const SkPoint& pt, double newT) { // if the tail nearly intersects itself but not quite, the caller records this separately - int result = addT(other, pt, newT); + int result = addT(this, pt, newT); SkOpSpan* span = &fTs[result]; - span->fLoop = true; + fLoop = span->fLoop = true; return result; } +void SkOpSegment::addSimpleAngle(int index) { + if (index == 0) { + SkASSERT(!fTs[index].fTiny && fTs[index + 1].fT > 0); + addStartSpan(1); + } else { + SkASSERT(!fTs[index - 1].fTiny && fTs[index - 1].fT < 1); + addEndSpan(index); + } + SkOpSpan& span = fTs[index]; + SkOpSegment* other = span.fOther; + SkOpSpan& oSpan = other->fTs[span.fOtherIndex]; + SkOpAngle* angle, * oAngle; + if (index == 0) { + SkASSERT(span.fOtherIndex - 1 >= 0); + SkASSERT(span.fOtherT == 1); + SkDEBUGCODE(SkOpSpan& oPrior = other->fTs[span.fOtherIndex - 1]); + SkASSERT(!oPrior.fTiny && oPrior.fT < 1); + other->addEndSpan(span.fOtherIndex); + angle = &this->angle(span.fToAngleIndex); + oAngle = &other->angle(oSpan.fFromAngleIndex); + } else { + SkASSERT(span.fOtherIndex + 1 < other->count()); + SkASSERT(span.fOtherT == 0); + SkASSERT(!oSpan.fTiny && (other->fTs[span.fOtherIndex + 1].fT > 0 + || (other->fTs[span.fOtherIndex + 1].fFromAngleIndex < 0 + && other->fTs[span.fOtherIndex + 1].fToAngleIndex < 0))); + int oIndex = 1; + do { + const SkOpSpan& osSpan = other->span(oIndex); + if (osSpan.fFromAngleIndex >= 0 || osSpan.fT > 0) { + break; + } + ++oIndex; + SkASSERT(oIndex < other->count()); + } while (true); + other->addStartSpan(oIndex); + angle = &this->angle(span.fFromAngleIndex); + oAngle = &other->angle(oSpan.fToAngleIndex); + } + angle->insert(oAngle); +} + +bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) { + bool aligned = false; + SkOpSpan* span = &fTs[index]; + SkOpSegment* other = span->fOther; + int oIndex = span->fOtherIndex; + SkOpSpan* oSpan = &other->fTs[oIndex]; + if (span->fT != thisT) { + span->fT = thisT; + oSpan->fOtherT = thisT; + aligned = true; + } + if (span->fPt != thisPt) { + span->fPt = thisPt; + oSpan->fPt = thisPt; + aligned = true; + } + double oT = oSpan->fT; + if (oT == 0 || oT == 1) { + return aligned; + } + int oStart = other->nextSpan(oIndex, -1) + 1; + int oEnd = other->nextSpan(oIndex, 1); + oSpan = &other->fTs[oStart]; + oT = oSpan->fT; + bool oAligned = false; + if (oSpan->fPt != thisPt) { + oAligned |= other->alignSpan(oStart, oT, thisPt); + } + int otherIndex = oStart; + while (++otherIndex < oEnd) { + SkOpSpan* oNextSpan = &other->fTs[otherIndex]; + if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) { + oAligned |= other->alignSpan(otherIndex, oT, thisPt); + } + } + if (oAligned) { + other->alignSpanState(oStart, oEnd); + } + return aligned; +} + +void SkOpSegment::alignSpanState(int start, int end) { + SkOpSpan* lastSpan = &fTs[--end]; + bool allSmall = lastSpan->fSmall; + bool allTiny = lastSpan->fTiny; + bool allDone = lastSpan->fDone; + SkDEBUGCODE(int winding = lastSpan->fWindValue); + SkDEBUGCODE(int oppWinding = lastSpan->fOppValue); + int index = start; + while (index < end) { + SkOpSpan* span = &fTs[index]; + span->fSmall = allSmall; + span->fTiny = allTiny; + if (span->fDone != allDone) { + span->fDone = allDone; + fDoneSpans += allDone ? 1 : -1; + } + SkASSERT(span->fWindValue == winding); + SkASSERT(span->fOppValue == oppWinding); + ++index; + } +} + void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr, SkTArray<SkPoint, true>* outsideTs) { int index = *indexPtr; @@ -667,7 +896,7 @@ void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* in TrackOutside(outsideTs, oStartPt); } end = &fTs[++index]; - } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1); + } while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1); *indexPtr = index; } @@ -680,13 +909,16 @@ void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, int oIndex = *oIndexPtr; SkOpSpan* const oTest = &fTs[oIndex]; SkOpSpan* oEnd = oTest; - const SkPoint& startPt = test.fPt; const SkPoint& oStartPt = oTest->fPt; double oStartT = oTest->fT; - if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) { +#if 0 // FIXME : figure out what disabling this breaks + const SkPoint& startPt = test.fPt; + // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition + if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { TrackOutside(oOutsidePts, startPt); } - while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) { +#endif + while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { zeroSpan(oEnd); oEnd = &fTs[++oIndex]; } @@ -711,7 +943,7 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d ++index; } double startT = fTs[index].fT; - while (index > 0 && fTs[index - 1].fT == startT) { + while (index > 0 && precisely_equal(fTs[index - 1].fT, startT)) { --index; } int oIndex = 0; @@ -720,7 +952,7 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d ++oIndex; } double oStartT = other->fTs[oIndex].fT; - while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) { + while (oIndex > 0 && precisely_equal(other->fTs[oIndex - 1].fT, oStartT)) { --oIndex; } SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; @@ -734,12 +966,10 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d do { SkASSERT(test->fT < 1); SkASSERT(oTest->fT < 1); -#if 0 - if (test->fDone || oTest->fDone) { -#else // consolidate the winding count even if done + + // consolidate the winding count even if done if ((test->fWindValue == 0 && test->fOppValue == 0) || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) { -#endif SkDEBUGCODE(int firstWind = test->fWindValue); SkDEBUGCODE(int firstOpp = test->fOppValue); do { @@ -768,14 +998,15 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d test = &fTs[index]; testPt = &test->fPt; testT = test->fT; - if (endPt == *testPt || endT == testT) { - break; - } oTest = &other->fTs[oIndex]; oTestPt = &oTest->fPt; - SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); + if (endPt == *testPt || precisely_equal(endT, testT)) { + break; + } +// SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); } while (endPt != *oTestPt); - if (endPt != *testPt && endT != testT) { // in rare cases, one may have ended before the other + // in rare cases, one may have ended before the other + if (endPt != *testPt && !precisely_equal(endT, testT)) { int lastWind = test[-1].fWindValue; int lastOpp = test[-1].fOppValue; bool zero = lastWind == 0 && lastOpp == 0; @@ -791,7 +1022,43 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d test = &fTs[++index]; testPt = &test->fPt; } while (endPt != *testPt); - } + } + if (endPt != *oTestPt) { + // look ahead to see if zeroing more spans will allows us to catch up + int oPeekIndex = oIndex; + bool success = true; + SkOpSpan* oPeek; + do { + oPeek = &other->fTs[oPeekIndex]; + if (oPeek->fT == 1) { + success = false; + break; + } + ++oPeekIndex; + } while (endPt != oPeek->fPt); + if (success) { + // make sure the matching point completes the coincidence span + success = false; + do { + if (oPeek->fOther == this) { + success = true; + break; + } + oPeek = &other->fTs[++oPeekIndex]; + } while (endPt == oPeek->fPt); + } + if (success) { + do { + if (!binary || test->fWindValue + oTest->fOppValue >= 0) { + other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts); + } else { + other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts); + } + oTest = &other->fTs[oIndex]; + oTestPt = &oTest->fPt; + } while (endPt != *oTestPt); + } + } int outCount = outsidePts.count(); if (!done() && outCount) { addCoinOutsides(outsidePts[0], endPt, other); @@ -803,7 +1070,7 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d // FIXME: this doesn't prevent the same span from being added twice // fix in caller, SkASSERT here? -void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, +const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt) { int tCount = fTs.count(); for (int tIndex = 0; tIndex < tCount; ++tIndex) { @@ -817,7 +1084,7 @@ void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool bor SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", __FUNCTION__, fID, t, other->fID, otherT); #endif - return; + return NULL; } } #if DEBUG_ADD_T_PAIR @@ -830,21 +1097,19 @@ void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool bor other->addOtherT(otherInsertedAt, t, insertedAt); matchWindingValue(insertedAt, t, borrowWind); other->matchWindingValue(otherInsertedAt, otherT, borrowWind); + return &span(insertedAt); } -void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const { - // add edge leading into junction - int min = SkMin32(end, start); - if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) { - addAngle(angles, end, start); - } - // add edge leading away from junction - int step = SkSign32(end - start); - int tIndex = nextExactSpan(end, step); - min = SkMin32(end, tIndex); - if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) { - addAngle(angles, end, tIndex); +const SkOpAngle& SkOpSegment::angle(int index) const { + SkASSERT(index >= 0); + int count = fAngles.count(); + if (index < count) { + return fAngles[index]; } + index -= count; + count = fSingletonAngles.count(); + SkASSERT(index < count); + return fSingletonAngles[index]; } bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const { @@ -862,164 +1127,168 @@ bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const { return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT); } -// note that this follows the same logic flow as active angle -bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const { - double referenceT = fTs[index].fT; - const SkPoint& referencePt = fTs[index].fPt; - int lesser = index; - while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand) - && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) { - buildAnglesInner(lesser, angles); - } - do { - buildAnglesInner(index, angles); - if (++index == fTs.count()) { - break; - } - if (!allowOpp && fTs[index].fOther->fOperand != fOperand) { - break; +// in extreme cases (like the buffer overflow test) return false to abort +// for now, if one t value represents two different points, then the values are too extreme +// to generate meaningful results +bool SkOpSegment::calcAngles() { + int spanCount = fTs.count(); + if (spanCount <= 2) { + return spanCount == 2; + } + int index = 1; + const SkOpSpan* firstSpan = &fTs[index]; + int activePrior = checkSetAngle(0); + const SkOpSpan* span = &fTs[0]; + if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) { + index = findStartSpan(0); // curve start intersects + if (index < 0) { + return false; } - if (fTs[index - 1].fTiny) { - referenceT = fTs[index].fT; - continue; + if (activePrior >= 0) { + addStartSpan(index); } - if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) { - // FIXME - // testQuad8 generates the wrong output unless false is returned here. Other tests will - // take this path although they aren't required to. This means that many go much slower - // because of this sort fail. - // SkDebugf("!!!\n"); + } + bool addEnd; + int endIndex = spanCount - 1; + span = &fTs[endIndex - 1]; + if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects + endIndex = findEndSpan(endIndex); + if (endIndex < 0) { return false; } - } while (precisely_negative(fTs[index].fT - referenceT)); - return true; -} - -void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const { - const SkOpSpan* span = &fTs[index]; - SkOpSegment* other = span->fOther; -// if there is only one live crossing, and no coincidence, continue -// in the same direction -// if there is coincidence, the only choice may be to reverse direction - // find edge on either side of intersection - int oIndex = span->fOtherIndex; - // if done == -1, prior span has already been processed - int step = 1; - int next = other->nextExactSpan(oIndex, step); - if (next < 0) { - step = -step; - next = other->nextExactSpan(oIndex, step); - } - // add candidate into and away from junction - other->addTwoAngles(next, oIndex, angles); -} - -int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType, - SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) { - addTwoAngles(startIndex, endIndex, angles); - if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) { - return SK_NaN32; - } - int angleCount = angles->count(); - // abort early before sorting if an unsortable (not an unorderable) angle is found - if (includeType != SkOpAngle::kUnaryXor) { - int firstIndex = -1; - while (++firstIndex < angleCount) { - const SkOpAngle& angle = (*angles)[firstIndex]; - if (angle.segment()->windSum(&angle) != SK_MinS32) { + } else { + addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts(); + } + SkASSERT(endIndex >= index); + int prior = 0; + while (index < endIndex) { + const SkOpSpan& fromSpan = fTs[index]; // for each intermediate intersection + const SkOpSpan* lastSpan; + span = &fromSpan; + int start = index; + do { + lastSpan = span; + span = &fTs[++index]; + SkASSERT(index < spanCount); + if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) { break; } + if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) { + return false; + } + } while (true); + int angleIndex = fAngles.count(); + int priorAngleIndex; + if (activePrior >= 0) { + int pActive = firstActive(prior); + SkASSERT(pActive < start); + fAngles.push_back().set(this, start, pActive); + priorAngleIndex = angleIndex++; + #if DEBUG_ANGLE + fAngles.back().setID(priorAngleIndex); + #endif } - if (firstIndex == angleCount) { - return SK_MinS32; + int active = checkSetAngle(start); + if (active >= 0) { + SkASSERT(active < index); + fAngles.push_back().set(this, active, index); + #if DEBUG_ANGLE + fAngles.back().setID(angleIndex); + #endif } + #if DEBUG_ANGLE + debugCheckPointsEqualish(start, index); + #endif + prior = start; + do { + const SkOpSpan* startSpan = &fTs[start - 1]; + if (!startSpan->fSmall || startSpan->fFromAngleIndex >= 0 + || startSpan->fToAngleIndex >= 0) { + break; + } + --start; + } while (start > 0); + do { + if (activePrior >= 0) { + SkASSERT(fTs[start].fFromAngleIndex == -1); + fTs[start].fFromAngleIndex = priorAngleIndex; + } + if (active >= 0) { + SkASSERT(fTs[start].fToAngleIndex == -1); + fTs[start].fToAngleIndex = angleIndex; + } + } while (++start < index); + activePrior = active; } - bool sortable = SortAngles2(*angles, sorted); -#if DEBUG_SORT_RAW - if (sorted->count() > 0) { - (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable); + if (addEnd && activePrior >= 0) { + addEndSpan(endIndex); } -#endif - if (!sortable) { - return SK_NaN32; + return true; +} + +int SkOpSegment::checkSetAngle(int tIndex) const { + const SkOpSpan* span = &fTs[tIndex]; + while (span->fTiny /* || span->fSmall */) { + span = &fTs[++tIndex]; } - if (includeType == SkOpAngle::kUnaryXor) { - return SK_MinS32; + return isCanceled(tIndex) ? -1 : tIndex; +} + +// at this point, the span is already ordered, or unorderable, or unsortable +int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) { + SkASSERT(includeType != SkOpAngle::kUnaryXor); + SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex); + if (NULL == firstAngle) { + return SK_NaN32; } // if all angles have a computed winding, // or if no adjacent angles are orderable, // or if adjacent orderable angles have no computed winding, // there's nothing to do // if two orderable angles are adjacent, and one has winding computed, transfer to the other - const SkOpAngle* baseAngle = NULL; - int last = angleCount; - int finalInitialOrderable = -1; + SkOpAngle* baseAngle = NULL; bool tryReverse = false; // look for counterclockwise transfers + SkOpAngle* angle = firstAngle; do { - int index = 0; + int testWinding = angle->segment()->windSum(angle); + if (SK_MinS32 != testWinding && !angle->unorderable()) { + baseAngle = angle; + continue; + } + if (angle->unorderable()) { + baseAngle = NULL; + tryReverse = true; + continue; + } + if (baseAngle) { + ComputeOneSum(baseAngle, angle, includeType); + baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; + tryReverse |= !baseAngle; + } + } while ((angle = angle->next()) != firstAngle); + if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(angle)) { + firstAngle = baseAngle; + tryReverse = true; + } + if (tryReverse) { + baseAngle = NULL; + angle = firstAngle; do { - SkOpAngle* testAngle = (*sorted)[index]; - int testWinding = testAngle->segment()->windSum(testAngle); - if (SK_MinS32 != testWinding && !testAngle->unorderable()) { - baseAngle = testAngle; + int testWinding = angle->segment()->windSum(angle); + if (SK_MinS32 != testWinding) { + baseAngle = angle; continue; } - if (testAngle->unorderable()) { + if (angle->unorderable()) { baseAngle = NULL; - tryReverse = true; continue; } if (baseAngle) { - ComputeOneSum(baseAngle, testAngle, includeType); - baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle - : NULL; - tryReverse |= !baseAngle; - continue; + ComputeOneSumReverse(baseAngle, angle, includeType); + baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; } - if (finalInitialOrderable + 1 == index) { - finalInitialOrderable = index; - } - } while (++index != last); - if (finalInitialOrderable < 0) { - break; - } - last = finalInitialOrderable + 1; - finalInitialOrderable = -2; // make this always negative the second time through - } while (baseAngle); - if (tryReverse) { - baseAngle = NULL; - last = 0; - finalInitialOrderable = angleCount; - do { - int index = angleCount; - while (--index >= last) { - SkOpAngle* testAngle = (*sorted)[index]; - int testWinding = testAngle->segment()->windSum(testAngle); - if (SK_MinS32 != testWinding) { - baseAngle = testAngle; - continue; - } - if (testAngle->unorderable()) { - baseAngle = NULL; - continue; - } - if (baseAngle) { - ComputeOneSumReverse(baseAngle, testAngle, includeType); - baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle - : NULL; - continue; - } - if (finalInitialOrderable - 1 == index) { - finalInitialOrderable = index; - } - } - if (finalInitialOrderable >= angleCount) { - break; - } - last = finalInitialOrderable; - finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through - } while (baseAngle); + } while ((angle = angle->previous()) != firstAngle); } int minIndex = SkMin32(startIndex, endIndex); return windSum(minIndex); @@ -1083,6 +1352,16 @@ void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* ne nextAngle->setLastMarked(last); } +void SkOpSegment::constructLine(SkPoint shortLine[2]) { + addLine(shortLine, false, false); + addT(NULL, shortLine[0], 0); + addT(NULL, shortLine[1], 1); + addStartSpan(1); + addEndSpan(1); + SkOpAngle& angle = fAngles.push_back(); + angle.set(this, 0, 1); +} + int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const { SkScalar bottom = fBounds.fBottom; @@ -1206,6 +1485,141 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { return false; } +const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const { + const SkOpSpan* firstSpan = &thisSpan; // rewind to the start + const SkOpSpan* beginSpan = fTs.begin(); + const SkPoint& testPt = thisSpan.fPt; + while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) { + --firstSpan; + } + return *firstSpan; +} + +const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const { + const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small + const SkOpSpan* lastSpan = &thisSpan; // find the end + const SkPoint& testPt = thisSpan.fPt; + while (lastSpan < endSpan && lastSpan[1].fPt == testPt) { + ++lastSpan; + } + return *lastSpan; +} + +// with a loop, the comparison is move involved +// scan backwards and forwards to count all matching points +// (verify that there are twp scans marked as loops) +// compare that against 2 matching scans for loop plus other results +bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) { + const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start + const SkOpSpan& lastSpan = this->lastSpan(thisSpan); // find the end + double firstLoopT = -1, lastLoopT = -1; + const SkOpSpan* testSpan = &firstSpan - 1; + while (++testSpan <= &lastSpan) { + if (testSpan->fLoop) { + firstLoopT = testSpan->fT; + break; + } + } + testSpan = &lastSpan + 1; + while (--testSpan >= &firstSpan) { + if (testSpan->fLoop) { + lastLoopT = testSpan->fT; + break; + } + } + SkASSERT((firstLoopT == -1) == (lastLoopT == -1)); + if (firstLoopT == -1) { + return false; + } + SkASSERT(firstLoopT < lastLoopT); + testSpan = &firstSpan - 1; + smallCounts[0] = smallCounts[1] = 0; + while (++testSpan <= &lastSpan) { + SkASSERT(approximately_equal(testSpan->fT, firstLoopT) + + approximately_equal(testSpan->fT, lastLoopT) == 1); + smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++; + } + return true; +} + +// see if spans with two or more intersections have the same number on the other end +void SkOpSegment::checkDuplicates() { + debugValidate(); + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; + int index; + int endIndex = 0; + bool endFound; + do { + index = endIndex; + endIndex = nextExactSpan(index, 1); + if ((endFound = endIndex < 0)) { + endIndex = count(); + } + int dupCount = endIndex - index; + if (dupCount < 2) { + continue; + } + do { + const SkOpSpan* thisSpan = &fTs[index]; + SkOpSegment* other = thisSpan->fOther; + int oIndex = thisSpan->fOtherIndex; + int oStart = other->nextExactSpan(oIndex, -1) + 1; + int oEnd = other->nextExactSpan(oIndex, 1); + if (oEnd < 0) { + oEnd = other->count(); + } + int oCount = oEnd - oStart; + // force the other to match its t and this pt if not on an end point + if (oCount != dupCount) { + MissingSpan& missing = missingSpans.push_back(); + missing.fOther = NULL; + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); + missing.fPt = thisSpan->fPt; + const SkOpSpan& oSpan = other->span(oIndex); + if (oCount > dupCount) { + missing.fSegment = this; + missing.fT = thisSpan->fT; + other->checkLinks(&oSpan, &missingSpans); + } else { + missing.fSegment = other; + missing.fT = oSpan.fT; + checkLinks(thisSpan, &missingSpans); + } + if (!missingSpans.back().fOther) { + missingSpans.pop_back(); + } + } + } while (++index < endIndex); + } while (!endFound); + int missingCount = missingSpans.count(); + if (missingCount == 0) { + return; + } + SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence; + for (index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + SkOpSegment* missingOther = missing.fOther; + if (missing.fSegment == missing.fOther) { + continue; + } + const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther, + missing.fOtherT, false, missing.fPt); + if (added && added->fSmall) { + missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence); + } + } + for (index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + missing.fSegment->fixOtherTIndex(); + missing.fOther->fixOtherTIndex(); + } + for (index = 0; index < missingCoincidence.count(); ++index) { + MissingSpan& missing = missingCoincidence[index]; + missing.fSegment->fixOtherTIndex(); + } + debugValidate(); +} + // look to see if the curve end intersects an intermediary that intersects the other void SkOpSegment::checkEnds() { debugValidate(); @@ -1313,7 +1727,9 @@ nextPeekIndex: int missingCount = missingSpans.count(); for (int index = 0; index < missingCount; ++index) { MissingSpan& missing = missingSpans[index]; - addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + if (this != missing.fOther) { + addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + } } fixOtherTIndex(); // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to @@ -1324,6 +1740,84 @@ nextPeekIndex: debugValidate(); } +void SkOpSegment::checkLinks(const SkOpSpan* base, + SkTArray<MissingSpan, true>* missingSpans) const { + const SkOpSpan* first = fTs.begin(); + const SkOpSpan* last = fTs.end() - 1; + SkASSERT(base >= first && last >= base); + const SkOpSegment* other = base->fOther; + const SkOpSpan* oFirst = other->fTs.begin(); + const SkOpSpan* oLast = other->fTs.end() - 1; + const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex]; + const SkOpSpan* test = base; + const SkOpSpan* missing = NULL; + while (test > first && (--test)->fPt == base->fPt) { + CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans); + } + test = base; + while (test < last && (++test)->fPt == base->fPt) { + CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans); + } +} + +// see if spans with two or more intersections all agree on common t and point values +void SkOpSegment::checkMultiples() { + debugValidate(); + int index; + int end = 0; + while (fTs[++end].fT == 0) + ; + while (fTs[end].fT < 1) { + int start = index = end; + end = nextExactSpan(index, 1); + if (end <= index) { + return; // buffer overflow example triggers this + } + if (index + 1 == end) { + continue; + } + // force the duplicates to agree on t and pt if not on the end + double thisT = fTs[index].fT; + const SkPoint& thisPt = fTs[index].fPt; + bool aligned = false; + while (++index < end) { + aligned |= alignSpan(index, thisT, thisPt); + } + if (aligned) { + alignSpanState(start, end); + } + } + debugValidate(); +} + +void SkOpSegment::CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan, + const SkOpSpan* oFirst, const SkOpSpan* oLast, const SkOpSpan** missingPtr, + SkTArray<MissingSpan, true>* missingSpans) { + SkASSERT(oSpan->fPt == test->fPt); + const SkOpSpan* oTest = oSpan; + while (oTest > oFirst && (--oTest)->fPt == test->fPt) { + if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) { + return; + } + } + oTest = oSpan; + while (oTest < oLast && (++oTest)->fPt == test->fPt) { + if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) { + return; + } + } + if (*missingPtr) { + missingSpans->push_back(); + } + MissingSpan& lastMissing = missingSpans->back(); + if (*missingPtr) { + lastMissing = missingSpans->end()[-2]; + } + *missingPtr = test; + lastMissing.fOther = test->fOther; + lastMissing.fOtherT = test->fOtherT; +} + bool SkOpSegment::checkSmall(int index) const { if (fTs[index].fSmall) { return true; @@ -1334,9 +1828,245 @@ bool SkOpSegment::checkSmall(int index) const { return fTs[index].fSmall; } +// a pair of curves may turn into coincident lines -- small may be a hint that that happened +// if a cubic contains a loop, the counts must be adjusted +void SkOpSegment::checkSmall() { + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; + const SkOpSpan* beginSpan = fTs.begin(); + const SkOpSpan* thisSpan = beginSpan - 1; + const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small + while (++thisSpan < endSpan) { + if (!thisSpan->fSmall) { + continue; + } + if (!thisSpan->fWindValue) { + continue; + } + const SkOpSpan& firstSpan = this->firstSpan(*thisSpan); + const SkOpSpan& lastSpan = this->lastSpan(*thisSpan); + ptrdiff_t smallCount = &lastSpan - &firstSpan + 1; + SkASSERT(1 <= smallCount && smallCount < count()); + if (smallCount <= 1) { + SkASSERT(1 == smallCount); + checkSmallCoincidence(firstSpan, NULL); + continue; + } + // at this point, check for missing computed intersections + const SkPoint& testPt = firstSpan.fPt; + thisSpan = &firstSpan - 1; + SkOpSegment* other = NULL; + while (++thisSpan <= &lastSpan) { + other = thisSpan->fOther; + if (other != this) { + break; + } + } + SkASSERT(other != this); + int oIndex = thisSpan->fOtherIndex; + const SkOpSpan& oSpan = other->span(oIndex); + const SkOpSpan& oFirstSpan = other->firstSpan(oSpan); + const SkOpSpan& oLastSpan = other->lastSpan(oSpan); + ptrdiff_t oCount = &oLastSpan - &oFirstSpan + 1; + if (fLoop) { + int smallCounts[2]; + SkASSERT(!other->fLoop); // FIXME: we need more complicated logic for pair of loops + if (calcLoopSpanCount(*thisSpan, smallCounts)) { + if (smallCounts[0] && oCount != smallCounts[0]) { + SkASSERT(0); // FIXME: need a working test case to properly code & debug + } + if (smallCounts[1] && oCount != smallCounts[1]) { + SkASSERT(0); // FIXME: need a working test case to properly code & debug + } + goto nextSmallCheck; + } + } + if (other->fLoop) { + int otherCounts[2]; + if (other->calcLoopSpanCount(other->span(oIndex), otherCounts)) { + if (otherCounts[0] && otherCounts[0] != smallCount) { + SkASSERT(0); // FIXME: need a working test case to properly code & debug + } + if (otherCounts[1] && otherCounts[1] != smallCount) { + SkASSERT(0); // FIXME: need a working test case to properly code & debug + } + goto nextSmallCheck; + } + } + if (oCount != smallCount) { // check if number of pts in this match other + MissingSpan& missing = missingSpans.push_back(); + missing.fOther = NULL; + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); + missing.fPt = testPt; + const SkOpSpan& oSpan = other->span(oIndex); + if (oCount > smallCount) { + missing.fSegment = this; + missing.fT = thisSpan->fT; + other->checkLinks(&oSpan, &missingSpans); + } else { + missing.fSegment = other; + missing.fT = oSpan.fT; + checkLinks(thisSpan, &missingSpans); + } + if (!missingSpans.back().fOther || missing.fSegment->done()) { + missingSpans.pop_back(); + } + } +nextSmallCheck: + thisSpan = &lastSpan; + } + int missingCount = missingSpans.count(); + for (int index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + SkOpSegment* missingOther = missing.fOther; + // note that add t pair may edit span arrays, so prior pointers to spans are no longer valid + if (!missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false, + missing.fPt)) { + continue; + } + int otherTIndex = missingOther->findT(missing.fOtherT, missing.fSegment); + const SkOpSpan& otherSpan = missingOther->span(otherTIndex); + if (otherSpan.fSmall) { + const SkOpSpan* nextSpan = &otherSpan; + do { + ++nextSpan; + } while (nextSpan->fSmall); + missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt, nextSpan->fT, + missingOther); + } else if (otherSpan.fT > 0) { + const SkOpSpan* priorSpan = &otherSpan; + do { + --priorSpan; + } while (priorSpan->fT == otherSpan.fT); + if (priorSpan->fSmall) { + missing.fSegment->addTCancel(missing.fPt, priorSpan->fPt, missingOther); + } + } + } + // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to + // avoid this + for (int index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + missing.fSegment->fixOtherTIndex(); + missing.fOther->fixOtherTIndex(); + } + debugValidate(); +} + +void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span, + SkTArray<MissingSpan, true>* checkMultiple) { + SkASSERT(span.fSmall); + SkASSERT(span.fWindValue); + SkASSERT(&span < fTs.end() - 1); + const SkOpSpan* next = &span + 1; + SkASSERT(!next->fSmall || checkMultiple); + if (checkMultiple) { + while (next->fSmall) { + ++next; + SkASSERT(next < fTs.end()); + } + } + SkOpSegment* other = span.fOther; + while (other != next->fOther) { + if (!checkMultiple) { + return; + } + const SkOpSpan* test = next + 1; + if (test == fTs.end()) { + return; + } + if (test->fPt != next->fPt || !precisely_equal(test->fT, next->fT)) { + return; + } + next = test; + } + SkASSERT(span.fT < next->fT); + int oStartIndex = other->findExactT(span.fOtherT, this); + int oEndIndex = other->findExactT(next->fOtherT, this); + // FIXME: be overly conservative by limiting this to the caller that allows multiple smalls + if (!checkMultiple || fVerb != SkPath::kLine_Verb || other->fVerb != SkPath::kLine_Verb) { + SkPoint mid = ptAtT((span.fT + next->fT) / 2); + const SkOpSpan& oSpanStart = other->fTs[oStartIndex]; + const SkOpSpan& oSpanEnd = other->fTs[oEndIndex]; + SkPoint oMid = other->ptAtT((oSpanStart.fT + oSpanEnd.fT) / 2); + if (!SkDPoint::ApproximatelyEqual(mid, oMid)) { + return; + } + } + // FIXME: again, be overly conservative to avoid breaking existing tests + const SkOpSpan& oSpan = oStartIndex < oEndIndex ? other->fTs[oStartIndex] + : other->fTs[oEndIndex]; + if (checkMultiple && !oSpan.fSmall) { + return; + } + SkASSERT(oSpan.fSmall); + if (oStartIndex < oEndIndex) { + addTCoincident(span.fPt, next->fPt, next->fT, other); + } else { + addTCancel(span.fPt, next->fPt, other); + } + if (!checkMultiple) { + return; + } + // check to see if either segment is coincident with a third segment -- if it is, and if + // the opposite segment is not already coincident with the third, make it so + // OPTIMIZE: to make this check easier, add coincident and cancel could set a coincident bit + if (span.fWindValue != 1 || span.fOppValue != 0) { +// start here; + // iterate through the spans, looking for the third coincident case + // if we find one, we need to return state to the caller so that the indices can be fixed + // this also suggests that all of this function is fragile since it relies on a valid index + } + // probably should make this a common function rather than copy/paste code + if (oSpan.fWindValue != 1 || oSpan.fOppValue != 0) { + const SkOpSpan* oTest = &oSpan; + while (--oTest >= other->fTs.begin()) { + if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) { + break; + } + SkOpSegment* testOther = oTest->fOther; + SkASSERT(testOther != this); + // look in both directions to see if there is a coincident span + const SkOpSpan* tTest = testOther->fTs.begin(); + for (int testIndex = 0; testIndex < testOther->count(); ++testIndex) { + if (tTest->fPt != span.fPt) { + ++tTest; + continue; + } + if (testOther->verb() != SkPath::kLine_Verb + || other->verb() != SkPath::kLine_Verb) { + SkPoint mid = ptAtT((span.fT + next->fT) / 2); + SkPoint oMid = other->ptAtT((oTest->fOtherT + tTest->fT) / 2); + if (!SkDPoint::ApproximatelyEqual(mid, oMid)) { + continue; + } + } +#if DEBUG_CONCIDENT + SkDebugf("%s coincident found=%d %1.9g %1.9g\n", __FUNCTION__, testOther->fID, + oTest->fOtherT, tTest->fT); +#endif + if (tTest->fT < oTest->fOtherT) { + addTCoincident(span.fPt, next->fPt, next->fT, testOther); + } else { + addTCancel(span.fPt, next->fPt, testOther); + } + MissingSpan missing; + missing.fSegment = testOther; + checkMultiple->push_back(missing); + break; + } + } + oTest = &oSpan; + while (++oTest < other->fTs.end()) { + if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) { + break; + } + + } + } +} + // if pair of spans on either side of tiny have the same end point and mid point, mark // them as parallel -// OPTIMIZATION : mark the segment to note that some span is tiny void SkOpSegment::checkTiny() { SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; SkOpSpan* thisSpan = fTs.begin() - 1; @@ -1401,8 +2131,12 @@ void SkOpSegment::checkTiny() { } for (int index = 0; index < missingCount; ++index) { MissingSpan& missing = missingSpans[index]; - missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + if (missing.fSegment != missing.fOther) { + missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, + missing.fPt); + } } + // OPTIMIZE: consolidate to avoid multiple calls to fix index for (int index = 0; index < missingCount; ++index) { MissingSpan& missing = missingSpans[index]; missing.fSegment->fixOtherTIndex(); @@ -1474,6 +2208,16 @@ bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* o return false; } +int SkOpSegment::findEndSpan(int endIndex) const { + const SkOpSpan* span = &fTs[--endIndex]; + const SkPoint& lastPt = span->fPt; + double endT = span->fT; + do { + span = &fTs[--endIndex]; + } while (SkDPoint::ApproximatelyEqual(span->fPt, lastPt) && (span->fT == endT || span->fTiny)); + return endIndex + 1; +} + /* The M and S variable name parts stand for the operators. Mi stands for Minuend (see wiki subtraction, analogous to difference) @@ -1519,56 +2263,40 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart } return other; } - // more than one viable candidate -- measure angles to find best - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted); + // more than one viable candidate -- measure angles to find best + + int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp); bool sortable = calcWinding != SK_NaN32; - if (sortable && sorted.count() == 0) { - // if no edge has a computed winding sum, we can go no further + if (!sortable) { *unsortable = true; return NULL; } - int angleCount = angles.count(); - int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(!sortable || firstIndex >= 0); -#if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); -#endif - if (!sortable) { + SkOpAngle* angle = spanToAngle(end, startIndex); + if (angle->unorderable()) { *unsortable = true; return NULL; } - SkASSERT(sorted[firstIndex]->segment() == this); -#if DEBUG_WINDING - SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, - sorted[firstIndex]->sign()); +#if DEBUG_SORT + SkDebugf("%s\n", __FUNCTION__); + angle->debugLoop(); #endif int sumMiWinding = updateWinding(endIndex, startIndex); int sumSuWinding = updateOppWinding(endIndex, startIndex); if (operand()) { SkTSwap<int>(sumMiWinding, sumSuWinding); } - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; + SkOpAngle* nextAngle = angle->next(); const SkOpAngle* foundAngle = NULL; bool foundDone = false; // iterate through the angle, and compute everyone's winding SkOpSegment* nextSegment; int activeCount = 0; do { - SkASSERT(nextIndex != firstIndex); - if (nextIndex == angleCount) { - nextIndex = 0; - } - const SkOpAngle* nextAngle = sorted[nextIndex]; nextSegment = nextAngle->segment(); - int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), - nextAngle->end(), op, &sumMiWinding, &sumSuWinding, - &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); + nextAngle->end(), op, &sumMiWinding, &sumSuWinding); if (activeAngle) { ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { @@ -1591,6 +2319,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart } SkOpSpan* last = nextAngle->lastMarked(); if (last) { + SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); *chase->append() = last; #if DEBUG_WINDING SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, @@ -1598,7 +2327,13 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart last->fSmall); #endif } - } while (++nextIndex != lastIndex); + } while ((nextAngle = nextAngle->next()) != angle); +#if DEBUG_ANGLE + if (foundAngle) { + foundAngle->debugSameAs(foundAngle); + } +#endif + markDoneBinary(SkMin32(startIndex, endIndex)); if (!foundAngle) { return NULL; @@ -1650,46 +2385,31 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next } return other; } - // more than one viable candidate -- measure angles to find best - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted); + // more than one viable candidate -- measure angles to find best + + int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding); bool sortable = calcWinding != SK_NaN32; - int angleCount = angles.count(); - int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(!sortable || firstIndex >= 0); -#if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); -#endif if (!sortable) { *unsortable = true; return NULL; } - SkASSERT(sorted[firstIndex]->segment() == this); -#if DEBUG_WINDING - SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, - sorted[firstIndex]->sign()); + SkOpAngle* angle = spanToAngle(end, startIndex); +#if DEBUG_SORT + SkDebugf("%s\n", __FUNCTION__); + angle->debugLoop(); #endif int sumWinding = updateWinding(endIndex, startIndex); - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; + SkOpAngle* nextAngle = angle->next(); const SkOpAngle* foundAngle = NULL; bool foundDone = false; - // iterate through the angle, and compute everyone's winding SkOpSegment* nextSegment; int activeCount = 0; do { - SkASSERT(nextIndex != firstIndex); - if (nextIndex == angleCount) { - nextIndex = 0; - } - const SkOpAngle* nextAngle = sorted[nextIndex]; nextSegment = nextAngle->segment(); - int maxWinding; bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), - &maxWinding, &sumWinding); + &sumWinding); if (activeAngle) { ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { @@ -1712,6 +2432,8 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next } SkOpSpan* last = nextAngle->lastMarked(); if (last) { + SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); + // assert here that span isn't already in array *chase->append() = last; #if DEBUG_WINDING SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, @@ -1719,7 +2441,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next last->fSmall); #endif } - } while (++nextIndex != lastIndex); + } while ((nextAngle = nextAngle->next()) != angle); markDoneUnary(SkMin32(startIndex, endIndex)); if (!foundAngle) { return NULL; @@ -1745,7 +2467,9 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort SkASSERT(end >= 0); SkOpSpan* endSpan = &fTs[end]; SkOpSegment* other; - if (isSimple(end)) { +// Detect cases where all the ends canceled out (e.g., +// there is no angle) and therefore there's only one valid connection + if (isSimple(end) || !spanToAngle(end, startIndex)) { #if DEBUG_WINDING SkDebugf("%s simple\n", __FUNCTION__); #endif @@ -1779,39 +2503,21 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); return other; } - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted); - bool sortable = calcWinding != SK_NaN32; - int angleCount = angles.count(); - int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(!sortable || firstIndex >= 0); + // parallel block above with presorted version + SkOpAngle* angle = spanToAngle(end, startIndex); + SkASSERT(angle); #if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable); -#endif - if (!sortable) { - *unsortable = true; - return NULL; - } - SkASSERT(sorted[firstIndex]->segment() == this); -#if DEBUG_WINDING - SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, - sorted[firstIndex]->sign()); + SkDebugf("%s\n", __FUNCTION__); + angle->debugLoop(); #endif - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; + SkOpAngle* nextAngle = angle->next(); const SkOpAngle* foundAngle = NULL; bool foundDone = false; SkOpSegment* nextSegment; int activeCount = 0; do { - SkASSERT(nextIndex != firstIndex); - if (nextIndex == angleCount) { - nextIndex = 0; - } - const SkOpAngle* nextAngle = sorted[nextIndex]; nextSegment = nextAngle->segment(); ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { @@ -1820,12 +2526,12 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort return NULL; } foundAngle = nextAngle; - foundDone = nextSegment->done(nextAngle); - } - if (nextSegment->done()) { - continue; + if (!(foundDone = nextSegment->done(nextAngle))) { + break; + } } - } while (++nextIndex != lastIndex); + nextAngle = nextAngle->next(); + } while (nextAngle != angle); markDone(SkMin32(startIndex, endIndex), 1); if (!foundAngle) { return NULL; @@ -1840,21 +2546,33 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort return nextSegment; } -int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) { - int angleCount = sorted.count(); - int firstIndex = -1; - for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - const SkOpAngle* angle = sorted[angleIndex]; - if (angle->segment() == this && angle->start() == end && - angle->end() == start) { - firstIndex = angleIndex; - break; +int SkOpSegment::findStartSpan(int startIndex) const { + int index = startIndex; + const SkOpSpan* span = &fTs[index]; + const SkPoint& firstPt = span->fPt; + double firstT = span->fT; + do { + if (index > 0) { + if (span->fT != firstT) { + break; + } + if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) { + return -1; + } } - } - return firstIndex; + ++index; + if (span->fTiny) { + if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) { + return -1; + } + firstT = fTs[index++].fT; + } + span = &fTs[index]; + } while (true); + return index; } -int SkOpSegment::findT(double t, const SkOpSegment* match) const { +int SkOpSegment::findExactT(double t, const SkOpSegment* match) const { int count = this->count(); for (int index = 0; index < count; ++index) { const SkOpSpan& span = fTs[index]; @@ -1866,21 +2584,24 @@ int SkOpSegment::findT(double t, const SkOpSegment* match) const { return -1; } -// FIXME: either: -// a) mark spans with either end unsortable as done, or -// b) rewrite findTop / findTopSegment / findTopContour to iterate further -// when encountering an unsortable span +int SkOpSegment::findT(double t, const SkOpSegment* match) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + if (approximately_equal_orderable(span.fT, t) && span.fOther == match) { + return index; + } + } + SkASSERT(0); + return -1; +} -// OPTIMIZATION : for a pair of lines, can we compute points at T (cached) -// and use more concise logic like the old edge walker code? -// FIXME: this needs to deal with coincident edges -SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable, - bool onlySortable) { +SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable) { // iterate through T intersections and return topmost // topmost tangent from y-min to first pt is closer to horizontal SkASSERT(!done()); int firstT = -1; - /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT); + /* SkPoint topPt = */ activeLeftTop(true, &firstT); if (firstT < 0) { *unsortable = true; firstT = 0; @@ -1894,59 +2615,53 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort } // sort the edges to find the leftmost int step = 1; - int end = nextSpan(firstT, step); - if (end == -1) { + int end; + if (span(firstT).fDone || (end = nextSpan(firstT, step)) == -1) { step = -1; end = nextSpan(firstT, step); SkASSERT(end != -1); } // if the topmost T is not on end, or is three-way or more, find left // look for left-ness from tLeft to firstT (matching y of other) - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(firstT - end != 0); - addTwoAngles(end, firstT, &angles); - if (!buildAngles(firstT, &angles, true) && onlySortable) { -// *unsortable = true; -// return NULL; - } - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind); - if (onlySortable && !sortable) { - *unsortable = true; - return NULL; + SkOpAngle* markAngle = spanToAngle(firstT, end); + if (!markAngle) { + markAngle = addSingletonAngles(firstT, step); + } + markAngle->markStops(); + const SkOpAngle* baseAngle = markAngle->findFirst(); + if (!baseAngle) { + return NULL; // nothing to do } - int first = SK_MaxS32; SkScalar top = SK_ScalarMax; - int count = sorted.count(); - for (int index = 0; index < count; ++index) { - const SkOpAngle* angle = sorted[index]; - if (onlySortable && angle->unorderable()) { - continue; - } - SkOpSegment* next = angle->segment(); - SkPathOpsBounds bounds; - next->subDivideBounds(angle->end(), angle->start(), &bounds); - if (approximately_greater(top, bounds.fTop)) { - top = bounds.fTop; - first = index; + const SkOpAngle* firstAngle = NULL; + const SkOpAngle* angle = baseAngle; + do { + if (!angle->unorderable()) { + SkOpSegment* next = angle->segment(); + SkPathOpsBounds bounds; + next->subDivideBounds(angle->end(), angle->start(), &bounds); + if (approximately_greater(top, bounds.fTop)) { + top = bounds.fTop; + firstAngle = angle; + } } - } - SkASSERT(first < SK_MaxS32); -#if DEBUG_SORT // || DEBUG_SWAP_TOP - sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable); + angle = angle->next(); + } while (angle != baseAngle); + SkASSERT(firstAngle); +#if DEBUG_SORT + SkDebugf("%s\n", __FUNCTION__); + firstAngle->debugLoop(); #endif // skip edges that have already been processed - firstT = first - 1; + angle = firstAngle; SkOpSegment* leftSegment; do { - if (++firstT == count) { - firstT = 0; - } - const SkOpAngle* angle = sorted[firstT]; - SkASSERT(!onlySortable || !angle->unsortable()); +// SkASSERT(!angle->unsortable()); leftSegment = angle->segment(); *tIndexPtr = angle->end(); *endIndexPtr = angle->start(); + angle = angle->next(); } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone); if (leftSegment->verb() >= SkPath::kQuad_Verb) { const int tIndex = *tIndexPtr; @@ -1972,6 +2687,14 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort return leftSegment; } +int SkOpSegment::firstActive(int tIndex) const { + while (fTs[tIndex].fTiny) { + SkASSERT(!isCanceled(tIndex)); + ++tIndex; + } + return tIndex; +} + // FIXME: not crazy about this // when the intersections are performed, the other index is into an // incomplete array. As the array grows, the indices become incorrect @@ -2005,14 +2728,21 @@ void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, boo fXor = evenOdd; fPts = pts; fVerb = verb; + fLoop = fSmall = fTiny = false; } -void SkOpSegment::initWinding(int start, int end) { +void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) { int local = spanSign(start, end); - int oppLocal = oppSign(start, end); - (void) markAndChaseWinding(start, end, local, oppLocal); + if (angleIncludeType == SkOpAngle::kBinarySingle) { + int oppLocal = oppSign(start, end); + (void) markAndChaseWinding(start, end, local, oppLocal); // OPTIMIZATION: the reverse mark and chase could skip the first marking - (void) markAndChaseWinding(end, start, local, oppLocal); + (void) markAndChaseWinding(end, start, local, oppLocal); + } else { + (void) markAndChaseWinding(start, end, local); + // OPTIMIZATION: the reverse mark and chase could skip the first marking + (void) markAndChaseWinding(end, start, local); + } } /* @@ -2034,13 +2764,9 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding, hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); #endif - if (!winding) { - winding = dx < 0 ? windVal : -windVal; - } else if (winding * dx < 0) { - int sideWind = winding + (dx < 0 ? windVal : -windVal); - if (abs(winding) < abs(sideWind)) { - winding = sideWind; - } + int sideWind = winding + (dx < 0 ? windVal : -windVal); + if (abs(winding) < abs(sideWind)) { + winding = sideWind; } #if DEBUG_WINDING_AT_T SkDebugf(" winding=%d\n", winding); @@ -2061,11 +2787,29 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc (void) markAndChaseWinding(end, start, winding, oppWind); } +bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const { + if (!baseAngle->inLoop()) { + return false; + } + int index = *indexPtr; + int froIndex = fTs[index].fFromAngleIndex; + int toIndex = fTs[index].fToAngleIndex; + while (++index < spanCount) { + int nextFro = fTs[index].fFromAngleIndex; + int nextTo = fTs[index].fToAngleIndex; + if (froIndex != nextFro || toIndex != nextTo) { + break; + } + } + *indexPtr = index; + return true; +} + // OPTIMIZE: successive calls could start were the last leaves off // or calls could specialize to walk forwards or backwards bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const { - size_t tCount = fTs.count(); - for (size_t index = 0; index < tCount; ++index) { + int tCount = fTs.count(); + for (int index = 0; index < tCount; ++index) { const SkOpSpan& span = fTs[index]; if (approximately_zero(startT - span.fT) && pt == span.fPt) { return false; @@ -2075,6 +2819,7 @@ bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const { } bool SkOpSegment::isSimple(int end) const { +#if 1 int count = fTs.count(); if (count == 2) { return true; @@ -2087,6 +2832,19 @@ bool SkOpSegment::isSimple(int end) const { return !approximately_greater_than_one(fTs[count - 2].fT); } return false; +#else + // OPTIMIZE: code could be rejiggered to use this simpler test. To make this work, a little + // more logic is required to ignore the dangling canceled out spans + const SkOpSpan& span = fTs[end]; + return span.fFromAngleIndex < 0 && span.fToAngleIndex < 0; +#endif +} + +bool SkOpSegment::isSmall(const SkOpAngle* angle) const { + int start = angle->start(); + int end = angle->end(); + const SkOpSpan& mSpan = fTs[SkMin32(start, end)]; + return mSpan.fSmall; } bool SkOpSegment::isTiny(const SkOpAngle* angle) const { @@ -2103,13 +2861,12 @@ bool SkOpSegment::isTiny(int index) const { // look pair of active edges going away from coincident edge // one of them should be the continuation of other // if both are active, look to see if they both the connect to another coincident pair -// if one at least one is a line, then make the pair coincident +// if at least one is a line, then make the pair coincident // if neither is a line, test for coincidence -bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step, - bool cancel) { +bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel) { int otherTIndex = other->findT(otherT, this); int next = other->nextExactSpan(otherTIndex, step); - int otherMin = SkTMin(otherTIndex, next); + int otherMin = SkMin32(otherTIndex, next); int otherWind = other->span(otherMin).fWindValue; if (otherWind == 0) { return false; @@ -2171,7 +2928,7 @@ SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) { return last; } -SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) { +SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) { int index = angle->start(); int endIndex = angle->end(); int step = SkSign32(endIndex - index); @@ -2189,6 +2946,22 @@ SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int win return last; } +SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) { + int min = SkMin32(index, endIndex); + int step = SkSign32(endIndex - index); + markWinding(min, winding); + SkOpSpan* last; + SkOpSegment* other = this; + while ((other = other->nextChase(&index, step, &min, &last))) { + if (other->fTs[min].fWindSum != SK_MinS32) { + SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop); + return NULL; + } + other->markWinding(min, winding); + } + return last; +} + SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) { int min = SkMin32(index, endIndex); int step = SkSign32(endIndex - index); @@ -2265,6 +3038,7 @@ void SkOpSegment::markDone(int index, int winding) { do { markOneDone(__FUNCTION__, index, winding); } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); + debugValidate(); } void SkOpSegment::markDoneBinary(int index) { @@ -2276,6 +3050,7 @@ void SkOpSegment::markDoneBinary(int index) { do { markOneDoneBinary(__FUNCTION__, index); } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); + debugValidate(); } void SkOpSegment::markDoneUnary(int index) { @@ -2287,11 +3062,12 @@ void SkOpSegment::markDoneUnary(int index) { do { markOneDoneUnary(__FUNCTION__, index); } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); + debugValidate(); } void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) { SkOpSpan* span = markOneWinding(funName, tIndex, winding); - if (!span) { + if (!span || span->fDone) { return; } span->fDone = true; @@ -2303,6 +3079,7 @@ void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) { if (!span) { return; } + SkASSERT(!span->fDone); span->fDone = true; fDoneSpans++; } @@ -2312,13 +3089,17 @@ void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) { if (!span) { return; } + if (span->fWindSum == SK_MinS32) { + SkDebugf("%s uncomputed\n", __FUNCTION__); + } + SkASSERT(!span->fDone); span->fDone = true; fDoneSpans++; } SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) { SkOpSpan& span = fTs[tIndex]; - if (span.fDone) { + if (span.fDone && !span.fSmall) { return NULL; } #if DEBUG_MARK_DONE @@ -2345,6 +3126,7 @@ SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding); SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum); span.fOppSum = oppWinding; + debugValidate(); return &span; } @@ -2447,10 +3229,12 @@ void SkOpSegment::markUnsortable(int start, int end) { span->fUnsortableEnd = true; } if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) { + debugValidate(); return; } span->fDone = true; fDoneSpans++; + debugValidate(); } void SkOpSegment::markWinding(int index, int winding) { @@ -2464,6 +3248,7 @@ void SkOpSegment::markWinding(int index, int winding) { do { markOneWinding(__FUNCTION__, index, winding); } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); + debugValidate(); } void SkOpSegment::markWinding(int index, int winding, int oppWinding) { @@ -2477,13 +3262,29 @@ void SkOpSegment::markWinding(int index, int winding, int oppWinding) { do { markOneWinding(__FUNCTION__, index, winding, oppWinding); } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT)); + debugValidate(); } void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) { int nextDoorWind = SK_MaxS32; int nextOppWind = SK_MaxS32; + // prefer exact matches if (tIndex > 0) { const SkOpSpan& below = fTs[tIndex - 1]; + if (below.fT == t) { + nextDoorWind = below.fWindValue; + nextOppWind = below.fOppValue; + } + } + if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) { + const SkOpSpan& above = fTs[tIndex + 1]; + if (above.fT == t) { + nextDoorWind = above.fWindValue; + nextOppWind = above.fOppValue; + } + } + if (nextDoorWind == SK_MaxS32 && tIndex > 0) { + const SkOpSpan& below = fTs[tIndex - 1]; if (approximately_negative(t - below.fT)) { nextDoorWind = below.fWindValue; nextOppWind = below.fOppValue; @@ -2637,70 +3438,98 @@ void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum); } -// This marks all spans unsortable so that this info is available for early -// exclusion in find top and others. This could be optimized to only mark -// adjacent spans that unsortable. However, this makes it difficult to later -// determine starting points for edge detection in find top and the like. -bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles, - SkTArray<SkOpAngle*, true>* angleList, - SortAngleKind orderKind) { - bool sortable = true; - int angleCount = angles.count(); - int angleIndex; - for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - const SkOpAngle& angle = angles[angleIndex]; - angleList->push_back(const_cast<SkOpAngle*>(&angle)); +void SkOpSegment::sortAngles() { + int spanCount = fTs.count(); + if (spanCount <= 2) { + return; + } + int index = 0; + do { + int fromIndex = fTs[index].fFromAngleIndex; + int toIndex = fTs[index].fToAngleIndex; + if (fromIndex < 0 && toIndex < 0) { + index += 1; + continue; + } + SkOpAngle* baseAngle = NULL; + if (fromIndex >= 0) { + baseAngle = &this->angle(fromIndex); + if (inLoop(baseAngle, spanCount, &index)) { + continue; + } + } #if DEBUG_ANGLE - (*(angleList->end() - 1))->setID(angleIndex); + bool wroteAfterHeader = false; #endif - sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind - && angle.unorderable())); - } - if (sortable) { - SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1); - for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind - && angles[angleIndex].unorderable())) { - sortable = false; - break; + if (toIndex >= 0) { + SkOpAngle* toAngle = &this->angle(toIndex); + if (!baseAngle) { + baseAngle = toAngle; + if (inLoop(baseAngle, spanCount, &index)) { + continue; + } + } else { + SkDEBUGCODE(int newIndex = index); + SkASSERT(!inLoop(baseAngle, spanCount, &newIndex) && newIndex == index); +#if DEBUG_ANGLE + SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT, + index); + wroteAfterHeader = true; +#endif + baseAngle->insert(toAngle); } } - } - if (!sortable) { - for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - const SkOpAngle& angle = angles[angleIndex]; - angle.segment()->markUnsortable(angle.start(), angle.end()); - } - } - return sortable; -} - -// set segments to unsortable if angle is unsortable, but do not set all angles -// note that for a simple 4 way crossing, two of the edges may be orderable even though -// two edges are too short to be orderable. -// perhaps some classes of unsortable angles should make all shared angles unsortable, but -// simple lines that have tiny crossings are always sortable on the large ends -// OPTIMIZATION: check earlier when angles are added to input if any are unsortable -// may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd -// solely for the purpose of short-circuiting future angle building around this center -bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles, - SkTArray<SkOpAngle*, true>* angleList) { - int angleCount = angles.count(); - int angleIndex; - for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - const SkOpAngle& angle = angles[angleIndex]; - if (angle.unsortable()) { - return false; - } - angleList->push_back(const_cast<SkOpAngle*>(&angle)); + int nextFrom, nextTo; + int firstIndex = index; + do { + SkOpSpan& span = fTs[index]; + SkOpSegment* other = span.fOther; + SkOpSpan& oSpan = other->fTs[span.fOtherIndex]; + int otherAngleIndex = oSpan.fFromAngleIndex; + if (otherAngleIndex >= 0) { #if DEBUG_ANGLE - (*(angleList->end() - 1))->setID(angleIndex); + if (!wroteAfterHeader) { + SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT, + index); + wroteAfterHeader = true; + } #endif - } - SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1); - // at this point angles are sorted but individually may not be orderable - // this means that only adjcent orderable segments may transfer winding - return true; + baseAngle->insert(&other->angle(otherAngleIndex)); + } + otherAngleIndex = oSpan.fToAngleIndex; + if (otherAngleIndex >= 0) { +#if DEBUG_ANGLE + if (!wroteAfterHeader) { + SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT, + index); + wroteAfterHeader = true; + } +#endif + baseAngle->insert(&other->angle(otherAngleIndex)); + } + if (++index == spanCount) { + break; + } + nextFrom = fTs[index].fFromAngleIndex; + nextTo = fTs[index].fToAngleIndex; + } while (fromIndex == nextFrom && toIndex == nextTo); + if (baseAngle && baseAngle->loopCount() == 1) { + index = firstIndex; + do { + SkOpSpan& span = fTs[index]; + span.fFromAngleIndex = span.fToAngleIndex = -1; + if (++index == spanCount) { + break; + } + nextFrom = fTs[index].fFromAngleIndex; + nextTo = fTs[index].fToAngleIndex; + } while (fromIndex == nextFrom && toIndex == nextTo); + baseAngle = NULL; + } +#if DEBUG_SORT + SkASSERT(!baseAngle || baseAngle->loopCount() > 1); +#endif + } while (index < spanCount); } // return true if midpoints were computed @@ -2802,8 +3631,8 @@ void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoin } void SkOpSegment::undoneSpan(int* start, int* end) { - size_t tCount = fTs.count(); - size_t index; + int tCount = fTs.count(); + int index; for (index = 0; index < tCount; ++index) { if (!fTs[index].fDone) { break; @@ -2947,382 +3776,3 @@ void SkOpSegment::zeroSpan(SkOpSpan* span) { span->fDone = true; ++fDoneSpans; } - -#if DEBUG_SWAP_TOP -bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const { - if (fVerb != SkPath::kCubic_Verb) { - return false; - } - SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); - return dst.controlsContainedByEnds(); -} -#endif - -#if DEBUG_CONCIDENT -// SkASSERT if pair has not already been added -void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const { - 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 SkOpSegment::debugShowTs(const char* prefix) const { - SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID); - int lastWind = -1; - int lastOpp = -1; - double lastT = -1; - int i; - for (i = 0; i < fTs.count(); ++i) { - bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue - || lastOpp != fTs[i].fOppValue; - if (change && lastWind >= 0) { - SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", - lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); - } - if (change) { - SkDebugf(" [o=%d", fTs[i].fOther->fID); - lastWind = fTs[i].fWindValue; - lastOpp = fTs[i].fOppValue; - lastT = fTs[i].fT; - } else { - SkDebugf(",%d", fTs[i].fOther->fID); - } - } - if (i <= 0) { - return; - } - SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", - lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); - if (fOperand) { - SkDebugf(" operand"); - } - if (done()) { - SkDebugf(" done"); - } - SkDebugf("\n"); -} -#endif - -#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY -void SkOpSegment::debugShowActiveSpans() const { - debugValidate(); - if (done()) { - return; - } -#if DEBUG_ACTIVE_SPANS_SHORT_FORM - int lastId = -1; - double lastT = -1; -#endif - for (int i = 0; i < fTs.count(); ++i) { - if (fTs[i].fDone) { - continue; - } - SkASSERT(i < fTs.count() - 1); -#if DEBUG_ACTIVE_SPANS_SHORT_FORM - if (lastId == fID && lastT == fTs[i].fT) { - continue; - } - lastId = fID; - lastT = fTs[i].fT; -#endif - SkDebugf("%s id=%d", __FUNCTION__, fID); - SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); - for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { - SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); - } - const SkOpSpan* span = &fTs[i]; - SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span)); - int iEnd = i + 1; - while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) { - ++iEnd; - } - SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT); - const SkOpSegment* other = fTs[i].fOther; - SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", - other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); - if (fTs[i].fWindSum == SK_MinS32) { - SkDebugf("?"); - } else { - SkDebugf("%d", fTs[i].fWindSum); - } - SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue); - } -} -#endif - - -#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE -void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) { - const SkPoint& pt = xyAtT(&span); - SkDebugf("%s id=%d", fun, fID); - SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); - for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { - SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); - } - SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> - fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); - SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=", - span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, - (&span)[1].fT, winding); - if (span.fWindSum == SK_MinS32) { - SkDebugf("?"); - } else { - SkDebugf("%d", span.fWindSum); - } - SkDebugf(" windValue=%d\n", span.fWindValue); -} - -void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, - int oppWinding) { - const SkPoint& pt = xyAtT(&span); - SkDebugf("%s id=%d", fun, fID); - SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); - for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { - SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); - } - SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> - fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); - SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=", - span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, - (&span)[1].fT, winding, oppWinding); - if (span.fOppSum == SK_MinS32) { - SkDebugf("?"); - } else { - SkDebugf("%d", span.fOppSum); - } - SkDebugf(" windSum="); - if (span.fWindSum == SK_MinS32) { - SkDebugf("?"); - } else { - SkDebugf("%d", span.fWindSum); - } - SkDebugf(" windValue=%d\n", span.fWindValue); -} -#endif - -#if DEBUG_SORT || DEBUG_SWAP_TOP -void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, - int first, const int contourWinding, - const int oppContourWinding, bool sortable) const { - if (--SkPathOpsDebug::gSortCount < 0) { - return; - } - if (!sortable) { - if (angles.count() == 0) { - return; - } - if (first < 0) { - first = 0; - } - } - SkASSERT(angles[first]->segment() == this); - SkASSERT(!sortable || angles.count() > 1); - int lastSum = contourWinding; - int oppLastSum = oppContourWinding; - const SkOpAngle* firstAngle = angles[first]; - int windSum = lastSum - spanSign(firstAngle); - int oppoSign = oppSign(firstAngle); - int oppWindSum = oppLastSum - oppoSign; - #define WIND_AS_STRING(x) char x##Str[12]; \ - if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \ - else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x) - WIND_AS_STRING(contourWinding); - WIND_AS_STRING(oppContourWinding); - SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__, - contourWindingStr, oppContourWindingStr, spanSign(angles[first])); - int index = first; - bool firstTime = true; - do { - const SkOpAngle& angle = *angles[index]; - const SkOpSegment& segment = *angle.segment(); - int start = angle.start(); - int end = angle.end(); - const SkOpSpan& sSpan = segment.fTs[start]; - const SkOpSpan& eSpan = segment.fTs[end]; - const SkOpSpan& mSpan = segment.fTs[SkMin32(start, end)]; - bool opp = segment.fOperand ^ fOperand; - if (!firstTime) { - oppoSign = segment.oppSign(&angle); - if (opp) { - oppLastSum = oppWindSum; - oppWindSum -= segment.spanSign(&angle); - if (oppoSign) { - lastSum = windSum; - windSum -= oppoSign; - } - } else { - lastSum = windSum; - windSum -= segment.spanSign(&angle); - if (oppoSign) { - oppLastSum = oppWindSum; - oppWindSum -= oppoSign; - } - } - } - SkDebugf("%s [%d] %s", __FUNCTION__, index, - angle.unsortable() ? "*** UNSORTABLE *** " : ""); - #if DEBUG_SORT_COMPACT - SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)", - segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)], - start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, - segment.xAtT(&eSpan), segment.yAtT(&eSpan)); - #else - switch (segment.fVerb) { - case SkPath::kLine_Verb: - SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts)); - break; - case SkPath::kQuad_Verb: - SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts)); - break; - case SkPath::kCubic_Verb: - SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts)); - break; - default: - SkASSERT(0); - } - SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT); - #endif - SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue); - SkPathOpsDebug::WindingPrintf(mSpan.fWindSum); - int last, wind; - if (opp) { - last = oppLastSum; - wind = oppWindSum; - } else { - last = lastSum; - wind = windSum; - } - bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind) - && UseInnerWinding(last, wind); - WIND_AS_STRING(last); - WIND_AS_STRING(wind); - WIND_AS_STRING(lastSum); - WIND_AS_STRING(oppLastSum); - WIND_AS_STRING(windSum); - WIND_AS_STRING(oppWindSum); - #undef WIND_AS_STRING - if (!oppoSign) { - SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr); - } else { - SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr, - opp ? windSumStr : oppWindSumStr); - } - SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n", - mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp); - ++index; - if (index == angles.count()) { - index = 0; - } - if (firstTime) { - firstTime = false; - } - } while (index != first); -} - -void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, - int first, bool sortable) { - if (!sortable) { - if (angles.count() == 0) { - return; - } - if (first < 0) { - first = 0; - } - } - const SkOpAngle* firstAngle = angles[first]; - const SkOpSegment* segment = firstAngle->segment(); - int winding = segment->updateWinding(firstAngle); - int oppWinding = segment->updateOppWinding(firstAngle); - debugShowSort(fun, angles, first, winding, oppWinding, sortable); -} - -#endif - -#if DEBUG_SHOW_WINDING -int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const { - if (!(1 << fID & ofInterest)) { - return 0; - } - int sum = 0; - SkTArray<char, true> slots(slotCount * 2); - memset(slots.begin(), ' ', slotCount * 2); - for (int i = 0; i < fTs.count(); ++i) { - // if (!(1 << fTs[i].fOther->fID & ofInterest)) { - // continue; - // } - sum += fTs[i].fWindValue; - slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue); - sum += fTs[i].fOppValue; - slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue); - } - SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount, - slots.begin() + slotCount); - return sum; -} -#endif - -void SkOpSegment::debugValidate() const { -#if DEBUG_VALIDATE - int count = fTs.count(); - SkASSERT(count >= 2); - SkASSERT(fTs[0].fT == 0); - SkASSERT(fTs[count - 1].fT == 1); - int done = 0; - double t = -1; - for (int i = 0; i < count; ++i) { - const SkOpSpan& span = fTs[i]; - SkASSERT(t <= span.fT); - t = span.fT; - int otherIndex = span.fOtherIndex; - const SkOpSegment* other = span.fOther; - const SkOpSpan& otherSpan = other->fTs[otherIndex]; - SkASSERT(otherSpan.fPt == span.fPt); - SkASSERT(otherSpan.fOtherT == t); - SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]); - done += span.fDone; - } - SkASSERT(done == fDoneSpans); -#endif -} - -#ifdef SK_DEBUG -void SkOpSegment::dumpPts() const { - int last = SkPathOpsVerbToPoints(fVerb); - SkDebugf("{{"); - int index = 0; - do { - SkDPoint::dump(fPts[index]); - SkDebugf(", "); - } while (++index < last); - SkDPoint::dump(fPts[index]); - SkDebugf("}}\n"); -} - -void SkOpSegment::dumpDPts() const { - int count = SkPathOpsVerbToPoints(fVerb); - SkDebugf("{{"); - int index = 0; - do { - SkDPoint dPt = {fPts[index].fX, fPts[index].fY}; - dPt.dump(); - if (index != count) { - SkDebugf(", "); - } - } while (++index <= count); - SkDebugf("}}\n"); -} - -void SkOpSegment::dumpSpans() const { - int count = this->count(); - for (int index = 0; index < count; ++index) { - const SkOpSpan& span = this->span(index); - SkDebugf("[%d] ", index); - span.dump(); - } -} -#endif diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 79d83b1155..54c1892d1b 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -19,7 +19,7 @@ class SkPathWriter; class SkOpSegment { public: SkOpSegment() { -#ifdef SK_DEBUG +#if defined(SK_DEBUG) || !FORCE_RELEASE fID = ++SkPathOpsDebug::gSegmentID; #endif } @@ -28,6 +28,12 @@ public: return fBounds.fTop < rh.fBounds.fTop; } + // FIXME: add some template or macro to avoid casting + SkOpAngle& angle(int index) { + const SkOpAngle& cAngle = (const_cast<const SkOpSegment*>(this))->angle(index); + return const_cast<SkOpAngle&>(cAngle); + } + const SkPathOpsBounds& bounds() const { return fBounds; } @@ -42,6 +48,8 @@ public: return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; } + void constructLine(SkPoint shortLine[2]); + int count() const { return fTs.count(); } @@ -59,7 +67,6 @@ public: return done(SkMin32(angle->start(), angle->end())); } - // used only by partial coincidence detection SkDPoint dPtAtT(double mid) const { return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); } @@ -72,6 +79,14 @@ public: return dxdy(index).fY; } + bool hasSmall() const { + return fSmall; + } + + bool hasTiny() const { + return fTiny; + } + bool intersected() const { return fTs.count() > 0; } @@ -131,11 +146,12 @@ public: return fTs[lesser].fOppValue; } - const SkOpSegment* other(int index) const { - return fTs[index].fOther; +#if DEBUG_VALIDATE + bool oppXor() const { + return fOppXor; } +#endif - // was used only by right angle winding finding SkPoint ptAtT(double mid) const { return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); } @@ -160,11 +176,23 @@ public: *sumWinding -= deltaSum; } - // OPTIMIZATION: mark as debugging only if used solely by tests const SkOpSpan& span(int tIndex) const { return fTs[tIndex]; } + const SkOpAngle* spanToAngle(int tStart, int tEnd) const { + SkASSERT(tStart != tEnd); + const SkOpSpan& span = fTs[tStart]; + int index = tStart < tEnd ? span.fToAngleIndex : span.fFromAngleIndex; + return index >= 0 ? &angle(index) : NULL; + } + + // FIXME: create some sort of macro or template that avoids casting + SkOpAngle* spanToAngle(int tStart, int tEnd) { + const SkOpAngle* cAngle = (const_cast<const SkOpSegment*>(this))->spanToAngle(tStart, tEnd); + return const_cast<SkOpAngle*>(cAngle); + } + // OPTIMIZATION: mark as debugging only if used solely by tests const SkTDArray<SkOpSpan>& spans() const { return fTs; @@ -217,6 +245,12 @@ public: } #endif +#if DEBUG_VALIDATE + bool _xor() const { // FIXME: used only by SkOpAngle::debugValidateLoop() + return fXor; + } +#endif + const SkPoint& xyAtT(const SkOpSpan* span) const { return span->fPt; } @@ -231,44 +265,56 @@ public: } #endif - bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles); + const SkOpAngle* activeAngle(int index, int* start, int* end, bool* done, + bool* sortable) const; SkPoint activeLeftTop(bool onlySortable, int* firstT) const; bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op); bool activeWinding(int index, int endIndex); void addCubic(const SkPoint pts[4], bool operand, bool evenOdd); void addCurveTo(int start, int end, SkPathWriter* path, bool active) const; + void addEndSpan(int endIndex); void addLine(const SkPoint pts[2], bool operand, bool evenOdd); void addOtherT(int index, double otherT, int otherIndex); void addQuad(const SkPoint pts[3], bool operand, bool evenOdd); - int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT); + void addSimpleAngle(int endIndex); + int addSelfT(const SkPoint& pt, double newT); + void addStartSpan(int endIndex); int addT(SkOpSegment* other, const SkPoint& pt, double newT); void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT, - SkOpSegment* other); - void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt); + SkOpSegment* other); + const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, + const SkPoint& pt); + bool alignSpan(int index, double thisT, const SkPoint& thisPt); + void alignSpanState(int start, int end); + const SkOpAngle& angle(int index) const; bool betweenTs(int lesser, double testT, int greater) const; + bool calcAngles(); + void checkDuplicates(); void checkEnds(); + void checkMultiples(); + void checkSmall(); bool checkSmall(int index) const; void checkTiny(); - int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType, - SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted); + int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType); int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const; bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const; SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, - bool* unsortable, SkPathOp op, const int xorMiMask, - const int xorSuMask); + bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask); SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, bool* unsortable); SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); + int findExactT(double t, const SkOpSegment* ) const; int findT(double t, const SkOpSegment* ) const; - SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable); + SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable); void fixOtherTIndex(); - void initWinding(int start, int end); + void initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType); void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx); bool isMissing(double startT, const SkPoint& pt) const; + bool isSmall(const SkOpAngle* angle) const; bool isTiny(const SkOpAngle* angle) const; bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel); SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); @@ -283,44 +329,44 @@ public: int nextSpan(int from, int step) const; void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); - enum SortAngleKind { - kMustBeOrdered_SortAngleKind, // required for winding calc - kMayBeUnordered_SortAngleKind // ok for find top - }; - static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with - SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2 - SortAngleKind ); - static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles, - SkTArray<SkOpAngle*, true>* angleList); + void sortAngles(); bool subDivide(int start, int end, SkPoint edge[4]) const; bool subDivide(int start, int end, SkDCubic* result) const; void undoneSpan(int* start, int* end); int updateOppWindingReverse(const SkOpAngle* angle) const; int updateWindingReverse(const SkOpAngle* angle) const; static bool UseInnerWinding(int outerWinding, int innerWinding); + static bool UseInnerWindingReverse(int outerWinding, int innerWinding); int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; int windSum(const SkOpAngle* angle) const; - -#ifdef SK_DEBUG +// available for testing only +#if DEBUG_VALIDATE + bool debugContains(const SkOpAngle* ) const; +#endif +#if defined(SK_DEBUG) || !FORCE_RELEASE int debugID() const { return fID; } +#else + int debugID() const { + return -1; + } #endif #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void debugShowActiveSpans() const; #endif -#if DEBUG_SORT || DEBUG_SWAP_TOP - void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, - const int contourWinding, const int oppContourWinding, bool sortable) const; - void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, - bool sortable); -#endif #if DEBUG_CONCIDENT void debugShowTs(const char* prefix) const; #endif #if DEBUG_SHOW_WINDING int debugShowWindingValues(int slotCount, int ofInterest) const; #endif + void debugValidate() const; + // available to testing only + void dumpAngles() const; + void dumpContour(int firstID, int lastID) const; + void dumpPts() const; + void dumpSpans() const; private: struct MissingSpan { @@ -332,40 +378,55 @@ private: SkPoint fPt; }; - bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles); - bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles); + const SkOpAngle* activeAngleInner(int index, int* start, int* end, bool* done, + bool* sortable) const; + const SkOpAngle* activeAngleOther(int index, int* start, int* end, bool* done, + bool* sortable) const; bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, - int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, - int* oppMaxWinding, int* oppSumWinding); - bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding); - void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const; + int* sumMiWinding, int* sumSuWinding); + bool activeWinding(int index, int endIndex, int* sumWinding); void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + int addSingletonAngleDown(int start, SkOpSegment** otherPtr); + int addSingletonAngleUp(int start, SkOpSegment** otherPtr); + SkOpAngle* addSingletonAngles(int start, int step); void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, const SkPoint& oPt); - void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const; bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const; - bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const; - void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const; void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index, SkTArray<SkPoint, true>* outsideTs); void bumpCoincidentOther(const SkOpSpan& oTest, int* index, SkTArray<SkPoint, true>* outsideTs); bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); + bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts); + void checkLinks(const SkOpSpan* , + SkTArray<MissingSpan, true>* missingSpans) const; + static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan, + const SkOpSpan* oFirst, const SkOpSpan* oLast, + const SkOpSpan** missingPtr, + SkTArray<MissingSpan, true>* missingSpans); + int checkSetAngle(int tIndex) const; + void checkSmallCoincidence(const SkOpSpan& span, SkTArray<MissingSpan, true>* ); bool clockwise(int tStart, int tEnd) const; static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); bool decrementSpan(SkOpSpan* span); - int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end); + int findEndSpan(int endIndex) const; + int findStartSpan(int startIndex) const; + int firstActive(int tIndex) const; + const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const; void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); + bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const; bool isSimple(int end) const; bool isTiny(int index) const; + const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const; void matchWindingValue(int tIndex, double t, bool borrowWind); SkOpSpan* markAndChaseDone(int index, int endIndex, int winding); SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding); - SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding); + SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding); + SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding); SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding); SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle); void markDoneBinary(int index, int winding, int oppWinding); @@ -380,10 +441,21 @@ private: void markWinding(int index, int winding, int oppWinding); void markUnsortable(int start, int end); bool monotonicInY(int tStart, int tEnd) const; + + bool multipleEnds() const { + return fTs[count() - 2].fT == 1; + } + + bool multipleStarts() const { + return fTs[1].fT == 0; + } + bool multipleSpans(int end) const; SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); int nextExactSpan(int from, int step) const; bool serpentine(int tStart, int tEnd) const; + void setFromAngleIndex(int endIndex, int angleIndex); + void setToAngleIndex(int endIndex, int angleIndex); void setUpWindings(int index, int endIndex, int* sumMiWinding, int* maxWinding, int* sumWinding); void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; @@ -395,7 +467,6 @@ private: int updateWinding(int index, int endIndex) const; int updateWinding(const SkOpAngle* angle) const; int updateWindingReverse(int index, int endIndex) const; - static bool UseInnerWindingReverse(int outerWinding, int innerWinding); SkOpSpan* verifyOneWinding(const char* funName, int tIndex); SkOpSpan* verifyOneWindingU(const char* funName, int tIndex); @@ -412,8 +483,12 @@ private: #if DEBUG_SWAP_TOP bool controlsContainedByEnds(int tStart, int tEnd) const; #endif + void debugAddAngle(int start, int end); #if DEBUG_CONCIDENT - void debugAddTPair(double t, const SkOpSegment& other, double otherT) const; + void debugAddTPair(double t, const SkOpSegment& other, double otherT) const; +#endif +#if DEBUG_ANGLE + void debugCheckPointsEqualish(int tStart, int tEnd) const; #endif #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding); @@ -424,27 +499,37 @@ private: return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; } #endif - void debugValidate() const; -#ifdef SK_DEBUG - void dumpPts() const; + // available to testing only + void debugConstruct(); + void debugConstructCubic(SkPoint shortQuad[4]); + void debugConstructLine(SkPoint shortQuad[2]); + void debugConstructQuad(SkPoint shortQuad[3]); + void debugReset(); void dumpDPts() const; - void dumpSpans() const; -#endif + void dumpSpan(int index) const; const SkPoint* fPts; SkPathOpsBounds fBounds; // FIXME: can't convert to SkTArray because it uses insert - SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1) + SkTDArray<SkOpSpan> fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1 +// FIXME: replace both with bucket storage that allows direct immovable pointers to angles + SkTArray<SkOpAngle, true> fSingletonAngles; // 0 or 2 -- allocated for singletons + SkTArray<SkOpAngle, true> fAngles; // 0 or 2+ -- (number of non-zero spans) * 2 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value int fDoneSpans; // quick check that segment is finished // OPTIMIZATION: force the following to be byte-sized SkPath::Verb fVerb; + bool fLoop; // set if cubic intersects itself bool fOperand; bool fXor; // set if original contour had even-odd fill bool fOppXor; // set if opposite operand had even-odd fill -#ifdef SK_DEBUG + bool fSmall; // set if some span is small + bool fTiny; // set if some span is tiny +#if defined(SK_DEBUG) || !FORCE_RELEASE int fID; #endif + + friend class PathOpsSegmentTester; }; #endif diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index 81ede1c9ab..2fe0b611b6 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -17,20 +17,24 @@ struct SkOpSpan { double fT; double fOtherT; // value at fOther[fOtherIndex].fT int fOtherIndex; // can't be used during intersection + int fFromAngleIndex; // (if t > 0) index into segment's angle array going negative in t + int fToAngleIndex; // (if t < 1) index into segment's angle array going positive in t int fWindSum; // accumulated from contours surrounding this one. int fOppSum; // for binary operators: the opposite winding sum int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here + bool fChased; // set after span has been added to chase array bool fDone; // if set, this span to next higher T has been processed + bool fLoop; // set when a cubic loops back to this point + bool fSmall; // if set, consecutive points are almost equal + bool fTiny; // if set, consecutive points are equal but consecutive ts are not precisely equal bool fUnsortableStart; // set when start is part of an unsortable pair bool fUnsortableEnd; // set when end is part of an unsortable pair - bool fSmall; // if set, consecutive points are almost equal - bool fTiny; // if set, span may still be considered once for edge following - bool fLoop; // set when a cubic loops back to this point -#ifdef SK_DEBUG + // available to testing only + const SkOpSegment* debugToSegment(ptrdiff_t* ) const; void dump() const; -#endif + void dumpOne() const; }; #endif diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index c48a7eef68..f34148390c 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -111,75 +111,62 @@ SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, i return NULL; } -SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) { - while (chase.count()) { +SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) { + while (chase->count()) { SkOpSpan* span; - chase.pop(&span); + chase->pop(&span); const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); SkOpSegment* segment = backPtr.fOther; - tIndex = backPtr.fOtherIndex; - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; - int done = 0; - if (segment->activeAngle(tIndex, &done, &angles)) { - SkOpAngle* last = angles.end() - 1; - tIndex = last->start(); - endIndex = last->end(); - #if TRY_ROTATE - *chase.insert(0) = span; - #else - *chase.append() = span; - #endif + *tIndex = backPtr.fOtherIndex; + bool sortable = true; + bool done = true; + *endIndex = -1; + if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done, + &sortable)) { + *tIndex = last->start(); + *endIndex = last->end(); + #if TRY_ROTATE + *chase->insert(0) = span; + #else + *chase->append() = span; + #endif return last->segment(); } - if (done == angles.count()) { + if (done) { continue; } - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SkOpSegment::SortAngles(angles, &sorted, - SkOpSegment::kMayBeUnordered_SortAngleKind); - int angleCount = sorted.count(); -#if DEBUG_SORT - sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable); -#endif if (!sortable) { continue; } // find first angle, initialize winding to computed fWindSum - int firstIndex = -1; - const SkOpAngle* angle; + const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); + const SkOpAngle* firstAngle; + SkDEBUGCODE(firstAngle = angle); + SkDEBUGCODE(bool loop = false); int winding; do { - angle = sorted[++firstIndex]; + angle = angle->next(); + SkASSERT(angle != firstAngle || !loop); + SkDEBUGCODE(loop |= angle == firstAngle); segment = angle->segment(); winding = segment->windSum(angle); } while (winding == SK_MinS32); int spanWinding = segment->spanSign(angle->start(), angle->end()); #if DEBUG_WINDING - SkDebugf("%s winding=%d spanWinding=%d\n", - __FUNCTION__, winding, spanWinding); + SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding); #endif // turn span winding into contour winding if (spanWinding * winding < 0) { winding += spanWinding; } - #if DEBUG_SORT - segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable); - #endif // we care about first sign and whether wind sum indicates this // edge is inside or outside. Maybe need to pass span winding // or first winding or something into this function? // advance to first undone angle, then return it and winding // (to set whether edges are active or not) - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; - angle = sorted[firstIndex]; - winding -= angle->segment()->spanSign(angle); - do { - SkASSERT(nextIndex != firstIndex); - if (nextIndex == angleCount) { - nextIndex = 0; - } - angle = sorted[nextIndex]; + firstAngle = angle; + winding -= firstAngle->segment()->spanSign(firstAngle); + while ((angle = angle->next()) != firstAngle) { segment = angle->segment(); int maxWinding = winding; winding -= segment->spanSign(angle); @@ -187,9 +174,9 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, segment->debugID(), maxWinding, winding, angle->sign()); #endif - tIndex = angle->start(); - endIndex = angle->end(); - int lesser = SkMin32(tIndex, endIndex); + *tIndex = angle->start(); + *endIndex = angle->end(); + int lesser = SkMin32(*tIndex, *endIndex); const SkOpSpan& nextSpan = segment->span(lesser); if (!nextSpan.fDone) { // FIXME: this be wrong? assign startWinding if edge is in @@ -201,8 +188,8 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) segment->markAndChaseWinding(angle, maxWinding, 0); break; } - } while (++nextIndex != lastIndex); - *chase.insert(0) = span; + } + *chase->insert(0) = span; return segment; } return NULL; @@ -221,6 +208,8 @@ static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool onlySortable) { SkOpSegment* result; + const SkOpSegment* lastTopStart = NULL; + int lastIndex = -1, lastEndIndex = -1; do { SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; int contourCount = contourList.count(); @@ -249,7 +238,16 @@ static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL return NULL; } *topLeft = bestXY; - result = topStart->findTop(index, endIndex, unsortable, onlySortable); + result = topStart->findTop(index, endIndex, unsortable); + if (!result) { + if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) { + *done = true; + return NULL; + } + lastTopStart = topStart; + lastIndex = *index; + lastEndIndex = *endIndex; + } } while (!result); if (result) { *unsortable = false; @@ -303,7 +301,7 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, const int index = *indexPtr; const int endIndex = *endIndexPtr; if (*firstContour) { - current->initWinding(index, endIndex); + current->initWinding(index, endIndex, angleIncludeType); *firstContour = false; return current; } @@ -313,9 +311,11 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, return current; } SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32); - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted); + const SkOpSpan& span = current->span(endIndex); + if ((index < endIndex ? span.fFromAngleIndex : span.fToAngleIndex) < 0) { + current->addSimpleAngle(endIndex); + } + sumWinding = current->computeSum(index, endIndex, angleIncludeType); if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { return current; } @@ -351,6 +351,25 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, return current; } +static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + if (!contour->calcAngles()) { + return false; + } + } + return true; +} + +static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->checkDuplicates(); + } +} + static void checkEnds(SkTArray<SkOpContour*, true>* contourList) { // it's hard to determine if the end of a cubic or conic nearly intersects another curve. // instead, look to see if the connecting curve intersected at that same end. @@ -361,6 +380,25 @@ static void checkEnds(SkTArray<SkOpContour*, true>* contourList) { } } +static void checkMultiples(SkTArray<SkOpContour*, true>* contourList) { + // it's hard to determine if the end of a cubic or conic nearly intersects another curve. + // instead, look to see if the connecting curve intersected at that same end. + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->checkMultiples(); + } +} + +// A small interval of a pair of curves may collapse to lines for each, triggering coincidence +static void checkSmall(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->checkSmall(); + } +} + // A tiny interval may indicate an undiscovered coincidence. Find and fix. static void checkTiny(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); @@ -386,6 +424,14 @@ static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) { } } +static void sortAngles(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->sortAngles(); + } +} + static void sortSegments(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { @@ -613,7 +659,7 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { #endif } -void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { +bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { #if DEBUG_SHOW_WINDING SkOpContour::debugShowWindingValues(contourList); #endif @@ -623,10 +669,18 @@ void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { #endif fixOtherTIndex(contourList); checkEnds(contourList); + checkMultiples(contourList); + checkDuplicates(contourList); checkTiny(contourList); + checkSmall(contourList); joinCoincidence(contourList); sortSegments(contourList); + if (!calcAngles(contourList)) { + return false; + } + sortAngles(contourList); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY DebugShowActiveSpans(*contourList); #endif + return true; } diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index afc751d130..9a558cf1b6 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -15,14 +15,14 @@ class SkPathWriter; void Assemble(const SkPathWriter& path, SkPathWriter* simple); // FIXME: find chase uses insert, so it can't be converted to SkTArray yet -SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex); +SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex); SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType , bool* firstContour, int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done); SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end); void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list, bool evenOdd, bool oppEvenOdd); -void HandleCoincidence(SkTArray<SkOpContour*, true>* , int ); +bool HandleCoincidence(SkTArray<SkOpContour*, true>* , int ); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList); diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 8e8ec47bf9..fda42a3140 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -455,16 +455,16 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d, if (t1 == 1 || t2 == 1) { align(3, 2, t1 == 1 ? &dst[0] : &dst[1]); } - if (precisely_subdivide_equal(dst[0].fX, a.fX)) { + if (AlmostBequalUlps(dst[0].fX, a.fX)) { dst[0].fX = a.fX; } - if (precisely_subdivide_equal(dst[0].fY, a.fY)) { + if (AlmostBequalUlps(dst[0].fY, a.fY)) { dst[0].fY = a.fY; } - if (precisely_subdivide_equal(dst[1].fX, d.fX)) { + if (AlmostBequalUlps(dst[1].fX, d.fX)) { dst[1].fX = d.fX; } - if (precisely_subdivide_equal(dst[1].fY, d.fY)) { + if (AlmostBequalUlps(dst[1].fY, d.fY)) { dst[1].fY = d.fY; } } @@ -508,16 +508,3 @@ SkDCubicPair SkDCubic::chopAt(double t) const { interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t); return dst; } - -#ifdef SK_DEBUG -void SkDCubic::dump() { - SkDebugf("{{"); - int index = 0; - do { - fPts[index].dump(); - SkDebugf(", "); - } while (++index < 3); - fPts[index].dump(); - SkDebugf("}}\n"); -} -#endif diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h index 973b76dfb2..500319607d 100644 --- a/src/pathops/SkPathOpsCubic.h +++ b/src/pathops/SkPathOpsCubic.h @@ -78,9 +78,9 @@ struct SkDCubic { void toQuadraticTs(double precision, SkTArray<double, true>* ts) const; SkDQuad toQuad() const; -#ifdef SK_DEBUG - void dump(); -#endif + // utilities callable by the user from the debugger when the implementation code is linked in + void dump() const; + void dumpNumber() const; }; #endif diff --git a/src/pathops/SkPathOpsCurve.h b/src/pathops/SkPathOpsCurve.h index 5d12cb811a..a7d3e81638 100644 --- a/src/pathops/SkPathOpsCurve.h +++ b/src/pathops/SkPathOpsCurve.h @@ -7,6 +7,7 @@ #ifndef SkPathOpsCurve_DEFINE #define SkPathOpsCurve_DEFINE +#include "SkIntersections.h" #include "SkPathOpsCubic.h" #include "SkPathOpsLine.h" #include "SkPathOpsQuad.h" @@ -149,4 +150,29 @@ static bool (* const CurveIsVertical[])(const SkPoint[], double , double) = { cubic_is_vertical }; +static void line_intersect_ray(const SkPoint a[2], const SkDLine& ray, SkIntersections* i) { + SkDLine line; + line.set(a); + i->intersectRay(line, ray); +} + +static void quad_intersect_ray(const SkPoint a[3], const SkDLine& ray, SkIntersections* i) { + SkDQuad quad; + quad.set(a); + i->intersectRay(quad, ray); +} + +static void cubic_intersect_ray(const SkPoint a[4], const SkDLine& ray, SkIntersections* i) { + SkDCubic cubic; + cubic.set(a); + i->intersectRay(cubic, ray); +} + +static void (* const CurveIntersectRay[])(const SkPoint[] , const SkDLine& , SkIntersections* ) = { + NULL, + line_intersect_ray, + quad_intersect_ray, + cubic_intersect_ray +}; + #endif diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index b68ab2acf8..4e4216310f 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -26,6 +26,17 @@ int SkPathOpsDebug::gSortCount; const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; #endif +bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpan *>& chaseArray, + const SkOpSpan* span) { + for (int index = 0; index < chaseArray.count(); ++index) { + const SkOpSpan* entry = chaseArray[index]; + if (entry == span) { + return true; + } + } + return false; +} + void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) { size_t len = strlen(str); bool num = false; @@ -81,81 +92,521 @@ void SkPathOpsDebug::BumpTestName(char* test) { } #endif +#if !DEBUG_SHOW_TEST_NAME // enable when building without extended test +void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) { +} +#endif + +#endif // defined SK_DEBUG || !FORCE_RELEASE + +#include "SkOpAngle.h" #include "SkOpSegment.h" -void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle, true>& angles) { - int count = angles.count(); - for (int index = 0; index < count; ++index) { - angles[index].dump(); - } +#if DEBUG_SORT +void SkOpAngle::debugLoop() const { + const SkOpAngle* first = this; + const SkOpAngle* next = this; + do { + next->debugOne(true); + SkDebugf("\n"); + next = next->fNext; + } while (next && next != first); } -void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle* , true>& angles) { - int count = angles.count(); - for (int index = 0; index < count; ++index) { - angles[index]->dump(); +void SkOpAngle::debugOne(bool functionHeader) const { +// fSegment->debugValidate(); + const SkOpSpan& mSpan = fSegment->span(SkMin32(fStart, fEnd)); + if (functionHeader) { + SkDebugf("%s ", __FUNCTION__); } -} -#endif // SK_DEBUG || !FORCE_RELEASE + SkDebugf("[%d", fSegment->debugID()); +#if DEBUG_ANGLE + SkDebugf("/%d", fID); +#endif + SkDebugf("] next="); + if (fNext) { + SkDebugf("%d", fNext->fSegment->debugID()); +#if DEBUG_ANGLE + SkDebugf("/%d", fNext->fID); +#endif + } else { + SkDebugf("?"); + } + SkDebugf(" sect=%d/%d ", fSectorStart, fSectorEnd); + SkDebugf(" s=%1.9g [%d] e=%1.9g [%d]", fSegment->span(fStart).fT, fStart, + fSegment->span(fEnd).fT, fEnd); + SkDebugf(" sgn=%d windVal=%d", sign(), mSpan.fWindValue); -#ifdef SK_DEBUG -void SkOpSpan::dump() const { - SkDebugf("t="); - DebugDumpDouble(fT); - SkDebugf(" pt="); - SkDPoint::dump(fPt); - SkDebugf(" other.fID=%d", fOther->debugID()); - SkDebugf(" [%d] otherT=", fOtherIndex); - DebugDumpDouble(fOtherT); +#if DEBUG_WINDING SkDebugf(" windSum="); - SkPathOpsDebug::WindingPrintf(fWindSum); - if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { + SkPathOpsDebug::WindingPrintf(mSpan.fWindSum); +#endif + if (mSpan.fOppValue != 0 || mSpan.fOppSum != SK_MinS32) { + SkDebugf(" oppVal=%d", mSpan.fOppValue); +#if DEBUG_WINDING SkDebugf(" oppSum="); - SkPathOpsDebug::WindingPrintf(fOppSum); - } - SkDebugf(" windValue=%d", fWindValue); - if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { - SkDebugf(" oppValue=%d", fOppValue); + SkPathOpsDebug::WindingPrintf(mSpan.fOppSum); +#endif } - if (fDone) { + if (mSpan.fDone) { SkDebugf(" done"); } - if (fUnsortableStart) { - SkDebugf(" unsortable-start"); + if (unorderable()) { + SkDebugf(" unorderable"); } - if (fUnsortableEnd) { - SkDebugf(" unsortable-end"); + if (small()) { + SkDebugf(" small"); } - if (fTiny) { + if (mSpan.fTiny) { SkDebugf(" tiny"); - } else if (fSmall) { - SkDebugf(" small"); } - if (fLoop) { - SkDebugf(" loop"); + if (fSegment->operand()) { + SkDebugf(" operand"); + } + if (fStop) { + SkDebugf(" stop"); } - SkDebugf("\n"); } +#endif -void Dump(const SkTArray<class SkOpAngle, true>& angles) { - SkPathOpsDebug::DumpAngles(angles); +#if DEBUG_ANGLE +void SkOpAngle::debugSameAs(const SkOpAngle* compare) const { + SK_DEBUGBREAK(fSegment == compare->fSegment); + const SkOpSpan& startSpan = fSegment->span(fStart); + const SkOpSpan& oStartSpan = fSegment->span(compare->fStart); + SK_DEBUGBREAK(startSpan.fToAngleIndex == oStartSpan.fToAngleIndex); + SK_DEBUGBREAK(startSpan.fFromAngleIndex == oStartSpan.fFromAngleIndex); + const SkOpSpan& endSpan = fSegment->span(fEnd); + const SkOpSpan& oEndSpan = fSegment->span(compare->fEnd); + SK_DEBUGBREAK(endSpan.fToAngleIndex == oEndSpan.fToAngleIndex); + SK_DEBUGBREAK(endSpan.fFromAngleIndex == oEndSpan.fFromAngleIndex); } +#endif -void Dump(const SkTArray<class SkOpAngle* , true>& angles) { - SkPathOpsDebug::DumpAngles(angles); +#if DEBUG_VALIDATE +void SkOpAngle::debugValidateNext() const { + const SkOpAngle* first = this; + const SkOpAngle* next = first; + SkTDArray<const SkOpAngle*>(angles); + do { + SK_DEBUGBREAK(next->fSegment->debugContains(next)); + angles.push(next); + next = next->next(); + if (next == first) { + break; + } + SK_DEBUGBREAK(!angles.contains(next)); + if (!next) { + return; + } + } while (true); } -void Dump(const SkTArray<class SkOpAngle, true>* angles) { - SkPathOpsDebug::DumpAngles(*angles); +void SkOpAngle::debugValidateLoop() const { + const SkOpAngle* first = this; + const SkOpAngle* next = first; + SK_DEBUGBREAK(first->next() != first); + int signSum = 0; + int oppSum = 0; + bool firstOperand = fSegment->operand(); + bool unorderable = false; + do { + unorderable |= next->fUnorderable; + const SkOpSegment* segment = next->fSegment; + bool operandsMatch = firstOperand == segment->operand(); + signSum += operandsMatch ? segment->spanSign(next) : segment->oppSign(next); + oppSum += operandsMatch ? segment->oppSign(next) : segment->spanSign(next); + const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd)); + if (segment->_xor()) { +// SK_DEBUGBREAK(span.fWindValue == 1); +// SK_DEBUGBREAK(span.fWindSum == SK_MinS32 || span.fWindSum == 1); + } + if (segment->oppXor()) { + SK_DEBUGBREAK(span.fOppValue == 0 || abs(span.fOppValue) == 1); +// SK_DEBUGBREAK(span.fOppSum == SK_MinS32 || span.fOppSum == 0 || abs(span.fOppSum) == 1); + } + next = next->next(); + if (!next) { + return; + } + } while (next != first); + if (unorderable) { + return; + } + SK_DEBUGBREAK(!signSum || fSegment->_xor()); + SK_DEBUGBREAK(!oppSum || fSegment->oppXor()); + int lastWinding; + int lastOppWinding; + int winding; + int oppWinding; + do { + const SkOpSegment* segment = next->fSegment; + const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd)); + winding = span.fWindSum; + if (winding != SK_MinS32) { +// SK_DEBUGBREAK(winding != 0); + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(winding)); + lastWinding = winding; + int diffWinding = segment->spanSign(next); + if (!segment->_xor()) { + SK_DEBUGBREAK(diffWinding != 0); + bool sameSign = (winding > 0) == (diffWinding > 0); + winding -= sameSign ? diffWinding : -diffWinding; + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(winding)); + SK_DEBUGBREAK(abs(winding) <= abs(lastWinding)); + if (!sameSign) { + SkTSwap(winding, lastWinding); + } + } + lastOppWinding = oppWinding = span.fOppSum; + if (oppWinding != SK_MinS32 && !segment->oppXor()) { + int oppDiffWinding = segment->oppSign(next); +// SK_DEBUGBREAK(abs(oppDiffWinding) <= abs(diffWinding) || segment->_xor()); + if (oppDiffWinding) { + bool oppSameSign = (oppWinding > 0) == (oppDiffWinding > 0); + oppWinding -= oppSameSign ? oppDiffWinding : -oppDiffWinding; + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(oppWinding)); + SK_DEBUGBREAK(abs(oppWinding) <= abs(lastOppWinding)); + if (!oppSameSign) { + SkTSwap(oppWinding, lastOppWinding); + } + } + } + firstOperand = segment->operand(); + break; + } + SK_DEBUGBREAK(span.fOppSum == SK_MinS32); + next = next->next(); + } while (next != first); + if (winding == SK_MinS32) { + return; + } + SK_DEBUGBREAK(oppWinding == SK_MinS32 || SkPathOpsDebug::ValidWind(oppWinding)); + first = next; + next = next->next(); + do { + const SkOpSegment* segment = next->fSegment; + lastWinding = winding; + lastOppWinding = oppWinding; + bool operandsMatch = firstOperand == segment->operand(); + if (operandsMatch) { + if (!segment->_xor()) { + winding -= segment->spanSign(next); + SK_DEBUGBREAK(winding != lastWinding); + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(winding)); + } + if (!segment->oppXor()) { + int oppDiffWinding = segment->oppSign(next); + if (oppWinding != SK_MinS32) { + oppWinding -= oppDiffWinding; + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(oppWinding)); + } else { + SK_DEBUGBREAK(oppDiffWinding == 0); + } + } + } else { + if (!segment->oppXor()) { + winding -= segment->oppSign(next); + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(winding)); + } + if (!segment->_xor()) { + oppWinding -= segment->spanSign(next); + SK_DEBUGBREAK(oppWinding != lastOppWinding); + SK_DEBUGBREAK(SkPathOpsDebug::ValidWind(oppWinding)); + } + } + bool useInner = SkOpSegment::UseInnerWinding(lastWinding, winding); + int sumWinding = useInner ? winding : lastWinding; + bool oppUseInner = SkOpSegment::UseInnerWinding(lastOppWinding, oppWinding); + int oppSumWinding = oppUseInner ? oppWinding : lastOppWinding; + if (!operandsMatch) { + SkTSwap(useInner, oppUseInner); + SkTSwap(sumWinding, oppSumWinding); + } + const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd)); + if (winding == -lastWinding) { + if (span.fWindSum != SK_MinS32) { + SkDebugf("%s useInner=%d spanSign=%d lastWinding=%d winding=%d windSum=%d\n", + __FUNCTION__, + useInner, segment->spanSign(next), lastWinding, winding, span.fWindSum); + } + } + if (oppWinding != SK_MinS32) { + if (span.fOppSum != SK_MinS32) { + SK_DEBUGBREAK(span.fOppSum == oppSumWinding || segment->oppXor() || segment->_xor()); + } + } else { + SK_DEBUGBREAK(!firstOperand); + SK_DEBUGBREAK(!segment->operand()); + SK_DEBUGBREAK(!span.fOppValue); + } + next = next->next(); + } while (next != first); } +#endif -void Dump(const SkTArray<class SkOpAngle* , true>* angles) { - SkPathOpsDebug::DumpAngles(*angles); +#if DEBUG_SWAP_TOP +bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const { + if (fVerb != SkPath::kCubic_Verb) { + return false; + } + SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT); + return dst.controlsContainedByEnds(); } +#endif +#if DEBUG_CONCIDENT +// SK_DEBUGBREAK if pair has not already been added +void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const { + for (int i = 0; i < fTs.count(); ++i) { + if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { + return; + } + } + SK_DEBUGBREAK(0); +} #endif -#if !FORCE_RELEASE && 0 // enable when building without extended test -void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) { +#if DEBUG_ANGLE +void SkOpSegment::debugCheckPointsEqualish(int tStart, int tEnd) const { + const SkPoint& basePt = fTs[tStart].fPt; + while (++tStart < tEnd) { + const SkPoint& cmpPt = fTs[tStart].fPt; + SK_DEBUGBREAK(SkDPoint::ApproximatelyEqual(basePt, cmpPt)); + } } #endif + +#if DEBUG_VALIDATE +bool SkOpSegment::debugContains(const SkOpAngle* angle) const { + for (int index = 0; index < fAngles.count(); ++index) { + if (&fAngles[index] == angle) { + return true; + } + } + for (int index = 0; index < fSingletonAngles.count(); ++index) { + if (&fSingletonAngles[index] == angle) { + return true; + } + } + return false; +} +#endif + +void SkOpSegment::debugReset() { + fTs.reset(); + fAngles.reset(); +} + +#if DEBUG_CONCIDENT +void SkOpSegment::debugShowTs(const char* prefix) const { + SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID); + int lastWind = -1; + int lastOpp = -1; + double lastT = -1; + int i; + for (i = 0; i < fTs.count(); ++i) { + bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue + || lastOpp != fTs[i].fOppValue; + if (change && lastWind >= 0) { + SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", + lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); + } + if (change) { + SkDebugf(" [o=%d", fTs[i].fOther->fID); + lastWind = fTs[i].fWindValue; + lastOpp = fTs[i].fOppValue; + lastT = fTs[i].fT; + } else { + SkDebugf(",%d", fTs[i].fOther->fID); + } + } + if (i <= 0) { + return; + } + SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]", + lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp); + if (fOperand) { + SkDebugf(" operand"); + } + if (done()) { + SkDebugf(" done"); + } + SkDebugf("\n"); +} +#endif + +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY +void SkOpSegment::debugShowActiveSpans() const { + debugValidate(); + if (done()) { + return; + } +#if DEBUG_ACTIVE_SPANS_SHORT_FORM + int lastId = -1; + double lastT = -1; +#endif + for (int i = 0; i < fTs.count(); ++i) { + if (fTs[i].fDone) { + continue; + } + SK_DEBUGBREAK(i < fTs.count() - 1); +#if DEBUG_ACTIVE_SPANS_SHORT_FORM + if (lastId == fID && lastT == fTs[i].fT) { + continue; + } + lastId = fID; + lastT = fTs[i].fT; +#endif + SkDebugf("%s id=%d", __FUNCTION__, fID); + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); + } + const SkOpSpan* span = &fTs[i]; + SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span)); + int iEnd = i + 1; + while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) { + ++iEnd; + } + SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT); + const SkOpSegment* other = fTs[i].fOther; + SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=", + other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex); + if (fTs[i].fWindSum == SK_MinS32) { + SkDebugf("?"); + } else { + SkDebugf("%d", fTs[i].fWindSum); + } + SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue); + } +} +#endif + +#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE +void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) { + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s id=%d", fun, fID); + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); + } + SK_DEBUGBREAK(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> + fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); + SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=", + span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, + (&span)[1].fT, winding); + if (span.fWindSum == SK_MinS32) { + SkDebugf("?"); + } else { + SkDebugf("%d", span.fWindSum); + } + SkDebugf(" windValue=%d\n", span.fWindValue); +} + +void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, + int oppWinding) { + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s id=%d", fun, fID); + SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); + for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { + SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); + } + SK_DEBUGBREAK(&span == &span.fOther->fTs[span.fOtherIndex].fOther-> + fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]); + SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=", + span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, + (&span)[1].fT, winding, oppWinding); + if (span.fOppSum == SK_MinS32) { + SkDebugf("?"); + } else { + SkDebugf("%d", span.fOppSum); + } + SkDebugf(" windSum="); + if (span.fWindSum == SK_MinS32) { + SkDebugf("?"); + } else { + SkDebugf("%d", span.fWindSum); + } + SkDebugf(" windValue=%d\n", span.fWindValue); +} +#endif + +#if DEBUG_SHOW_WINDING +int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const { + if (!(1 << fID & ofInterest)) { + return 0; + } + int sum = 0; + SkTArray<char, true> slots(slotCount * 2); + memset(slots.begin(), ' ', slotCount * 2); + for (int i = 0; i < fTs.count(); ++i) { + // if (!(1 << fTs[i].fOther->fID & ofInterest)) { + // continue; + // } + sum += fTs[i].fWindValue; + slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue); + sum += fTs[i].fOppValue; + slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue); + } + SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount, + slots.begin() + slotCount); + return sum; +} +#endif + +void SkOpSegment::debugValidate() const { +#if DEBUG_VALIDATE + int count = fTs.count(); + SK_DEBUGBREAK(count >= 2); + SK_DEBUGBREAK(fTs[0].fT == 0); + SK_DEBUGBREAK(fTs[count - 1].fT == 1); + int done = 0; + double t = -1; + const SkOpSpan* last = NULL; + bool tinyTFound = false; + bool hasLoop = false; + for (int i = 0; i < count; ++i) { + const SkOpSpan& span = fTs[i]; + SK_DEBUGBREAK(t <= span.fT); + t = span.fT; + int otherIndex = span.fOtherIndex; + const SkOpSegment* other = span.fOther; + SK_DEBUGBREAK(other != this || fVerb == SkPath::kCubic_Verb); + const SkOpSpan& otherSpan = other->fTs[otherIndex]; + SK_DEBUGBREAK(otherSpan.fPt == span.fPt); + SK_DEBUGBREAK(otherSpan.fOtherT == t); + SK_DEBUGBREAK(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]); + done += span.fDone; + if (last) { + bool tsEqual = last->fT == span.fT; + bool tsPreciselyEqual = precisely_equal(last->fT, span.fT); + SK_DEBUGBREAK(!tsEqual || tsPreciselyEqual); + bool pointsEqual = last->fPt == span.fPt; + bool pointsNearlyEqual = AlmostEqualUlps(last->fPt, span.fPt); +#if 0 // bufferOverflow test triggers this + SK_DEBUGBREAK(!tsPreciselyEqual || pointsNearlyEqual); +#endif +// SK_DEBUGBREAK(!last->fTiny || !tsPreciselyEqual || span.fTiny || tinyTFound); + SK_DEBUGBREAK(last->fTiny || tsPreciselyEqual || !pointsEqual || hasLoop); + SK_DEBUGBREAK(!last->fTiny || pointsEqual); + SK_DEBUGBREAK(!last->fTiny || last->fDone); + SK_DEBUGBREAK(!last->fSmall || pointsNearlyEqual); + SK_DEBUGBREAK(!last->fSmall || last->fDone); +// SK_DEBUGBREAK(!last->fSmall || last->fTiny); +// SK_DEBUGBREAK(last->fTiny || !pointsEqual || last->fDone == span.fDone); + if (last->fTiny) { + tinyTFound |= !tsPreciselyEqual; + } else { + tinyTFound = false; + } + } + last = &span; + hasLoop |= last->fLoop; + } + SK_DEBUGBREAK(done == fDoneSpans); + if (fAngles.count() ) { + fAngles.begin()->debugValidateLoop(); + } +#endif +} diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index d2155188da..5cacee5c7a 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -31,6 +31,10 @@ #define SK_SNPRINTF snprintf #endif +#define WIND_AS_STRING(x) char x##Str[12]; \ + if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \ + else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x) + #if FORCE_RELEASE #define DEBUG_ACTIVE_OP 0 @@ -121,13 +125,12 @@ #define DEBUG_TEST 0 #endif -#if defined SK_DEBUG || !FORCE_RELEASE - #if DEBUG_SHOW_TEST_NAME #include "SkTLS.h" #endif #include "SkTArray.h" +#include "SkTDArray.h" class SkPathOpsDebug { public: @@ -147,6 +150,7 @@ public: static const char* kPathOpStr[]; #endif + static bool ChaseContains(const SkTDArray<struct SkOpSpan *>& , const struct SkOpSpan * ); static void MathematicaIze(char* str, size_t bufferSize); static bool ValidWind(int winding); static void WindingPrintf(int winding); @@ -158,10 +162,20 @@ public: #define DEBUG_FILENAME_STRING (reinterpret_cast<char* >(SkTLS::Get(SkPathOpsDebug::CreateNameStr, \ SkPathOpsDebug::DeleteNameStr))) static void BumpTestName(char* ); - static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); #endif + static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); static void DumpAngles(const SkTArray<class SkOpAngle, true>& angles); static void DumpAngles(const SkTArray<class SkOpAngle* , true>& angles); + static void DumpContours(const SkTArray<class SkOpContour, true>& contours); + static void DumpContours(const SkTArray<class SkOpContour* , true>& contours); + static void DumpContourAngles(const SkTArray<class SkOpContour, true>& contours); + static void DumpContourAngles(const SkTArray<class SkOpContour* , true>& contours); + static void DumpContourPts(const SkTArray<class SkOpContour, true>& contours); + static void DumpContourPts(const SkTArray<class SkOpContour* , true>& contours); + static void DumpContourSpans(const SkTArray<class SkOpContour, true>& contours); + static void DumpContourSpans(const SkTArray<class SkOpContour* , true>& contours); + static void DumpSpans(const SkTDArray<struct SkOpSpan *>& ); + static void DumpSpans(const SkTDArray<struct SkOpSpan *>* ); }; // shorthand for calling from debugger @@ -170,6 +184,32 @@ void Dump(const SkTArray<class SkOpAngle* , true>& angles); void Dump(const SkTArray<class SkOpAngle, true>* angles); void Dump(const SkTArray<class SkOpAngle* , true>* angles); -#endif // SK_DEBUG || !FORCE_RELEASE +void Dump(const SkTArray<class SkOpContour, true>& contours); +void Dump(const SkTArray<class SkOpContour* , true>& contours); +void Dump(const SkTArray<class SkOpContour, true>* contours); +void Dump(const SkTArray<class SkOpContour* , true>* contours); + +void Dump(const SkTDArray<SkOpSpan *>& chaseArray); +void Dump(const SkTDArray<SkOpSpan *>* chaseArray); + +void DumpAngles(const SkTArray<class SkOpContour, true>& contours); +void DumpAngles(const SkTArray<class SkOpContour* , true>& contours); +void DumpAngles(const SkTArray<class SkOpContour, true>* contours); +void DumpAngles(const SkTArray<class SkOpContour* , true>* contours); + +void DumpPts(const SkTArray<class SkOpContour, true>& contours); +void DumpPts(const SkTArray<class SkOpContour* , true>& contours); +void DumpPts(const SkTArray<class SkOpContour, true>* contours); +void DumpPts(const SkTArray<class SkOpContour* , true>* contours); + +void DumpSpans(const SkTArray<class SkOpContour, true>& contours); +void DumpSpans(const SkTArray<class SkOpContour* , true>& contours); +void DumpSpans(const SkTArray<class SkOpContour, true>* contours); +void DumpSpans(const SkTArray<class SkOpContour* , true>* contours); + +// generates tools/path_sorter.htm and path_visualizer.htm compatible data +void DumpQ(const struct SkDQuad& quad1, const struct SkDQuad& quad2, int testNo); + +void DumpT(const struct SkDQuad& quad, double t); #endif diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index 1e74123abf..7587fda69a 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -189,13 +189,3 @@ double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double } return t; } - -#ifdef SK_DEBUG -void SkDLine::dump() { - SkDebugf("{{"); - fPts[0].dump(); - SkDebugf(", "); - fPts[1].dump(); - SkDebugf("}}\n"); -} -#endif diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index a3cfcf26ef..e4ed0c9b20 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -38,9 +38,7 @@ struct SkDLine { SkDPoint ptAtT(double t) const; SkDLine subDivide(double t1, double t2) const; -#ifdef SK_DEBUG - void dump(); -#endif + void dump() const; private: SkDVector tangent() const { return fPts[0] - fPts[1]; } }; diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 1b7b03b95b..130d4983f9 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -9,23 +9,20 @@ #include "SkPathOpsCommon.h" #include "SkPathWriter.h" -// FIXME: this and find chase should be merge together, along with -// other code that walks winding in angles -// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure -// so it isn't duplicated by walkers like this one -static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) { +static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) { while (chase.count()) { SkOpSpan* span; chase.pop(&span); const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); SkOpSegment* segment = backPtr.fOther; - nextStart = backPtr.fOtherIndex; - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; - int done = 0; - if (segment->activeAngle(nextStart, &done, &angles)) { - SkOpAngle* last = angles.end() - 1; - nextStart = last->start(); - nextEnd = last->end(); + *tIndex = backPtr.fOtherIndex; + bool sortable = true; + bool done = true; + *endIndex = -1; + if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done, + &sortable)) { + *tIndex = last->start(); + *endIndex = last->end(); #if TRY_ROTATE *chase.insert(0) = span; #else @@ -33,52 +30,31 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int #endif return last->segment(); } - if (done == angles.count()) { + if (done) { continue; } - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SkOpSegment::SortAngles(angles, &sorted, - SkOpSegment::kMayBeUnordered_SortAngleKind); - int angleCount = sorted.count(); -#if DEBUG_SORT - sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable); -#endif if (!sortable) { continue; } // find first angle, initialize winding to computed fWindSum - int firstIndex = -1; - const SkOpAngle* angle; - bool foundAngle = true; + const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); + const SkOpAngle* firstAngle = angle; + SkDEBUGCODE(bool loop = false); + int winding; do { - ++firstIndex; - if (firstIndex >= angleCount) { - foundAngle = false; - break; - } - angle = sorted[firstIndex]; + angle = angle->next(); + SkASSERT(angle != firstAngle || !loop); + SkDEBUGCODE(loop |= angle == firstAngle); segment = angle->segment(); - } while (segment->windSum(angle) == SK_MinS32); - if (!foundAngle) { - continue; - } - #if DEBUG_SORT - segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); - #endif + winding = segment->windSum(angle); + } while (winding == SK_MinS32); int sumMiWinding = segment->updateWindingReverse(angle); int sumSuWinding = segment->updateOppWindingReverse(angle); if (segment->operand()) { SkTSwap<int>(sumMiWinding, sumSuWinding); } - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; SkOpSegment* first = NULL; - do { - SkASSERT(nextIndex != firstIndex); - if (nextIndex == angleCount) { - nextIndex = 0; - } - angle = sorted[nextIndex]; + while ((angle = angle->next()) != firstAngle) { segment = angle->segment(); int start = angle->start(); int end = angle->end(); @@ -88,13 +64,13 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int if (!segment->done(angle)) { if (!first) { first = segment; - nextStart = start; - nextEnd = end; + *tIndex = start; + *endIndex = end; } (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, angle); } - } while (++nextIndex != lastIndex); + } if (first) { #if TRY_ROTATE *chase.insert(0) = span; @@ -160,9 +136,6 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { do { if (!unsortable && current->done()) { - #if DEBUG_ACTIVE_SPANS - DebugShowActiveSpans(contourList); - #endif if (simple->isEmpty()) { simple->init(); } @@ -199,7 +172,6 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o if (!unsortable && !simple->isEmpty()) { unsortable = current->checkSmall(min); } - SkASSERT(unsortable || simple->isEmpty()); if (!current->done(min)) { current->addCurveTo(index, endIndex, simple, true); current->markDoneBinary(min); @@ -208,11 +180,13 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o simple->close(); } else { SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); - if (last && !last->fLoop) { + if (last && !last->fChased && !last->fLoop) { + last->fChased = true; + SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last)); *chaseArray.append() = last; } } - current = findChaseOp(chaseArray, index, endIndex); + current = findChaseOp(chaseArray, &index, &endIndex); #if DEBUG_ACTIVE_SPANS DebugShowActiveSpans(contourList); #endif @@ -304,7 +278,9 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { for (index = 0; index < contourList.count(); ++index) { total += contourList[index]->segments().count(); } - HandleCoincidence(&contourList, total); + if (!HandleCoincidence(&contourList, total)) { + return false; + } // construct closed contours SkPathWriter wrapper(*result); bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper); diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index c3e0b40ab9..8fd247ee51 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -15,7 +15,13 @@ inline bool AlmostEqualUlps(const SkPoint& pt1, const SkPoint& pt2) { } struct SkDVector { - double fX, fY; + double fX; + double fY; + + void set(const SkVector& pt) { + fX = pt.fX; + fY = pt.fY; + } friend SkDPoint operator+(const SkDPoint& a, const SkDVector& b); @@ -48,6 +54,13 @@ struct SkDVector { return fX * a.fY - fY * a.fX; } + // similar to cross, this bastardization considers nearly coincident to be zero + double crossCheck(const SkDVector& a) const { + double xy = fX * a.fY; + double yx = fY * a.fX; + return AlmostEqualUlps(xy, yx) ? 0 : xy - yx; + } + double dot(const SkDVector& a) const { return fX * a.fX + fY * a.fY; } @@ -85,7 +98,6 @@ struct SkDPoint { fY = pt.fY; } - void operator+=(const SkDVector& v) { fX += v.fX; fY += v.fY; @@ -136,6 +148,15 @@ struct SkDPoint { return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance? } +#if SK_DEBUG + static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) { + if (approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY)) { + return true; + } + return RoughlyEqualUlps(a.fX, b.fX) && RoughlyEqualUlps(a.fY, b.fY); + } +#endif + bool approximatelyPEqual(const SkDPoint& a) const { if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { return true; @@ -150,6 +171,20 @@ struct SkDPoint { return AlmostPequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? } + bool approximatelyDEqual(const SkDPoint& a) const { + if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { + return true; + } + if (!RoughlyEqualUlps(fX, a.fX) || !RoughlyEqualUlps(fY, a.fY)) { + return false; + } + double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ? + double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY); + double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY); + largest = SkTMax(largest, -tiniest); + return AlmostDequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? + } + bool approximatelyZero() const { return approximately_zero(fX) && approximately_zero(fY); } @@ -191,23 +226,9 @@ struct SkDPoint { return roughly_equal(a.fY, fY) && roughly_equal(a.fX, fX); } - #ifdef SK_DEBUG - void dump() { - SkDebugf("{"); - DebugDumpDouble(fX); - SkDebugf(", "); - DebugDumpDouble(fY); - SkDebugf("}"); - } - - static void dump(const SkPoint& pt) { - SkDebugf("{"); - DebugDumpFloat(pt.fX); - SkDebugf(", "); - DebugDumpFloat(pt.fY); - SkDebugf("}"); - } - #endif + // utilities callable by the user from the debugger when the implementation code is linked in + void dump() const; + static void Dump(const SkPoint& pt); }; #endif diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 63e20388dd..c1d068af34 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -252,10 +252,10 @@ SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, dou SkDLine b1 = {{c, sub[1] + (c - sub[2])}}; SkIntersections i; i.intersectRay(b0, b1); - if (i.used() == 1) { + if (i.used() == 1 && i[0][0] >= 0 && i[1][0] >= 0) { b = i.pt(0); } else { - SkASSERT(i.used() == 2 || i.used() == 0); + SkASSERT(i.used() <= 2); b = SkDPoint::Mid(b0[1], b1[1]); } #endif @@ -265,14 +265,14 @@ SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, dou if (t1 == 1 || t2 == 1) { align(2, &b); } - if (precisely_subdivide_equal(b.fX, a.fX)) { + if (AlmostBequalUlps(b.fX, a.fX)) { b.fX = a.fX; - } else if (precisely_subdivide_equal(b.fX, c.fX)) { + } else if (AlmostBequalUlps(b.fX, c.fX)) { b.fX = c.fX; } - if (precisely_subdivide_equal(b.fY, a.fY)) { + if (AlmostBequalUlps(b.fY, a.fY)) { b.fY = a.fY; - } else if (precisely_subdivide_equal(b.fY, c.fY)) { + } else if (AlmostBequalUlps(b.fY, c.fY)) { b.fY = c.fY; } return b; @@ -340,16 +340,3 @@ void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { *a -= *b; // a = A - 2*B + C *b -= *c; // b = 2*B - 2*C } - -#ifdef SK_DEBUG -void SkDQuad::dump() { - SkDebugf("{{"); - int index = 0; - do { - fPts[index].dump(); - SkDebugf(", "); - } while (++index < 2); - fPts[index].dump(); - SkDebugf("}}\n"); -} -#endif diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h index 69d5a6dd90..932c5fbe75 100644 --- a/src/pathops/SkPathOpsQuad.h +++ b/src/pathops/SkPathOpsQuad.h @@ -62,9 +62,10 @@ struct SkDQuad { SkDCubic toCubic() const; SkDPoint top(double startT, double endT) const; -#ifdef SK_DEBUG - void dump(); -#endif + // utilities callable by the user from the debugger when the implementation code is linked in + void dump() const; + void dumpComma(const char*) const; + private: // static double Tangent(const double* quadratic, double t); // uncalled }; diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 548f83e660..66a6c40268 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -33,9 +33,6 @@ static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWrite if (current->activeWinding(index, endIndex)) { do { if (!unsortable && current->done()) { - #if DEBUG_ACTIVE_SPANS - DebugShowActiveSpans(contourList); - #endif if (simple->isEmpty()) { simple->init(); break; @@ -77,11 +74,15 @@ static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWrite simple->close(); } else { SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex); - if (last && !last->fLoop) { + if (last && !last->fChased && !last->fLoop) { + last->fChased = true; + SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last)); + // assert that last isn't already in array *chaseArray.append() = last; } } - current = FindChase(chaseArray, index, endIndex); + SkTDArray<SkOpSpan *>* chaseArrayPtr = &chaseArray; + current = FindChase(chaseArrayPtr, &index, &endIndex); #if DEBUG_ACTIVE_SPANS DebugShowActiveSpans(contourList); #endif @@ -182,7 +183,9 @@ bool Simplify(const SkPath& path, SkPath* result) { next = *nextPtr++; } while (AddIntersectTs(current, next) && nextPtr != listEnd); } while (currentPtr != listEnd); - HandleCoincidence(&contourList, 0); + if (!HandleCoincidence(&contourList, 0)) { + return false; + } // construct closed contours SkPathWriter simple(*result); if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple) diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 4fa86abd91..e8054ad476 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -85,6 +85,7 @@ inline int UlpsDistance(double a, double b) { const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; const double FLT_EPSILON_HALF = FLT_EPSILON / 2; const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; +const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16; const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; @@ -121,6 +122,10 @@ inline bool approximately_zero_double(double x) { return fabs(x) < FLT_EPSILON_DOUBLE; } +inline bool approximately_zero_orderable(double x) { + return fabs(x) < FLT_EPSILON_ORDERABLE_ERR; +} + inline bool approximately_zero_squared(double x) { return fabs(x) < FLT_EPSILON_SQUARED; } @@ -139,7 +144,7 @@ inline bool approximately_zero_inverse(double x) { // OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead inline bool approximately_zero_when_compared_to(double x, double y) { - return x == 0 || fabs(x / y) < FLT_EPSILON; + return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); } // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use @@ -164,6 +169,10 @@ inline bool approximately_equal_double(double x, double y) { return approximately_zero_double(x - y); } +inline bool approximately_equal_orderable(double x, double y) { + return approximately_zero_orderable(x - y); +} + inline bool approximately_equal_squared(double x, double y) { return approximately_equal(x, y); } @@ -172,18 +181,50 @@ inline bool approximately_greater(double x, double y) { return x - FLT_EPSILON >= y; } +inline bool approximately_greater_double(double x, double y) { + return x - FLT_EPSILON_DOUBLE >= y; +} + +inline bool approximately_greater_orderable(double x, double y) { + return x - FLT_EPSILON_ORDERABLE_ERR >= y; +} + inline bool approximately_greater_or_equal(double x, double y) { return x + FLT_EPSILON > y; } +inline bool approximately_greater_or_equal_double(double x, double y) { + return x + FLT_EPSILON_DOUBLE > y; +} + +inline bool approximately_greater_or_equal_orderable(double x, double y) { + return x + FLT_EPSILON_ORDERABLE_ERR > y; +} + inline bool approximately_lesser(double x, double y) { return x + FLT_EPSILON <= y; } +inline bool approximately_lesser_double(double x, double y) { + return x + FLT_EPSILON_DOUBLE <= y; +} + +inline bool approximately_lesser_orderable(double x, double y) { + return x + FLT_EPSILON_ORDERABLE_ERR <= y; +} + inline bool approximately_lesser_or_equal(double x, double y) { return x - FLT_EPSILON < y; } +inline bool approximately_lesser_or_equal_double(double x, double y) { + return x - FLT_EPSILON_DOUBLE < y; +} + +inline bool approximately_lesser_or_equal_orderable(double x, double y) { + return x - FLT_EPSILON_ORDERABLE_ERR < y; +} + inline bool approximately_greater_than_one(double x) { return x > 1 - FLT_EPSILON; } @@ -204,6 +245,10 @@ inline bool approximately_negative(double x) { return x < FLT_EPSILON; } +inline bool approximately_negative_orderable(double x) { + return x < FLT_EPSILON_ORDERABLE_ERR; +} + inline bool precisely_negative(double x) { return x < DBL_EPSILON_ERR; } @@ -212,6 +257,10 @@ inline bool approximately_one_or_less(double x) { return x < 1 + FLT_EPSILON; } +inline bool approximately_one_or_less_double(double x) { + return x < 1 + FLT_EPSILON_DOUBLE; +} + inline bool approximately_positive(double x) { return x > -FLT_EPSILON; } @@ -224,6 +273,16 @@ inline bool approximately_zero_or_more(double x) { return x > -FLT_EPSILON; } +inline bool approximately_zero_or_more_double(double x) { + return x > -FLT_EPSILON_DOUBLE; +} + +inline bool approximately_between_orderable(double a, double b, double c) { + return a <= c + ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c) + : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b); +} + inline bool approximately_between(double a, double b, double c) { return a <= c ? approximately_negative(a - b) && approximately_negative(b - c) : approximately_negative(b - a) && approximately_negative(c - b); @@ -311,22 +370,4 @@ inline double SkPinT(double t) { return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; } -#ifdef SK_DEBUG -inline void DebugDumpDouble(double x) { - if (x == floor(x)) { - SkDebugf("%.0f", x); - } else { - SkDebugf("%1.17g", x); - } -} - -inline void DebugDumpFloat(float x) { - if (x == floorf(x)) { - SkDebugf("%.0f", x); - } else { - SkDebugf("%1.9gf", x); - } -} -#endif - #endif diff --git a/src/pathops/SkPathWriter.h b/src/pathops/SkPathWriter.h index 574708231b..f32074d3cd 100644 --- a/src/pathops/SkPathWriter.h +++ b/src/pathops/SkPathWriter.h @@ -41,5 +41,4 @@ private: bool fMoved; }; - #endif /* defined(__PathOps__SkPathWriter__) */ diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp index e5b486c76c..f9a7bf5179 100644 --- a/src/pathops/SkQuarticRoot.cpp +++ b/src/pathops/SkQuarticRoot.cpp @@ -71,7 +71,9 @@ int SkReducedQuarticRoots(const double t4, const double t3, const double t2, con return num; } if (oneHint) { - SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0)); // 1 is one root + SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0) || + approximately_zero_when_compared_to(t4 + t3 + t2 + t1 + t0, // 1 is one root + SkTMax(fabs(t4), SkTMax(fabs(t3), SkTMax(fabs(t2), SkTMax(fabs(t1), fabs(t0))))))); // note that -C == A + B + D + E int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots); for (int i = 0; i < num; ++i) { @@ -101,7 +103,8 @@ int SkQuarticRootsReal(int firstCubicRoot, const double A, const double B, const const double q = a2 * a / 8 - a * b / 2 + c; const double r = -3 * a2 * a2 / 256 + a2 * b / 16 - a * c / 4 + d; int num; - if (approximately_zero(r)) { + double largest = SkTMax(fabs(p), fabs(q)); + if (approximately_zero_when_compared_to(r, largest)) { /* no absolute term: y(y^3 + py + q) = 0 */ num = SkDCubic::RootsReal(1, 0, p, q, s); s[num++] = 0; |