Add svg path arcto

The arcto() used by SVG in Chrome and Android is ported here, using conics
instead of cubics. The logic is a direct transposition of the WebKit code.

The attached GM includes SVG that draws the same as Skia.

R=reed@google.com
BUG=skia:3959
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1613303002

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

4 files changed, 253 insertions, 4 deletions

diff --git a/gm/arcto.cpp b/gm/arcto.cpp
new file mode 100644
index 0000000000..900c6b30ea
--- /dev/null
+++ b/gm/arcto.cpp
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "gm.h"
+#include "SkParsePath.h"
+#include "SkPath.h"
+
+/*
+The arcto test below should draw the same as this SVG:
+(Note that Skia's arcTo Direction parameter value is opposite SVG's sweep value, e.g. 0 / 1)
+
+<svg width="500" height="600">
+<path d="M 50,100 A50,50,   0,0,1, 150,200" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M100,100 A50,100,  0,0,1, 200,200" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M150,100 A50,50,  45,0,1, 250,200" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M200,100 A50,100, 45,0,1, 300,200" style="stroke:#660000; fill:none; stroke-width:2" />
+
+<path d="M150,200 A50,50,   0,1,0, 150,300" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M200,200 A50,100,  0,1,0, 200,300" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M250,200 A50,50,  45,1,0, 250,300" style="stroke:#660000; fill:none; stroke-width:2" />
+<path d="M300,200 A50,100, 45,1,0, 300,300" style="stroke:#660000; fill:none; stroke-width:2" />
+
+<path d="M250,400  A120,80 0 0,0 250,500"
+    fill="none" stroke="red" stroke-width="5" />
+
+<path d="M250,400  A120,80 0 1,1 250,500"
+    fill="none" stroke="green" stroke-width="5"/>
+
+<path d="M250,400  A120,80 0 1,0 250,500"
+    fill="none" stroke="purple" stroke-width="5"/>
+
+<path d="M250,400  A120,80 0 0,1 250,500"
+    fill="none" stroke="blue" stroke-width="5"/>
+</svg>
+ */
+
+DEF_SIMPLE_GM(arcto, canvas, 500, 600) {
+    SkPaint paint;
+    paint.setAntiAlias(true);
+    paint.setStyle(SkPaint::kStroke_Style);
+    paint.setStrokeWidth(2);
+    paint.setColor(0xFF660000);
+    canvas->scale(2, 2);
+    SkRect oval = SkRect::MakeXYWH(100, 100, 100, 100);
+    SkPath svgArc;
+
+    for (int angle = 0; angle <= 45; angle += 45) {
+       for (int oHeight = 2; oHeight >= 1; --oHeight) {
+            SkScalar ovalHeight = oval.height() / oHeight;
+            svgArc.moveTo(oval.fLeft, oval.fTop);
+            svgArc.arcTo(oval.width() / 2, ovalHeight, SkIntToScalar(angle), SkPath::kSmall_ArcSize,
+                    SkPath::kCW_Direction, oval.right(), oval.bottom());
+            canvas->drawPath(svgArc, paint);
+            svgArc.reset();
+
+            svgArc.moveTo(oval.fLeft + 100, oval.fTop + 100);
+            svgArc.arcTo(oval.width() / 2, ovalHeight, SkIntToScalar(angle), SkPath::kLarge_ArcSize,
+                    SkPath::kCCW_Direction, oval.right(), oval.bottom() + 100);
+            canvas->drawPath(svgArc, paint);
+            oval.offset(50, 0);
+            svgArc.reset();
+
+        }
+    }
+
+    paint.setStrokeWidth(5);
+    const SkColor purple = 0xFF800080;
+    const SkColor darkgreen = 0xFF008000;
+    const SkColor colors[] = { SK_ColorRED, darkgreen, purple, SK_ColorBLUE };
+    const char* arcstrs[] = {
+        "M250,400  A120,80 0 0,0 250,500",
+        "M250,400  A120,80 0 1,1 250,500",
+        "M250,400  A120,80 0 1,0 250,500",
+        "M250,400  A120,80 0 0,1 250,500"
+    };
+    int cIndex = 0;
+    for (const char* arcstr : arcstrs) {
+        SkParsePath::FromSVGString(arcstr, &svgArc);
+        paint.setColor(colors[cIndex++]);
+        canvas->drawPath(svgArc, paint);
+    }
+}
diff --git a/include/core/SkPath.h b/include/core/SkPath.h
index 6952719815..7c6fd35d5a 100644
--- a/include/core/SkPath.h
+++ b/include/core/SkPath.h
@@ -499,10 +499,12 @@ public:
         this->arcTo(p1.fX, p1.fY, p2.fX, p2.fY, radius);
     }
 
