path ops work in progress

src/pathops/SkOpAngle.cpp

Index: src/pathops/SkOpAngle.cpp
===================================================================
--- src/pathops/SkOpAngle.cpp	(revision 9111)
+++ src/pathops/SkOpAngle.cpp	(working copy)
@@ -6,12 +6,10 @@
  */
 #include "SkIntersections.h"
 #include "SkOpAngle.h"
+#include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
 
-#if DEBUG_SORT || DEBUG_SORT_SINGLE
-#include "SkOpSegment.h"
-#endif
 
 // FIXME: this is bogus for quads and cubics
 // if the quads and cubics' line from end pt to ctrl pt are coincident,
@@ -31,7 +29,8 @@
 
 maybe I could set up LineParameters lazily
 */
-static int simple_compare(double x, double y, double rx, double ry) {
+static int simple_compare(double x, double y, double rx, double ry, double error) {
+    SkASSERT(error);
     if ((y < 0) ^ (ry < 0)) {  // OPTIMIZATION: better to use y * ry < 0 ?
         return y < 0;
     }
@@ -40,7 +39,7 @@
     }
     double x_ry = x * ry;
     double rx_y = rx * y;
-    double cmp = x_ry - rx_y;
+    double cmp = (x_ry - rx_y) * error;
     if (!approximately_zero(cmp)) {
         return cmp < 0;
     }
@@ -51,12 +50,18 @@
     return -1;
 }
 
+static double gError[] = {
+    0, 1, 1.0/2, 1.0/3
+};
+
 bool SkOpAngle::operator<(const SkOpAngle& rh) const {
     double x = dx();
     double y = dy();
     double rx = rh.dx();
     double ry = rh.dy();
-    int simple = simple_compare(x, y, rx, ry);
+    SkPath::Verb verb = fSegment->verb();
+    SkPath::Verb rVerb = rh.fSegment->verb();
+    int simple = simple_compare(x, y, rx, ry, gError[verb] * gError[rVerb]);
     if (simple >= 0) {
         return simple;
     }
@@ -70,16 +75,16 @@
         return fSide < rh.fSide;
     }
     // see if either curve can be lengthened and try the tangent compare again
