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 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 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 /* External Class Implementation                                        */
 368 /************************************************************************/
 369
 370 bool shapePrepare(SwShape* shape, const Shape* sdata, unsigned tid, const Matrix* transform,  const SwBBox& clipRegion, SwBBox& renderRegion)
 371 {
 372     if (!shapeGenOutline(shape, sdata, tid, transform)) return false;
 373     if (!mathUpdateOutlineBBox(shape->outline, clipRegion, renderRegion)) return false;
 374
 375     //Keep it for Rasterization Region
 376     shape->bbox = renderRegion;
 377
 378     //Check valid region
 379     if (renderRegion.max.x - renderRegion.min.x < 1 && renderRegion.max.y - renderRegion.min.y < 1) return false;
 380
 381     //Check boundary
 382     if (renderRegion.min.x >= clipRegion.max.x || renderRegion.min.y >= clipRegion.max.y ||
 383         renderRegion.max.x <= clipRegion.min.x || renderRegion.max.y <= clipRegion.min.y) return false;
 384
 385     return true;
 386 }
 387
 388
 389 bool shapePrepared(const SwShape* shape)
 390 {
 391     return shape->rle ? true : false;
 392 }
 393
 394
 395 bool shapeGenRle(SwShape* shape, TVG_UNUSED const Shape* sdata, bool antiAlias, bool hasComposite)
 396 {
 397     //FIXME: Should we draw it?
 398     //Case: Stroke Line
 399     //if (shape.outline->opened) return true;
 400
 401     //Case A: Fast Track Rectangle Drawing
 402     if (!hasComposite && (shape->rect = _fastTrack(shape->outline))) return true;
 403     //Case B: Normale Shape RLE Drawing
 404     if ((shape->rle = rleRender(shape->rle, shape->outline, shape->bbox,antiAlias))) return true;
 405
 406     return false;
 407 }
 408
 409
 410 void shapeDelOutline(SwShape* shape, uint32_t tid)
 411 {
 412     mpoolRetOutline(tid);
 413     shape->outline = nullptr;
 414 }
 415
 416
 417 void shapeReset(SwShape* shape)
 418 {
 419     rleReset(shape->rle);
 420     rleReset(shape->strokeRle);
 421     shape->rect = false;
 422     shape->bbox.reset();
 423 }
 424
 425
 426 bool shapeGenOutline(SwShape* shape, const Shape* sdata, unsigned tid, const Matrix* transform)
 427 {
 428     const PathCommand* cmds = nullptr;
 429     auto cmdCnt = sdata->pathCommands(&cmds);
 430
 431     const Point* pts = nullptr;
 432     auto ptsCnt = sdata->pathCoords(&pts);
 433
 434     //No actual shape data
 435     if (cmdCnt == 0 || ptsCnt == 0) return false;
 436
 437     //smart reservation
 438     auto outlinePtsCnt = 0;
 439     auto outlineCntrsCnt = 0;
 440
 441     for (uint32_t i = 0; i < cmdCnt; ++i) {
 442         switch(*(cmds + i)) {
 443             case PathCommand::Close: {
 444                 ++outlinePtsCnt;
 445                 break;
 446             }
 447             case PathCommand::MoveTo: {
 448                 ++outlineCntrsCnt;
 449                 ++outlinePtsCnt;
 450                 break;
 451             }
 452             case PathCommand::LineTo: {
 453                 ++outlinePtsCnt;
 454                 break;
 455             }
 456             case PathCommand::CubicTo: {
 457                 outlinePtsCnt += 3;
 458                 break;
 459             }
 460         }
 461     }
 462
 463     ++outlinePtsCnt;    //for close
 464     ++outlineCntrsCnt;  //for end
 465
 466     shape->outline = mpoolReqOutline(tid);
 467     auto outline = shape->outline;
 468     outline->opened = true;
 469
 470     _growOutlinePoint(*outline, outlinePtsCnt);
 471     _growOutlineContour(*outline, outlineCntrsCnt);
 472
 473     auto closed = false;
 474
 475     //Generate Outlines
 476     while (cmdCnt-- > 0) {
 477         switch(*cmds) {
 478             case PathCommand::Close: {
 479                 _outlineClose(*outline);
 480                 closed = true;
 481                 break;
 482             }
 483             case PathCommand::MoveTo: {
 484                 _outlineMoveTo(*outline, pts, transform);
 485                 ++pts;
 486                 break;
 487             }
 488             case PathCommand::LineTo: {
 489                 _outlineLineTo(*outline, pts, transform);
 490                 ++pts;
 491                 break;
 492             }
 493             case PathCommand::CubicTo: {
 494                 _outlineCubicTo(*outline, pts, pts + 1, pts + 2, transform);
 495                 pts += 3;
 496                 break;
 497             }
 498         }
 499         ++cmds;
 500     }
 501
 502     _outlineEnd(*outline);
 503
 504     if (closed) outline->opened = false;
 505
 506     outline->fillRule = sdata->fillRule();
 507     shape->outline = outline;
 508
 509     return true;
 510 }
 511
 512
 513 void shapeFree(SwShape* shape)
 514 {
 515     rleFree(shape->rle);
 516     shapeDelFill(shape);
 517
 518     if (shape->stroke) {
 519         rleFree(shape->strokeRle);
 520         strokeFree(shape->stroke);
 521     }
 522 }
 523
 524
 525 void shapeDelStroke(SwShape* shape)
 526 {
 527     if (!shape->stroke) return;
 528     rleFree(shape->strokeRle);
 529     shape->strokeRle = nullptr;
 530     strokeFree(shape->stroke);
 531     shape->stroke = nullptr;
 532 }
 533
 534
 535 void shapeResetStroke(SwShape* shape, const Shape* sdata, const Matrix* transform)
 536 {
 537     if (!shape->stroke) shape->stroke = static_cast<SwStroke*>(calloc(1, sizeof(SwStroke)));
 538     auto stroke = shape->stroke;
 539     if (!stroke) return;
 540
 541     strokeReset(stroke, sdata, transform);
 542     rleReset(shape->strokeRle);
 543 }
 544
 545
 546 bool shapeGenStrokeRle(SwShape* shape, const Shape* sdata, unsigned tid, const Matrix* transform, const SwBBox& clipRegion, SwBBox& renderRegion)
 547 {
 548     SwOutline* shapeOutline = nullptr;
 549     SwOutline* strokeOutline = nullptr;
 550     bool freeOutline = false;
 551     bool ret = true;
 552
 553     //Dash Style Stroke
 554     if (sdata->strokeDash(nullptr) > 0) {
 555         shapeOutline = _genDashOutline(sdata, transform);
 556         if (!shapeOutline) return false;
 557         freeOutline = true;
 558     //Normal Style stroke
 559     } else {
 560         if (!shape->outline) {
 561             if (!shapeGenOutline(shape, sdata, tid, transform)) return false;
 562         }
 563         shapeOutline = shape->outline;
 564     }
 565
 566     if (!strokeParseOutline(shape->stroke, *shapeOutline)) {
 567         ret = false;
 568         goto fail;
 569     }
 570
 571     strokeOutline = strokeExportOutline(shape->stroke, tid);
 572     if (!strokeOutline) {
 573         ret = false;
 574         goto fail;
 575     }
 576
 577     if (!mathUpdateOutlineBBox(strokeOutline, clipRegion, renderRegion)) {
 578         ret = false;
 579         goto fail;
 580     }
 581
 582     shape->strokeRle = rleRender(shape->strokeRle, strokeOutline, renderRegion, true);
 583
 584 fail:
 585     if (freeOutline) {
 586         if (shapeOutline->cntrs) free(shapeOutline->cntrs);
 587         if (shapeOutline->pts) free(shapeOutline->pts);
 588         if (shapeOutline->types) free(shapeOutline->types);
 589         free(shapeOutline);
 590     }
 591     mpoolRetStrokeOutline(tid);
 592
 593     return ret;
 594 }
 595
 596
 597 bool shapeGenFillColors(SwShape* shape, const Fill* fill, const Matrix* transform, SwSurface* surface, uint32_t opacity, bool ctable)
 598 {
 599     return fillGenColorTable(shape->fill, fill, transform, surface, opacity, ctable);
 600 }
 601
 602
 603 bool shapeGenStrokeFillColors(SwShape* shape, const Fill* fill, const Matrix* transform, SwSurface* surface, uint32_t opacity, bool ctable)
 604 {
 605     return fillGenColorTable(shape->stroke->fill, fill, transform, surface, opacity, ctable);
 606 }
 607
 608
 609 void shapeResetFill(SwShape* shape)
 610 {
 611     if (!shape->fill) {
 612         shape->fill = static_cast<SwFill*>(calloc(1, sizeof(SwFill)));
 613         if (!shape->fill) return;
 614     }
 615     fillReset(shape->fill);
 616 }
 617
 618
 619 void shapeResetStrokeFill(SwShape* shape)
 620 {
 621     if (!shape->stroke->fill) {
 622         shape->stroke->fill = static_cast<SwFill*>(calloc(1, sizeof(SwFill)));
 623         if (!shape->stroke->fill) return;
 624     }
 625     fillReset(shape->stroke->fill);
 626 }
 627
 628
 629 void shapeDelFill(SwShape* shape)
 630 {
 631     if (!shape->fill) return;
 632     fillFree(shape->fill);
 633     shape->fill = nullptr;
 634 }
 635
 636
 637 void shapeDelStrokeFill(SwShape* shape)
 638 {
 639     if (!shape->stroke->fill) return;
 640     fillFree(shape->stroke->fill);
 641     shape->stroke->fill = nullptr;
 642 }