path ops near exact

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 62 matching lines @@
      3 e t^2 - 6 f t^2 + 3 g t^2 -
        e t^3 + 3 f t^3 - 3 g t^3 + h t^3
  */
 
 class LineCubicIntersections {
 public:
 
 LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i)
     : cubic(c)
     , line(l)
-    , intersections(i) {
+    , intersections(i)
+    , fAllowNear(true) {
+}
+
+void allowNear(bool allow) {
+    fAllowNear = allow;
 }
 
 // see parallel routine in line quadratic intersections
 int intersectRay(double roots[3]) {
     double adj = line[1].fX - line[0].fX;
     double opp = line[1].fY - line[0].fY;
     SkDCubic r;
     for (int n = 0; n < 4; ++n) {
         r[n].fX = (cubic[n].fY - line[0].fY) * adj - (cubic[n].fX - line[0].fX) * opp;
     }
     double A, B, C, D;
     SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D);
     return SkDCubic::RootsValidT(A, B, C, D, roots);
 }
 
 int intersect() {
-    addEndPoints();
+    addExactEndPoints();
     double rootVals[3];
     int roots = intersectRay(rootVals);
     for (int index = 0; index < roots; ++index) {
         double cubicT = rootVals[index];
         double lineT = findLineT(cubicT);
         if (pinTs(&cubicT, &lineT)) {
             SkDPoint pt = line.xyAtT(lineT);
 #if ONE_OFF_DEBUG
             SkDPoint cPt = cubic.xyAtT(cubicT);
             SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
                     cPt.fX, cPt.fY);
 #endif
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearEndPoints();
+    }
     return intersections.used();
 }
 
 int horizontalIntersect(double axisIntercept, double roots[3]) {
     double A, B, C, D;
     SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D);
     D -= axisIntercept;
     return SkDCubic::RootsValidT(A, B, C, D, roots);
 }
 
 int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
-    addHorizontalEndPoints(left, right, axisIntercept);
+    addExactHorizontalEndPoints(left, right, axisIntercept);
     double rootVals[3];
     int roots = horizontalIntersect(axisIntercept, rootVals);
     for (int index = 0; index < roots; ++index) {
         double cubicT = rootVals[index];
         SkDPoint pt = cubic.xyAtT(cubicT);
         double lineT = (pt.fX - left) / (right - left);
         if (pinTs(&cubicT, &lineT)) {
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearHorizontalEndPoints(left, right, axisIntercept);
+    }
     if (flipped) {
         intersections.flip();
     }
     return intersections.used();
 }
 
 int verticalIntersect(double axisIntercept, double roots[3]) {
     double A, B, C, D;
     SkDCubic::Coefficients(&cubic[0].fX, &A, &B, &C, &D);
     D -= axisIntercept;
     return SkDCubic::RootsValidT(A, B, C, D, roots);
 }
 
 int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
-    addVerticalEndPoints(top, bottom, axisIntercept);
+    addExactVerticalEndPoints(top, bottom, axisIntercept);
     double rootVals[3];
     int roots = verticalIntersect(axisIntercept, rootVals);
     for (int index = 0; index < roots; ++index) {
         double cubicT = rootVals[index];
         SkDPoint pt = cubic.xyAtT(cubicT);
         double lineT = (pt.fY - top) / (bottom - top);
         if (pinTs(&cubicT, &lineT)) {
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearVerticalEndPoints(top, bottom, axisIntercept);
+    }
     if (flipped) {
         intersections.flip();
     }
     return intersections.used();
 }
 
 protected:
 
