src/lib/sw_engine/tvgSwShape.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 #include "tvgSwCommon.h"
  23 #include "tvgBezier.h"
  24
  25 /************************************************************************/
  26 /* Internal Class Implementation                                        */
  27 /************************************************************************/
  28
  29 struct Line
  30 {
  31     Point pt1;
  32     Point pt2;
  33 };
  34
  35
  36 static float _lineLength(const Point& pt1, const Point& pt2)
  37 {
  38     /* approximate sqrt(x*x + y*y) using alpha max plus beta min algorithm.
  39        With alpha = 1, beta = 3/8, giving results with the largest error less
  40        than 7% compared to the exact value. */
  41     Point diff = {pt2.x - pt1.x, pt2.y - pt1.y};
  42     if (diff.x < 0) diff.x = -diff.x;
  43     if (diff.y < 0) diff.y = -diff.y;
  44     return (diff.x > diff.y) ? (diff.x + diff.y * 0.375f) : (diff.y + diff.x * 0.375f);
  45 }
  46
  47
  48 static void _lineSplitAt(const Line& cur, float at, Line& left, Line& right)
  49 {
  50     auto len = _lineLength(cur.pt1, cur.pt2);
  51     auto dx = ((cur.pt2.x - cur.pt1.x) / len) * at;
  52     auto dy = ((cur.pt2.y - cur.pt1.y) / len) * at;
  53     left.pt1 = cur.pt1;
  54     left.pt2.x = left.pt1.x + dx;
  55     left.pt2.y = left.pt1.y + dy;
  56     right.pt1 = left.pt2;
  57     right.pt2 = cur.pt2;
  58 }
  59
  60
  61 static void _growOutlineContour(SwOutline& outline, uint32_t n)
  62 {
  63     if (outline.reservedCntrsCnt >= outline.cntrsCnt + n) return;
  64     outline.reservedCntrsCnt = outline.cntrsCnt + n;
  65     outline.cntrs = static_cast<uint32_t*>(realloc(outline.cntrs, outline.reservedCntrsCnt * sizeof(uint32_t)));
  66 }
  67
  68
  69 static void _growOutlinePoint(SwOutline& outline, uint32_t n)
  70 {
  71     if (outline.reservedPtsCnt >= outline.ptsCnt + n) return;
  72     outline.reservedPtsCnt = outline.ptsCnt + n;
  73     outline.pts = static_cast<SwPoint*>(realloc(outline.pts, outline.reservedPtsCnt * sizeof(SwPoint)));
  74     outline.types = static_cast<uint8_t*>(realloc(outline.types, outline.reservedPtsCnt * sizeof(uint8_t)));
  75 }
  76
  77
  78 static void _outlineEnd(SwOutline& outline)
  79 {
  80     _growOutlineContour(outline, 1);
  81     if (outline.ptsCnt > 0) {
  82         outline.cntrs[outline.cntrsCnt] = outline.ptsCnt - 1;
  83         ++outline.cntrsCnt;
  84     }
  85 }
  86
  87
  88 static void _outlineMoveTo(SwOutline& outline, const Point* to, const Matrix* transform)
  89 {
  90     _growOutlinePoint(outline, 1);
  91
  92     outline.pts[outline.ptsCnt] = mathTransform(to, transform);
  93     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_POINT;
  94
  95     if (outline.ptsCnt > 0) {
  96         _growOutlineContour(outline, 1);
  97         outline.cntrs[outline.cntrsCnt] = outline.ptsCnt - 1;
  98         ++outline.cntrsCnt;
  99     }
 100
 101     ++outline.ptsCnt;
 102 }
 103
 104
 105 static void _outlineLineTo(SwOutline& outline, const Point* to, const Matrix* transform)
 106 {
 107     _growOutlinePoint(outline, 1);
 108
 109     outline.pts[outline.ptsCnt] = mathTransform(to, transform);
 110     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_POINT;
 111     ++outline.ptsCnt;
 112 }
 113
 114
 115 static void _outlineCubicTo(SwOutline& outline, const Point* ctrl1, const Point* ctrl2, const Point* to, const Matrix* transform)
 116 {
 117     _growOutlinePoint(outline, 3);
 118
 119     outline.pts[outline.ptsCnt] = mathTransform(ctrl1, transform);
 120     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_CUBIC;
 121     ++outline.ptsCnt;
 122
 123     outline.pts[outline.ptsCnt] = mathTransform(ctrl2, transform);
 124     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_CUBIC;
 125     ++outline.ptsCnt;
 126
 127     outline.pts[outline.ptsCnt] = mathTransform(to, transform);
 128     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_POINT;
 129     ++outline.ptsCnt;
 130 }
 131
 132
 133 static void _outlineClose(SwOutline& outline)
 134 {
 135     uint32_t i = 0;
 136
 137     if (outline.cntrsCnt > 0) {
 138         i = outline.cntrs[outline.cntrsCnt - 1] + 1;
 139     } else {
 140         i = 0;   //First Path
 141     }
 142
 143     //Make sure there is at least one point in the current path
 144     if (outline.ptsCnt == i) {
 145         outline.opened = true;
 146         return;
 147     }
 148
 149     //Close the path
 150     _growOutlinePoint(outline, 1);
 151
 152     outline.pts[outline.ptsCnt] = outline.pts[i];
 153     outline.types[outline.ptsCnt] = SW_CURVE_TYPE_POINT;
 154     ++outline.ptsCnt;
 155
 156     outline.opened = false;
 157 }
 158
 159
 160 static void _dashLineTo(SwDashStroke& dash, const Point* to, const Matrix* transform)
 161 {
 162     _growOutlinePoint(*dash.outline, dash.outline->ptsCnt >> 1);
 163     _growOutlineContour(*dash.outline, dash.outline->cntrsCnt >> 1);
 164
 165     Line cur = {dash.ptCur, *to};
 166     auto len = _lineLength(cur.pt1, cur.pt2);
 167
 168     if (len < dash.curLen) {
 169         dash.curLen -= len;
 170         if (!dash.curOpGap) {
 171             _outlineMoveTo(*dash.outline, &dash.ptCur, transform);
 172             _outlineLineTo(*dash.outline, to, transform);
 173         }
 174     } else {
 175         while (len > dash.curLen) {
 176             len -= dash.curLen;
 177             Line left, right;
 178             _lineSplitAt(cur, dash.curLen, left, right);;
 179             dash.curIdx = (dash.curIdx + 1) % dash.cnt;
 180             if (!dash.curOpGap) {
 181                 _outlineMoveTo(*dash.outline, &left.pt1, transform);
 182                 _outlineLineTo(*dash.outline, &left.pt2, transform);
 183             }
 184             dash.curLen = dash.pattern[dash.curIdx];
 185             dash.curOpGap = !dash.curOpGap;
 186             cur = right;
 187             dash.ptCur = cur.pt1;
 188         }
 189         //leftovers
 190         dash.curLen -= len;
 191         if (!dash.curOpGap) {
 192             _outlineMoveTo(*dash.outline, &cur.pt1, transform);
 193             _outlineLineTo(*dash.outline, &cur.pt2, transform);
 194         }
 195         if (dash.curLen < 1 && TO_SWCOORD(len) > 1) {
 196             //move to next dash
 197             dash.curIdx = (dash.curIdx + 1) % dash.cnt;
 198             dash.curLen = dash.pattern[dash.curIdx];
 199             dash.curOpGap = !dash.curOpGap;
 200         }
 201     }
 202     dash.ptCur = *to;
 203 }
 204
 205
 206 static void _dashCubicTo(SwDashStroke& dash, const Point* ctrl1, const Point* ctrl2, const Point* to, const Matrix* transform)
 207 {
 208     _growOutlinePoint(*dash.outline, dash.outline->ptsCnt >> 1);
 209     _growOutlineContour(*dash.outline, dash.outline->cntrsCnt >> 1);
 210
 211     Bezier cur = {dash.ptCur, *ctrl1, *ctrl2, *to};
 212     auto len = bezLength(cur);
 213
 214     if (len < dash.curLen) {
 215         dash.curLen -= len;
 216         if (!dash.curOpGap) {
 217             _outlineMoveTo(*dash.outline, &dash.ptCur, transform);
 218             _outlineCubicTo(*dash.outline, ctrl1, ctrl2, to, transform);
 219         }
 220     } else {
 221         while (len > dash.curLen) {
 222             Bezier left, right;
 223             len -= dash.curLen;
 224             bezSplitAt(cur, dash.curLen, left, right);
 225             dash.curIdx = (dash.curIdx + 1) % dash.cnt;
 226             if (!dash.curOpGap) {
 227                 _outlineMoveTo(*dash.outline, &left.start, transform);
 228                 _outlineCubicTo(*dash.outline, &left.ctrl1, &left.ctrl2, &left.end, transform);
 229             }
 230             dash.curLen = dash.pattern[dash.curIdx];
 231             dash.curOpGap = !dash.curOpGap;
 232             cur = right;
 233             dash.ptCur = right.start;
 234         }
 235         //leftovers
 236         dash.curLen -= len;
 237         if (!dash.curOpGap) {
 238             _outlineMoveTo(*dash.outline, &cur.start, transform);
 239             _outlineCubicTo(*dash.outline, &cur.ctrl1, &cur.ctrl2, &cur.end, transform);
 240         }
 241         if (dash.curLen < 1 && TO_SWCOORD(len) > 1) {
 242             //move to next dash
 243             dash.curIdx = (dash.curIdx + 1) % dash.cnt;
 244             dash.curLen = dash.pattern[dash.curIdx];
 245             dash.curOpGap = !dash.curOpGap;
 246         }
 247     }
 248     dash.ptCur = *to;
 249 }
 250
 251
 252 static SwOutline* _genDashOutline(const Shape* sdata, const Matrix* transform)
 253 {
 254     const PathCommand* cmds = nullptr;
 255     auto cmdCnt = sdata->pathCommands(&cmds);
 256
 257     const Point* pts = nullptr;
 258     auto ptsCnt = sdata->pathCoords(&pts);
 259
 260     //No actual shape data
 261     if (cmdCnt == 0 || ptsCnt == 0) return nullptr;
 262
 263     SwDashStroke dash;
 264     dash.curIdx = 0;
 265     dash.curLen = 0;
 266     dash.ptStart = {0, 0};
 267     dash.ptCur = {0, 0};
 268     dash.curOpGap = false;
 269
 270     const float* pattern;
 271     dash.cnt = sdata->strokeDash(&pattern);
 272     if (dash.cnt == 0) return nullptr;
 273
 274     //OPTMIZE ME: Use mempool???
 275     dash.pattern = const_cast<float*>(pattern);
 276     dash.outline = static_cast<SwOutline*>(calloc(1, sizeof(SwOutline)));
 277     dash.outline->opened = true;
 278
 279     //smart reservation
 280     auto outlinePtsCnt = 0;
 281     auto outlineCntrsCnt = 0;
 282
 283     for (uint32_t i = 0; i < cmdCnt; ++i) {
 284         switch(*(cmds + i)) {
 285             case PathCommand::Close: {
 286                 ++outlinePtsCnt;
 287                 break;
 288             }
 289             case PathCommand::MoveTo: {
 290                 ++outlineCntrsCnt;
 291                 ++outlinePtsCnt;
 292                 break;
 293             }
 294             case PathCommand::LineTo: {
 295                 ++outlinePtsCnt;
 296                 break;
 297             }
 298             case PathCommand::CubicTo: {
 299                 outlinePtsCnt += 3;
 300                 break;
 301             }
 302         }
 303     }
 304
 305     ++outlinePtsCnt;    //for close
 306     ++outlineCntrsCnt;  //for end
 307
 308     //Reserve Approximitely 20x...
 309     _growOutlinePoint(*dash.outline, outlinePtsCnt * 20);
 310     _growOutlineContour(*dash.outline, outlineCntrsCnt * 20);
 311
 312     while (cmdCnt-- > 0) {
 313         switch(*cmds) {
 314             case PathCommand::Close: {
 315                 _dashLineTo(dash, &dash.ptStart, transform);
 316                 break;
 317             }
 318             case PathCommand::MoveTo: {
 319                 //reset the dash
 320                 dash.curIdx = 0;
 321                 dash.curLen = *dash.pattern;
 322                 dash.curOpGap = false;
 323                 dash.ptStart = dash.ptCur = *pts;
 324                 ++pts;
 325                 break;
 326             }
 327             case PathCommand::LineTo: {
 328                 _dashLineTo(dash, pts, transform);
 329                 ++pts;
 330                 break;
 331             }
 332             case PathCommand::CubicTo: {
 333                 _dashCubicTo(dash, pts, pts + 1, pts + 2, transform);
 334                 pts += 3;
 335                 break;
 336             }
 337         }
 338         ++cmds;
 339     }
 340
 341     _outlineEnd(*dash.outline);
 342
 343     return dash.outline;
 344 }
 345
 346
 347 static bool _fastTrack(const SwOutline* outline)
 348 {
 349     //Fast Track: Othogonal rectangle?
 350     if (outline->ptsCnt != 5) return false;
 351
 352     auto pt1 = outline->pts + 0;
 353     auto pt2 = outline->pts + 1;
 354     auto pt3 = outline->pts + 2;
 355     auto pt4 = outline->pts + 3;
 356
 357     auto a = SwPoint{pt1->x, pt3->y};
 358     auto b = SwPoint{pt3->x, pt1->y};
 359
 360     if ((*pt2 == a && *pt4 == b) || (*pt2 == b && *pt4 == a)) return true;
 361
 362     return false;
 363 }
 364
 365
 366
 367 static bool _genOutline(SwShape* shape, const Shape* sdata, const Matrix* transform, SwMpool* mpool, unsigned tid)
 368 {
 369     const PathCommand* cmds = nullptr;
 370     auto cmdCnt = sdata->pathCommands(&cmds);
 371
 372     const Point* pts = nullptr;
 373     auto ptsCnt = sdata->pathCoords(&pts);
 374
 375     //No actual shape data
 376     if (cmdCnt == 0 || ptsCnt == 0) return false;
 377
 378     //smart reservation
 379     auto outlinePtsCnt = 0;
 380     auto outlineCntrsCnt = 0;
 381
 382     for (uint32_t i = 0; i < cmdCnt; ++i) {
 383         switch(*(cmds + i)) {
 384             case PathCommand::Close: {
 385                 ++outlinePtsCnt;
 386                 break;
 387             }
 388             case PathCommand::MoveTo: {
 389                 ++outlineCntrsCnt;
 390                 ++outlinePtsCnt;
 391                 break;
 392             }
 393             case PathCommand::LineTo: {
 394                 ++outlinePtsCnt;
 395                 break;
 396             }
 397             case PathCommand::CubicTo: {
 398                 outlinePtsCnt += 3;
 399                 break;
 400             }
 401         }
 402     }
 403
 404     ++outlinePtsCnt;    //for close
 405     ++outlineCntrsCnt;  //for end
 406
 407     shape->outline = mpoolReqOutline(mpool, tid);
 408     auto outline = shape->outline;
 409     outline->opened = true;
 410
 411     _growOutlinePoint(*outline, outlinePtsCnt);
 412     _growOutlineContour(*outline, outlineCntrsCnt);
 413
 414     auto closed = false;
 415
 416     //Generate Outlines
 417     while (cmdCnt-- > 0) {
 418         switch(*cmds) {
 419             case PathCommand::Close: {
 420                 _outlineClose(*outline);
 421                 closed = true;
 422                 break;
 423             }
 424             case PathCommand::MoveTo: {
 425                 _outlineMoveTo(*outline, pts, transform);
 426                 ++pts;
 427                 break;
 428             }
 429             case PathCommand::LineTo: {
 430                 _outlineLineTo(*outline, pts, transform);
 431                 ++pts;
 432                 break;
 433             }
 434             case PathCommand::CubicTo: {
 435                 _outlineCubicTo(*outline, pts, pts + 1, pts + 2, transform);
 436                 pts += 3;
 437                 break;
 438             }
 439         }
 440         ++cmds;
 441     }
 442
 443     _outlineEnd(*outline);
 444
 445     if (closed) outline->opened = false;
 446
 447     outline->fillRule = sdata->fillRule();
 448     shape->outline = outline;
 449
 450     return true;
 451 }
 452
 453
 454 /************************************************************************/
 455 /* External Class Implementation                                        */
 456 /************************************************************************/
 457
 458 bool shapePrepare(SwShape* shape, const Shape* sdata, const Matrix* transform,  const SwBBox& clipRegion, SwBBox& renderRegion, SwMpool* mpool, unsigned tid)
 459 {
 460     if (!_genOutline(shape, sdata, transform, mpool, tid)) return false;
 461     if (!mathUpdateOutlineBBox(shape->outline, clipRegion, renderRegion)) return false;
 462
 463     //Keep it for Rasterization Region
 464     shape->bbox = renderRegion;
 465
 466     //Check valid region
 467     if (renderRegion.max.x - renderRegion.min.x < 1 && renderRegion.max.y - renderRegion.min.y < 1) return false;
 468
 469     //Check boundary
 470     if (renderRegion.min.x >= clipRegion.max.x || renderRegion.min.y >= clipRegion.max.y ||
 471         renderRegion.max.x <= clipRegion.min.x || renderRegion.max.y <= clipRegion.min.y) return false;
 472
 473     return true;
 474 }
 475
 476
 477 bool shapePrepared(const SwShape* shape)
 478 {
 479     return shape->rle ? true : false;
 480 }
 481
 482
 483 bool shapeGenRle(SwShape* shape, TVG_UNUSED const Shape* sdata, bool antiAlias, bool hasComposite)
 484 {
 485     //FIXME: Should we draw it?
 486     //Case: Stroke Line
 487     //if (shape.outline->opened) return true;
 488
 489     //Case A: Fast Track Rectangle Drawing
 490     if (!hasComposite && (shape->rect = _fastTrack(shape->outline))) return true;
 491     //Case B: Normale Shape RLE Drawing
 492     if ((shape->rle = rleRender(shape->rle, shape->outline, shape->bbox, antiAlias))) return true;
 493
 494     return false;
 495 }
 496
 497
 498 void shapeDelOutline(SwShape* shape, SwMpool* mpool, uint32_t tid)
 499 {
 500     mpoolRetOutline(mpool, tid);
 501     shape->outline = nullptr;
 502 }
 503
 504
 505 void shapeReset(SwShape* shape)
 506 {
 507     rleReset(shape->rle);
 508     rleReset(shape->strokeRle);
 509     shape->rect = false;
 510     shape->bbox.reset();
 511 }
 512
 513
 514 void shapeFree(SwShape* shape)
 515 {
 516     rleFree(shape->rle);
 517     shapeDelFill(shape);
 518
 519     if (shape->stroke) {
 520         rleFree(shape->strokeRle);
 521         strokeFree(shape->stroke);
 522     }
 523 }
 524
 525
 526 void shapeDelStroke(SwShape* shape)
 527 {
 528     if (!shape->stroke) return;
 529     rleFree(shape->strokeRle);
 530     shape->strokeRle = nullptr;
 531     strokeFree(shape->stroke);
 532     shape->stroke = nullptr;
 533 }
 534
 535
 536 void shapeResetStroke(SwShape* shape, const Shape* sdata, const Matrix* transform)
 537 {
 538     if (!shape->stroke) shape->stroke = static_cast<SwStroke*>(calloc(1, sizeof(SwStroke)));
 539     auto stroke = shape->stroke;
 540     if (!stroke) return;
 541
 542     strokeReset(stroke, sdata, transform);
 543     rleReset(shape->strokeRle);
 544 }
 545
 546
 547 bool shapeGenStrokeRle(SwShape* shape, const Shape* sdata, const Matrix* transform, const SwBBox& clipRegion, SwBBox& renderRegion, SwMpool* mpool, unsigned tid)
 548 {
 549     SwOutline* shapeOutline = nullptr;
 550     SwOutline* strokeOutline = nullptr;
 551     bool freeOutline = false;
 552     bool ret = true;
 553
 554     //Dash Style Stroke
 555     if (sdata->strokeDash(nullptr) > 0) {
 556         shapeOutline = _genDashOutline(sdata, transform);
 557         if (!shapeOutline) return false;
 558         freeOutline = true;
 559     //Normal Style stroke
 560     } else {
 561         if (!shape->outline) {
 562             if (!_genOutline(shape, sdata, transform, mpool, tid)) return false;
 563         }
 564         shapeOutline = shape->outline;
 565     }
 566
 567     if (!strokeParseOutline(shape->stroke, *shapeOutline)) {
 568         ret = false;
 569         goto fail;
 570     }
 571
 572     strokeOutline = strokeExportOutline(shape->stroke, mpool, tid);
 573     if (!strokeOutline) {
 574         ret = false;
 575         goto fail;
 576     }
 577
 578     if (!mathUpdateOutlineBBox(strokeOutline, clipRegion, renderRegion)) {
 579         ret = false;
 580         goto fail;
 581     }
 582
 583     shape->strokeRle = rleRender(shape->strokeRle, strokeOutline, renderRegion, true);
 584
 585 fail:
 586     if (freeOutline) {
 587         if (shapeOutline->cntrs) free(shapeOutline->cntrs);
 588         if (shapeOutline->pts) free(shapeOutline->pts);
 589         if (shapeOutline->types) free(shapeOutline->types);
 590         free(shapeOutline);
 591     }
 592     mpoolRetStrokeOutline(mpool, tid);
 593
 594     return ret;
 595 }
 596
 597
 598 bool shapeGenFillColors(SwShape* shape, const Fill* fill, const Matrix* transform, SwSurface* surface, uint32_t opacity, bool ctable)
 599 {
 600     return fillGenColorTable(shape->fill, fill, transform, surface, opacity, ctable);
 601 }
 602
 603
 604 bool shapeGenStrokeFillColors(SwShape* shape, const Fill* fill, const Matrix* transform, SwSurface* surface, uint32_t opacity, bool ctable)
 605 {
 606     return fillGenColorTable(shape->stroke->fill, fill, transform, surface, opacity, ctable);
 607 }
 608
 609
 610 void shapeResetFill(SwShape* shape)
 611 {
 612     if (!shape->fill) {
 613         shape->fill = static_cast<SwFill*>(calloc(1, sizeof(SwFill)));
 614         if (!shape->fill) return;
 615     }
 616     fillReset(shape->fill);
 617 }
 618
 619
 620 void shapeResetStrokeFill(SwShape* shape)
 621 {
 622     if (!shape->stroke->fill) {
 623         shape->stroke->fill = static_cast<SwFill*>(calloc(1, sizeof(SwFill)));
 624         if (!shape->stroke->fill) return;
 625     }
 626     fillReset(shape->stroke->fill);
 627 }
 628
 629
 630 void shapeDelFill(SwShape* shape)
 631 {
 632     if (!shape->fill) return;
 633     fillFree(shape->fill);
 634     shape->fill = nullptr;
 635 }
 636
 637
 638 void shapeDelStrokeFill(SwShape* shape)
 639 {
 640     if (!shape->stroke->fill) return;
 641     fillFree(shape->stroke->fill);
 642     shape->stroke->fill = nullptr;
 643 }