path ops -- rewrite angle sort

This is a major change resulting from a minor
tweak. In the old code, the intersection point
of two curves was shared between them, but the
intersection points and end points of sorted edges was
computed directly from the intersection T value.

In this CL, both intersection points and sorted points
are the same, and intermediate control points are computed
to preserve their slope.

The sort itself has been completely rewritten to be more
robust and remove 'magic' checks, conditions that empirically
worked but couldn't be rationalized.

This CL was triggered by errors generated computing the clips
of SKP files. At this point, all 73M standard tests work and
at least the first troublesome SKPs work.

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

git-svn-id: http://skia.googlecode.com/svn/trunk@9432 2bbb7eff-a529-9590-31e7-b0007b416f81

21 files changed, 658 insertions, 292 deletions

diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 922c1030d1..5106bbba98 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -426,6 +426,35 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
             && pt[0].approximatelyEqual(pt[1])) {
         removeOne(used() - 2);
     }
+    // vet the pairs of t values to see if the mid value is also on the curve. If so, mark
+    // the span as coincident
+    if (fUsed >= 2 && !coincidentUsed()) {
+        int last = fUsed - 1;
+        int match = 0;
+        for (int index = 0; index < last; ++index) {
+            double mid1 = (fT[0][index] + fT[0][index + 1]) / 2;
+            double mid2 = (fT[1][index] + fT[1][index + 1]) / 2;
+            pt[0] = c1.xyAtT(mid1);
+            pt[1] = c2.xyAtT(mid2);
+            if (pt[0].approximatelyEqual(pt[1])) {
+                match |= 1 << index;
+            }
+        }
+        if (match) {
+            if (((match + 1) & match) != 0) {
+                SkDebugf("%s coincident hole\n", __FUNCTION__);
+            }
+            // for now, assume that everything from start to finish is coincident
+            if (fUsed > 2) {
+                  fPt[1] = fPt[last];
+                  fT[0][1] = fT[0][last];
+                  fT[1][1] = fT[1][last];
+                  fIsCoincident[0] = 0x03;
+                  fIsCoincident[1] = 0x03;
+                  fUsed = 2;
+            }
+        }
+    }
     return fUsed;
 }
 
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index b1e1783e57..13c0dbbef4 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -34,6 +34,47 @@ int SkIntersections::computePoints(const SkDLine& line, int used) {
     return fUsed;
 }
 
+int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
+    double axLen = a[1].fX - a[0].fX;
+    double ayLen = a[1].fY - a[0].fY;
+    double bxLen = b[1].fX - b[0].fX;
+    double byLen = b[1].fY - b[0].fY;
+    /* Slopes match when denom goes to zero:
+                      axLen / ayLen ==                   bxLen / byLen
+    (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
+             byLen  * axLen         ==  ayLen          * bxLen
+             byLen  * axLen         -   ayLen          * bxLen == 0 ( == denom )
+     */
+    double denom = byLen * axLen - ayLen * bxLen;
+    double ab0y = a[0].fY - b[0].fY;
+    double ab0x = a[0].fX - b[0].fX;
+    double numerA = ab0y * bxLen - byLen * ab0x;
+    double numerB = ab0y * axLen - ayLen * ab0x;
+    numerA /= denom;
+    numerB /= denom;
+    int used;
+    if (!approximately_zero(denom)) {
+        fT[0][0] = numerA;
+        fT[1][0] = numerB;
+        used = 1;
+    } else {
+       /* See if the axis intercepts match:
+                  ay - ax * ayLen / axLen  ==          by - bx * ayLen / axLen
+         axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
+         axLen *  ay - ax * ayLen          == axLen *  by - bx * ayLen
+        */
+        if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX,
+                axLen * b[0].fY - ayLen * b[0].fX)) {
+            return fUsed = 0;
+        }
+        // there's no great answer for intersection points for coincident rays, but return something
+        fT[0][0] = fT[1][0] = 0;
+        fT[1][0] = fT[1][1] = 1;
+        used = 2;
+    }
+    return computePoints(a, used);
+}
+
 /*
    Determine the intersection point of two line segments
    Return FALSE if the lines don't intersect
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 5df08ac069..b6a1761781 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -19,12 +19,14 @@
  * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D(at^2+bt+c)+E(dt^2+et+f)+F
  */
 
-static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4],
-        bool oneHint, int firstCubicRoot) {
+static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots[4],
+        bool oneHint, bool flip, int firstCubicRoot) {
+    SkDQuad flipped;
+    const SkDQuad& q = flip ? (flipped = quad.flip()) : quad;
     double a, b, c;
-    SkDQuad::SetABC(&q2[0].fX, &a, &b, &c);
+    SkDQuad::SetABC(&q[0].fX, &a, &b, &c);
     double d, e, f;
-    SkDQuad::SetABC(&q2[0].fY, &d, &e, &f);
+    SkDQuad::SetABC(&q[0].fY, &d, &e, &f);
     const double t4 =     i.x2() *  a * a
                     +     i.xy() *  a * d
                     +     i.y2() *  d * d;
@@ -48,10 +50,15 @@ static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4
                     +     i.y()  *  f
                     +     i.c();
     int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots);
-    if (rootCount >= 0) {
-        return rootCount;
+    if (rootCount < 0) {
+        rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots);
     }
-    return SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots);
+    if (flip) {
+        for (int index = 0; index < rootCount; ++index) {
+            roots[index] = 1 - roots[index];
+        }
+    }
+    return rootCount;
 }
 
 static int addValidRoots(const double roots[4], const int count, double valid[4]) {
@@ -403,9 +410,11 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
         return fUsed;
     }
     int index;
-    bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0];
+    bool flip1 = q1[2] == q2[0];
+    bool flip2 = q1[0] == q2[2];
+    bool useCubic = q1[0] == q2[0];
     double roots1[4];
-    int rootCount = findRoots(i2, q1, roots1, useCubic, 0);
+    int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
     // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
     double roots1Copy[4];
     int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
@@ -414,7 +423,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
         pts1[index] = q1.xyAtT(roots1Copy[index]);
     }
     double roots2[4];
-    int rootCount2 = findRoots(i1, q2, roots2, useCubic, 0);
+    int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
     double roots2Copy[4];
     int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
     SkDPoint pts2[4];
