path ops near exact

Modify line intersections to first
- match exact ends
- compute intersections
- match near ends
where the exact ends are preferred, then near matches, then
computed matches. This pulls matches towards existing end points
when possible, and keeps intersection distances consistent with
different line/line line/quad and line/cubic computations.

BUG=

Review URL: https://codereview.chromium.org/19183003

git-svn-id: http://skia.googlecode.com/svn/trunk@10073 2bbb7eff-a529-9590-31e7-b0007b416f81

20 files changed, 555 insertions, 260 deletions

diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 511879cd70..6e049708ac 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -15,11 +15,12 @@
 #include "SkTSort.h"
 
 #if ONE_OFF_DEBUG
-static const double tLimits1[2][2] = {{0.36, 0.37}, {0.63, 0.64}};
+static const double tLimits1[2][2] = {{0.388600450, 0.388600452}, {0.245852802, 0.245852804}};
 static const double tLimits2[2][2] = {{-0.865211397, -0.865215212}, {-0.865207696, -0.865208078}};
 #endif
 
-#define DEBUG_QUAD_PART 0
+#define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1
+#define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0
 #define SWAP_TOP_DEBUG 0
 
 static const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision
@@ -31,25 +32,27 @@ static int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceO
     // extremely shallow quadratic?
     int order = reducer->reduce(quad, SkReduceOrder::kFill_Style);
 #if DEBUG_QUAD_PART
-    SkDebugf("%s cubic=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)"
-            " t=(%1.17g,%1.17g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
+    SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
+            " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
             cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY,
             cubic[3].fX, cubic[3].fY, tStart, tEnd);
-    SkDebugf("%s part=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)"
-            " quad=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)\n", __FUNCTION__,
+    SkDebugf("  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
+             "  {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
             part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY,
             part[3].fX, part[3].fY, quad[0].fX, quad[0].fY,
             quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
-    SkDebugf("%s simple=(%1.17g,%1.17g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
+#if DEBUG_QUAD_PART_SHOW_SIMPLE
+    SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
     if (order > 1) {
-        SkDebugf(" %1.17g,%1.17g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
+        SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
     }
     if (order > 2) {
-        SkDebugf(" %1.17g,%1.17g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
+        SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
     }
     SkDebugf(")\n");
     SkASSERT(order < 4 && order > 0);
 #endif
+#endif
     return order;
 }
 
@@ -240,7 +243,7 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC
                             i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
                 #endif
                     }
-                    intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
+          //          intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
                     // FIXME: if no intersection is found, either quadratics intersected where
                     // cubics did not, or the intersection was missed. In the former case, expect
                     // the quadratics to be nearly parallel at the point of intersection, and check
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index f86a21ccc1..dc80479f60 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -80,7 +80,12 @@ 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
@@ -97,7 +102,7 @@ int intersectRay(double roots[3]) {
 }
 
 int intersect() {
-    addEndPoints();
+    addExactEndPoints();
     double rootVals[3];
     int roots = intersectRay(rootVals);
     for (int index = 0; index < roots; ++index) {
@@ -113,6 +118,9 @@ int intersect() {
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearEndPoints();
+    }
     return intersections.used();
 }
 
@@ -124,7 +132,7 @@ int horizontalIntersect(double axisIntercept, double roots[3]) {
 }
 
 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) {
@@ -135,6 +143,9 @@ int horizontalIntersect(double axisIntercept, double left, double right, bool fl
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearHorizontalEndPoints(left, right, axisIntercept);
+    }
     if (flipped) {
         intersections.flip();
     }
@@ -149,7 +160,7 @@ int verticalIntersect(double axisIntercept, double roots[3]) {
 }
 
 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) {
@@ -160,6 +171,9 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip
             intersections.insert(cubicT, lineT, pt);
         }
     }
+    if (fAllowNear) {
+        addNearVerticalEndPoints(top, bottom, axisIntercept);
+    }
     if (flipped) {
         intersections.flip();
     }
@@ -168,65 +182,81 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip
 
 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?
+        double cubicT = (double) (cIndex >> 1);
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
+    }
+}
+
+void addNearEndPoints() {
+    for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+        double cubicT = (double) (cIndex >> 1);
+        if (intersections.hasT(cubicT)) {
             continue;
         }
-        double lineT = findLineT(cIndex >> 1);
-        if (!between(0, lineT, 1)) {
+        double lineT = line.nearPoint(cubic[cIndex]);
+        if (lineT < 0) {
             continue;
         }
-        SkDPoint linePt = line.xyAtT(lineT);
-        if (linePt.approximatelyEqual(cubic[cIndex])) {
-            intersections.insert(cIndex >> 1, lineT, cubic[cIndex]);
-        }
+        intersections.insert(cubicT, lineT, cubic[cIndex]);
     }
 }
 
