src/lib/sw_engine/tvgSwStroke.cpp

   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 #include <string.h>
  24 #include <math.h>
  25 #include "tvgSwCommon.h"
  26
  27 /************************************************************************/
  28 /* Internal Class Implementation                                        */
  29 /************************************************************************/
  30
  31 static constexpr auto SW_STROKE_TAG_POINT = 1;
  32 static constexpr auto SW_STROKE_TAG_CUBIC = 2;
  33 static constexpr auto SW_STROKE_TAG_BEGIN = 4;
  34 static constexpr auto SW_STROKE_TAG_END = 8;
  35
  36 static inline SwFixed SIDE_TO_ROTATE(const int32_t s)
  37 {
  38     return (SW_ANGLE_PI2 - static_cast<SwFixed>(s) * SW_ANGLE_PI);
  39 }
  40
  41
  42 static inline void SCALE(const SwStroke& stroke, SwPoint& pt)
  43 {
  44     pt.x = static_cast<SwCoord>(pt.x * stroke.sx);
  45     pt.y = static_cast<SwCoord>(pt.y * stroke.sy);
  46 }
  47
  48
  49 static void _growBorder(SwStrokeBorder* border, uint32_t newPts)
  50 {
  51     auto maxOld = border->maxPts;
  52     auto maxNew = border->ptsCnt + newPts;
  53
  54     if (maxNew <= maxOld) return;
  55
  56     auto maxCur = maxOld;
  57
  58     while (maxCur < maxNew)
  59         maxCur += (maxCur >> 1) + 16;
  60     //OPTIMIZE: use mempool!
  61     border->pts = static_cast<SwPoint*>(realloc(border->pts, maxCur * sizeof(SwPoint)));
  62     border->tags = static_cast<uint8_t*>(realloc(border->tags, maxCur * sizeof(uint8_t)));
  63     border->maxPts = maxCur;
  64 }
  65
  66
  67 static void _borderClose(SwStrokeBorder* border, bool reverse)
  68 {
  69     auto start = border->start;
  70     auto count = border->ptsCnt;
  71
  72     //Don't record empty paths!
  73     if (count <= start + 1U) {
  74         border->ptsCnt = start;
  75     } else {
  76         /* Copy the last point to the start of this sub-path,
  77            since it contains the adjusted starting coordinates */
  78         border->ptsCnt = --count;
  79         border->pts[start] = border->pts[count];
  80
  81         if (reverse) {
  82             //reverse the points
  83             auto pt1 = border->pts + start + 1;
  84             auto pt2 = border->pts + count - 1;
  85
  86             while (pt1 < pt2) {
  87                 auto tmp = *pt1;
  88                 *pt1 = *pt2;
  89                 *pt2 = tmp;
  90                 ++pt1;
  91                 --pt2;
  92             }
  93
  94             //reverse the tags
  95             auto tag1 = border->tags + start + 1;
  96             auto tag2 = border->tags + count - 1;
  97
  98             while (tag1 < tag2) {
  99                 auto tmp = *tag1;
 100                 *tag1 = *tag2;
 101                 *tag2 = tmp;
 102                 ++tag1;
 103                 --tag2;
 104             }
 105         }
 106
 107         border->tags[start] |= SW_STROKE_TAG_BEGIN;
 108         border->tags[count - 1] |=  SW_STROKE_TAG_END;
 109     }
 110
 111     border->start = -1;
 112     border->movable = false;
 113 }
 114
 115
 116 static void _borderCubicTo(SwStrokeBorder* border, const SwPoint& ctrl1, const SwPoint& ctrl2, const SwPoint& to)
 117 {
 118     _growBorder(border, 3);
 119
 120     auto pt = border->pts + border->ptsCnt;
 121     auto tag = border->tags + border->ptsCnt;
 122
 123     pt[0] = ctrl1;
 124     pt[1] = ctrl2;
 125     pt[2] = to;
 126
 127     tag[0] = SW_STROKE_TAG_CUBIC;
 128     tag[1] = SW_STROKE_TAG_CUBIC;
 129     tag[2] = SW_STROKE_TAG_POINT;
 130
 131     border->ptsCnt += 3;
 132
 133     border->movable = false;
 134 }
 135
 136
 137 static void _borderArcTo(SwStrokeBorder* border, const SwPoint& center, SwFixed radius, SwFixed angleStart, SwFixed angleDiff, SwStroke& stroke)
 138 {
 139     constexpr SwFixed ARC_CUBIC_ANGLE = SW_ANGLE_PI / 2;
 140     SwPoint a = {static_cast<SwCoord>(radius), 0};
 141     mathRotate(a, angleStart);
 142     SCALE(stroke, a);
 143     a += center;
 144
 145     auto total = angleDiff;
 146     auto angle = angleStart;
 147     auto rotate = (angleDiff >= 0) ? SW_ANGLE_PI2 : -SW_ANGLE_PI2;
 148
 149     while (total != 0) {
 150         auto step = total;
 151         if (step > ARC_CUBIC_ANGLE) step = ARC_CUBIC_ANGLE;
 152         else if (step < -ARC_CUBIC_ANGLE) step = -ARC_CUBIC_ANGLE;
 153
 154         auto next = angle + step;
 155         auto theta = step;
 156         if (theta < 0) theta = -theta;
 157
 158         theta >>= 1;
 159
 160         //compute end point
 161         SwPoint b = {static_cast<SwCoord>(radius), 0};
 162         mathRotate(b, next);
 163         SCALE(stroke, b);
 164         b += center;
 165
 166         //compute first and second control points
 167         auto length = mathMulDiv(radius, mathSin(theta) * 4, (0x10000L + mathCos(theta)) * 3);
 168
 169         SwPoint a2 = {static_cast<SwCoord>(length), 0};
 170         mathRotate(a2, angle + rotate);
 171         SCALE(stroke, a2);
 172         a2 += a;
 173
 174         SwPoint b2 = {static_cast<SwCoord>(length), 0};
 175         mathRotate(b2, next - rotate);
 176         SCALE(stroke, b2);
 177         b2 += b;
 178
 179         //add cubic arc
 180         _borderCubicTo(border, a2, b2, b);
 181
 182         //process the rest of the arc?
 183         a = b;
 184         total -= step;
 185         angle = next;
 186     }
 187 }
 188
 189
 190 static void _borderLineTo(SwStrokeBorder* border, const SwPoint& to, bool movable)
 191 {
 192     if (border->movable) {
 193         //move last point
 194         border->pts[border->ptsCnt - 1] = to;
 195     } else {
 196
 197         //don't add zero-length line_to
 198         if (border->ptsCnt > 0 && (border->pts[border->ptsCnt - 1] - to).small()) return;
 199
 200         _growBorder(border, 1);
 201         border->pts[border->ptsCnt] = to;
 202         border->tags[border->ptsCnt] = SW_STROKE_TAG_POINT;
 203         border->ptsCnt += 1;
 204     }
 205
 206     border->movable = movable;
 207 }
 208
 209
 210 static void _borderMoveTo(SwStrokeBorder* border, SwPoint& to)
 211 {
 212     //close current open path if any?
 213     if (border->start >= 0) _borderClose(border, false);
 214
 215     border->start = border->ptsCnt;
 216     border->movable = false;
 217
 218     _borderLineTo(border, to, false);
 219 }
 220
 221
 222 static void _arcTo(SwStroke& stroke, int32_t side)
 223 {
 224     auto border = stroke.borders + side;
 225     auto rotate = SIDE_TO_ROTATE(side);
 226     auto total = mathDiff(stroke.angleIn, stroke.angleOut);
 227     if (total == SW_ANGLE_PI) total = -rotate * 2;
 228
 229     _borderArcTo(border, stroke.center, stroke.width, stroke.angleIn + rotate, total, stroke);
 230     border->movable = false;
 231 }
 232
 233
 234 static void _outside(SwStroke& stroke, int32_t side, SwFixed lineLength)
 235 {
 236     constexpr SwFixed MITER_LIMIT = 4 * (1 << 16);
 237
 238     auto border = stroke.borders + side;
 239
 240     if (stroke.join == StrokeJoin::Round) {
 241         _arcTo(stroke, side);
 242     } else {
 243         //this is a mitered (pointed) or beveled (truncated) corner
 244         auto rotate = SIDE_TO_ROTATE(side);
 245         auto bevel = (stroke.join == StrokeJoin::Bevel) ? true : false;
 246         SwFixed phi = 0;
 247         SwFixed thcos = 0;
 248
 249         if (!bevel) {
 250             auto theta = mathDiff(stroke.angleIn, stroke.angleOut);
 251             if (theta == SW_ANGLE_PI) {
 252                 theta = rotate;
 253                 phi = stroke.angleIn;
 254             } else {
 255                 theta /= 2;
 256                 phi = stroke.angleIn + theta + rotate;
 257             }
 258
 259             thcos = mathCos(theta);
 260             auto sigma = mathMultiply(MITER_LIMIT, thcos);
 261
 262             //is miter limit exceeded?
 263             if (sigma < 0x10000L) bevel = true;
 264         }
 265
 266         //this is a bevel (broken angle)
 267         if (bevel) {
 268             SwPoint delta = {static_cast<SwCoord>(stroke.width), 0};
 269             mathRotate(delta, stroke.angleOut + rotate);
 270             SCALE(stroke, delta);
 271             delta += stroke.center;
 272             border->movable = false;
 273             _borderLineTo(border, delta, false);
 274         //this is a miter (intersection)
 275         } else {
 276             auto length = mathDivide(stroke.width, thcos);
 277             SwPoint delta = {static_cast<SwCoord>(length), 0};
 278             mathRotate(delta, phi);
 279             SCALE(stroke, delta);
 280             delta += stroke.center;
 281             _borderLineTo(border, delta, false);
 282
 283             /* Now add and end point
 284                Only needed if not lineto (lineLength is zero for curves) */
 285             if (lineLength == 0) {
 286                 delta = {static_cast<SwCoord>(stroke.width), 0};
 287                 mathRotate(delta, stroke.angleOut + rotate);
 288                 SCALE(stroke, delta);
 289                 delta += stroke.center;
 290                 _borderLineTo(border, delta, false);
 291             }
 292         }
 293     }
 294 }
 295
 296
 297 static void _inside(SwStroke& stroke, int32_t side, SwFixed lineLength)
 298 {
 299     auto border = stroke.borders + side;
 300     auto theta = mathDiff(stroke.angleIn, stroke.angleOut) / 2;
 301     SwPoint delta;
 302     bool intersect = false;
 303
 304     /* Only intersect borders if between two line_to's and both
 305        lines are long enough (line length is zero fur curves). */
 306     if (border->movable && lineLength > 0) {
 307         //compute minimum required length of lines
 308         SwFixed minLength = abs(mathMultiply(stroke.width, mathTan(theta)));
 309         if (stroke.lineLength >= minLength && lineLength >= minLength) intersect = true;
 310     }
 311
 312     auto rotate = SIDE_TO_ROTATE(side);
 313
 314     if (!intersect) {
 315         delta = {static_cast<SwCoord>(stroke.width), 0};
 316         mathRotate(delta, stroke.angleOut + rotate);
 317         SCALE(stroke, delta);
 318         delta += stroke.center;
 319         border->movable = false;
 320     } else {
 321         //compute median angle
 322         auto phi = stroke.angleIn + theta;
 323         auto thcos = mathCos(theta);
 324         delta = {static_cast<SwCoord>(mathDivide(stroke.width, thcos)), 0};
 325         mathRotate(delta, phi + rotate);
 326         SCALE(stroke, delta);
 327         delta += stroke.center;
 328     }
 329
 330     _borderLineTo(border, delta, false);
 331 }
 332
 333
 334 void _processCorner(SwStroke& stroke, SwFixed lineLength)
 335 {
 336     auto turn = mathDiff(stroke.angleIn, stroke.angleOut);
 337
 338     //no specific corner processing is required if the turn is 0
 339     if (turn == 0) return;
 340
 341     //when we turn to the right, the inside side is 0
 342     int32_t inside = 0;
 343
 344     //otherwise, the inside is 1
 345     if (turn < 0) inside = 1;
 346
 347     //process the inside
 348     _inside(stroke, inside, lineLength);
 349
 350     //process the outside
 351     _outside(stroke, 1 - inside, lineLength);
 352 }
 353
 354
 355 void _firstSubPath(SwStroke& stroke, SwFixed startAngle, SwFixed lineLength)
 356 {
 357     SwPoint delta = {static_cast<SwCoord>(stroke.width), 0};
 358     mathRotate(delta, startAngle + SW_ANGLE_PI2);
 359     SCALE(stroke, delta);
 360
 361     auto pt = stroke.center + delta;
 362     auto border = stroke.borders;
 363     _borderMoveTo(border, pt);
 364
 365     pt = stroke.center - delta;
 366     ++border;
 367     _borderMoveTo(border, pt);
 368
 369     /* Save angle, position and line length for last join
 370        lineLength is zero for curves */
 371     stroke.subPathAngle = startAngle;
 372     stroke.firstPt = false;
 373     stroke.subPathLineLength = lineLength;
 374 }
 375
 376
 377 static void _lineTo(SwStroke& stroke, const SwPoint& to)
 378 {
 379     auto delta = to - stroke.center;
 380
 381     //a zero-length lineto is a no-op; avoid creating a spurious corner
 382     if (delta.zero()) return;
 383
 384     //compute length of line
 385     auto lineLength =  mathLength(delta);
 386     auto angle = mathAtan(delta);
 387
 388     delta = {static_cast<SwCoord>(stroke.width), 0};
 389     mathRotate(delta, angle + SW_ANGLE_PI2);
 390     SCALE(stroke, delta);
 391
 392     //process corner if necessary
 393     if (stroke.firstPt) {
 394         /* This is the first segment of a subpath. We need to add a point to each border
 395         at their respective starting point locations. */
 396         _firstSubPath(stroke, angle, lineLength);
 397     } else {
 398         //process the current corner
 399         stroke.angleOut = angle;
 400         _processCorner(stroke, lineLength);
 401     }
 402
 403     //now add a line segment to both the inside and outside paths
 404     auto border = stroke.borders;
 405     auto side = 1;
 406
 407     while (side >= 0) {
 408         auto pt = to + delta;
 409
 410         //the ends of lineto borders are movable
 411         _borderLineTo(border, pt, true);
 412
 413         delta.x = -delta.x;
 414         delta.y = -delta.y;
 415
 416         --side;
 417         ++border;
 418     }
 419
 420     stroke.angleIn = angle;
 421     stroke.center = to;
 422     stroke.lineLength = lineLength;
 423 }
 424
 425
 426 static void _cubicTo(SwStroke& stroke, const SwPoint& ctrl1, const SwPoint& ctrl2, const SwPoint& to)
 427 {
 428     /* if all control points are coincident, this is a no-op;
 429        avoid creating a spurious corner */
 430     if ((stroke.center - ctrl1).small() && (ctrl1 - ctrl2).small() && (ctrl2 - to).small()) {
 431         stroke.center = to;
 432         return;
 433     }
 434
 435     SwPoint bezStack[37];   //TODO: static?
 436     auto limit = bezStack + 32;
 437     auto arc = bezStack;
 438     auto firstArc = true;
 439     arc[0] = to;
 440     arc[1] = ctrl2;
 441     arc[2] = ctrl1;
 442     arc[3] = stroke.center;
 443
 444     while (arc >= bezStack) {
 445         SwFixed angleIn, angleOut, angleMid;
 446
 447         //initialize with current direction
 448         angleIn = angleOut = angleMid = stroke.angleIn;
 449
 450         if (arc < limit && !mathSmallCubic(arc, angleIn, angleMid, angleOut)) {
 451             if (stroke.firstPt) stroke.angleIn = angleIn;
 452             mathSplitCubic(arc);
 453             arc += 3;
 454             continue;
 455         }
 456
 457         if (firstArc) {
 458             firstArc = false;
 459             //process corner if necessary
 460             if (stroke.firstPt) {
 461                 _firstSubPath(stroke, angleIn, 0);
 462             } else {
 463                 stroke.angleOut = angleIn;
 464                 _processCorner(stroke, 0);
 465             }
 466         } else if (abs(mathDiff(stroke.angleIn, angleIn)) > (SW_ANGLE_PI / 8) / 4) {
 467             //if the deviation from one arc to the next is too great add a round corner
 468             stroke.center = arc[3];
 469             stroke.angleOut = angleIn;
 470             stroke.join = StrokeJoin::Round;
 471
 472             _processCorner(stroke, 0);
 473
 474             //reinstate line join style
 475             stroke.join = stroke.joinSaved;
 476         }
 477
 478         //the arc's angle is small enough; we can add it directly to each border
 479         auto theta1 = mathDiff(angleIn, angleMid) / 2;
 480         auto theta2 = mathDiff(angleMid, angleOut) / 2;
 481         auto phi1 = mathMean(angleIn, angleMid);
 482         auto phi2 = mathMean(angleMid, angleOut);
 483         auto length1 = mathDivide(stroke.width, mathCos(theta1));
 484         auto length2 = mathDivide(stroke.width, mathCos(theta2));
 485         SwFixed alpha0 = 0;
 486
 487         //compute direction of original arc
 488         if (stroke.handleWideStrokes) {
 489             alpha0 = mathAtan(arc[0] - arc[3]);
 490         }
 491
 492         auto border = stroke.borders;
 493         int32_t side = 0;
 494
 495         while (side <= 1)
 496         {
 497             auto rotate = SIDE_TO_ROTATE(side);
 498
 499             //compute control points
 500             SwPoint _ctrl1 = {static_cast<SwCoord>(length1), 0};
 501             mathRotate(_ctrl1, phi1 + rotate);
 502             SCALE(stroke, _ctrl1);
 503             _ctrl1 += arc[2];
 504
 505             SwPoint _ctrl2 = {static_cast<SwCoord>(length2), 0};
 506             mathRotate(_ctrl2, phi2 + rotate);
 507             SCALE(stroke, _ctrl2);
 508             _ctrl2 += arc[1];
 509
 510             //compute end point
 511             SwPoint _end = {static_cast<SwCoord>(stroke.width), 0};
 512             mathRotate(_end, angleOut + rotate);
 513             SCALE(stroke, _end);
 514             _end += arc[0];
 515
 516             if (stroke.handleWideStrokes) {
 517
 518                 /* determine whether the border radius is greater than the radius of
 519                    curvature of the original arc */
 520                 auto _start = border->pts[border->ptsCnt - 1];
 521                 auto alpha1 = mathAtan(_end - _start);
 522
 523                 //is the direction of the border arc opposite to that of the original arc?
 524                 if (abs(mathDiff(alpha0, alpha1)) > SW_ANGLE_PI / 2) {
 525
 526                     //use the sine rule to find the intersection point
 527                     auto beta = mathAtan(arc[3] - _start);
 528                     auto gamma = mathAtan(arc[0] - _end);
 529                     auto bvec = _end - _start;
 530                     auto blen = mathLength(bvec);
 531                     auto sinA = abs(mathSin(alpha1 - gamma));
 532                     auto sinB = abs(mathSin(beta - gamma));
 533                     auto alen = mathMulDiv(blen, sinA, sinB);
 534
 535                     SwPoint delta = {static_cast<SwCoord>(alen), 0};
 536                     mathRotate(delta, beta);
 537                     delta += _start;
 538
 539                     //circumnavigate the negative sector backwards
 540                     border->movable = false;
 541                     _borderLineTo(border, delta, false);
 542                     _borderLineTo(border, _end, false);
 543                     _borderCubicTo(border, _ctrl2, _ctrl1, _start);
 544
 545                     //and then move to the endpoint
 546                     _borderLineTo(border, _end, false);
 547
 548                     ++side;
 549                     ++border;
 550                     continue;
 551                 }
 552
 553             //else fall through
 554             }
 555             _borderCubicTo(border, _ctrl1, _ctrl2, _end);
 556             ++side;
 557             ++border;
 558         }
 559         arc -= 3;
 560         stroke.angleIn = angleOut;
 561     }
 562     stroke.center = to;
 563 }
 564
 565
 566 static void _addCap(SwStroke& stroke, SwFixed angle, int32_t side)
 567 {
 568     if (stroke.cap == StrokeCap::Square) {
 569         auto rotate = SIDE_TO_ROTATE(side);
 570         auto border = stroke.borders + side;
 571
 572         SwPoint delta = {static_cast<SwCoord>(stroke.width), 0};
 573         mathRotate(delta, angle);
 574         SCALE(stroke, delta);
 575
 576         SwPoint delta2 = {static_cast<SwCoord>(stroke.width), 0};
 577         mathRotate(delta2, angle + rotate);
 578         SCALE(stroke, delta2);
 579         delta += stroke.center + delta2;
 580
 581         _borderLineTo(border, delta, false);
 582
 583         delta = {static_cast<SwCoord>(stroke.width), 0};
 584         mathRotate(delta, angle);
 585         SCALE(stroke, delta);
 586
 587         delta2 = {static_cast<SwCoord>(stroke.width), 0};
 588         mathRotate(delta2, angle - rotate);
 589         SCALE(stroke, delta2);
 590         delta += delta2 + stroke.center;
 591
 592         _borderLineTo(border, delta, false);
 593
 594     } else if (stroke.cap == StrokeCap::Round) {
 595
 596         stroke.angleIn = angle;
 597         stroke.angleOut = angle + SW_ANGLE_PI;
 598         _arcTo(stroke, side);
 599         return;
 600
 601     } else {  //Butt
 602         auto rotate = SIDE_TO_ROTATE(side);
 603         auto border = stroke.borders + side;
 604
 605         SwPoint delta = {static_cast<SwCoord>(stroke.width), 0};
 606         mathRotate(delta, angle + rotate);
 607         SCALE(stroke, delta);
 608         delta += stroke.center;
 609
 610         _borderLineTo(border, delta, false);
 611
 612         delta = {static_cast<SwCoord>(stroke.width), 0};
 613         mathRotate(delta, angle - rotate);
 614         SCALE(stroke, delta);
 615         delta += stroke.center;
 616
 617         _borderLineTo(border, delta, false);
 618     }
 619 }
 620
 621
 622 static void _addReverseLeft(SwStroke& stroke, bool opened)
 623 {
 624     auto right = stroke.borders + 0;
 625     auto left = stroke.borders + 1;
 626     auto newPts = left->ptsCnt - left->start;
 627
 628     if (newPts <= 0) return;
 629
 630     _growBorder(right, newPts);
 631
 632     auto dstPt = right->pts + right->ptsCnt;
 633     auto dstTag = right->tags + right->ptsCnt;
 634     auto srcPt = left->pts + left->ptsCnt - 1;
 635     auto srcTag = left->tags + left->ptsCnt - 1;
 636
 637     while (srcPt >= left->pts + left->start) {
 638         *dstPt = *srcPt;
 639         *dstTag = *srcTag;
 640
 641         if (opened) {
 642              dstTag[0] &= ~(SW_STROKE_TAG_BEGIN | SW_STROKE_TAG_END);
 643         } else {
 644             //switch begin/end tags if necessary
 645             auto ttag = dstTag[0] & (SW_STROKE_TAG_BEGIN | SW_STROKE_TAG_END);
 646             if (ttag == SW_STROKE_TAG_BEGIN || ttag == SW_STROKE_TAG_END)
 647               dstTag[0] ^= (SW_STROKE_TAG_BEGIN | SW_STROKE_TAG_END);
 648         }
 649
 650         --srcPt;
 651         --srcTag;
 652         ++dstPt;
 653         ++dstTag;
 654     }
 655
 656     left->ptsCnt = left->start;
 657     right->ptsCnt += newPts;
 658     right->movable = false;
 659     left->movable = false;
 660 }
 661
 662
 663 static void _beginSubPath(SwStroke& stroke, const SwPoint& to, bool closed)
 664 {
 665     /* We cannot process the first point because there is not enough
 666        information regarding its corner/cap. Later, it will be processed
 667        in the _endSubPath() */
 668
 669     stroke.firstPt = true;
 670     stroke.center = to;
 671     stroke.closedSubPath = closed;
 672
 673     /* Determine if we need to check whether the border radius is greater
 674        than the radius of curvature of a curve, to handle this case specially.
 675        This is only required if bevel joins or butt caps may be created because
 676        round & miter joins and round & square caps cover the nagative sector
 677        created with wide strokes. */
 678     if ((stroke.join != StrokeJoin::Round) || (!stroke.closedSubPath && stroke.cap == StrokeCap::Butt))
 679         stroke.handleWideStrokes = true;
 680     else
 681         stroke.handleWideStrokes = false;
 682
 683     stroke.ptStartSubPath = to;
 684     stroke.angleIn = 0;
 685 }
 686
 687
 688 static void _endSubPath(SwStroke& stroke)
 689 {
 690     if (stroke.closedSubPath) {
 691         //close the path if needed
 692         if (stroke.center != stroke.ptStartSubPath)
 693             _lineTo(stroke, stroke.ptStartSubPath);
 694
 695         //process the corner
 696         stroke.angleOut = stroke.subPathAngle;
 697         auto turn = mathDiff(stroke.angleIn, stroke.angleOut);
 698
 699         //No specific corner processing is required if the turn is 0
 700         if (turn != 0) {
 701
 702             //when we turn to the right, the inside is 0
 703             int32_t inside = 0;
 704
 705             //otherwise, the inside is 1
 706             if (turn < 0) inside = 1;
 707
 708             _inside(stroke, inside, stroke.subPathLineLength);        //inside
 709             _outside(stroke, 1 - inside, stroke.subPathLineLength);   //outside
 710         }
 711
 712         _borderClose(stroke.borders + 0, false);
 713         _borderClose(stroke.borders + 1, true);
 714     } else {
 715         auto right = stroke.borders;
 716
 717         /* all right, this is an opened path, we need to add a cap between
 718            right & left, add the reverse of left, then add a final cap
 719            between left & right */
 720         _addCap(stroke, stroke.angleIn, 0);
 721
 722         //add reversed points from 'left' to 'right'
 723         _addReverseLeft(stroke, true);
 724
 725         //now add the final cap
 726         stroke.center = stroke.ptStartSubPath;
 727         _addCap(stroke, stroke.subPathAngle + SW_ANGLE_PI, 0);
 728
 729         /* now end the right subpath accordingly. The left one is rewind
 730            and deosn't need further processing */
 731         _borderClose(right, false);
 732     }
 733 }
 734
 735
 736 static void _getCounts(SwStrokeBorder* border, uint32_t& ptsCnt, uint32_t& cntrsCnt)
 737 {
 738     auto count = border->ptsCnt;
 739     auto tags = border->tags;
 740     uint32_t _ptsCnt = 0;
 741     uint32_t _cntrsCnt = 0;
 742     bool inCntr = false;
 743
 744     while (count > 0) {
 745         if (tags[0] & SW_STROKE_TAG_BEGIN) {
 746             if (inCntr) goto fail;
 747             inCntr = true;
 748         } else if (!inCntr) goto fail;
 749
 750         if (tags[0] & SW_STROKE_TAG_END) {
 751             inCntr = false;
 752             ++_cntrsCnt;
 753         }
 754         --count;
 755         ++_ptsCnt;
 756         ++tags;
 757     }
 758
 759     if (inCntr) goto fail;
 760
 761     ptsCnt = _ptsCnt;
 762     cntrsCnt = _cntrsCnt;
 763
 764     return;
 765
 766 fail:
 767     ptsCnt = 0;
 768     cntrsCnt = 0;
 769 }
 770
 771
 772 static void _exportBorderOutline(const SwStroke& stroke, SwOutline* outline, uint32_t side)
 773 {
 774     auto border = stroke.borders + side;
 775
 776     if (border->ptsCnt == 0) return;  //invalid border
 777
 778     memcpy(outline->pts + outline->ptsCnt, border->pts, border->ptsCnt * sizeof(SwPoint));
 779
 780     auto cnt = border->ptsCnt;
 781     auto src = border->tags;
 782     auto tags = outline->types + outline->ptsCnt;
 783     auto cntrs = outline->cntrs + outline->cntrsCnt;
 784     auto idx = outline->ptsCnt;
 785
 786     while (cnt > 0) {
 787
 788         if (*src & SW_STROKE_TAG_POINT) *tags = SW_CURVE_TYPE_POINT;
 789         else if (*src & SW_STROKE_TAG_CUBIC) *tags = SW_CURVE_TYPE_CUBIC;
 790         else {
 791             //LOG: What type of stroke outline??
 792         }
 793
 794         if (*src & SW_STROKE_TAG_END) {
 795             *cntrs = idx;
 796             ++cntrs;
 797             ++outline->cntrsCnt;
 798         }
 799         ++src;
 800         ++tags;
 801         ++idx;
 802         --cnt;
 803     }
 804     outline->ptsCnt = outline->ptsCnt + border->ptsCnt;
 805 }
 806
 807
 808 /************************************************************************/
 809 /* External Class Implementation                                        */
 810 /************************************************************************/
 811
 812 void strokeFree(SwStroke* stroke)
 813 {
 814     if (!stroke) return;
 815
 816     //free borders
 817     if (stroke->borders[0].pts) free(stroke->borders[0].pts);
 818     if (stroke->borders[0].tags) free(stroke->borders[0].tags);
 819     if (stroke->borders[1].pts) free(stroke->borders[1].pts);
 820     if (stroke->borders[1].tags) free(stroke->borders[1].tags);
 821
 822     fillFree(stroke->fill);
 823     stroke->fill = nullptr;
 824
 825     free(stroke);
 826 }
 827
 828
 829 void strokeReset(SwStroke* stroke, const Shape* sdata, const Matrix* transform)
 830 {
 831     if (transform) {
 832         stroke->sx = sqrtf(powf(transform->e11, 2.0f) + powf(transform->e21, 2.0f));
 833         stroke->sy = sqrtf(powf(transform->e12, 2.0f) + powf(transform->e22, 2.0f));
 834     } else {
 835         stroke->sx = stroke->sy = 1.0f;
 836     }
 837
 838     stroke->width = HALF_STROKE(sdata->strokeWidth());
 839     stroke->cap = sdata->strokeCap();
 840
 841     //Save line join: it can be temporarily changed when stroking curves...
 842     stroke->joinSaved = stroke->join = sdata->strokeJoin();
 843
 844     stroke->borders[0].ptsCnt = 0;
 845     stroke->borders[0].start = -1;
 846     stroke->borders[1].ptsCnt = 0;
 847     stroke->borders[1].start = -1;
 848 }
 849
 850
 851 bool strokeParseOutline(SwStroke* stroke, const SwOutline& outline)
 852 {
 853     uint32_t first = 0;
 854
 855     for (uint32_t i = 0; i < outline.cntrsCnt; ++i) {
 856         auto last = outline.cntrs[i];  //index of last point in contour
 857         auto limit = outline.pts + last;
 858
 859         //Skip empty points
 860         if (last <= first) {
 861             first = last + 1;
 862             continue;
 863         }
 864
 865         auto start = outline.pts[first];
 866         auto pt = outline.pts + first;
 867         auto types = outline.types + first;
 868         auto type = types[0];
 869
 870         //A contour cannot start with a cubic control point
 871         if (type == SW_CURVE_TYPE_CUBIC) return false;
 872
 873         auto closed =  outline.closed ? outline.closed[i]: false;
 874
 875         _beginSubPath(*stroke, start, closed);
 876
 877         while (pt < limit) {
 878             ++pt;
 879             ++types;
 880
 881             //emit a signel line_to
 882             if (types[0] == SW_CURVE_TYPE_POINT) {
 883                 _lineTo(*stroke, *pt);
 884             //types cubic
 885             } else {
 886                 if (pt + 1 > limit || types[1] != SW_CURVE_TYPE_CUBIC) return false;
 887
 888                 pt += 2;
 889                 types += 2;
 890
 891                 if (pt <= limit) {
 892                     _cubicTo(*stroke, pt[-2], pt[-1], pt[0]);
 893                     continue;
 894                 }
 895                 _cubicTo(*stroke, pt[-2], pt[-1], start);
 896                 goto close;
 897             }
 898         }
 899
 900     close:
 901         if (!stroke->firstPt) _endSubPath(*stroke);
 902         first = last + 1;
 903     }
 904     return true;
 905 }
 906
 907
 908 SwOutline* strokeExportOutline(SwStroke* stroke, SwMpool* mpool, unsigned tid)
 909 {
 910     uint32_t count1, count2, count3, count4;
 911
 912     _getCounts(stroke->borders + 0, count1, count2);
 913     _getCounts(stroke->borders + 1, count3, count4);
 914
 915     auto ptsCnt = count1 + count3;
 916     auto cntrsCnt = count2 + count4;
 917
 918     auto outline = mpoolReqStrokeOutline(mpool, tid);
 919     if (outline->reservedPtsCnt < ptsCnt) {
 920         outline->pts = static_cast<SwPoint*>(realloc(outline->pts, sizeof(SwPoint) * ptsCnt));
 921         outline->types = static_cast<uint8_t*>(realloc(outline->types, sizeof(uint8_t) * ptsCnt));
 922         outline->reservedPtsCnt = ptsCnt;
 923     }
 924     if (outline->reservedCntrsCnt < cntrsCnt) {
 925         outline->cntrs = static_cast<uint32_t*>(realloc(outline->cntrs, sizeof(uint32_t) * cntrsCnt));
 926         outline->reservedCntrsCnt = cntrsCnt;
 927     }
 928
 929     _exportBorderOutline(*stroke, outline, 0);  //left
 930     _exportBorderOutline(*stroke, outline, 1);  //right
 931
 932     return outline;
 933 }