@@ -427,9 +436,9 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
                 insert(roots1Copy[0], roots2Copy[0], pts1[0]);
             } else if (pts1[0].moreRoughlyEqual(pts2[0])) {
                 // experiment: try to find intersection by chasing t
-                rootCount = findRoots(i2, q1, roots1, useCubic, 0);
+                rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
                 (void) addValidRoots(roots1, rootCount, roots1Copy);
-                rootCount2 = findRoots(i1, q2, roots2, useCubic, 0);
+                rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
                 (void) addValidRoots(roots2, rootCount2, roots2Copy);
                 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {
                     insert(roots1Copy[0], roots2Copy[0], pts1[0]);
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index 72f801bb1b..ace8474d1d 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -23,7 +23,7 @@ int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
 
 int SkIntersections::coincidentUsed() const {
     if (!fIsCoincident[0]) {
-        SkASSERT(!fIsCoincident[0]);
+        SkASSERT(!fIsCoincident[1]);
         return 0;
     }
     int count = 0;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 83ff6b1549..23470d7884 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -207,9 +207,10 @@ public:
     int intersect(const SkDCubic&, const SkDLine&);
     int intersect(const SkDCubic&, const SkDQuad&);
     int intersect(const SkDCubic&, const SkDCubic&);
-    int intersectRay(const SkDCubic& , const SkDLine&);
-    int intersectRay(const SkDQuad& , const SkDLine&);
-    static SkDPoint Line(const SkDLine& , const SkDLine&);
+    int intersectRay(const SkDLine&, const SkDLine&);
+    int intersectRay(const SkDQuad&, const SkDLine&);
+    int intersectRay(const SkDCubic&, const SkDLine&);
+    static SkDPoint Line(const SkDLine&, const SkDLine&);
     void offset(int base, double start, double end);
     void quickRemoveOne(int index, int replace);
     static bool Test(const SkDLine& , const SkDLine&);
diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h
index 5139c6c6cf..8824e54bb1 100644
--- a/src/pathops/SkLineParameters.h
+++ b/src/pathops/SkLineParameters.h
@@ -24,28 +24,37 @@
 class SkLineParameters {
 public:
     void cubicEndPoints(const SkDCubic& pts) {
-        cubicEndPoints(pts, 0, 3);
+        cubicEndPoints(pts, 0, 1);
+        if (dx() == 0 && dy() == 0) {
+            cubicEndPoints(pts, 0, 2);
+            if (dx() == 0 && dy() == 0) {
+                cubicEndPoints(pts, 0, 3);
+            }
+        }
     }
 
     void cubicEndPoints(const SkDCubic& pts, int s, int e) {
-        a = approximately_pin(pts[s].fY - pts[e].fY);
-        b = approximately_pin(pts[e].fX - pts[s].fX);
+        a = pts[s].fY - pts[e].fY;
+        b = pts[e].fX - pts[s].fX;
         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
     }
 
     void lineEndPoints(const SkDLine& pts) {
-        a = approximately_pin(pts[0].fY - pts[1].fY);
-        b = approximately_pin(pts[1].fX - pts[0].fX);
+        a = pts[0].fY - pts[1].fY;
+        b = pts[1].fX - pts[0].fX;
         c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
     }
 
     void quadEndPoints(const SkDQuad& pts) {
-        quadEndPoints(pts, 0, 2);
+        quadEndPoints(pts, 0, 1);
+        if (dx() == 0 && dy() == 0) {
+            quadEndPoints(pts, 0, 2);
+        }
     }
 
     void quadEndPoints(const SkDQuad& pts, int s, int e) {
-        a = approximately_pin(pts[s].fY - pts[e].fY);
-        b = approximately_pin(pts[e].fX - pts[s].fX);
+        a = pts[s].fY - pts[e].fY;
+        b = pts[e].fX - pts[s].fX;
         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
     }
 
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index dee2906b7f..c295bfb9d8 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -6,95 +6,169 @@
  */
 #include "SkIntersections.h"
 #include "SkOpAngle.h"
+#include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
 
-#if DEBUG_SORT || DEBUG_SORT_SINGLE
-#include "SkOpSegment.h"
+#if DEBUG_ANGLE
+#include "SkString.h"
+
+static const char funcName[] = "SkOpSegment::operator<";
+static const int bugChar = strlen(funcName) + 1;
+#endif
+
+/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
+   positive y. The largest angle has a positive x and a zero y. */
+
+#if DEBUG_ANGLE
+    static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
+        bugOut->appendf(append);
+        bugOut->writable_str()[bugChar] = "><"[compare];
+        SkDebugf("%s\n", bugOut->c_str());
+        return compare;
+    }
+
+    #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
+#else
+    #define COMPARE_RESULT(append, compare) compare   
 #endif
 
-// FIXME: this is bogus for quads and cubics
-// if the quads and cubics' line from end pt to ctrl pt are coincident,
-// there's no obvious way to determine the curve ordering from the
-// derivatives alone. In particular, if one quadratic's coincident tangent
-// is longer than the other curve, the final control point can place the
-// longer curve on either side of the shorter one.
-// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
-// may provide some help, but nothing has been figured out yet.
+bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{
+    double absX = fabs(x);
+    double absY = fabs(y);
+    double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
+    int exponent;
+    (void) frexp(length, &exponent);
+    double epsilon = ldexp(FLT_EPSILON, exponent);
+    SkPath::Verb verb = fSegment->verb();
+    SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
+    // FIXME: the quad and cubic factors are made up ; determine actual values
+    double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
+    double xSlop = slop;
+    double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
+    double x1 = x - xSlop;
+    double y1 = y + ySlop;
+    double x_ry1 = x1 * ry;
+    double rx_y1 = rx * y1;
+    *result = x_ry1 < rx_y1;
+    double x2 = x + xSlop;
+    double y2 = y - ySlop;
+    double x_ry2 = x2 * ry;
+    double rx_y2 = rx * y2;
+    bool less2 = x_ry2 < rx_y2;
+    return *result == less2;
+}
 
-/*(
+/*
 for quads and cubics, set up a parameterized line (e.g. LineParameters )
 for points [0] to [1]. See if point [2] is on that line, or on one side
 or the other. If it both quads' end points are on the same side, choose
 the shorter tangent. If the tangents are equal, choose the better second
 tangent angle
 
-maybe I could set up LineParameters lazily
+FIXME: maybe I could set up LineParameters lazily
 */
-static int simple_compare(double x, double y, double rx, double ry) {
-    if ((y < 0) ^ (ry < 0)) {  // OPTIMIZATION: better to use y * ry < 0 ?
-        return y < 0;
-    }
-    if (y == 0 && ry == 0 && x * rx < 0) {
-        return x < rx;
-    }
-    double x_ry = x * ry;
-    double rx_y = rx * y;
-    double cmp = x_ry - rx_y;
-    if (!approximately_zero(cmp)) {
-        return cmp < 0;
-    }
-    if (approximately_zero(x_ry) && approximately_zero(rx_y)
-            && !approximately_zero_squared(cmp)) {
-        return cmp < 0;
-    }
-    return -1;
-}
-
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {
-    double x = dx();
+bool SkOpAngle::operator<(const SkOpAngle& rh) const {  // this/lh: left-hand; rh: right-hand
     double y = dy();
-    double rx = rh.dx();
     double ry = rh.dy();
-    int simple = simple_compare(x, y, rx, ry);
-    if (simple >= 0) {
-        return simple;
+#if DEBUG_ANGLE
+    SkString bugOut;
+    bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g"
+        " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName,
+        fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd),
+        rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
+#endif
+    double y_ry = y * ry;
+    if (y_ry < 0) {  // if y's are opposite signs, we can do a quick return
+        return COMPARE_RESULT("1 y * ry < 0", y < 0);
     }
-    // at this point, the initial tangent line is coincident
-    // see if edges curl away from each other
-    if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
-            || !approximately_zero(rh.fSide))) {
-        // FIXME: running demo will trigger this assertion
-        // (don't know if commenting out will trigger further assertion or not)
-        // commenting it out allows demo to run in release, though
-        return fSide < rh.fSide;
+    // at this point, both y's must be the same sign, or one (or both) is zero
+    double x = dx();
+    double rx = rh.dx();
+    if (x * rx < 0) {  // if x's are opposite signs, use y to determine first or second half
+        if (y < 0 && ry < 0) {  // if y's are negative, lh x is smaller if positive
+            return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0);
+        }
+        if (y >= 0 && ry >= 0) {  // if y's are zero or positive, lh x is smaller if negative
+            return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0);
+        }
+        SkASSERT((y == 0) ^ (ry == 0));  // if one y is zero and one is negative, neg y is smaller
+        return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0);
     }
-    // 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
+    // at this point, both x's must be the same sign, or one (or both) is zero
+    if (y_ry == 0) { // if either y is zero
+        if (y + ry < 0) { // if the other y is less than zero, it must be smaller
+            return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0);
+        }
+        if (y + ry > 0) { // if a y is greater than zero and an x is positive,  non zero is smaller
+            return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0));
+        }
+        // at this point, both y's are zero, so lines are coincident or one is degenerate
+        SkASSERT(x * rx != 0);  // and a degenerate line should haven't gotten this far
+    } 
+    // see if either curve can be lengthened before trying the tangent
+    if (fSegment->other(fEnd) != rh.fSegment  // tangents not absolutely identical
+            && rh.fSegment->other(rh.fEnd) != fSegment) {  // and not intersecting
         SkOpAngle longer = *this;
         SkOpAngle rhLonger = rh;
-        if (longer.lengthen() | rhLonger.lengthen()) {
-            return longer < rhLonger;
+        if ((longer.lengthen(rh) | rhLonger.lengthen(*this))  // lengthen both
+                && (fUnorderable || !longer.fUnorderable)
+                && (rh.fUnorderable || !rhLonger.fUnorderable)) {
+#if DEBUG_ANGLE
+            bugOut.prepend("  ");
+#endif
+            return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
+        }
+    }
+    if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
+        // at this point, y's are the same sign, neither is zero
+        //   and x's are the same sign, or one (or both) is zero
+        double x_ry = x * ry;
+        double rx_y = rx * y;
+        if (!fComputed && !rh.fComputed) {
+            if (!AlmostEqualUlps(x_ry, rx_y)) {
+                return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
+            }
+        } else {
+            // if the vector was a result of subdividing a curve, see if it is stable
+            bool sloppy1 = x_ry < rx_y;
+            bool sloppy2 = !sloppy1;
+            if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) 
+                    && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2))
+                    && sloppy1 != sloppy2) {
+                return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1);
+            }
         }
     }
