pathops version two

src/pathops/SkPathOpsQuad.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 "SkLineParameters.h"
 #include "SkPathOpsCubic.h"
 #include "SkPathOpsQuad.h"
-#include "SkPathOpsTriangle.h"
+
+/* started with at_most_end_pts_in_common from SkDQuadIntersection.cpp */
+// Do a quick reject by rotating all points relative to a line formed by
+// a pair of one quad's points. If the 2nd quad's points
+// are on the line or on the opposite side from the 1st quad's 'odd man', the
+// curves at most intersect at the endpoints.
+/* if returning true, check contains true if quad's hull collapsed, making the cubic linear
+   if returning false, check contains true if the the quad pair have only the end point in common
+*/
+bool SkDQuad::hullIntersects(const SkDQuad& q2, bool* isLinear) const {
+    bool linear = true;
+    for (int oddMan = 0; oddMan < kPointCount; ++oddMan) {
+        const SkDPoint* endPt[2];
+        this->otherPts(oddMan, endPt);
+        double origX = endPt[0]->fX;
+        double origY = endPt[0]->fY;
+        double adj = endPt[1]->fX - origX;
+        double opp = endPt[1]->fY - origY;
+        double sign = (fPts[oddMan].fY - origY) * adj - (fPts[oddMan].fX - origX) * opp;
+        if (approximately_zero(sign)) {
+            continue;
+        }
+        linear = false;
+        bool foundOutlier = false;
+        for (int n = 0; n < kPointCount; ++n) {
+            double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
+            if (test * sign > 0 && !precisely_zero(test)) {
+                foundOutlier = true;
+                break;
+            }
+        }
+        if (!foundOutlier) {
+            return false;
+        }
+    }
+    *isLinear = linear;
+    return true;
+}
+
+/* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan)
+oddMan    opp   x=oddMan^opp  x=x-oddMan  m=x>>2   x&~m
+    0       1         1            1         0       1
+            2         2            2         0       2
+    1       1         0           -1        -1       0
+            2         3            2         0       2
+    2       1         3            1         0       1
+            2         0           -2        -1       0
+*/
+void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const {
+    for (int opp = 1; opp < kPointCount; ++opp) {
+        int end = (oddMan ^ opp) - oddMan;  // choose a value not equal to oddMan
+        end &= ~(end >> 2);  // if the value went negative, set it to zero
+        endPt[opp - 1] = &fPts[end];
+    }
+}
 
 // from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html
 // (currently only used by testing)
 double SkDQuad::nearestT(const SkDPoint& pt) const {
     SkDVector pos = fPts[0] - pt;
     // search points P of bezier curve with PM.(dP / dt) = 0
     // a calculus leads to a 3d degree equation :
     SkDVector A = fPts[1] - fPts[0];
     SkDVector B = fPts[2] - fPts[1];
     B -= A;
@@ skipping 14 matching lines @@
             distMin = dist;
             bestIndex = index;
         }
     }
     if (bestIndex >= 0) {
         return ts[bestIndex];
     }
     return d0 < d2 ? 0 : 1;
 }
 
-bool SkDQuad::pointInHull(const SkDPoint& pt) const {
-    return ((const SkDTriangle&) fPts).contains(pt);
-}
-
 SkDPoint SkDQuad::top(double startT, double endT) const {
     SkDQuad sub = subDivide(startT, endT);
     SkDPoint topPt = sub[0];
     if (topPt.fY > sub[2].fY || (topPt.fY == sub[2].fY && topPt.fX > sub[2].fX)) {
         topPt = sub[2];
     }
     if (!between(sub[0].fY, sub[1].fY, sub[2].fY)) {
         double extremeT;
         if (FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, &extremeT)) {
             extremeT = startT + (endT - startT) * extremeT;
@@ skipping 73 matching lines @@
     s[1] = -sqrt_D - p;
     return 1 + !AlmostDequalUlps(s[0], s[1]);
 }
 
 bool SkDQuad::isLinear(int startIndex, int endIndex) const {
     SkLineParameters lineParameters;
     lineParameters.quadEndPoints(*this, startIndex, endIndex);
     // FIXME: maybe it's possible to avoid this and compare non-normalized
     lineParameters.normalize();
     double distance = lineParameters.controlPtDistance(*this);
-    return approximately_zero(distance);
+    double tiniest = SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY),
+            fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
+    double largest = SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY),
+            fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
+    largest = SkTMax(largest, -tiniest);
+    return approximately_zero_when_compared_to(distance, largest);
 }
 
 SkDCubic SkDQuad::toCubic() const {
     SkDCubic cubic;
     cubic[0] = fPts[0];
     cubic[2] = fPts[1];
     cubic[3] = fPts[2];
     cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
     cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
     cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
@@ skipping 79 matching lines @@
         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 && i[0][0] >= 0 && i[1][0] >= 0) {
         b = i.pt(0);
     } else {
         SkASSERT(i.used() <= 2);
         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 (AlmostBequalUlps(b.fX, a.fX)) {
         b.fX = a.fX;
     } else if (AlmostBequalUlps(b.fX, c.fX)) {
         b.fX = c.fX;
@@ skipping 61 matching lines @@
  * c =             C
  */
 void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) {
     *a = quad[0];      // a = A
     *b = 2 * quad[2];  // b =     2*B
     *c = quad[4];      // c =             C
     *b -= *c;          // b =     2*B -   C
     *a -= *b;          // a = A - 2*B +   C
     *b -= *c;          // b =     2*B - 2*C
 }