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