path ops -- rewrite angle sort

src/pathops/SkDQuadIntersection.cpp

 // Another approach is to start with the implicit form of one curve and solve
 // (seek implicit coefficients in QuadraticParameter.cpp
 // by substituting in the parametric form of the other.
 // The downside of this approach is that early rejects are difficult to come by.
 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step
 
 
 #include "SkDQuadImplicit.h"
 #include "SkIntersections.h"
 #include "SkPathOpsLine.h"
 #include "SkQuarticRoot.h"
 #include "SkTDArray.h"
 #include "SkTSort.h"
 
 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F
  * and given x = at^2 + bt + c  (the parameterized form)
  *           y = dt^2 + et + f
  * then
  * 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;
     const double t3 = 2 * i.x2() *  a * b
                     +     i.xy() * (a * e +     b * d)
                     + 2 * i.y2() *  d * e;
     const double t2 =     i.x2() * (b * b + 2 * a * c)
                     +     i.xy() * (c * d +     b * e + a * f)
                     +     i.y2() * (e * e + 2 * d * f)
                     +     i.x()  *  a
                     +     i.y()  *  d;
     const double t1 = 2 * i.x2() *  b * c
                     +     i.xy() * (c * e + b * f)
                     + 2 * i.y2() *  e * f
                     +     i.x()  *  b
                     +     i.y()  *  e;
     const double t0 =     i.x2() *  c * c
                     +     i.xy() *  c * f
                     +     i.y2() *  f * f
                     +     i.x()  *  c
                     +     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]) {
     int result = 0;
     int index;
     for (index = 0; index < count; ++index) {
         if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) {
             continue;
         }
         double t = 1 - roots[index];
@@ skipping 331 matching lines @@
         if ((t = SkIntersections::Axial(q2, q1[0], useVertical)) >= 0) {
             insertCoincident(0, t, q1[0]);
         }
         if ((t = SkIntersections::Axial(q2, q1[2], useVertical)) >= 0) {
             insertCoincident(1, t, q1[2]);
         }
         SkASSERT(coincidentUsed() <= 2);
         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);
     SkDPoint pts1[4];
     for (index = 0; index < r1Count; ++index) {
         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];
     for (index = 0; index < r2Count; ++index) {
         pts2[index] = q2.xyAtT(roots2Copy[index]);
     }
     if (r1Count == r2Count && r1Count <= 1) {
         if (r1Count == 1) {
             if (pts1[0].approximatelyEqualHalf(pts2[0])) {
                 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]);
                 }
             }
         }
         return fUsed;
     }
     int closest[4];
     double dist[4];
@@ skipping 46 matching lines @@
         }
         if (lowestIndex < 0) {
             break;
         }
         insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]],
                 pts1[lowestIndex]);
         closest[lowestIndex] = -1;
     } while (++used < r1Count);
     return fUsed;
 }