-    if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
-            || (rh.fVerb == SkPath::kLine_Verb
-            && approximately_zero(rx) && approximately_zero(ry))) {
+    if (fSide * rh.fSide == 0) {
+        SkASSERT(fSide + rh.fSide != 0);
+        return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide);
+    }
+    // at this point, the initial tangent line is nearly coincident
+    // see if edges curl away from each other
+    if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) {
+        return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide);
+    }
+    if (fUnsortable || rh.fUnsortable) {
+        // even with no solution, return a stable sort
+        return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
+    }
+    SkPath::Verb verb = fSegment->verb();
+    SkPath::Verb rVerb = rh.fSegment->verb();
+    if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
+            || (rVerb == SkPath::kLine_Verb
+            && approximately_zero(ry) && approximately_zero(rx))) {
         // See general unsortable comment below. This case can happen when
         // one line has a non-zero change in t but no change in x and y.
         fUnsortable = true;
-        rh.fUnsortable = true;
-        return this < &rh;  // even with no solution, return a stable sort
+        return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh);
     }
-    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
+        return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh);
     }
-    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,22 +184,20 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const {
     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[SkPathOpsVerbToPoints(partVerb)].fX) / 2;
-        ray[1].fY = (part[0].fY + part[SkPathOpsVerbToPoints(partVerb)].fY) / 2;
+        ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]);
         SkASSERT(ray[0] != ray[1]);
-        roots = (i.*CurveRay[SkPathOpsVerbToPoints(fVerb)])(fPts, ray);
-        rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rh.fVerb)])(rh.fPts, ray);
+        roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray);
+        rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray);
     } while ((roots == 0 || rroots == 0) && (flip ^= true));
     if (roots == 0 || rroots == 0) {
         // FIXME: we don't have a solution in this case. The interim solution
         // is to mark the edges as unsortable, exclude them from this and
         // future computations, and allow the returned path to be fragmented
         fUnsortable = true;
-        rh.fUnsortable = true;
-        return this < &rh;  // even with no solution, return a stable sort
+        return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
     }
     SkASSERT(fSide != 0 && rh.fSide != 0);
     SkASSERT(fSide * rh.fSide > 0); // both are the same sign
@@ -164,105 +236,96 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const {
             break;
         }
     }
- #if 0
-    SkDVector lRay = lLoc - fCurvePart[0];
-    SkDVector rRay = rLoc - fCurvePart[0];
-    int rayDir = simple_compare(lRay.fX, lRay.fY, rRay.fX, rRay.fY);
-    SkASSERT(rayDir >= 0);
-    if (rayDir < 0) {
-        fUnsortable = true;
-        rh.fUnsortable = true;
-        return this < &rh;  // even with no solution, return a stable sort
-    }
-#endif
-   if (flip) {
+    if (flip) {
         leftLessThanRight = !leftLessThanRight;
-  //      rayDir = !rayDir;
     }
-#if 0 && (DEBUG_SORT || DEBUG_SORT_SINGLE)
-    SkDebugf("%d %c %d (fSide %c 0) loc={{%1.9g,%1.9g}, {%1.9g,%1.9g}} flip=%d rayDir=%d\n",
-                fSegment->debugID(), "><"[leftLessThanRight], rh.fSegment->debugID(),
-                "<>"[fSide > 0], lLoc.fX, lLoc.fY, rLoc.fX, rLoc.fY, flip, rayDir);
-#endif
-//    SkASSERT(leftLessThanRight == (bool) rayDir);
-    return leftLessThanRight;
+    return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight);
 }
 
-bool SkOpAngle::lengthen() {
-    int newEnd = fEnd;
-    if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
-        fEnd = newEnd;
-        setSpans();
-        return true;
-    }
-    return false;
+bool SkOpAngle::isHorizontal() const {
+    return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
 }
 
-bool SkOpAngle::reverseLengthen() {
-    if (fReversed) {
+// lengthen cannot cross opposite angle
+bool SkOpAngle::lengthen(const SkOpAngle& opp) {
+    if (fSegment->other(fEnd) == opp.fSegment) {
         return false;
     }
-    int newEnd = fStart;
-    if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+    // FIXME: make this a while loop instead and make it as large as possible?
+    int newEnd = fEnd;
+    if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
         fEnd = newEnd;
-        fReversed = true;
         setSpans();
         return true;
     }
     return false;
 }
 
-void SkOpAngle::set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment,
-        int start, int end, const SkTDArray<SkOpSpan>& spans) {
+void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
     fSegment = segment;
     fStart = start;
     fEnd = end;
-    fPts = orig;
-    fVerb = verb;
-    fSpans = &spans;
-    fReversed = false;
-    fUnsortable = false;
     setSpans();
 }
 
