use conics for arcTo

guarded by SK_SUPPORT_LEGACY_ARCTO_QUADS

BUG=skia:

Review URL: https://codereview.chromium.org/892703002

3 files changed, 149 insertions, 22 deletions

diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index ac02afc633..7896b0db40 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -1555,3 +1555,89 @@ SkScalar SkConic::TransformW(const SkPoint pts[], SkScalar w,
     w = SkScalarSqrt((w1 * w1) / (w0 * w2));
     return w;
 }
+
+int SkConic::BuildUnitArc(const SkVector& uStart, const SkVector& uStop, SkRotationDirection dir,
+                          const SkMatrix* userMatrix, SkConic dst[kMaxConicsForArc]) {
+    // rotate by x,y so that uStart is (1.0)
+    SkScalar x = SkPoint::DotProduct(uStart, uStop);
+    SkScalar y = SkPoint::CrossProduct(uStart, uStop);
+
+    SkScalar absY = SkScalarAbs(y);
+
+    // check for (effectively) coincident vectors
+    // this can happen if our angle is nearly 0 or nearly 180 (y == 0)
+    // ... we use the dot-prod to distinguish between 0 and 180 (x > 0)
+    if (absY <= SK_ScalarNearlyZero && x > 0 && ((y >= 0 && kCW_SkRotationDirection == dir) ||
+                                                 (y <= 0 && kCCW_SkRotationDirection == dir))) {
+        return 0;
+    }
+
+    if (dir == kCCW_SkRotationDirection) {
+        y = -y;
+    }
+
+    // We decide to use 1-conic per quadrant of a circle. What quadrant does [xy] lie in?
+    //      0 == [0  .. 90)
+    //      1 == [90 ..180)
+    //      2 == [180..270)
+    //      3 == [270..360)
+    //
+    int quadrant = 0;
+    if (0 == y) {
+        quadrant = 2;        // 180
+        SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero);
+    } else if (0 == x) {
+        SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero);
+        quadrant = y > 0 ? 1 : 3; // 90 : 270
+    } else {
+        if (y < 0) {
+            quadrant += 2;
+        }
+        if ((x < 0) != (y < 0)) {
+            quadrant += 1;
+        }
+    }
+
+    const SkPoint quadrantPts[] = {
+        { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }
+    };
+    const SkScalar quadrantWeight = SK_ScalarRoot2Over2;
+
+    int conicCount = quadrant;
+    for (int i = 0; i < conicCount; ++i) {
+        dst[i].set(&quadrantPts[i * 2], quadrantWeight);
+    }
+
+    // Now compute any remaing (sub-90-degree) arc for the last conic
+    const SkPoint finalP = { x, y };
+    const SkPoint& lastQ = quadrantPts[quadrant * 2];  // will already be a unit-vector
+    const SkScalar dot = SkVector::DotProduct(lastQ, finalP);
+    SkASSERT(0 <= dot && dot <= SK_Scalar1);
+
+    if (dot < 1 - SK_ScalarNearlyZero) {
+        SkVector offCurve = { lastQ.x() + x, lastQ.y() + y };
+        // compute the bisector vector, and then rescale to be the off-curve point.
+        // we compute its length from cos(theta/2) = length / 1, using half-angle identity we get
+        // length = sqrt(2 / (1 + cos(theta)). We already have cos() when to computed the dot.
+        // This is nice, since our computed weight is cos(theta/2) as well!
+        //
+        const SkScalar cosThetaOver2 = SkScalarSqrt((1 + dot) / 2);
+        offCurve.setLength(SkScalarInvert(cosThetaOver2));
+        dst[conicCount].set(lastQ, offCurve, finalP, cosThetaOver2);
+        conicCount += 1;
+    }
+
+    // now handle counter-clockwise and the initial unitStart rotation
+    SkMatrix    matrix;
+    matrix.setSinCos(uStart.fY, uStart.fX);
+    if (dir == kCCW_SkRotationDirection) {
+        matrix.preScale(SK_Scalar1, -SK_Scalar1);
+    }
+    if (userMatrix) {
+        matrix.postConcat(*userMatrix);
+    }
+    for (int i = 0; i < conicCount; ++i) {
+        matrix.mapPoints(dst[i].fPts, 3);
+    }
+    return conicCount;
+}
diff --git a/src/core/SkGeometry.h b/src/core/SkGeometry.h
index b14a2ddb98..ad4bffcb62 100644
--- a/src/core/SkGeometry.h
+++ b/src/core/SkGeometry.h
@@ -226,7 +226,6 @@ enum SkRotationDirection {
 int SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop,
                    SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]);
 
