path ops -- fix skp bugs

src/pathops/SkOpAngle.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkIntersections.h"
 #include "SkOpAngle.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
 
+#if DEBUG_SORT || DEBUG_SORT_SINGLE
+#include "SkOpSegment.h"
+#endif
+
 // FIXME: this is bogus for quads and cubics
 // if the quads and cubics' line from end pt to ctrl pt are coincident,
 // 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.
 
 /*(
 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
 */
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {
-    double y = dy();
-    double ry = rh.dy();
+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;
     }
-    double x = dx();
-    double rx = rh.dx();
     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();
+    double y = dy();
+    double rx = rh.dx();
+    double ry = rh.dy();
+    int simple = simple_compare(x, y, rx, ry);
+    if (simple >= 0) {
+        return simple;
+    }
     // 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;
     }
     // see if either curve can be lengthened and try the tangent compare again
@@ skipping 25 matching lines @@
     // 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
     // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
     double len = fTangent1.normalSquared();
     double rlen = rh.fTangent1.normalSquared();
     SkDLine ray;
     SkIntersections i, ri;
     int roots, rroots;
     bool flip = false;
+    bool useThis;
+    bool leftLessThanRight = fSide > 0;
     do {
-        bool useThis = (len < rlen) ^ flip;
+        useThis = (len < rlen) ^ flip;
         const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
         SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
         ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
             part[2] : part[1];
         ray[1].fX = (part[0].fX + part[partVerb].fX) / 2;
         ray[1].fY = (part[0].fY + part[partVerb].fY) / 2;
         SkASSERT(ray[0] != ray[1]);
         roots = (i.*CurveRay[fVerb])(fPts, ray);
         rroots = (ri.*CurveRay[rh.fVerb])(rh.fPts, ray);
     } 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
     }
-    SkDPoint loc;
+    SkASSERT(fSide != 0 && rh.fSide != 0);
+    SkASSERT(fSide * rh.fSide > 0); // both are the same sign
+    SkDPoint lLoc;
     double best = SK_ScalarInfinity;
-    SkDVector dxy;
-    double dist;
-    int index;
-    for (index = 0; index < roots; ++index) {
-        loc = (*CurveDPointAtT[fVerb])(fPts, i[0][index]);
-        dxy = loc - ray[0];
-        dist = dxy.lengthSquared();
+#if DEBUG_SORT
+    SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n",
+            fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY,
+            ray[1].fX, ray[1].fY, "-+"[fSide > 0]);
+#endif
+    for (int index = 0; index < roots; ++index) {
+        SkDPoint loc = i.pt(index);
+        SkDVector dxy = loc - ray[0];
+        double dist = dxy.lengthSquared();
+#if DEBUG_SORT
+        SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 
+                best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY);
+#endif
         if (best > dist) {
+            lLoc = loc;
             best = dist;
         }
     }
-    for (index = 0; index < rroots; ++index) {
-        loc = (*CurveDPointAtT[rh.fVerb])(rh.fPts, ri[0][index]);
-        dxy = loc - ray[0];
-        dist = dxy.lengthSquared();
+    flip = false;
+    SkDPoint rLoc;
+    for (int index = 0; index < rroots; ++index) {
+        rLoc = ri.pt(index);
+        SkDVector dxy = rLoc - ray[0];
+        double dist = dxy.lengthSquared();
+#if DEBUG_SORT
+        SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n", 
+                best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY);
+#endif
         if (best > dist) {
-            return fSide < 0;
+            flip = true;
+            break;
         }
     }
-    return fSide > 0;
+ #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) {
+        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;
 }
 
 bool SkOpAngle::lengthen() {
     int newEnd = fEnd;
     if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
         fEnd = newEnd;
         setSpans();
         return true;
     }
     return false;
@@ skipping 132 matching lines @@
 #if 1
 #if DEBUG_UNSORTABLE
     SkPoint iPt = (*CurvePointAtT[fVerb])(fPts, startT);
     SkPoint ePt = (*CurvePointAtT[fVerb])(fPts, endT);
     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
     fUnsortable = true;
 #endif
 }