-void addHorizontalEndPoints(double left, double right, double y) {
+void addExactHorizontalEndPoints(double left, double right, double y) {
     for (int cIndex = 0; cIndex < 4; cIndex += 3) {
-        if (cubic[cIndex].fY != y) {
+        double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y);
+        if (lineT < 0) {
             continue;
         }
-        if (cubic[cIndex].fX == left) {
-            intersections.insert(cIndex >> 1, 0, 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;
         }
-        if (cubic[cIndex].fX == right) {
-            intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
+        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 addVerticalEndPoints(double top, double bottom, double x) {
+void addExactVerticalEndPoints(double top, double bottom, double x) {
     for (int cIndex = 0; cIndex < 4; cIndex += 3) {
-        if (cubic[cIndex].fX != x) {
+        double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x);
+        if (lineT < 0) {
             continue;
         }
-        if (cubic[cIndex].fY == top) {
-            intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
+        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;
         }
-        if (cubic[cIndex].fY == bottom) {
-            intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
+        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) {
@@ -264,6 +294,7 @@ private:
 const SkDCubic& cubic;
 const SkDLine& line;
 SkIntersections& intersections;
+bool fAllowNear;
 };
 
 int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y,
@@ -280,6 +311,7 @@ int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom,
 
 int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) {
     LineCubicIntersections c(cubic, line, *this);
+    c.allowNear(fAllowNear);
     return c.intersect();
 }
 
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 3b88b88702..faa7c1d392 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -75,47 +75,19 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
     return computePoints(a, used);
 }
 
-static bool checkEndPoint(double x, double y, const SkDLine& l, double* tPtr, int useX) {
-    if (!between(l[0].fX, x, l[1].fX) || !between(l[0].fY, y, l[1].fY)) {
-        return false;
-    }
-    double xLen = l[1].fX - l[0].fX;
-    double yLen = l[1].fY - l[0].fY;
-    if (useX < 0) {
-        useX = SkTAbs(xLen) > SkTAbs(yLen);
-    }
-    // OPTIMIZATION: do between test before divide
-    double t = useX ? (x - l[0].fX) / xLen : (y - l[0].fY) / yLen;
-    if (!between(0, t, 1)) {
-        return false;
-    }
-    double opp = useX ? (1 - t) * l[0].fY + t * l[1].fY : (1 - t) * l[0].fX + t * l[1].fX;
-    if (!AlmostEqualUlps(opp, useX ? y : x)) {
-        return false;
-    }
-    *tPtr = t;
-    return true;
-}
-
 // note that this only works if both lines are neither horizontal nor vertical
 int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
     // see if end points intersect the opposite line
     double t;
     for (int iA = 0; iA < 2; ++iA) {
-        if (!checkEndPoint(a[iA].fX, a[iA].fY, b, &t, -1)) {
-            continue;
+        if ((t = b.exactPoint(a[iA])) >= 0) {
+            insert(iA, t, a[iA]);
         }
-        insert(iA, t, a[iA]);
     }
     for (int iB = 0; iB < 2; ++iB) {
-        if (!checkEndPoint(b[iB].fX, b[iB].fY, a, &t, -1)) {
-            continue;
+        if ((t = a.exactPoint(b[iB])) >= 0) {
+            insert(t, iB, b[iB]);
         }
-        insert(t, iB, b[iB]);
-    }
-    if (used() > 0) {
-        SkASSERT(fUsed <= 2);
-        return used(); // coincident lines are returned here
     }
     /* Determine the intersection point of two line segments
        Return FALSE if the lines don't intersect
@@ -131,166 +103,198 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
              byLen  * axLen         -   ayLen          * bxLen == 0 ( == denom )
      */
     double denom = byLen * axLen - ayLen * bxLen;
-    double ab0y = a[0].fY - b[0].fY;
-    double ab0x = a[0].fX - b[0].fX;
-    double numerA = ab0y * bxLen - byLen * ab0x;
-    double numerB = ab0y * axLen - ayLen * ab0x;
-    bool mayNotOverlap = (numerA < 0 && denom > numerA) || (numerA > 0 && denom < numerA)
-            || (numerB < 0 && denom > numerB) || (numerB > 0 && denom < numerB);
-    numerA /= denom;
-    numerB /= denom;
-    if ((!approximately_zero(denom) || (!approximately_zero_inverse(numerA)
-            && !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA)
-            && !sk_double_isnan(numerB)) {
-        if (mayNotOverlap) {
-            return 0;
+    if (0 != denom) {
+        double ab0y = a[0].fY - b[0].fY;
+        double ab0x = a[0].fX - b[0].fX;
+        double numerA = ab0y * bxLen - byLen * ab0x;
+        double numerB = ab0y * axLen - ayLen * ab0x;
+        if (between(0, numerA, denom) && between(0, numerB, denom)) {
+            fT[0][0] = numerA / denom;
+            fT[1][0] = numerB / denom;
+            return computePoints(a, 1);
         }
-        fT[0][0] = numerA;
-        fT[1][0] = numerB;
-        fPt[0] = a.xyAtT(numerA);
-        return computePoints(a, 1);
     }
-    return 0;
+    if (fAllowNear || 0 == denom) {
+        for (int iA = 0; iA < 2; ++iA) {
+            if ((t = b.nearPoint(a[iA])) >= 0) {
+                insert(iA, t, a[iA]);
+            }
+        }
+        for (int iB = 0; iB < 2; ++iB) {
+            if ((t = a.nearPoint(b[iB])) >= 0) {
+                insert(t, iB, b[iB]);
+            }
+        }
+    }
+    return fUsed;
 }
 
-int SkIntersections::horizontal(const SkDLine& line, double y) {
+static int horizontal_coincident(const SkDLine& line, double y) {
     double min = line[0].fY;
     double max = line[1].fY;
     if (min > max) {
         SkTSwap(min, max);
     }
     if (min > y || max < y) {
-        return fUsed = 0;
+        return 0;
     }
     if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
-        fT[0][0] = 0;
-        fT[0][1] = 1;
-        return fUsed = 2;
+        return 2;
     }
-    fT[0][0] = (y - line[0].fY) / (line[1].fY - line[0].fY);
-    return fUsed = 1;
+    return 1;
 }
 
-static bool checkEndPointH(const SkDPoint& end, double left, double right,
-                           double y, bool flipped, double* tPtr) {
-    if (!between(left, end.fX, right) || !AlmostEqualUlps(y, end.fY)) {
-        return false;
+static double horizontal_intercept(const SkDLine& line, double y) {
+     return (y - line[0].fY) / (line[1].fY - line[0].fY);
+}
+
+int SkIntersections::horizontal(const SkDLine& line, double y) {
+    int horizontalType = horizontal_coincident(line, y);
+    if (horizontalType == 1) {
+        fT[0][0] = horizontal_intercept(line, y);
+    } else if (horizontalType == 2) {
+        fT[0][0] = 0;
+        fT[0][1] = 1;
     }
-    double t = (end.fX - left) / (right - left);
-    SkASSERT(between(0, t, 1));
-    *tPtr = flipped ? 1 - t : t;
-    return true;
+    return fUsed = horizontalType;
 }
 
 int SkIntersections::horizontal(const SkDLine& line, double left, double right,
                                 double y, bool flipped) {
     // see if end points intersect the opposite line
     double t;
-    if (checkEndPoint(left, y, line, &t, true)) {
-        insert(t, flipped, left, y);
+    const SkDPoint leftPt = { left, y };
+    if ((t = line.exactPoint(leftPt)) >= 0) {
+        insert(t, (double) flipped, leftPt);
     }
     if (left != right) {
-        if (checkEndPoint(right, y, line, &t, true)) {
-            insert(t, !flipped, right, y);
+        const SkDPoint rightPt = { right, y };
+        if ((t = line.exactPoint(rightPt)) >= 0) {
+            insert(t, (double) !flipped, rightPt);
         }
         for (int index = 0; index < 2; ++index) {
-            if (!checkEndPointH(line[index], left, right, y, flipped, &t)) {
-                continue;
+            if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
+                insert((double) index, flipped ? 1 - t : t, line[index]);
             }
-            insert(index, t, line[index]);
         }
     }
-    if (used() > 0) {
-        SkASSERT(fUsed <= 2);
-        return used(); // coincident lines are returned here
+    int result = horizontal_coincident(line, y);
+    if (result == 1 && fUsed == 0) {
+        fT[0][0] = horizontal_intercept(line, y);
+        double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
+        if (between(left, xIntercept, right)) {
+            fT[1][0] = (xIntercept - left) / (right - left);
+            if (flipped) {
+                // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
+                for (int index = 0; index < result; ++index) {
+                    fT[1][index] = 1 - fT[1][index];
+                }
+            }
+            return computePoints(line, result);
+        }
     }
-    int result = horizontal(line, y);
-    if (!result) {
-        return 0;
+    if (!fAllowNear && result != 2) {
+        return fUsed;
     }
-    SkASSERT(result == 1);
-    double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
-    if (!precisely_between(left, xIntercept, right)) {
-        return fUsed = 0;
+    if ((t = line.nearPoint(leftPt)) >= 0) {
+        insert(t, (double) flipped, leftPt);
     }
-    fT[1][0] = (xIntercept - left) / (right - left);
-    if (flipped) {
-        // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
-        for (int index = 0; index < result; ++index) {
-            fT[1][index] = 1 - fT[1][index];
+    if (left != right) {
+        const SkDPoint rightPt = { right, y };
+        if ((t = line.nearPoint(rightPt)) >= 0) {
+            insert(t, (double) !flipped, rightPt);
+        }
+        for (int index = 0; index < 2; ++index) {
+            if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
+                insert((double) index, flipped ? 1 - t : t, line[index]);
+            }
         }
     }
-    return computePoints(line, result);
+    return fUsed;
 }
 
-int SkIntersections::vertical(const SkDLine& line, double x) {
+static int vertical_coincident(const SkDLine& line, double x) {
     double min = line[0].fX;
     double max = line[1].fX;
     if (min > max) {
         SkTSwap(min, max);
     }
     if (!precisely_between(min, x, max)) {
-        return fUsed = 0;
+        return 0;
     }
     if (AlmostEqualUlps(min, max)) {
-        fT[0][0] = 0;
-        fT[0][1] = 1;
-        return fUsed = 2;
+        return 2;
     }
-    fT[0][0] = (x - line[0].fX) / (line[1].fX - line[0].fX);
-    return fUsed = 1;
+    return 1;
 }
 
-static bool checkEndPointV(const SkDPoint& end, double top, double bottom,
-                           double x, bool flipped, double* tPtr) {
-    if (!between(top, end.fY, bottom) || !AlmostEqualUlps(x, end.fX)) {
-        return false;
+static double vertical_intercept(const SkDLine& line, double x) {
+    return (x - line[0].fX) / (line[1].fX - line[0].fX);
+}
+
+int SkIntersections::vertical(const SkDLine& line, double x) {
+    int verticalType = vertical_coincident(line, x);
+    if (verticalType == 1) {
+        fT[0][0] = vertical_intercept(line, x);
+    } else if (verticalType == 2) {
+        fT[0][0] = 0;
+        fT[0][1] = 1;
     }
-    double t = (end.fY - top) / (bottom - top);
-    SkASSERT(between(0, t, 1));
-    *tPtr = flipped ? 1 - t : t;
-    return true;
+    return fUsed = verticalType;
 }
 
 int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
-                                double x, bool flipped) {
+                              double x, bool flipped) {
     // see if end points intersect the opposite line
     double t;
-    if (checkEndPoint(x, top, line, &t, false)) {
-        insert(t, flipped, x, top);
+    SkDPoint topPt = { x, top };
+    if ((t = line.exactPoint(topPt)) >= 0) {
+        insert(t, (double) flipped, topPt);
     }
     if (top != bottom) {
-        if (checkEndPoint(x, bottom,line, &t, false)) {
-            insert(t, !flipped, x, bottom);
+        SkDPoint bottomPt = { x, bottom };
+        if ((t = line.exactPoint(bottomPt)) >= 0) {
+            insert(t, (double) !flipped, bottomPt);
         }
         for (int index = 0; index < 2; ++index) {
-            if (!checkEndPointV(line[index], top, bottom, x, flipped, &t)) {
-                continue;
+            if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
+                insert((double) index, flipped ? 1 - t : t, line[index]);
             }
-            insert( index, t, line[index]);
         }
     }
-    if (used() > 0) {
-        SkASSERT(fUsed <= 2);
-        return used(); // coincident lines are returned here
+    int result = vertical_coincident(line, x);
+    if (result == 1 && fUsed == 0) {
+        fT[0][0] = vertical_intercept(line, x);
+        double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
+        if (between(top, yIntercept, bottom)) {
+            fT[1][0] = (yIntercept - top) / (bottom - top);
+            if (flipped) {
+                // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
+                for (int index = 0; index < result; ++index) {
+                    fT[1][index] = 1 - fT[1][index];
+                }
+            }
+            return computePoints(line, result);
+        }
     }
-    int result = vertical(line, x);
-    if (!result) {
-        return 0;
+    if (!fAllowNear && result != 2) {
+        return fUsed;
     }
-    SkASSERT(result == 1);
-    double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
-    if (!precisely_between(top, yIntercept, bottom)) {
-        return fUsed = 0;
+    if ((t = line.nearPoint(topPt)) >= 0) {
+        insert(t, (double) flipped, topPt);
     }
-    fT[1][0] = (yIntercept - top) / (bottom - top);
-    if (flipped) {
-        // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
-        for (int index = 0; index < result; ++index) {
-            fT[1][index] = 1 - fT[1][index];
+    if (top != bottom) {
+        SkDPoint bottomPt = { x, bottom };
+        if ((t = line.nearPoint(bottomPt)) >= 0) {
+            insert(t, (double) !flipped, bottomPt);
+        }
+        for (int index = 0; index < 2; ++index) {
+            if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
+                insert((double) index, flipped ? 1 - t : t, line[index]);
+            }
         }
     }
-    return computePoints(line, result);
+    return fUsed;
 }
 
 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 54c8b4979b..124c7dab06 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -127,6 +127,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou
     line[0] -= dxdy;
     line[1] += dxdy;
     SkIntersections rootTs;
+    rootTs.allowNear(false);
     int roots = rootTs.intersect(q1, line);
     if (roots == 0) {
         if (subDivide) {
@@ -154,6 +155,7 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
     SkSTArray<kTestCount * 2, double, true> tsFound;
     for (size_t index = 0; index < kTestCount; ++index) {
         SkIntersections rootTs;
+        rootTs.allowNear(false);
         int roots = rootTs.intersect(q2, *testLines[index]);
         for (int idx2 = 0; idx2 < roots; ++idx2) {
             double t = rootTs[0][idx2];
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 98e38621e0..9df2dc248a 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -92,7 +92,12 @@ public:
     LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i)
         : quad(q)
         , line(l)
-        , intersections(i) {
+        , intersections(i)
+        , fAllowNear(true) {
+    }
+
+    void allowNear(bool allow) {
+        fAllowNear = allow;
     }
 
     int intersectRay(double roots[2]) {
@@ -126,7 +131,7 @@ public:
     }
 
     int intersect() {
-        addEndPoints();
+        addExactEndPoints();
         double rootVals[2];
         int roots = intersectRay(rootVals);
         for (int index = 0; index < roots; ++index) {
@@ -137,6 +142,9 @@ public:
                 intersections->insert(quadT, lineT, pt);
             }
         }
+        if (fAllowNear) {
+            addNearEndPoints();
+        }
         return intersections->used();
     }
 
@@ -151,7 +159,7 @@ public:
     }
 
     int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
-        addHorizontalEndPoints(left, right, axisIntercept);
+        addExactHorizontalEndPoints(left, right, axisIntercept);
         double rootVals[2];
         int roots = horizontalIntersect(axisIntercept, rootVals);
         for (int index = 0; index < roots; ++index) {
@@ -162,6 +170,9 @@ public:
                 intersections->insert(quadT, lineT, pt);
             }
         }
+        if (fAllowNear) {
+            addNearHorizontalEndPoints(left, right, axisIntercept);
+        }
         if (flipped) {
             intersections->flip();
         }
@@ -179,7 +190,7 @@ public:
     }
 
     int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
-        addVerticalEndPoints(top, bottom, axisIntercept);
+        addExactVerticalEndPoints(top, bottom, axisIntercept);
         double rootVals[2];
         int roots = verticalIntersect(axisIntercept, rootVals);
         for (int index = 0; index < roots; ++index) {
@@ -190,6 +201,9 @@ public:
                 intersections->insert(quadT, lineT, pt);
             }
         }
+        if (fAllowNear) {
+            addNearVerticalEndPoints(top, bottom, axisIntercept);
+        }
         if (flipped) {
             intersections->flip();
         }
@@ -198,73 +212,88 @@ public:
 
 protected:
     // add endpoints first to get zero and one t values exactly
-    void addEndPoints() {
+    void addExactEndPoints() {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
-            bool foundEnd = false;
-            for (int lIndex = 0; lIndex < 2; lIndex++) {
-                if (quad[qIndex] == line[lIndex]) {
-                    intersections->insert(qIndex >> 1, lIndex, line[lIndex]);
-                    foundEnd = true;
-                }
-            }
-            if (foundEnd) {
+            double lineT = line.exactPoint(quad[qIndex]);
+            if (lineT < 0) {
                 continue;
             }
-            // See if the quad end touches the line.
-            double dist = line.isLeft(quad[qIndex]); // 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?
+            double quadT = (double) (qIndex >> 1);
+            intersections->insert(quadT, lineT, quad[qIndex]);
+        }
+    }
+
+    void addNearEndPoints() {
+        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+            double quadT = (double) (qIndex >> 1);
+            if (intersections->hasT(quadT)) {
                 continue;
             }
-            double lineT = findLineT(qIndex >> 1);
-            if (!between(0, lineT, 1)) {
+            double lineT = line.nearPoint(quad[qIndex]);
+            if (lineT < 0) {
                 continue;
             }
-            SkDPoint linePt = line.xyAtT(lineT);
-            if (linePt.approximatelyEqual(quad[qIndex])) {
-                intersections->insert(qIndex >> 1, lineT, quad[qIndex]);
+            intersections->insert(quadT, lineT, quad[qIndex]);
+        }
+        // FIXME: see if line end is nearly on quad
+    }
+
+    void addExactHorizontalEndPoints(double left, double right, double y) {
+        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+            double lineT = SkDLine::ExactPointH(quad[qIndex], left, right, y);
+            if (lineT < 0) {
+                continue;
             }
+            double quadT = (double) (qIndex >> 1);
+            intersections->insert(quadT, lineT, quad[qIndex]);
         }
     }
 
-    void addHorizontalEndPoints(double left, double right, double y) {
+    void addNearHorizontalEndPoints(double left, double right, double y) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
-            if (!AlmostEqualUlps(quad[qIndex].fY, y)) {
+            double quadT = (double) (qIndex >> 1);
+            if (intersections->hasT(quadT)) {
                 continue;
             }
-            double x = quad[qIndex].fX;
-            if (between(left, x, right)) {
-                double t = (x - left) / (right - left);
-                intersections->insert(qIndex >> 1, t, quad[qIndex]);
+            double lineT = SkDLine::NearPointH(quad[qIndex], left, right, y);
+            if (lineT < 0) {
+                continue;
             }
+            intersections->insert(quadT, lineT, quad[qIndex]);
         }
+        // FIXME: see if line end is nearly on quad
     }
 
-    void addVerticalEndPoints(double top, double bottom, double x) {
+    void addExactVerticalEndPoints(double top, double bottom, double x) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
-            if (!AlmostEqualUlps(quad[qIndex].fX, x)) {
+            double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x);
+            if (lineT < 0) {
                 continue;
             }
-            double y = quad[qIndex].fY;
-            if (between(top, y, bottom)) {
-                double t = (y - top) / (bottom - top);
-                intersections->insert(qIndex >> 1, t, quad[qIndex]);
+            double quadT = (double) (qIndex >> 1);
+            intersections->insert(quadT, lineT, quad[qIndex]);
+        }
+    }
+
+    void addNearVerticalEndPoints(double top, double bottom, double x) {
+        for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+            double quadT = (double) (qIndex >> 1);
+            if (intersections->hasT(quadT)) {
+                continue;
+            }
+            double lineT = SkDLine::NearPointV(quad[qIndex], top, bottom, x);
+            if (lineT < 0) {
+                continue;
             }
+            intersections->insert(quadT, lineT, quad[qIndex]);
         }
+        // FIXME: see if line end is nearly on quad
     }
 
     double findLineT(double t) {
         SkDPoint xy = quad.xyAtT(t);
         double dx = line[1].fX - line[0].fX;
         double dy = line[1].fY - line[0].fY;
-#if 0
-        if (fabs(dx) > fabs(dy)) {
-            return (xy.fX - line[0].fX) / dx;
-        }
-        return (xy.fY - line[0].fY) / dy;
-#else
         double dxT = (xy.fX - line[0].fX) / dx;
         double dyT = (xy.fY - line[0].fY) / dy;
         if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) {
@@ -274,7 +303,6 @@ protected:
             return dxT;
         }
         return fabs(dx) > fabs(dy) ? dxT : dyT;
-#endif
     }
 
     static bool PinTs(double* quadT, double* lineT) {
@@ -284,16 +312,8 @@ protected:
         if (!approximately_zero_or_more(*lineT)) {
             return false;
         }
-        if (precisely_less_than_zero(*quadT)) {
-            *quadT = 0;
-        } else if (precisely_greater_than_one(*quadT)) {
-            *quadT = 1;
-        }
-        if (precisely_less_than_zero(*lineT)) {
-            *lineT = 0;
-        } else if (precisely_greater_than_one(*lineT)) {
-            *lineT = 1;
-        }
+        *quadT = SkPinT(*quadT);
+        *lineT = SkPinT(*lineT);
         return true;
     }
 
@@ -301,6 +321,7 @@ private:
     const SkDQuad& quad;
     const SkDLine& line;
     SkIntersections* intersections;
+    bool fAllowNear;
 };
 
 // utility for pairs of coincident quads
@@ -355,6 +376,7 @@ int SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, do
 
 int SkIntersections::intersect(const SkDQuad& quad, const SkDLine& line) {
     LineQuadraticIntersections q(quad, line, this);
+    q.allowNear(fAllowNear);
     return q.intersect();
 }
 
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index af6cc080ef..fe23316683 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -156,7 +156,7 @@ void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub
     insertCoincident(e1, e2, endPt);
 }
 
-int SkIntersections::insert(double one, double two, double x, double y) {
+int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
     if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
         // For now, don't allow a mix of coincident and non-coincident intersections
         return -1;
@@ -166,15 +166,17 @@ int SkIntersections::insert(double one, double two, double x, double y) {
     for (index = 0; index < fUsed; ++index) {
         double oldOne = fT[0][index];
         double oldTwo = fT[1][index];
-        if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) {
+        if (one == oldOne && two == oldTwo) {
+            return -1;
+        }
+        if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
             if ((precisely_zero(one) && !precisely_zero(oldOne))
                     || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
                     || (precisely_zero(two) && !precisely_zero(oldTwo))
                     || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
                 fT[0][index] = one;
                 fT[1][index] = two;
-                fPt[index].fX = x;
-                fPt[index].fY = y;
+                fPt[index] = pt;
             }
             return -1;
         }
@@ -196,18 +198,13 @@ int SkIntersections::insert(double one, double two, double x, double y) {
         fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
         fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
     }
-    fPt[index].fX = x;
-    fPt[index].fY = y;
+    fPt[index] = pt;
     fT[0][index] = one;
     fT[1][index] = two;
     ++fUsed;
     return index;
 }
 
-int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
-    return insert(one, two, pt.fX, pt.fY);
-}
-
 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
     int index = insertSwap(one, two, pt);
     int bit = 1 << index;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index c0bb61fef0..de3d44cd70 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -45,6 +45,10 @@ public:
         SkDEBUGCODE(fDepth = i.fDepth);
     }
 
+    void allowNear(bool nearAllowed) {
+        fAllowNear = nearAllowed;
+    }
+
     int cubic(const SkPoint a[4]) {
         SkDCubic cubic;
         cubic.set(a);
@@ -88,6 +92,11 @@ public:
         return intersect(cubic, quad);
     }
 
+    bool hasT(double t) const {
+        SkASSERT(t == 0 || t == 1);
+        return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
+    }
+
     int insertSwap(double one, double two, const SkDPoint& pt) {
         if (fSwap) {
             return insert(two, one, pt);
@@ -96,14 +105,6 @@ public:
         }
     }
 
-    int insertSwap(double one, double two, double x, double y) {
-        if (fSwap) {
-            return insert(two, one, x, y);
-        } else {
-            return insert(one, two, x, y);
-        }
-    }
-
     bool isCoincident(int index) {
         return (fIsCoincident[0] & 1 << index) != 0;
     }
@@ -166,6 +167,7 @@ public:
 
     // leaves flip, swap alone
     void reset() {
+        fAllowNear = true;
         fUsed = 0;
     }
 
@@ -204,7 +206,6 @@ public:
     int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
     // FIXME : does not respect swap
     int insert(double one, double two, const SkDPoint& pt);
-    int insert(double one, double two, double x, double y);
     // start if index == 0 : end if index == 1
     void insertCoincident(double one, double two, const SkDPoint& pt);
     void insertCoincidentPair(double s1, double e1, double s2, double e2,
@@ -248,6 +249,7 @@ private:
     double fT[2][9];
     uint16_t fIsCoincident[2];  // bit arrays, one bit set for each coincident T
     unsigned char fUsed;
+    bool fAllowNear;
     bool fSwap;
 #ifdef SK_DEBUG
     int fDepth;
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 84f0eb10dd..456e6c0068 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -90,6 +90,20 @@ public:
 
     void calcCoincidentWinding();
 
+    void checkEnds() {
+        if (!fContainsCurves) {
+            return;
+        }
+        int segmentCount = fSegments.count();
+        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
+            SkOpSegment* segment = &fSegments[sIndex];
+            if (segment->verb() == SkPath::kLine_Verb) {
+                continue;
+            }
+            fSegments[sIndex].checkEnds();
+        }
+    }
+
     void complete() {
         setBounds();
         fContainsIntercepts = false;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 8bd4cc275a..5b20749957 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -209,7 +209,7 @@ bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* s
 void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
     SkASSERT(start != end);
     SkOpAngle& angle = anglesPtr->push_back();
-#if DEBUG_ANGLE
+#if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq
     SkTArray<SkOpAngle, true>& angles = *anglesPtr;
     if (angles.count() > 1) {
         const SkOpSegment* aSeg = angles[0].segment();
@@ -1080,6 +1080,86 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
     return false;
 }
 
+// look to see if the curve end intersects an intermediary that intersects the other
+void SkOpSegment::checkEnds() {
+#if 1
+    return;  // FIXME: suspect we will need the code below to make intersections consistent
+#else
+    SkTDArray<SkOpSpan> missingSpans;
+    int count = fTs.count();
+    for (int index = 0; index < count; ++index) {
+        const SkOpSpan& span = fTs[index];
+        const SkOpSegment* other = span.fOther;
+        const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex];
+        double otherT = otherSpan->fT;
+        if (otherT != 0 && otherT != 1) {
+            continue;
+        }
+        int peekStart = span.fOtherIndex;
+        while (peekStart > 0) {
+            const SkOpSpan* peeker = &other->fTs[peekStart - 1];
+            if (peeker->fT != otherT) {
+                break;
+            }
+            --peekStart;
+        }
+        int otherLast = other->fTs.count() - 1;
+        int peekLast = span.fOtherIndex;
+        while (peekLast < otherLast) {
+            const SkOpSpan* peeker = &other->fTs[peekLast + 1];
+            if (peeker->fT != otherT) {
+                break;
+            }
+            ++peekLast;
+        }
+        if (peekStart == peekLast) {
+            continue;
+        }
+        double t = span.fT;
+        int tStart = index;
+        while (tStart > 0 && t == fTs[tStart - 1].fT) {
+            --tStart;
+        }
+        int tLast = index;
+        int last = count - 1;
+        while (tLast < last && t == fTs[tLast + 1].fT) {
+            ++tLast;
+        }
+        for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
+            if (peekIndex == span.fOtherIndex) {
+                continue;
+            }
+            const SkOpSpan& peekSpan = other->fTs[peekIndex];
+            SkOpSegment* match = peekSpan.fOther;
+            const double matchT = peekSpan.fOtherT;
+            for (int tIndex = tStart; tIndex <= tLast; ++tIndex) {
+                const SkOpSpan& tSpan = fTs[tIndex];
+                if (tSpan.fOther == match && tSpan.fOtherT == matchT) {
+                    goto nextPeeker;
+                }
+            }
+            // this segment is missing a entry that the other contains
+            // remember so we can add the missing one and recompute the indices
+            SkOpSpan* missing = missingSpans.append();
+            missing->fT = t;
+            missing->fOther = match;
+            missing->fOtherT = matchT;
+            missing->fPt = peekSpan.fPt;
+        }
+nextPeeker:
+        ;
+    }
+    int missingCount = missingSpans.count();
+    for (int index = 0; index < missingCount; ++index)  {
+        const SkOpSpan& missing = missingSpans[index];
+        addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
+    }
+    if (missingCount > 0) {
+        fixOtherTIndex();
+    }
+#endif
+}
+
 bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) {
     SkASSERT(greaterTIndex >= lesserTIndex);
     double greaterT = fTs[greaterTIndex].fT;
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 3cbd29e77e..7e5e644f1d 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -254,6 +254,7 @@ public:
                   const SkPoint& oPt);
     int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT);
     bool betweenTs(int lesser, double testT, int greater) const;
+    void checkEnds();
     int computeSum(int startIndex, int endIndex, bool binary);
     int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
                      double mid, bool opp, bool current) const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 5a30c3a98e..9a92b00acd 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -344,6 +344,16 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bo
     return current;
 }
 
+void CheckEnds(SkTArray<SkOpContour*, true>* contourList) {
+    // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
+    // instead, look to see if the connecting curve intersected at that same end.
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->checkEnds();
+    }
+}
+
 void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 569edb7e32..4ba4af2300 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -13,6 +13,7 @@
 class SkPathWriter;
 
 void Assemble(const SkPathWriter& path, SkPathWriter* simple);
+void CheckEnds(SkTArray<SkOpContour*, true>* contourList);
 // FIXME: find chase uses insert, so it can't be converted to SkTArray yet
 SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex);
 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour,
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 5484147c3a..05fe241e0f 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -103,10 +103,10 @@ extern int gDebugMaxWindValue;
         DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION)
 
 #if DEBUG_AS_C_CODE
-#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define QUAD_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define LINE_DEBUG_STR  "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define PT_DEBUG_STR "{{%1.17g,%1.17g}}"
+#define CUBIC_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define QUAD_DEBUG_STR  "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define LINE_DEBUG_STR  "{{%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define PT_DEBUG_STR "{{%1.9g,%1.9g}}"
 #else
 #define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
 #define QUAD_DEBUG_STR  "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp
index b7c91c991d..47c0565b69 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -41,8 +41,99 @@ double SkDLine::isLeft(const SkDPoint& pt) const {
     return p0.cross(p2);
 }
 
+// OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1)
 SkDPoint SkDLine::xyAtT(double t) const {
     double one_t = 1 - t;
     SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
     return result;
 }
+
+double SkDLine::exactPoint(const SkDPoint& xy) const {
+    if (xy == fPts[0]) {  // do cheapest test first
+        return 0;
+    }
+    if (xy == fPts[1]) {
+        return 1;
+    }
+    return -1;
+}
+
+double SkDLine::nearPoint(const SkDPoint& xy) const {
+    if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
+            || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
+        return -1;
+    }
+    // project a perpendicular ray from the point to the line; find the T on the line
+    SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
+    double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
+    SkDVector ab0 = xy - fPts[0];
+    double numer = len.fX * ab0.fX + ab0.fY * len.fY;
+    if (!between(0, numer, denom)) {
+        return -1;
+    }
+    double t = numer / denom;
+    SkDPoint realPt = xyAtT(t);
+    SkDVector distU = xy - realPt;
+    double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
+    double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
+    // find the ordinal in the original line with the largest unsigned exponent
+    double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+    double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+    largest = SkTMax(largest, -tiniest);
+    if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
+        return -1;
+    }
+    t = SkPinT(t);
+    SkASSERT(between(0, t, 1));
+    return t;
+}
+
+double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
+    if (xy.fY == y) {
+        if (xy.fX == left) {
+            return 0;
+        }
+        if (xy.fX == right) {
+            return 1;
+        }
+    }
+    return -1;
+}
+
+double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
+    if (!AlmostEqualUlps(xy.fY, y)) {
+        return -1;
+    }
+    if (!AlmostBetweenUlps(left, xy.fX, right)) {
+        return -1;
+    }
+    double t = (xy.fX - left) / (right - left);
+    t = SkPinT(t);
+    SkASSERT(between(0, t, 1));
+    return t;
+}
+
+double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
+    if (xy.fX == x) {
+        if (xy.fY == top) {
+            return 0;
+        }
+        if (xy.fY == bottom) {
+            return 1;
+        }
+    }
+    return -1;
+}
+
+double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
+    if (!AlmostEqualUlps(xy.fX, x)) {
+        return -1;
+    }
+    if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
+        return -1;
+    }
+    double t = (xy.fY - top) / (bottom - top);
+    t = SkPinT(t);
+    SkASSERT(between(0, t, 1));
+    return t;
+}
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index 34bb6587d3..c5ac7fdb09 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -12,21 +12,28 @@
 struct SkDLine {
     SkDPoint fPts[2];
 
+    const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
+    SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
+
     void set(const SkPoint pts[2]) {
         fPts[0] = pts[0];
         fPts[1] = pts[1];
     }
 
-    const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
-    SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
-
-    double isLeft(const SkDPoint& pt) const;
-    SkDLine subDivide(double t1, double t2) const;
     static SkDLine SubDivide(const SkPoint a[2], double t1, double t2) {
         SkDLine line;
         line.set(a);
         return line.subDivide(t1, t2);
     }
+
+    double exactPoint(const SkDPoint& xy) const;
+    static double ExactPointH(const SkDPoint& xy, double left, double right, double y);
+    static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x);
+    double isLeft(const SkDPoint& pt) const;
+    double nearPoint(const SkDPoint& xy) const;
+    static double NearPointH(const SkDPoint& xy, double left, double right, double y);
+    static double NearPointV(const SkDPoint& xy, double top, double bottom, double x);
+    SkDLine subDivide(double t1, double t2) const;
     SkDPoint xyAtT(double t) const;
 private:
     SkDVector tangent() const { return fPts[0] - fPts[1]; }
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 0df4859cdf..71efeeea8c 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -299,6 +299,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
     SkOpContour::debugShowWindingValues(contourList);
 #endif
     FixOtherTIndex(&contourList);
+    CheckEnds(&contourList);
     SortSegments(&contourList);
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
     DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 3cbc28abf4..636e3854fd 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -164,6 +164,7 @@ SkDVector SkDQuad::dxdyAtT(double t) const {
     return result;
 }
 
+// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
 SkDPoint SkDQuad::xyAtT(double t) const {
     double one_t = 1 - t;
     double a = one_t * one_t;
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index fd40c38503..488778904f 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -185,6 +185,7 @@ bool Simplify(const SkPath& path, SkPath* result) {
     // eat through coincident edges
     CoincidenceCheck(&contourList, 0);
     FixOtherTIndex(&contourList);
+    CheckEnds(&contourList);
     SortSegments(&contourList);
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
     DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 999e1b215d..a076d155f2 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -16,8 +16,7 @@ static bool equal_ulps(float A, float B, int epsilon) {
     floatIntA.fFloat = A;
     floatIntB.fFloat = B;
     // Different signs means they do not match.
-    if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0))
-    {
+    if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
         // Check for equality to make sure +0 == -0
         return A == B;
     }
@@ -26,6 +25,18 @@ static bool equal_ulps(float A, float B, int epsilon) {
     return ulpsDiff <= epsilon;
 }
 
+static bool less_ulps(float A, float B, int epsilon) {
+    SkFloatIntUnion floatIntA, floatIntB;
+    floatIntA.fFloat = A;
+    floatIntB.fFloat = B;
+    // Check different signs with float epsilon since we only care if they're both close to 0.
+    if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
+        return A <= B + FLT_EPSILON * epsilon;
+    }
+    // Find the difference in ULPs.
+    return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon;
+}
+
 bool AlmostEqualUlps(float A, float B) {
     const int UlpsEpsilon = 16;
     return equal_ulps(A, B, UlpsEpsilon);
@@ -36,6 +47,12 @@ bool RoughlyEqualUlps(float A, float B) {
     return equal_ulps(A, B, UlpsEpsilon);
 }
 
+bool AlmostBetweenUlps(float a, float b, float c) {
+    const int UlpsEpsilon = 1;
+    return a <= c ? less_ulps(a, b, UlpsEpsilon) && less_ulps(b, c, UlpsEpsilon)
+        : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon);
+}
+
 // cube root approximation using bit hack for 64-bit float
 // adapted from Kahan's cbrt
 static double cbrt_5d(double d) {
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 20641d3345..c988691e26 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -33,6 +33,11 @@ inline bool RoughlyEqualUlps(double A, double B) {
     return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
 }
 
+bool AlmostBetweenUlps(float a, float b, float c);
+inline bool AlmostBetweenUlps(double A, double B, double C) {
+    return AlmostBetweenUlps(SkDoubleToScalar(A), SkDoubleToScalar(B), SkDoubleToScalar(C));
+}
+
 // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
 // DBL_EPSILON == 2.22045e-16
 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
@@ -260,4 +265,8 @@ inline int SkDSideBit(double x) {
     return 1 << SKDSide(x);
 }
 
+inline double SkPinT(double t) {
+    return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
+}
+
 #endif