-// experimental
 struct SkConic {
     SkConic() {}
     SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
@@ -248,6 +247,13 @@ struct SkConic {
         fW = w;
     }
 
+    void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
+        fPts[0] = p0;
+        fPts[1] = p1;
+        fPts[2] = p2;
+        fW = w;
+    }
+
     /**
      *  Given a t-value [0...1] return its position and/or tangent.
      *  If pos is not null, return its position at the t-value.
@@ -292,6 +298,12 @@ struct SkConic {
     bool findMaxCurvature(SkScalar* t) const;
 
     static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
+
+    enum {
+        kMaxConicsForArc = 5
+    };
+    static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
+                            const SkMatrix*, SkConic conics[kMaxConicsForArc]);
 };
 
 #include "SkTemplates.h"
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 195424e7c0..4f5fffb7dd 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -915,23 +915,22 @@ static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar
     return false;
 }
 
-static int build_arc_points(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
-                            SkPoint pts[kSkBuildQuadArcStorage]) {
-    SkVector start, stop;
-
-    start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX);
-    stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle),
-                             &stop.fX);
+// Return the unit vectors pointing at the start/stop points for the given start/sweep angles
+//
+static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
+                                   SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
+    startV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &startV->fX);
+    stopV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), &stopV->fX);
 
     /*  If the sweep angle is nearly (but less than) 360, then due to precision
-        loss in radians-conversion and/or sin/cos, we may end up with coincident
-        vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
-        of drawing a nearly complete circle (good).
-             e.g. canvas.drawArc(0, 359.99, ...)
-             -vs- canvas.drawArc(0, 359.9, ...)
-        We try to detect this edge case, and tweak the stop vector
+     loss in radians-conversion and/or sin/cos, we may end up with coincident
+     vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
+     of drawing a nearly complete circle (good).
+     e.g. canvas.drawArc(0, 359.99, ...)
+     -vs- canvas.drawArc(0, 359.9, ...)
+     We try to detect this edge case, and tweak the stop vector
      */
-    if (start == stop) {
+    if (*startV == *stopV) {
         SkScalar sw = SkScalarAbs(sweepAngle);
         if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
             SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
@@ -940,21 +939,34 @@ static int build_arc_points(const SkRect& oval, SkScalar startAngle, SkScalar sw
             // not sure how much will be enough, so we use a loop
             do {
                 stopRad -= deltaRad;
-                stop.fY = SkScalarSinCos(stopRad, &stop.fX);
-            } while (start == stop);
+                stopV->fY = SkScalarSinCos(stopRad, &stopV->fX);
+            } while (*startV == *stopV);
         }
     }
+    *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
+}
+
+#ifdef SK_SUPPORT_LEGACY_ARCTO_QUADS
+static int build_arc_points(const SkRect& oval, const SkVector& start, const SkVector& stop,
+                            SkRotationDirection dir, SkPoint pts[kSkBuildQuadArcStorage]) {
+    SkMatrix    matrix;
 
+    matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
+    matrix.postTranslate(oval.centerX(), oval.centerY());
+
+    return SkBuildQuadArc(start, stop, dir, &matrix, pts);
+}
+#else
+static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
+                            SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc]) {
     SkMatrix    matrix;
 
     matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
     matrix.postTranslate(oval.centerX(), oval.centerY());
 
-    return SkBuildQuadArc(start, stop,
-                          sweepAngle > 0 ? kCW_SkRotationDirection :
-                                           kCCW_SkRotationDirection,
-                          &matrix, pts);
+    return SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
 }
+#endif
 
 void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
                           Direction dir) {
@@ -1320,8 +1332,13 @@ void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
         return;
     }
 
+    SkVector startV, stopV;
+    SkRotationDirection dir;
+    angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
+
+#ifdef SK_SUPPORT_LEGACY_ARCTO_QUADS
     SkPoint pts[kSkBuildQuadArcStorage];
-    int count = build_arc_points(oval, startAngle, sweepAngle, pts);
+    int count = build_arc_points(oval, startV, stopV, dir, pts);
     SkASSERT((count & 1) == 1);
 
     this->incReserve(count);
@@ -1329,6 +1346,18 @@ void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
     for (int i = 1; i < count; i += 2) {
         this->quadTo(pts[i], pts[i+1]);
     }
+#else
+    SkConic conics[SkConic::kMaxConicsForArc];
+    int count = build_arc_conics(oval, startV, stopV, dir, conics);
+    if (count) {
+        this->incReserve(count * 2 + 1);
+        const SkPoint& pt = conics[0].fPts[0];
+        forceMoveTo ? this->moveTo(pt) : this->lineTo(pt);
+        for (int i = 0; i < count; ++i) {
+            this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
+        }
+    }
+#endif
 }
 
 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {