working on initial winding for cubics

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"
+#include "SkPathOpsCurve.h"
 #include "SkPathOpsLine.h"
 #include "SkPathOpsQuad.h"
 #include "SkPathOpsRect.h"
 #include "SkTSort.h"
 
 const int SkDCubic::gPrecisionUnit = 256;  // FIXME: test different values in test framework
 
 // give up when changing t no longer moves point
 // also, copy point rather than recompute it when it does change
 double SkDCubic::binarySearch(double min, double max, double axisIntercept,
@@ skipping 46 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() const {
-    double sum = (fPts[0].fX - fPts[3].fX) * (fPts[0].fY + fPts[3].fY);
-    for (int idx = 0; idx < 3; ++idx) {
-        sum += (fPts[idx + 1].fX - fPts[idx].fX) * (fPts[idx + 1].fY + fPts[idx].fY);
+bool SkDCubic::clockwise(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();
     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);
+}
+
 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 84 matching lines @@
             fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY), fPts[3].fX), fPts[3].fY);
     largest = SkTMax(largest, -tiniest);
     double distance = lineParameters.controlPtDistance(*this, 1);
     if (!approximately_zero_when_compared_to(distance, largest)) {
         return false;
     }
     distance = lineParameters.controlPtDistance(*this, 2);
     return approximately_zero_when_compared_to(distance, largest);
 }
 
-bool SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
+bool SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t, CubicType* resultType) {
     SkScalar d[3];
     SkCubicType cubicType = SkClassifyCubic(pointsPtr, d);
     if (cubicType == kLoop_SkCubicType) {
         // crib code from gpu path utils that finds t values where loop self-intersects
         // use it to find mid of t values which should be a friendly place to chop
         SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
         SkScalar ls = d[1] - tempSqrt;
         SkScalar lt = 2.f * d[0];
         SkScalar ms = d[1] + tempSqrt;
         SkScalar mt = 2.f * d[0];
         if (between(0, ls, lt) || between(0, ms, mt)) {
             ls = ls / lt;
             ms = ms / mt;
             SkScalar smaller = SkTMax(0.f, SkTMin(ls, ms));
             SkScalar larger = SkTMin(1.f, SkTMax(ls, ms));
             *t = (smaller + larger) / 2;
+            *resultType = kSplitAtLoop_SkDCubicType;
             return *t > 0 && *t < 1;
         }
     } else if (kSerpentine_SkCubicType == cubicType || kCusp_SkCubicType == cubicType) {
         SkDCubic cubic;
         cubic.set(pointsPtr);
         double inflectionTs[2];
         int infTCount = cubic.findInflections(inflectionTs);
         if (infTCount == 2) {
             double maxCurvature[3];
             int roots = cubic.findMaxCurvature(maxCurvature);
+#if DEBUG_CUBIC_SPLIT
+            SkDebugf("%s\n", __FUNCTION__);
+            cubic.dump();
+            for (int index = 0; index < infTCount; ++index) {
+                SkDebugf("inflectionsTs[%d]=%1.9g ", index, inflectionTs[index]);
+                SkDPoint pt = cubic.ptAtT(inflectionTs[index]);
+                SkDVector dPt = cubic.dxdyAtT(inflectionTs[index]);
+                SkDLine perp = {{pt - dPt, pt + dPt}};
+                perp.dump();
+            }
+            for (int index = 0; index < roots; ++index) {
+                SkDebugf("maxCurvature[%d]=%1.9g ", index, maxCurvature[index]);
+                SkDPoint pt = cubic.ptAtT(maxCurvature[index]);
+                SkDVector dPt = cubic.dxdyAtT(maxCurvature[index]);
+                SkDLine perp = {{pt - dPt, pt + dPt}};
+                perp.dump();
+            }
+#endif
             for (int index = 0; index < roots; ++index) {
                 if (between(inflectionTs[0], maxCurvature[index], inflectionTs[1])) {
                     *t = maxCurvature[index];
+                    *resultType = kSplitAtMaxCurvature_SkDCubicType;
                     return true;
                 }
             }
         } else if (infTCount == 1) {
             *t = inflectionTs[0];
+            *resultType = kSplitAtInflection_SkDCubicType;
             return *t > 0 && *t < 1;
         }
-        return false;
     }
     return false;
 }
 
 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);
 }
 
 void SkDCubic::otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const {
@@ skipping 202 matching lines @@
     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) const {
+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];
@@ skipping 167 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;
 }