-void addEndPoints() {
+void addExactEndPoints() {
     for (int cIndex = 0; cIndex < 4; cIndex += 3) {
-        bool foundEnd = false;
-        for (int lIndex = 0; lIndex < 2; lIndex++) {
-            if (cubic[cIndex] == line[lIndex]) {
-                intersections.insert(cIndex >> 1, lIndex, line[lIndex]);
-                foundEnd = true;
-            }
-        }
-        // for the test case this was written for, the dist / error ratio was 170.6667
-        // it looks like the cubic stops short of touching the line, but this fixed it.
-        if (foundEnd) {
+        double lineT = line.exactPoint(cubic[cIndex]);
+        if (lineT < 0) {
             continue;
         }
-        // See if the cubic end touches the line.
-        double dist = line.isLeft(cubic[cIndex]); // this distance isn't cartesian
-        SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line
-        // compute the ULPS of the larger of the x/y deltas
-        double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY));
-        if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance?
-            continue;
-        }
-        double lineT = findLineT(cIndex >> 1);
-        if (!between(0, lineT, 1)) {
-            continue;
-        }
-        SkDPoint linePt = line.xyAtT(lineT);
-        if (linePt.approximatelyEqual(cubic[cIndex])) {
-            intersections.insert(cIndex >> 1, lineT, cubic[cIndex]);
-        }
+        double cubicT = (double) (cIndex >> 1);
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
     }
 }
 
-void addHorizontalEndPoints(double left, double right, double y) {
+void addNearEndPoints() {
     for (int cIndex = 0; cIndex < 4; cIndex += 3) {
-        if (cubic[cIndex].fY != y) {
+        double cubicT = (double) (cIndex >> 1);
+        if (intersections.hasT(cubicT)) {
             continue;
         }
-        if (cubic[cIndex].fX == left) {
-            intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
+        double lineT = line.nearPoint(cubic[cIndex]);
+        if (lineT < 0) {
+            continue;
         }
-        if (cubic[cIndex].fX == right) {
-            intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
-        }
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
     }
 }
 
-void addVerticalEndPoints(double top, double bottom, double x) {
+void addExactHorizontalEndPoints(double left, double right, double y) {
     for (int cIndex = 0; cIndex < 4; cIndex += 3) {
-        if (cubic[cIndex].fX != x) {
+        double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y);
+        if (lineT < 0) {
             continue;
         }
-        if (cubic[cIndex].fY == top) {
-            intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
-        }
-        if (cubic[cIndex].fY == bottom) {
-            intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
-        }
+        double cubicT = (double) (cIndex >> 1);
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
     }
 }
 
+void addNearHorizontalEndPoints(double left, double right, double y) {
+    for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+        double cubicT = (double) (cIndex >> 1);
+        if (intersections.hasT(cubicT)) {
+            continue;
+        }
+        double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y);
+        if (lineT < 0) {
+            continue;
+        }
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
+    }
+    // FIXME: see if line end is nearly on cubic
+}
+
+void addExactVerticalEndPoints(double top, double bottom, double x) {
+    for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+        double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x);
+        if (lineT < 0) {
+            continue;
+        }
+        double cubicT = (double) (cIndex >> 1);
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
+    }
+}
+
+void addNearVerticalEndPoints(double top, double bottom, double x) {
+    for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+        double cubicT = (double) (cIndex >> 1);
+        if (intersections.hasT(cubicT)) {
+            continue;
+        }
+        double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x);
+        if (lineT < 0) {
+            continue;
+        }
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
+    }
+    // FIXME: see if line end is nearly on cubic
+}
+
 double findLineT(double t) {
     SkDPoint xy = cubic.xyAtT(t);
     double dx = line[1].fX - line[0].fX;
     double dy = line[1].fY - line[0].fY;
     if (fabs(dx) > fabs(dy)) {
         return (xy.fX - line[0].fX) / dx;
     }
     return (xy.fY - line[0].fY) / dy;
 }
 
@@ skipping 15 matching lines @@
         *lineT = 1;
     }
     return true;
 }
 
 private:
 
 const SkDCubic& cubic;
 const SkDLine& line;
 SkIntersections& intersections;
+bool fAllowNear;
 };
 
 int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y,
         bool flipped) {
     LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this);
     return c.horizontalIntersect(y, left, right, flipped);
 }
 
 int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom, double x,
         bool flipped) {
     LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this);
     return c.verticalIntersect(x, top, bottom, flipped);
 }
 
 int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) {
     LineCubicIntersections c(cubic, line, *this);
+    c.allowNear(fAllowNear);
     return c.intersect();
 }
 
 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.xyAtT(fT[0][index]);
     }
     return fUsed;
 }