-
 void SkOpAngle::setSpans() {
-    double startT = (*fSpans)[fStart].fT;
-    double endT = (*fSpans)[fEnd].fT;
-    switch (fVerb) {
+    fUnorderable = false;
+    if (fSegment->verb() == SkPath::kLine_Verb) {
+        fUnsortable = false;
+    } else {
+        // if start-1 exists and is tiny, then start pt may have moved
+        int smaller = SkMin32(fStart, fEnd);
+        int tinyCheck = smaller;
+        while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) {
+            --tinyCheck;
+        }
+        if ((fUnsortable = smaller > 0 && tinyCheck == 0)) {
+            return;
+        }
+        int larger = SkMax32(fStart, fEnd);
+        tinyCheck = larger;
+        int max = fSegment->count() - 1;
+        while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) {
+            ++tinyCheck;
+        }
+        if ((fUnsortable = larger < max && tinyCheck == max)) {
+            return;
+        }
+    }
+    fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
+    // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
+    // rounding the curve part to float precision here
+    // fCurvePart.round(fSegment->verb());
+    switch (fSegment->verb()) {
     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);
-        }
+        fTangent1.quadEndPoints(quad);
         fSide = -fTangent1.pointDistance(fCurvePart[2]);  // not normalized -- compare sign only
-        } 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);
- //         nextC = 3;
-            if (dx() == 0 && dy() == 0) {
-                fTangent1.cubicEndPoints(fCurvePart, 0, 3);
+        if (fComputed && dx() > 0 && approximately_zero(dy())) {
+            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
+            int last = fSegment->count() - 1;
+            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
+            SkLineParameters origTan;
+            origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
+            if ((fUnorderable = origTan.dx() <= 0
+                    || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match?
+                return;
             }
         }
- //     fSide = -fTangent1.pointDistance(fCurvePart[nextC]);  // compare sign only
- //     if (nextC == 2 && approximately_zero(fSide)) {
- //         fSide = -fTangent1.pointDistance(fCurvePart[3]);
- //     }
+        } break;
+    case SkPath::kCubic_Verb: {
+        fTangent1.cubicEndPoints(fCurvePart);
         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,35 +350,62 @@ void SkOpAngle::setSpans() {
                 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;
             }
         }
         fSide = -bestSide;  // compare sign only
+        if (fComputed && dx() > 0 && approximately_zero(dy())) {
+            SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
+            int last = fSegment->count() - 1;
+            fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
+            SkLineParameters origTan;
+            origTan.cubicEndPoints(origCurve);
+            if ((fUnorderable = origTan.dx() <= 0)) {
+                fUnsortable = fSegment->isTiny(this);
+                return;
+            }
+            // if one is < 0 and the other is >= 0
+            if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) {
+                fUnsortable = fSegment->isTiny(this);
+                return;
+            }
+            SkDCubicPair split = origCurve.chopAt(startT);
+            SkLineParameters splitTan;
+            splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
+            if ((fUnorderable = splitTan.dx() <= 0)) {
+                fUnsortable = fSegment->isTiny(this);
+                return;
+            }
+            // if one is < 0 and the other is >= 0
+            if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) {
+                fUnsortable = fSegment->isTiny(this);
+                return;
+            }
+        } 
         } break;
     default:
         SkASSERT(0);
     }
-    fUnsortable = dx() == 0 && dy() == 0;
-    if (fUnsortable) {
+    if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
         return;
     }
     SkASSERT(fStart != fEnd);
     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[SkPathOpsVerbToPoints(fVerb)])(fPts, thisSpan.fT);
-            SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(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 +420,8 @@ void SkOpAngle::setSpans() {
     }
 #if 1
 #if DEBUG_UNSORTABLE
-    SkPoint iPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, startT);
-    SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(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
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index 00520ecf43..cca1a224dd 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -8,10 +8,10 @@
 #define SkOpAngle_DEFINED
 
 #include "SkLineParameters.h"
-#include "SkOpSpan.h"
 #include "SkPath.h"
 #include "SkPathOpsCubic.h"
-#include "SkTDArray.h"
+
+class SkOpSegment;
 
 // sorting angles
 // given angles of {dx dy ddx ddy dddx dddy} sort them
@@ -19,6 +19,8 @@ class SkOpAngle {
 public:
     bool operator<(const SkOpAngle& rh) const;
 
+    bool calcSlop(double x, double y, double rx, double ry, bool* result) const;
+
     double dx() const {
         return fTangent1.dx();
     }
@@ -31,17 +33,9 @@ public:
         return fEnd;
     }
 
-    bool isHorizontal() const {
-        return dy() == 0 && fVerb == SkPath::kLine_Verb;
-    }
-
-    bool lengthen();
-    bool reverseLengthen();
-
-    void set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment,
-            int start, int end, const SkTDArray<SkOpSpan>& spans);
+    bool isHorizontal() const;
 
-    void setSpans();
+    void set(const SkOpSegment* segment, int start, int end);
 
     SkOpSegment* segment() const {
         return const_cast<SkOpSegment*>(fSegment);
@@ -51,44 +45,47 @@ public:
         return SkSign32(fStart - fEnd);
     }
 
-    const SkTDArray<SkOpSpan>* spans() const {
-        return fSpans;
-    }
-
     int start() const {
         return fStart;
     }
 
+    bool unorderable() const {
+        return fUnorderable;
+    }
+
     bool unsortable() const {
         return fUnsortable;
     }
 
 #if DEBUG_ANGLE
-    const SkPoint* pts() const {
-        return fPts;
-    }
-
-    SkPath::Verb verb() const {
-        return fVerb;
-    }
-
     void debugShow(const SkPoint& a) const {
         SkDebugf("    d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
     }
+
+    void setID(int id) {
+        fID = id;
+    }
 #endif
 
 private:
-    const SkPoint* fPts;
+    bool lengthen(const SkOpAngle& );
+    void setSpans();
+
     SkDCubic fCurvePart;
-    SkPath::Verb fVerb;
     double fSide;
     SkLineParameters fTangent1;
-    const SkTDArray<SkOpSpan>* fSpans;
     const SkOpSegment* fSegment;
     int fStart;
     int fEnd;
-    bool fReversed;
+    bool fComputed; // tangent is computed, may contain some error
+    // if subdividing a quad or cubic causes the tangent to go from the maximum angle to the
+    // minimum, mark it unorderable. It still can be sorted, which is good enough for find-top
+    // but can't be ordered, and therefore can't be used to compute winding
+    bool fUnorderable; 
     mutable bool fUnsortable;  // this alone is editable by the less than operator
+#if DEBUG_ANGLE
+    int fID;
+#endif
 };
 
 #endif
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 817732e0e5..a9e20fd11a 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -209,19 +209,22 @@ void SkOpSegment::addAngle(SkTDArray<SkOpAngle>* anglesPtr, int start, int end)
     SkOpAngle* angle = anglesPtr->append();
 #if DEBUG_ANGLE
     SkTDArray<SkOpAngle>& angles = *anglesPtr;
