Path ops formerly found the topmost unprocessed edge and determined its angle sort order to initialize the winding. This never worked correctly with cubics and was flaky with paths consisting mostly of vertical edges.

This replacement shoots axis-aligned rays through all intersecting edges to find the outermost one either horizontally or vertically. The resulting code is smaller and twice as fast.

To support this, most of the horizontal / vertical intersection code was rewritten and standardized, and old code supporting the top-directed winding was deleted.

Contours were pointed to by an SkTDArray. Instead, put them in a linked list, and designate the list head with its own class to ensure that methods that take lists of contours start at the top. This change removed a large percentage of memory allocations used by path ops.

TBR=reed@google.com
BUG=skia:3588

Review URL: https://codereview.chromium.org/1111333002

1 files changed, 48 insertions, 22 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);
+}