1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "VectorDrawableUtils.h"
18
19#include "PathParser.h"
20
21#include <math.h>
22#include <utils/Log.h>
23
24namespace android {
25namespace uirenderer {
26
27class PathResolver {
28public:
29    float currentX = 0;
30    float currentY = 0;
31    float ctrlPointX = 0;
32    float ctrlPointY = 0;
33    float currentSegmentStartX = 0;
34    float currentSegmentStartY = 0;
35    void addCommand(SkPath* outPath, char previousCmd,
36            char cmd, const std::vector<float>* points, size_t start, size_t end);
37};
38
39bool VectorDrawableUtils::canMorph(const PathData& morphFrom, const PathData& morphTo) {
40    if (morphFrom.verbs.size() != morphTo.verbs.size()) {
41        return false;
42    }
43
44    for (unsigned int i = 0; i < morphFrom.verbs.size(); i++) {
45        if (morphFrom.verbs[i] != morphTo.verbs[i]
46                ||  morphFrom.verbSizes[i] != morphTo.verbSizes[i]) {
47            return false;
48        }
49    }
50    return true;
51}
52
53bool VectorDrawableUtils::interpolatePathData(PathData* outData, const PathData& morphFrom,
54        const PathData& morphTo, float fraction) {
55    if (!canMorph(morphFrom, morphTo)) {
56        return false;
57    }
58    interpolatePaths(outData, morphFrom, morphTo, fraction);
59    return true;
60}
61
62 /**
63 * Convert an array of PathVerb to Path.
64 */
65void VectorDrawableUtils::verbsToPath(SkPath* outPath, const PathData& data) {
66    PathResolver resolver;
67    char previousCommand = 'm';
68    size_t start = 0;
69    outPath->reset();
70    for (unsigned int i = 0; i < data.verbs.size(); i++) {
71        size_t verbSize = data.verbSizes[i];
72        resolver.addCommand(outPath, previousCommand, data.verbs[i], &data.points, start,
73                start + verbSize);
74        previousCommand = data.verbs[i];
75        start += verbSize;
76    }
77}
78
79/**
80 * The current PathVerb will be interpolated between the
81 * <code>nodeFrom</code> and <code>nodeTo</code> according to the
82 * <code>fraction</code>.
83 *
84 * @param nodeFrom The start value as a PathVerb.
85 * @param nodeTo The end value as a PathVerb
86 * @param fraction The fraction to interpolate.
87 */
88void VectorDrawableUtils::interpolatePaths(PathData* outData,
89        const PathData& from, const PathData& to, float fraction) {
90    outData->points.resize(from.points.size());
91    outData->verbSizes = from.verbSizes;
92    outData->verbs = from.verbs;
93
94    for (size_t i = 0; i < from.points.size(); i++) {
95        outData->points[i] = from.points[i] * (1 - fraction) + to.points[i] * fraction;
96    }
97}
98
99/**
100 * Converts an arc to cubic Bezier segments and records them in p.
101 *
102 * @param p The target for the cubic Bezier segments
103 * @param cx The x coordinate center of the ellipse
104 * @param cy The y coordinate center of the ellipse
105 * @param a The radius of the ellipse in the horizontal direction
106 * @param b The radius of the ellipse in the vertical direction
107 * @param e1x E(eta1) x coordinate of the starting point of the arc
108 * @param e1y E(eta2) y coordinate of the starting point of the arc
109 * @param theta The angle that the ellipse bounding rectangle makes with horizontal plane
110 * @param start The start angle of the arc on the ellipse
111 * @param sweep The angle (positive or negative) of the sweep of the arc on the ellipse
112 */
113static void arcToBezier(SkPath* p,
114        double cx,
115        double cy,
116        double a,
117        double b,
118        double e1x,
119        double e1y,
120        double theta,
121        double start,
122        double sweep) {
123    // Taken from equations at: http://spaceroots.org/documents/ellipse/node8.html
124    // and http://www.spaceroots.org/documents/ellipse/node22.html
125
126    // Maximum of 45 degrees per cubic Bezier segment
127    int numSegments = ceil(fabs(sweep * 4 / M_PI));
128
129    double eta1 = start;
130    double cosTheta = cos(theta);
131    double sinTheta = sin(theta);
132    double cosEta1 = cos(eta1);
133    double sinEta1 = sin(eta1);
134    double ep1x = (-a * cosTheta * sinEta1) - (b * sinTheta * cosEta1);
135    double ep1y = (-a * sinTheta * sinEta1) + (b * cosTheta * cosEta1);
136
137    double anglePerSegment = sweep / numSegments;
138    for (int i = 0; i < numSegments; i++) {
139        double eta2 = eta1 + anglePerSegment;
140        double sinEta2 = sin(eta2);
141        double cosEta2 = cos(eta2);
142        double e2x = cx + (a * cosTheta * cosEta2) - (b * sinTheta * sinEta2);
143        double e2y = cy + (a * sinTheta * cosEta2) + (b * cosTheta * sinEta2);
144        double ep2x = -a * cosTheta * sinEta2 - b * sinTheta * cosEta2;
145        double ep2y = -a * sinTheta * sinEta2 + b * cosTheta * cosEta2;
146        double tanDiff2 = tan((eta2 - eta1) / 2);
147        double alpha =
148                sin(eta2 - eta1) * (sqrt(4 + (3 * tanDiff2 * tanDiff2)) - 1) / 3;
149        double q1x = e1x + alpha * ep1x;
150        double q1y = e1y + alpha * ep1y;
151        double q2x = e2x - alpha * ep2x;
152        double q2y = e2y - alpha * ep2y;
153
154        p->cubicTo((float) q1x,
155                (float) q1y,
156                (float) q2x,
157                (float) q2y,
158                (float) e2x,
159                (float) e2y);
160        eta1 = eta2;
161        e1x = e2x;
162        e1y = e2y;
163        ep1x = ep2x;
164        ep1y = ep2y;
165    }
166}
167
168inline double toRadians(float theta) { return theta * M_PI / 180;}
169
170static void drawArc(SkPath* p,
171        float x0,
172        float y0,
173        float x1,
174        float y1,
175        float a,
176        float b,
177        float theta,
178        bool isMoreThanHalf,
179        bool isPositiveArc) {
180
181    /* Convert rotation angle from degrees to radians */
182    double thetaD = toRadians(theta);
183    /* Pre-compute rotation matrix entries */
184    double cosTheta = cos(thetaD);
185    double sinTheta = sin(thetaD);
186    /* Transform (x0, y0) and (x1, y1) into unit space */
187    /* using (inverse) rotation, followed by (inverse) scale */
188    double x0p = (x0 * cosTheta + y0 * sinTheta) / a;
189    double y0p = (-x0 * sinTheta + y0 * cosTheta) / b;
190    double x1p = (x1 * cosTheta + y1 * sinTheta) / a;
191    double y1p = (-x1 * sinTheta + y1 * cosTheta) / b;
192
193    /* Compute differences and averages */
194    double dx = x0p - x1p;
195    double dy = y0p - y1p;
196    double xm = (x0p + x1p) / 2;
197    double ym = (y0p + y1p) / 2;
198    /* Solve for intersecting unit circles */
199    double dsq = dx * dx + dy * dy;
200    if (dsq == 0.0) {
201        ALOGW("Points are coincident");
202        return; /* Points are coincident */
203    }
204    double disc = 1.0 / dsq - 1.0 / 4.0;
205    if (disc < 0.0) {
206        ALOGW("Points are too far apart %f", dsq);
207        float adjust = (float) (sqrt(dsq) / 1.99999);
208        drawArc(p, x0, y0, x1, y1, a * adjust,
209                b * adjust, theta, isMoreThanHalf, isPositiveArc);
210        return; /* Points are too far apart */
211    }
212    double s = sqrt(disc);
213    double sdx = s * dx;
214    double sdy = s * dy;
215    double cx;
216    double cy;
217    if (isMoreThanHalf == isPositiveArc) {
218        cx = xm - sdy;
219        cy = ym + sdx;
220    } else {
221        cx = xm + sdy;
222        cy = ym - sdx;
223    }
224
225    double eta0 = atan2((y0p - cy), (x0p - cx));
226
227    double eta1 = atan2((y1p - cy), (x1p - cx));
228
229    double sweep = (eta1 - eta0);
230    if (isPositiveArc != (sweep >= 0)) {
231        if (sweep > 0) {
232            sweep -= 2 * M_PI;
233        } else {
234            sweep += 2 * M_PI;
235        }
236    }
237
238    cx *= a;
239    cy *= b;
240    double tcx = cx;
241    cx = cx * cosTheta - cy * sinTheta;
242    cy = tcx * sinTheta + cy * cosTheta;
243
244    arcToBezier(p, cx, cy, a, b, x0, y0, thetaD, eta0, sweep);
245}
246
247
248
249// Use the given verb, and points in the range [start, end) to insert a command into the SkPath.
250void PathResolver::addCommand(SkPath* outPath, char previousCmd,
251        char cmd, const std::vector<float>* points, size_t start, size_t end) {
252
253    int incr = 2;
254    float reflectiveCtrlPointX;
255    float reflectiveCtrlPointY;
256
257    switch (cmd) {
258    case 'z':
259    case 'Z':
260        outPath->close();
261        // Path is closed here, but we need to move the pen to the
262        // closed position. So we cache the segment's starting position,
263        // and restore it here.
264        currentX = currentSegmentStartX;
265        currentY = currentSegmentStartY;
266        ctrlPointX = currentSegmentStartX;
267        ctrlPointY = currentSegmentStartY;
268        outPath->moveTo(currentX, currentY);
269        break;
270    case 'm':
271    case 'M':
272    case 'l':
273    case 'L':
274    case 't':
275    case 'T':
276        incr = 2;
277        break;
278    case 'h':
279    case 'H':
280    case 'v':
281    case 'V':
282        incr = 1;
283        break;
284    case 'c':
285    case 'C':
286        incr = 6;
287        break;
288    case 's':
289    case 'S':
290    case 'q':
291    case 'Q':
292        incr = 4;
293        break;
294    case 'a':
295    case 'A':
296        incr = 7;
297        break;
298    }
299
300    for (unsigned int k = start; k < end; k += incr) {
301        switch (cmd) {
302        case 'm': // moveto - Start a new sub-path (relative)
303            currentX += points->at(k + 0);
304            currentY += points->at(k + 1);
305            if (k > start) {
306                // According to the spec, if a moveto is followed by multiple
307                // pairs of coordinates, the subsequent pairs are treated as
308                // implicit lineto commands.
309                outPath->rLineTo(points->at(k + 0), points->at(k + 1));
310            } else {
311                outPath->rMoveTo(points->at(k + 0), points->at(k + 1));
312                currentSegmentStartX = currentX;
313                currentSegmentStartY = currentY;
314            }
315            break;
316        case 'M': // moveto - Start a new sub-path
317            currentX = points->at(k + 0);
318            currentY = points->at(k + 1);
319            if (k > start) {
320                // According to the spec, if a moveto is followed by multiple
321                // pairs of coordinates, the subsequent pairs are treated as
322                // implicit lineto commands.
323                outPath->lineTo(points->at(k + 0), points->at(k + 1));
324            } else {
325                outPath->moveTo(points->at(k + 0), points->at(k + 1));
326                currentSegmentStartX = currentX;
327                currentSegmentStartY = currentY;
328            }
329            break;
330        case 'l': // lineto - Draw a line from the current point (relative)
331            outPath->rLineTo(points->at(k + 0), points->at(k + 1));
332            currentX += points->at(k + 0);
333            currentY += points->at(k + 1);
334            break;
335        case 'L': // lineto - Draw a line from the current point
336            outPath->lineTo(points->at(k + 0), points->at(k + 1));
337            currentX = points->at(k + 0);
338            currentY = points->at(k + 1);
339            break;
340        case 'h': // horizontal lineto - Draws a horizontal line (relative)
341            outPath->rLineTo(points->at(k + 0), 0);
342            currentX += points->at(k + 0);
343            break;
344        case 'H': // horizontal lineto - Draws a horizontal line
345            outPath->lineTo(points->at(k + 0), currentY);
346            currentX = points->at(k + 0);
347            break;
348        case 'v': // vertical lineto - Draws a vertical line from the current point (r)
349            outPath->rLineTo(0, points->at(k + 0));
350            currentY += points->at(k + 0);
351            break;
352        case 'V': // vertical lineto - Draws a vertical line from the current point
353            outPath->lineTo(currentX, points->at(k + 0));
354            currentY = points->at(k + 0);
355            break;
356        case 'c': // curveto - Draws a cubic Bézier curve (relative)
357            outPath->rCubicTo(points->at(k + 0), points->at(k + 1), points->at(k + 2), points->at(k + 3),
358                    points->at(k + 4), points->at(k + 5));
359
360            ctrlPointX = currentX + points->at(k + 2);
361            ctrlPointY = currentY + points->at(k + 3);
362            currentX += points->at(k + 4);
363            currentY += points->at(k + 5);
364
365            break;
366        case 'C': // curveto - Draws a cubic Bézier curve
367            outPath->cubicTo(points->at(k + 0), points->at(k + 1), points->at(k + 2), points->at(k + 3),
368                    points->at(k + 4), points->at(k + 5));
369            currentX = points->at(k + 4);
370            currentY = points->at(k + 5);
371            ctrlPointX = points->at(k + 2);
372            ctrlPointY = points->at(k + 3);
373            break;
374        case 's': // smooth curveto - Draws a cubic Bézier curve (reflective cp)
375            reflectiveCtrlPointX = 0;
376            reflectiveCtrlPointY = 0;
377            if (previousCmd == 'c' || previousCmd == 's'
378                    || previousCmd == 'C' || previousCmd == 'S') {
379                reflectiveCtrlPointX = currentX - ctrlPointX;
380                reflectiveCtrlPointY = currentY - ctrlPointY;
381            }
382            outPath->rCubicTo(reflectiveCtrlPointX, reflectiveCtrlPointY,
383                    points->at(k + 0), points->at(k + 1),
384                    points->at(k + 2), points->at(k + 3));
385            ctrlPointX = currentX + points->at(k + 0);
386            ctrlPointY = currentY + points->at(k + 1);
387            currentX += points->at(k + 2);
388            currentY += points->at(k + 3);
389            break;
390        case 'S': // shorthand/smooth curveto Draws a cubic Bézier curve(reflective cp)
391            reflectiveCtrlPointX = currentX;
392            reflectiveCtrlPointY = currentY;
393            if (previousCmd == 'c' || previousCmd == 's'
394                    || previousCmd == 'C' || previousCmd == 'S') {
395                reflectiveCtrlPointX = 2 * currentX - ctrlPointX;
396                reflectiveCtrlPointY = 2 * currentY - ctrlPointY;
397            }
398            outPath->cubicTo(reflectiveCtrlPointX, reflectiveCtrlPointY,
399                    points->at(k + 0), points->at(k + 1), points->at(k + 2), points->at(k + 3));
400            ctrlPointX = points->at(k + 0);
401            ctrlPointY = points->at(k + 1);
402            currentX = points->at(k + 2);
403            currentY = points->at(k + 3);
404            break;
405        case 'q': // Draws a quadratic Bézier (relative)
406            outPath->rQuadTo(points->at(k + 0), points->at(k + 1), points->at(k + 2), points->at(k + 3));
407            ctrlPointX = currentX + points->at(k + 0);
408            ctrlPointY = currentY + points->at(k + 1);
409            currentX += points->at(k + 2);
410            currentY += points->at(k + 3);
411            break;
412        case 'Q': // Draws a quadratic Bézier
413            outPath->quadTo(points->at(k + 0), points->at(k + 1), points->at(k + 2), points->at(k + 3));
414            ctrlPointX = points->at(k + 0);
415            ctrlPointY = points->at(k + 1);
416            currentX = points->at(k + 2);
417            currentY = points->at(k + 3);
418            break;
419        case 't': // Draws a quadratic Bézier curve(reflective control point)(relative)
420            reflectiveCtrlPointX = 0;
421            reflectiveCtrlPointY = 0;
422            if (previousCmd == 'q' || previousCmd == 't'
423                    || previousCmd == 'Q' || previousCmd == 'T') {
424                reflectiveCtrlPointX = currentX - ctrlPointX;
425                reflectiveCtrlPointY = currentY - ctrlPointY;
426            }
427            outPath->rQuadTo(reflectiveCtrlPointX, reflectiveCtrlPointY,
428                    points->at(k + 0), points->at(k + 1));
429            ctrlPointX = currentX + reflectiveCtrlPointX;
430            ctrlPointY = currentY + reflectiveCtrlPointY;
431            currentX += points->at(k + 0);
432            currentY += points->at(k + 1);
433            break;
434        case 'T': // Draws a quadratic Bézier curve (reflective control point)
435            reflectiveCtrlPointX = currentX;
436            reflectiveCtrlPointY = currentY;
437            if (previousCmd == 'q' || previousCmd == 't'
438                    || previousCmd == 'Q' || previousCmd == 'T') {
439                reflectiveCtrlPointX = 2 * currentX - ctrlPointX;
440                reflectiveCtrlPointY = 2 * currentY - ctrlPointY;
441            }
442            outPath->quadTo(reflectiveCtrlPointX, reflectiveCtrlPointY,
443                    points->at(k + 0), points->at(k + 1));
444            ctrlPointX = reflectiveCtrlPointX;
445            ctrlPointY = reflectiveCtrlPointY;
446            currentX = points->at(k + 0);
447            currentY = points->at(k + 1);
448            break;
449        case 'a': // Draws an elliptical arc
450            // (rx ry x-axis-rotation large-arc-flag sweep-flag x y)
451            drawArc(outPath,
452                    currentX,
453                    currentY,
454                    points->at(k + 5) + currentX,
455                    points->at(k + 6) + currentY,
456                    points->at(k + 0),
457                    points->at(k + 1),
458                    points->at(k + 2),
459                    points->at(k + 3) != 0,
460                    points->at(k + 4) != 0);
461            currentX += points->at(k + 5);
462            currentY += points->at(k + 6);
463            ctrlPointX = currentX;
464            ctrlPointY = currentY;
465            break;
466        case 'A': // Draws an elliptical arc
467            drawArc(outPath,
468                    currentX,
469                    currentY,
470                    points->at(k + 5),
471                    points->at(k + 6),
472                    points->at(k + 0),
473                    points->at(k + 1),
474                    points->at(k + 2),
475                    points->at(k + 3) != 0,
476                    points->at(k + 4) != 0);
477            currentX = points->at(k + 5);
478            currentY = points->at(k + 6);
479            ctrlPointX = currentX;
480            ctrlPointY = currentY;
481            break;
482        default:
483            LOG_ALWAYS_FATAL("Unsupported command: %c", cmd);
484            break;
485        }
486        previousCmd = cmd;
487    }
488}
489
490} // namespace uirenderer
491} // namespace android
492