-    if (angles.count() > 1 && !fTs[start].fTiny) {
-        SkPoint angle0Pt = (*CurvePointAtT[SkPathOpsVerbToPoints(angles[0].verb())])(angles[0].pts(),
-                (*angles[0].spans())[angles[0].start()].fT);
-        SkPoint newPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[start].fT);
-        bool match = AlmostEqualUlps(angle0Pt.fX, newPt.fX);
-        match &= AlmostEqualUlps(angle0Pt.fY, newPt.fY);
-        if (!match) {
-            SkDebugf("%s no match\n", __FUNCTION__);
-            SkASSERT(0);
+    if (angles.count() > 1) {
+        const SkOpSegment* aSeg = angles[0].segment();
+        int aStart = angles[0].start();
+        if (!aSeg->fTs[aStart].fTiny) {
+            const SkPoint& angle0Pt = aSeg->xyAtT(aStart);
+            SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts,
+                    aSeg->fTs[aStart].fT);
+#if ONE_OFF_DEBUG
+            SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__,
+                    aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY);
+#endif
+            SkASSERT(newPt.approximatelyEqual(angle0Pt));
         }
     }
 #endif
-    angle->set(fPts, fVerb, this, start, end, fTs);
+    angle->set(this, start, end);
 }
 
 void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) {
@@ -853,7 +856,8 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
     // OPTIMIZATION: check all angles to see if any have computed wind sum
     // before sorting (early exit if none)
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ...
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
 #if DEBUG_SORT
     sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
 #endif
@@ -979,7 +983,8 @@ int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hi
     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)
-    int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, top, bottom, basePt.fX, false);
+    int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
+            (fPts, top, bottom, basePt.fX, false);
     if (pts == 0 || (current && pts == 1)) {
         return bestTIndex;
     }
@@ -1126,6 +1131,9 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart
         }
         while (precisely_zero(startT - other->fTs[*nextEnd].fT));
         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
+        if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
+            return NULL;
+        }
         return other;
     }
     // more than one viable candidate -- measure angles to find best
@@ -1135,7 +1143,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(firstIndex >= 0);
@@ -1177,12 +1185,12 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart
         if (activeAngle) {
             ++activeCount;
             if (!foundAngle || (foundDone && activeCount & 1)) {
-                if (nextSegment->tiny(nextAngle)) {
+                if (nextSegment->isTiny(nextAngle)) {
                     *unsortable = true;
                     return NULL;
                 }
                 foundAngle = nextAngle;
-                foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
+                foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle);
             }
         }
         if (nextSegment->done()) {
@@ -1257,7 +1265,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(firstIndex >= 0);
@@ -1294,7 +1302,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next
         if (activeAngle) {
             ++activeCount;
             if (!foundAngle || (foundDone && activeCount & 1)) {
-                if (nextSegment->tiny(nextAngle)) {
+                if (nextSegment->isTiny(nextAngle)) {
                     *unsortable = true;
                     return NULL;
                 }
@@ -1386,7 +1394,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, false);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     if (!sortable) {
         *unsortable = true;
 #if DEBUG_SORT
@@ -1416,7 +1424,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort
         nextSegment = nextAngle->segment();
         ++activeCount;
         if (!foundAngle || (foundDone && activeCount & 1)) {
-            if (nextSegment->tiny(nextAngle)) {
+            if (nextSegment->isTiny(nextAngle)) {
                 *unsortable = true;
                 return NULL;
             }
@@ -1628,7 +1636,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort
     addTwoAngles(end, firstT, &angles);
     buildAngles(firstT, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
     int first = SK_MaxS32;
     SkScalar top = SK_ScalarMax;
     int count = sorted.count();
@@ -2081,7 +2089,8 @@ bool SkOpSegment::clockwise(int tStart, int tEnd) const {
     SkASSERT(fVerb != SkPath::kLine_Verb);
     SkPoint edge[4];
     subDivide(tStart, tEnd, edge);
-    double sum = (edge[0].fX - edge[SkPathOpsVerbToPoints(fVerb)].fX) * (edge[0].fY + edge[SkPathOpsVerbToPoints(fVerb)].fY);
+    int points = SkPathOpsVerbToPoints(fVerb);
+    double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
     if (fVerb == SkPath::kCubic_Verb) {
         SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
         if (edge[1].fY < lesser && edge[2].fY < lesser) {
@@ -2095,7 +2104,7 @@ bool SkOpSegment::clockwise(int tStart, int tEnd) const {
             }
         }
     }
-    for (int idx = 0; idx < SkPathOpsVerbToPoints(fVerb); ++idx){
+    for (int idx = 0; idx < points; ++idx){
         sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
     }
     return sum <= 0;
@@ -2334,8 +2343,8 @@ void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int*
 // exclusion in find top and others. This could be optimized to only mark
 // adjacent spans that unsortable. However, this makes it difficult to later
 // determine starting points for edge detection in find top and the like.
-bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles,
-                             SkTDArray<SkOpAngle*>* angleList) {
+bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList,
+                             SortAngleKind orderKind) {
     bool sortable = true;
     int angleCount = angles.count();
     int angleIndex;
@@ -2343,12 +2352,17 @@ bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles,
     for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
         const SkOpAngle& angle = angles[angleIndex];
         *angleList->append() = const_cast<SkOpAngle*>(&angle);
-        sortable &= !angle.unsortable();
+#if DEBUG_ANGLE
+        (*(angleList->end() - 1))->setID(angleIndex);
+#endif
+        sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+                    && angle.unorderable()));
     }
     if (sortable) {
         SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
         for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
-            if (angles[angleIndex].unsortable()) {
+            if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+                        && angles[angleIndex].unorderable())) {
                 sortable = false;
                 break;
             }
@@ -2363,20 +2377,80 @@ bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles,
     return sortable;
 }
 
-void SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+    SkASSERT(start != end);
     edge[0] = fTs[start].fPt;
-    edge[SkPathOpsVerbToPoints(fVerb)] = fTs[end].fPt;
-    if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) {
-        SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[SkPathOpsVerbToPoints(fVerb)].fX, edge[SkPathOpsVerbToPoints(fVerb)].fY }};
+    int points = SkPathOpsVerbToPoints(fVerb);
+    edge[points] = fTs[end].fPt;
+    if (fVerb == SkPath::kLine_Verb) {
+        return false;
+    }
+    double startT = fTs[start].fT;
+    double endT = fTs[end].fT;
+    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+        // don't compute midpoints if we already have them
         if (fVerb == SkPath::kQuad_Verb) {
-            edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], fTs[start].fT,
-                    fTs[end].fT).asSkPoint();
-        } else {
-            SkDCubic::SubDivide(fPts, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub);
-            edge[1] = sub[0].asSkPoint();
-            edge[2] = sub[1].asSkPoint();
+            edge[1] = fPts[1];
+            return false;
         }
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        if (start < end) {
+            edge[1] = fPts[1];
+            edge[2] = fPts[2];
+            return false;
+        }
+        edge[1] = fPts[2];
+        edge[2] = fPts[1];
+        return false;
+    }
+    const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
+    if (fVerb == SkPath::kQuad_Verb) {
+        edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
+    } else {
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        SkDPoint ctrl[2];
+        SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
+        edge[1] = ctrl[0].asSkPoint();
+        edge[2] = ctrl[1].asSkPoint();
     }
