1 /*
2 * Copyright (c) 2020 - 2024 the ThorVG project. 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
23 #include "../../lv_conf_internal.h"
24 #if LV_USE_THORVG_INTERNAL
25
26 /*
27 * The FreeType Project LICENSE
28 * ----------------------------
29
30 * 2006-Jan-27
31
32 * Copyright 1996-2002, 2006 by
33 * David Turner, Robert Wilhelm, and Werner Lemberg
34
35
36
37 * Introduction
38 * ============
39
40 * The FreeType Project is distributed in several archive packages;
41 * some of them may contain, in addition to the FreeType font engine,
42 * various tools and contributions which rely on, or relate to, the
43 * FreeType Project.
44
45 * This license applies to all files found in such packages, and
46 * which do not fall under their own explicit license. The license
47 * affects thus the FreeType font engine, the test programs,
48 * documentation and makefiles, at the very least.
49
50 * This license was inspired by the BSD, Artistic, and IJG
51 * (Independent JPEG Group) licenses, which all encourage inclusion
52 * and use of free software in commercial and freeware products
53 * alike. As a consequence, its main points are that:
54
55 * o We don't promise that this software works. However, we will be
56 * interested in any kind of bug reports. (`as is' distribution)
57
58 * o You can use this software for whatever you want, in parts or
59 * full form, without having to pay us. (`royalty-free' usage)
60
61 * o You may not pretend that you wrote this software. If you use
62 * it, or only parts of it, in a program, you must acknowledge
63 * somewhere in your documentation that you have used the
64 * FreeType code. (`credits')
65
66 * We specifically permit and encourage the inclusion of this
67 * software, with or without modifications, in commercial products.
68 * We disclaim all warranties covering The FreeType Project and
69 * assume no liability related to The FreeType Project.
70
71
72 * Finally, many people asked us for a preferred form for a
73 * credit/disclaimer to use in compliance with this license. We thus
74 * encourage you to use the following text:
75
76 * """
77 * Portions of this software are copyright � <year> The FreeType
78 * Project (www.freetype.org). All rights reserved.
79 * """
80
81 * Please replace <year> with the value from the FreeType version you
82 * actually use.
83
84 * Legal Terms
85 * ===========
86
87 * 0. Definitions
88 * --------------
89
90 * Throughout this license, the terms `package', `FreeType Project',
91 * and `FreeType archive' refer to the set of files originally
92 * distributed by the authors (David Turner, Robert Wilhelm, and
93 * Werner Lemberg) as the `FreeType Project', be they named as alpha,
94 * beta or final release.
95
96 * `You' refers to the licensee, or person using the project, where
97 * `using' is a generic term including compiling the project's source
98 * code as well as linking it to form a `program' or `executable'.
99 * This program is referred to as `a program using the FreeType
100 * engine'.
101
102 * This license applies to all files distributed in the original
103 * FreeType Project, including all source code, binaries and
104 * documentation, unless otherwise stated in the file in its
105 * original, unmodified form as distributed in the original archive.
106 * If you are unsure whether or not a particular file is covered by
107 * this license, you must contact us to verify this.
108
109 * The FreeType Project is copyright (C) 1996-2000 by David Turner,
110 * Robert Wilhelm, and Werner Lemberg. All rights reserved except as
111 * specified below.
112
113 * 1. No Warranty
114 * --------------
115
116 * THE FREETYPE PROJECT IS PROVIDED `AS IS' WITHOUT WARRANTY OF ANY
117 * KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
118 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
119 * PURPOSE. IN NO EVENT WILL ANY OF THE AUTHORS OR COPYRIGHT HOLDERS
120 * BE LIABLE FOR ANY DAMAGES CAUSED BY THE USE OR THE INABILITY TO
121 * USE, OF THE FREETYPE PROJECT.
122
123 * 2. Redistribution
124 * -----------------
125
126 * This license grants a worldwide, royalty-free, perpetual and
127 * irrevocable right and license to use, execute, perform, compile,
128 * display, copy, create derivative works of, distribute and
129 * sublicense the FreeType Project (in both source and object code
130 * forms) and derivative works thereof for any purpose; and to
131 * authorize others to exercise some or all of the rights granted
132 * herein, subject to the following conditions:
133
134 * o Redistribution of source code must retain this license file
135 * (`FTL.TXT') unaltered; any additions, deletions or changes to
136 * the original files must be clearly indicated in accompanying
137 * documentation. The copyright notices of the unaltered,
138 * original files must be preserved in all copies of source
139 * files.
140
141 * o Redistribution in binary form must provide a disclaimer that
142 * states that the software is based in part of the work of the
143 * FreeType Team, in the distribution documentation. We also
144 * encourage you to put an URL to the FreeType web page in your
145 * documentation, though this isn't mandatory.
146
147 * These conditions apply to any software derived from or based on
148 * the FreeType Project, not just the unmodified files. If you use
149 * our work, you must acknowledge us. However, no fee need be paid
150 * to us.
151
152 * 3. Advertising
153 * --------------
154
155 * Neither the FreeType authors and contributors nor you shall use
156 * the name of the other for commercial, advertising, or promotional
157 * purposes without specific prior written permission.
158
159 * We suggest, but do not require, that you use one or more of the
160 * following phrases to refer to this software in your documentation
161 * or advertising materials: `FreeType Project', `FreeType Engine',
162 * `FreeType library', or `FreeType Distribution'.
163
164 * As you have not signed this license, you are not required to
165 * accept it. However, as the FreeType Project is copyrighted
166 * material, only this license, or another one contracted with the
167 * authors, grants you the right to use, distribute, and modify it.
168 * Therefore, by using, distributing, or modifying the FreeType
169 * Project, you indicate that you understand and accept all the terms
170 * of this license.
171
172 * 4. Contacts
173 * -----------
174
175 * There are two mailing lists related to FreeType:
176
177 * o freetype@nongnu.org
178
179 * Discusses general use and applications of FreeType, as well as
180 * future and wanted additions to the library and distribution.
181 * If you are looking for support, start in this list if you
182 * haven't found anything to help you in the documentation.
183
184 * o freetype-devel@nongnu.org
185
186 * Discusses bugs, as well as engine internals, design issues,
187 * specific licenses, porting, etc.
188
189 * Our home page can be found at
190
191 * http://www.freetype.org
192 */
193
194 #include <setjmp.h>
195 #include <limits.h>
196 #include <memory.h>
197 #include "tvgSwCommon.h"
198
199 /************************************************************************/
200 /* Internal Class Implementation */
201 /************************************************************************/
202
203 constexpr auto PIXEL_BITS = 8; //must be at least 6 bits!
204 constexpr auto ONE_PIXEL = (1L << PIXEL_BITS);
205
206 using Area = long;
207
208 struct Band
209 {
210 SwCoord min, max;
211 };
212
213 struct Cell
214 {
215 SwCoord x;
216 SwCoord cover;
217 Area area;
218 Cell *next;
219 };
220
221 struct RleWorker
222 {
223 SwRle* rle;
224
225 SwPoint cellPos;
226 SwPoint cellMin;
227 SwPoint cellMax;
228 SwCoord cellXCnt;
229 SwCoord cellYCnt;
230
231 Area area;
232 SwCoord cover;
233
234 Cell* cells;
235 ptrdiff_t maxCells;
236 ptrdiff_t cellsCnt;
237
238 SwPoint pos;
239
240 SwPoint bezStack[32 * 3 + 1];
241 SwPoint lineStack[32 + 1];
242 int levStack[32];
243
244 SwOutline* outline;
245
246 int bandSize;
247 int bandShoot;
248
249 jmp_buf jmpBuf;
250
251 void* buffer;
252 long bufferSize;
253
254 Cell** yCells;
255 SwCoord yCnt;
256
257 bool invalid;
258 bool antiAlias;
259 };
260
261
UPSCALE(const SwPoint & pt)262 static inline SwPoint UPSCALE(const SwPoint& pt)
263 {
264 return {SwCoord(((unsigned long) pt.x) << (PIXEL_BITS - 6)), SwCoord(((unsigned long) pt.y) << (PIXEL_BITS - 6))};
265 }
266
267
TRUNC(const SwPoint & pt)268 static inline SwPoint TRUNC(const SwPoint& pt)
269 {
270 return {pt.x >> PIXEL_BITS, pt.y >> PIXEL_BITS};
271 }
272
273
TRUNC(const SwCoord x)274 static inline SwCoord TRUNC(const SwCoord x)
275 {
276 return x >> PIXEL_BITS;
277 }
278
279
SUBPIXELS(const SwPoint & pt)280 static inline SwPoint SUBPIXELS(const SwPoint& pt)
281 {
282 return {SwCoord(((unsigned long) pt.x) << PIXEL_BITS), SwCoord(((unsigned long) pt.y) << PIXEL_BITS)};
283 }
284
285
SUBPIXELS(const SwCoord x)286 static inline SwCoord SUBPIXELS(const SwCoord x)
287 {
288 return SwCoord(((unsigned long) x) << PIXEL_BITS);
289 }
290
291 /*
292 * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min'
293 * algorithm. We use alpha = 1, beta = 3/8, giving us results with a
294 * largest error less than 7% compared to the exact value.
295 */
HYPOT(SwPoint pt)296 static inline SwCoord HYPOT(SwPoint pt)
297 {
298 if (pt.x < 0) pt.x = -pt.x;
299 if (pt.y < 0) pt.y = -pt.y;
300 return ((pt.x > pt.y) ? (pt.x + (3 * pt.y >> 3)) : (pt.y + (3 * pt.x >> 3)));
301 }
302
303
_horizLine(RleWorker & rw,SwCoord x,SwCoord y,SwCoord area,SwCoord aCount)304 static void _horizLine(RleWorker& rw, SwCoord x, SwCoord y, SwCoord area, SwCoord aCount)
305 {
306 x += rw.cellMin.x;
307 y += rw.cellMin.y;
308
309 //Clip Y range
310 if (y < rw.cellMin.y || y >= rw.cellMax.y) return;
311
312 /* compute the coverage line's coverage, depending on the outline fill rule */
313 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
314 auto coverage = static_cast<int>(area >> (PIXEL_BITS * 2 + 1 - 8)); //range 0 - 255
315
316 if (coverage < 0) coverage = -coverage;
317
318 if (rw.outline->fillRule == FillRule::EvenOdd) {
319 coverage &= 511;
320 if (coverage > 255) coverage = 511 - coverage;
321 } else {
322 //normal non-zero winding rule
323 if (coverage > 255) coverage = 255;
324 }
325
326 if (coverage == 0) return;
327
328 //span has ushort coordinates. check limit overflow
329 if (x >= SHRT_MAX) {
330 TVGERR("SW_ENGINE", "X-coordinate overflow!");
331 return;
332 }
333 if (y >= SHRT_MAX) {
334 TVGERR("SW_ENGINE", "Y-coordinate overflow!");
335 return;
336 }
337
338 auto rle = rw.rle;
339
340 if (!rw.antiAlias) coverage = 255;
341
342 //see whether we can add this span to the current list
343 if (rle->size > 0) {
344 auto span = rle->spans + rle->size - 1;
345 if ((span->coverage == coverage) && (span->y == y) && (span->x + span->len == x)) {
346 //Clip x range
347 SwCoord xOver = 0;
348 if (x + aCount >= rw.cellMax.x) xOver -= (x + aCount - rw.cellMax.x);
349 if (x < rw.cellMin.x) xOver -= (rw.cellMin.x - x);
350
351 //span->len += (aCount + xOver) - 1;
352 span->len += (aCount + xOver);
353 return;
354 }
355 }
356
357 //span pool is full, grow it.
358 if (rle->size >= rle->alloc) {
359 auto newSize = (rle->size > 0) ? (rle->size * 2) : 256;
360 if (rle->alloc < newSize) {
361 rle->alloc = newSize;
362 rle->spans = static_cast<SwSpan*>(realloc(rle->spans, rle->alloc * sizeof(SwSpan)));
363 }
364 }
365
366 //Clip x range
367 SwCoord xOver = 0;
368 if (x + aCount >= rw.cellMax.x) xOver -= (x + aCount - rw.cellMax.x);
369 if (x < rw.cellMin.x) {
370 xOver -= (rw.cellMin.x - x);
371 x = rw.cellMin.x;
372 }
373
374 //Nothing to draw
375 if (aCount + xOver <= 0) return;
376
377 //add a span to the current list
378 auto span = rle->spans + rle->size;
379 span->x = x;
380 span->y = y;
381 span->len = (aCount + xOver);
382 span->coverage = coverage;
383 rle->size++;
384 }
385
386
_sweep(RleWorker & rw)387 static void _sweep(RleWorker& rw)
388 {
389 if (rw.cellsCnt == 0) return;
390
391 for (int y = 0; y < rw.yCnt; ++y) {
392 auto cover = 0;
393 auto x = 0;
394 auto cell = rw.yCells[y];
395
396 while (cell) {
397 if (cell->x > x && cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), cell->x - x);
398 cover += cell->cover;
399 auto area = cover * (ONE_PIXEL * 2) - cell->area;
400 if (area != 0 && cell->x >= 0) _horizLine(rw, cell->x, y, area, 1);
401 x = cell->x + 1;
402 cell = cell->next;
403 }
404
405 if (cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), rw.cellXCnt - x);
406 }
407 }
408
409
_findCell(RleWorker & rw)410 static Cell* _findCell(RleWorker& rw)
411 {
412 auto x = rw.cellPos.x;
413 if (x > rw.cellXCnt) x = rw.cellXCnt;
414
415 auto pcell = &rw.yCells[rw.cellPos.y];
416
417 while(true) {
418 Cell* cell = *pcell;
419 if (!cell || cell->x > x) break;
420 if (cell->x == x) return cell;
421 pcell = &cell->next;
422 }
423
424 if (rw.cellsCnt >= rw.maxCells) longjmp(rw.jmpBuf, 1);
425
426 auto cell = rw.cells + rw.cellsCnt++;
427 cell->x = x;
428 cell->area = 0;
429 cell->cover = 0;
430 cell->next = *pcell;
431 *pcell = cell;
432
433 return cell;
434 }
435
436
_recordCell(RleWorker & rw)437 static void _recordCell(RleWorker& rw)
438 {
439 if (rw.area | rw.cover) {
440 auto cell = _findCell(rw);
441 cell->area += rw.area;
442 cell->cover += rw.cover;
443 }
444 }
445
446
_setCell(RleWorker & rw,SwPoint pos)447 static void _setCell(RleWorker& rw, SwPoint pos)
448 {
449 /* Move the cell pointer to a new position. We set the `invalid' */
450 /* flag to indicate that the cell isn't part of those we're interested */
451 /* in during the render phase. This means that: */
452 /* */
453 /* . the new vertical position must be within min_ey..max_ey-1. */
454 /* . the new horizontal position must be strictly less than max_ex */
455 /* */
456 /* Note that if a cell is to the left of the clipping region, it is */
457 /* actually set to the (min_ex-1) horizontal position. */
458
459 /* All cells that are on the left of the clipping region go to the
460 min_ex - 1 horizontal position. */
461 pos.x -= rw.cellMin.x;
462 pos.y -= rw.cellMin.y;
463
464 if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
465
466 //Are we moving to a different cell?
467 if (pos != rw.cellPos) {
468 //Record the current one if it is valid
469 if (!rw.invalid) _recordCell(rw);
470 }
471
472 rw.area = 0;
473 rw.cover = 0;
474 rw.cellPos = pos;
475 rw.invalid = ((unsigned)pos.y >= (unsigned)rw.cellYCnt || pos.x >= rw.cellXCnt);
476 }
477
478
_startCell(RleWorker & rw,SwPoint pos)479 static void _startCell(RleWorker& rw, SwPoint pos)
480 {
481 if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
482 if (pos.x < rw.cellMin.x) pos.x = rw.cellMin.x;
483
484 rw.area = 0;
485 rw.cover = 0;
486 rw.cellPos = pos - rw.cellMin;
487 rw.invalid = false;
488
489 _setCell(rw, pos);
490 }
491
492
_moveTo(RleWorker & rw,const SwPoint & to)493 static void _moveTo(RleWorker& rw, const SwPoint& to)
494 {
495 //record current cell, if any */
496 if (!rw.invalid) _recordCell(rw);
497
498 //start to a new position
499 _startCell(rw, TRUNC(to));
500
501 rw.pos = to;
502 }
503
504
_lineTo(RleWorker & rw,const SwPoint & to)505 static void _lineTo(RleWorker& rw, const SwPoint& to)
506 {
507 #define SW_UDIV(a, b) \
508 static_cast<SwCoord>(((unsigned long)(a) * (unsigned long)(b)) >> \
509 (sizeof(long) * CHAR_BIT - PIXEL_BITS))
510
511 auto e1 = TRUNC(rw.pos);
512 auto e2 = TRUNC(to);
513
514 //vertical clipping
515 if ((e1.y >= rw.cellMax.y && e2.y >= rw.cellMax.y) || (e1.y < rw.cellMin.y && e2.y < rw.cellMin.y)) {
516 rw.pos = to;
517 return;
518 }
519
520 auto line = rw.lineStack;
521 line[0] = to;
522 line[1] = rw.pos;
523
524 while (true) {
525 auto diff = line[0] - line[1];
526 auto L = HYPOT(diff);
527
528 if (L > SHRT_MAX) {
529 mathSplitLine(line);
530 ++line;
531 continue;
532 }
533 e1 = TRUNC(line[1]);
534 e2 = TRUNC(line[0]);
535
536 auto f1 = line[1] - SUBPIXELS(e1);
537 SwPoint f2;
538
539 //inside one cell
540 if (e1 == e2) {
541 ;
542 //any horizontal line
543 } else if (diff.y == 0) {
544 e1.x = e2.x;
545 _setCell(rw, e1);
546 } else if (diff.x == 0) {
547 //vertical line up
548 if (diff.y > 0) {
549 do {
550 f2.y = ONE_PIXEL;
551 rw.cover += (f2.y - f1.y);
552 rw.area += (f2.y - f1.y) * f1.x * 2;
553 f1.y = 0;
554 ++e1.y;
555 _setCell(rw, e1);
556 } while(e1.y != e2.y);
557 //vertical line down
558 } else {
559 do {
560 f2.y = 0;
561 rw.cover += (f2.y - f1.y);
562 rw.area += (f2.y - f1.y) * f1.x * 2;
563 f1.y = ONE_PIXEL;
564 --e1.y;
565 _setCell(rw, e1);
566 } while(e1.y != e2.y);
567 }
568 //any other line
569 } else {
570 Area prod = diff.x * f1.y - diff.y * f1.x;
571
572 /* These macros speed up repetitive divisions by replacing them
573 with multiplications and right shifts. */
574 auto dx_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.x);
575 auto dy_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.y);
576
577 /* The fundamental value `prod' determines which side and the */
578 /* exact coordinate where the line exits current cell. It is */
579 /* also easily updated when moving from one cell to the next. */
580 do {
581 auto px = diff.x * ONE_PIXEL;
582 auto py = diff.y * ONE_PIXEL;
583
584 //left
585 if (prod <= 0 && prod - px > 0) {
586 f2 = {0, SW_UDIV(-prod, -dx_r)};
587 prod -= py;
588 rw.cover += (f2.y - f1.y);
589 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
590 f1 = {ONE_PIXEL, f2.y};
591 --e1.x;
592 //up
593 } else if (prod - px <= 0 && prod - px + py > 0) {
594 prod -= px;
595 f2 = {SW_UDIV(-prod, dy_r), ONE_PIXEL};
596 rw.cover += (f2.y - f1.y);
597 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
598 f1 = {f2.x, 0};
599 ++e1.y;
600 //right
601 } else if (prod - px + py <= 0 && prod + py >= 0) {
602 prod += py;
603 f2 = {ONE_PIXEL, SW_UDIV(prod, dx_r)};
604 rw.cover += (f2.y - f1.y);
605 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
606 f1 = {0, f2.y};
607 ++e1.x;
608 //down
609 } else {
610 f2 = {SW_UDIV(prod, -dy_r), 0};
611 prod += px;
612 rw.cover += (f2.y - f1.y);
613 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
614 f1 = {f2.x, ONE_PIXEL};
615 --e1.y;
616 }
617
618 _setCell(rw, e1);
619
620 } while(e1 != e2);
621 }
622
623 f2 = {line[0].x - SUBPIXELS(e2.x), line[0].y - SUBPIXELS(e2.y)};
624 rw.cover += (f2.y - f1.y);
625 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
626 rw.pos = line[0];
627
628 if (line-- == rw.lineStack) return;
629 }
630 }
631
632
_cubicTo(RleWorker & rw,const SwPoint & ctrl1,const SwPoint & ctrl2,const SwPoint & to)633 static void _cubicTo(RleWorker& rw, const SwPoint& ctrl1, const SwPoint& ctrl2, const SwPoint& to)
634 {
635 auto arc = rw.bezStack;
636 arc[0] = to;
637 arc[1] = ctrl2;
638 arc[2] = ctrl1;
639 arc[3] = rw.pos;
640
641 //Short-cut the arc that crosses the current band
642 auto min = arc[0].y;
643 auto max = arc[0].y;
644
645 SwCoord y;
646 for (auto i = 1; i < 4; ++i) {
647 y = arc[i].y;
648 if (y < min) min = y;
649 if (y > max) max = y;
650 }
651
652 if (TRUNC(min) >= rw.cellMax.y || TRUNC(max) < rw.cellMin.y) goto draw;
653
654 /* Decide whether to split or draw. See `Rapid Termination */
655 /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
656 /* F. Hain, at */
657 /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
658 while (true) {
659 {
660 //diff is the P0 - P3 chord vector
661 auto diff = arc[3] - arc[0];
662 auto L = HYPOT(diff);
663
664 //avoid possible arithmetic overflow below by splitting
665 if (L > SHRT_MAX) goto split;
666
667 //max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1)
668 auto sLimit = L * (ONE_PIXEL / 6);
669
670 auto diff1 = arc[1] - arc[0];
671 auto s = diff.y * diff1.x - diff.x * diff1.y;
672 if (s < 0) s = -s;
673 if (s > sLimit) goto split;
674
675 //s is L * the perpendicular distance from P2 to the line P0 - P3
676 auto diff2 = arc[2] - arc[0];
677 s = diff.y * diff2.x - diff.x * diff2.y;
678 if (s < 0) s = -s;
679 if (s > sLimit) goto split;
680
681 /* Split super curvy segments where the off points are so far
682 from the chord that the angles P0-P1-P3 or P0-P2-P3 become
683 acute as detected by appropriate dot products */
684 if (diff1.x * (diff1.x - diff.x) + diff1.y * (diff1.y - diff.y) > 0 ||
685 diff2.x * (diff2.x - diff.x) + diff2.y * (diff2.y - diff.y) > 0)
686 goto split;
687
688 //no reason to split
689 goto draw;
690 }
691 split:
692 mathSplitCubic(arc);
693 arc += 3;
694 continue;
695
696 draw:
697 _lineTo(rw, arc[0]);
698 if (arc == rw.bezStack) return;
699 arc -= 3;
700 }
701 }
702
703
_decomposeOutline(RleWorker & rw)704 static void _decomposeOutline(RleWorker& rw)
705 {
706 auto outline = rw.outline;
707 auto first = 0; //index of first point in contour
708
709 for (auto cntr = outline->cntrs.begin(); cntr < outline->cntrs.end(); ++cntr) {
710 auto last = *cntr;
711 auto limit = outline->pts.data + last;
712 auto start = UPSCALE(outline->pts[first]);
713 auto pt = outline->pts.data + first;
714 auto types = outline->types.data + first;
715 ++types;
716
717 _moveTo(rw, UPSCALE(outline->pts[first]));
718
719 while (pt < limit) {
720 //emit a single line_to
721 if (types[0] == SW_CURVE_TYPE_POINT) {
722 ++pt;
723 ++types;
724 _lineTo(rw, UPSCALE(*pt));
725 //types cubic
726 } else {
727 pt += 3;
728 types += 3;
729 if (pt <= limit) _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), UPSCALE(pt[0]));
730 else if (pt - 1 == limit) _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), start);
731 else goto close;
732 }
733 }
734 close:
735 _lineTo(rw, start);
736 first = last + 1;
737 }
738 }
739
740
_genRle(RleWorker & rw)741 static int _genRle(RleWorker& rw)
742 {
743 if (setjmp(rw.jmpBuf) == 0) {
744 _decomposeOutline(rw);
745 if (!rw.invalid) _recordCell(rw);
746 return 0;
747 }
748 return -1; //lack of cell memory
749 }
750
751
_intersectSpansRegion(const SwRle * clip,const SwRle * target,SwSpan * outSpans,uint32_t outSpansCnt)752 static SwSpan* _intersectSpansRegion(const SwRle *clip, const SwRle *target, SwSpan *outSpans, uint32_t outSpansCnt)
753 {
754 auto out = outSpans;
755 auto spans = target->spans;
756 auto end = target->spans + target->size;
757 auto clipSpans = clip->spans;
758 auto clipEnd = clip->spans + clip->size;
759
760 while (spans < end && clipSpans < clipEnd) {
761 //align y-coordinates.
762 if (clipSpans->y > spans->y) {
763 ++spans;
764 continue;
765 }
766 if (spans->y > clipSpans->y) {
767 ++clipSpans;
768 continue;
769 }
770
771 //Try clipping with all clip spans which have a same y-coordinate.
772 auto temp = clipSpans;
773 while(temp < clipEnd && outSpansCnt > 0 && temp->y == clipSpans->y) {
774 auto sx1 = spans->x;
775 auto sx2 = sx1 + spans->len;
776 auto cx1 = temp->x;
777 auto cx2 = cx1 + temp->len;
778
779 //The span must be left(x1) to right(x2) direction. Not intersected.
780 if (cx2 < sx1 || sx2 < cx1) {
781 ++temp;
782 continue;
783 }
784
785 //clip span region.
786 auto x = sx1 > cx1 ? sx1 : cx1;
787 auto len = (sx2 < cx2 ? sx2 : cx2) - x;
788 if (len > 0) {
789 out->x = x;
790 out->y = temp->y;
791 out->len = len;
792 out->coverage = (uint8_t)(((spans->coverage * temp->coverage) + 0xff) >> 8);
793 ++out;
794 --outSpansCnt;
795 }
796 ++temp;
797 }
798 ++spans;
799 }
800 return out;
801 }
802
803
_intersectSpansRect(const SwBBox * bbox,const SwRle * targetRle,SwSpan * outSpans,uint32_t outSpansCnt)804 static SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRle *targetRle, SwSpan *outSpans, uint32_t outSpansCnt)
805 {
806 auto out = outSpans;
807 auto spans = targetRle->spans;
808 auto end = targetRle->spans + targetRle->size;
809 auto minx = static_cast<int16_t>(bbox->min.x);
810 auto miny = static_cast<int16_t>(bbox->min.y);
811 auto maxx = minx + static_cast<int16_t>(bbox->max.x - bbox->min.x) - 1;
812 auto maxy = miny + static_cast<int16_t>(bbox->max.y - bbox->min.y) - 1;
813
814 while (outSpansCnt > 0 && spans < end) {
815 if (spans->y > maxy) {
816 spans = end;
817 break;
818 }
819 if (spans->y < miny || spans->x > maxx || spans->x + spans->len <= minx) {
820 ++spans;
821 continue;
822 }
823 if (spans->x < minx) {
824 out->len = (spans->len - (minx - spans->x)) < (maxx - minx + 1) ? (spans->len - (minx - spans->x)) : (maxx - minx + 1);
825 out->x = minx;
826 }
827 else {
828 out->x = spans->x;
829 out->len = spans->len < (maxx - spans->x + 1) ? spans->len : (maxx - spans->x + 1);
830 }
831 if (out->len > 0) {
832 out->y = spans->y;
833 out->coverage = spans->coverage;
834 ++out;
835 --outSpansCnt;
836 }
837 ++spans;
838 }
839 return out;
840 }
841
842
_replaceClipSpan(SwRle * rle,SwSpan * clippedSpans,uint32_t size)843 void _replaceClipSpan(SwRle *rle, SwSpan* clippedSpans, uint32_t size)
844 {
845 free(rle->spans);
846 rle->spans = clippedSpans;
847 rle->size = rle->alloc = size;
848 }
849
850
851 /************************************************************************/
852 /* External Class Implementation */
853 /************************************************************************/
854
rleRender(SwRle * rle,const SwOutline * outline,const SwBBox & renderRegion,bool antiAlias)855 SwRle* rleRender(SwRle* rle, const SwOutline* outline, const SwBBox& renderRegion, bool antiAlias)
856 {
857 constexpr auto RENDER_POOL_SIZE = 16384L;
858 constexpr auto BAND_SIZE = 40;
859
860 //TODO: We can preserve several static workers in advance
861 RleWorker rw;
862 Cell buffer[RENDER_POOL_SIZE / sizeof(Cell)];
863
864 //Init Cells
865 rw.buffer = buffer;
866 rw.bufferSize = sizeof(buffer);
867 rw.yCells = reinterpret_cast<Cell**>(buffer);
868 rw.cells = nullptr;
869 rw.maxCells = 0;
870 rw.cellsCnt = 0;
871 rw.area = 0;
872 rw.cover = 0;
873 rw.invalid = true;
874 rw.cellMin = renderRegion.min;
875 rw.cellMax = renderRegion.max;
876 rw.cellXCnt = rw.cellMax.x - rw.cellMin.x;
877 rw.cellYCnt = rw.cellMax.y - rw.cellMin.y;
878 rw.outline = const_cast<SwOutline*>(outline);
879 rw.bandSize = rw.bufferSize / (sizeof(Cell) * 2); //bandSize: 256
880 rw.bandShoot = 0;
881 rw.antiAlias = antiAlias;
882
883 if (!rle) rw.rle = reinterpret_cast<SwRle*>(calloc(1, sizeof(SwRle)));
884 else rw.rle = rle;
885
886 //Generate RLE
887 Band bands[BAND_SIZE];
888 Band* band;
889
890 /* set up vertical bands */
891 auto bandCnt = static_cast<int>((rw.cellMax.y - rw.cellMin.y) / rw.bandSize);
892 if (bandCnt == 0) bandCnt = 1;
893 else if (bandCnt >= BAND_SIZE) bandCnt = (BAND_SIZE - 1);
894
895 auto min = rw.cellMin.y;
896 auto yMax = rw.cellMax.y;
897 SwCoord max;
898 int ret;
899
900 for (int n = 0; n < bandCnt; ++n, min = max) {
901 max = min + rw.bandSize;
902 if (n == bandCnt -1 || max > yMax) max = yMax;
903
904 bands[0].min = min;
905 bands[0].max = max;
906 band = bands;
907
908 while (band >= bands) {
909 rw.yCells = static_cast<Cell**>(rw.buffer);
910 rw.yCnt = band->max - band->min;
911
912 int cellStart = sizeof(Cell*) * (int)rw.yCnt;
913 int cellMod = cellStart % sizeof(Cell);
914
915 if (cellMod > 0) cellStart += sizeof(Cell) - cellMod;
916
917 auto cellsMax = reinterpret_cast<Cell*>((char*)rw.buffer + rw.bufferSize);
918 rw.cells = reinterpret_cast<Cell*>((char*)rw.buffer + cellStart);
919
920 if (rw.cells >= cellsMax) goto reduce_bands;
921
922 rw.maxCells = cellsMax - rw.cells;
923 if (rw.maxCells < 2) goto reduce_bands;
924
925 for (int y = 0; y < rw.yCnt; ++y)
926 rw.yCells[y] = nullptr;
927
928 rw.cellsCnt = 0;
929 rw.invalid = true;
930 rw.cellMin.y = band->min;
931 rw.cellMax.y = band->max;
932 rw.cellYCnt = band->max - band->min;
933
934 ret = _genRle(rw);
935 if (ret == 0) {
936 _sweep(rw);
937 --band;
938 continue;
939 } else if (ret == 1) {
940 goto error;
941 }
942
943 reduce_bands:
944 /* render pool overflow: we will reduce the render band by half */
945 auto bottom = band->min;
946 auto top = band->max;
947 auto middle = bottom + ((top - bottom) >> 1);
948
949 /* This is too complex for a single scanline; there must
950 be some problems */
951 if (middle == bottom) goto error;
952
953 if (bottom - top >= rw.bandSize) ++rw.bandShoot;
954
955 band[1].min = bottom;
956 band[1].max = middle;
957 band[0].min = middle;
958 band[0].max = top;
959 ++band;
960 }
961 }
962
963 if (rw.bandShoot > 8 && rw.bandSize > 16)
964 rw.bandSize = (rw.bandSize >> 1);
965
966 return rw.rle;
967
968 error:
969 free(rw.rle);
970 return nullptr;
971 }
972
973
rleRender(const SwBBox * bbox)974 SwRle* rleRender(const SwBBox* bbox)
975 {
976 auto width = static_cast<uint16_t>(bbox->max.x - bbox->min.x);
977 auto height = static_cast<uint16_t>(bbox->max.y - bbox->min.y);
978
979 auto rle = static_cast<SwRle*>(malloc(sizeof(SwRle)));
980 rle->spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * height));
981 rle->size = height;
982 rle->alloc = height;
983
984 auto span = rle->spans;
985 for (uint16_t i = 0; i < height; ++i, ++span) {
986 span->x = bbox->min.x;
987 span->y = bbox->min.y + i;
988 span->len = width;
989 span->coverage = 255;
990 }
991
992 return rle;
993 }
994
995
rleReset(SwRle * rle)996 void rleReset(SwRle* rle)
997 {
998 if (!rle) return;
999 rle->size = 0;
1000 }
1001
1002
rleFree(SwRle * rle)1003 void rleFree(SwRle* rle)
1004 {
1005 if (!rle) return;
1006 if (rle->spans) free(rle->spans);
1007 free(rle);
1008 }
1009
1010
rleClip(SwRle * rle,const SwRle * clip)1011 void rleClip(SwRle *rle, const SwRle *clip)
1012 {
1013 if (rle->size == 0 || clip->size == 0) return;
1014 auto spanCnt = rle->size > clip->size ? rle->size : clip->size;
1015 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (spanCnt)));
1016 auto spansEnd = _intersectSpansRegion(clip, rle, spans, spanCnt);
1017
1018 _replaceClipSpan(rle, spans, spansEnd - spans);
1019
1020 TVGLOG("SW_ENGINE", "Using Path Clipping!");
1021 }
1022
1023
rleClip(SwRle * rle,const SwBBox * clip)1024 void rleClip(SwRle *rle, const SwBBox* clip)
1025 {
1026 if (rle->size == 0) return;
1027 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (rle->size)));
1028 auto spansEnd = _intersectSpansRect(clip, rle, spans, rle->size);
1029
1030 _replaceClipSpan(rle, spans, spansEnd - spans);
1031
1032 TVGLOG("SW_ENGINE", "Using Box Clipping!");
1033 }
1034
1035 #endif /* LV_USE_THORVG_INTERNAL */
1036
1037
