pathops version two

src/pathops/SkDCubicLineIntersection.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 "SkPathOpsCubic.h"
 #include "SkPathOpsLine.h"
 
@@ skipping 75 matching lines @@
         , fLine(l)
         , fIntersections(i)
         , fAllowNear(true) {
         i->setMax(3);
     }
 
     void allowNear(bool allow) {
         fAllowNear = allow;
     }
 
+    void checkCoincident() {
+        int last = fIntersections->used() - 1;
+        for (int index = 0; index < last; ) {
+            double cubicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
+            SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
+            double t = fLine.nearPoint(cubicMidPt, 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);
+        }
+    }
+
     // see parallel routine in line quadratic intersections
     int intersectRay(double roots[3]) {
         double adj = fLine[1].fX - fLine[0].fX;
         double opp = fLine[1].fY - fLine[0].fY;
         SkDCubic c;
         for (int n = 0; n < 4; ++n) {
             c[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp;
         }
         double A, B, C, D;
         SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
@@ skipping 18 matching lines @@
         addExactEndPoints();
         if (fAllowNear) {
             addNearEndPoints();
         }
         double rootVals[3];
         int roots = intersectRay(rootVals);
         for (int index = 0; index < roots; ++index) {
             double cubicT = rootVals[index];
             double lineT = findLineT(cubicT);
             SkDPoint pt;
-            if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized)) {
-    #if ONE_OFF_DEBUG
-                SkDPoint cPt = fCubic.ptAtT(cubicT);
-                SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
-                        cPt.fX, cPt.fY);
-    #endif
-                for (int inner = 0; inner < fIntersections->used(); ++inner) {
-                    if (fIntersections->pt(inner) != pt) {
-                        continue;
-                    }
-                    double existingCubicT = (*fIntersections)[0][inner];
-                    if (cubicT == existingCubicT) {
-                        goto skipInsert;
-                    }
-                    // check if midway on cubic is also same point. If so, discard this
-                    double cubicMidT = (existingCubicT + cubicT) / 2;
-                    SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
-                    if (cubicMidPt.approximatelyEqual(pt)) {
-                        goto skipInsert;
-                    }
-                }
+            if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
-        skipInsert:
-                ;
             }
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
     static int HorizontalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) {
         double A, B, C, D;
         SkDCubic::Coefficients(&c[0].fY, &A, &B, &C, &D);
         D -= axisIntercept;
         int count = SkDCubic::RootsValidT(A, B, C, D, roots);
         for (int index = 0; index < count; ++index) {
             SkDPoint calcPt = c.ptAtT(roots[index]);
             if (!approximately_equal(calcPt.fY, axisIntercept)) {
                 double extremeTs[6];
                 int extrema = SkDCubic::FindExtrema(c[0].fY, c[1].fY, c[2].fY, c[3].fY, extremeTs);
                 count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kYAxis, roots);
                 break;
             }
         }
         return count;
     }
 
     int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
         addExactHorizontalEndPoints(left, right, axisIntercept);
         if (fAllowNear) {
             addNearHorizontalEndPoints(left, right, axisIntercept);
         }
         double roots[3];
         int count = HorizontalIntersect(fCubic, axisIntercept, roots);
         for (int index = 0; index < count; ++index) {
             double cubicT = roots[index];
-            SkDPoint pt;
-            pt.fX = fCubic.ptAtT(cubicT).fX;
-            pt.fY = axisIntercept;
+            SkDPoint pt = { fCubic.ptAtT(cubicT).fX,  axisIntercept };
             double lineT = (pt.fX - left) / (right - left);
-            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
+        bool uniqueAnswer(double cubicT, const SkDPoint& pt) {
+            for (int inner = 0; inner < fIntersections->used(); ++inner) {
+                if (fIntersections->pt(inner) != pt) {
+                    continue;
+                }
+                double existingCubicT = (*fIntersections)[0][inner];
+                if (cubicT == existingCubicT) {
+                    return false;
+                }
+                // check if midway on cubic is also same point. If so, discard this
+                double cubicMidT = (existingCubicT + cubicT) / 2;
+                SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
+                if (cubicMidPt.approximatelyEqual(pt)) {
+                    return false;
+                }
+            }
+#if ONE_OFF_DEBUG
+            SkDPoint cPt = fCubic.ptAtT(cubicT);
+            SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+                    cPt.fX, cPt.fY);
+#endif
+            return true;
+        }
+
     static int VerticalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) {
         double A, B, C, D;
         SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
         D -= axisIntercept;
         int count = SkDCubic::RootsValidT(A, B, C, D, roots);
         for (int index = 0; index < count; ++index) {
             SkDPoint calcPt = c.ptAtT(roots[index]);
             if (!approximately_equal(calcPt.fX, axisIntercept)) {
                 double extremeTs[6];
                 int extrema = SkDCubic::FindExtrema(c[0].fX, c[1].fX, c[2].fX, c[3].fX, extremeTs);
                 count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kXAxis, roots);
                 break;
             }
         }
         return count;
     }
 
     int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
         addExactVerticalEndPoints(top, bottom, axisIntercept);
         if (fAllowNear) {
             addNearVerticalEndPoints(top, bottom, axisIntercept);
         }
         double roots[3];
         int count = VerticalIntersect(fCubic, axisIntercept, roots);
         for (int index = 0; index < count; ++index) {
             double cubicT = roots[index];
-            SkDPoint pt;
-            pt.fX = axisIntercept;
-            pt.fY = fCubic.ptAtT(cubicT).fY;
+            SkDPoint pt = { axisIntercept, fCubic.ptAtT(cubicT).fY };
             double lineT = (pt.fY - top) / (bottom - top);
-            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
     protected:
 
     void addExactEndPoints() {
         for (int cIndex = 0; cIndex < 4; cIndex += 3) {
             double lineT = fLine.exactPoint(fCubic[cIndex]);
             if (lineT < 0) {
                 continue;
@@ skipping 85 matching lines @@
         if (!approximately_one_or_less(*lineT)) {
             return false;
         }
         if (!approximately_zero_or_more(*lineT)) {
             return false;
         }
         double cT = *cubicT = SkPinT(*cubicT);
         double lT = *lineT = SkPinT(*lineT);
         SkDPoint lPt = fLine.ptAtT(lT);
         SkDPoint cPt = fCubic.ptAtT(cT);
-        if (!lPt.moreRoughlyEqual(cPt)) {
+        if (!lPt.roughlyEqual(cPt)) {
             return false;
         }
         // FIXME: if points are roughly equal but not approximately equal, need to do
         // a binary search like quad/quad intersection to find more precise t values
         if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT != 1)) {
             *pt = lPt;
         } else if (ptSet == kPointUninitialized) {
             *pt = cPt;
         }
         SkPoint gridPt = pt->asSkPoint();
@@ skipping 38 matching lines @@
 }
 
 int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) {
     LineCubicIntersections c(cubic, line, this);
     fUsed = c.intersectRay(fT[0]);
     for (int index = 0; index < fUsed; ++index) {
         fPt[index] = cubic.ptAtT(fT[0][index]);
     }
     return fUsed;
 }