+    return true;
+}
+
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
+    SkASSERT(start != end);
+    (*result)[0].set(fTs[start].fPt);
+    int points = SkPathOpsVerbToPoints(fVerb);
+    (*result)[points].set(fTs[end].fPt);
+    if (fVerb == SkPath::kLine_Verb) {
+        return false;
+    }
+    double startT = fTs[start].fT;
+    double endT = fTs[end].fT;
+    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+        // don't compute midpoints if we already have them
+        if (fVerb == SkPath::kQuad_Verb) {
+            (*result)[1].set(fPts[1]);
+            return false;
+        }
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        if (start < end) {
+            (*result)[1].set(fPts[1]);
+            (*result)[2].set(fPts[2]);
+            return false;
+        }
+        (*result)[1].set(fPts[2]);
+        (*result)[2].set(fPts[1]);
+        return false;
+    }
+    if (fVerb == SkPath::kQuad_Verb) {
+        (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
+    } else {
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
+    }
+    return true;
 }
 
 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
@@ -2385,13 +2459,17 @@ void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) c
     (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
 }
 
-bool SkOpSegment::tiny(const SkOpAngle* angle) const {
+bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
     int start = angle->start();
     int end = angle->end();
     const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
     return mSpan.fTiny;
 }
 
+bool SkOpSegment::isTiny(int index) const {
+    return fTs[index].fTiny;
+}
+
 void SkOpSegment::TrackOutside(SkTDArray<double>* outsideTs, double end, double start) {
     int outCount = outsideTs->count();
     if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) {
@@ -2735,8 +2813,8 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTDArray<SkOpAngle*>& an
         }
         SkDebugf("%s [%d] %s", __FUNCTION__, index,
                 angle.unsortable() ? "*** UNSORTABLE *** " : "");
-    #if COMPACT_DEBUG_SORT
-        SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)",
+    #if DEBUG_SORT_COMPACT
+        SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
                 segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
                 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
                 segment.xAtT(&eSpan), segment.yAtT(&eSpan));
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index e489acfb02..b26bad14a6 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -8,6 +8,7 @@
 #define SkOpSegment_DEFINE
 
 #include "SkOpAngle.h"
+#include "SkOpSpan.h"
 #include "SkPathOpsBounds.h"
 #include "SkPathOpsCurve.h"
 #include "SkTDArray.h"
@@ -40,6 +41,10 @@ public:
         return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
     }
 
+    int count() const {
+        return fTs.count();
+    }
+
     bool done() const {
         SkASSERT(fDoneSpans <= fTs.count());
         return fDoneSpans == fTs.count();
@@ -120,6 +125,10 @@ public:
         return fTs[lesser].fOppValue;
     }
 
+    const SkOpSegment* other(int index) const {
+        return fTs[index].fOther;
+    }
+
     const SkPoint* pts() const {
         return fPts;
     }
@@ -262,6 +271,8 @@ public:
     bool isLinear(int start, int end) const;
     bool isMissing(double startT) const;
     bool isSimple(int end) const;
+    bool isTiny(const SkOpAngle* angle) const;
+    bool isTiny(int index) const;
     SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
     SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
@@ -279,8 +290,14 @@ public:
     int nextSpan(int from, int step) const;
     void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
             int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
-    static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList);
-    void subDivide(int start, int end, SkPoint edge[4]) const;
+    enum SortAngleKind {
+        kMustBeOrdered_SortAngleKind, // required for winding calc
+        kMayBeUnordered_SortAngleKind // ok for find top
+    };
+    static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList,
+                           SortAngleKind );
+    bool subDivide(int start, int end, SkPoint edge[4]) const;
+    bool subDivide(int start, int end, SkDCubic* result) const;
     void undoneSpan(int* start, int* end);
     int updateOppWindingReverse(const SkOpAngle* angle) const;
     int updateWindingReverse(const SkOpAngle* angle) const;
@@ -348,7 +365,6 @@ private:
     SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
     bool serpentine(int tStart, int tEnd) const;
     void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
-    bool tiny(const SkOpAngle* angle) const;
     static void TrackOutside(SkTDArray<double>* outsideTs, double end, double start);
     int updateOppWinding(int index, int endIndex) const;
     int updateOppWinding(const SkOpAngle* angle) const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index a089d7c7f2..9215cbc84a 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -134,7 +134,8 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex)
             continue;
         }
         SkTDArray<SkOpAngle*> sorted;
-        bool sortable = SkOpSegment::SortAngles(angles, &sorted);
+        bool sortable = SkOpSegment::SortAngles(angles, &sorted,
+                SkOpSegment::kMayBeUnordered_SortAngleKind);
         int angleCount = sorted.count();
 #if DEBUG_SORT
         sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 674213c383..c644a67117 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -403,11 +403,23 @@ SkDCubic SkDCubic::subDivide(double t1, double t2) const {
     /* by = */ dst[1].fY = (my * 2 - ny) / 18;
     /* cx = */ dst[2].fX = (nx * 2 - mx) / 18;
     /* cy = */ dst[2].fY = (ny * 2 - my) / 18;
+    // FIXME: call align() ?
     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);
+#if 0
     double ex = interp_cubic_coords(&fPts[0].fX, (t1 * 2 + t2) / 3);
     double ey = interp_cubic_coords(&fPts[0].fY, (t1 * 2 + t2) / 3);
     double fx = interp_cubic_coords(&fPts[0].fX, (t1 + t2 * 2) / 3);
@@ -420,6 +432,30 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d,
     /* by = */ dst[0].fY = (my * 2 - ny) / 18;
     /* cx = */ dst[1].fX = (nx * 2 - mx) / 18;
     /* cy = */ dst[1].fY = (ny * 2 - my) / 18;
+#else
+    // this approach assumes that the control points computed directly are accurate enough
+    SkDCubic sub = subDivide(t1, t2);
+    dst[0] = sub[1] + (a - sub[0]);
+    dst[1] = sub[2] + (d - sub[3]);
+#endif
+    if (t1 == 0 || t2 == 0) {
+        align(0, 1, t1 == 0 ? &dst[0] : &dst[1]);
+    }
+    if (t1 == 1 || t2 == 1) {
+        align(3, 2, t1 == 1 ? &dst[0] : &dst[1]);
+    }
+    if (precisely_subdivide_equal(dst[0].fX, a.fX)) {
+        dst[0].fX = a.fX;
+    }
+    if (precisely_subdivide_equal(dst[0].fY, a.fY)) {
+        dst[0].fY = a.fY;
+    }
+    if (precisely_subdivide_equal(dst[1].fX, d.fX)) {
+        dst[1].fX = d.fX;
+    }
+    if (precisely_subdivide_equal(dst[1].fY, d.fY)) {
+        dst[1].fY = d.fY;
+    }
 }
 
 /* classic one t subdivision */
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 37492ddbba..c884ea9714 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -8,6 +8,7 @@
 #ifndef SkPathOpsCubic_DEFINED
 #define SkPathOpsCubic_DEFINED
 
+#include "SkPath.h"
 #include "SkPathOpsPoint.h"
 #include "SkTDArray.h"
 
@@ -32,6 +33,7 @@ struct SkDCubic {
     const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 4); return fPts[n]; }
     SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 4); return fPts[n]; }
 
