Implement Conics in SkCurveMeasure

src/utils/SkCurveMeasure.cpp

Index: src/utils/SkCurveMeasure.cpp
diff --git a/src/utils/SkCurveMeasure.cpp b/src/utils/SkCurveMeasure.cpp
index a82008e67e25a47460b5129a6e7f1598a701ea04..5958f4471f971ecaf7e8fcd76dd4302da2c6487e 100644
--- a/src/utils/SkCurveMeasure.cpp
+++ b/src/utils/SkCurveMeasure.cpp
@@ -11,7 +11,7 @@
 // for abs
 #include <cmath>
 
-#define UNIMPLEMENTED SkDEBUGF(("%s:%d unimplemented\n", __FILE__, __LINE__))
+#define UNIMPLEMENTED SkDEBUGFAILF("%s:%d unimplemented\n", __FILE__, __LINE__)
 
 /// Used inside SkCurveMeasure::getTime's Newton's iteration
 static inline SkPoint evaluate(const SkPoint pts[4], SkSegType segType,
@@ -65,24 +65,74 @@ static inline SkVector evaluateDerivative(const SkPoint pts[4],
 
     return tan;
 }
+
+/*
+ * Derivation of conic formulae based on parameterization from
+ * http://citeseerx.ist.psu.edu/viewdoc/
+ *   download?doi=10.1.1.44.5740&rep=rep1&type=ps
+ * referenced in SkGeometry.cpp
+ *
+ * Usage: below and in the constructor for ArcLengthIntegrator
+ *
+ * Mathematica:
+ *
+ * conic[t_] := (A*(1 - t)^2 + 2*w*B*(1 - t)*t + C*t^2)/
+ *      (1 - 2*(1 - w)*t + 2*(1 - w)*t^2)
+ *
+ * conic[0]
+ *
+ * >>> A
+ *
+ * conic[1]
+ *
+ * >>> C
+ *
+ * Simplify[Derivative[1][conic][t]]
+ *
+ * >>> (2*(C*t*(1 + t*(-1 + w)) - A*(-1 + t)*(t*(-1 + w) - w) + B*(1 - 2*t)*w))/
+ *     (1 + 2*t*(-1 + w) - 2*t^2*(-1 + w))^2
+ *
+ * HornerForm[Numerator[Simplify[Derivative[1][conic][t]]], t]
+ *
+ * >>> -2*A*w + 2*B*w + t*(-2*A + 2*C + 4*A*w - 4*B*w +
+ *               t*(2*A - 2*C - 2*A*w + 2*C*w))
+ *
+ * HornerForm[Denominator[Simplify[Derivative[1][conic][t]]], t]
+ *
+ * >>> 1 + t*(-4 + 4*w + t*(8 - 12*w + 4*w^2 +
+ *               t*(-8 + 16*w - 8*w^2 + t*(4 - 8*w + 4*w^2))))
+ *
+ */
+
 /// Used in ArcLengthIntegrator::computeLength
 static inline Sk8f evaluateDerivativeLength(const Sk8f& ts,
-                                            const Sk8f (&xCoeff)[3],
-                                            const Sk8f (&yCoeff)[3],
+                                            const Sk8f (&fXCoeff)[3],
+                                            const Sk8f (&fYCoeff)[3],
+                                            const SkScalar w,
                                             const SkSegType segType) {
     Sk8f x;
     Sk8f y;
     switch (segType) {
         case kQuad_SegType:
-            x = xCoeff[0]*ts + xCoeff[1];
-            y = yCoeff[0]*ts + yCoeff[1];
+            x = fXCoeff[0]*ts + fXCoeff[1];
+            y = fYCoeff[0]*ts + fYCoeff[1];
             break;
         case kCubic_SegType:
-            x = (xCoeff[0]*ts + xCoeff[1])*ts + xCoeff[2];
-            y = (yCoeff[0]*ts + yCoeff[1])*ts + yCoeff[2];
+            x = (fXCoeff[0]*ts + fXCoeff[1])*ts + fXCoeff[2];
+            y = (fYCoeff[0]*ts + fYCoeff[1])*ts + fYCoeff[2];
             break;
-        case kConic_SegType:
-            UNIMPLEMENTED;
+        case kConic_SegType: {
+            Sk8f xnum = (fXCoeff[0]*ts + fXCoeff[1])*ts + fXCoeff[2];
+            Sk8f ynum = (fYCoeff[0]*ts + fYCoeff[1])*ts + fYCoeff[2];
+
+            SkScalar w44 = 4 + 4*w;
+            SkScalar w484 = 4 - 8*w + 4*w*w;
+            Sk8f denom =  ts*(-8 + w44 + ts*(8 + -w44 + w484 + ts*(-2*w484
+                              + ts*(w484)))) + 1;
+
+            x = xnum / denom;
+            y = ynum / denom;
+        }
             break;
         default:
             UNIMPLEMENTED;
@@ -106,11 +156,11 @@ ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType)
             float Cy = pts[2].y();
 
             // precompute coefficients for derivative
-            xCoeff[0] = Sk8f(2*(Ax - 2*Bx + Cx));
-            xCoeff[1] = Sk8f(2*(Bx - Ax));
+            fXCoeff[0] = Sk8f(2*(Ax - 2*Bx + Cx));
+            fXCoeff[1] = Sk8f(2*(Bx - Ax));
 
-            yCoeff[0] = Sk8f(2*(Ay - 2*By + Cy));
-            yCoeff[1] = Sk8f(2*(By - Ay));
+            fYCoeff[0] = Sk8f(2*(Ay - 2*By + Cy));
+            fYCoeff[1] = Sk8f(2*(By - Ay));
         }
             break;
         case kCubic_SegType:
@@ -125,17 +175,40 @@ ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType)
             float Dy = pts[3].y();
 
             // precompute coefficients for derivative
