src/loaders/svg/tvgSvgPath.cpp

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