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