diff options
Diffstat (limited to 'src/pathops')
33 files changed, 913 insertions, 1770 deletions
diff --git a/src/pathops/SkDConicLineIntersection.cpp b/src/pathops/SkDConicLineIntersection.cpp index 674068d55f..c9d825d56c 100644 --- a/src/pathops/SkDConicLineIntersection.cpp +++ b/src/pathops/SkDConicLineIntersection.cpp @@ -17,12 +17,19 @@ public: LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i) : fConic(c) - , fLine(l) + , fLine(&l) , fIntersections(i) , fAllowNear(true) { i->setMax(3); // allow short partial coincidence plus discrete intersection } + LineConicIntersections(const SkDConic& c) + : fConic(c) + SkDEBUGPARAMS(fLine(NULL)) + SkDEBUGPARAMS(fIntersections(NULL)) + SkDEBUGPARAMS(fAllowNear(false)) { + } + void allowNear(bool allow) { fAllowNear = allow; } @@ -32,7 +39,7 @@ public: for (int index = 0; index < last; ) { double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; SkDPoint conicMidPt = fConic.ptAtT(conicMidT); - double t = fLine.nearPoint(conicMidPt, NULL); + double t = fLine->nearPoint(conicMidPt, NULL); if (t < 0) { ++index; continue; @@ -56,6 +63,10 @@ public: return approximately_zero_when_compared_to(a - b, max); } #endif + int horizontalIntersect(double axisIntercept, double roots[2]) { + double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; + return this->validT(conicVals, axisIntercept, roots); + } int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { this->addExactHorizontalEndPoints(left, right, axisIntercept); @@ -63,11 +74,11 @@ public: this->addNearHorizontalEndPoints(left, right, axisIntercept); } double roots[2]; - double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; - int count = this->validT(conicVals, axisIntercept, roots); + int count = this->horizontalIntersect(axisIntercept, roots); for (int index = 0; index < count; ++index) { double conicT = roots[index]; SkDPoint pt = fConic.ptAtT(conicT); + SkDEBUGCODE_(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }); SkASSERT(close_to(pt.fY, axisIntercept, conicVals)); double lineT = (pt.fX - left) / (right - left); if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) @@ -93,7 +104,7 @@ public: double conicT = rootVals[index]; double lineT = this->findLineT(conicT); SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); - SkDEBUGCODE(SkDPoint linePt = fLine.ptAtT(lineT)); + SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); SkASSERT(conicPt.approximatelyEqual(linePt)); SkDPoint pt; if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized) @@ -106,11 +117,11 @@ public: } int intersectRay(double roots[2]) { - double adj = fLine[1].fX - fLine[0].fX; - double opp = fLine[1].fY - fLine[0].fY; + double adj = (*fLine)[1].fX - (*fLine)[0].fX; + double opp = (*fLine)[1].fY - (*fLine)[0].fY; double r[3]; for (int n = 0; n < 3; ++n) { - r[n] = (fConic[n].fY - fLine[0].fY) * adj - (fConic[n].fX - fLine[0].fX) * opp; + r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp; } return this->validT(r, 0, roots); } @@ -125,17 +136,22 @@ public: return SkDQuad::RootsValidT(A, 2 * B, C, roots); } + int verticalIntersect(double axisIntercept, double roots[2]) { + double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; + return this->validT(conicVals, axisIntercept, roots); + } + int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { this->addExactVerticalEndPoints(top, bottom, axisIntercept); if (fAllowNear) { this->addNearVerticalEndPoints(top, bottom, axisIntercept); } double roots[2]; - double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; - int count = this->validT(conicVals, axisIntercept, roots); + int count = this->verticalIntersect(axisIntercept, roots); for (int index = 0; index < count; ++index) { double conicT = roots[index]; SkDPoint pt = fConic.ptAtT(conicT); + SkDEBUGCODE_(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }); SkASSERT(close_to(pt.fX, axisIntercept, conicVals)); double lineT = (pt.fY - top) / (bottom - top); if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) @@ -155,7 +171,7 @@ protected: // add endpoints first to get zero and one t values exactly void addExactEndPoints() { for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { - double lineT = fLine.exactPoint(fConic[cIndex]); + double lineT = fLine->exactPoint(fConic[cIndex]); if (lineT < 0) { continue; } @@ -170,7 +186,7 @@ protected: if (fIntersections->hasT(conicT)) { continue; } - double lineT = fLine.nearPoint(fConic[cIndex], NULL); + double lineT = fLine->nearPoint(fConic[cIndex], NULL); if (lineT < 0) { continue; } @@ -233,12 +249,12 @@ protected: double findLineT(double t) { SkDPoint xy = fConic.ptAtT(t); - double dx = fLine[1].fX - fLine[0].fX; - double dy = fLine[1].fY - fLine[0].fY; + double dx = (*fLine)[1].fX - (*fLine)[0].fX; + double dy = (*fLine)[1].fY - (*fLine)[0].fY; if (fabs(dx) > fabs(dy)) { - return (xy.fX - fLine[0].fX) / dx; + return (xy.fX - (*fLine)[0].fX) / dx; } - return (xy.fY - fLine[0].fY) / dy; + return (xy.fY - (*fLine)[0].fY) / dy; } bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { @@ -251,16 +267,16 @@ protected: double qT = *conicT = SkPinT(*conicT); double lT = *lineT = SkPinT(*lineT); if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { - *pt = fLine.ptAtT(lT); + *pt = (*fLine).ptAtT(lT); } else if (ptSet == kPointUninitialized) { *pt = fConic.ptAtT(qT); } SkPoint gridPt = pt->asSkPoint(); - if (SkDPoint::ApproximatelyEqual(gridPt, fLine[0].asSkPoint())) { - *pt = fLine[0]; + if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { + *pt = (*fLine)[0]; *lineT = 0; - } else if (SkDPoint::ApproximatelyEqual(gridPt, fLine[1].asSkPoint())) { - *pt = fLine[1]; + } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { + *pt = (*fLine)[1]; *lineT = 1; } if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { @@ -302,7 +318,7 @@ protected: private: const SkDConic& fConic; - const SkDLine& fLine; + const SkDLine* fLine; SkIntersections* fIntersections; bool fAllowNear; }; @@ -335,3 +351,13 @@ int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) { } return fUsed; } + +int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) { + LineConicIntersections c(conic); + return c.horizontalIntersect(y, roots); +} + +int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) { + LineConicIntersections c(conic); + return c.verticalIntersect(x, roots); +} diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index ed96b9c5d7..5fd8e7fdb7 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -188,7 +188,7 @@ static int horizontal_coincident(const SkDLine& line, double y) { return 1; } -static double horizontal_intercept(const SkDLine& line, double y) { +double SkIntersections::HorizontalIntercept(const SkDLine& line, double y) { return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); } @@ -214,7 +214,7 @@ int SkIntersections::horizontal(const SkDLine& line, double left, double right, } int result = horizontal_coincident(line, y); if (result == 1 && fUsed == 0) { - fT[0][0] = horizontal_intercept(line, y); + fT[0][0] = HorizontalIntercept(line, y); double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); if (between(left, xIntercept, right)) { fT[1][0] = (xIntercept - left) / (right - left); @@ -264,7 +264,7 @@ static int vertical_coincident(const SkDLine& line, double x) { return 1; } -static double vertical_intercept(const SkDLine& line, double x) { +double SkIntersections::VerticalIntercept(const SkDLine& line, double x) { return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); } @@ -290,7 +290,7 @@ int SkIntersections::vertical(const SkDLine& line, double top, double bottom, } int result = vertical_coincident(line, x); if (result == 1 && fUsed == 0) { - fT[0][0] = vertical_intercept(line, x); + fT[0][0] = VerticalIntercept(line, x); double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); if (between(top, yIntercept, bottom)) { fT[1][0] = (yIntercept - top) / (bottom - top); diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index b8a9a641dd..5e3596ec20 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -95,12 +95,19 @@ public: LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i) : fQuad(q) - , fLine(l) + , fLine(&l) , fIntersections(i) , fAllowNear(true) { i->setMax(3); // allow short partial coincidence plus discrete intersection } + LineQuadraticIntersections(const SkDQuad& q) + : fQuad(q) + SkDEBUGPARAMS(fLine(NULL)) + SkDEBUGPARAMS(fIntersections(NULL)) + SkDEBUGPARAMS(fAllowNear(false)) { + } + void allowNear(bool allow) { fAllowNear = allow; } @@ -110,7 +117,7 @@ public: for (int index = 0; index < last; ) { double quadMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; SkDPoint quadMidPt = fQuad.ptAtT(quadMidT); - double t = fLine.nearPoint(quadMidPt, NULL); + double t = fLine->nearPoint(quadMidPt, NULL); if (t < 0) { ++index; continue; @@ -144,11 +151,11 @@ public: for each of the three points (e.g. n = 0 to 2) quad[n].fY' = (quad[n].fY - line[0].fY) * A - (quad[n].fX - line[0].fX) * O */ - double adj = fLine[1].fX - fLine[0].fX; - double opp = fLine[1].fY - fLine[0].fY; + double adj = (*fLine)[1].fX - (*fLine)[0].fX; + double opp = (*fLine)[1].fY - (*fLine)[0].fY; double r[3]; for (int n = 0; n < 3; ++n) { - r[n] = (fQuad[n].fY - fLine[0].fY) * adj - (fQuad[n].fX - fLine[0].fX) * opp; + r[n] = (fQuad[n].fY - (*fLine)[0].fY) * adj - (fQuad[n].fX - (*fLine)[0].fX) * opp; } double A = r[2]; double B = r[1]; @@ -269,7 +276,7 @@ protected: // add endpoints first to get zero and one t values exactly void addExactEndPoints() { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - double lineT = fLine.exactPoint(fQuad[qIndex]); + double lineT = fLine->exactPoint(fQuad[qIndex]); if (lineT < 0) { continue; } @@ -284,7 +291,7 @@ protected: if (fIntersections->hasT(quadT)) { continue; } - double lineT = fLine.nearPoint(fQuad[qIndex], NULL); + double lineT = fLine->nearPoint(fQuad[qIndex], NULL); if (lineT < 0) { continue; } @@ -347,12 +354,12 @@ protected: double findLineT(double t) { SkDPoint xy = fQuad.ptAtT(t); - double dx = fLine[1].fX - fLine[0].fX; - double dy = fLine[1].fY - fLine[0].fY; + double dx = (*fLine)[1].fX - (*fLine)[0].fX; + double dy = (*fLine)[1].fY - (*fLine)[0].fY; if (fabs(dx) > fabs(dy)) { - return (xy.fX - fLine[0].fX) / dx; + return (xy.fX - (*fLine)[0].fX) / dx; } - return (xy.fY - fLine[0].fY) / dy; + return (xy.fY - (*fLine)[0].fY) / dy; } bool pinTs(double* quadT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { @@ -365,16 +372,16 @@ protected: double qT = *quadT = SkPinT(*quadT); double lT = *lineT = SkPinT(*lineT); if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { - *pt = fLine.ptAtT(lT); + *pt = (*fLine).ptAtT(lT); } else if (ptSet == kPointUninitialized) { *pt = fQuad.ptAtT(qT); } SkPoint gridPt = pt->asSkPoint(); - if (SkDPoint::ApproximatelyEqual(gridPt, fLine[0].asSkPoint())) { - *pt = fLine[0]; + if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { + *pt = (*fLine)[0]; *lineT = 0; - } else if (SkDPoint::ApproximatelyEqual(gridPt, fLine[1].asSkPoint())) { - *pt = fLine[1]; + } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { + *pt = (*fLine)[1]; *lineT = 1; } if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { @@ -392,7 +399,7 @@ protected: private: const SkDQuad& fQuad; - const SkDLine& fLine; + const SkDLine* fLine; SkIntersections* fIntersections; bool fAllowNear; }; @@ -425,3 +432,13 @@ int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) { } return fUsed; } + +int SkIntersections::HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots) { + LineQuadraticIntersections q(quad); + return q.horizontalIntersect(y, roots); +} + +int SkIntersections::VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots) { + LineQuadraticIntersections q(quad); + return q.verticalIntersect(x, roots); +} diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index a1f859833a..7caf04bf4d 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -25,37 +25,6 @@ int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoin return closest; } -// called only by test code -int SkIntersections::coincidentUsed() const { - if (!fIsCoincident[0]) { - SkASSERT(!fIsCoincident[1]); - return 0; - } - int count = 0; - SkDEBUGCODE(int count2 = 0;) - for (int index = 0; index < fUsed; ++index) { - if (fIsCoincident[0] & (1 << index)) { - ++count; - } -#ifdef SK_DEBUG - if (fIsCoincident[1] & (1 << index)) { - ++count2; - } -#endif - } - SkASSERT(count == count2); - return count; -} - -int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar, - SkScalar, SkScalar, SkScalar, bool) = { - NULL, - &SkIntersections::verticalLine, - &SkIntersections::verticalQuad, - &SkIntersections::verticalConic, - &SkIntersections::verticalCubic -}; - void SkIntersections::flip() { for (int index = 0; index < fUsed; ++index) { fT[1][index] = 1 - fT[1][index]; @@ -174,12 +143,6 @@ int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPo return result; } -void SkIntersections::quickRemoveOne(int index, int replace) { - if (index < replace) { - fT[0][index] = fT[0][replace]; - } -} - void SkIntersections::removeOne(int index) { int remaining = --fUsed - index; if (remaining <= 0) { @@ -194,31 +157,3 @@ void SkIntersections::removeOne(int index) { SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; } - -int SkIntersections::verticalConic(const SkPoint a[3], SkScalar weight, - SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { - SkDConic conic; - conic.set(a, weight); - return vertical(conic, top, bottom, x, flipped); -} - -int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar weight, - SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { - SkDCubic cubic; - cubic.set(a); - return vertical(cubic, top, bottom, x, flipped); -} - -int SkIntersections::verticalLine(const SkPoint a[2], SkScalar weight, - SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { - SkDLine line; - line.set(a); - return vertical(line, top, bottom, x, flipped); -} - -int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar weight, - SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { - SkDQuad quad; - quad.set(a); - return vertical(quad, top, bottom, x, flipped); -} diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 57fb49bcd2..c12db38b6c 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -224,7 +224,6 @@ public: void alignQuadPts(const SkPoint a[3], const SkPoint b[3]); int cleanUpCoincidence(); int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const; - int coincidentUsed() const; void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1, const SkDCubic& c2); void flip(); @@ -235,6 +234,9 @@ public: int horizontal(const SkDConic&, double left, double right, double y, bool flipped); int horizontal(const SkDCubic&, double left, double right, double y, bool flipped); int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); + static double HorizontalIntercept(const SkDLine& line, double y); + static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots); + static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots); // FIXME : does not respect swap int insert(double one, double two, const SkDPoint& pt); void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2); @@ -256,21 +258,15 @@ public: int intersectRay(const SkDCubic&, const SkDLine&); void merge(const SkIntersections& , int , const SkIntersections& , int ); int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const; - void quickRemoveOne(int index, int replace); void removeOne(int index); void setCoincident(int index); int vertical(const SkDLine&, double top, double bottom, double x, bool flipped); int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped); int vertical(const SkDConic&, double top, double bottom, double x, bool flipped); int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped); - int verticalConic(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom, - SkScalar x, bool flipped); - int verticalCubic(const SkPoint a[4], SkScalar weight, SkScalar top, SkScalar bottom, - SkScalar x, bool flipped); - int verticalLine(const SkPoint a[2], SkScalar weight, SkScalar top, SkScalar bottom, - SkScalar x, bool flipped); - int verticalQuad(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom, - SkScalar x, bool flipped); + static double VerticalIntercept(const SkDLine& line, double x); + static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots); + static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots); int depth() const { #ifdef SK_DEBUG @@ -280,6 +276,7 @@ public: #endif } + int debugCoincidentUsed() const; void dump() const; // implemented for testing only private: @@ -303,7 +300,4 @@ private: #endif }; -extern int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar weight, - SkScalar top, SkScalar bottom, SkScalar x, bool flipped); - #endif diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 52a98d0ba7..6e49c4977f 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -360,6 +360,10 @@ recomputeSector: fUnorderable = true; return false; } + if (stepUp != (fStart->t() < computedEnd->t())) { + fUnorderable = true; + return false; + } SkOpSpanBase* saveEnd = fEnd; fComputedEnd = fEnd = computedEnd; setSpans(); @@ -597,78 +601,6 @@ bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const { return true; } -// 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. -SkOpAngle* SkOpAngle::findFirst() { - SkOpAngle* best = this; - int bestStart = SkTMin(fSectorStart, fSectorEnd); - 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 - 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 @@ -816,26 +748,6 @@ int SkOpAngle::loopCount() const { return count; } -// OPTIMIZATION: can this be done better in after when angles are sorted? -bool SkOpAngle::markStops() { - SkOpAngle* angle = this; - int lastEnd = SkTMax(fSectorStart, fSectorEnd); - do { - angle = angle->fNext; - if (!angle) { - return false; - } - 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); - return true; -} - bool SkOpAngle::merge(SkOpAngle* angle) { SkASSERT(fNext); SkASSERT(angle->fNext); @@ -968,7 +880,6 @@ void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) { SkASSERT(start != end); fNext = NULL; fComputeSector = fComputedSector = fCheckCoincidence = false; - fStop = false; setSpans(); setSector(); SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1); @@ -1157,11 +1068,6 @@ deferTilLater: } } -int SkOpAngle::sign() const { - SkASSERT(fStart->t() != fEnd->t()); - return fStart->t() < fEnd->t() ? -1 : 1; -} - SkOpSpan* SkOpAngle::starter() { return fStart->starter(fEnd); } diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index 7088dd716f..dba3f3ffac 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -42,7 +42,7 @@ struct SkOpAngle { return SkDEBUGRELEASE(fID, -1); } -#if DEBUG_SORT || DEBUG_SWAP_TOP +#if DEBUG_SORT void debugLoop() const; #endif @@ -51,6 +51,7 @@ struct SkOpAngle { #endif const SkOpPtT* debugPtT(int id) const; const SkOpSegment* debugSegment(int id) const; + int debugSign() const; const SkOpSpanBase* debugSpan(int id) const; void debugValidate() const; void debugValidateNext() const; // in debug builds, verify that angle loop is uncorrupted @@ -69,14 +70,12 @@ struct SkOpAngle { bool endsIntersect(SkOpAngle* ); bool endToSide(const SkOpAngle* rh, bool* inside) const; - SkOpAngle* findFirst(); int findSector(SkPath::Verb verb, double x, double y) const; SkOpGlobalState* globalState() const; void insert(SkOpAngle* ); SkOpSpanBase* lastMarked() const; bool loopContains(const SkOpAngle* ) const; int loopCount() const; - bool markStops(); bool merge(SkOpAngle* ); double midT() const; bool midToSide(const SkOpAngle* rh, bool* inside) const; @@ -112,7 +111,6 @@ struct SkOpAngle { void setSector(); void setSpans(); - int sign() const; SkOpSpanBase* start() const { return fStart; @@ -138,7 +136,6 @@ struct SkOpAngle { int8_t fSectorStart; // in 32nds of a circle int8_t fSectorEnd; bool fIsCurve; - bool fStop; // set if ordered angle is greater than the previous bool fUnorderable; bool fUnorderedSweep; // set when a cubic's first control point between the sweep vectors bool fComputeSector; diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h index 84bc832e9f..4d906e1af1 100644 --- a/src/pathops/SkOpCoincidence.h +++ b/src/pathops/SkOpCoincidence.h @@ -36,6 +36,7 @@ public: bool apply(); bool contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, SkOpPtT* oppPtTEnd, bool flipped); + void debugShowCoincidence() const; void detach(SkCoincidentSpans* ); void dump() const; void expand(); diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index 107c83169b..178ba3e89c 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -37,28 +37,6 @@ SkOpSegment* SkOpContour::addCurve(SkPath::Verb verb, const SkPoint pts[4], return NULL; } -SkOpSegment* SkOpContour::nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase** end) { - int segmentCount = fSortedSegments.count(); - SkASSERT(segmentCount > 0); - for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) { - SkOpSegment* testSegment = fSortedSegments[sortedIndex]; - if (testSegment->done()) { - continue; - } - SkOpSpanBase* span = testSegment->head(); - SkOpSpanBase* testS, * testE; - while (SkOpSegment::NextCandidate(span, &testS, &testE)) { - if (!testSegment->isVertical(testS, testE)) { - *start = testS; - *end = testE; - return testSegment; - } - span = span->upCast()->next(); - } - } - return NULL; -} - void SkOpContour::toPath(SkPathWriter* path) const { const SkPoint& pt = fHead.pts()[0]; path->deferredMove(pt); @@ -69,41 +47,6 @@ void SkOpContour::toPath(SkPathWriter* path) const { path->close(); } -void SkOpContour::topSortableSegment(const SkDPoint& topLeft, SkDPoint* bestXY, - SkOpSegment** topStart) { - int segmentCount = fSortedSegments.count(); - SkASSERT(segmentCount > 0); - int sortedIndex = fFirstSorted; - fDone = true; // may be cleared below - for ( ; sortedIndex < segmentCount; ++sortedIndex) { - SkOpSegment* testSegment = fSortedSegments[sortedIndex]; - if (testSegment->done()) { - if (sortedIndex == fFirstSorted) { - ++fFirstSorted; - } - continue; - } - fDone = false; - SkDPoint testXY = testSegment->activeLeftTop(NULL); - if (*topStart) { - if (testXY.fY < topLeft.fY) { - continue; - } - if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { - continue; - } - if (bestXY->fY < testXY.fY) { - continue; - } - if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { - continue; - } - } - *topStart = testSegment; - *bestXY = testXY; - } -} - SkOpSegment* SkOpContour::undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) { SkOpSegment* segment = &fHead; do { diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 9abf38238b..dd5dbb40ca 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -12,6 +12,8 @@ #include "SkTSort.h" class SkChunkAlloc; +enum class SkOpRayDir; +struct SkOpRayHit; class SkPathWriter; class SkOpContour { @@ -106,7 +108,7 @@ public: } int debugIndent() const { - return SkDEBUGRELEASE(fIndent, 0); + return SkDEBUGRELEASE(fDebugIndent, 0); } #if DEBUG_ACTIVE_SPANS @@ -119,23 +121,23 @@ public: #endif const SkOpAngle* debugAngle(int id) const { - return SkDEBUGRELEASE(globalState()->debugAngle(id), NULL); + return SkDEBUGRELEASE(this->globalState()->debugAngle(id), NULL); } SkOpContour* debugContour(int id) { - return SkDEBUGRELEASE(globalState()->debugContour(id), NULL); + return SkDEBUGRELEASE(this->globalState()->debugContour(id), NULL); } const SkOpPtT* debugPtT(int id) const { - return SkDEBUGRELEASE(globalState()->debugPtT(id), NULL); + return SkDEBUGRELEASE(this->globalState()->debugPtT(id), NULL); } const SkOpSegment* debugSegment(int id) const { - return SkDEBUGRELEASE(globalState()->debugSegment(id), NULL); + return SkDEBUGRELEASE(this->globalState()->debugSegment(id), NULL); } const SkOpSpanBase* debugSpan(int id) const { - return SkDEBUGRELEASE(globalState()->debugSpan(id), NULL); + return SkDEBUGRELEASE(this->globalState()->debugSpan(id), NULL); } SkOpGlobalState* globalState() const { @@ -159,9 +161,17 @@ public: return fDone; } - void dump(); - void dumpAll(); + void dump() const; + void dumpAll() const; void dumpAngles() const; + void dumpContours() const; + void dumpContoursAll() const; + void dumpContoursAngles() const; + void dumpContoursPts() const; + void dumpContoursPt(int segmentID) const; + void dumpContoursSegment(int segmentID) const; + void dumpContoursSpan(int segmentID) const; + void dumpContoursSpans() const; void dumpPt(int ) const; void dumpPts() const; void dumpPtsX() const; @@ -174,6 +184,8 @@ public: return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())]; } + SkOpSpan* findSortableTop(SkOpContour* ); + SkOpSegment* first() { SkASSERT(fCount > 0); return &fHead; @@ -184,8 +196,8 @@ public: return &fHead; } - void indentDump() { - SkDEBUGCODE(fIndent += 2); + void indentDump() const { + SkDEBUGCODE(fDebugIndent += 2); } void init(SkOpGlobalState* globalState, bool operand, bool isXor) { @@ -236,8 +248,6 @@ public: return fNext; } - SkOpSegment* nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase** end); - bool operand() const { return fOperand; } @@ -246,10 +256,12 @@ public: return fOppXor; } - void outdentDump() { - SkDEBUGCODE(fIndent -= 2); + void outdentDump() const { + SkDEBUGCODE(fDebugIndent -= 2); } + void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkChunkAlloc* ); + void remove(SkOpContour* contour) { if (contour == this) { SkASSERT(fCount == 0); @@ -271,9 +283,10 @@ public: fNext = NULL; fCount = 0; fDone = false; + fTopsFound = false; SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin)); SkDEBUGCODE(fFirstSorted = -1); - SkDEBUGCODE(fIndent = 0); + SkDEBUGCODE(fDebugIndent = 0); } void setBounds() { @@ -316,15 +329,6 @@ public: } while ((segment = segment->next())); } - void sortSegments() { - SkOpSegment* segment = &fHead; - do { - *fSortedSegments.append() = segment; - } while ((segment = segment->next())); - SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); - fFirstSorted = 0; - } - const SkPoint& start() const { return fHead.pts()[0]; } @@ -344,7 +348,6 @@ public: } void toPath(SkPathWriter* path) const; - void topSortableSegment(const SkDPoint& topLeft, SkDPoint* bestXY, SkOpSegment** topStart); SkOpSegment* undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr); private: @@ -352,16 +355,19 @@ private: SkOpSegment fHead; SkOpSegment* fTail; SkOpContour* fNext; - SkTDArray<SkOpSegment*> fSortedSegments; // set by find top segment SkPathOpsBounds fBounds; int fCount; int fFirstSorted; bool fDone; // set by find top segment + bool fTopsFound; bool fOperand; // true for the second argument to a binary operator bool fXor; // set if original path had even-odd fill bool fOppXor; // set if opposite path had even-odd fill SkDEBUGCODE(int fID); - SkDEBUGCODE(int fIndent); + SkDEBUGCODE(mutable int fDebugIndent); +}; + +class SkOpContourHead : public SkOpContour { }; #endif diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index ce35f846b3..de813cb7c9 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -102,47 +102,6 @@ SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** sta return other->activeAngleInner(oSpan, startPtr, endPtr, done, sortable); } -SkDPoint SkOpSegment::activeLeftTop(SkOpSpanBase** firstSpan) { - SkASSERT(!done()); - SkDPoint topPt = {SK_ScalarMax, SK_ScalarMax}; - // see if either end is not done since we want smaller Y of the pair - bool lastDone = true; - SkOpSpanBase* span = &fHead; - SkOpSpanBase* lastSpan = NULL; - do { - if (!lastDone || (!span->final() && !span->upCast()->done())) { - const SkPoint& xy = span->pt(); - if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) { - topPt = xy; - if (firstSpan) { - *firstSpan = span; - } - } - if (fVerb != SkPath::kLine_Verb && !lastDone) { - double curveTopT; - SkDCurve curve; - this->subDivide(lastSpan, span, &curve); - SkDPoint curveTop = (curve.*Top[fVerb])(fPts, fWeight, lastSpan->t(), span->t(), - &curveTopT); - if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY && topPt.fX > curveTop.fX)) { - topPt = curveTop; - if (firstSpan) { - const SkPoint& lastXY = lastSpan->pt(); - *firstSpan = lastXY.fY > xy.fY || (lastXY.fY == xy.fY && lastXY.fX > xy.fX) - ? span : lastSpan; - } - } - } - lastSpan = span; - } - if (span->final()) { - break; - } - lastDone = span->upCast()->done(); - } while ((span = span->upCast()->next())); - return topPt; -} - bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, SkPathOp op) { int sumMiWinding = this->updateWinding(end, start); @@ -278,88 +237,6 @@ SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* alloc return result; } -SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr, - SkChunkAlloc* allocator) { - SkOpSpan* startSpan = fTail.prev(); - SkASSERT(startSpan); - SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); - *anglePtr = angle; - angle->set(&fTail, startSpan); - fTail.setFromAngle(angle); - SkOpSegment* other = NULL; // these initializations silence a release build warning - SkOpSpan* oStartSpan = NULL; - SkOpSpanBase* oEndSpan = NULL; - SkOpPtT* ptT = fTail.ptT(), * startPtT = ptT; - while ((ptT = ptT->next()) != startPtT) { - other = ptT->segment(); - oStartSpan = ptT->span()->upCastable(); - if (oStartSpan && oStartSpan->windValue()) { - oEndSpan = oStartSpan->next(); - break; - } - oEndSpan = ptT->span(); - oStartSpan = oEndSpan->prev(); - if (oStartSpan && oStartSpan->windValue()) { - break; - } - } - if (!oStartSpan) { - return NULL; - } - SkOpAngle* oAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); - oAngle->set(oStartSpan, oEndSpan); - oStartSpan->setToAngle(oAngle); - *otherPtr = other; - return oAngle; -} - -SkOpAngle* SkOpSegment::addSingletonAngles(int step, SkChunkAlloc* allocator) { - SkOpSegment* other; - SkOpAngle* angle, * otherAngle; - if (step > 0) { - otherAngle = addSingletonAngleUp(&other, &angle, allocator); - } else { - otherAngle = addSingletonAngleDown(&other, &angle, allocator); - } - if (!otherAngle) { - return NULL; - } - angle->insert(otherAngle); - return angle; -} - -SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr, - SkChunkAlloc* allocator) { - SkOpSpanBase* endSpan = fHead.next(); - SkASSERT(endSpan); - SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); - *anglePtr = angle; - angle->set(&fHead, endSpan); - fHead.setToAngle(angle); - SkOpSegment* other = NULL; // these initializations silence a release build warning - SkOpSpan* oStartSpan = NULL; - SkOpSpanBase* oEndSpan = NULL; - SkOpPtT* ptT = fHead.ptT(), * startPtT = ptT; - while ((ptT = ptT->next()) != startPtT) { - other = ptT->segment(); - oEndSpan = ptT->span(); - oStartSpan = oEndSpan->prev(); - if (oStartSpan && oStartSpan->windValue()) { - break; - } - oStartSpan = oEndSpan->upCastable(); - if (oStartSpan && oStartSpan->windValue()) { - oEndSpan = oStartSpan->next(); - break; - } - } - SkOpAngle* oAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); - oAngle->set(oEndSpan, oStartSpan); - oEndSpan->setFromAngle(oAngle); - *otherPtr = other; - return oAngle; -} - SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) { debugValidate(); SkPoint pt = this->ptAtT(t); @@ -437,14 +314,6 @@ void SkOpSegment::align() { debugValidate(); } -bool SkOpSegment::BetweenTs(const SkOpSpanBase* lesser, double testT, - const SkOpSpanBase* greater) { - if (lesser->t() > greater->t()) { - SkTSwap<const SkOpSpanBase*>(lesser, greater); - } - return approximately_between(lesser->t(), testT, greater->t()); -} - void SkOpSegment::calcAngles(SkChunkAlloc* allocator) { bool activePrior = !fHead.isCanceled(); if (activePrior && !fHead.simple()) { @@ -494,20 +363,9 @@ void SkOpSegment::checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* al } while ((base = span->next())); } -// from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order -bool SkOpSegment::clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const { - SkASSERT(fVerb != SkPath::kLine_Verb); - if (fVerb != SkPath::kCubic_Verb) { - SkOpCurve edge; - this->subDivide(start, end, &edge); - return SkDQuad::Clockwise(edge, swap); - } - return SkDCubic::Clockwise(fPts, start->t(), end->t(), swap); -} - void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType includeType) { - const SkOpSegment* baseSegment = baseAngle->segment(); + SkOpSegment* baseSegment = baseAngle->segment(); int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); int sumSuWinding; bool binary = includeType >= SkOpAngle::kBinarySingle; @@ -534,9 +392,9 @@ void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle nextAngle->setLastMarked(last); } -void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, +void SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType includeType) { - const SkOpSegment* baseSegment = baseAngle->segment(); + SkOpSegment* baseSegment = baseAngle->segment(); int sumMiWinding = baseSegment->updateWinding(baseAngle); int sumSuWinding; bool binary = includeType >= SkOpAngle::kBinarySingle; @@ -634,102 +492,6 @@ int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, return start->starter(end)->windSum(); } -SkOpSpan* SkOpSegment::crossedSpanY(const SkPoint& basePt, double mid, bool opp, bool current, - SkScalar* bestY, double* hitT, bool* hitSomething, bool* vertical) { - SkScalar bottom = fBounds.fBottom; - *vertical = false; - if (bottom <= *bestY) { - return NULL; - } - SkScalar top = fBounds.fTop; - if (top >= basePt.fY) { - return NULL; - } - if (fBounds.fLeft > basePt.fX) { - return NULL; - } - if (fBounds.fRight < basePt.fX) { - return NULL; - } - if (fBounds.fLeft == fBounds.fRight) { - // if vertical, and directly above test point, wait for another one - *vertical = AlmostEqualUlps(basePt.fX, fBounds.fLeft); - return NULL; - } - // intersect ray starting at basePt with edge - SkIntersections intersections; - // OPTIMIZE: use specialty function that intersects ray with curve, - // returning t values only for curve (we don't care about t on ray) - intersections.allowNear(false); - int pts = (intersections.*CurveVertical[fVerb])(fPts, fWeight, top, bottom, basePt.fX, false); - if (pts == 0 || (current && pts == 1)) { - return NULL; - } - if (current) { - SkASSERT(pts > 1); - int closestIdx = 0; - double closest = fabs(intersections[0][0] - mid); - for (int idx = 1; idx < pts; ++idx) { - double test = fabs(intersections[0][idx] - mid); - if (closest > test) { - closestIdx = idx; - closest = test; - } - } - intersections.quickRemoveOne(closestIdx, --pts); - } - double bestT = -1; - for (int index = 0; index < pts; ++index) { - double foundT = intersections[0][index]; - if (approximately_less_than_zero(foundT) - || approximately_greater_than_one(foundT)) { - continue; - } - SkScalar testY = (*CurvePointAtT[fVerb])(fPts, fWeight, foundT).fY; - if (approximately_negative(testY - *bestY) - || approximately_negative(basePt.fY - testY)) { - continue; - } - if (pts > 1 && fVerb == SkPath::kLine_Verb) { - *vertical = true; - return NULL; // if the intersection is edge on, wait for another one - } - if (fVerb > SkPath::kLine_Verb) { - SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, foundT).fX; - if (approximately_zero(dx)) { - *vertical = true; - return NULL; // hit vertical, wait for another one - } - } - *bestY = testY; - bestT = foundT; - } - if (bestT < 0) { - return NULL; - } - SkASSERT(bestT >= 0); - SkASSERT(bestT < 1); - SkOpSpanBase* testTSpanBase = &this->fHead; - SkOpSpanBase* nextTSpan; - double endT = 0; - do { - nextTSpan = testTSpanBase->upCast()->next(); - endT = nextTSpan->t(); - if (endT >= bestT) { - break; - } - testTSpanBase = nextTSpan; - } while (testTSpanBase); - SkOpSpan* bestTSpan = NULL; - SkOpSpan* testTSpan = testTSpanBase->upCast(); - if (!testTSpan->isCanceled()) { - *hitT = bestT; - bestTSpan = testTSpan; - *hitSomething = true; - } - return bestTSpan; -} - void SkOpSegment::detach(const SkOpSpan* span) { if (span->done()) { --fDoneCount; @@ -1036,126 +798,6 @@ SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** n return nextSegment; } -SkOpSegment* SkOpSegment::findTop(bool firstPass, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, - bool* unsortable, SkChunkAlloc* allocator) { - // iterate through T intersections and return topmost - // topmost tangent from y-min to first pt is closer to horizontal - SkASSERT(!done()); - SkOpSpanBase* firstT = NULL; - (void) this->activeLeftTop(&firstT); - if (!firstT) { - *unsortable = !firstPass; - firstT = &fHead; - while (firstT->upCast()->done()) { - firstT = firstT->upCast()->next(); - } - *startPtr = firstT; - *endPtr = firstT->upCast()->next(); - return this; - } - // sort the edges to find the leftmost - int step = 1; - SkOpSpanBase* end; - if (firstT->final() || firstT->upCast()->done()) { - step = -1; - end = firstT->prev(); - SkASSERT(end); - } else { - end = firstT->upCast()->next(); - } - // 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) - SkASSERT(firstT != end); - SkOpAngle* markAngle = spanToAngle(firstT, end); - if (!markAngle) { - markAngle = addSingletonAngles(step, allocator); - } - if (!markAngle) { - return NULL; - } - if (!markAngle->markStops()) { - return NULL; - } - const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle - : markAngle->findFirst(); - if (!baseAngle) { - return NULL; // nothing to do - } - SkScalar top = SK_ScalarMax; - const SkOpAngle* firstAngle = NULL; - const SkOpAngle* angle = baseAngle; -#if DEBUG_SWAP_TOP - SkDebugf("-%s- baseAngle\n", __FUNCTION__); - baseAngle->debugLoop(); -#endif - do { - if (!angle->unorderable()) { - const SkOpSegment* next = angle->segment(); - SkPathOpsBounds bounds; - next->subDivideBounds(angle->end(), angle->start(), &bounds); - if (top > bounds.fTop) { - top = bounds.fTop; - firstAngle = angle; - } - } - angle = angle->next(); - } while (angle != baseAngle); - if (!firstAngle) { - return NULL; // if all are unorderable, give up - } -#if DEBUG_SWAP_TOP - SkDebugf("-%s- firstAngle\n", __FUNCTION__); - firstAngle->debugLoop(); -#endif - // skip edges that have already been processed - angle = firstAngle; - SkOpSegment* leftSegment = NULL; - bool looped = false; - do { - *unsortable = angle->unorderable(); - if (firstPass || !*unsortable) { - leftSegment = angle->segment(); - *startPtr = angle->end(); - *endPtr = angle->start(); - const SkOpSpan* firstSpan = (*startPtr)->starter(*endPtr); - if (!firstSpan->done()) { - break; - } - } - angle = angle->next(); - looped = true; - } while (angle != firstAngle); - if (angle == firstAngle && looped) { - return NULL; - } - if (leftSegment->verb() >= SkPath::kQuad_Verb) { - SkOpSpanBase* start = *startPtr; - SkOpSpanBase* end = *endPtr; - bool swap; - bool cw = leftSegment->clockwise(start, end, &swap); -#if DEBUG_SWAP_TOP - SkDebugf("%s id=%d s=%1.9g e=%1.9g (%c) cw=%d swap=%d inflections=%d monotonic=%d\n", - __FUNCTION__, leftSegment->debugID(), start->t(), end->t(), - start->t() < end->t() ? '-' : '+', cw, - swap, leftSegment->debugInflections(start, end), - leftSegment->monotonicInY(start, end)); -#endif - if (!cw && swap) { - // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first - // sorted but merely the first not already processed (i.e., not done) - SkTSwap(*startPtr, *endPtr); - } - // FIXME: clockwise isn't reliable -- try computing swap from tangent ? - } else { -#if DEBUG_SWAP_TOP - SkDebugf("%s id=%d s=%1.9g e=%1.9g (%c) cw=%d swap=%d inflections=%d monotonic=%d\n", - __FUNCTION__, leftSegment->debugID(), (*startPtr)->t(), (*endPtr)->t(), - (*startPtr)->t() < (*endPtr)->t() ? '-' : '+', -1, -1, -1, 1); -#endif - } - return leftSegment; -} - SkOpGlobalState* SkOpSegment::globalState() const { return contour()->globalState(); } @@ -1169,6 +811,7 @@ void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkP fCubicType = SkDCubic::kUnsplit_SkDCubicType; fCount = 0; fDoneCount = 0; + fTopsFound = false; fVisited = false; SkOpSpan* zeroSpan = &fHead; zeroSpan->init(this, NULL, 0, fPts[0]); @@ -1178,68 +821,6 @@ void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkP SkDEBUGCODE(fID = globalState()->nextSegmentID()); } -void SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, - SkOpAngle::IncludeType angleIncludeType) { - int local = SkOpSegment::SpanSign(start, end); - SkDEBUGCODE(bool success); - if (angleIncludeType == SkOpAngle::kBinarySingle) { - int oppLocal = SkOpSegment::OppSign(start, end); - SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, oppLocal, NULL); - // OPTIMIZATION: the reverse mark and chase could skip the first marking - SkDEBUGCODE(success |=) markAndChaseWinding(end, start, local, oppLocal, NULL); - } else { - SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, NULL); - // OPTIMIZATION: the reverse mark and chase could skip the first marking - SkDEBUGCODE(success |=) markAndChaseWinding(end, start, local, NULL); - } - SkASSERT(success); -} - -/* -when we start with a vertical intersect, we try to use the dx to determine if the edge is to -the left or the right of vertical. This determines if we need to add the span's -sign or not. However, this isn't enough. -If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed. -If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed -from has the same x direction as this span, the winding should change. If the dx is opposite, then -the same winding is shared by both. -*/ -bool SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHit, - int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx) { - SkASSERT(this == start->segment()); - SkASSERT(hitDx || !winding); - SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX; -// SkASSERT(dx); - int windVal = start->starter(end)->windValue(); -#if DEBUG_WINDING_AT_T - SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding, - hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); -#endif - int sideWind = winding + (dx < 0 ? windVal : -windVal); - if (abs(winding) < abs(sideWind)) { - winding = sideWind; - } - SkDEBUGCODE(int oppLocal = SkOpSegment::OppSign(start, end)); - SkASSERT(hitOppDx || !oppWind || !oppLocal); - int oppWindVal = start->starter(end)->oppValue(); - if (!oppWind) { - oppWind = dx < 0 ? oppWindVal : -oppWindVal; - } else if (hitOppDx * dx >= 0) { - int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal); - if (abs(oppWind) < abs(oppSideWind)) { - oppWind = oppSideWind; - } - } -#if DEBUG_WINDING_AT_T - SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind); -#endif - // if this fails to mark (because the edges are too small) inform caller to try again - bool success = markAndChaseWinding(start, end, winding, oppWind, NULL); - // OPTIMIZATION: the reverse mark and chase could skip the first marking - success |= markAndChaseWinding(end, start, winding, oppWind, NULL); - return success; -} - bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { SkDPoint cPt = this->dPtAtT(t); SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); @@ -1306,8 +887,7 @@ bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, while ((other = other->nextChase(&start, &step, &spanStart, &last))) { if (spanStart->windSum() != SK_MinS32) { if (this->operand() == other->operand()) { - SkASSERT(spanStart->windSum() == winding); - if (spanStart->oppSum() != oppWinding) { + if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { this->globalState()->setWindingFailed(); return false; } @@ -1438,39 +1018,6 @@ static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { return NULL; } -bool SkOpSegment::monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* end) const { - SkASSERT(fVerb != SkPath::kLine_Verb); - if (fVerb == SkPath::kQuad_Verb) { - SkDQuad dst = SkDQuad::SubDivide(fPts, start->t(), end->t()); - return dst.monotonicInY(); - } - if (fVerb == SkPath::kConic_Verb) { - SkDConic dst = SkDConic::SubDivide(fPts, fWeight, start->t(), end->t()); - return dst.monotonicInY(); - } - SkASSERT(fVerb == SkPath::kCubic_Verb); - SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t()); - if (dst.monotonicInY()) { - return true; - } - SkDCubic whole; - whole.set(fPts); - return whole.monotonicInY(); -} - -bool SkOpSegment::NextCandidate(SkOpSpanBase* span, SkOpSpanBase** start, - SkOpSpanBase** end) { - while (span->final() || span->upCast()->done()) { - if (span->final()) { - return false; - } - span = span->upCast()->next(); - } - *start = span; - *end = span->upCast()->next(); - return true; -} - SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, SkOpSpanBase** last) const { SkOpSpanBase* origStart = *startPtr; @@ -1499,7 +1046,7 @@ SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpS return NULL; } #if DEBUG_WINDING - if (angle->sign() != next->sign() && !angle->segment()->contour()->isXor() + if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() && !next->segment()->contour()->isXor()) { SkDebugf("%s mismatched signs\n", __FUNCTION__); } @@ -1558,7 +1105,7 @@ void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc SkASSERT(ptT->span() == span); while ((ptT = ptT->next()) != spanStopPtT) { SkOpSegment* opp = ptT->span()->segment(); - if (opp->setVisited()) { + if (!opp->setVisited()) { continue; } if (opp->verb() == SkPath::kLine_Verb) { @@ -2024,19 +1571,6 @@ bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, return true; } -void SkOpSegment::subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end, - SkPathOpsBounds* bounds) const { - SkDCurve edge; - subDivide(start, end, &edge); - (edge.*SetBounds[fVerb])(fPts, fWeight, start->t(), end->t(), bounds); -} - -SkDPoint SkOpSegment::top(const SkOpSpanBase* start, const SkOpSpanBase* end, double* topT) const { - SkDCurve edge; - subDivide(start, end, &edge); - return (edge.*Top[fVerb])(fPts, fWeight, start->t(), end->t(), topT); -} - void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { SkOpSpan* span = this->head(); do { @@ -2072,10 +1606,19 @@ int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { return updateOppWinding(startSpan, endSpan); } -int SkOpSegment::updateWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { - const SkOpSpan* lesser = start->starter(end); +int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { + SkOpSpan* lesser = start->starter(end); int winding = lesser->windSum(); if (winding == SK_MinS32) { + SkOpGlobalState* globals = this->globalState(); + SkOpContour* contourHead = globals->contourHead(); + int windTry = 0; + while (!lesser->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) { + ; + } + winding = lesser->windSum(); + } + if (winding == SK_MinS32) { return winding; } int spanWinding = SkOpSegment::SpanSign(start, end); @@ -2086,15 +1629,15 @@ int SkOpSegment::updateWinding(const SkOpSpanBase* start, const SkOpSpanBase* en return winding; } -int SkOpSegment::updateWinding(const SkOpAngle* angle) const { - const SkOpSpanBase* startSpan = angle->start(); - const SkOpSpanBase* endSpan = angle->end(); +int SkOpSegment::updateWinding(SkOpAngle* angle) { + SkOpSpanBase* startSpan = angle->start(); + SkOpSpanBase* endSpan = angle->end(); return updateWinding(endSpan, startSpan); } -int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const { - const SkOpSpanBase* startSpan = angle->start(); - const SkOpSpanBase* endSpan = angle->end(); +int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { + SkOpSpanBase* startSpan = angle->start(); + SkOpSpanBase* endSpan = angle->end(); return updateWinding(startSpan, endSpan); } @@ -2110,41 +1653,6 @@ bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { return result; } -int SkOpSegment::windingAtT(double tHit, const SkOpSpan* span, bool crossOpp, - SkScalar* dx) const { - if (approximately_zero(tHit - span->t())) { // if we hit the end of a span, disregard - return SK_MinS32; - } - int winding = crossOpp ? span->oppSum() : span->windSum(); - SkASSERT(winding != SK_MinS32); - int windVal = crossOpp ? span->oppValue() : span->windValue(); -#if DEBUG_WINDING_AT_T - SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__, - debugID(), crossOpp, tHit, span->t(), winding, windVal); -#endif - // see if a + change in T results in a +/- change in X (compute x'(T)) - *dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX; - if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) { - *dx = fPts[2].fX - fPts[1].fX - *dx; - } - if (*dx == 0) { -#if DEBUG_WINDING_AT_T - SkDebugf(" dx=0 winding=SK_MinS32\n"); -#endif - return SK_MinS32; - } - if (windVal < 0) { // reverse sign if opp contour traveled in reverse - *dx = -*dx; - } - if (winding * *dx > 0) { // if same signs, result is negative - winding += *dx > 0 ? -windVal : windVal; - } -#if DEBUG_WINDING_AT_T - SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding); -#endif - return winding; -} - int SkOpSegment::windSum(const SkOpAngle* angle) const { const SkOpSpan* minSpan = angle->start()->starter(angle->end()); return minSpan->windSum(); diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index a762a66a5a..13b99c6f46 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -17,6 +17,8 @@ struct SkDCurve; class SkOpCoincidence; class SkOpContour; +enum class SkOpRayDir; +struct SkOpRayHit; class SkPathWriter; class SkOpSegment { @@ -41,8 +43,6 @@ public: bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op, int* sumMiWinding, int* sumSuWinding); - SkDPoint activeLeftTop(SkOpSpanBase** firstT); - bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end); bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding); @@ -79,9 +79,6 @@ public: } SkOpPtT* addMissing(double t, SkOpSegment* opp, SkChunkAlloc* ); - SkOpAngle* addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** , SkChunkAlloc* ); - SkOpAngle* addSingletonAngles(int step, SkChunkAlloc* ); - SkOpAngle* addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** , SkChunkAlloc* ); SkOpAngle* addStartSpan(SkChunkAlloc* allocator) { SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); @@ -101,7 +98,6 @@ public: SkOpPtT* addT(double t, AllowAlias , SkChunkAlloc* ); void align(); - static bool BetweenTs(const SkOpSpanBase* lesser, double testT, const SkOpSpanBase* greater); const SkPathOpsBounds& bounds() const { return fBounds; @@ -114,10 +110,9 @@ public: void calcAngles(SkChunkAlloc*); void checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); void checkNearCoincidence(SkOpAngle* ); - bool clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const; static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); - static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, + static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType); @@ -129,9 +124,6 @@ public: return fCount; } - SkOpSpan* crossedSpanY(const SkPoint& basePt, double mid, bool opp, bool current, - SkScalar* bestY, double* hitT, bool* hitSomething, bool* vertical); - void debugAddAngle(double startT, double endT, SkChunkAlloc*); const SkOpAngle* debugAngle(int id) const; SkOpContour* debugContour(int id); @@ -140,10 +132,6 @@ public: return SkDEBUGRELEASE(fID, -1); } -#if DEBUG_SWAP_TOP - int debugInflections(const SkOpSpanBase* start, const SkOpSpanBase* end) const; -#endif - SkOpAngle* debugLastAngle(); const SkOpPtT* debugPtT(int id) const; void debugReset(); @@ -184,6 +172,7 @@ public: void dumpAngles() const; void dumpCoin() const; void dumpPts() const; + void dumpPtsInner() const; SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, @@ -191,8 +180,7 @@ public: SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable); SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable); - SkOpSegment* findTop(bool firstPass, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, - bool* unsortable, SkChunkAlloc* ); + SkOpSpan* findSortableTop(SkOpContour* ); SkOpGlobalState* globalState() const; const SkOpSpan* head() const { @@ -204,10 +192,6 @@ public: } void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb); - void initWinding(SkOpSpanBase* start, SkOpSpanBase* end, - SkOpAngle::IncludeType angleIncludeType); - bool initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHit, int winding, - SkScalar hitDx, int oppWind, SkScalar hitOppDx); SkOpSpan* insert(SkOpSpan* prev, SkChunkAlloc* allocator) { SkOpSpan* result = SkOpTAllocator<SkOpSpan>::Allocate(allocator); @@ -259,7 +243,6 @@ public: bool markWinding(SkOpSpan* , int winding, int oppWinding); bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const; void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); - bool monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* end) const; void moveMultiples(); void moveNearby(); @@ -267,7 +250,6 @@ public: return fNext; } - static bool NextCandidate(SkOpSpanBase* span, SkOpSpanBase** start, SkOpSpanBase** end); SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const; bool operand() const; @@ -301,6 +283,9 @@ public: bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const; + void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, + SkChunkAlloc* allocator); + void resetVisited() { fVisited = false; } @@ -353,8 +338,6 @@ public: bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const; bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkOpCurve* result) const; - void subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end, - SkPathOpsBounds* bounds) const; const SkOpSpanBase* tail() const { return &fTail; @@ -364,19 +347,13 @@ public: return &fTail; } - static double TAtMid(const SkOpSpanBase* start, const SkOpSpanBase* end, double mid) { - return start->t() * (1 - mid) + end->t() * mid; - } - - SkDPoint top(const SkOpSpanBase* start, const SkOpSpanBase* end, double* topT) const; - void undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end); int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const; int updateOppWinding(const SkOpAngle* angle) const; int updateOppWindingReverse(const SkOpAngle* angle) const; - int updateWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const; - int updateWinding(const SkOpAngle* angle) const; - int updateWindingReverse(const SkOpAngle* angle) const; + int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end); + int updateWinding(SkOpAngle* angle); + int updateWindingReverse(const SkOpAngle* angle); static bool UseInnerWinding(int outerWinding, int innerWinding); @@ -388,7 +365,7 @@ public: return fWeight; } - int windingAtT(double tHit, const SkOpSpan* span, bool crossOpp, SkScalar* dx) const; + SkOpSpan* windingSpanAtT(double tHit); int windSum(const SkOpAngle* angle) const; SkPoint* writablePt(bool end) { @@ -408,6 +385,7 @@ private: int fDoneCount; // number of processed spans (zero initially) SkPath::Verb fVerb; SkDCubic::CubicType fCubicType; + bool fTopsFound; bool fVisited; // used by missing coincidence check SkDEBUGCODE(int fID); }; diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp index b75a692f74..9c9e07f985 100755 --- a/src/pathops/SkOpSpan.cpp +++ b/src/pathops/SkOpSpan.cpp @@ -86,65 +86,6 @@ SkOpSegment* SkOpPtT::segment() { return span()->segment(); } -// find the starting or ending span with an existing loop of angles -// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier? -// FIXME? assert that only one other span has a valid windValue or oppValue -bool SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) { - SkOpAngle* angle; - if (checkFrom) { - if (!this->final()) { - return false; - } - if (this->fromAngle()) { - SkASSERT(this->fromAngle()->loopCount() == 2); - return true; - } - angle = this->segment()->addEndSpan(allocator); - } else { - SkASSERT(this->t() == 0); - SkOpSpan* span = this->upCast(); - if (span->toAngle()) { - SkASSERT(span->toAngle()->loopCount() == 2); - SkASSERT(!span->fromAngle()); - span->setFromAngle(span->toAngle()->next()); - return true; - } - angle = this->segment()->addStartSpan(allocator); - } - SkOpPtT* ptT = this->ptT(); - SkOpSpanBase* oSpanBase; - SkOpSpan* oSpan; - SkOpSegment* other; - do { - ptT = ptT->next(); - oSpanBase = ptT->span(); - oSpan = oSpanBase->upCastable(); - other = oSpanBase->segment(); - if (oSpan && oSpan->windValue()) { - break; - } - if (oSpanBase->t() == 0) { - continue; - } - SkOpSpan* oFromSpan = oSpanBase->prev(); - SkASSERT(oFromSpan->t() < 1); - if (oFromSpan->windValue()) { - break; - } - } while (ptT != this->ptT()); - SkOpAngle* oAngle; - if (checkFrom) { - oAngle = other->addStartSpan(allocator); - SkASSERT(oSpan && !oSpan->final()); - SkASSERT(oAngle == oSpan->toAngle()); - } else { - oAngle = other->addEndSpan(allocator); - SkASSERT(oAngle == oSpanBase->fromAngle()); - } - angle->insert(oAngle); - return true; -} - void SkOpSpanBase::align() { if (this->fAligned) { return; @@ -308,11 +249,6 @@ tryNextRemainder: fSpanAdds += span->fSpanAdds; } -void SkOpSpan::applyCoincidence(SkOpSpan* opp) { - SkASSERT(!final()); - SkASSERT(0); // incomplete -} - bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { SkASSERT(this->segment() != segment); const SkOpSpan* next = fCoincident; @@ -345,6 +281,7 @@ void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoin fWindSum = fOppSum = SK_MinS32; fWindValue = 1; fOppValue = 0; + fTopTTry = 0; fChased = fDone = false; segment->bumpCount(); } @@ -358,3 +295,13 @@ void SkOpSpan::setOppSum(int oppSum) { SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(oppSum) <= DEBUG_LIMIT_WIND_SUM); fOppSum = oppSum; } + +void SkOpSpan::setWindSum(int windSum) { + SkASSERT(!final()); + if (fWindSum != SK_MinS32 && fWindSum != windSum) { + this->globalState()->setWindingFailed(); + return; + } + SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(windSum) <= DEBUG_LIMIT_WIND_SUM); + fWindSum = windSum; +} diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index ee2f332440..1d535d2635 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -124,7 +124,6 @@ protected: class SkOpSpanBase { public: - bool addSimpleAngle(bool checkFrom , SkChunkAlloc* ); void align(); bool aligned() const { @@ -333,8 +332,6 @@ protected: // no direct access to internals to avoid treating a span base as a class SkOpSpan : public SkOpSpanBase { public: - void applyCoincidence(SkOpSpan* opp); - bool clearCoincident() { SkASSERT(!final()); if (fCoincident == this) { @@ -432,12 +429,7 @@ public: fToAngle = angle; } - void setWindSum(int windSum) { - SkASSERT(!final()); - SkASSERT(fWindSum == SK_MinS32 || fWindSum == windSum); - SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(windSum) <= DEBUG_LIMIT_WIND_SUM); - fWindSum = windSum; - } + void setWindSum(int windSum); void setWindValue(int windValue) { SkASSERT(!final()); @@ -446,6 +438,8 @@ public: fWindValue = windValue; } + bool sortableTop(SkOpContour* ); + SkOpAngle* toAngle() const { SkASSERT(!final()); return fToAngle; @@ -469,6 +463,7 @@ private: // no direct access to internals to avoid treating a span base as a sp 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 + int fTopTTry; // specifies direction and t value to try next bool fDone; // if set, this span to next higher T has been processed }; diff --git a/src/pathops/SkPathOpsBounds.h b/src/pathops/SkPathOpsBounds.h index 7b9daa3671..b99f36f5d9 100644 --- a/src/pathops/SkPathOpsBounds.h +++ b/src/pathops/SkPathOpsBounds.h @@ -47,19 +47,6 @@ struct SkPathOpsBounds : public SkRect { && AlmostLessOrEqualUlps(pt.fY, fBottom); } - // unlike isEmpty(), this permits lines, but not points - // FIXME: unused for now - bool isReallyEmpty() const { - // use !<= instead of > to detect NaN values - return !(fLeft <= fRight) || !(fTop <= fBottom) - || (fLeft == fRight && fTop == fBottom); - } - - void setPointBounds(const SkDPoint& pt) { - fLeft = fRight = SkDoubleToScalar(pt.fX); - fTop = fBottom = SkDoubleToScalar(pt.fY); - } - typedef SkRect INHERITED; }; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 05b370a1df..734b5f0819 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -11,106 +11,16 @@ #include "SkPathWriter.h" #include "SkTSort.h" -static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList, - SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, - double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) { - SkOpSpanBase* start = *startPtr; - SkOpSpanBase* end = *endPtr; - const double mid = *midPtr; - const SkOpSegment* current = *currentPtr; - double tAtMid = SkOpSegment::TAtMid(start, end, mid); - SkPoint basePt = current->ptAtT(tAtMid); - int contourCount = contourList.count(); - SkScalar bestY = SK_ScalarMin; - SkOpSegment* bestSeg = NULL; - SkOpSpan* bestTSpan = NULL; - bool bestOpp; - bool hitSomething = false; - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = contourList[cTest]; - bool testOpp = contour->operand() ^ current->operand() ^ opp; - if (basePt.fY < contour->bounds().fTop) { - continue; - } - if (bestY > contour->bounds().fBottom) { - continue; - } - SkOpSegment* testSeg = contour->first(); - SkASSERT(testSeg); - do { - SkScalar testY = bestY; - double testHit; - bool vertical; - SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp, - testSeg == current, &testY, &testHit, &hitSomething, &vertical); - if (!testTSpan) { - if (vertical) { - hitSomething = true; - bestSeg = NULL; - goto abortContours; // vertical encountered, return and try different point - } - continue; - } - if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) { - double baseT = start->t(); - double endT = end->t(); - double newMid = (testHit - baseT) / (endT - baseT); -#if DEBUG_WINDING - double midT = SkOpSegment::TAtMid(start, end, mid); - SkPoint midXY = current->ptAtT(midT); - double newMidT = SkOpSegment::TAtMid(start, end, newMid); - SkPoint newXY = current->ptAtT(newMidT); - SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" - " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, - current->debugID(), mid, newMid, - baseT, start->pt().fX, start->pt().fY, - baseT + mid * (endT - baseT), midXY.fX, midXY.fY, - baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, - endT, end->pt().fX, end->pt().fY); -#endif - *midPtr = newMid * 2; // calling loop with divide by 2 before continuing - return SK_MinS32; - } - bestSeg = testSeg; - *bestHit = testHit; - bestOpp = testOpp; - bestTSpan = testTSpan; - bestY = testY; - } while ((testSeg = testSeg->next())); - } -abortContours: - int result; - if (!bestSeg) { - result = hitSomething ? SK_MinS32 : 0; - } else { - if (bestTSpan->windSum() == SK_MinS32) { - *currentPtr = bestSeg; - *startPtr = bestTSpan; - *endPtr = bestTSpan->next(); - SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); - *tryAgain = true; - return 0; - } - result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx); - SkASSERT(result == SK_MinS32 || *bestDx); - } - double baseT = (*startPtr)->t(); - double endT = (*endPtr)->t(); - *bestHit = baseT + mid * (endT - baseT); - return result; -} - -SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr, +SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) { - int contourCount = contourList.count(); SkOpSegment* result; - for (int cIndex = 0; cIndex < contourCount; ++cIndex) { - SkOpContour* contour = contourList[cIndex]; + SkOpContour* contour = contourList; + do { result = contour->undoneSegment(startPtr, endPtr); if (result) { return result; } - } + } while ((contour = contour->next())); return NULL; } @@ -196,234 +106,41 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, } #if DEBUG_ACTIVE_SPANS -void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) { - int index; - for (index = 0; index < contourList.count(); ++ index) { - contourList[index]->debugShowActiveSpans(); - } -} -#endif - -static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList, - bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkDPoint* topLeft, - bool* unsortable, bool* done, SkChunkAlloc* allocator) { - SkOpSegment* result; - const SkOpSegment* lastTopStart = NULL; - SkOpSpanBase* lastStart = NULL, * lastEnd = NULL; - do { - SkDPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; - int contourCount = contourList.count(); - SkOpSegment* topStart = NULL; - *done = true; - for (int cIndex = 0; cIndex < contourCount; ++cIndex) { - SkOpContour* contour = contourList[cIndex]; - if (contour->done()) { - continue; - } - const SkPathOpsBounds& bounds = contour->bounds(); - if (bounds.fBottom < topLeft->fY) { - *done = false; - continue; - } - if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) { - *done = false; - continue; - } - contour->topSortableSegment(*topLeft, &bestXY, &topStart); - if (!contour->done()) { - *done = false; - } - } - if (!topStart) { - return NULL; - } - *topLeft = bestXY; - result = topStart->findTop(firstPass, start, end, unsortable, allocator); - if (!result) { - if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) { - *done = true; - return NULL; - } - lastTopStart = topStart; - lastStart = *start; - lastEnd = *end; - } - } while (!result); - return result; -} - -static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList, - SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit, - SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { - double test = 0.9; - int contourWinding; +void DebugShowActiveSpans(SkOpContourHead* contourList) { + SkOpContour* contour = contourList; do { - contourWinding = contourRangeCheckY(contourList, currentPtr, start, end, - tHit, hitDx, tryAgain, &test, opp); - if (contourWinding != SK_MinS32 || *tryAgain) { - return contourWinding; - } - if (*currentPtr && (*currentPtr)->isVertical()) { - *onlyVertical = true; - return contourWinding; - } - test /= 2; - } while (!approximately_negative(test)); - SkASSERT(0); // FIXME: incomplete functionality - return contourWinding; -} - -static void skipVertical(const SkTDArray<SkOpContour* >& contourList, - SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) { - if (!(*current)->isVertical(*start, *end)) { - return; - } - int contourCount = contourList.count(); - for (int cIndex = 0; cIndex < contourCount; ++cIndex) { - SkOpContour* contour = contourList[cIndex]; - if (contour->done()) { - continue; - } - SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end); - if (nonVertical) { - *current = nonVertical; - return; - } - } - return; + contour->debugShowActiveSpans(); + } while ((contour = contour->next())); } - -struct SortableTop2 { // error if local in pre-C++11 - SkOpSpanBase* fStart; - SkOpSpanBase* fEnd; -}; - -SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass, - SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr, - SkOpSpanBase** endPtr, SkDPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, - SkChunkAlloc* allocator) { - SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft, - unsortable, done, allocator); - if (!current) { - return NULL; - } - SkOpSpanBase* start = *startPtr; - SkOpSpanBase* end = *endPtr; - SkASSERT(current == start->segment()); - if (*firstContour) { - current->initWinding(start, end, angleIncludeType); - *firstContour = false; - return current; - } - SkOpSpan* minSpan = start->starter(end); - int sumWinding = minSpan->windSum(); - if (sumWinding == SK_MinS32) { - SkOpSpanBase* iSpan = end; - SkOpSpanBase* oSpan = start; - do { - bool checkFrom = oSpan->t() < iSpan->t(); - if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) { - if (!iSpan->addSimpleAngle(checkFrom, allocator)) { - *unsortable = true; - return NULL; - } - } - sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType); - SkTSwap(iSpan, oSpan); - } while (sumWinding == SK_MinS32 && iSpan == start); - } - if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { - return current; - } - int contourWinding; - int oppContourWinding = 0; - // the simple upward projection of the unresolved points hit unsortable angles - // shoot rays at right angles to the segment to find its winding, ignoring angle cases - bool tryAgain; - double tHit; - SkScalar hitDx = 0; - SkScalar hitOppDx = 0; - // keep track of subsequent returns to detect infinite loops - SkTDArray<SortableTop2> sortableTops; - do { - // if current is vertical, find another candidate which is not - // if only remaining candidates are vertical, then they can be marked done - SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); - SkASSERT(current == (*startPtr)->segment()); - skipVertical(contourList, ¤t, startPtr, endPtr); - SkASSERT(current); // FIXME: if null, all remaining are vertical - SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); - SkASSERT(current == (*startPtr)->segment()); - tryAgain = false; - contourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, - &hitDx, &tryAgain, onlyVertical, false); - SkASSERT(current == (*startPtr)->segment()); - if (tryAgain) { - bool giveUp = false; - int count = sortableTops.count(); - for (int index = 0; index < count; ++index) { - const SortableTop2& prev = sortableTops[index]; - if (giveUp) { - prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd)); - } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) { - // remaining edges are non-vertical and cannot have their winding computed - // mark them as done and return, and hope that assembly can fill the holes - giveUp = true; - index = -1; - } - } - if (giveUp) { - *done = true; - return NULL; - } - } - SortableTop2* sortableTop = sortableTops.append(); - sortableTop->fStart = *startPtr; - sortableTop->fEnd = *endPtr; -#if DEBUG_SORT - SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n", - __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(), - tHit, hitDx, tryAgain, *onlyVertical); #endif - if (*onlyVertical) { - return current; - } - if (tryAgain) { - continue; - } - if (angleIncludeType < SkOpAngle::kBinarySingle) { - break; - } - oppContourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, - &hitOppDx, &tryAgain, NULL, true); - SkASSERT(current == (*startPtr)->segment()); - } while (tryAgain); - bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx, - oppContourWinding, hitOppDx); - if (current->done()) { - return NULL; - } else if (!success) { // check if the span has a valid winding - SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast() - : (*endPtr)->upCast(); - if (minSpan->windSum() == SK_MinS32) { - return NULL; - } - } - return current; -} -void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list, - bool evenOdd, bool oppEvenOdd) { +bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) { + SkTDArray<SkOpContour* > list; + SkOpContour* contour = *contourList; do { if (contour->count()) { contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); *list.append() = contour; } } while ((contour = contour->next())); - if (list.count() < 2) { - return; + int count = list.count(); + if (!count) { + return false; + } + if (count > 1) { + SkTQSort<SkOpContour>(list.begin(), list.end() - 1); } - SkTQSort<SkOpContour>(list.begin(), list.end() - 1); + contour = list[0]; + SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour); + contour->globalState()->setContourHead(contourHead); + *contourList = contourHead; + for (int index = 1; index < count; ++index) { + SkOpContour* next = list[index]; + contour->setNext(next); + contour = next; + } + contour->setNext(NULL); + return true; } class DistanceLessThan { @@ -444,8 +161,8 @@ public: */ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune - SkOpContour contour; - SkOpGlobalState globalState(NULL SkDEBUGPARAMS(&contour)); + SkOpContourHead contour; + SkOpGlobalState globalState(NULL, &contour); #if DEBUG_SHOW_TEST_NAME SkDebugf("</div>\n"); #endif @@ -634,65 +351,52 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) { #endif } -static void align(SkTDArray<SkOpContour* >* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; +static void align(SkOpContourHead* contourList) { + SkOpContour* contour = contourList; + do { contour->align(); - } + } while ((contour = contour->next())); } -static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; +static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) { + SkOpContour* contour = contourList; + do { contour->calcAngles(allocator); - } + } while ((contour = contour->next())); } -static void missingCoincidence(SkTDArray<SkOpContour* >* contourList, +static void missingCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; + SkOpContour* contour = contourList; + do { contour->missingCoincidence(coincidence, allocator); - } + } while ((contour = contour->next())); } -static void moveMultiples(SkTDArray<SkOpContour* >* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; +static void moveMultiples(SkOpContourHead* contourList) { + SkOpContour* contour = contourList; + do { contour->moveMultiples(); - } + } while ((contour = contour->next())); } -static void moveNearby(SkTDArray<SkOpContour* >* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; +static void moveNearby(SkOpContourHead* contourList) { + SkOpContour* contour = contourList; + do { contour->moveNearby(); - } + } while ((contour = contour->next())); } -static void sortAngles(SkTDArray<SkOpContour* >* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; +static void sortAngles(SkOpContourHead* contourList) { + SkOpContour* contour = contourList; + do { contour->sortAngles(); - } -} - -static void sortSegments(SkTDArray<SkOpContour* >* contourList) { - int contourCount = (*contourList).count(); - for (int cTest = 0; cTest < contourCount; ++cTest) { - SkOpContour* contour = (*contourList)[cTest]; - contour->sortSegments(); - } + } while ((contour = contour->next())); } -bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence, - SkChunkAlloc* allocator, SkOpGlobalState* globalState) { +bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence, + SkChunkAlloc* allocator) { + SkOpGlobalState* globalState = contourList->globalState(); // combine t values when multiple intersections occur on some segments but not others moveMultiples(contourList); // move t values and points together to eliminate small/tiny gaps @@ -711,7 +415,6 @@ bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* c if (!coincidence->apply()) { // adjust the winding value to account for coincident edges return false; } - sortSegments(contourList); calcAngles(contourList, allocator); sortAngles(contourList); if (globalState->angleCoincidence()) { @@ -721,7 +424,8 @@ bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* c } } #if DEBUG_ACTIVE_SPANS - DebugShowActiveSpans(*contourList); + coincidence->debugShowCoincidence(); + DebugShowActiveSpans(contourList); #endif return true; } diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index 82eb5da215..25faf8223e 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -17,19 +17,14 @@ class SkPathWriter; void Assemble(const SkPathWriter& path, SkPathWriter* simple); SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr); -SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour*>& , bool firstPass, - SkOpAngle::IncludeType , bool* firstContour, SkOpSpanBase** index, - SkOpSpanBase** endIndex, SkDPoint* topLeft, bool* unsortable, - bool* done, bool* onlyVertical, SkChunkAlloc* ); -SkOpSegment* FindUndone(SkTDArray<SkOpContour*>& contourList, SkOpSpanBase** startPtr, +SkOpSpan* FindSortableTop(SkOpContourHead* ); +SkOpSegment* FindUndone(SkOpContourHead* , SkOpSpanBase** startPtr, SkOpSpanBase** endPtr); -void MakeContourList(SkOpContour* , SkTDArray<SkOpContour*>& list, - bool evenOdd, bool oppEvenOdd); -bool HandleCoincidence(SkTDArray<SkOpContour*>* , SkOpCoincidence* , SkChunkAlloc* , - SkOpGlobalState* ); - +bool SortContourList(SkOpContourHead** , bool evenOdd, bool oppEvenOdd); +bool HandleCoincidence(SkOpContourHead* , SkOpCoincidence* , SkChunkAlloc* ); +bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, bool expectSuccess); #if DEBUG_ACTIVE_SPANS -void DebugShowActiveSpans(SkTDArray<SkOpContour*>& contourList); +void DebugShowActiveSpans(SkOpContourHead* ); #endif #endif diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 777298b297..972c510643 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -16,6 +16,15 @@ const int SkDCubic::gPrecisionUnit = 256; // FIXME: test different values in test framework +void SkDCubic::align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const { + if (fPts[endIndex].fX == fPts[ctrlIndex].fX) { + dstPt->fX = fPts[endIndex].fX; + } + if (fPts[endIndex].fY == fPts[ctrlIndex].fY) { + dstPt->fY = fPts[endIndex].fY; + } +} + // give up when changing t no longer moves point // also, copy point rather than recompute it when it does change double SkDCubic::binarySearch(double min, double max, double axisIntercept, @@ -75,45 +84,45 @@ double SkDCubic::calcPrecision() const { return (width > height ? width : height) / gPrecisionUnit; } -bool SkDCubic::clockwise(const SkDCubic& whole, bool* swap) const { - SkDPoint lastPt = fPts[kPointLast]; - SkDPoint firstPt = fPts[0]; - double sum = 0; - // pick the control point furthest from the line connecting the end points - SkLineParameters lineParameters; - lineParameters.cubicEndPoints(*this, 0, 3); - lineParameters.normalize(); - double tiniest = SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), - fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY), fPts[3].fX), fPts[3].fY); - double largest = SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), - fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY), fPts[3].fX), fPts[3].fY); - largest = SkTMax(largest, -tiniest); - double pt1dist = lineParameters.controlPtDistance(*this, 1); - double pt2dist = lineParameters.controlPtDistance(*this, 2); -#if DEBUG_SWAP_TOP - SkDebugf("%s pt1dist=%1.9g pt2dist=%1.9g\n", __FUNCTION__, pt1dist, pt2dist); -#endif - int furthest; - if (!approximately_zero_when_compared_to(pt1dist, largest) - && !approximately_zero_when_compared_to(pt2dist, largest) && pt1dist * pt2dist < 0) { - furthest = 2; - } else { - furthest = fabs(pt1dist) < fabs(pt2dist) ? 2 : 1; - } - for (int idx = 1; idx <= 3; ++idx) { - sum += (firstPt.fX - lastPt.fX) * (firstPt.fY + lastPt.fY); - lastPt = firstPt; - firstPt = idx == 1 ? fPts[furthest] : fPts[kPointLast]; - } - *swap = sum > 0 && !this->monotonicInY() && !whole.monotonicInY(); - return sum <= 0; + +/* classic one t subdivision */ +static void interp_cubic_coords(const double* src, double* dst, double t) { + double ab = SkDInterp(src[0], src[2], t); + double bc = SkDInterp(src[2], src[4], t); + double cd = SkDInterp(src[4], src[6], t); + double abc = SkDInterp(ab, bc, t); + double bcd = SkDInterp(bc, cd, t); + double abcd = SkDInterp(abc, bcd, t); + + dst[0] = src[0]; + dst[2] = ab; + dst[4] = abc; + dst[6] = abcd; + dst[8] = bcd; + dst[10] = cd; + dst[12] = src[6]; } -bool SkDCubic::Clockwise(const SkPoint* pts, double startT, double endT, bool* swap) { - SkDCubic cubic; - cubic.set(pts); - SkDCubic part = cubic.subDivide(startT, endT); - return part.clockwise(cubic, swap); +SkDCubicPair SkDCubic::chopAt(double t) const { + SkDCubicPair dst; + if (t == 0.5) { + dst.pts[0] = fPts[0]; + dst.pts[1].fX = (fPts[0].fX + fPts[1].fX) / 2; + dst.pts[1].fY = (fPts[0].fY + fPts[1].fY) / 2; + dst.pts[2].fX = (fPts[0].fX + 2 * fPts[1].fX + fPts[2].fX) / 4; + dst.pts[2].fY = (fPts[0].fY + 2 * fPts[1].fY + fPts[2].fY) / 4; + dst.pts[3].fX = (fPts[0].fX + 3 * (fPts[1].fX + fPts[2].fX) + fPts[3].fX) / 8; + dst.pts[3].fY = (fPts[0].fY + 3 * (fPts[1].fY + fPts[2].fY) + fPts[3].fY) / 8; + dst.pts[4].fX = (fPts[1].fX + 2 * fPts[2].fX + fPts[3].fX) / 4; + dst.pts[4].fY = (fPts[1].fY + 2 * fPts[2].fY + fPts[3].fY) / 4; + dst.pts[5].fX = (fPts[2].fX + fPts[3].fX) / 2; + dst.pts[5].fY = (fPts[2].fY + fPts[3].fY) / 2; + dst.pts[6] = fPts[3]; + return dst; + } + interp_cubic_coords(&fPts[0].fX, &dst.pts[0].fX, t); + interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t); + return dst; } void SkDCubic::Coefficients(const double* src, double* A, double* B, double* C, double* D) { @@ -636,15 +645,6 @@ SkDCubic SkDCubic::subDivide(double t1, double t2) const { return dst; } -void SkDCubic::align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const { - if (fPts[endIndex].fX == fPts[ctrlIndex].fX) { - dstPt->fX = fPts[endIndex].fX; - } - if (fPts[endIndex].fY == fPts[ctrlIndex].fY) { - dstPt->fY = fPts[endIndex].fY; - } -} - void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint dst[2]) const { SkASSERT(t1 != t2); @@ -672,42 +672,17 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d, } } -/* classic one t subdivision */ -static void interp_cubic_coords(const double* src, double* dst, double t) { - double ab = SkDInterp(src[0], src[2], t); - double bc = SkDInterp(src[2], src[4], t); - double cd = SkDInterp(src[4], src[6], t); - double abc = SkDInterp(ab, bc, t); - double bcd = SkDInterp(bc, cd, t); - double abcd = SkDInterp(abc, bcd, t); - - dst[0] = src[0]; - dst[2] = ab; - dst[4] = abc; - dst[6] = abcd; - dst[8] = bcd; - dst[10] = cd; - dst[12] = src[6]; -} - -SkDCubicPair SkDCubic::chopAt(double t) const { - SkDCubicPair dst; - if (t == 0.5) { - dst.pts[0] = fPts[0]; - dst.pts[1].fX = (fPts[0].fX + fPts[1].fX) / 2; - dst.pts[1].fY = (fPts[0].fY + fPts[1].fY) / 2; - dst.pts[2].fX = (fPts[0].fX + 2 * fPts[1].fX + fPts[2].fX) / 4; - dst.pts[2].fY = (fPts[0].fY + 2 * fPts[1].fY + fPts[2].fY) / 4; - dst.pts[3].fX = (fPts[0].fX + 3 * (fPts[1].fX + fPts[2].fX) + fPts[3].fX) / 8; - dst.pts[3].fY = (fPts[0].fY + 3 * (fPts[1].fY + fPts[2].fY) + fPts[3].fY) / 8; - dst.pts[4].fX = (fPts[1].fX + 2 * fPts[2].fX + fPts[3].fX) / 4; - dst.pts[4].fY = (fPts[1].fY + 2 * fPts[2].fY + fPts[3].fY) / 4; - dst.pts[5].fX = (fPts[2].fX + fPts[3].fX) / 2; - dst.pts[5].fY = (fPts[2].fY + fPts[3].fY) / 2; - dst.pts[6] = fPts[3]; - return dst; +double SkDCubic::top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const { + double extremeTs[2]; + double topT = -1; + int roots = SkDCubic::FindExtrema(&fPts[0].fY, extremeTs); + for (int index = 0; index < roots; ++index) { + double t = startT + (endT - startT) * extremeTs[index]; + SkDPoint mid = dCurve.ptAtT(t); + if (topPt->fY > mid.fY || (topPt->fY == mid.fY && topPt->fX > mid.fX)) { + topT = t; + *topPt = mid; + } } - interp_cubic_coords(&fPts[0].fX, &dst.pts[0].fX, t); - interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t); - return dst; + return topT; } diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h index 3d68151852..7a57e94ef6 100644 --- a/src/pathops/SkPathOpsCubic.h +++ b/src/pathops/SkPathOpsCubic.h @@ -57,8 +57,6 @@ struct SkDCubic { double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const; double calcPrecision() const; SkDCubicPair chopAt(double t) const; - bool clockwise(const SkDCubic& whole, bool* swap) const; - static bool Clockwise(const SkPoint* pts, double startT, double endT, bool* swap); static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D); static bool ComplexBreak(const SkPoint pts[4], SkScalar* t, CubicType* cubicType); int convexHull(char order[kPointCount]) const; @@ -77,8 +75,7 @@ struct SkDCubic { static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) { SkDCubic cubic; - cubic.set(a); - return cubic.findInflections(tValues); + return cubic.set(a).findInflections(tValues); } int findMaxCurvature(double tValues[]) const; @@ -120,8 +117,7 @@ struct SkDCubic { static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) { SkDCubic cubic; - cubic.set(a); - return cubic.subDivide(t1, t2); + return cubic.set(a).subDivide(t1, t2); } void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const; @@ -129,10 +125,10 @@ struct SkDCubic { static void SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) { SkDCubic cubic; - cubic.set(pts); - cubic.subDivide(a, d, t1, t2, p); + cubic.set(pts).subDivide(a, d, t1, t2, p); } + double top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const; SkDQuad toQuad() const; static const int gPrecisionUnit; diff --git a/src/pathops/SkPathOpsCurve.cpp b/src/pathops/SkPathOpsCurve.cpp index 651e64a908..bf44d25e17 100644 --- a/src/pathops/SkPathOpsCurve.cpp +++ b/src/pathops/SkPathOpsCurve.cpp @@ -8,98 +8,6 @@ #include "SkPathOpsRect.h" #include "SkPathOpsCurve.h" -SkDPoint SkDCurve::conicTop(const SkPoint curve[3], SkScalar curveWeight, - double startT, double endT, double* topT) { - SkDPoint topPt = fConic[0]; - *topT = startT; - if (topPt.fY > fConic[2].fY || (topPt.fY == fConic[2].fY && topPt.fX > fConic[2].fX)) { - *topT = endT; - topPt = fConic[2]; - } - if (!fConic.monotonicInY()) { - double extremeT; - if (SkDConic::FindExtrema(&fConic.fPts.fPts[0].fY, fConic.fWeight, &extremeT)) { - SkDConic dCurve; - dCurve.set(curve, curveWeight); - extremeT = startT + (endT - startT) * extremeT; - SkDPoint test = dCurve.ptAtT(extremeT); - if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) { - *topT = extremeT; - topPt = test; - } - } - } - return topPt; -} - -SkDPoint SkDCurve::cubicTop(const SkPoint curve[4], SkScalar , - double startT, double endT, double* topT) { - SkDPoint topPt = fCubic[0]; - *topT = startT; - if (topPt.fY > fCubic[3].fY || (topPt.fY == fCubic[3].fY && topPt.fX > fCubic[3].fX)) { - *topT = endT; - topPt = fCubic[3]; - } - double extremeTs[2]; - if (!fCubic.monotonicInY()) { - int roots = SkDCubic::FindExtrema(&fCubic.fPts[0].fY, extremeTs); - SkDCubic dCurve; - dCurve.set(curve); - for (int index = 0; index < roots; ++index) { - double t = startT + (endT - startT) * extremeTs[index]; - SkDPoint mid = dCurve.ptAtT(t); - if (topPt.fY > mid.fY || (topPt.fY == mid.fY && topPt.fX > mid.fX)) { - *topT = t; - topPt = mid; - } - } - } - return topPt; -} - -SkDPoint SkDCurve::lineTop(const SkPoint[2], SkScalar , double startT, double endT, double* topT) { - SkDPoint topPt = fLine[0]; - *topT = startT; - if (topPt.fY > fLine[1].fY || (topPt.fY == fLine[1].fY && topPt.fX > fLine[1].fX)) { - *topT = endT; - topPt = fLine[1]; - } - return topPt; -} - -SkDPoint SkDCurve::quadTop(const SkPoint curve[3], SkScalar , - double startT, double endT, double* topT) { - SkDPoint topPt = fQuad[0]; - *topT = startT; - if (topPt.fY > fQuad[2].fY || (topPt.fY == fQuad[2].fY && topPt.fX > fQuad[2].fX)) { - *topT = endT; - topPt = fQuad[2]; - } - if (!fQuad.monotonicInY()) { - double extremeT; - if (SkDQuad::FindExtrema(&fQuad.fPts[0].fY, &extremeT)) { - SkDQuad dCurve; - dCurve.set(curve); - extremeT = startT + (endT - startT) * extremeT; - SkDPoint test = dCurve.ptAtT(extremeT); - if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) { - *topT = extremeT; - topPt = test; - } - } - } - return topPt; -} - -SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar curveWeight, - double tStart, double tEnd, double* topT) = { - NULL, - &SkDCurve::lineTop, - &SkDCurve::quadTop, - &SkDCurve::conicTop, - &SkDCurve::cubicTop -}; - void SkDCurve::setConicBounds(const SkPoint curve[3], SkScalar curveWeight, double tStart, double tEnd, SkPathOpsBounds* bounds) { SkDConic dCurve; @@ -120,12 +28,6 @@ void SkDCurve::setCubicBounds(const SkPoint curve[4], SkScalar , SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom)); } -void SkDCurve::setLineBounds(const SkPoint[2], SkScalar , - double , double , SkPathOpsBounds* bounds) { - bounds->setPointBounds(fLine[0]); - bounds->add(fLine[1]); -} - void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar , double tStart, double tEnd, SkPathOpsBounds* bounds) { SkDQuad dCurve; @@ -135,12 +37,3 @@ void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar , bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop), SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom)); } - -void (SkDCurve::* const SetBounds[])(const SkPoint curve[], SkScalar curveWeight, - double tStart, double tEnd, SkPathOpsBounds* bounds) = { - NULL, - &SkDCurve::setLineBounds, - &SkDCurve::setQuadBounds, - &SkDCurve::setConicBounds, - &SkDCurve::setCubicBounds -}; diff --git a/src/pathops/SkPathOpsCurve.h b/src/pathops/SkPathOpsCurve.h index bfbc515719..c830e66d4d 100644 --- a/src/pathops/SkPathOpsCurve.h +++ b/src/pathops/SkPathOpsCurve.h @@ -8,9 +8,6 @@ #define SkPathOpsCurve_DEFINE #include "SkIntersections.h" -#include "SkPathOpsCubic.h" -#include "SkPathOpsLine.h" -#include "SkPathOpsQuad.h" #ifndef SK_RELEASE #include "SkPath.h" @@ -78,15 +75,11 @@ struct SkDCurve { double s, double e, SkPathOpsBounds* ); void setCubicBounds(const SkPoint curve[4], SkScalar , double s, double e, SkPathOpsBounds* ); - void setLineBounds(const SkPoint[2], SkScalar , double , double , SkPathOpsBounds* ); void setQuadBounds(const SkPoint curve[3], SkScalar , double s, double e, SkPathOpsBounds*); }; -extern void (SkDCurve::* const SetBounds[])(const SkPoint curve[], SkScalar cWeight, - double tStart, double tEnd, SkPathOpsBounds* ); - extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight, double tStart, double tEnd, double* topT); @@ -276,4 +269,59 @@ static void (* const CurveIntersectRay[])(const SkPoint[] , SkScalar , const SkD cubic_intersect_ray }; +static int line_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) { + SkDLine line; + roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y); + return between(0, roots[0], 1); +} + +static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) { + SkDLine line; + roots[0] = SkIntersections::VerticalIntercept(line.set(a), x); + return between(0, roots[0], 1); +} + +static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) { + SkDQuad quad; + return SkIntersections::HorizontalIntercept(quad.set(a), y, roots); +} + +static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) { + SkDQuad quad; + return SkIntersections::VerticalIntercept(quad.set(a), x, roots); +} + +static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) { + SkDConic conic; + return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots); +} + +static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) { + SkDConic conic; + return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots); +} + +static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) { + SkDCubic cubic; + return cubic.set(a).horizontalIntersect(y, roots); +} + +static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) { + SkDCubic cubic; + return cubic.set(a).verticalIntersect(x, roots); +} + +static int (* const CurveIntercept[])(const SkPoint[] , SkScalar , SkScalar , double* ) = { + NULL, + NULL, + line_intercept_h, + line_intercept_v, + quad_intercept_h, + quad_intercept_v, + conic_intercept_h, + conic_intercept_v, + cubic_intercept_h, + cubic_intercept_v, +}; + #endif diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index a9f8fe6acc..2903e08984 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -14,6 +14,15 @@ extern bool FLAGS_runFail; #endif +#if DEBUG_SORT +int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; +int SkPathOpsDebug::gSortCount; +#endif + +#if DEBUG_ACTIVE_OP +const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; +#endif + #if defined SK_DEBUG || !FORCE_RELEASE const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; @@ -23,15 +32,6 @@ int SkPathOpsDebug::gContourID = 0; int SkPathOpsDebug::gSegmentID = 0; #endif -#if DEBUG_SORT || DEBUG_SWAP_TOP -int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; -int SkPathOpsDebug::gSortCount; -#endif - -#if DEBUG_ACTIVE_OP -const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; -#endif - bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray, const SkOpSpanBase* span) { for (int index = 0; index < chaseArray.count(); ++index) { @@ -135,20 +135,25 @@ void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp show_op(shapeOp, "path", "pathB"); } +#include "SkPathOpsCubic.h" +#include "SkPathOpsQuad.h" + +SkDCubic SkDQuad::debugToCubic() const { + SkDCubic cubic; + cubic[0] = fPts[0]; + cubic[2] = fPts[1]; + cubic[3] = fPts[2]; + cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; + cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; + cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; + cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; + return cubic; +} + #include "SkOpAngle.h" +#include "SkOpCoincidence.h" #include "SkOpSegment.h" -#if DEBUG_SWAP_TOP -int SkOpSegment::debugInflections(const SkOpSpanBase* start, const SkOpSpanBase* end) const { - if (fVerb != SkPath::kCubic_Verb) { - return false; - } - SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t()); - double inflections[2]; - return dst.findInflections(inflections); -} -#endif - SkOpAngle* SkOpSegment::debugLastAngle() { SkOpAngle* result = NULL; SkOpSpan* span = this->head(); @@ -195,13 +200,20 @@ void SkOpSegment::debugShowActiveSpans() const { const SkOpPtT* ptT = span->ptT(); SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY); SkDebugf(" tEnd=%1.9g", span->next()->t()); - SkDebugf(" windSum="); if (span->windSum() == SK_MinS32) { - SkDebugf("?"); + SkDebugf(" windSum=?"); } else { - SkDebugf("%d", span->windSum()); + SkDebugf(" windSum=%d", span->windSum()); + } + if (span->oppValue() && span->oppSum() == SK_MinS32) { + SkDebugf(" oppSum=?"); + } else if (span->oppValue() || span->oppSum() != SK_MinS32) { + SkDebugf(" oppSum=%d", span->oppSum()); + } + SkDebugf(" windValue=%d", span->windValue()); + if (span->oppValue() || span->oppSum() != SK_MinS32) { + SkDebugf(" oppValue=%d", span->oppValue()); } - SkDebugf(" windValue=%d oppValue=%d", span->windValue(), span->oppValue()); SkDebugf("\n"); } while ((span = span->next()->upCastable())); } @@ -297,7 +309,7 @@ SkString SkOpAngle::debugPart() const { } #endif -#if DEBUG_SORT || DEBUG_SWAP_TOP +#if DEBUG_SORT void SkOpAngle::debugLoop() const { const SkOpAngle* first = this; const SkOpAngle* next = this; @@ -339,14 +351,14 @@ void SkOpAngle::debugValidate() const { bool useXor = op ? oppXor : isXor; SkASSERT(lastXor == -1 || lastXor == (int) useXor); lastXor = (int) useXor; - wind += next->sign() * (op ? minSpan->oppValue() : minSpan->windValue()); + wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue()); if (useXor) { wind &= 1; } useXor = op ? isXor : oppXor; SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor); lastOppXor = (int) useXor; - opp += next->sign() * (op ? minSpan->windValue() : minSpan->oppValue()); + opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue()); if (useXor) { opp &= 1; } @@ -377,6 +389,19 @@ void SkOpAngle::debugValidateNext() const { #endif } +void SkOpCoincidence::debugShowCoincidence() const { + SkCoincidentSpans* span = fHead; + while (span) { + SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, + span->fCoinPtTStart->segment()->debugID(), + span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT); + SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, + span->fOppPtTStart->segment()->debugID(), + span->fOppPtTStart->fT, span->fOppPtTEnd->fT); + span = span->fNext; + } +} + void SkOpSegment::debugValidate() const { #if DEBUG_VALIDATE const SkOpSpanBase* span = &fHead; @@ -474,6 +499,28 @@ bool SkOpSpan::debugCoinLoopCheck() const { return true; } +// called only by test code +int SkIntersections::debugCoincidentUsed() const { + if (!fIsCoincident[0]) { + SkASSERT(!fIsCoincident[1]); + return 0; + } + int count = 0; + SkDEBUGCODE(int count2 = 0;) + for (int index = 0; index < fUsed; ++index) { + if (fIsCoincident[0] & (1 << index)) { + ++count; + } +#ifdef SK_DEBUG + if (fIsCoincident[1] & (1 << index)) { + ++count2; + } +#endif + } + SkASSERT(count == count2); + return count; +} + #include "SkOpContour.h" int SkOpPtT::debugLoopLimit(bool report) const { diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 0624ad687a..61c2ecab53 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -45,15 +45,14 @@ #define DEBUG_ASSEMBLE 0 #define DEBUG_CUBIC_BINARY_SEARCH 0 #define DEBUG_CUBIC_SPLIT 0 -#define DEBUG_DUMP_SEGMENTS 0 // 1 +#define DEBUG_DUMP_SEGMENTS 0 #define DEBUG_FLOW 0 #define DEBUG_LIMIT_WIND_SUM 0 #define DEBUG_MARK_DONE 0 #define DEBUG_PATH_CONSTRUCTION 0 #define DEBUG_PERP 0 -#define DEBUG_SHOW_TEST_NAME 0 // 1 +#define DEBUG_SHOW_TEST_NAME 0 #define DEBUG_SORT 0 -#define DEBUG_SWAP_TOP 0 // 1 #define DEBUG_T_SECT 0 #define DEBUG_T_SECT_DUMP 0 #define DEBUG_VALIDATE 0 @@ -78,7 +77,6 @@ #define DEBUG_PERP 1 #define DEBUG_SHOW_TEST_NAME 1 #define DEBUG_SORT 1 -#define DEBUG_SWAP_TOP 1 #define DEBUG_T_SECT 0 #define DEBUG_T_SECT_DUMP 0 #define DEBUG_VALIDATE 1 @@ -133,8 +131,6 @@ #include "SkTLS.h" #endif -#include "SkTDArray.h" - class SkPathOpsDebug { public: static const char* kLVerbStr[]; @@ -144,7 +140,7 @@ public: static int gSegmentID; #endif -#if DEBUG_SORT || DEBUG_SWAP_TOP +#if DEBUG_SORT static int gSortCountDefault; static int gSortCount; #endif @@ -200,15 +196,6 @@ public: static const class SkOpPtT* DebugSpanPtT(const class SkOpSpanBase*, int id); static const class SkOpSegment* DebugSpanSegment(const class SkOpSpanBase*, int id); static const class SkOpSpanBase* DebugSpanSpan(const class SkOpSpanBase*, int id); - - static void DumpContours(SkTDArray<class SkOpContour* >* contours); - static void DumpContoursAll(SkTDArray<class SkOpContour* >* contours); - static void DumpContoursAngles(const SkTDArray<class SkOpContour* >* contours); - static void DumpContoursPt(const SkTDArray<class SkOpContour* >* contours, int id); - static void DumpContoursPts(const SkTDArray<class SkOpContour* >* contours); - static void DumpContoursSegment(const SkTDArray<class SkOpContour* >* contours, int id); - static void DumpContoursSpan(const SkTDArray<class SkOpContour* >* contours, int id); - static void DumpContoursSpans(const SkTDArray<class SkOpContour* >* contours); }; struct SkDQuad; @@ -217,19 +204,4 @@ struct SkDQuad; void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo); void DumpT(const SkDQuad& quad, double t); -const struct SkOpAngle* DebugAngle(const SkTDArray<class SkOpContour* >* contours, int id); -class SkOpContour* DebugContour(const SkTDArray<class SkOpContour* >* contours, int id); -const class SkOpPtT* DebugPtT(const SkTDArray<class SkOpContour* >* contours, int id); -const class SkOpSegment* DebugSegment(const SkTDArray<class SkOpContour* >* contours, int id); -const class SkOpSpanBase* DebugSpan(const SkTDArray<class SkOpContour* >* contours, int id); - -void Dump(const SkTDArray<class SkOpContour* >* contours); -void DumpAll(SkTDArray<class SkOpContour* >* contours); -void DumpAngles(const SkTDArray<class SkOpContour* >* contours); -void DumpCoin(const SkTDArray<class SkOpContour* >* contours); -void DumpPt(const SkTDArray<class SkOpContour* >* contours, int segmentID); -void DumpPts(const SkTDArray<class SkOpContour* >* contours); -void DumpSegment(const SkTDArray<class SkOpContour* >* contours, int segmentID); -void DumpSpan(const SkTDArray<class SkOpContour* >* contours, int spanID); -void DumpSpans(const SkTDArray<class SkOpContour* >* contours); #endif diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index ce55861522..ce502019ae 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -15,9 +15,10 @@ struct SkDLine { const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; } SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; } - void set(const SkPoint pts[2]) { + const SkDLine& set(const SkPoint pts[2]) { fPts[0] = pts[0]; fPts[1] = pts[1]; + return *this; } double exactPoint(const SkDPoint& xy) const; diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 1105af5d70..f9a4fa3ca6 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -98,41 +98,17 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** return NULL; } -static bool bridgeOp(SkTDArray<SkOpContour* >& contourList, const SkPathOp op, +static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) { - bool firstContour = true; bool unsortable = false; - bool topUnsortable = false; - bool firstPass = true; - SkDPoint lastTopLeft; - SkDPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; do { - SkOpSpanBase* start = NULL; - SkOpSpanBase* end = NULL; - bool topDone; - bool onlyVertical = false; - lastTopLeft = topLeft; - SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kBinarySingle, - &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical, - allocator); - if (!current) { - if ((!topUnsortable || firstPass) && !topDone) { - SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); - if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) { - if (firstPass) { - firstPass = false; - } else { - break; - } - } - topLeft.fX = topLeft.fY = SK_ScalarMin; - continue; - } - break; - } else if (onlyVertical) { + SkOpSpan* span = FindSortableTop(contourList); + if (!span) { break; } - firstPass = !topUnsortable || lastTopLeft != topLeft; + SkOpSegment* current = span->segment(); + SkOpSpanBase* start = span->next(); + SkOpSpanBase* end = span; SkTDArray<SkOpSpanBase*> chase; do { if (current->activeOp(start, end, xorMask, xorOpMask, op)) { @@ -260,11 +236,13 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) { } #endif -bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { +bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, + bool expectSuccess) { SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune SkOpContour contour; + SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); SkOpCoincidence coincidence; - SkOpGlobalState globalState(&coincidence SkDEBUGPARAMS(&contour)); + SkOpGlobalState globalState(&coincidence, contourList); #if DEBUGGING_PATHOPS_FROM_HOST dump_op(one, two, op); #endif @@ -285,7 +263,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { subtrahend = &one; op = kDifference_SkPathOp; } -#if DEBUG_SORT || DEBUG_SWAP_TOP +#if DEBUG_SORT SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; #endif // turn path into list of segments @@ -303,36 +281,24 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { #endif const int xorOpMask = builder.xorMask(); - SkTDArray<SkOpContour* > contourList; - MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask, - xorOpMask == kEvenOdd_PathOpsMask); - SkOpContour** currentPtr = contourList.begin(); - if (!currentPtr) { + if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, + xorOpMask == kEvenOdd_PathOpsMask)) { result->reset(); result->setFillType(fillType); return true; } - if ((*currentPtr)->count() == 0) { - SkASSERT((*currentPtr)->next() == NULL); - result->reset(); - result->setFillType(fillType); - return true; - } - SkOpContour** listEnd = contourList.end(); // find all intersections between segments + SkOpContour* current = contourList; do { - SkOpContour** nextPtr = currentPtr; - SkOpContour* current = *currentPtr++; - SkOpContour* next; - do { - next = *nextPtr++; - } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd); - } while (currentPtr != listEnd); + SkOpContour* next = current; + while (AddIntersectTs(current, next, &coincidence, &allocator) + && (next = next->next())) + ; + } while ((current = current->next())); #if DEBUG_VALIDATE globalState.setPhase(SkOpGlobalState::kWalking); #endif - // eat through coincident edges - if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) { + if (!HandleCoincidence(contourList, &coincidence, &allocator)) { return false; } // construct closed contours @@ -350,3 +316,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { } return true; } + +bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { + return OpDebug(one, two, op, result, true); +} diff --git a/src/pathops/SkPathOpsPoint.cpp b/src/pathops/SkPathOpsPoint.cpp index dc9cde55a3..e0f175dac5 100644 --- a/src/pathops/SkPathOpsPoint.cpp +++ b/src/pathops/SkPathOpsPoint.cpp @@ -10,8 +10,3 @@ SkDVector operator-(const SkDPoint& a, const SkDPoint& b) { SkDVector v = {a.fX - b.fX, a.fY - b.fY}; return v; } - -SkDPoint operator+(const SkDPoint& a, const SkDVector& b) { - SkDPoint v = {a.fX + b.fX, a.fY + b.fY}; - return v; -} diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index c596b91cc0..e3f722bede 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -23,8 +23,6 @@ struct SkDVector { fY = pt.fY; } - friend SkDPoint operator+(const SkDPoint& a, const SkDVector& b); - // only used by testing void operator+=(const SkDVector& v) { fX += v.fX; @@ -208,7 +206,7 @@ struct SkDPoint { } static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) { - if (!RoughlyEqualUlps(a.fX, b.fX) || !RoughlyEqualUlps(a.fY, b.fY)) { + if (!RoughlyEqualUlps(a.fX, b.fX) && !RoughlyEqualUlps(a.fY, b.fY)) { return false; } SkDPoint dA, dB; diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 66f191bb0e..717d8bc03d 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -73,39 +73,6 @@ void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const { } } -// from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html -// (currently only used by testing) -double SkDQuad::nearestT(const SkDPoint& pt) const { - SkDVector pos = fPts[0] - pt; - // search points P of bezier curve with PM.(dP / dt) = 0 - // a calculus leads to a 3d degree equation : - SkDVector A = fPts[1] - fPts[0]; - SkDVector B = fPts[2] - fPts[1]; - B -= A; - double a = B.dot(B); - double b = 3 * A.dot(B); - double c = 2 * A.dot(A) + pos.dot(B); - double d = pos.dot(A); - double ts[3]; - int roots = SkDCubic::RootsValidT(a, b, c, d, ts); - double d0 = pt.distanceSquared(fPts[0]); - double d2 = pt.distanceSquared(fPts[2]); - double distMin = SkTMin(d0, d2); - int bestIndex = -1; - for (int index = 0; index < roots; ++index) { - SkDPoint onQuad = ptAtT(ts[index]); - double dist = pt.distanceSquared(onQuad); - if (distMin > dist) { - distMin = dist; - bestIndex = index; - } - } - if (bestIndex >= 0) { - return ts[bestIndex]; - } - return d0 < d2 ? 0 : 1; -} - int SkDQuad::AddValidTs(double s[], int realRoots, double* t) { int foundRoots = 0; for (int index = 0; index < realRoots; ++index) { @@ -188,25 +155,6 @@ bool SkDQuad::isLinear(int startIndex, int endIndex) const { return approximately_zero_when_compared_to(distance, largest); } -SkDConic SkDQuad::toConic() const { - SkDConic conic; - memcpy(conic.fPts.fPts, fPts, sizeof(fPts)); - conic.fWeight = 1; - return conic; -} - -SkDCubic SkDQuad::toCubic() const { - SkDCubic cubic; - cubic[0] = fPts[0]; - cubic[2] = fPts[1]; - cubic[3] = fPts[2]; - cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; - cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; - cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; - cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; - return cubic; -} - SkDVector SkDQuad::dxdyAtT(double t) const { double a = t - 1; double b = 1 - 2 * t; @@ -346,17 +294,6 @@ SkDQuadPair SkDQuad::chopAt(double t) const return dst; } -bool SkDQuad::Clockwise(const SkOpCurve& edge, bool* swap) { - SkDQuad temp; - double sum = (edge[0].fX - edge[kPointLast].fX) * (edge[0].fY + edge[kPointLast].fY); - for (int idx = 0; idx < kPointLast; ++idx){ - sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY); - } - temp.set(edge.fPts); - *swap = sum > 0 && !temp.monotonicInY(); - return sum <= 0; -} - static int valid_unit_divide(double numer, double denom, double* ratio) { if (numer < 0) { diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h index de4ce4baa3..01d4d64dbb 100644 --- a/src/pathops/SkPathOpsQuad.h +++ b/src/pathops/SkPathOpsQuad.h @@ -60,7 +60,6 @@ struct SkDQuad { static int AddValidTs(double s[], int realRoots, double* t); void align(int endIndex, SkDPoint* dstPt) const; SkDQuadPair chopAt(double t) const; - static bool Clockwise(const SkOpCurve& edge, bool* swap); SkDVector dxdyAtT(double t) const; static int FindExtrema(const double src[], double tValue[1]); bool hullIntersects(const SkDQuad& , bool* isLinear) const; @@ -69,7 +68,6 @@ struct SkDQuad { bool isLinear(int startIndex, int endIndex) const; bool monotonicInX() const; bool monotonicInY() const; - double nearestT(const SkDPoint&) const; void otherPts(int oddMan, const SkDPoint* endPt[2]) const; SkDPoint ptAtT(double t) const; static int RootsReal(double A, double B, double C, double t[2]); @@ -88,9 +86,8 @@ struct SkDQuad { quad.set(pts); return quad.subDivide(a, c, t1, t2); } - SkDConic toConic() const; - SkDCubic toCubic() const; + SkDCubic debugToCubic() const; // utilities callable by the user from the debugger when the implementation code is linked in void dump() const; void dumpID(int id) const; diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 14c6837c1b..d37998b448 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -10,41 +10,17 @@ #include "SkPathOpsCommon.h" #include "SkPathWriter.h" -static bool bridgeWinding(SkTDArray<SkOpContour* >& contourList, SkPathWriter* simple, +static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple, SkChunkAlloc* allocator) { - bool firstContour = true; bool unsortable = false; - bool topUnsortable = false; - bool firstPass = true; - SkDPoint lastTopLeft; - SkDPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; do { - SkOpSpanBase* start = NULL; - SkOpSpanBase* end = NULL; - bool topDone; - bool onlyVertical = false; - lastTopLeft = topLeft; - SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kUnaryWinding, - &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical, - allocator); - if (!current) { - if ((!topUnsortable || firstPass) && !topDone) { - SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); - if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) { - if (firstPass) { - firstPass = false; - } else { - break; - } - } - topLeft.fX = topLeft.fY = SK_ScalarMin; - continue; - } - break; - } else if (onlyVertical) { + SkOpSpan* span = FindSortableTop(contourList); + if (!span) { break; } - firstPass = !topUnsortable || lastTopLeft != topLeft; + SkOpSegment* current = span->segment(); + SkOpSpanBase* start = span->next(); + SkOpSpanBase* end = span; SkTDArray<SkOpSpanBase*> chase; do { if (current->activeWinding(start, end)) { @@ -93,7 +69,6 @@ static bool bridgeWinding(SkTDArray<SkOpContour* >& contourList, SkPathWriter* s if (last && !last->chased()) { last->setChased(true); SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); - // assert that last isn't already in array *chase.append() = last; #if DEBUG_WINDING SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID()); @@ -117,7 +92,7 @@ static bool bridgeWinding(SkTDArray<SkOpContour* >& contourList, SkPathWriter* s } // returns true if all edges were processed -static bool bridgeXor(SkTDArray<SkOpContour* >& contourList, SkPathWriter* simple, +static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple, SkChunkAlloc* allocator) { SkOpSegment* current; SkOpSpanBase* start; @@ -191,8 +166,9 @@ bool Simplify(const SkPath& path, SkPath* result) { // turn path into list of segments SkOpCoincidence coincidence; SkOpContour contour; - SkOpGlobalState globalState(&coincidence SkDEBUGPARAMS(&contour)); -#if DEBUG_SORT || DEBUG_SWAP_TOP + SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); + SkOpGlobalState globalState(&coincidence, contourList); +#if DEBUG_SORT SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; #endif SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); @@ -202,34 +178,22 @@ bool Simplify(const SkPath& path, SkPath* result) { #if DEBUG_DUMP_SEGMENTS contour.dumpSegments((SkPathOp) -1); #endif - SkTDArray<SkOpContour* > contourList; - MakeContourList(&contour, contourList, false, false); - SkOpContour** currentPtr = contourList.begin(); - if (!currentPtr) { + if (!SortContourList(&contourList, false, false)) { result->reset(); result->setFillType(fillType); return true; } - if ((*currentPtr)->count() == 0) { - SkASSERT((*currentPtr)->next() == NULL); - result->reset(); - result->setFillType(fillType); - return true; - } - SkOpContour** listEnd2 = contourList.end(); // find all intersections between segments + SkOpContour* current = contourList; do { - SkOpContour** nextPtr = currentPtr; - SkOpContour* current = *currentPtr++; - SkOpContour* next; - do { - next = *nextPtr++; - } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd2); - } while (currentPtr != listEnd2); + SkOpContour* next = current; + while (AddIntersectTs(current, next, &coincidence, &allocator) + && (next = next->next())); + } while ((current = current->next())); #if DEBUG_VALIDATE globalState.setPhase(SkOpGlobalState::kWalking); #endif - if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) { + if (!HandleCoincidence(contourList, &coincidence, &allocator)) { return false; } // construct closed contours diff --git a/src/pathops/SkPathOpsTightBounds.cpp b/src/pathops/SkPathOpsTightBounds.cpp index 01c16732c2..f60c291710 100644 --- a/src/pathops/SkPathOpsTightBounds.cpp +++ b/src/pathops/SkPathOpsTightBounds.cpp @@ -10,24 +10,20 @@ bool TightBounds(const SkPath& path, SkRect* result) { SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune SkOpContour contour; - SkOpGlobalState globalState( NULL SkDEBUGPARAMS(&contour)); + SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); + SkOpGlobalState globalState(NULL, contourList); // turn path into list of segments SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); if (!builder.finish(&allocator)) { return false; } - SkTDArray<SkOpContour* > contourList; - MakeContourList(&contour, contourList, false, false); - SkOpContour** currentPtr = contourList.begin(); - result->setEmpty(); - if (!currentPtr) { + if (!SortContourList(&contourList, false, false)) { + result->setEmpty(); return true; } - SkOpContour** listEnd = contourList.end(); - SkOpContour* current = *currentPtr++; + SkOpContour* current = contourList; SkPathOpsBounds bounds = current->bounds(); - while (currentPtr != listEnd) { - current = *currentPtr++; + while ((current = current->next())) { bounds.add(current->bounds()); } *result = bounds; diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 15a1b4b89b..845288f609 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -24,17 +24,18 @@ enum SkPathOpsMask { class SkOpCoincidence; class SkOpContour; +class SkOpContourHead; class SkOpGlobalState { public: - SkOpGlobalState(SkOpCoincidence* coincidence SkDEBUGPARAMS(SkOpContour* head)) + SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head) : fCoincidence(coincidence) + , fContourHead(head) , fWindingFailed(false) , fAngleCoincidence(false) #if DEBUG_VALIDATE , fPhase(kIntersecting) #endif - SkDEBUGPARAMS(fHead(head)) SkDEBUGPARAMS(fAngleID(0)) SkDEBUGPARAMS(fContourID(0)) SkDEBUGPARAMS(fPtTID(0)) @@ -49,6 +50,10 @@ public: }; #endif + enum { + kMaxWindingTries = 10 + }; + bool angleCoincidence() { return fAngleCoincidence; } @@ -57,6 +62,10 @@ public: return fCoincidence; } + SkOpContourHead* contourHead() { + return fContourHead; + } + #ifdef SK_DEBUG const struct SkOpAngle* debugAngle(int id) const; SkOpContour* debugContour(int id); @@ -94,6 +103,10 @@ public: fAngleCoincidence = true; } + void setContourHead(SkOpContourHead* contourHead) { + fContourHead = contourHead; + } + #if DEBUG_VALIDATE void setPhase(Phase phase) { SkASSERT(fPhase != phase); @@ -112,13 +125,13 @@ public: private: SkOpCoincidence* fCoincidence; + SkOpContourHead* fContourHead; bool fWindingFailed; bool fAngleCoincidence; #if DEBUG_VALIDATE Phase fPhase; #endif #ifdef SK_DEBUG - SkOpContour* fHead; int fAngleID; int fContourID; int fPtTID; diff --git a/src/pathops/SkPathOpsWinding.cpp b/src/pathops/SkPathOpsWinding.cpp new file mode 100644 index 0000000000..53083e484e --- /dev/null +++ b/src/pathops/SkPathOpsWinding.cpp @@ -0,0 +1,402 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +// given a prospective edge, compute its initial winding by projecting a ray +// if the ray hits another edge + // if the edge doesn't have a winding yet, hop up to that edge and start over + // concern : check for hops forming a loop + // if the edge is unsortable, or + // the intersection is nearly at the ends, or + // the tangent at the intersection is nearly coincident to the ray, + // choose a different ray and try again + // concern : if it is unable to succeed after N tries, try another edge? direction? +// if no edge is hit, compute the winding directly + +// given the top span, project the most perpendicular ray and look for intersections + // let's try up and then down. What the hey + +// bestXY is initialized by caller with basePt + +#include "SkOpContour.h" +#include "SkOpSegment.h" +#include "SkPathOpsCurve.h" + +enum class SkOpRayDir { + kLeft, + kTop, + kRight, + kBottom, +}; + +#if DEBUG_WINDING +const char* gDebugRayDirName[] = { + "kLeft", + "kTop", + "kRight", + "kBottom" +}; +#endif + +static int xy_index(SkOpRayDir dir) { + return static_cast<int>(dir) & 1; +} + +static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) { + return (&pt.fX)[xy_index(dir)]; +} + +static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) { + return (&pt.fX)[!xy_index(dir)]; +} + +static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) { + return (&v.fX)[xy_index(dir)]; +} + +static double pt_dydx(const SkDVector& v, SkOpRayDir dir) { + return (&v.fX)[!xy_index(dir)]; +} + +static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) { + return (&r.fLeft)[static_cast<int>(dir)]; +} + +static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) { + int i = !xy_index(dir); + return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]); +} + +static bool less_than(SkOpRayDir dir) { + return static_cast<bool>((static_cast<int>(dir) & 2) == 0); +} + +static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { + bool vPartPos = pt_dydx(v, dir) > 0; + bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0; + return vPartPos == leftBottom; +} + +struct SkOpRayHit { + SkOpRayDir makeTestBase(SkOpSpan* span, double t) { + fNext = NULL; + fSpan = span; + fT = span->t() * (1 - t) + span->next()->t() * t; + SkOpSegment* segment = span->segment(); + fSlope = segment->dSlopeAtT(fT); + fPt = segment->ptAtT(fT); + fValid = true; + return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop; + } + + SkOpRayHit* fNext; + SkOpSpan* fSpan; + SkPoint fPt; + double fT; + SkDVector fSlope; + bool fValid; +}; + +void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, + SkChunkAlloc* allocator) { + // if the bounds extreme is outside the best, we're done + SkScalar baseXY = pt_xy(base.fPt, dir); + SkScalar boundsXY = rect_side(fBounds, dir); + bool checkLessThan = less_than(dir); + if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { + return; + } + SkOpSegment* testSegment = &fHead; + do { + testSegment->rayCheck(base, dir, hits, allocator); + } while ((testSegment = testSegment->next())); +} + +void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, + SkChunkAlloc* allocator) { + if (!sideways_overlap(fBounds, base.fPt, dir)) { + return; + } + SkScalar baseXY = pt_xy(base.fPt, dir); + SkScalar boundsXY = rect_side(fBounds, dir); + bool checkLessThan = less_than(dir); + if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { + return; + } + double tVals[3]; + SkScalar baseYX = pt_yx(base.fPt, dir); + int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals); + for (int index = 0; index < roots; ++index) { + double t = tVals[index]; + if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) { + continue; + } + SkDVector slope; + SkPoint pt; + SkDEBUGCODE(sk_bzero(&slope, sizeof(slope))); + bool valid = false; + if (approximately_zero(t)) { + pt = fPts[0]; + } else if (approximately_equal(t, 1)) { + pt = fPts[SkPathOpsVerbToPoints(fVerb)]; + } else { + SkASSERT(between(0, t, 1)); + pt = this->ptAtT(t); + if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) { + if (base.fSpan->segment() == this) { + continue; + } + } else { + SkScalar ptXY = pt_xy(pt, dir); + if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) { + continue; + } + slope = this->dSlopeAtT(t); + if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this + && roughly_equal(base.fT, t) + && SkDPoint::RoughlyEqual(pt, base.fPt)) { + #if DEBUG_WINDING + SkDebugf("%s (rarely expect this)\n", __FUNCTION__); + #endif + continue; + } + if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) { + valid = true; + } + } + } + SkOpSpan* span = this->windingSpanAtT(t); + if (!span) { + valid = false; + } else if (!span->windValue() && !span->oppValue()) { + continue; + } + SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator); + newHit->fNext = *hits; + newHit->fPt = pt; + newHit->fSlope = slope; + newHit->fSpan = span; + newHit->fT = t; + newHit->fValid = valid; + *hits = newHit; + } +} + +SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { + SkOpSpan* span = &fHead; + SkOpSpanBase* next; + do { + next = span->next(); + if (approximately_equal(tHit, next->t())) { + return NULL; + } + if (tHit < next->t()) { + return span; + } + } while (!next->final() && (span = next->upCast())); + return NULL; +} + +static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { + return a->fPt.fX < b->fPt.fX; +} + +static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { + return b->fPt.fX < a->fPt.fX; +} + +static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { + return a->fPt.fY < b->fPt.fY; +} + +static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { + return b->fPt.fY < a->fPt.fY; +} + +static double get_t_guess(int tTry, int* dirOffset) { + double t = 0.5; + *dirOffset = tTry & 1; + int tBase = tTry >> 1; + int tBits = 0; + while (tTry >>= 1) { + t /= 2; + ++tBits; + } + if (tBits) { + int tIndex = (tBase - 1) & ((1 << tBits) - 1); + t += t * 2 * tIndex; + } + return t; +} + +bool SkOpSpan::sortableTop(SkOpContour* contourHead) { + SkChunkAlloc allocator(1024); + int dirOffset; + double t = get_t_guess(fTopTTry++, &dirOffset); + SkOpRayHit hitBase; + SkOpRayDir dir = hitBase.makeTestBase(this, t); + if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { + return false; + } + SkOpRayHit* hitHead = &hitBase; + dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); + SkOpContour* contour = contourHead; + do { + contour->rayCheck(hitBase, dir, &hitHead, &allocator); + } while ((contour = contour->next())); + // sort hits + SkSTArray<1, SkOpRayHit*> sorted; + SkOpRayHit* hit = hitHead; + while (hit) { + sorted.push_back(hit); + hit = hit->fNext; + } + int count = sorted.count(); + SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) + ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y + : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); + // verify windings +#if DEBUG_WINDING + SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, + gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), + hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); + for (int index = 0; index < count; ++index) { + hit = sorted[index]; + SkOpSpan* span = hit->fSpan; + SkOpSegment* hitSegment = span ? span->segment() : NULL; + bool operand = span ? hitSegment->operand() : false; + bool ccw = ccw_dxdy(hit->fSlope, dir); + SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, + hit->fValid, operand, span ? span->debugID() : -1, ccw); + if (span) { + hitSegment->dumpPtsInner(); + } + SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, + hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); + } +#endif + const SkPoint* last = NULL; + int wind = 0; + int oppWind = 0; + for (int index = 0; index < count; ++index) { + hit = sorted[index]; + if (!hit->fValid) { + return false; + } + bool ccw = ccw_dxdy(hit->fSlope, dir); + SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); + SkOpSpan* span = hit->fSpan; + SkOpSegment* hitSegment = span->segment(); + if (!span) { + return false; + } + if (span->windValue() == 0 && span->oppValue() == 0) { + continue; + } + if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { + return false; + } + if (index < count - 1) { + const SkPoint& next = sorted[index + 1]->fPt; + if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { + return false; + } + } + bool operand = hitSegment->operand(); + if (operand) { + SkTSwap(wind, oppWind); + } + int lastWind = wind; + int lastOpp = oppWind; + int windValue = ccw ? -span->windValue() : span->windValue(); + int oppValue = ccw ? -span->oppValue() : span->oppValue(); + wind += windValue; + oppWind += oppValue; + bool sumSet = false; + int spanSum = span->windSum(); + int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; + if (spanSum == SK_MinS32) { + span->setWindSum(windSum); + sumSet = true; + } else { + // the need for this condition suggests that UseInnerWinding is flawed + // happened when last = 1 wind = -1 +#if 0 + SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) + || (abs(wind) == abs(lastWind) + && (windSum ^ wind ^ lastWind) == spanSum)); +#endif + } + int oSpanSum = span->oppSum(); + int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; + if (oSpanSum == SK_MinS32) { + span->setOppSum(oppSum); + } else { +#if 0 + SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum + || (abs(oppWind) == abs(lastOpp) + && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); +#endif + } + if (sumSet) { + (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL); + (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL); + } + if (operand) { + SkTSwap(wind, oppWind); + } + last = &hit->fPt; + } + return true; +} + +SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { + SkOpSpan* span = &fHead; + SkOpSpanBase* next; + do { + next = span->next(); + if (span->done()) { + continue; + } + if (span->windSum() != SK_MinS32) { + return span; + } + if (span->sortableTop(contourHead)) { + return span; + } + } while (!next->final() && (span = next->upCast())); + return NULL; +} + +SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { + SkOpSegment* testSegment = &fHead; + do { + if (testSegment->done()) { + continue; + } + SkOpSpan* result = testSegment->findSortableTop(contourHead); + if (result) { + return result; + } + } while ((testSegment = testSegment->next())); + return NULL; +} + +SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { + for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { + SkOpContour* contour = contourHead; + do { + if (contour->done()) { + continue; + } + SkOpSpan* result = contour->findSortableTop(contourHead); + if (result) { + return result; + } + } while ((contour = contour->next())); + } + return NULL; +} |