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 | |
64 | static 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 | |
74 | static 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 | |
86 | static 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 | |
99 | void _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 | |
270 | static 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 | |
316 | static 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 | |
486 | static 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 | |
537 | bool 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 | |