+    void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; 
     double calcPrecision() const;
     SkDCubicPair chopAt(double t) const;
     bool clockwise() const;
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 2d0962b1e4..6c8ca954f1 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -68,21 +68,21 @@ static void showPathContours(SkPath::Iter& iter, const char* pathName) {
     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
         switch (verb) {
             case SkPath::kMove_Verb:
-                SkDebugf("%s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
+                SkDebugf("    %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
                 continue;
             case SkPath::kLine_Verb:
-                SkDebugf("%s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
+                SkDebugf("    %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
                 break;
             case SkPath::kQuad_Verb:
-                SkDebugf("%s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
+                SkDebugf("    %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
                     pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
                 break;
             case SkPath::kCubic_Verb:
-                SkDebugf("%s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
+                SkDebugf("    %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
                     pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
                 break;
             case SkPath::kClose_Verb:
-                SkDebugf("%s.close();\n", pathName);
+                SkDebugf("    %s.close();\n", pathName);
                 break;
             default:
                 SkDEBUGFAIL("bad verb");
@@ -98,12 +98,17 @@ static const char* gFillTypeStr[] = {
     "kInverseEvenOdd_FillType"
 };
 
+
+void ShowFunctionHeader() {
+    SkDebugf("\nstatic void test#(skiatest::Reporter* reporter) {\n");
+}
+
 void ShowPath(const SkPath& path, const char* pathName) {
     SkPath::Iter iter(path, true);
     SkPath::FillType fillType = path.getFillType();
     SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
-    SkDebugf("SkPath %s;\n", pathName);
-    SkDebugf("%s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
+    SkDebugf("    SkPath %s;\n", pathName);
+    SkDebugf("    %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
     iter.setPath(path, true);
     showPathContours(iter, pathName);
 }
@@ -117,8 +122,7 @@ static const char* gOpStrs[] = {
 };
 
 void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) {
-    SkDebugf("SkPath result;\n");
-    SkDebugf("bool success = Op(%s, %s, %s, &result);\n", pathOne, pathTwo, gOpStrs[op]);
-    SkDebugf("SkASSERT(success);\n");
+    SkDebugf("    testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]);
+    SkDebugf("}\n");
 }
 #endif
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 61b59c3189..cc1b8ead95 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -61,6 +61,7 @@ extern int gDebugMaxWindValue;
 #define DEBUG_SHOW_TEST_PROGRESS 0
 #define DEBUG_SHOW_WINDING 0
 #define DEBUG_SORT 0
+#define DEBUG_SORT_COMPACT 0
 #define DEBUG_SORT_SINGLE 0
 #define DEBUG_SWAP_TOP 0
 #define DEBUG_UNSORTABLE 0
@@ -73,7 +74,7 @@ extern int gDebugMaxWindValue;
 #define DEBUG_ACTIVE_OP 1
 #define DEBUG_ACTIVE_SPANS 1
 #define DEBUG_ACTIVE_SPANS_FIRST_ONLY 0
-#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
+#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
 #define DEBUG_ADD_INTERSECTING_TS 1
 #define DEBUG_ADD_T_PAIR 1
 #define DEBUG_ANGLE 1
@@ -90,6 +91,7 @@ extern int gDebugMaxWindValue;
 #define DEBUG_SHOW_TEST_PROGRESS 1
 #define DEBUG_SHOW_WINDING 0
 #define DEBUG_SORT 1
+#define DEBUG_SORT_COMPACT 0
 #define DEBUG_SORT_SINGLE 0
 #define DEBUG_SWAP_TOP 1
 #define DEBUG_UNSORTABLE 1
@@ -144,6 +146,7 @@ extern const char* kPathOpStr[];
 #endif
 
 #if DEBUG_SHOW_PATH
+void ShowFunctionHeader();
 void ShowPath(const SkPath& path, const char* pathName);
 void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo);
 #endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index db55635d89..f030765a61 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -37,7 +37,8 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int
             continue;
         }
         SkTDArray<SkOpAngle*> sorted;
-        bool sortable = SkOpSegment::SortAngles(angles, &sorted);
+        bool sortable = SkOpSegment::SortAngles(angles, &sorted,
+                SkOpSegment::kMayBeUnordered_SortAngleKind);
         int angleCount = sorted.count();
 #if DEBUG_SORT
         sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0);
@@ -232,6 +233,7 @@ static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
 
 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
 #if DEBUG_SHOW_PATH
+    ShowFunctionHeader();
     ShowPath(one, "path");
     ShowPath(two, "pathB");
     ShowOp(op, "path", "pathB");
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 23734c98b5..534154f199 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -117,8 +117,8 @@ struct SkDPoint {
             return true;
         }
         double inv = 1 / denom;
-        return approximately_equal(fX * inv, a.fX * inv)
-                && approximately_equal(fY * inv, a.fY * inv);
+        return approximately_equal_double(fX * inv, a.fX * inv)
+                && approximately_equal_double(fY * inv, a.fY * inv);
     }
 
     bool approximatelyEqualHalf(const SkDPoint& a) const {
@@ -151,6 +151,13 @@ struct SkDPoint {
         return temp.lengthSquared();
     }
 
+    static SkDPoint Mid(const SkDPoint& a, const SkDPoint& b) {
+        SkDPoint result;
+        result.fX = (a.fX + b.fX) / 2;
+        result.fY = (a.fY + b.fY) / 2;
+        return result;
+    }
+
     double moreRoughlyEqual(const SkDPoint& a) const {
         return more_roughly_equal(a.fY, fY) && more_roughly_equal(a.fX, fX);
     }
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 685f49e160..ce89469062 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -4,6 +4,7 @@
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
+#include "SkIntersections.h"
 #include "SkLineParameters.h"
 #include "SkPathOpsCubic.h"
 #include "SkPathOpsQuad.h"
@@ -220,12 +221,53 @@ SkDQuad SkDQuad::subDivide(double t1, double t2) const {
     return dst;
 }
 
+void SkDQuad::align(int endIndex, SkDPoint* dstPt) const {  
+    if (fPts[endIndex].fX == fPts[1].fX) {
+        dstPt->fX = fPts[endIndex].fX;
+    }
+    if (fPts[endIndex].fY == fPts[1].fY) {
+        dstPt->fY = fPts[endIndex].fY;
+    }
+}
+
 SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const {
+    SkASSERT(t1 != t2);
     SkDPoint b;
+#if 0
+    // this approach assumes that the control point computed directly is accurate enough
     double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2);
     double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2);
     b.fX = 2 * dx - (a.fX + c.fX) / 2;
     b.fY = 2 * dy - (a.fY + c.fY) / 2;
+#else
+    SkDQuad sub = subDivide(t1, t2);
+    SkDLine b0 = {{a, sub[1] + (a - sub[0])}};
+    SkDLine b1 = {{c, sub[1] + (c - sub[2])}};
+    SkIntersections i;
+    i.intersectRay(b0, b1);
+    if (i.used() == 1) {
+        b = i.pt(0);
+    } else {
+        SkASSERT(i.used() == 2 || i.used() == 0);
+        b = SkDPoint::Mid(b0[1], b1[1]);
+    }
+#endif
+    if (t1 == 0 || t2 == 0) {
+        align(0, &b);
+    }
+    if (t1 == 1 || t2 == 1) {
+        align(2, &b);
+    }
+    if (precisely_subdivide_equal(b.fX, a.fX)) {
+        b.fX = a.fX;
+    } else if (precisely_subdivide_equal(b.fX, c.fX)) {
+        b.fX = c.fX;
+    }
+    if (precisely_subdivide_equal(b.fY, a.fY)) {
+        b.fY = a.fY;
+    } else if (precisely_subdivide_equal(b.fY, c.fY)) {
+        b.fY = c.fY;
+    }
     return b;
 }
 
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index d5ca0c7443..d06f3449bf 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -19,6 +19,11 @@ struct SkDQuadPair {
 struct SkDQuad {
     SkDPoint fPts[3];
 
+    SkDQuad flip() const {
+        SkDQuad result = {{fPts[2], fPts[1], fPts[0]}};
+        return result;
+    }
+
     void set(const SkPoint pts[3]) {
         fPts[0] = pts[0];
         fPts[1] = pts[1];
@@ -29,6 +34,7 @@ struct SkDQuad {
     SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 3); return fPts[n]; }
 
     static int AddValidTs(double s[], int realRoots, double* t);
+    void align(int endIndex, SkDPoint* dstPt) const;
     SkDQuadPair chopAt(double t) const;
     SkDVector dxdyAtT(double t) const;
     static int FindExtrema(double a, double b, double c, double tValue[1]);
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 199d7be14b..b071ca5371 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -4,36 +4,31 @@
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
+#include "SkFloatBits.h"
 #include "SkPathOpsTypes.h"
 
 const int UlpsEpsilon = 16;
 
 // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
-union SkPathOpsUlpsFloat {
-    int32_t fInt;
-    float fFloat;
-
-    SkPathOpsUlpsFloat(float num = 0.0f) : fFloat(num) {}
-    bool negative() const { return fInt < 0; }
-};
-
+// FIXME: move to SkFloatBits.h
 bool AlmostEqualUlps(float A, float B) {
-    SkPathOpsUlpsFloat uA(A);
-    SkPathOpsUlpsFloat uB(B);
+    SkFloatIntUnion floatIntA, floatIntB;
+    floatIntA.fFloat = A;
+    floatIntB.fFloat = B;
     // Different signs means they do not match.
-    if (uA.negative() != uB.negative())
+    if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0))
     {
         // Check for equality to make sure +0 == -0
         return A == B;
     }
     // Find the difference in ULPs.
-    int ulpsDiff = abs(uA.fInt - uB.fInt);
+    int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
     return ulpsDiff <= UlpsEpsilon;
 }
 
 // cube root approximation using bit hack for 64-bit float
 // adapted from Kahan's cbrt
-static  double cbrt_5d(double d) {
+static double cbrt_5d(double d) {
     const unsigned int B1 = 715094163;
     double t = 0.0;
     unsigned int* pt = (unsigned int*) &t;
@@ -43,7 +38,7 @@ static  double cbrt_5d(double d) {
 }
 
 // iterative cube root approximation using Halley's method (double)
-static  double cbrta_halleyd(const double a, const double R) {
+static double cbrta_halleyd(const double a, const double R) {
     const double a3 = a * a * a;
     const double b = a * (a3 + R + R) / (a3 + a3 + R);
     return b;
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 0f689d818e..6ead79455c 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -7,8 +7,6 @@
 #ifndef SkPathOpsTypes_DEFINED
 #define SkPathOpsTypes_DEFINED
 
-#define SK_CONIC_SUPPORT_ENABLED 1
-
 #include <float.h>  // for FLT_EPSILON
 #include <math.h>   // for fabs, sqrt
 
@@ -25,7 +23,7 @@ enum SkPathOpsMask {
 };
 
 // Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
-extern bool AlmostEqualUlps(float A, float B);
+bool AlmostEqualUlps(float A, float B);
 inline bool AlmostEqualUlps(double A, double B) {
     return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
 }
@@ -34,10 +32,12 @@ inline bool AlmostEqualUlps(double A, double B) {
 // DBL_EPSILON == 2.22045e-16
 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
 const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
+const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
 const double DBL_EPSILON_ERR = DBL_EPSILON * 4;  // FIXME: tune -- allow a few bits of error
+const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
 const double ROUGH_EPSILON = FLT_EPSILON * 64;
 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
 
@@ -49,6 +49,10 @@ inline bool precisely_zero(double x) {
     return fabs(x) < DBL_EPSILON_ERR;
 }
 
+inline bool precisely_subdivide_zero(double x) {
+    return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
+}
+
 inline bool approximately_zero(float x) {
     return fabs(x) < FLT_EPSILON;
 }
@@ -61,6 +65,10 @@ inline bool approximately_zero_half(double x) {
     return fabs(x) < FLT_EPSILON_HALF;
 }
 
+inline bool approximately_zero_double(double x) {
+    return fabs(x) < FLT_EPSILON_DOUBLE;
+}
+
 inline bool approximately_zero_squared(double x) {
     return fabs(x) < FLT_EPSILON_SQUARED;
 }
@@ -69,6 +77,10 @@ inline bool approximately_zero_sqrt(double x) {
     return fabs(x) < FLT_EPSILON_SQRT;
 }
 
+inline bool roughly_zero(double x) {
+    return fabs(x) < ROUGH_EPSILON;
+}
+
 inline bool approximately_zero_inverse(double x) {
     return fabs(x) > FLT_EPSILON_INVERSE;
 }
@@ -88,10 +100,18 @@ inline bool precisely_equal(double x, double y) {
     return precisely_zero(x - y);
 }
 
+inline bool precisely_subdivide_equal(double x, double y) {
+    return precisely_subdivide_zero(x - y);
+}
+
 inline bool approximately_equal_half(double x, double y) {
     return approximately_zero_half(x - y);
 }
 
+inline bool approximately_equal_double(double x, double y) {
+    return approximately_zero_double(x - y);
+}
+
 inline bool approximately_equal_squared(double x, double y) {
     return approximately_equal(x, y);
 }
@@ -112,14 +132,6 @@ inline bool approximately_lesser_or_equal(double x, double y) {
     return x - FLT_EPSILON < y;
 }
 
-inline double approximately_pin(double x) {
-    return approximately_zero(x) ? 0 : x;
-}
-
-inline float approximately_pin(float x) {
-    return approximately_zero(x) ? 0 : x;
-}
-
 inline bool approximately_greater_than_one(double x) {
     return x > 1 - FLT_EPSILON;
 }
@@ -192,8 +204,6 @@ struct SkDTriangle;
 struct SkDCubic;
 struct SkDRect;
 
-#if SK_CONIC_SUPPORT_ENABLED
-
 inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
     int verb = (1 << points) >> 1;
 #ifdef SK_DEBUG
@@ -221,18 +231,6 @@ inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
     return points;
 }
 
-#else
-
-inline SkPath::Verb SkOpPointsToVerb(int points) {
-    return (SkPath::Verb) (points);
-}
-
-inline SkPath::Verb SkOpVerbToPoints(SkPath::Verb verb) {
-    return (int) verb ;
-}
-
-#endif
-
 inline double SkDInterp(double A, double B, double t) {
     return A + (B - A) * t;
 }