pathops coincidence and security rewrite

src/pathops/SkOpAngle.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 "SkOpAngle.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"
 #include "SkTSort.h"
@@ skipping 44 matching lines @@
                               20         |         26
                                  21      |      25
                                      22 23 24
 */
 
 // return true if lh < this < rh
 bool SkOpAngle::after(SkOpAngle* test) {
     SkOpAngle* lh = test;
     SkOpAngle* rh = lh->fNext;
     SkASSERT(lh != rh);
+    fCurvePart = fOriginalCurvePart;
+    lh->fCurvePart = lh->fOriginalCurvePart;
+    lh->fCurvePart.offset(lh->segment()->verb(), fCurvePart[0] - lh->fCurvePart[0]);
+    rh->fCurvePart = rh->fOriginalCurvePart;
+    rh->fCurvePart.offset(rh->segment()->verb(), fCurvePart[0] - rh->fCurvePart[0]);
+
 #if DEBUG_ANGLE
     SkString bugOut;
     bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
                   " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
             lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
             lh->fStart->t(), lh->fEnd->t(),
             segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
             rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
             rh->fStart->t(), rh->fEnd->t());
@@ skipping 68 matching lines @@
     // FIXME : once all variants are understood, rewrite this more simply
     if (ltOrder == 0 && lrOrder == 0) {
         SkASSERT(trOrder < 0);
         // FIXME : once this is verified to work, remove one opposite angle call
         SkDEBUGCODE(bool lrOpposite = lh->oppositePlanes(rh));
         bool ltOpposite = lh->oppositePlanes(this);
         SkASSERT(lrOpposite != ltOpposite);
         return COMPARE_RESULT(8, ltOpposite);
     } else if (ltOrder == 1 && trOrder == 0) {
         SkASSERT(lrOrder < 0);
-        SkDEBUGCODE(bool ltOpposite = lh->oppositePlanes(this));
         bool trOpposite = oppositePlanes(rh);
-        SkASSERT(ltOpposite != trOpposite);
         return COMPARE_RESULT(9, trOpposite);
     } else if (lrOrder == 1 && trOrder == 1) {
         SkASSERT(ltOrder < 0);
         SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
         bool lrOpposite = lh->oppositePlanes(rh);
         SkASSERT(lrOpposite != trOpposite);
         return COMPARE_RESULT(10, lrOpposite);
     }
     if (lrOrder < 0) {
         if (ltOrder < 0) {
             return COMPARE_RESULT(11, trOrder);
         }
         return COMPARE_RESULT(12, ltOrder);
     }
     return COMPARE_RESULT(13, !lrOrder);
 }
 
 // given a line, see if the opposite curve's convex hull is all on one side
 // returns -1=not on one side    0=this CW of test   1=this CCW of test
 int SkOpAngle::allOnOneSide(const SkOpAngle* test) {
     SkASSERT(!fIsCurve);
     SkASSERT(test->fIsCurve);
-    const SkDPoint& origin = test->fCurvePart[0];
-    SkVector line;
-    if (segment()->verb() == SkPath::kLine_Verb) {
-        const SkPoint* linePts = segment()->pts();
-        int lineStart = fStart->t() < fEnd->t() ? 0 : 1;
-        line = linePts[lineStart ^ 1] - linePts[lineStart];
-    } else {
-        line = (fCurvePart[1] - fCurvePart[0]).asSkVector();
-    }
+    SkDPoint origin = fCurvePart[0];
+    SkDVector line = fCurvePart[1] - origin;
     float crosses[3];
     SkPath::Verb testVerb = test->segment()->verb();
     int iMax = SkPathOpsVerbToPoints(testVerb);
 //    SkASSERT(origin == test.fCurveHalf[0]);
     const SkDCurve& testCurve = test->fCurvePart;
     for (int index = 1; index <= iMax; ++index) {
         float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
         float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
         crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2;
     }
@@ skipping 40 matching lines @@
         scratch[1] = rh->fCurvePart[1] - rh->fCurvePart[0];
         tweep = &scratch[1];
     }
     double s0xt0 = sweep->crossCheck(*tweep);
     if (tangentsDiverge(rh, s0xt0)) {
         return s0xt0 < 0;
     }
     // compute the perpendicular to the endpoints and see where it intersects the opposite curve
     // if the intersections within the t range, do a cross check on those
     bool inside;