-    /** Close the current contour. If the current point is not equal to the
-        first point of the contour, a line segment is automatically added.
-    */
-    void close();
+    enum ArcSize {
+        /** the smaller of the two possible SVG arcs. */
+        kSmall_ArcSize,
+        /** the larger of the two possible SVG arcs. */
+        kLarge_ArcSize,
+    };
 
     enum Direction {
         /** clockwise direction for adding closed contours */
@@ -512,6 +514,48 @@ public:
     };
 
     /**
+     *  Append an elliptical arc from the current point in the format used by SVG.
+     *  The center of the ellipse is computed to satisfy the constraints below.
+     *
+     *  @param rx,ry The radii in the x and y directions respectively.
+     *  @param xAxisRotate The angle in degrees relative to the x-axis.
+     *  @param largeArc Determines whether the smallest or largest arc possible
+     *         is drawn.
+     *  @param sweep Determines if the arc should be swept in an anti-clockwise or
+     *         clockwise direction. Note that this enum value is opposite the SVG
+     *         arc sweep value.
+     *  @param x,y The destination coordinates.
+     */
+    void arcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, ArcSize largeArc,
+               Direction sweep, SkScalar x, SkScalar y);
+
+    void arcTo(const SkPoint r, SkScalar xAxisRotate, ArcSize largeArc, Direction sweep,
+               const SkPoint xy) {
+        this->arcTo(r.fX, r.fY, xAxisRotate, largeArc, sweep, xy.fX, xy.fY);
+    }
+
+    /** Same as arcTo format used by SVG, but the destination coordinate is relative to the
+     *  last point on this contour. If there is no previous point, then a
+     *  moveTo(0,0) is inserted automatically.
+     *
+     *  @param rx,ry The radii in the x and y directions respectively.
+     *  @param xAxisRotate The angle in degrees relative to the x-axis.
+     *  @param largeArc Determines whether the smallest or largest arc possible
+     *         is drawn.
+     *  @param sweep Determines if the arc should be swept in an anti-clockwise or
+     *         clockwise direction. Note that this enum value is opposite the SVG
+     *         arc sweep value.
+     *  @param dx,dy The destination coordinates relative to the last point.
+     */
+    void rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, ArcSize largeArc,
+                Direction sweep, SkScalar dx, SkScalar dy);
+
+    /** Close the current contour. If the current point is not equal to the
+        first point of the contour, a line segment is automatically added.
+    */
+    void close();
+
+    /**
      *  Returns whether or not a fill type is inverted
      *
      *  kWinding_FillType        -> false
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index c77a25b4aa..40ca50b5ca 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -1257,6 +1257,113 @@ void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
     }
 }
 
+// This converts the SVG arc to conics.
+// Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
+// Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic()
+// See also SVG implementation notes:
+// http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
+// Note that arcSweep bool value is flipped from the original implementation.
+void SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge,
+                   SkPath::Direction arcSweep, SkScalar x, SkScalar y) {
+    SkPoint srcPts[2];
+    this->getLastPt(&srcPts[0]);
+    // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto")
+    // joining the endpoints.
+    // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
+    if (!rx || !ry) {
+        return;
+    }
+    // If the current point and target point for the arc are identical, it should be treated as a
+    // zero length path. This ensures continuity in animations.
+    srcPts[1].set(x, y);
+    if (srcPts[0] == srcPts[1]) {
+        return;
+    }
+    rx = SkScalarAbs(rx);
+    ry = SkScalarAbs(ry);
+    SkVector midPointDistance = srcPts[0] - srcPts[1];
+    midPointDistance *= 0.5f;
+
+    SkMatrix pointTransform;
+    pointTransform.setRotate(-angle);
+
+    SkPoint transformedMidPoint;
+    pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1);
+    SkScalar squareRx = rx * rx;
+    SkScalar squareRy = ry * ry;
+    SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX;
+    SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY;
+
+    // Check if the radii are big enough to draw the arc, scale radii if not.
+    // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
+    SkScalar radiiScale = squareX / squareRx + squareY / squareRy;
+    if (radiiScale > 1) {
+        radiiScale = SkScalarSqrt(radiiScale);
+        rx *= radiiScale;
+        ry *= radiiScale;
+    }
+
+    pointTransform.setScale(1 / rx, 1 / ry);
+    pointTransform.preRotate(-angle);
+
+    SkPoint unitPts[2];
+    pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts));
+    SkVector delta = unitPts[1] - unitPts[0];
+
+    SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY;
+    SkScalar scaleFactorSquared = SkTMax(1 / d - 0.25f, 0.f);
+
+    SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared);
+    if (SkToBool(arcSweep) != SkToBool(arcLarge)) {  // flipped from the original implementation
+        scaleFactor = -scaleFactor;
+    }
+    delta.scale(scaleFactor);
+    SkPoint centerPoint = unitPts[0] + unitPts[1];
+    centerPoint *= 0.5f;
+    centerPoint.offset(-delta.fY, delta.fX);
+    unitPts[0] -= centerPoint;
+    unitPts[1] -= centerPoint;
+    SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX);
+    SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX);
+    SkScalar thetaArc = theta2 - theta1;
+    if (thetaArc < 0 && !arcSweep) {  // arcSweep flipped from the original implementation
+        thetaArc += SK_ScalarPI * 2;
+    } else if (thetaArc > 0 && arcSweep) {  // arcSweep flipped from the original implementation
+        thetaArc -= SK_ScalarPI * 2;
+    }
+    pointTransform.setRotate(angle);
+    pointTransform.preScale(rx, ry);
+
+    int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (SK_ScalarPI / 2)));
+    SkScalar thetaWidth = thetaArc / segments;
+    SkScalar t = SkScalarTan(0.5f * thetaWidth);
+    if (!SkScalarIsFinite(t)) {
+        return;
+    }
+    SkScalar startTheta = theta1;
+    SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf);
+    for (int i = 0; i < segments; ++i) {
+        SkScalar endTheta = startTheta + thetaWidth;
+        SkScalar cosEndTheta, sinEndTheta = SkScalarSinCos(endTheta, &cosEndTheta);
+
+        unitPts[1].set(cosEndTheta, sinEndTheta);
+        unitPts[1] += centerPoint;
+        unitPts[0] = unitPts[1];
+        unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta);
+        SkPoint mapped[2];
+        pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts));
+        this->conicTo(mapped[0], mapped[1], w);
+        startTheta = endTheta;
+    }
+}
+
+void SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc,
+                    SkPath::Direction sweep, SkScalar dx, SkScalar dy) {
+    SkPoint currentPoint;
+    this->getLastPt(&currentPoint);
+    this->arcTo(rx, ry, xAxisRotate, largeArc, sweep, currentPoint.fX + dx, currentPoint.fY + dy);
+}
+
 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
     if (oval.isEmpty() || 0 == sweepAngle) {
         return;
diff --git a/src/utils/SkParsePath.cpp b/src/utils/SkParsePath.cpp
index 3eb9e1ef79..c0f39aa06f 100644
--- a/src/utils/SkParsePath.cpp
+++ b/src/utils/SkParsePath.cpp
@@ -64,6 +64,7 @@ static const char* find_scalar(const char str[], SkScalar* value,
     if (isRelative) {
         *value += relative;
     }
+    str = skip_sep(str);
     return str;
 }
 
@@ -156,6 +157,17 @@ bool SkParsePath::FromSVGString(const char data[], SkPath* result) {
                 lastc = points[0];
                 c = points[1];
                 break;
+            case 'A': {
+                SkPoint radii;
+                data = find_points(data, &radii, 1, false, nullptr);
+                SkScalar angle, largeArc, sweep;
+                data = find_scalar(data, &angle, false, 0);
+                data = find_scalar(data, &largeArc, false, 0);
+                data = find_scalar(data, &sweep, false, 0);
+                data = find_points(data, &points[0], 1, relative, &c);
+                path.arcTo(radii, angle, (SkPath::ArcSize) SkToBool(largeArc),
+                        (SkPath::Direction) !SkToBool(sweep), points[0]);
+                } break;
             case 'Z':
                 path.close();
 #if 0   // !!! still a bug?