pathops coincidence and security rewrite

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 "SkPathOpsCurve.h"
 #include "SkPathOpsLine.h"
 #include "SkPathOpsQuad.h"
 
 /*
 Find the interection of a line and quadratic by solving for valid t values.
 
 From http://stackoverflow.com/questions/1853637/how-to-find-the-mathematical-function-defining-a-bezier-curve
 
 "A Bezier curve is a parametric function. A quadratic Bezier curve (i.e. three
 control points) can be expressed as: F(t) = A(1 - t)^2 + B(1 - t)t + Ct^2 where
@@ skipping 73 matching lines @@
     enum PinTPoint {
         kPointUninitialized,
         kPointInitialized
     };
 
     LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i)
         : fQuad(q)
         , fLine(&l)
         , fIntersections(i)
         , fAllowNear(true) {
-        i->setMax(3);  // allow short partial coincidence plus discrete intersection
+        i->setMax(4);  // allow short partial coincidence plus discrete intersections
     }
 
     LineQuadraticIntersections(const SkDQuad& q)
-        : fQuad(q) 
+        : fQuad(q)
         SkDEBUGPARAMS(fLine(nullptr))
         SkDEBUGPARAMS(fIntersections(nullptr))
         SkDEBUGPARAMS(fAllowNear(false)) {
     }
 
     void allowNear(bool allow) {
         fAllowNear = allow;
     }
 
     void checkCoincident() {
@@ skipping 174 matching lines @@
             double quadT = (double) (qIndex >> 1);
             if (fIntersections->hasT(quadT)) {
                 continue;
             }
             double lineT = fLine->nearPoint(fQuad[qIndex], nullptr);
             if (lineT < 0) {
                 continue;
             }
             fIntersections->insert(quadT, lineT, fQuad[qIndex]);
         }
-        // FIXME: see if line end is nearly on quad
+        addLineNearEndPoints();
+    }
+
+    void addLineNearEndPoints() {
+        for (int lIndex = 0; lIndex < 2; ++lIndex) {
+            double lineT = (double) lIndex;
+            if (fIntersections->hasOppT(lineT)) {
+                continue;
+            }
+            double quadT = ((SkDCurve*) &fQuad)->nearPoint(SkPath::kQuad_Verb,
+                    (*fLine)[lIndex], (*fLine)[!lIndex]);
+            if (quadT < 0) {
+                continue;
+            }
+            fIntersections->insert(quadT, lineT, (*fLine)[lIndex]);
+        }
     }
 
     void addExactHorizontalEndPoints(double left, double right, double y) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
             double lineT = SkDLine::ExactPointH(fQuad[qIndex], left, right, y);
             if (lineT < 0) {
                 continue;
             }
             double quadT = (double) (qIndex >> 1);
             fIntersections->insert(quadT, lineT, fQuad[qIndex]);
         }
     }
 
     void addNearHorizontalEndPoints(double left, double right, double y) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
             double quadT = (double) (qIndex >> 1);
             if (fIntersections->hasT(quadT)) {
                 continue;
             }
             double lineT = SkDLine::NearPointH(fQuad[qIndex], left, right, y);
             if (lineT < 0) {
                 continue;
             }
             fIntersections->insert(quadT, lineT, fQuad[qIndex]);
         }
-        // FIXME: see if line end is nearly on quad
+        addLineNearEndPoints();

[herb_g, 2016/07/18 15:13:39]

this->

[caryclark, 2016/07/18 15:55:49]

Done.

     }
 
     void addExactVerticalEndPoints(double top, double bottom, double x) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
             double lineT = SkDLine::ExactPointV(fQuad[qIndex], top, bottom, x);
             if (lineT < 0) {
                 continue;
             }
             double quadT = (double) (qIndex >> 1);
             fIntersections->insert(quadT, lineT, fQuad[qIndex]);
         }
     }
 
     void addNearVerticalEndPoints(double top, double bottom, double x) {
         for (int qIndex = 0; qIndex < 3; qIndex += 2) {
             double quadT = (double) (qIndex >> 1);
             if (fIntersections->hasT(quadT)) {
                 continue;
             }
             double lineT = SkDLine::NearPointV(fQuad[qIndex], top, bottom, x);
             if (lineT < 0) {
                 continue;
             }
             fIntersections->insert(quadT, lineT, fQuad[qIndex]);
         }
-        // FIXME: see if line end is nearly on quad
+        addLineNearEndPoints();
     }
 
     double findLineT(double t) {
         SkDPoint xy = fQuad.ptAtT(t);
         double dx = (*fLine)[1].fX - (*fLine)[0].fX;
         double dy = (*fLine)[1].fY - (*fLine)[0].fY;
         if (fabs(dx) > fabs(dy)) {
             return (xy.fX - (*fLine)[0].fX) / dx;
         }
         return (xy.fY - (*fLine)[0].fY) / dy;
@@ skipping 82 matching lines @@
 
 // SkDQuad accessors to Intersection utilities
 
 int SkDQuad::horizontalIntersect(double yIntercept, double roots[2]) const {
     return SkIntersections::HorizontalIntercept(*this, yIntercept, roots);
 }
 
 int SkDQuad::verticalIntersect(double xIntercept, double roots[2]) const {
     return SkIntersections::VerticalIntercept(*this, xIntercept, roots);
 }