align top and bounds computations

src/pathops/SkPathOpsCubic.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 "SkGeometry.h"
 #include "SkLineParameters.h"
 #include "SkPathOpsConic.h"
 #include "SkPathOpsCubic.h"
@@ skipping 57 matching lines @@
 
 // FIXME: cache keep the bounds and/or precision with the caller?
 double SkDCubic::calcPrecision() const {
     SkDRect dRect;
     dRect.setBounds(*this);  // OPTIMIZATION: just use setRawBounds ?
     double width = dRect.fRight - dRect.fLeft;
     double height = dRect.fBottom - dRect.fTop;
     return (width > height ? width : height) / gPrecisionUnit;
 }
 
-bool SkDCubic::clockwise(bool* swap) const {
+bool SkDCubic::clockwise(const SkDCubic& whole, bool* swap) const {
     SkDPoint lastPt = fPts[kPointLast];
     SkDPoint firstPt = fPts[0];
     double sum = 0;
     // pick the control point furthest from the line connecting the end points
     SkLineParameters lineParameters;
     lineParameters.cubicEndPoints(*this, 0, 3);
     lineParameters.normalize();
     double tiniest = SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY),
             fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY), fPts[3].fX), fPts[3].fY);
     double largest = SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY),
             fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY), fPts[3].fX), fPts[3].fY);
     largest = SkTMax(largest, -tiniest);
     double pt1dist = lineParameters.controlPtDistance(*this, 1);
     double pt2dist = lineParameters.controlPtDistance(*this, 2);
 #if DEBUG_SWAP_TOP
     SkDebugf("%s pt1dist=%1.9g pt2dist=%1.9g\n", __FUNCTION__, pt1dist, pt2dist);
 #endif
     int furthest;
     if (!approximately_zero_when_compared_to(pt1dist, largest)
             && !approximately_zero_when_compared_to(pt2dist, largest) && pt1dist * pt2dist < 0) {
         furthest = 2;
     } else {
         furthest = fabs(pt1dist) < fabs(pt2dist) ? 2 : 1;
     }
     for (int idx = 1; idx <= 3; ++idx) {
         sum += (firstPt.fX - lastPt.fX) * (firstPt.fY + lastPt.fY);
         lastPt = firstPt;
         firstPt = idx == 1 ? fPts[furthest] : fPts[kPointLast];
     }
-    *swap = sum > 0 && !this->monotonicInY();
+    *swap = sum > 0 && !this->monotonicInY() && !whole.monotonicInY();
     return sum <= 0;
 }
 
 bool SkDCubic::Clockwise(const SkPoint* pts, double startT, double endT, bool* swap) {
     SkDCubic cubic;
     cubic.set(pts);
-#if 0
-    bool flip = startT > endT;
-    double inflectionTs[2];
-    int inflections = cubic.findInflections(inflectionTs);
-    for (int index = 0; index < inflections; ++index) {
-        double inflectionT = inflectionTs[index];
-        if (between(startT, inflectionT, endT)) {
-            if (flip) {
-                if (!roughly_equal(inflectionT, endT)) {
-                startT = inflectionT;
-                }
-            } else {
-                if (!roughly_equal(inflectionT, startT)) {
-                    endT = inflectionT;
-                }
-            }
-        }
-    }
-#endif
     SkDCubic part = cubic.subDivide(startT, endT);
-    return part.clockwise(swap);
+    return part.clockwise(cubic, swap);
 }
 
 void SkDCubic::Coefficients(const double* src, double* A, double* B, double* C, double* D) {
     *A = src[6];  // d
     *B = src[4] * 3;  // 3*c
     *C = src[2] * 3;  // 3*b
     *D = src[0];  // a
     *A -= *D - *C + *B;     // A =   -a + 3*b - 3*c + d
     *B += 3 * *D - 2 * *C;  // B =  3*a - 6*b + 3*c
     *C -= 3 * *D;           // C = -3*a + 3*b
@@ skipping 148 matching lines @@
             }
         } else if (infTCount == 1) {
             *t = inflectionTs[0];
             *resultType = kSplitAtInflection_SkDCubicType;
             return *t > 0 && *t < 1;
         }
     }
     return false;
 }
 
