shape ops work in progress

refined line/quad intersection, made more robust
still working on edge cases

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

11 files changed, 460 insertions, 122 deletions

diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp
index 973b981a3c..1d2c2b85c9 100644
--- a/experimental/Intersection/EdgeDemo.cpp
+++ b/experimental/Intersection/EdgeDemo.cpp
@@ -233,9 +233,9 @@ static void tryRonco(const SkPath& path) {
     SkScalar cellWidth = overall.width() / divs * 2;
     SkScalar cellHeight = overall.height() / divs * 2;
     SkRect target;
-    if (true) {
-        int xDiv = 28;
-        int yDiv = 17;
+    if (1) {
+        int xDiv = 27;
+        int yDiv = 11;
         target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs,
                 overall.fTop + (overall.height() - cellHeight) * yDiv / divs,
                  cellWidth, cellHeight);
diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm
index b65a295acc..8acc283856 100644
--- a/experimental/Intersection/EdgeDemoApp.mm
+++ b/experimental/Intersection/EdgeDemoApp.mm
@@ -16,9 +16,9 @@ public:
     };
 protected:
     virtual void onDraw(SkCanvas* canvas) {
-        static int step = 0; // 12752; // 17908 ; // 17904; // drawLetters first error
+        static int step = 0; // 17909 ; // drawLetters first error
                              // drawStars triggers error at 23275
-                             // error is not easy to debug in its current state
+                             // drawStars error not easy to debug last time I checked
         static double seconds;
         if (step == -1) {
             timeval t;
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 8a8cb30c0c..c379fb2d77 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -15,14 +15,14 @@ void cubecode_test(int test);
 void Intersection_Tests() {
     int testsRun = 0;
     SimplifyNew_Test();
-    QuadraticIntersection_Test();
+    LineQuadraticIntersection_Test();
     MiniSimplify_Test();
+    QuadraticIntersection_Test();
     SimplifyAngle_Test();
     QuarticRoot_Test();
  //   QuadraticIntersection_Test();
     Simplify4x4QuadraticsThreaded_Test(testsRun);
     QuadLineIntersectThreaded_Test(testsRun);
-    LineQuadraticIntersection_Test();
     Simplify4x4RectsThreaded_Test(testsRun);
     SimplifyNondegenerate4x4TrianglesThreaded_Test(testsRun);
     SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index c1421e3603..fe12b25902 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -143,6 +143,8 @@ public:
         ++fUsed;
     }
 
+    // FIXME: all callers should be moved to regular insert. Failures are likely
+    // if two separate callers differ on whether ts are equal or not
     void insertOne(double t, int side) {
         int used = side ? fUsed2 : fUsed;
         assert(used <= 1 || fT[side][0] < fT[side][1]);
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index f730250808..b3303cf95e 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -88,7 +88,7 @@ Thus, if the slope of the line tends towards vertical, we use:
  */
 
 
-class LineQuadraticIntersections : public Intersections {
+class LineQuadraticIntersections {
 public:
 
 LineQuadraticIntersections(const Quadratic& q, const _Line& l, Intersections& i)
@@ -97,7 +97,7 @@ LineQuadraticIntersections(const Quadratic& q, const _Line& l, Intersections& i)
     , intersections(i) {
 }
 
-int intersectRay() {
+int intersectRay(double roots[2]) {
 /*
     solve by rotating line+quad so line is horizontal, then finding the roots
     set up matrix to rotate quad to x-axis
@@ -124,77 +124,128 @@ int intersectRay() {
     double C = r[0];
     A += C - 2 * B; // A = a - 2*b + c
     B -= C; // B = -(b - c)
-    return quadraticRoots(A, B, C, intersections.fT[0]);
+    return quadraticRoots(A, B, C, roots);
 }
 
 int intersect() {
-    int roots = intersectRay();
-    for (int index = 0; index < roots; ) {
-        double lineT = findLineT(intersections.fT[0][index]);
-        if (lineIntersects(lineT, index, roots)) {
-            ++index;
+    addEndPoints();
+    double rootVals[2];
+    int roots = intersectRay(rootVals);
+    for (int index = 0; index < roots; ++index) {
+        double quadT = rootVals[index];
+        double lineT = findLineT(quadT);
+        if (pinTs(quadT, lineT)) {
+            intersections.insert(quadT, lineT);
         }
     }
-    return roots;
+    return intersections.fUsed;
 }
 
-int horizontalIntersect(double axisIntercept) {
+int horizontalIntersect(double axisIntercept, double roots[2]) {
     double D = quad[2].y; // f
     double E = quad[1].y; // e
     double F = quad[0].y; // d
     D += F - 2 * E; // D = d - 2*e + f
     E -= F; // E = -(d - e)
     F -= axisIntercept;
-    return quadraticRoots(D, E, F, intersections.fT[0]);
+    return quadraticRoots(D, E, F, roots);
 }
 
-int horizontalIntersect(double axisIntercept, double left, double right) {
-    int roots = horizontalIntersect(axisIntercept);
-    for (int index = 0; index < roots; ) {
+int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
+    addHorizontalEndPoints(left, right, axisIntercept);
+    double rootVals[2];
+    int roots = horizontalIntersect(axisIntercept, rootVals);
+    for (int index = 0; index < roots; ++index) {
         double x;
-        xy_at_t(quad, intersections.fT[0][index], x, *(double*) NULL);
+        double quadT = rootVals[index];
+        xy_at_t(quad, quadT, x, *(double*) NULL);
         double lineT = (x - left) / (right - left);
-        if (lineIntersects(lineT, index, roots)) {
-            ++index;
+        if (pinTs(quadT, lineT)) {
+            intersections.insert(quadT, lineT);
         }
     }
-    return roots;
+    if (flipped) {
+        flip();
+    }
+    return intersections.fUsed;
 }
 
-int verticalIntersect(double axisIntercept) {
+int verticalIntersect(double axisIntercept, double roots[2]) {
     double D = quad[2].x; // f
     double E = quad[1].x; // e
     double F = quad[0].x; // d
     D += F - 2 * E; // D = d - 2*e + f
     E -= F; // E = -(d - e)
     F -= axisIntercept;
-    return quadraticRoots(D, E, F, intersections.fT[0]);
+    return quadraticRoots(D, E, F, roots);
 }
 
-int verticalIntersect(double axisIntercept, double top, double bottom) {
-    int roots = verticalIntersect(axisIntercept);
-    for (int index = 0; index < roots; ) {
+int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
+    addVerticalEndPoints(top, bottom, axisIntercept);
+    double rootVals[2];
+    int roots = verticalIntersect(axisIntercept, rootVals);
+    for (int index = 0; index < roots; ++index) {
         double y;
-        xy_at_t(quad, intersections.fT[0][index], *(double*) NULL, y);
+        double quadT = rootVals[index];
+        xy_at_t(quad, quadT, *(double*) NULL, y);
         double lineT = (y - top) / (bottom - top);
-        if (lineIntersects(lineT, index, roots)) {
-            ++index;
+        if (pinTs(quadT, lineT)) {
+            intersections.insert(quadT, lineT);
         }
     }
-    return roots;
+    if (flipped) {
+        flip();
+    }
+    return intersections.fUsed;
 }
 
 protected:
 
+// add endpoints first to get zero and one t values exactly
+void addEndPoints()
+{
+    for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+        for (int lIndex = 0; lIndex < 2; lIndex++) {
+            if (quad[qIndex] == line[lIndex]) {
+                intersections.insert(qIndex >> 1, lIndex);
+            }
+        }
+    }
+}
+
+void addHorizontalEndPoints(double left, double right, double y)
+{
+    for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+        if (quad[qIndex].y != y) {
+            continue;
+        }
+        if (quad[qIndex].x == left) {
+            intersections.insert(qIndex >> 1, 0);
+        }
+        if (quad[qIndex].x == right) {
+            intersections.insert(qIndex >> 1, 1);
+        }
+    }
+}
+
+void addVerticalEndPoints(double top, double bottom, double x)
+{
+    for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+        if (quad[qIndex].x != x) {
+            continue;
+        }
+        if (quad[qIndex].y == top) {
+            intersections.insert(qIndex >> 1, 0);
+        }
+        if (quad[qIndex].y == bottom) {
+            intersections.insert(qIndex >> 1, 1);
+        }
+    }
+}
+
 double findLineT(double t) {
     double x, y;
     xy_at_t(quad, t, x, y);
-    if (approximately_equal(x, line[0].x) && approximately_equal(y, line[0].y)) {
-        return 0;
-    }
-    if (approximately_equal(x, line[1].x) && approximately_equal(y, line[1].y)) {
-        return 1;
-    }
     double dx = line[1].x - line[0].x;
     double dy = line[1].y - line[0].y;
     if (fabs(dx) > fabs(dy)) {
@@ -203,19 +254,31 @@ double findLineT(double t) {
     return (y - line[0].y) / dy;
 }
 
-bool lineIntersects(double lineT, const int x, int& roots) {
-    if (!approximately_zero_or_more(lineT) || !approximately_one_or_less(lineT)) {
-        if (x < --roots) {
-            intersections.fT[0][x] = intersections.fT[0][roots];
-        }
+void flip() {
+    // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
+    int roots = intersections.fUsed;
+    for (int index = 0; index < roots; ++index) {
+        intersections.fT[1][index] = 1 - intersections.fT[1][index];
+    }
+}
+
+bool pinTs(double& quadT, double& lineT) {
+    if (!approximately_one_or_less(lineT)) {
         return false;
     }
-    if (approximately_less_than_zero(lineT)) {
+    if (!approximately_zero_or_more(lineT)) {
+        return false;
+    }
+    if (quadT < 0) {
+        quadT = 0;
+    } else if (quadT > 1) {
+        quadT = 1;
+    }
+    if (lineT < 0) {
         lineT = 0;
-    } else if (approximately_greater_than_one(lineT)) {
+    } else if (lineT > 1) {
         lineT = 1;
     }
-    intersections.fT[1][x] = lineT;
     return true;
 }
 
@@ -228,12 +291,12 @@ Intersections& intersections;
 
 // utility for pairs of coincident quads
 static double horizontalIntersect(const Quadratic& quad, const _Point& pt) {
-    Intersections intersections;
-    LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
-    int roots = q.horizontalIntersect(pt.y);
+    LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+    double rootVals[2];
+    int roots = q.horizontalIntersect(pt.y, rootVals);
     for (int index = 0; index < roots; ++index) {
         double x;
-        double t = intersections.fT[0][index];
+        double t = rootVals[index];
         xy_at_t(quad, t, x, *(double*) 0);
         if (approximately_equal(x, pt.x)) {
             return t;
@@ -243,12 +306,12 @@ static double horizontalIntersect(const Quadratic& quad, const _Point& pt) {
 }
 
 static double verticalIntersect(const Quadratic& quad, const _Point& pt) {
-    Intersections intersections;
-    LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
-    int roots = q.verticalIntersect(pt.x);
+    LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+    double rootVals[2];
+    int roots = q.verticalIntersect(pt.x, rootVals);
     for (int index = 0; index < roots; ++index) {
         double y;
-        double t = intersections.fT[0][index];
+        double t = rootVals[index];
         xy_at_t(quad, t, *(double*) 0, y);
         if (approximately_equal(y, pt.y)) {
             return t;
@@ -266,17 +329,17 @@ double axialIntersect(const Quadratic& q1, const _Point& p, bool vertical) {
 
 int horizontalIntersect(const Quadratic& quad, double left, double right,
         double y, double tRange[2]) {
-    Intersections i;
-    LineQuadraticIntersections q(quad, *((_Line*) 0), i);
-    int result = q.horizontalIntersect(y);
+    LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+    double rootVals[2];
+    int result = q.horizontalIntersect(y, rootVals);
     int tCount = 0;
     for (int index = 0; index < result; ++index) {
         double x, y;
-        xy_at_t(quad, i.fT[0][index], x, y);
+        xy_at_t(quad, rootVals[index], x, y);
         if (x < left || x > right) {
             continue;
         }
-        tRange[tCount++] = i.fT[0][index];
+        tRange[tCount++] = rootVals[index];
     }
     return tCount;
 }
@@ -284,27 +347,13 @@ int horizontalIntersect(const Quadratic& quad, double left, double right,
 int horizontalIntersect(const Quadratic& quad, double left, double right, double y,
         bool flipped, Intersections& intersections) {
     LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
-    int result = q.horizontalIntersect(y, left, right);
-    if (flipped) {
-        // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
-        for (int index = 0; index < result; ++index) {
-            intersections.fT[1][index] = 1 - intersections.fT[1][index];
-        }
-    }
-    return result;
+    return q.horizontalIntersect(y, left, right, flipped);
 }
 
 int verticalIntersect(const Quadratic& quad, double top, double bottom, double x,
         bool flipped, Intersections& intersections) {
     LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
-    int result = q.verticalIntersect(x, top, bottom);
-    if (flipped) {
-        // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
-        for (int index = 0; index < result; ++index) {
-            intersections.fT[1][index] = 1 - intersections.fT[1][index];
-        }
-    }
-    return result;
+    return q.verticalIntersect(x, top, bottom, flipped);
 }
 
 int intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
@@ -314,5 +363,5 @@ int intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
 
 int intersectRay(const Quadratic& quad, const _Line& line, Intersections& i) {
     LineQuadraticIntersections q(quad, line, i);
-    return q.intersectRay();
+    return q.intersectRay(i.fT[0]);
 }
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index 268d7d3f62..9960117c73 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -93,8 +93,7 @@ static bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Interse
         for (int i1 = 0; i1 < 3; i1 += 2) {
             for (int i2 = 0; i2 < 3; i2 += 2) {
                 if (q1[i1] == q2[i2]) {
-                    i.insertOne(i1 >> 1, 0);
-                    i.insertOne(i2 >> 1, 1);
+                    i.insert(i1 >> 1, i2 >> 1);
                 }
             }
         }
@@ -110,7 +109,6 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
     // if the quads share an end point, check to see if they overlap
 
     if (onlyEndPtsInCommon(q1, q2, i)) {
-        assert(i.insertBalanced());
         return i.intersected();
     }
     QuadImplicitForm i1(q1);
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index f33c8b183f..4785e86129 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -20,6 +20,8 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
         const int aXorMask, const int bXorMask, SkPath& simple) {
     bool firstContour = true;
     do {
+
+#if SORTABLE_CONTOURS // old way
         Segment* topStart = findTopContour(contourList);
         if (!topStart) {
             break;
@@ -28,6 +30,13 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
         // follow edges to intersection by changing the index by direction.
         int index, endIndex;
         Segment* current = topStart->findTop(index, endIndex);
+#else // new way: iterate while top is unsortable
+        int index, endIndex;
+        Segment* current = findSortableTop(contourList, index, endIndex);
+        if (!current) {
+            break;
+        }
+#endif
         int contourWinding;
         if (firstContour) {
             contourWinding = 0;
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 402661e7f8..62439d0c0b 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -26,10 +26,12 @@ int gDebugMaxWindValue = SK_MaxS32;
 #endif
 
 #define PRECISE_T_SORT 1
+#define SORTABLE_CONTOURS 0 // set to 1 for old code that works most of the time
 
 #define DEBUG_UNUSED 0 // set to expose unused functions
+#define FORCE_RELEASE 0
 
-#if 1 // set to 1 for multiple thread -- no debugging
+#if FORCE_RELEASE || defined SK_RELEASE // set force release to 1 for multiple thread -- no debugging
 
 const bool gRunTestsInOneThread = false;
 
@@ -498,7 +500,6 @@ public:
     // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
     // may provide some help, but nothing has been figured out yet.
 
- //   start here
     /*(
     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
@@ -820,6 +821,10 @@ public:
         fID = ++gSegmentID;
 #endif
     }
+    
+    bool operator<(const Segment& rh) const {
+        return fBounds.fTop < rh.fBounds.fTop;
+    }
 
     bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const {
         if (activeAngleInner(index, done, angles)) {
@@ -848,7 +853,7 @@ public:
     }
 
     bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const {
-        int next = nextSpan(index, 1);
+        int next = nextExactSpan(index, 1);
         if (next > 0) {
             const Span& upSpan = fTs[index];
             if (upSpan.fWindValue) {
@@ -860,7 +865,7 @@ public:
                 }
             }
         }
-        int prev = nextSpan(index, -1);
+        int prev = nextExactSpan(index, -1);
         // edge leading into junction
         if (prev >= 0) {
             const Span& downSpan = fTs[prev];
@@ -1658,7 +1663,7 @@ public:
         const Span& mSpan = fTs[SkMin32(start, end)];
         return mSpan.fDone;
     }
-
+    
     Segment* findNextOp(SkTDArray<Span*>& chase, bool active,
             int& nextStart, int& nextEnd, int& winding, int& spanWinding,
             bool& unsortable, ShapeOp op,
@@ -2345,10 +2350,9 @@ public:
         int count = fTs.count();
         // see if either end is not done since we want smaller Y of the pair
         bool lastDone = true;
-        bool lastUnsortableEnd;
         for (int index = 0; index < count; ++index) {
             const Span& span = fTs[index];
-            if ((!span.fDone && !span.fUnsortableStart) || (!lastDone && !lastUnsortableEnd)) {
+            if (!span.fDone || !lastDone) {
                 const SkPoint& intercept = xyAtT(&span);
                 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
                         && topPt.fX > intercept.fX)) {
@@ -2359,7 +2363,6 @@ public:
                 }
             }
             lastDone = span.fDone;
-            lastUnsortableEnd = span.fUnsortableEnd;
         }
         // sort the edges to find the leftmost
         int step = 1;
@@ -2387,8 +2390,12 @@ public:
             const Angle* angle = sorted[++firstT];
             if (angle->unsortable()) {
                 // FIXME: if all angles are unsortable, find next topmost
-                SkASSERT(firstT < angles.count() - 1);
-                continue;
+                if (firstT >= angles.count() - 1) {
+    #if SORTABLE_CONTOURS
+                    SkASSERT(0);
+    #endif
+                    return NULL;
+                }
             }
             leftSegment = angle->segment();
             tIndex = angle->end();
@@ -2422,7 +2429,7 @@ public:
 
     // OPTIMIZATION: uses tail recursion. Unwise?
     Span* innerChaseDone(int index, int step, int winding) {
-        int end = nextSpan(index, step);
+        int end = nextExactSpan(index, step);
         SkASSERT(end >= 0);
         if (multipleSpans(end)) {
             return &fTs[end];
@@ -2430,14 +2437,14 @@ public:
         const Span& endSpan = fTs[end];
         Segment* other = endSpan.fOther;
         index = endSpan.fOtherIndex;
-        int otherEnd = other->nextSpan(index, step);
+        int otherEnd = other->nextExactSpan(index, step);
         Span* last = other->innerChaseDone(index, step, winding);
         other->markDone(SkMin32(index, otherEnd), winding);
         return last;
     }
 
     Span* innerChaseWinding(int index, int step, int winding) {
-        int end = nextSpan(index, step);
+        int end = nextExactSpan(index, step);
         SkASSERT(end >= 0);
         if (multipleSpans(end)) {
             return &fTs[end];
@@ -2445,7 +2452,7 @@ public:
         const Span& endSpan = fTs[end];
         Segment* other = endSpan.fOther;
         index = endSpan.fOtherIndex;
-        int otherEnd = other->nextSpan(index, step);
+        int otherEnd = other->nextExactSpan(index, step);
         int min = SkMin32(index, otherEnd);
         if (other->fTs[min].fWindSum != SK_MinS32) {
             SkASSERT(other->fTs[min].fWindSum == winding);
@@ -2600,6 +2607,21 @@ public:
         span.fWindSum = winding;
         return &span;
     }
+    
+    void markUnsortable(int start, int end) {
+        Span* span = &fTs[start];
+        if (start < end) {
+            span->fUnsortableStart = true;
+        } else {
+            --span;
+            span->fUnsortableEnd = true;
+        }
+        if (span->fDone) {
+            return;
+        }
+        span->fDone = true;
+        fDoneSpans++;
+    }
 
     void markWinding(int index, int winding) {
     //    SkASSERT(!done());
@@ -2685,6 +2707,8 @@ public:
     // FIXME
     // this returns at any difference in T, vs. a preset minimum. It may be
     // that all callers to nextSpan should use this instead.
+    // OPTIMIZATION splitting this into separate loops for up/down steps
+    // would allow using precisely_negative instead of precisely_zero
     int nextExactSpan(int from, int step) const {
         const Span& fromSpan = fTs[from];
         int count = fTs.count();
@@ -2736,14 +2760,7 @@ public:
             Angle& angle = angles[angleIndex];
             if (angle.unsortable()) {
                 // so that it is available for early exclusion in findTop and others
-                const SkTDArray<Span>* spans = angle.spans();
-                Span* span = const_cast<Span*>(&(*spans)[angle.start()]);
-                if (angle.start() < angle.end()) {
-                    span->fUnsortableStart = true;
-                } else {
-                    --span;
-                    span->fUnsortableEnd = true;
-                }
+                angle.segment()->markUnsortable(angle.start(), angle.end());
                 result = false;
             }
         }
@@ -2800,6 +2817,10 @@ public:
         end = index;
     }
 
+    bool unsortable(int index) const {
+        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
+    }
+
     void updatePts(const SkPoint pts[]) {
         fPts = pts;
     }
@@ -2997,8 +3018,10 @@ public:
         for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
             SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
         }
-        SkDebugf(") t=%1.9g (%1.9g,%1.9g) newWindSum=%d windSum=",
-                span.fT, pt.fX, pt.fY, winding);
+        SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
+                fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
+        SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=",
+                span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding);
         if (span.fWindSum == SK_MinS32) {
             SkDebugf("?");
         } else {
@@ -3031,15 +3054,21 @@ public:
                 lastSum = windSum;
                 windSum -= segment.spanSign(&angle);
             }
-            SkDebugf("%s [%d] %s id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
-                    " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n",
-                    __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE ***" : "",
+            SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
+                    " sign=%d windValue=%d windSum=", 
+                    __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "",
                     segment.fID, kLVerbStr[segment.fVerb],
-                    start, segment.xAtT(&sSpan),
-                    segment.yAtT(&sSpan), end, segment.xAtT(&eSpan),
-                    segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue,
-                    lastSum, windSum, useInnerWinding(lastSum, windSum)
-                    ? windSum : lastSum, mSpan.fDone);
+                    start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
+                    segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(),
+                    mSpan.fWindValue);
+            if (mSpan.fWindSum == SK_MinS32) {
+                SkDebugf("?");
+            } else {
+                SkDebugf("%d", mSpan.fWindSum);
+            }
+            SkDebugf(" winding: %d->%d (max=%d) done=%d\n", lastSum, windSum,
+                    useInnerWinding(lastSum, windSum) ? windSum : lastSum,
+                    mSpan.fDone);
 #if false && DEBUG_ANGLE
             angle.debugShow(segment.xyAtT(&sSpan));
 #endif
@@ -3327,6 +3356,18 @@ public:
         fXor = isXor;
     }
 
+#if !SORTABLE_CONTOURS
+    void sortSegments() {
+        int segmentCount = fSegments.count();
+        fSortedSegments.setReserve(segmentCount);
+        for (int test = 0; test < segmentCount; ++test) {
+            *fSortedSegments.append() = &fSegments[test];
+        }
+        QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+        fFirstSorted = 0;
+    }
+#endif
+
     // OPTIMIZATION: feel pretty uneasy about this. It seems like once again
     // we need to sort and walk edges in y, but that on the surface opens the
     // same can of worms as before. But then, this is a rough sort based on
@@ -3367,6 +3408,28 @@ public:
         return bestSegment;
     }
 
+#if !SORTABLE_CONTOURS
+    Segment* topSortableSegment(SkScalar& bestY) {
+        int segmentCount = fSortedSegments.count();
+        SkASSERT(segmentCount > 0);
+        Segment* bestSegment = NULL;
+        while (fFirstSorted < segmentCount) {
+            Segment* testSegment = fSortedSegments[fFirstSorted];
+            if (testSegment->done()) {
+                fFirstSorted++;
+                continue;
+            }
+            bestSegment = testSegment;
+            break;
+        }
+        if (!bestSegment) {
+            return NULL;
+        }
+        bestY = bestSegment->activeTop();
+        return bestSegment;
+    }
+#endif
+
     Segment* undoneSegment(int& start, int& end) {
         int segmentCount = fSegments.count();
         for (int test = 0; test < segmentCount; ++test) {
@@ -3445,6 +3508,10 @@ protected:
 
 private:
     SkTArray<Segment> fSegments;
+#if !SORTABLE_CONTOURS
+    SkTDArray<Segment*> fSortedSegments;
+    int fFirstSorted;
+#endif
     SkTDArray<Coincidence> fCoincidences;
     SkTDArray<const Contour*> fCrosses;
     Bounds fBounds;
@@ -3769,6 +3836,7 @@ protected:
 #if DEBUG_ADD_INTERSECTING_TS
 static void debugShowLineIntersection(int pts, const Work& wt,
         const Work& wn, const double wtTs[2], const double wnTs[2]) {
+    return;
     if (!pts) {
         SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
                 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
@@ -3795,6 +3863,37 @@ static void debugShowLineIntersection(int pts, const Work& wt,
     SkDebugf("\n");
 }
 
+static void debugShowQuadLineIntersection(int pts, const Work& wt,
+        const Work& wn, const double wtTs[2], const double wnTs[2]) {
+    if (!pts) {
+        SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
+                " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
+                __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
+                wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+                wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
+                wt.pts()[2].fX, wt.pts()[2].fY );
+        return;
+    }
+    SkPoint wtOutPt, wnOutPt;
+    QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
+    LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
+    SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+            __FUNCTION__,
+            wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+            wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+            wtOutPt.fX, wtOutPt.fY);
+    if (pts == 2) {
+        SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+    }
+    SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+            wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
+            wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
+    if (pts == 2) {
+        SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+    }
+    SkDebugf("\n");
+}
+
 static void debugShowQuadIntersection(int pts, const Work& wt,
         const Work& wn, const double wtTs[2], const double wnTs[2]) {
     if (!pts) {
@@ -3831,6 +3930,10 @@ static void debugShowLineIntersection(int , const Work& ,
         const Work& , const double [2], const double [2]) {
 }
 
+static void debugShowQuadLineIntersection(int , const Work& ,
+        const Work& , const double [2], const double [2]) {
+}
+
 static void debugShowQuadIntersection(int , const Work& ,
         const Work& , const double [2], const double [2]) {
 }
@@ -3938,6 +4041,8 @@ static bool addIntersectTs(Contour* test, Contour* next) {
                         case Work::kQuad_Segment: {
                             swap = true;
                             pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
+                            debugShowQuadLineIntersection(pts, wt, wn,
+                                    ts.fT[1], ts.fT[0]);
                             break;
                         }
                         case Work::kCubic_Segment: {
@@ -3961,6 +4066,8 @@ static bool addIntersectTs(Contour* test, Contour* next) {
                             break;
                         case Work::kLine_Segment: {
                             pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
+                            debugShowQuadLineIntersection(pts, wt, wn,
+                                    ts.fT[1], ts.fT[0]);
                             break;
                         }
                         case Work::kQuad_Segment: {
@@ -4028,12 +4135,6 @@ static bool addIntersectTs(Contour* test, Contour* next) {
                 }
 
             }
-            int pt2 = 0;
-            int pt2inc = 1;
-            if (ts.fFlip) {
-                pt2 = pts - 1;
-                pt2inc = -1;
-            }
             for (int pt = 0; pt < pts; ++pt) {
                 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
                 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
@@ -4041,7 +4142,6 @@ static bool addIntersectTs(Contour* test, Contour* next) {
                 int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
                 wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
                 wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
-                pt2 += pt2inc;
             }
         } while (wn.advance());
     } while (wt.advance());
@@ -4232,6 +4332,7 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList,
     return winding;
 }
 
+#if SORTABLE_CONTOURS
 // OPTIMIZATION: not crazy about linear search here to find top active y.
 // seems like we should break down and do the sort, or maybe sort each
 // contours' segments?
@@ -4266,6 +4367,7 @@ static Segment* findTopContour(SkTDArray<Contour*>& contourList) {
     }
     return topStart;
 }
+#endif
 
 static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
     int contourCount = contourList.count();
@@ -4393,6 +4495,42 @@ static bool windingIsActive(int winding, int spanWinding) {
             && (!winding || !spanWinding || winding == -spanWinding);
 }
 
+#if !SORTABLE_CONTOURS
+static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
+        int& endIndex) {
+    Segment* result;
+    do {
+        int contourCount = contourList.count();
+        int cIndex = 0;
+        Segment* topStart;
+        SkScalar bestY = SK_ScalarMax;
+        Contour* contour;
+        do {
+            contour = contourList[cIndex];
+            topStart = contour->topSortableSegment(bestY);
+        } while (!topStart && ++cIndex < contourCount);
+        if (!topStart) {
+            return NULL;
+        }
+        while (++cIndex < contourCount) {
+            contour = contourList[cIndex];
+            if (bestY < contour->bounds().fTop) {
+                continue;
+            }
+            SkScalar testY = SK_ScalarMax;
+            Segment* test = contour->topSortableSegment(testY);
+            if (!test || bestY <= testY) {
+                continue;
+            }
+            topStart = test;
+            bestY = testY;
+        }
+        result = topStart->findTop(index, endIndex);
+    } while (!result);
+    return result;
+}
+#endif
+
 // Each segment may have an inside or an outside. Segments contained within
 // winding may have insides on either side, and form a contour that should be
 // ignored. Segments that are coincident with opposing direction segments may
@@ -4407,6 +4545,7 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) {
     bool firstContour = true;
     bool unsortable = false;
     do {
+#if SORTABLE_CONTOURS // old way
         Segment* topStart = findTopContour(contourList);
         if (!topStart) {
             break;
@@ -4415,6 +4554,13 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) {
         // follow edges to intersection by changing the index by direction.
         int index, endIndex;
         Segment* current = topStart->findTop(index, endIndex);
+#else // new way: iterate while top is unsortable
+        int index, endIndex;
+        Segment* current = findSortableTop(contourList, index, endIndex);
+        if (!current) {
+            break;
+        }
+#endif
         int contourWinding;
         if (firstContour) {
             contourWinding = 0;
@@ -4568,6 +4714,16 @@ static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
     }
 }
 
+#if !SORTABLE_CONTOURS
+static void sortSegments(SkTDArray<Contour*>& contourList) {
+    int contourCount = contourList.count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        Contour* contour = contourList[cTest];
+        contour->sortSegments();
+    }
+}
+#endif
+
 static void makeContourList(SkTArray<Contour>& contours,
         SkTDArray<Contour*>& list) {
     int count = contours.count();
@@ -4614,6 +4770,9 @@ void simplifyx(const SkPath& path, SkPath& simple) {
     // eat through coincident edges
     coincidenceCheck(contourList);
     fixOtherTIndex(contourList);
+#if !SORTABLE_CONTOURS
+    sortSegments(contourList);
+#endif
     // construct closed contours
     if (builder.xorMask() == kWinding_Mask
                 ? !bridgeWinding(contourList, simple)
diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp
index 0c9c2e0803..11b083f947 100644
--- a/experimental/Intersection/SimplifyFindTop_Test.cpp
+++ b/experimental/Intersection/SimplifyFindTop_Test.cpp
@@ -27,9 +27,13 @@ static const SimplifyFindTopTest::Segment* testCommon(
         addIntersectTs(contourList[1], contourList[1]);
     }
     fixOtherTIndex(contourList);
+#if SORTABLE_CONTOURS // old way
     SimplifyFindTopTest::Segment* topStart = findTopContour(contourList);
     const SimplifyFindTopTest::Segment* topSegment = topStart->findTop(index,
             end);
+#else
+    const SimplifyFindTopTest::Segment* topSegment = findSortableTop(contourList, index, end);
+#endif
     return topSegment;
 }
 
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 9841176cd3..4cd7f01b82 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2828,12 +2828,26 @@ static void testQuadratic38() {
     testSimplifyx(path);
 }
 
-static void (*firstTest)() = testQuadratic7;
+static void testQuadratic51() {
+    SkPath path;
+    path.moveTo(369.863983f, 145.645813f);
+    path.quadTo(382.380371f, 121.254936f, 406.236359f, 121.254936f);
+    path.lineTo(369.863983f, 145.645813f);
+    path.close();
+    path.moveTo(369.970581f, 137.94342f);
+    path.quadTo(383.98465f, 121.254936f, 406.235992f, 121.254936f);
+    path.lineTo(369.970581f, 137.94342f);
+    path.close();
+    testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic51;
 
 static struct {
     void (*fun)();
     const char* str;
 } tests[] = {
+    TEST(testQuadratic51),
     TEST(testQuadratic38),
     TEST(testQuadratic37),
     TEST(testQuadratic36),
@@ -3113,7 +3127,7 @@ static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
 
 static bool skipAll = false;
 static bool runSubTests = false;
-static bool runReverse = false;
+static bool runReverse = true;
 
 void SimplifyNew_Test() {
     if (skipAll) {
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index eb737ab8a1..e1c01882d4 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -2317,11 +2317,114 @@ path.quadTo(353.736877,186.014496, 353.736816,186.014923);
 path.quadTo(353.161499,190.31131, 353.161499,195.011719);
 </div>
 
+<div id="testQuadratic48o">
+path.moveTo(366.608826, 151.196014);
+path.quadTo(378.803101, 136.674606, 398.164948, 136.674606);
+path.lineTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.lineTo(350, 120);
+path.lineTo(366.608826, 151.196014);
+path.close();
+</div>
+
+<div id="testQuadratic48s">
+path.moveTo(369.285553, 126.984779);
+path.lineTo(393.291473,102.232819);
+path.lineTo(382.416199,131.740402);
+path.lineTo(396.039917,136.674606);
+path.quadTo(387.290802,136.674606, 380.294495,140.44487);
+path.quadTo(379.623352,140.760971, 378.965302,141.103577);
+path.lineTo(378.917297,141.233856);
+path.quadTo(378.86972,141.206131, 378.822021,141.178574);
+path.quadTo(372.011871,144.761871, 366.608826,151.196014);
+path.lineTo(350,120);
+path.lineTo(369.285553,126.984779);
+path.close();
+</div>
+
+<div id="testQuadratic49s">
+path.moveTo(366.400513, 204.162521);
+path.lineTo(411.545044, 81.6732483);
+path.lineTo(366.400513, 204.162521);
+path.close();
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188, 121.147957, 368.11853, 121.147957);
+path.quadTo(389.193115, 121.147957, 400.693176, 136.124817);
+path.lineTo(331.585693, 138.050415);
+path.close();
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
+<div id="testQuadratic50o">
+path.moveTo(366.400513, 204.162521);
+path.lineTo(411.545044, 81.6732483);
+path.lineTo(366.400513, 204.162521);
+path.close();
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188, 121.147957, 368.11853, 121.147957);
+path.quadTo(389.193115, 121.147957, 400.693176, 136.124817);
+path.lineTo(331.585693, 138.050415);
+path.close();
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
+<div id="testQuadratic50s">
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188,121.147957, 368.11853,121.147957);
+path.quadTo(378.797424,121.147957, 387.017914,124.993469);
+path.quadTo(391.577667,123.030998, 396.645874,122.098694);
+path.quadTo(401.232697,121.254936, 406.235992,121.254936);
+path.lineTo(395.061676,126.397095);
+path.lineTo(391.979187,127.81559);
+path.quadTo(393.010406,128.517273, 393.994415,129.292801);
+path.quadTo(394.053131,129.339066, 394.111664,129.385605);
+path.lineTo(393.910492,129.520508);
+path.lineTo(383.340973,136.608322);
+path.lineTo(375.350006,136.830978);
+path.quadTo(376.20224,135.708145, 377.092102,134.66626);
+path.lineTo(372.197113,136.918823);
+</div>
+
+<div id="testQuadratic51">
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
 </div>
 
 <script type="text/javascript">
 
 var testDivs = [
+    testQuadratic51,
+    testQuadratic50o,
+    testQuadratic50s,
+    testQuadratic49s,
+    testQuadratic48o,
+    testQuadratic48s,
     testQuadratic47o,
     testQuadratic47s,
     testQuadratic46o,