-            xCoeff[0] = Sk8f(3*(-Ax + 3*(Bx - Cx) + Dx));
-            xCoeff[1] = Sk8f(6*(Ax - 2*Bx + Cx));
-            xCoeff[2] = Sk8f(3*(-Ax + Bx));
+            fXCoeff[0] = Sk8f(3*(-Ax + 3*(Bx - Cx) + Dx));
+            fXCoeff[1] = Sk8f(6*(Ax - 2*Bx + Cx));
+            fXCoeff[2] = Sk8f(3*(-Ax + Bx));
 
-            yCoeff[0] = Sk8f(3*(-Ay + 3*(By - Cy) + Dy));
-            yCoeff[1] = Sk8f(6*(Ay - 2*By + Cy));
-            yCoeff[2] = Sk8f(3*(-Ay + By));
+            fYCoeff[0] = Sk8f(3*(-Ay + 3*(By - Cy) + Dy));
+            fYCoeff[1] = Sk8f(6*(Ay - 2*By + Cy));
+            fYCoeff[2] = Sk8f(3*(-Ay + By));
         }
             break;
-        case kConic_SegType:
-            UNIMPLEMENTED;
+        case kConic_SegType: {
+            float Ax = pts[0].x();
+            float Bx = pts[1].x();
+            float Cx = pts[2].x();
+            float Ay = pts[0].y();
+            float By = pts[1].y();
+            float Cy = pts[2].y();
+
+            fConicW = pts[3].x();
+
+            SkScalar w = fConicW;
+
+            // precompute coefficients for derivative
+            SkScalar AwBwx = -2*(Ax*w - Bx*w);
+            SkScalar AxCx = Ax - Cx;
+            fXCoeff[0] = Sk8f(2*(AxCx - Ax*w + Cx*w));
+            fXCoeff[1] = Sk8f(-2*(AxCx + AwBwx));
+            fXCoeff[2] = Sk8f(AwBwx);
+
+            SkScalar AwBwy = -2*(Ay*w - By*w);
+            SkScalar AyCy = Ay - Cy;
+            fYCoeff[0] = Sk8f(2*(AyCy - Ay*w + Cy*w));
+            fYCoeff[1] = Sk8f(-2*(AyCy + AwBwy));
+            fYCoeff[2] = Sk8f(AwBwy);
+        }
             break;
         default:
             UNIMPLEMENTED;
@@ -148,8 +221,9 @@ ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType)
 SkScalar ArcLengthIntegrator::computeLength(SkScalar t) {
     SkScalar length = 0.0f;
 
-    Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType);
-    lengths = weights*lengths;
+    Sk8f lengths =
+        evaluateDerivativeLength(absc * t, fXCoeff, fYCoeff, fConicW, fSegType);
+    lengths = weights * lengths;
     // is it faster or more accurate to sum and then multiply or vice versa?
     lengths = lengths*(t*0.5f);
 
@@ -214,8 +288,8 @@ SkScalar SkCurveMeasure::getTime(SkScalar targetLength) {
     }
 
     SkScalar currentLength = getLength();
-
-    if (targetLength > currentLength || (SkScalarNearlyEqual(targetLength, currentLength))) {
+    if (targetLength > currentLength ||
+       (SkScalarNearlyEqual(targetLength, currentLength))) {
         return 1.0f;
     }
     if (kLine_SegType == fSegType) {