+bool SkDCubic::monotonicInX() const {
+    return precisely_between(fPts[0].fX, fPts[1].fX, fPts[3].fX)
+            && precisely_between(fPts[0].fX, fPts[2].fX, fPts[3].fX);
+}
+
 bool SkDCubic::monotonicInY() const {
-    return between(fPts[0].fY, fPts[1].fY, fPts[3].fY)
-            && between(fPts[0].fY, fPts[2].fY, fPts[3].fY);
+    return precisely_between(fPts[0].fY, fPts[1].fY, fPts[3].fY)
+            && precisely_between(fPts[0].fY, fPts[2].fY, fPts[3].fY);
 }
 
 void SkDCubic::otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const {
     int offset = (int) !SkToBool(index);
     o1Pts[0] = &fPts[offset];
     o1Pts[1] = &fPts[++offset];
     o1Pts[2] = &fPts[++offset];
 }
 
 int SkDCubic::searchRoots(double extremeTs[6], int extrema, double axisIntercept,
@@ skipping 19 matching lines @@
 
 // cubic roots
 
 static const double PI = 3.141592653589793;
 
 // from SkGeometry.cpp (and Numeric Solutions, 5.6)
 int SkDCubic::RootsValidT(double A, double B, double C, double D, double t[3]) {
     double s[3];
     int realRoots = RootsReal(A, B, C, D, s);
     int foundRoots = SkDQuad::AddValidTs(s, realRoots, t);
+    for (int index = 0; index < realRoots; ++index) {
+        double tValue = s[index];
+        if (!approximately_one_or_less(tValue) && between(1, tValue, 1.00005)) {
+            for (int idx2 = 0; idx2 < foundRoots; ++idx2) {
+                if (approximately_equal(t[idx2], 1)) {
+                    goto nextRoot;
+                }
+            }
+            SkASSERT(foundRoots < 3);
+            t[foundRoots++] = 1;
+        } else if (!approximately_zero_or_more(tValue) && between(-0.00005, tValue, 0)) {
+            for (int idx2 = 0; idx2 < foundRoots; ++idx2) {
+                if (approximately_equal(t[idx2], 0)) {
+                    goto nextRoot;
+                }
+            }
+            SkASSERT(foundRoots < 3);
+            t[foundRoots++] = 0;
+        }
+nextRoot:
+        ;
+    }
     return foundRoots;
 }
 
 int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) {
 #ifdef SK_DEBUG
     // create a string mathematica understands
     // GDB set print repe 15 # if repeated digits is a bother
     //     set print elements 400 # if line doesn't fit
     char str[1024];
     sk_bzero(str, sizeof(str));
@@ skipping 124 matching lines @@
     coeff[2] = 2 * b * b + c * a;
     coeff[3] = a * b;
 }
 
 /** SkDCubic'(t) = At^2 + Bt + C, where
     A = 3(-a + 3(b - c) + d)
     B = 6(a - 2b + c)
     C = 3(b - a)
     Solve for t, keeping only those that fit between 0 < t < 1
 */
-int SkDCubic::FindExtrema(double a, double b, double c, double d, double tValues[2]) {
+int SkDCubic::FindExtrema(const double src[], double tValues[2]) {
     // we divide A,B,C by 3 to simplify
-    double A = d - a + 3*(b - c);
-    double B = 2*(a - b - b + c);
+    double a = src[0];
+    double b = src[2];
+    double c = src[4];
+    double d = src[6];
+    double A = d - a + 3 * (b - c);
+    double B = 2 * (a - b - b + c);
     double C = b - a;
 
     return SkDQuad::RootsValidT(A, B, C, tValues);
 }
 
 /*  from SkGeometry.cpp
     Looking for F' dot F'' == 0
 
     A = b - a
     B = c - 2b + a
     C = d - 3c + 3b - a
 
     F' = 3Ct^2 + 6Bt + 3A
     F'' = 6Ct + 6B
 
     F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
 */
 int SkDCubic::findMaxCurvature(double tValues[]) const {
     double coeffX[4], coeffY[4];
     int i;
     formulate_F1DotF2(&fPts[0].fX, coeffX);
     formulate_F1DotF2(&fPts[0].fY, coeffY);
     for (i = 0; i < 4; i++) {
         coeffX[i] = coeffX[i] + coeffY[i];
     }
     return RootsValidT(coeffX[0], coeffX[1], coeffX[2], coeffX[3], tValues);
 }
 
-SkDPoint SkDCubic::top(double startT, double endT, double* topT) const {
-    SkDCubic sub = subDivide(startT, endT);
-    SkDPoint topPt = sub[0];
-    *topT = startT;
-    if (topPt.fY > sub[3].fY || (topPt.fY == sub[3].fY && topPt.fX > sub[3].fX)) {
-        *topT = endT;
-        topPt = sub[3];
-    }
-    double extremeTs[2];
-    if (!sub.monotonicInY()) {
-        int roots = FindExtrema(sub[0].fY, sub[1].fY, sub[2].fY, sub[3].fY, extremeTs);
-        for (int index = 0; index < roots; ++index) {
-            double t = startT + (endT - startT) * extremeTs[index];
-            SkDPoint mid = ptAtT(t);
-            if (topPt.fY > mid.fY || (topPt.fY == mid.fY && topPt.fX > mid.fX)) {
-                *topT = t;
-                topPt = mid;
-            }
-        }
-    }
-    return topPt;
-}
-
 SkDPoint SkDCubic::ptAtT(double t) const {
     if (0 == t) {
         return fPts[0];
     }
     if (1 == t) {
         return fPts[3];
     }
     double one_t = 1 - t;
     double one_t2 = one_t * one_t;
     double a = one_t2 * one_t;
@@ skipping 160 matching lines @@
         dst.pts[4].fY = (fPts[1].fY + 2 * fPts[2].fY + fPts[3].fY) / 4;
         dst.pts[5].fX = (fPts[2].fX + fPts[3].fX) / 2;
         dst.pts[5].fY = (fPts[2].fY + fPts[3].fY) / 2;
         dst.pts[6] = fPts[3];
         return dst;
     }
     interp_cubic_coords(&fPts[0].fX, &dst.pts[0].fX, t);
     interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t);
     return dst;
 }