1/*
2 * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved.
3
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10
11 * The above copyright notice and this permission notice shall be included in all
12 * copies or substantial portions of the Software.
13
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 * SOFTWARE.
21 */
22
23/*
24 * Copyright notice for the EFL:
25
26 * Copyright (C) EFL developers (see AUTHORS)
27
28 * All rights reserved.
29
30 * Redistribution and use in source and binary forms, with or without
31 * modification, are permitted provided that the following conditions are met:
32
33 * 1. Redistributions of source code must retain the above copyright
34 * notice, this list of conditions and the following disclaimer.
35 * 2. Redistributions in binary form must reproduce the above copyright
36 * notice, this list of conditions and the following disclaimer in the
37 * documentation and/or other materials provided with the distribution.
38
39 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
40 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
41 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
42 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
43 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
44 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
45 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
46 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
47 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
48 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49*/
50
51#define _USE_MATH_DEFINES //Math Constants are not defined in Standard C/C++.
52
53#include <cstring>
54#include <math.h>
55#include <ctype.h>
56#include "tvgSvgLoaderCommon.h"
57#include "tvgSvgPath.h"
58#include "tvgSvgUtil.h"
59
60/************************************************************************/
61/* Internal Class Implementation */
62/************************************************************************/
63
64static char* _skipComma(const char* content)
65{
66 while (*content && isspace(*content)) {
67 content++;
68 }
69 if (*content == ',') return (char*)content + 1;
70 return (char*)content;
71}
72
73
74static bool _parseNumber(char** content, float* number)
75{
76 char* end = NULL;
77 *number = svgUtilStrtof(*content, &end);
78 //If the start of string is not number
79 if ((*content) == end) return false;
80 //Skip comma if any
81 *content = _skipComma(end);
82 return true;
83}
84
85
86static bool _parseFlag(char** content, int* number)
87{
88 char* end = NULL;
89 if (*(*content) != '0' && *(*content) != '1') return false;
90 *number = *(*content) - '0';
91 *content += 1;
92 end = *content;
93 *content = _skipComma(end);
94
95 return true;
96}
97
98
99void _pathAppendArcTo(Array<PathCommand>* cmds, Array<Point>* pts, Point* cur, Point* curCtl, float x, float y, float rx, float ry, float angle, bool largeArc, bool sweep)
100{
101 float cxp, cyp, cx, cy;
102 float sx, sy;
103 float cosPhi, sinPhi;
104 float dx2, dy2;
105 float x1p, y1p;
106 float x1p2, y1p2;
107 float rx2, ry2;
108 float lambda;
109 float c;
110 float at;
111 float theta1, deltaTheta;
112 float nat;
113 float delta, bcp;
114 float cosPhiRx, cosPhiRy;
115 float sinPhiRx, sinPhiRy;
116 float cosTheta1, sinTheta1;
117 int segments;
118
119 //Some helpful stuff is available here:
120 //http://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes
121 sx = cur->x;
122 sy = cur->y;
123
124 //If start and end points are identical, then no arc is drawn
125 if ((fabsf(x - sx) < (1.0f / 256.0f)) && (fabsf(y - sy) < (1.0f / 256.0f))) return;
126
127 //Correction of out-of-range radii, see F6.6.1 (step 2)
128 rx = fabsf(rx);
129 ry = fabsf(ry);
130
131 angle = angle * M_PI / 180.0f;
132 cosPhi = cosf(angle);
133 sinPhi = sinf(angle);
134 dx2 = (sx - x) / 2.0f;
135 dy2 = (sy - y) / 2.0f;
136 x1p = cosPhi * dx2 + sinPhi * dy2;
137 y1p = cosPhi * dy2 - sinPhi * dx2;
138 x1p2 = x1p * x1p;
139 y1p2 = y1p * y1p;
140 rx2 = rx * rx;
141 ry2 = ry * ry;
142 lambda = (x1p2 / rx2) + (y1p2 / ry2);
143
144 //Correction of out-of-range radii, see F6.6.2 (step 4)
145 if (lambda > 1.0f) {
146 //See F6.6.3
147 float lambdaRoot = sqrtf(lambda);
148
149 rx *= lambdaRoot;
150 ry *= lambdaRoot;
151 //Update rx2 and ry2
152 rx2 = rx * rx;
153 ry2 = ry * ry;
154 }
155
156 c = (rx2 * ry2) - (rx2 * y1p2) - (ry2 * x1p2);
157
158 //Check if there is no possible solution
159 //(i.e. we can't do a square root of a negative value)
160 if (c < 0.0f) {
161 //Scale uniformly until we have a single solution
162 //(see F6.2) i.e. when c == 0.0
163 float scale = sqrtf(1.0f - c / (rx2 * ry2));
164 rx *= scale;
165 ry *= scale;
166 //Update rx2 and ry2
167 rx2 = rx * rx;
168 ry2 = ry * ry;
169
170 //Step 2 (F6.5.2) - simplified since c == 0.0
171 cxp = 0.0f;
172 cyp = 0.0f;
173 //Step 3 (F6.5.3 first part) - simplified since cxp and cyp == 0.0
174 cx = 0.0f;
175 cy = 0.0f;
176 } else {
177 //Complete c calculation
178 c = sqrtf(c / ((rx2 * y1p2) + (ry2 * x1p2)));
179 //Inverse sign if Fa == Fs
180 if (largeArc == sweep) c = -c;
181
182 //Step 2 (F6.5.2)
183 cxp = c * (rx * y1p / ry);
184 cyp = c * (-ry * x1p / rx);
185
186 //Step 3 (F6.5.3 first part)
187 cx = cosPhi * cxp - sinPhi * cyp;
188 cy = sinPhi * cxp + cosPhi * cyp;
189 }
190
191 //Step 3 (F6.5.3 second part) we now have the center point of the ellipse
192 cx += (sx + x) / 2.0f;
193 cy += (sy + y) / 2.0f;
194
195 //Sstep 4 (F6.5.4)
196 //We dont' use arccos (as per w3c doc), see
197 //http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm
198 //Note: atan2 (0.0, 1.0) == 0.0
199 at = atan2(((y1p - cyp) / ry), ((x1p - cxp) / rx));
200 theta1 = (at < 0.0f) ? 2.0f * M_PI + at : at;
201
202 nat = atan2(((-y1p - cyp) / ry), ((-x1p - cxp) / rx));
203 deltaTheta = (nat < at) ? 2.0f * M_PI - at + nat : nat - at;
204
205 if (sweep) {
206 //Ensure delta theta < 0 or else add 360 degrees
207 if (deltaTheta < 0.0f) deltaTheta += (float)(2.0f * M_PI);
208 } else {
209 //Ensure delta theta > 0 or else substract 360 degrees
210 if (deltaTheta > 0.0f) deltaTheta -= (float)(2.0f * M_PI);
211 }
212
213 //Add several cubic bezier to approximate the arc
214 //(smaller than 90 degrees)
215 //We add one extra segment because we want something
216 //Smaller than 90deg (i.e. not 90 itself)
217 segments = static_cast<int>(fabsf(deltaTheta / float(M_PI_2)) + 1.0f);
218 delta = deltaTheta / segments;
219
220 //http://www.stillhq.com/ctpfaq/2001/comp.text.pdf-faq-2001-04.txt (section 2.13)
221 bcp = 4.0f / 3.0f * (1.0f - cosf(delta / 2.0f)) / sinf(delta / 2.0f);
222
223 cosPhiRx = cosPhi * rx;
224 cosPhiRy = cosPhi * ry;
225 sinPhiRx = sinPhi * rx;
226 sinPhiRy = sinPhi * ry;
227
228 cosTheta1 = cosf(theta1);
229 sinTheta1 = sinf(theta1);
230
231 for (int i = 0; i < segments; ++i) {
232 //End angle (for this segment) = current + delta
233 float c1x, c1y, ex, ey, c2x, c2y;
234 float theta2 = theta1 + delta;
235 float cosTheta2 = cosf(theta2);
236 float sinTheta2 = sinf(theta2);
237 Point p[3];
238
239 //First control point (based on start point sx,sy)
240 c1x = sx - bcp * (cosPhiRx * sinTheta1 + sinPhiRy * cosTheta1);
241 c1y = sy + bcp * (cosPhiRy * cosTheta1 - sinPhiRx * sinTheta1);
242
243 //End point (for this segment)
244 ex = cx + (cosPhiRx * cosTheta2 - sinPhiRy * sinTheta2);
245 ey = cy + (sinPhiRx * cosTheta2 + cosPhiRy * sinTheta2);
246
247 //Second control point (based on end point ex,ey)
248 c2x = ex + bcp * (cosPhiRx * sinTheta2 + sinPhiRy * cosTheta2);
249 c2y = ey + bcp * (sinPhiRx * sinTheta2 - cosPhiRy * cosTheta2);
250 cmds->push(PathCommand::CubicTo);
251 p[0] = {c1x, c1y};
252 p[1] = {c2x, c2y};
253 p[2] = {ex, ey};
254 pts->push(p[0]);
255 pts->push(p[1]);
256 pts->push(p[2]);
257 *curCtl = p[1];
258 *cur = p[2];
259
260 //Next start point is the current end point (same for angle)
261 sx = ex;
262 sy = ey;
263 theta1 = theta2;
264 //Avoid recomputations
265 cosTheta1 = cosTheta2;
266 sinTheta1 = sinTheta2;
267 }
268}
269
270static int _numberCount(char cmd)
271{
272 int count = 0;
273 switch (cmd) {
274 case 'M':
275 case 'm':
276 case 'L':
277 case 'l':
278 case 'T':
279 case 't': {
280 count = 2;
281 break;
282 }
283 case 'C':
284 case 'c':
285 case 'E':
286 case 'e': {
287 count = 6;
288 break;
289 }
290 case 'H':
291 case 'h':
292 case 'V':
293 case 'v': {
294 count = 1;
295 break;
296 }
297 case 'S':
298 case 's':
299 case 'Q':
300 case 'q': {
301 count = 4;
302 break;
303 }
304 case 'A':
305 case 'a': {
306 count = 7;
307 break;
308 }
309 default:
310 break;
311 }
312 return count;
313}
314
315
316static bool _processCommand(Array<PathCommand>* cmds, Array<Point>* pts, char cmd, float* arr, int count, Point* cur, Point* curCtl, Point* startPoint, bool *isQuadratic)
317{
318 switch (cmd) {
319 case 'm':
320 case 'l':
321 case 'c':
322 case 's':
323 case 'q':
324 case 't': {
325 for (int i = 0; i < count - 1; i += 2) {
326 arr[i] = arr[i] + cur->x;
327 arr[i + 1] = arr[i + 1] + cur->y;
328 }
329 break;
330 }
331 case 'h': {
332 arr[0] = arr[0] + cur->x;
333 break;
334 }
335 case 'v': {
336 arr[0] = arr[0] + cur->y;
337 break;
338 }
339 case 'a': {
340 arr[5] = arr[5] + cur->x;
341 arr[6] = arr[6] + cur->y;
342 break;
343 }
344 default: {
345 break;
346 }
347 }
348
349 switch (cmd) {
350 case 'm':
351 case 'M': {
352 Point p = {arr[0], arr[1]};
353 cmds->push(PathCommand::MoveTo);
354 pts->push(p);
355 *cur = {arr[0], arr[1]};
356 *startPoint = {arr[0], arr[1]};
357 break;
358 }
359 case 'l':
360 case 'L': {
361 Point p = {arr[0], arr[1]};
362 cmds->push(PathCommand::LineTo);
363 pts->push(p);
364 *cur = {arr[0], arr[1]};
365 break;
366 }
367 case 'c':
368 case 'C': {
369 Point p[3];
370 cmds->push(PathCommand::CubicTo);
371 p[0] = {arr[0], arr[1]};
372 p[1] = {arr[2], arr[3]};
373 p[2] = {arr[4], arr[5]};
374 pts->push(p[0]);
375 pts->push(p[1]);
376 pts->push(p[2]);
377 *curCtl = p[1];
378 *cur = p[2];
379 *isQuadratic = false;
380 break;
381 }
382 case 's':
383 case 'S': {
384 Point p[3], ctrl;
385 if ((cmds->count > 1) && (cmds->data[cmds->count - 1] == PathCommand::CubicTo) &&
386 !(*isQuadratic)) {
387 ctrl.x = 2 * cur->x - curCtl->x;
388 ctrl.y = 2 * cur->y - curCtl->y;
389 } else {
390 ctrl = *cur;
391 }
392 cmds->push(PathCommand::CubicTo);
393 p[0] = ctrl;
394 p[1] = {arr[0], arr[1]};
395 p[2] = {arr[2], arr[3]};
396 pts->push(p[0]);
397 pts->push(p[1]);
398 pts->push(p[2]);
399 *curCtl = p[1];
400 *cur = p[2];
401 *isQuadratic = false;
402 break;
403 }
404 case 'q':
405 case 'Q': {
406 Point p[3];
407 float ctrl_x0 = (cur->x + 2 * arr[0]) * (1.0 / 3.0);
408 float ctrl_y0 = (cur->y + 2 * arr[1]) * (1.0 / 3.0);
409 float ctrl_x1 = (arr[2] + 2 * arr[0]) * (1.0 / 3.0);
410 float ctrl_y1 = (arr[3] + 2 * arr[1]) * (1.0 / 3.0);
411 cmds->push(PathCommand::CubicTo);
412 p[0] = {ctrl_x0, ctrl_y0};
413 p[1] = {ctrl_x1, ctrl_y1};
414 p[2] = {arr[2], arr[3]};
415 pts->push(p[0]);
416 pts->push(p[1]);
417 pts->push(p[2]);
418 *curCtl = {arr[0], arr[1]};
419 *cur = p[2];
420 *isQuadratic = true;
421 break;
422 }
423 case 't':
424 case 'T': {
425 Point p[3], ctrl;
426 if ((cmds->count > 1) && (cmds->data[cmds->count - 1] == PathCommand::CubicTo) &&
427 *isQuadratic) {
428 ctrl.x = 2 * cur->x - curCtl->x;
429 ctrl.y = 2 * cur->y - curCtl->y;
430 } else {
431 ctrl = *cur;
432 }
433 float ctrl_x0 = (cur->x + 2 * ctrl.x) * (1.0 / 3.0);
434 float ctrl_y0 = (cur->y + 2 * ctrl.y) * (1.0 / 3.0);
435 float ctrl_x1 = (arr[0] + 2 * ctrl.x) * (1.0 / 3.0);
436 float ctrl_y1 = (arr[1] + 2 * ctrl.y) * (1.0 / 3.0);
437 cmds->push(PathCommand::CubicTo);
438 p[0] = {ctrl_x0, ctrl_y0};
439 p[1] = {ctrl_x1, ctrl_y1};
440 p[2] = {arr[0], arr[1]};
441 pts->push(p[0]);
442 pts->push(p[1]);
443 pts->push(p[2]);
444 *curCtl = {ctrl.x, ctrl.y};
445 *cur = p[2];
446 *isQuadratic = true;
447 break;
448 }
449 case 'h':
450 case 'H': {
451 Point p = {arr[0], cur->y};
452 cmds->push(PathCommand::LineTo);
453 pts->push(p);
454 cur->x = arr[0];
455 break;
456 }
457 case 'v':
458 case 'V': {
459 Point p = {cur->x, arr[0]};
460 cmds->push(PathCommand::LineTo);
461 pts->push(p);
462 cur->y = arr[0];
463 break;
464 }
465 case 'z':
466 case 'Z': {
467 cmds->push(PathCommand::Close);
468 *cur = *startPoint;
469 break;
470 }
471 case 'a':
472 case 'A': {
473 _pathAppendArcTo(cmds, pts, cur, curCtl, arr[5], arr[6], arr[0], arr[1], arr[2], arr[3], arr[4]);
474 *cur = *curCtl = {arr[5], arr[6]};
475 *isQuadratic = false;
476 break;
477 }
478 default: {
479 return false;
480 }
481 }
482 return true;
483}
484
485
486static char* _nextCommand(char* path, char* cmd, float* arr, int* count)
487{
488 int large, sweep;
489
490 path = _skipComma(path);
491 if (isalpha(*path)) {
492 *cmd = *path;
493 path++;
494 *count = _numberCount(*cmd);
495 } else {
496 if (*cmd == 'm') *cmd = 'l';
497 else if (*cmd == 'M') *cmd = 'L';
498 }
499 if (*count == 7) {
500 //Special case for arc command
501 if (_parseNumber(&path, &arr[0])) {
502 if (_parseNumber(&path, &arr[1])) {
503 if (_parseNumber(&path, &arr[2])) {
504 if (_parseFlag(&path, &large)) {
505 if (_parseFlag(&path, &sweep)) {
506 if (_parseNumber(&path, &arr[5])) {
507 if (_parseNumber(&path, &arr[6])) {
508 arr[3] = (float)large;
509 arr[4] = (float)sweep;
510 return path;
511 }
512 }
513 }
514 }
515 }
516 }
517 }
518 *count = 0;
519 return NULL;
520 }
521 for (int i = 0; i < *count; i++) {
522 if (!_parseNumber(&path, &arr[i])) {
523 *count = 0;
524 return NULL;
525 }
526 path = _skipComma(path);
527 }
528 return path;
529}
530
531
532/************************************************************************/
533/* External Class Implementation */
534/************************************************************************/
535
536
537bool svgPathToTvgPath(const char* svgPath, Array<PathCommand>& cmds, Array<Point>& pts)
538{
539 float numberArray[7];
540 int numberCount = 0;
541 Point cur = { 0, 0 };
542 Point curCtl = { 0, 0 };
543 Point startPoint = { 0, 0 };
544 char cmd = 0;
545 bool isQuadratic = false;
546 char* path = (char*)svgPath;
547
548 while ((path[0] != '\0')) {
549 path = _nextCommand(path, &cmd, numberArray, &numberCount);
550 if (!path) break;
551 if (!_processCommand(&cmds, &pts, cmd, numberArray, numberCount, &cur, &curCtl, &startPoint, &isQuadratic)) break;
552 }
553
554 return true;
555}
556