diff options
author | commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-04-14 17:08:59 +0000 |
---|---|---|
committer | commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-04-14 17:08:59 +0000 |
commit | 4431e7757cfcb8cfa99535eed0e9f156dabf95c2 (patch) | |
tree | f5939d4bb12b64c6953c8bae3ea684791565ca7f /src/pathops | |
parent | 95f79261addecd8c3b4e64f2f1469f9e1aa0acb2 (diff) |
Mike R: please sanity check SkPostConfig.h
Mike K: please sanity check Test.cpp and skia_test.cpp
Feel free to look at the rest, but I don't expect any in depth review of path ops innards.
Path Ops first iteration used QuickSort to order segments radiating from an intersection to compute the winding rule.
This revision uses a circular sort instead. Breaking out the circular sort into its own long-lived structure (SkOpAngle) allows doing less work and provides a home for caching additional sorting data.
The circle sort is more stable than the former sort, has a robust ordering and fewer exceptions. It finds unsortable ordering less often. It is less reliant on the initial curve tangent, using convex hulls instead whenever it can.
Additional debug validation makes sure that the computed structures are self-consistent. A new visualization tool helps verify that the angle ordering is correct.
The 70+M tests pass with this change on Windows, Mac, Linux 32 and Linux 64 in debug and release.
R=mtklein@google.com, reed@google.com
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/131103009
git-svn-id: http://skia.googlecode.com/svn/trunk@14183 2bbb7eff-a529-9590-31e7-b0007b416f81
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; |