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