-    if (/* cmp && */ (*fSpans)[fEnd].fOther != rh.fSegment  // tangents not absolutely identical
-            && (*rh.fSpans)[rh.fEnd].fOther != fSegment) {  // and not intersecting
+    if (fSegment->other(fEnd) != rh.fSegment  // tangents not absolutely identical
+            && rh.fSegment->other(rh.fEnd) != fSegment) {  // and not intersecting
         SkOpAngle longer = *this;
         SkOpAngle rhLonger = rh;
         if (longer.lengthen() | rhLonger.lengthen()) {
             return longer < rhLonger;
         }
     }
-    if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
-            || (rh.fVerb == SkPath::kLine_Verb
+    if ((verb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
+            || (rVerb == SkPath::kLine_Verb
             && approximately_zero(rx) && approximately_zero(ry))) {
         // See general unsortable comment below. This case can happen when
         // one line has a non-zero change in t but no change in x and y.
@@ -87,14 +92,13 @@
         rh.fUnsortable = true;
         return this < &rh;  // even with no solution, return a stable sort
     }
-    if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
-            || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
+    if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) {
         fUnsortable = true;
         rh.fUnsortable = true;
         return this < &rh;  // even with no solution, return a stable sort
     }
-    SkASSERT(fVerb >= SkPath::kQuad_Verb);
-    SkASSERT(rh.fVerb >= SkPath::kQuad_Verb);
+    SkASSERT(verb >= SkPath::kQuad_Verb);
+    SkASSERT(rVerb >= SkPath::kQuad_Verb);
     // FIXME: until I can think of something better, project a ray from the
     // end of the shorter tangent to midway between the end points
     // through both curves and use the resulting angle to sort
@@ -110,14 +114,14 @@
     do {
         useThis = (len < rlen) ^ flip;
         const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
-        SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
+        SkPath::Verb partVerb = useThis ? verb : rVerb;
         ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
             part[2] : part[1];
         ray[1].fX = (part[0].fX + part[partVerb].fX) / 2;
         ray[1].fY = (part[0].fY + part[partVerb].fY) / 2;
         SkASSERT(ray[0] != ray[1]);
-        roots = (i.*CurveRay[fVerb])(fPts, ray);
-        rroots = (ri.*CurveRay[rh.fVerb])(rh.fPts, ray);
+        roots = (i.*CurveRay[verb])(fSegment->pts(), ray);
+        rroots = (ri.*CurveRay[rVerb])(rh.fSegment->pts(), ray);
     } while ((roots == 0 || rroots == 0) && (flip ^= true));
     if (roots == 0 || rroots == 0) {
         // FIXME: we don't have a solution in this case. The interim solution
@@ -167,7 +171,7 @@
  #if 0
     SkDVector lRay = lLoc - fCurvePart[0];
     SkDVector rRay = rLoc - fCurvePart[0];
-    int rayDir = simple_compare(lRay.fX, lRay.fY, rRay.fX, rRay.fY);
+    int rayDir = simple_compare(lRay.fX, lRay.fY, rRay.fX, rRay.fY, gError[verb] * gError[rVerb]);
     SkASSERT(rayDir >= 0);
     if (rayDir < 0) {
         fUnsortable = true;
@@ -188,9 +192,13 @@
     return leftLessThanRight;
 }
 
+bool SkOpAngle::isHorizontal() const {
+    return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
+}
+
 bool SkOpAngle::lengthen() {
     int newEnd = fEnd;
-    if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+    if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
         fEnd = newEnd;
         setSpans();
         return true;
@@ -203,7 +211,7 @@
         return false;
     }
     int newEnd = fStart;
-    if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+    if (fStart > fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
         fEnd = newEnd;
         fReversed = true;
         setSpans();
@@ -217,9 +225,10 @@
     fSegment = segment;
     fStart = start;
     fEnd = end;
-    fPts = orig;
-    fVerb = verb;
-    fSpans = &spans;
+    if (fSegment->isTiny(this) && (start == 0 || end == fSegment->count() - 1)) {
+        fUnsortable = true;
+        return;
+    }
     fReversed = false;
     fUnsortable = false;
     setSpans();
@@ -227,18 +236,15 @@
 
 
 void SkOpAngle::setSpans() {
-    double startT = (*fSpans)[fStart].fT;
-    double endT = (*fSpans)[fEnd].fT;
-    switch (fVerb) {
+    fSegment->subDivide(fStart, fEnd, &fCurvePart);
+    switch (fSegment->verb()) {
     case SkPath::kLine_Verb: {
-        SkDLine l = SkDLine::SubDivide(fPts, startT, endT);
         // OPTIMIZATION: for pure line compares, we never need fTangent1.c
-        fTangent1.lineEndPoints(l);
+        fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
         fSide = 0;
         } break;
     case SkPath::kQuad_Verb: {
         SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
-        quad = SkDQuad::SubDivide(fPts, startT, endT);
         fTangent1.quadEndPoints(quad, 0, 1);
         if (dx() == 0 && dy() == 0) {
             fTangent1.quadEndPoints(quad);
@@ -247,7 +253,6 @@
         } break;
     case SkPath::kCubic_Verb: {
  //     int nextC = 2;
-        fCurvePart = SkDCubic::SubDivide(fPts, startT, endT);
         fTangent1.cubicEndPoints(fCurvePart, 0, 1);
         if (dx() == 0 && dy() == 0) {
             fTangent1.cubicEndPoints(fCurvePart, 0, 2);
@@ -262,7 +267,10 @@
  //     }
         double testTs[4];
         // OPTIMIZATION: keep inflections precomputed with cubic segment?
-        int testCount = SkDCubic::FindInflections(fPts, testTs);
+        const SkPoint* pts = fSegment->pts();
+        int testCount = SkDCubic::FindInflections(pts, testTs);
+        double startT = fSegment->t(fStart);
+        double endT = fSegment->t(fEnd);
         double limitT = endT;
         int index;
         for (index = 0; index < testCount; ++index) {
@@ -287,7 +295,7 @@
                 testT = (testT + testTs[testIndex + 1]) / 2;
             }
             // OPTIMIZE: could avoid call for t == startT, endT
-            SkDPoint pt = dcubic_xy_at_t(fPts, testT);
+            SkDPoint pt = dcubic_xy_at_t(pts, testT);
             double testSide = fTangent1.pointDistance(pt);
             if (fabs(bestSide) < fabs(testSide)) {
                 bestSide = testSide;
@@ -306,16 +314,16 @@
     int step = fStart < fEnd ? 1 : -1;  // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
     for (int index = fStart; index != fEnd; index += step) {
 #if 1
-        const SkOpSpan& thisSpan = (*fSpans)[index];
-        const SkOpSpan& nextSpan = (*fSpans)[index + step];
+        const SkOpSpan& thisSpan = fSegment->span(index);
+        const SkOpSpan& nextSpan = fSegment->span(index + step);
         if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
             continue;
         }
         fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
 #if DEBUG_UNSORTABLE
         if (fUnsortable) {
-            SkPoint iPt = (*CurvePointAtT[fVerb])(fPts, thisSpan.fT);
-            SkPoint ePt = (*CurvePointAtT[fVerb])(fPts, nextSpan.fT);
+            SkPoint iPt = fSegment->xyAtT(index);
+            SkPoint ePt = fSegment->xyAtT(index + step);
             SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
                     index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
         }
@@ -330,8 +338,8 @@
     }
 #if 1
 #if DEBUG_UNSORTABLE
-    SkPoint iPt = (*CurvePointAtT[fVerb])(fPts, startT);
-    SkPoint ePt = (*CurvePointAtT[fVerb])(fPts, endT);
+    SkPoint iPt = fSegment->xyAtT(fStart);
+    SkPoint ePt = fSegment->xyAtT(fEnd);
     SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
         fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
 #endif