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
24 namespace android {
25 namespace uirenderer {
26
27 class PathResolver {
28 public:
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
canMorph(const PathData & morphFrom,const PathData & morphTo)39 bool 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
interpolatePathData(PathData * outData,const PathData & morphFrom,const PathData & morphTo,float fraction)53 bool 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 */
verbsToPath(SkPath * outPath,const PathData & data)65 void 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 */
interpolatePaths(PathData * outData,const PathData & from,const PathData & to,float fraction)88 void 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 */
arcToBezier(SkPath * p,double cx,double cy,double a,double b,double e1x,double e1y,double theta,double start,double sweep)113 static 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
toRadians(float theta)168 inline double toRadians(float theta) { return theta * M_PI / 180;}
169
drawArc(SkPath * p,float x0,float y0,float x1,float y1,float a,float b,float theta,bool isMoreThanHalf,bool isPositiveArc)170 static 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.
addCommand(SkPath * outPath,char previousCmd,char cmd,const std::vector<float> * points,size_t start,size_t end)250 void 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