src/loaders/svg/tvgSvgPath.cpp

   1 /*
   2  * Copyright (c) 2020 - 2022 Samsung Electronics Co., Ltd. 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 <clocale>
  56 #include <ctype.h>
  57 #include "tvgSvgLoaderCommon.h"
  58 #include "tvgSvgPath.h"
  59 #include "tvgSvgUtil.h"
  60
  61 /************************************************************************/
  62 /* Internal Class Implementation                                        */
  63 /************************************************************************/
  64
  65 static char* _skipComma(const char* content)
  66 {
  67     while (*content && isspace(*content)) {
  68         content++;
  69     }
  70     if (*content == ',') return (char*)content + 1;
  71     return (char*)content;
  72 }
  73
  74
  75 static bool _parseNumber(char** content, float* number)
  76 {
  77     char* end = NULL;
  78     *number = svgUtilStrtof(*content, &end);
  79     //If the start of string is not number
  80     if ((*content) == end) return false;
  81     //Skip comma if any
  82     *content = _skipComma(end);
  83     return true;
  84 }
  85
  86
  87 static bool _parseFlag(char** content, int* number)
  88 {
  89     char* end = NULL;
  90     if (*(*content) != '0' && *(*content) != '1') return false;
  91     *number = *(*content) - '0';
  92     *content += 1;
  93     end = *content;
  94     *content = _skipComma(end);
  95
  96     return true;
  97 }
  98
  99
 100 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)
 101 {
 102     float cxp, cyp, cx, cy;
 103     float sx, sy;
 104     float cosPhi, sinPhi;
 105     float dx2, dy2;
 106     float x1p, y1p;
 107     float x1p2, y1p2;
 108     float rx2, ry2;
 109     float lambda;
 110     float c;
 111     float at;
 112     float theta1, deltaTheta;
 113     float nat;
 114     float delta, bcp;
 115     float cosPhiRx, cosPhiRy;
 116     float sinPhiRx, sinPhiRy;
 117     float cosTheta1, sinTheta1;
 118     int segments;
 119
 120     //Some helpful stuff is available here:
 121     //http://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes
 122     sx = cur->x;
 123     sy = cur->y;
 124
 125     //If start and end points are identical, then no arc is drawn
 126     if ((fabsf(x - sx) < (1.0f / 256.0f)) && (fabsf(y - sy) < (1.0f / 256.0f))) return;
 127
 128     //Correction of out-of-range radii, see F6.6.1 (step 2)
 129     rx = fabsf(rx);
 130     ry = fabsf(ry);
 131
 132     angle = angle * M_PI / 180.0f;
 133     cosPhi = cosf(angle);
 134     sinPhi = sinf(angle);
 135     dx2 = (sx - x) / 2.0f;
 136     dy2 = (sy - y) / 2.0f;
 137     x1p = cosPhi * dx2 + sinPhi * dy2;
 138     y1p = cosPhi * dy2 - sinPhi * dx2;
 139     x1p2 = x1p * x1p;
 140     y1p2 = y1p * y1p;
 141     rx2 = rx * rx;
 142     ry2 = ry * ry;
 143     lambda = (x1p2 / rx2) + (y1p2 / ry2);
 144
 145     //Correction of out-of-range radii, see F6.6.2 (step 4)
 146     if (lambda > 1.0f) {
 147         //See F6.6.3
 148         float lambdaRoot = sqrtf(lambda);
 149
 150         rx *= lambdaRoot;
 151         ry *= lambdaRoot;
 152         //Update rx2 and ry2
 153         rx2 = rx * rx;
 154         ry2 = ry * ry;
 155     }
 156
 157     c = (rx2 * ry2) - (rx2 * y1p2) - (ry2 * x1p2);
 158
 159     //Check if there is no possible solution
 160     //(i.e. we can't do a square root of a negative value)
 161     if (c < 0.0f) {
 162         //Scale uniformly until we have a single solution
 163         //(see F6.2) i.e. when c == 0.0
 164         float scale = sqrtf(1.0f - c / (rx2 * ry2));
 165         rx *= scale;
 166         ry *= scale;
 167         //Update rx2 and ry2
 168         rx2 = rx * rx;
 169         ry2 = ry * ry;
 170
 171         //Step 2 (F6.5.2) - simplified since c == 0.0
 172         cxp = 0.0f;
 173         cyp = 0.0f;
 174         //Step 3 (F6.5.3 first part) - simplified since cxp and cyp == 0.0
 175         cx = 0.0f;
 176         cy = 0.0f;
 177     } else {
 178         //Complete c calculation
 179         c = sqrtf(c / ((rx2 * y1p2) + (ry2 * x1p2)));
 180         //Inverse sign if Fa == Fs
 181         if (largeArc == sweep) c = -c;
 182
 183         //Step 2 (F6.5.2)
 184         cxp = c * (rx * y1p / ry);
 185         cyp = c * (-ry * x1p / rx);
 186
 187         //Step 3 (F6.5.3 first part)
 188         cx = cosPhi * cxp - sinPhi * cyp;
 189         cy = sinPhi * cxp + cosPhi * cyp;
 190     }
 191
 192     //Step 3 (F6.5.3 second part) we now have the center point of the ellipse
 193     cx += (sx + x) / 2.0f;
 194     cy += (sy + y) / 2.0f;
 195
 196     //Sstep 4 (F6.5.4)
 197     //We dont' use arccos (as per w3c doc), see
 198     //http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm
 199     //Note: atan2 (0.0, 1.0) == 0.0
 200     at = atan2(((y1p - cyp) / ry), ((x1p - cxp) / rx));
 201     theta1 = (at < 0.0f) ? 2.0f * M_PI + at : at;
 202
 203     nat = atan2(((-y1p - cyp) / ry), ((-x1p - cxp) / rx));
 204     deltaTheta = (nat < at) ? 2.0f * M_PI - at + nat : nat - at;
 205
 206     if (sweep) {
 207         //Ensure delta theta < 0 or else add 360 degrees
 208         if (deltaTheta < 0.0f) deltaTheta += (float)(2.0f * M_PI);
 209     } else {
 210         //Ensure delta theta > 0 or else substract 360 degrees
 211         if (deltaTheta > 0.0f) deltaTheta -= (float)(2.0f * M_PI);
 212     }
 213
 214     //Add several cubic bezier to approximate the arc
 215     //(smaller than 90 degrees)
 216     //We add one extra segment because we want something
 217     //Smaller than 90deg (i.e. not 90 itself)
 218     segments = static_cast<int>(fabsf(deltaTheta / float(M_PI_2)) + 1.0f);
 219     delta = deltaTheta / segments;
 220
 221     //http://www.stillhq.com/ctpfaq/2001/comp.text.pdf-faq-2001-04.txt (section 2.13)
 222     bcp = 4.0f / 3.0f * (1.0f - cosf(delta / 2.0f)) / sinf(delta / 2.0f);
 223
 224     cosPhiRx = cosPhi * rx;
 225     cosPhiRy = cosPhi * ry;
 226     sinPhiRx = sinPhi * rx;
 227     sinPhiRy = sinPhi * ry;
 228
 229     cosTheta1 = cosf(theta1);
 230     sinTheta1 = sinf(theta1);
 231
 232     for (int i = 0; i < segments; ++i) {
 233         //End angle (for this segment) = current + delta
 234         float c1x, c1y, ex, ey, c2x, c2y;
 235         float theta2 = theta1 + delta;
 236         float cosTheta2 = cosf(theta2);
 237         float sinTheta2 = sinf(theta2);
 238         Point p[3];
 239
 240         //First control point (based on start point sx,sy)
 241         c1x = sx - bcp * (cosPhiRx * sinTheta1 + sinPhiRy * cosTheta1);
 242         c1y = sy + bcp * (cosPhiRy * cosTheta1 - sinPhiRx * sinTheta1);
 243
 244         //End point (for this segment)
 245         ex = cx + (cosPhiRx * cosTheta2 - sinPhiRy * sinTheta2);
 246         ey = cy + (sinPhiRx * cosTheta2 + cosPhiRy * sinTheta2);
 247
 248         //Second control point (based on end point ex,ey)
 249         c2x = ex + bcp * (cosPhiRx * sinTheta2 + sinPhiRy * cosTheta2);
 250         c2y = ey + bcp * (sinPhiRx * sinTheta2 - cosPhiRy * cosTheta2);
 251         cmds->push(PathCommand::CubicTo);
 252         p[0] = {c1x, c1y};
 253         p[1] = {c2x, c2y};
 254         p[2] = {ex, ey};
 255         pts->push(p[0]);
 256         pts->push(p[1]);
 257         pts->push(p[2]);
 258         *curCtl = p[1];
 259         *cur = p[2];
 260
 261         //Next start point is the current end point (same for angle)
 262         sx = ex;
 263         sy = ey;
 264         theta1 = theta2;
 265         //Avoid recomputations
 266         cosTheta1 = cosTheta2;
 267         sinTheta1 = sinTheta2;
 268     }
 269 }
 270
 271 static int _numberCount(char cmd)
 272 {
 273     int count = 0;
 274     switch (cmd) {
 275         case 'M':
 276         case 'm':
 277         case 'L':
 278         case 'l':
 279         case 'T':
 280         case 't': {
 281             count = 2;
 282             break;
 283         }
 284         case 'C':
 285         case 'c':
 286         case 'E':
 287         case 'e': {
 288             count = 6;
 289             break;
 290         }
 291         case 'H':
 292         case 'h':
 293         case 'V':
 294         case 'v': {
 295             count = 1;
 296             break;
 297         }
 298         case 'S':
 299         case 's':
 300         case 'Q':
 301         case 'q': {
 302             count = 4;
 303             break;
 304         }
 305         case 'A':
 306         case 'a': {
 307             count = 7;
 308             break;
 309         }
 310         default:
 311             break;
 312     }
 313     return count;
 314 }
 315
 316
 317 static bool _processCommand(Array<PathCommand>* cmds, Array<Point>* pts, char cmd, float* arr, int count, Point* cur, Point* curCtl, Point* startPoint, bool *isQuadratic)
 318 {
 319     switch (cmd) {
 320         case 'm':
 321         case 'l':
 322         case 'c':
 323         case 's':
 324         case 'q':
 325         case 't': {
 326             for (int i = 0; i < count - 1; i += 2) {
 327                 arr[i] = arr[i] + cur->x;
 328                 arr[i + 1] = arr[i + 1] + cur->y;
 329             }
 330             break;
 331         }
 332         case 'h': {
 333             arr[0] = arr[0] + cur->x;
 334             break;
 335         }
 336         case 'v': {
 337             arr[0] = arr[0] + cur->y;
 338             break;
 339         }
 340         case 'a': {
 341             arr[5] = arr[5] + cur->x;
 342             arr[6] = arr[6] + cur->y;
 343             break;
 344         }
 345         default: {
 346             break;
 347         }
 348     }
 349
 350     switch (cmd) {
 351         case 'm':
 352         case 'M': {
 353             Point p = {arr[0], arr[1]};
 354             cmds->push(PathCommand::MoveTo);
 355             pts->push(p);
 356             *cur = {arr[0], arr[1]};
 357             *startPoint = {arr[0], arr[1]};
 358             break;
 359         }
 360         case 'l':
 361         case 'L': {
 362             Point p = {arr[0], arr[1]};
 363             cmds->push(PathCommand::LineTo);
 364             pts->push(p);
 365             *cur = {arr[0], arr[1]};
 366             break;
 367         }
 368         case 'c':
 369         case 'C': {
 370             Point p[3];
 371             cmds->push(PathCommand::CubicTo);
 372             p[0] = {arr[0], arr[1]};
 373             p[1] = {arr[2], arr[3]};
 374             p[2] = {arr[4], arr[5]};
 375             pts->push(p[0]);
 376             pts->push(p[1]);
 377             pts->push(p[2]);
 378             *curCtl = p[1];
 379             *cur = p[2];
 380             *isQuadratic = false;
 381             break;
 382         }
 383         case 's':
 384         case 'S': {
 385             Point p[3], ctrl;
 386             if ((cmds->count > 1) && (cmds->data[cmds->count - 1] == PathCommand::CubicTo) &&
 387                 !(*isQuadratic)) {
 388                 ctrl.x = 2 * cur->x - curCtl->x;
 389                 ctrl.y = 2 * cur->y - curCtl->y;
 390             } else {
 391                 ctrl = *cur;
 392             }
 393             cmds->push(PathCommand::CubicTo);
 394             p[0] = ctrl;
 395             p[1] = {arr[0], arr[1]};
 396             p[2] = {arr[2], arr[3]};
 397             pts->push(p[0]);
 398             pts->push(p[1]);
 399             pts->push(p[2]);
 400             *curCtl = p[1];
 401             *cur = p[2];
 402             *isQuadratic = false;
 403             break;
 404         }
 405         case 'q':
 406         case 'Q': {
 407             Point p[3];
 408             float ctrl_x0 = (cur->x + 2 * arr[0]) * (1.0 / 3.0);
 409             float ctrl_y0 = (cur->y + 2 * arr[1]) * (1.0 / 3.0);
 410             float ctrl_x1 = (arr[2] + 2 * arr[0]) * (1.0 / 3.0);
 411             float ctrl_y1 = (arr[3] + 2 * arr[1]) * (1.0 / 3.0);
 412             cmds->push(PathCommand::CubicTo);
 413             p[0] = {ctrl_x0, ctrl_y0};
 414             p[1] = {ctrl_x1, ctrl_y1};
 415             p[2] = {arr[2], arr[3]};
 416             pts->push(p[0]);
 417             pts->push(p[1]);
 418             pts->push(p[2]);
 419             *curCtl = {arr[0], arr[1]};
 420             *cur = p[2];
 421             *isQuadratic = true;
 422             break;
 423         }
 424         case 't':
 425         case 'T': {
 426             Point p[3], ctrl;
 427             if ((cmds->count > 1) && (cmds->data[cmds->count - 1] == PathCommand::CubicTo) &&
 428                 *isQuadratic) {
 429                 ctrl.x = 2 * cur->x - curCtl->x;
 430                 ctrl.y = 2 * cur->y - curCtl->y;
 431             } else {
 432                 ctrl = *cur;
 433             }
 434             float ctrl_x0 = (cur->x + 2 * ctrl.x) * (1.0 / 3.0);
 435             float ctrl_y0 = (cur->y + 2 * ctrl.y) * (1.0 / 3.0);
 436             float ctrl_x1 = (arr[0] + 2 * ctrl.x) * (1.0 / 3.0);
 437             float ctrl_y1 = (arr[1] + 2 * ctrl.y) * (1.0 / 3.0);
 438             cmds->push(PathCommand::CubicTo);
 439             p[0] = {ctrl_x0, ctrl_y0};
 440             p[1] = {ctrl_x1, ctrl_y1};
 441             p[2] = {arr[0], arr[1]};
 442             pts->push(p[0]);
 443             pts->push(p[1]);
 444             pts->push(p[2]);
 445             *curCtl = {ctrl.x, ctrl.y};
 446             *cur = p[2];
 447             *isQuadratic = true;
 448             break;
 449         }
 450         case 'h':
 451         case 'H': {
 452             Point p = {arr[0], cur->y};
 453             cmds->push(PathCommand::LineTo);
 454             pts->push(p);
 455             cur->x = arr[0];
 456             break;
 457         }
 458         case 'v':
 459         case 'V': {
 460             Point p = {cur->x, arr[0]};
 461             cmds->push(PathCommand::LineTo);
 462             pts->push(p);
 463             cur->y = arr[0];
 464             break;
 465         }
 466         case 'z':
 467         case 'Z': {
 468             cmds->push(PathCommand::Close);
 469             *cur = *startPoint;
 470             break;
 471         }
 472         case 'a':
 473         case 'A': {
 474             _pathAppendArcTo(cmds, pts, cur, curCtl, arr[5], arr[6], arr[0], arr[1], arr[2], arr[3], arr[4]);
 475             *cur = *curCtl = {arr[5], arr[6]};
 476             *isQuadratic = false;
 477             break;
 478         }
 479         default: {
 480             return false;
 481         }
 482     }
 483     return true;
 484 }
 485
 486
 487 static char* _nextCommand(char* path, char* cmd, float* arr, int* count)
 488 {
 489     int large, sweep;
 490
 491     path = _skipComma(path);
 492     if (isalpha(*path)) {
 493         *cmd = *path;
 494         path++;
 495         *count = _numberCount(*cmd);
 496     } else {
 497         if (*cmd == 'm') *cmd = 'l';
 498         else if (*cmd == 'M') *cmd = 'L';
 499     }
 500     if (*count == 7) {
 501         //Special case for arc command
 502         if (_parseNumber(&path, &arr[0])) {
 503             if (_parseNumber(&path, &arr[1])) {
 504                 if (_parseNumber(&path, &arr[2])) {
 505                     if (_parseFlag(&path, &large)) {
 506                         if (_parseFlag(&path, &sweep)) {
 507                             if (_parseNumber(&path, &arr[5])) {
 508                                 if (_parseNumber(&path, &arr[6])) {
 509                                     arr[3] = (float)large;
 510                                     arr[4] = (float)sweep;
 511                                     return path;
 512                                 }
 513                             }
 514                         }
 515                     }
 516                 }
 517             }
 518         }
 519         *count = 0;
 520         return NULL;
 521     }
 522     for (int i = 0; i < *count; i++) {
 523         if (!_parseNumber(&path, &arr[i])) {
 524             *count = 0;
 525             return NULL;
 526         }
 527         path = _skipComma(path);
 528     }
 529     return path;
 530 }
 531
 532
 533 /************************************************************************/
 534 /* External Class Implementation                                        */
 535 /************************************************************************/
 536
 537
 538 bool svgPathToTvgPath(const char* svgPath, Array<PathCommand>& cmds, Array<Point>& pts)
 539 {
 540     float numberArray[7];
 541     int numberCount = 0;
 542     Point cur = { 0, 0 };
 543     Point curCtl = { 0, 0 };
 544     Point startPoint = { 0, 0 };
 545     char cmd = 0;
 546     bool isQuadratic = false;
 547     char* path = (char*)svgPath;
 548     char* curLocale;
 549
 550     curLocale = setlocale(LC_NUMERIC, NULL);
 551     if (curLocale) curLocale = strdup(curLocale);
 552     setlocale(LC_NUMERIC, "POSIX");
 553
 554     while ((path[0] != '\0')) {
 555         path = _nextCommand(path, &cmd, numberArray, &numberCount);
 556         if (!path) break;
 557         if (!_processCommand(&cmds, &pts, cmd, numberArray, numberCount, &cur, &curCtl, &startPoint, &isQuadratic)) break;
 558     }
 559
 560     setlocale(LC_NUMERIC, curLocale);
 561     if (curLocale) free(curLocale);
 562
 563     return true;
 564 }