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