pathops version two

src/pathops/SkDQuadLineIntersection.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 "SkPathOpsLine.h"
 #include "SkPathOpsQuad.h"
 
@@ skipping 87 matching lines @@
         , fLine(l)
         , fIntersections(i)
         , fAllowNear(true) {
         i->setMax(3);  // allow short partial coincidence plus discrete intersection
     }
 
     void allowNear(bool allow) {
         fAllowNear = allow;
     }
 
+    void checkCoincident() {
+        int last = fIntersections->used() - 1;
+        for (int index = 0; index < last; ) {
+            double quadMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
+            SkDPoint quadMidPt = fQuad.ptAtT(quadMidT);
+            double t = fLine.nearPoint(quadMidPt, NULL);
+            if (t < 0) {
+                ++index;
+                continue;
+            }
+            if (fIntersections->isCoincident(index)) {
+                fIntersections->removeOne(index);
+                --last;
+            } else if (fIntersections->isCoincident(index + 1)) {
+                fIntersections->removeOne(index + 1);
+                --last;
+            } else {
+                fIntersections->setCoincident(index++);
+            }
+            fIntersections->setCoincident(index);
+        }
+    }
+
     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
         |cos(a) -sin(a)|
         |sin(a)  cos(a)|
         note that cos(a) = A(djacent) / Hypoteneuse
                   sin(a) = O(pposite) / Hypoteneuse
         since we are computing Ts, we can ignore hypoteneuse, the scale factor:
         |  A     -O    |
@@ skipping 15 matching lines @@
         A += C - 2 * B;  // A = a - 2*b + c
         B -= C;  // B = -(b - c)
         return SkDQuad::RootsValidT(A, 2 * B, C, roots);
     }
 
     int intersect() {
         addExactEndPoints();
         if (fAllowNear) {
             addNearEndPoints();
         }
-        if (fIntersections->used() == 2) {
-            // FIXME : need sharable code that turns spans into coincident if middle point is on
-        } else {
-            double rootVals[2];
-            int roots = intersectRay(rootVals);
-            for (int index = 0; index < roots; ++index) {
-                double quadT = rootVals[index];
-                double lineT = findLineT(quadT);
-                SkDPoint pt;
-                if (pinTs(&quadT, &lineT, &pt, kPointUninitialized)) {
-                    fIntersections->insert(quadT, lineT, pt);
-                }
+        double rootVals[2];
+        int roots = intersectRay(rootVals);
+        for (int index = 0; index < roots; ++index) {
+            double quadT = rootVals[index];
+            double lineT = findLineT(quadT);
+            SkDPoint pt;
+            if (pinTs(&quadT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(quadT, pt)) {
+                fIntersections->insert(quadT, lineT, pt);
             }
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
     int horizontalIntersect(double axisIntercept, double roots[2]) {
         double D = fQuad[2].fY;  // f
         double E = fQuad[1].fY;  // e
         double F = fQuad[0].fY;  // d
         D += F - 2 * E;         // D = d - 2*e + f
         E -= F;                 // E = -(d - e)
         F -= axisIntercept;
         return SkDQuad::RootsValidT(D, 2 * E, F, roots);
     }
 
     int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
         addExactHorizontalEndPoints(left, right, axisIntercept);
         if (fAllowNear) {
             addNearHorizontalEndPoints(left, right, axisIntercept);
         }
         double rootVals[2];
         int roots = horizontalIntersect(axisIntercept, rootVals);
         for (int index = 0; index < roots; ++index) {
             double quadT = rootVals[index];
             SkDPoint pt = fQuad.ptAtT(quadT);
             double lineT = (pt.fX - left) / (right - left);
-            if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) {
                 fIntersections->insert(quadT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
+    bool uniqueAnswer(double quadT, const SkDPoint& pt) {
+        for (int inner = 0; inner < fIntersections->used(); ++inner) {
+            if (fIntersections->pt(inner) != pt) {
+                continue;
+            }
+            double existingQuadT = (*fIntersections)[0][inner];
+            if (quadT == existingQuadT) {
+                return false;
+            }
+            // check if midway on quad is also same point. If so, discard this
+            double quadMidT = (existingQuadT + quadT) / 2;
+            SkDPoint quadMidPt = fQuad.ptAtT(quadMidT);
+            if (quadMidPt.approximatelyEqual(pt)) {
+                return false;
+            }
+        }
+#if ONE_OFF_DEBUG
+        SkDPoint qPt = fQuad.ptAtT(quadT);
+        SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+                qPt.fX, qPt.fY);
+#endif
+        return true;
+    }
+
     int verticalIntersect(double axisIntercept, double roots[2]) {
         double D = fQuad[2].fX;  // f
         double E = fQuad[1].fX;  // e
         double F = fQuad[0].fX;  // d
         D += F - 2 * E;         // D = d - 2*e + f
         E -= F;                 // E = -(d - e)
         F -= axisIntercept;
         return SkDQuad::RootsValidT(D, 2 * E, F, roots);
     }
 
     int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
         addExactVerticalEndPoints(top, bottom, axisIntercept);
         if (fAllowNear) {
             addNearVerticalEndPoints(top, bottom, axisIntercept);
         }
         double rootVals[2];
         int roots = verticalIntersect(axisIntercept, rootVals);
         for (int index = 0; index < roots; ++index) {
             double quadT = rootVals[index];
             SkDPoint pt = fQuad.ptAtT(quadT);
             double lineT = (pt.fY - top) / (bottom - top);
-            if (pinTs(&quadT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) {
                 fIntersections->insert(quadT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
 protected:
     // add endpoints first to get zero and one t values exactly
     void addExactEndPoints() {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
             double lineT = fLine.exactPoint(fQuad[qIndex]);
             if (lineT < 0) {
                 continue;
@@ skipping 143 matching lines @@
 }
 
 int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) {
     LineQuadraticIntersections q(quad, line, this);
     fUsed = q.intersectRay(fT[0]);
     for (int index = 0; index < fUsed; ++index) {
         fPt[index] = quad.ptAtT(fT[0][index]);
     }
     return fUsed;
 }