-    if (!fCurvePart[SkPathOpsVerbToPoints(this->segment()->verb())].approximatelyEqual(
-            rh->fCurvePart[SkPathOpsVerbToPoints(rh->segment()->verb())])) {
+    if (!fEnd->contains(rh->fEnd)) {
         if (this->endToSide(rh, &inside)) {
             return inside;
         }
         if (rh->endToSide(this, &inside)) {
             return !inside;
         }
     }
     if (this->midToSide(rh, &inside)) {
         return inside;
     }
@@ skipping 14 matching lines @@
 
 // the original angle is too short to get meaningful sector information
 // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
 // would cause it to intersect one of the adjacent angles
 bool SkOpAngle::computeSector() {
     if (fComputedSector) {
         return !fUnorderable;
     }
     fComputedSector = true;
     bool stepUp = fStart->t() < fEnd->t();
-    const SkOpSpanBase* checkEnd = fEnd;
+    SkOpSpanBase* checkEnd = fEnd;
     if (checkEnd->final() && stepUp) {
         fUnorderable = true;
         return false;
     }
     do {
 // advance end
         const SkOpSegment* other = checkEnd->segment();
         const SkOpSpanBase* oSpan = other->head();
         do {
             if (oSpan->segment() != segment()) {
                 continue;
             }
             if (oSpan == checkEnd) {
                 continue;
             }
             if (!approximately_equal(oSpan->t(), checkEnd->t())) {
                 continue;
             }
             goto recomputeSector;
         } while (!oSpan->final() && (oSpan = oSpan->upCast()->next()));
         checkEnd = stepUp ? !checkEnd->final()
                 ? checkEnd->upCast()->next() : nullptr
                 : checkEnd->prev();
     } while (checkEnd);
 recomputeSector:
-    SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head() 
+    SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head()
             : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
     if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
         fUnorderable = true;
         return false;
     }
     if (stepUp != (fStart->t() < computedEnd->t())) {
         fUnorderable = true;
         return false;
     }
     SkOpSpanBase* saveEnd = fEnd;
@@ skipping 71 matching lines @@
     return sqrt(longest) / dist;
 }
 
 bool SkOpAngle::endsIntersect(SkOpAngle* rh) {
     SkPath::Verb lVerb = this->segment()->verb();
     SkPath::Verb rVerb = rh->segment()->verb();
     int lPts = SkPathOpsVerbToPoints(lVerb);
     int rPts = SkPathOpsVerbToPoints(rVerb);
     SkDLine rays[] = {{{this->fCurvePart[0], rh->fCurvePart[rPts]}},
             {{this->fCurvePart[0], this->fCurvePart[lPts]}}};
-    if (rays[0][1] == rays[1][1]) {
+    if (this->fEnd->contains(rh->fEnd)) {
         return checkParallel(rh);
     }
     double smallTs[2] = {-1, -1};
     bool limited[2] = {false, false};
     for (int index = 0; index < 2; ++index) {
         SkPath::Verb cVerb = index ? rVerb : lVerb;
         // if the curve is a line, then the line and the ray intersect only at their crossing
         if (cVerb == SkPath::kLine_Verb) {
             continue;
         }
@@ skipping 119 matching lines @@
     const SkDCurve& curve = rh->fCurvePart;
     int oppPts = SkPathOpsVerbToPoints(oppVerb);
     for (int idx2 = 0; idx2 <= oppPts; ++idx2) {
         minX = SkTMin(minX, curve[idx2].fX);
         minY = SkTMin(minY, curve[idx2].fY);
         maxX = SkTMax(maxX, curve[idx2].fX);
         maxY = SkTMax(maxY, curve[idx2].fY);
     }
     double maxWidth = SkTMax(maxX - minX, maxY - minY);
     endDist /= maxWidth;
-    if (endDist < 5e-11) {  // empirically found
+    if (endDist < 5e-12) {  // empirically found
         return false;
     }
     const SkDPoint* endPt = &rayEnd[0];
     SkDPoint oppPt = iEnd.pt(closestEnd);
     SkDVector vLeft = *endPt - start;
     SkDVector vRight = oppPt - start;
-    double dir = vLeft.crossCheck(vRight);
+    double dir = vLeft.crossNoNormalCheck(vRight);
     if (!dir) {
         return false;
     }
     *inside = dir < 0;
     return true;
 }
 
 /*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
     0    x                      x               x
     1    x                      x          x
@@ skipping 219 matching lines @@
             double rx_y = rightX * leftY;
             if (x_ry == rx_y) {
                 if (leftX * rightX < 0 || leftY * rightY < 0) {
                     return true;  // exactly 180 degrees apart
                 }
                 goto unorderable;
             }
             SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
             return x_ry < rx_y;
         }
-        if ((result = allOnOneSide(rh)) >= 0) {
+        if ((result = this->allOnOneSide(rh)) >= 0) {
             return result;
         }
         if (fUnorderable || approximately_zero(rh->fSide)) {
             goto unorderable;
         }
     } else if (!rh->fIsCurve) {
         if ((result = rh->allOnOneSide(this)) >= 0) {
             return !result;
         }
         if (rh->fUnorderable || approximately_zero(fSide)) {
             goto unorderable;
         }
-    }
-    if ((result = convexHullOverlaps(rh)) >= 0) {
+    } else if ((result = this->convexHullOverlaps(rh)) >= 0) {
         return result;
     }
-    return endsIntersect(rh);
+    return this->endsIntersect(rh);
 unorderable:
     fUnorderable = true;
     rh->fUnorderable = true;
     return true;
 }
 
 // OPTIMIZE: if this shows up in a profile, add a previous pointer
 // as is, this should be rarely called
 SkOpAngle* SkOpAngle::previous() const {
     SkOpAngle* last = fNext;
@@ skipping 23 matching lines @@
 
 void SkOpAngle::setCurveHullSweep() {
     fUnorderedSweep = false;
     fSweep[0] = fCurvePart[1] - fCurvePart[0];
     const SkOpSegment* segment = fStart->segment();
     if (SkPath::kLine_Verb == segment->verb()) {
         fSweep[1] = fSweep[0];
         return;
     }
     fSweep[1] = fCurvePart[2] - fCurvePart[0];
+    // OPTIMIZE: I do the following float check a lot -- probably need a
+    // central place for this val-is-small-compared-to-curve check
+    double maxVal = 0;
+    for (int index = 0; index < SkPathOpsVerbToPoints(segment->verb()); ++index) {
+        maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurvePart[index].fX),
+                SkTAbs(fCurvePart[index].fY)));
+    }
+
     if (SkPath::kCubic_Verb != segment->verb()) {
-        if (!fSweep[0].fX && !fSweep[0].fY) {
+        if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
+                && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
             fSweep[0] = fSweep[1];
         }
         return;
     }
     SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0];
     if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
         fSweep[0] = fSweep[1];
         fSweep[1] = thirdSweep;
-        if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
+        if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
+                && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
             fSweep[0] = fSweep[1];
             fCurvePart[1] = fCurvePart[3];
             fIsCurve = false;
         }
         return;
     }
     double s1x3 = fSweep[0].crossCheck(thirdSweep);
     double s3x2 = thirdSweep.crossCheck(fSweep[1]);
     if (s1x3 * s3x2 >= 0) {  // if third vector is on or between first two vectors
         return;
@@ skipping 17 matching lines @@
         fUnorderable = true;
         return;
     }
     const SkOpSegment* segment = fStart->segment();
     const SkPoint* pts = segment->pts();
     SkDEBUGCODE(fCurvePart.fVerb = SkPath::kCubic_Verb);
     SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
             = SK_ScalarNaN);
     SkDEBUGCODE(fCurvePart.fVerb = segment->verb());
     segment->subDivide(fStart, fEnd, &fCurvePart);
+    fOriginalCurvePart = fCurvePart;
     setCurveHullSweep();
     const SkPath::Verb verb = segment->verb();
     if (verb != SkPath::kLine_Verb
             && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
         SkDLine lineHalf;
         lineHalf[0].set(fCurvePart[0].asSkPoint());
         lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
         fTangentHalf.lineEndPoints(lineHalf);
         fSide = 0;
     }
@@ skipping 135 matching lines @@
     double s0dt0 = sweep[0].dot(tweep[0]);
     if (!s0dt0) {
         return true;
     }
     SkASSERT(s0dt0 != 0);
     double m = s0xt0 / s0dt0;
     double sDist = sweep[0].length() * m;
     double tDist = tweep[0].length() * m;
     bool useS = fabs(sDist) < fabs(tDist);
     double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
-    return mFactor < 2400;  // empirically found limit
+    return mFactor < 50;   // empirically found limit
 }