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

1 files changed, 75 insertions, 53 deletions

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();
 }