1 | /**************************************************************************** |
2 | * |
3 | * ftgrays.c |
4 | * |
5 | * A new `perfect' anti-aliasing renderer (body). |
6 | * |
7 | * Copyright (C) 2000-2023 by |
8 | * David Turner, Robert Wilhelm, and Werner Lemberg. |
9 | * |
10 | * This file is part of the FreeType project, and may only be used, |
11 | * modified, and distributed under the terms of the FreeType project |
12 | * license, LICENSE.TXT. By continuing to use, modify, or distribute |
13 | * this file you indicate that you have read the license and |
14 | * understand and accept it fully. |
15 | * |
16 | */ |
17 | |
18 | /************************************************************************** |
19 | * |
20 | * This file can be compiled without the rest of the FreeType engine, by |
21 | * defining the STANDALONE_ macro when compiling it. You also need to |
22 | * put the files `ftgrays.h' and `ftimage.h' into the current |
23 | * compilation directory. Typically, you could do something like |
24 | * |
25 | * - copy `src/smooth/ftgrays.c' (this file) to your current directory |
26 | * |
27 | * - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the |
28 | * same directory |
29 | * |
30 | * - compile `ftgrays' with the STANDALONE_ macro defined, as in |
31 | * |
32 | * cc -c -DSTANDALONE_ ftgrays.c |
33 | * |
34 | * The renderer can be initialized with a call to |
35 | * `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated |
36 | * with a call to `ft_gray_raster.raster_render'. |
37 | * |
38 | * See the comments and documentation in the file `ftimage.h' for more |
39 | * details on how the raster works. |
40 | * |
41 | */ |
42 | |
43 | /************************************************************************** |
44 | * |
45 | * This is a new anti-aliasing scan-converter for FreeType 2. The |
46 | * algorithm used here is _very_ different from the one in the standard |
47 | * `ftraster' module. Actually, `ftgrays' computes the _exact_ |
48 | * coverage of the outline on each pixel cell by straight segments. |
49 | * |
50 | * It is based on ideas that I initially found in Raph Levien's |
51 | * excellent LibArt graphics library (see https://www.levien.com/libart |
52 | * for more information, though the web pages do not tell anything |
53 | * about the renderer; you'll have to dive into the source code to |
54 | * understand how it works). |
55 | * |
56 | * Note, however, that this is a _very_ different implementation |
57 | * compared to Raph's. Coverage information is stored in a very |
58 | * different way, and I don't use sorted vector paths. Also, it doesn't |
59 | * use floating point values. |
60 | * |
61 | * Bézier segments are flattened by splitting them until their deviation |
62 | * from straight line becomes much smaller than a pixel. Therefore, the |
63 | * pixel coverage by a Bézier curve is calculated approximately. To |
64 | * estimate the deviation, we use the distance from the control point |
65 | * to the conic chord centre or the cubic chord trisection. These |
66 | * distances vanish fast after each split. In the conic case, they vanish |
67 | * predictably and the number of necessary splits can be calculated. |
68 | * |
69 | * This renderer has the following advantages: |
70 | * |
71 | * - It doesn't need an intermediate bitmap. Instead, one can supply a |
72 | * callback function that will be called by the renderer to draw gray |
73 | * spans on any target surface. You can thus do direct composition on |
74 | * any kind of bitmap, provided that you give the renderer the right |
75 | * callback. |
76 | * |
77 | * - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on |
78 | * each pixel cell by straight segments. |
79 | * |
80 | * - It performs a single pass on the outline (the `standard' FT2 |
81 | * renderer makes two passes). |
82 | * |
83 | * - It can easily be modified to render to _any_ number of gray levels |
84 | * cheaply. |
85 | * |
86 | * - For small (< 80) pixel sizes, it is faster than the standard |
87 | * renderer. |
88 | * |
89 | */ |
90 | |
91 | |
92 | /************************************************************************** |
93 | * |
94 | * The macro FT_COMPONENT is used in trace mode. It is an implicit |
95 | * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log |
96 | * messages during execution. |
97 | */ |
98 | #undef FT_COMPONENT |
99 | #define FT_COMPONENT smooth |
100 | |
101 | |
102 | #ifdef STANDALONE_ |
103 | |
104 | |
105 | /* The size in bytes of the render pool used by the scan-line converter */ |
106 | /* to do all of its work. */ |
107 | #define FT_RENDER_POOL_SIZE 16384L |
108 | |
109 | |
110 | /* Auxiliary macros for token concatenation. */ |
111 | #define FT_ERR_XCAT( x, y ) x ## y |
112 | #define FT_ERR_CAT( x, y ) FT_ERR_XCAT( x, y ) |
113 | |
114 | #define FT_BEGIN_STMNT do { |
115 | #define FT_END_STMNT } while ( 0 ) |
116 | |
117 | #define FT_MIN( a, b ) ( (a) < (b) ? (a) : (b) ) |
118 | #define FT_MAX( a, b ) ( (a) > (b) ? (a) : (b) ) |
119 | #define FT_ABS( a ) ( (a) < 0 ? -(a) : (a) ) |
120 | |
121 | |
122 | /* |
123 | * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min' |
124 | * algorithm. We use alpha = 1, beta = 3/8, giving us results with a |
125 | * largest error less than 7% compared to the exact value. |
126 | */ |
127 | #define FT_HYPOT( x, y ) \ |
128 | ( x = FT_ABS( x ), \ |
129 | y = FT_ABS( y ), \ |
130 | x > y ? x + ( 3 * y >> 3 ) \ |
131 | : y + ( 3 * x >> 3 ) ) |
132 | |
133 | |
134 | /* define this to dump debugging information */ |
135 | /* #define FT_DEBUG_LEVEL_TRACE */ |
136 | |
137 | |
138 | #ifdef FT_DEBUG_LEVEL_TRACE |
139 | #include <stdio.h> |
140 | #include <stdarg.h> |
141 | #endif |
142 | |
143 | #include <stddef.h> |
144 | #include <string.h> |
145 | #include <setjmp.h> |
146 | #include <limits.h> |
147 | #define FT_CHAR_BIT CHAR_BIT |
148 | #define FT_UINT_MAX UINT_MAX |
149 | #define FT_INT_MAX INT_MAX |
150 | #define FT_ULONG_MAX ULONG_MAX |
151 | |
152 | #define ADD_INT( a, b ) \ |
153 | (int)( (unsigned int)(a) + (unsigned int)(b) ) |
154 | |
155 | #define FT_STATIC_BYTE_CAST( type, var ) (type)(unsigned char)(var) |
156 | |
157 | |
158 | #define ft_memset memset |
159 | |
160 | #define ft_setjmp setjmp |
161 | #define ft_longjmp longjmp |
162 | #define ft_jmp_buf jmp_buf |
163 | |
164 | typedef ptrdiff_t FT_PtrDist; |
165 | |
166 | |
167 | #define Smooth_Err_Ok 0 |
168 | #define Smooth_Err_Invalid_Outline -1 |
169 | #define Smooth_Err_Cannot_Render_Glyph -2 |
170 | #define Smooth_Err_Invalid_Argument -3 |
171 | #define Smooth_Err_Raster_Overflow -4 |
172 | |
173 | #define FT_BEGIN_HEADER |
174 | #define FT_END_HEADER |
175 | |
176 | #include "ftimage.h" |
177 | #include "ftgrays.h" |
178 | |
179 | |
180 | /* This macro is used to indicate that a function parameter is unused. */ |
181 | /* Its purpose is simply to reduce compiler warnings. Note also that */ |
182 | /* simply defining it as `(void)x' doesn't avoid warnings with certain */ |
183 | /* ANSI compilers (e.g. LCC). */ |
184 | #define FT_UNUSED( x ) (x) = (x) |
185 | |
186 | |
187 | /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */ |
188 | |
189 | #ifdef FT_DEBUG_LEVEL_TRACE |
190 | |
191 | void |
192 | FT_Message( const char* fmt, |
193 | ... ) |
194 | { |
195 | va_list ap; |
196 | |
197 | |
198 | va_start( ap, fmt ); |
199 | vfprintf( stderr, fmt, ap ); |
200 | va_end( ap ); |
201 | } |
202 | |
203 | |
204 | /* empty function useful for setting a breakpoint to catch errors */ |
205 | int |
206 | FT_Throw( int error, |
207 | int line, |
208 | const char* file ) |
209 | { |
210 | FT_UNUSED( error ); |
211 | FT_UNUSED( line ); |
212 | FT_UNUSED( file ); |
213 | |
214 | return 0; |
215 | } |
216 | |
217 | |
218 | /* we don't handle tracing levels in stand-alone mode; */ |
219 | #ifndef FT_TRACE5 |
220 | #define FT_TRACE5( varformat ) FT_Message varformat |
221 | #endif |
222 | #ifndef FT_TRACE7 |
223 | #define FT_TRACE7( varformat ) FT_Message varformat |
224 | #endif |
225 | #ifndef FT_ERROR |
226 | #define FT_ERROR( varformat ) FT_Message varformat |
227 | #endif |
228 | |
229 | #define FT_THROW( e ) \ |
230 | ( FT_Throw( FT_ERR_CAT( Smooth_Err_, e ), \ |
231 | __LINE__, \ |
232 | __FILE__ ) | \ |
233 | FT_ERR_CAT( Smooth_Err_, e ) ) |
234 | |
235 | #else /* !FT_DEBUG_LEVEL_TRACE */ |
236 | |
237 | #define FT_TRACE5( x ) do { } while ( 0 ) /* nothing */ |
238 | #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */ |
239 | #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */ |
240 | #define FT_THROW( e ) FT_ERR_CAT( Smooth_Err_, e ) |
241 | |
242 | #endif /* !FT_DEBUG_LEVEL_TRACE */ |
243 | |
244 | |
245 | #define FT_Trace_Enable() do { } while ( 0 ) /* nothing */ |
246 | #define FT_Trace_Disable() do { } while ( 0 ) /* nothing */ |
247 | |
248 | |
249 | #define FT_DEFINE_OUTLINE_FUNCS( class_, \ |
250 | move_to_, line_to_, \ |
251 | conic_to_, cubic_to_, \ |
252 | shift_, delta_ ) \ |
253 | static const FT_Outline_Funcs class_ = \ |
254 | { \ |
255 | move_to_, \ |
256 | line_to_, \ |
257 | conic_to_, \ |
258 | cubic_to_, \ |
259 | shift_, \ |
260 | delta_ \ |
261 | }; |
262 | |
263 | #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, \ |
264 | raster_new_, raster_reset_, \ |
265 | raster_set_mode_, raster_render_, \ |
266 | raster_done_ ) \ |
267 | const FT_Raster_Funcs class_ = \ |
268 | { \ |
269 | glyph_format_, \ |
270 | raster_new_, \ |
271 | raster_reset_, \ |
272 | raster_set_mode_, \ |
273 | raster_render_, \ |
274 | raster_done_ \ |
275 | }; |
276 | |
277 | |
278 | #else /* !STANDALONE_ */ |
279 | |
280 | |
281 | #include <ft2build.h> |
282 | #include FT_CONFIG_CONFIG_H |
283 | #include "ftgrays.h" |
284 | #include <freetype/internal/ftobjs.h> |
285 | #include <freetype/internal/ftdebug.h> |
286 | #include <freetype/internal/ftcalc.h> |
287 | #include <freetype/ftoutln.h> |
288 | |
289 | #include "ftsmerrs.h" |
290 | |
291 | |
292 | #endif /* !STANDALONE_ */ |
293 | |
294 | |
295 | #ifndef FT_MEM_SET |
296 | #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c ) |
297 | #endif |
298 | |
299 | #ifndef FT_MEM_ZERO |
300 | #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count ) |
301 | #endif |
302 | |
303 | #ifndef FT_ZERO |
304 | #define FT_ZERO( p ) FT_MEM_ZERO( p, sizeof ( *(p) ) ) |
305 | #endif |
306 | |
307 | /* as usual, for the speed hungry :-) */ |
308 | |
309 | #undef RAS_ARG |
310 | #undef RAS_ARG_ |
311 | #undef RAS_VAR |
312 | #undef RAS_VAR_ |
313 | |
314 | #ifndef FT_STATIC_RASTER |
315 | |
316 | #define RAS_ARG gray_PWorker worker |
317 | #define RAS_ARG_ gray_PWorker worker, |
318 | |
319 | #define RAS_VAR worker |
320 | #define RAS_VAR_ worker, |
321 | |
322 | #else /* FT_STATIC_RASTER */ |
323 | |
324 | #define RAS_ARG void |
325 | #define RAS_ARG_ /* empty */ |
326 | #define RAS_VAR /* empty */ |
327 | #define RAS_VAR_ /* empty */ |
328 | |
329 | #endif /* FT_STATIC_RASTER */ |
330 | |
331 | |
332 | /* must be at least 6 bits! */ |
333 | #define PIXEL_BITS 8 |
334 | |
335 | #define ONE_PIXEL ( 1 << PIXEL_BITS ) |
336 | #undef TRUNC |
337 | #define TRUNC( x ) (TCoord)( (x) >> PIXEL_BITS ) |
338 | #undef FRACT |
339 | #define FRACT( x ) (TCoord)( (x) & ( ONE_PIXEL - 1 ) ) |
340 | |
341 | #if PIXEL_BITS >= 6 |
342 | #define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) ) |
343 | #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) ) |
344 | #else |
345 | #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) ) |
346 | #define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) ) |
347 | #endif |
348 | |
349 | |
350 | /* Compute `dividend / divisor' and return both its quotient and */ |
351 | /* remainder, cast to a specific type. This macro also ensures that */ |
352 | /* the remainder is always positive. We use the remainder to keep */ |
353 | /* track of accumulating errors and compensate for them. */ |
354 | #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ |
355 | FT_BEGIN_STMNT \ |
356 | (quotient) = (type)( (dividend) / (divisor) ); \ |
357 | (remainder) = (type)( (dividend) % (divisor) ); \ |
358 | if ( (remainder) < 0 ) \ |
359 | { \ |
360 | (quotient)--; \ |
361 | (remainder) += (type)(divisor); \ |
362 | } \ |
363 | FT_END_STMNT |
364 | |
365 | #if defined( __GNUC__ ) && __GNUC__ < 7 && defined( __arm__ ) |
366 | /* Work around a bug specific to GCC which make the compiler fail to */ |
367 | /* optimize a division and modulo operation on the same parameters */ |
368 | /* into a single call to `__aeabi_idivmod'. See */ |
369 | /* */ |
370 | /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 */ |
371 | #undef FT_DIV_MOD |
372 | #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ |
373 | FT_BEGIN_STMNT \ |
374 | (quotient) = (type)( (dividend) / (divisor) ); \ |
375 | (remainder) = (type)( (dividend) - (quotient) * (divisor) ); \ |
376 | if ( (remainder) < 0 ) \ |
377 | { \ |
378 | (quotient)--; \ |
379 | (remainder) += (type)(divisor); \ |
380 | } \ |
381 | FT_END_STMNT |
382 | #endif /* __arm__ */ |
383 | |
384 | |
385 | /* Calculating coverages for a slanted line requires a division each */ |
386 | /* time the line crosses from cell to cell. These macros speed up */ |
387 | /* the repetitive divisions by replacing them with multiplications */ |
388 | /* and right shifts so that at most two divisions are performed for */ |
389 | /* each slanted line. Nevertheless, these divisions are noticeable */ |
390 | /* in the overall performance because flattened curves produce a */ |
391 | /* very large number of slanted lines. */ |
392 | /* */ |
393 | /* The division results here are always within ONE_PIXEL. Therefore */ |
394 | /* the shift magnitude should be at least PIXEL_BITS wider than the */ |
395 | /* divisors to provide sufficient accuracy of the multiply-shift. */ |
396 | /* It should not exceed (64 - PIXEL_BITS) to prevent overflowing and */ |
397 | /* leave enough room for 64-bit unsigned multiplication however. */ |
398 | #define FT_UDIVPREP( c, b ) \ |
399 | FT_Int64 b ## _r = c ? (FT_Int64)0xFFFFFFFF / ( b ) : 0 |
400 | #define FT_UDIV( a, b ) \ |
401 | (TCoord)( ( (FT_UInt64)( a ) * (FT_UInt64)( b ## _r ) ) >> 32 ) |
402 | |
403 | |
404 | /* Scale area and apply fill rule to calculate the coverage byte. */ |
405 | /* The top fill bit is used for the non-zero rule. The eighth */ |
406 | /* fill bit is used for the even-odd rule. The higher coverage */ |
407 | /* bytes are either clamped for the non-zero-rule or discarded */ |
408 | /* later for the even-odd rule. */ |
409 | #define FT_FILL_RULE( coverage, area, fill ) \ |
410 | FT_BEGIN_STMNT \ |
411 | coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) ); \ |
412 | if ( coverage & fill ) \ |
413 | coverage = ~coverage; \ |
414 | if ( coverage > 255 && fill & INT_MIN ) \ |
415 | coverage = 255; \ |
416 | FT_END_STMNT |
417 | |
418 | |
419 | /* It is faster to write small spans byte-by-byte than calling */ |
420 | /* `memset'. This is mainly due to the cost of the function call. */ |
421 | #define FT_GRAY_SET( d, s, count ) \ |
422 | FT_BEGIN_STMNT \ |
423 | unsigned char* q = d; \ |
424 | switch ( count ) \ |
425 | { \ |
426 | case 7: *q++ = (unsigned char)s; FALL_THROUGH; \ |
427 | case 6: *q++ = (unsigned char)s; FALL_THROUGH; \ |
428 | case 5: *q++ = (unsigned char)s; FALL_THROUGH; \ |
429 | case 4: *q++ = (unsigned char)s; FALL_THROUGH; \ |
430 | case 3: *q++ = (unsigned char)s; FALL_THROUGH; \ |
431 | case 2: *q++ = (unsigned char)s; FALL_THROUGH; \ |
432 | case 1: *q = (unsigned char)s; FALL_THROUGH; \ |
433 | case 0: break; \ |
434 | default: FT_MEM_SET( d, s, count ); \ |
435 | } \ |
436 | FT_END_STMNT |
437 | |
438 | |
439 | /************************************************************************** |
440 | * |
441 | * TYPE DEFINITIONS |
442 | */ |
443 | |
444 | /* don't change the following types to FT_Int or FT_Pos, since we might */ |
445 | /* need to define them to "float" or "double" when experimenting with */ |
446 | /* new algorithms */ |
447 | |
448 | typedef long TPos; /* subpixel coordinate */ |
449 | typedef int TCoord; /* integer scanline/pixel coordinate */ |
450 | typedef int TArea; /* cell areas, coordinate products */ |
451 | |
452 | |
453 | typedef struct TCell_* PCell; |
454 | |
455 | typedef struct TCell_ |
456 | { |
457 | TCoord x; /* same with gray_TWorker.ex */ |
458 | TCoord cover; /* same with gray_TWorker.cover */ |
459 | TArea area; |
460 | PCell next; |
461 | |
462 | } TCell; |
463 | |
464 | typedef struct TPixmap_ |
465 | { |
466 | unsigned char* origin; /* pixmap origin at the bottom-left */ |
467 | int pitch; /* pitch to go down one row */ |
468 | |
469 | } TPixmap; |
470 | |
471 | /* maximum number of gray cells in the buffer */ |
472 | #if FT_RENDER_POOL_SIZE > 2048 |
473 | #define FT_MAX_GRAY_POOL ( FT_RENDER_POOL_SIZE / sizeof ( TCell ) ) |
474 | #else |
475 | #define FT_MAX_GRAY_POOL ( 2048 / sizeof ( TCell ) ) |
476 | #endif |
477 | |
478 | /* FT_Span buffer size for direct rendering only */ |
479 | #define FT_MAX_GRAY_SPANS 16 |
480 | |
481 | |
482 | #if defined( _MSC_VER ) /* Visual C++ (and Intel C++) */ |
483 | /* We disable the warning `structure was padded due to */ |
484 | /* __declspec(align())' in order to compile cleanly with */ |
485 | /* the maximum level of warnings. */ |
486 | #pragma warning( push ) |
487 | #pragma warning( disable : 4324 ) |
488 | #endif /* _MSC_VER */ |
489 | |
490 | typedef struct gray_TWorker_ |
491 | { |
492 | ft_jmp_buf jump_buffer; |
493 | |
494 | TCoord min_ex, max_ex; /* min and max integer pixel coordinates */ |
495 | TCoord min_ey, max_ey; |
496 | TCoord count_ey; /* same as (max_ey - min_ey) */ |
497 | |
498 | PCell cell; /* current cell */ |
499 | PCell cell_free; /* call allocation next free slot */ |
500 | PCell cell_null; /* last cell, used as dumpster and limit */ |
501 | |
502 | PCell* ycells; /* array of cell linked-lists; one per */ |
503 | /* vertical coordinate in the current band */ |
504 | |
505 | TPos x, y; /* last point position */ |
506 | |
507 | FT_Outline outline; /* input outline */ |
508 | TPixmap target; /* target pixmap */ |
509 | |
510 | FT_Raster_Span_Func render_span; |
511 | void* render_span_data; |
512 | |
513 | } gray_TWorker, *gray_PWorker; |
514 | |
515 | #if defined( _MSC_VER ) |
516 | #pragma warning( pop ) |
517 | #endif |
518 | |
519 | #ifndef FT_STATIC_RASTER |
520 | #define ras (*worker) |
521 | #else |
522 | static gray_TWorker ras; |
523 | #endif |
524 | |
525 | /* The |x| value of the null cell. Must be the largest possible */ |
526 | /* integer value stored in a `TCell.x` field. */ |
527 | #define CELL_MAX_X_VALUE INT_MAX |
528 | |
529 | |
530 | #define FT_INTEGRATE( ras, a, b ) \ |
531 | ras.cell->cover = ADD_INT( ras.cell->cover, a ), \ |
532 | ras.cell->area = ADD_INT( ras.cell->area, (a) * (TArea)(b) ) |
533 | |
534 | |
535 | typedef struct gray_TRaster_ |
536 | { |
537 | void* memory; |
538 | |
539 | } gray_TRaster, *gray_PRaster; |
540 | |
541 | |
542 | #ifdef FT_DEBUG_LEVEL_TRACE |
543 | |
544 | /* to be called while in the debugger -- */ |
545 | /* this function causes a compiler warning since it is unused otherwise */ |
546 | static void |
547 | gray_dump_cells( RAS_ARG ) |
548 | { |
549 | int y; |
550 | |
551 | |
552 | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
553 | { |
554 | PCell cell = ras.ycells[y - ras.min_ey]; |
555 | |
556 | |
557 | printf( "%3d:" , y ); |
558 | |
559 | for ( ; cell != ras.cell_null; cell = cell->next ) |
560 | printf( " (%3d, c:%4d, a:%6d)" , |
561 | cell->x, cell->cover, cell->area ); |
562 | printf( "\n" ); |
563 | } |
564 | } |
565 | |
566 | #endif /* FT_DEBUG_LEVEL_TRACE */ |
567 | |
568 | |
569 | /************************************************************************** |
570 | * |
571 | * Set the current cell to a new position. |
572 | */ |
573 | static void |
574 | gray_set_cell( RAS_ARG_ TCoord ex, |
575 | TCoord ey ) |
576 | { |
577 | /* Move the cell pointer to a new position in the linked list. We use */ |
578 | /* a dumpster null cell for everything outside of the clipping region */ |
579 | /* during the render phase. This means that: */ |
580 | /* */ |
581 | /* . the new vertical position must be within min_ey..max_ey-1. */ |
582 | /* . the new horizontal position must be strictly less than max_ex */ |
583 | /* */ |
584 | /* Note that if a cell is to the left of the clipping region, it is */ |
585 | /* actually set to the (min_ex-1) horizontal position. */ |
586 | |
587 | TCoord ey_index = ey - ras.min_ey; |
588 | |
589 | |
590 | if ( ey_index < 0 || ey_index >= ras.count_ey || ex >= ras.max_ex ) |
591 | ras.cell = ras.cell_null; |
592 | else |
593 | { |
594 | PCell* pcell = ras.ycells + ey_index; |
595 | PCell cell; |
596 | |
597 | |
598 | ex = FT_MAX( ex, ras.min_ex - 1 ); |
599 | |
600 | while ( 1 ) |
601 | { |
602 | cell = *pcell; |
603 | |
604 | if ( cell->x > ex ) |
605 | break; |
606 | |
607 | if ( cell->x == ex ) |
608 | goto Found; |
609 | |
610 | pcell = &cell->next; |
611 | } |
612 | |
613 | /* insert new cell */ |
614 | cell = ras.cell_free++; |
615 | if ( cell >= ras.cell_null ) |
616 | ft_longjmp( ras.jump_buffer, 1 ); |
617 | |
618 | cell->x = ex; |
619 | cell->area = 0; |
620 | cell->cover = 0; |
621 | |
622 | cell->next = *pcell; |
623 | *pcell = cell; |
624 | |
625 | Found: |
626 | ras.cell = cell; |
627 | } |
628 | } |
629 | |
630 | |
631 | #ifndef FT_INT64 |
632 | |
633 | /************************************************************************** |
634 | * |
635 | * Render a scanline as one or more cells. |
636 | */ |
637 | static void |
638 | gray_render_scanline( RAS_ARG_ TCoord ey, |
639 | TPos x1, |
640 | TCoord y1, |
641 | TPos x2, |
642 | TCoord y2 ) |
643 | { |
644 | TCoord ex1, ex2, fx1, fx2, first, dy, delta, mod; |
645 | TPos p, dx; |
646 | int incr; |
647 | |
648 | |
649 | ex1 = TRUNC( x1 ); |
650 | ex2 = TRUNC( x2 ); |
651 | |
652 | /* trivial case. Happens often */ |
653 | if ( y1 == y2 ) |
654 | { |
655 | gray_set_cell( RAS_VAR_ ex2, ey ); |
656 | return; |
657 | } |
658 | |
659 | fx1 = FRACT( x1 ); |
660 | fx2 = FRACT( x2 ); |
661 | |
662 | /* everything is located in a single cell. That is easy! */ |
663 | /* */ |
664 | if ( ex1 == ex2 ) |
665 | goto End; |
666 | |
667 | /* ok, we'll have to render a run of adjacent cells on the same */ |
668 | /* scanline... */ |
669 | /* */ |
670 | dx = x2 - x1; |
671 | dy = y2 - y1; |
672 | |
673 | if ( dx > 0 ) |
674 | { |
675 | p = ( ONE_PIXEL - fx1 ) * dy; |
676 | first = ONE_PIXEL; |
677 | incr = 1; |
678 | } |
679 | else |
680 | { |
681 | p = fx1 * dy; |
682 | first = 0; |
683 | incr = -1; |
684 | dx = -dx; |
685 | } |
686 | |
687 | /* the fractional part of y-delta is mod/dx. It is essential to */ |
688 | /* keep track of its accumulation for accurate rendering. */ |
689 | /* XXX: y-delta and x-delta below should be related. */ |
690 | FT_DIV_MOD( TCoord, p, dx, delta, mod ); |
691 | |
692 | FT_INTEGRATE( ras, delta, fx1 + first ); |
693 | y1 += delta; |
694 | ex1 += incr; |
695 | gray_set_cell( RAS_VAR_ ex1, ey ); |
696 | |
697 | if ( ex1 != ex2 ) |
698 | { |
699 | TCoord lift, rem; |
700 | |
701 | |
702 | p = ONE_PIXEL * dy; |
703 | FT_DIV_MOD( TCoord, p, dx, lift, rem ); |
704 | |
705 | do |
706 | { |
707 | delta = lift; |
708 | mod += rem; |
709 | if ( mod >= (TCoord)dx ) |
710 | { |
711 | mod -= (TCoord)dx; |
712 | delta++; |
713 | } |
714 | |
715 | FT_INTEGRATE( ras, delta, ONE_PIXEL ); |
716 | y1 += delta; |
717 | ex1 += incr; |
718 | gray_set_cell( RAS_VAR_ ex1, ey ); |
719 | } while ( ex1 != ex2 ); |
720 | } |
721 | |
722 | fx1 = ONE_PIXEL - first; |
723 | |
724 | End: |
725 | FT_INTEGRATE( ras, y2 - y1, fx1 + fx2 ); |
726 | } |
727 | |
728 | |
729 | /************************************************************************** |
730 | * |
731 | * Render a given line as a series of scanlines. |
732 | */ |
733 | static void |
734 | gray_render_line( RAS_ARG_ TPos to_x, |
735 | TPos to_y ) |
736 | { |
737 | TCoord ey1, ey2, fy1, fy2, first, delta, mod; |
738 | TPos p, dx, dy, x, x2; |
739 | int incr; |
740 | |
741 | |
742 | ey1 = TRUNC( ras.y ); |
743 | ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */ |
744 | |
745 | /* perform vertical clipping */ |
746 | if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || |
747 | ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) |
748 | goto End; |
749 | |
750 | fy1 = FRACT( ras.y ); |
751 | fy2 = FRACT( to_y ); |
752 | |
753 | /* everything is on a single scanline */ |
754 | if ( ey1 == ey2 ) |
755 | { |
756 | gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 ); |
757 | goto End; |
758 | } |
759 | |
760 | dx = to_x - ras.x; |
761 | dy = to_y - ras.y; |
762 | |
763 | /* vertical line - avoid calling gray_render_scanline */ |
764 | if ( dx == 0 ) |
765 | { |
766 | TCoord ex = TRUNC( ras.x ); |
767 | TCoord two_fx = FRACT( ras.x ) << 1; |
768 | |
769 | |
770 | if ( dy > 0) |
771 | { |
772 | first = ONE_PIXEL; |
773 | incr = 1; |
774 | } |
775 | else |
776 | { |
777 | first = 0; |
778 | incr = -1; |
779 | } |
780 | |
781 | delta = first - fy1; |
782 | FT_INTEGRATE( ras, delta, two_fx); |
783 | ey1 += incr; |
784 | |
785 | gray_set_cell( RAS_VAR_ ex, ey1 ); |
786 | |
787 | delta = first + first - ONE_PIXEL; |
788 | while ( ey1 != ey2 ) |
789 | { |
790 | FT_INTEGRATE( ras, delta, two_fx); |
791 | ey1 += incr; |
792 | |
793 | gray_set_cell( RAS_VAR_ ex, ey1 ); |
794 | } |
795 | |
796 | delta = fy2 - ONE_PIXEL + first; |
797 | FT_INTEGRATE( ras, delta, two_fx); |
798 | |
799 | goto End; |
800 | } |
801 | |
802 | /* ok, we have to render several scanlines */ |
803 | if ( dy > 0) |
804 | { |
805 | p = ( ONE_PIXEL - fy1 ) * dx; |
806 | first = ONE_PIXEL; |
807 | incr = 1; |
808 | } |
809 | else |
810 | { |
811 | p = fy1 * dx; |
812 | first = 0; |
813 | incr = -1; |
814 | dy = -dy; |
815 | } |
816 | |
817 | /* the fractional part of x-delta is mod/dy. It is essential to */ |
818 | /* keep track of its accumulation for accurate rendering. */ |
819 | FT_DIV_MOD( TCoord, p, dy, delta, mod ); |
820 | |
821 | x = ras.x + delta; |
822 | gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first ); |
823 | |
824 | ey1 += incr; |
825 | gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); |
826 | |
827 | if ( ey1 != ey2 ) |
828 | { |
829 | TCoord lift, rem; |
830 | |
831 | |
832 | p = ONE_PIXEL * dx; |
833 | FT_DIV_MOD( TCoord, p, dy, lift, rem ); |
834 | |
835 | do |
836 | { |
837 | delta = lift; |
838 | mod += rem; |
839 | if ( mod >= (TCoord)dy ) |
840 | { |
841 | mod -= (TCoord)dy; |
842 | delta++; |
843 | } |
844 | |
845 | x2 = x + delta; |
846 | gray_render_scanline( RAS_VAR_ ey1, |
847 | x, ONE_PIXEL - first, |
848 | x2, first ); |
849 | x = x2; |
850 | |
851 | ey1 += incr; |
852 | gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); |
853 | } while ( ey1 != ey2 ); |
854 | } |
855 | |
856 | gray_render_scanline( RAS_VAR_ ey1, |
857 | x, ONE_PIXEL - first, |
858 | to_x, fy2 ); |
859 | |
860 | End: |
861 | ras.x = to_x; |
862 | ras.y = to_y; |
863 | } |
864 | |
865 | #else |
866 | |
867 | /************************************************************************** |
868 | * |
869 | * Render a straight line across multiple cells in any direction. |
870 | */ |
871 | static void |
872 | gray_render_line( RAS_ARG_ TPos to_x, |
873 | TPos to_y ) |
874 | { |
875 | TPos dx, dy; |
876 | TCoord fx1, fy1, fx2, fy2; |
877 | TCoord ex1, ey1, ex2, ey2; |
878 | |
879 | |
880 | ey1 = TRUNC( ras.y ); |
881 | ey2 = TRUNC( to_y ); |
882 | |
883 | /* perform vertical clipping */ |
884 | if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || |
885 | ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) |
886 | goto End; |
887 | |
888 | ex1 = TRUNC( ras.x ); |
889 | ex2 = TRUNC( to_x ); |
890 | |
891 | fx1 = FRACT( ras.x ); |
892 | fy1 = FRACT( ras.y ); |
893 | |
894 | dx = to_x - ras.x; |
895 | dy = to_y - ras.y; |
896 | |
897 | if ( ex1 == ex2 && ey1 == ey2 ) /* inside one cell */ |
898 | ; |
899 | else if ( dy == 0 ) /* ex1 != ex2 */ /* any horizontal line */ |
900 | { |
901 | gray_set_cell( RAS_VAR_ ex2, ey2 ); |
902 | goto End; |
903 | } |
904 | else if ( dx == 0 ) |
905 | { |
906 | if ( dy > 0 ) /* vertical line up */ |
907 | do |
908 | { |
909 | fy2 = ONE_PIXEL; |
910 | FT_INTEGRATE( ras, fy2 - fy1, fx1 * 2 ); |
911 | fy1 = 0; |
912 | ey1++; |
913 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
914 | } while ( ey1 != ey2 ); |
915 | else /* vertical line down */ |
916 | do |
917 | { |
918 | fy2 = 0; |
919 | FT_INTEGRATE( ras, fy2 - fy1, fx1 * 2 ); |
920 | fy1 = ONE_PIXEL; |
921 | ey1--; |
922 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
923 | } while ( ey1 != ey2 ); |
924 | } |
925 | else /* any other line */ |
926 | { |
927 | FT_Int64 prod = dx * (FT_Int64)fy1 - dy * (FT_Int64)fx1; |
928 | FT_UDIVPREP( ex1 != ex2, dx ); |
929 | FT_UDIVPREP( ey1 != ey2, dy ); |
930 | |
931 | |
932 | /* The fundamental value `prod' determines which side and the */ |
933 | /* exact coordinate where the line exits current cell. It is */ |
934 | /* also easily updated when moving from one cell to the next. */ |
935 | do |
936 | { |
937 | if ( prod - dx * ONE_PIXEL > 0 && |
938 | prod <= 0 ) /* left */ |
939 | { |
940 | fx2 = 0; |
941 | fy2 = FT_UDIV( -prod, -dx ); |
942 | prod -= dy * ONE_PIXEL; |
943 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
944 | fx1 = ONE_PIXEL; |
945 | fy1 = fy2; |
946 | ex1--; |
947 | } |
948 | else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL > 0 && |
949 | prod - dx * ONE_PIXEL <= 0 ) /* up */ |
950 | { |
951 | prod -= dx * ONE_PIXEL; |
952 | fx2 = FT_UDIV( -prod, dy ); |
953 | fy2 = ONE_PIXEL; |
954 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
955 | fx1 = fx2; |
956 | fy1 = 0; |
957 | ey1++; |
958 | } |
959 | else if ( prod + dy * ONE_PIXEL >= 0 && |
960 | prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 ) /* right */ |
961 | { |
962 | prod += dy * ONE_PIXEL; |
963 | fx2 = ONE_PIXEL; |
964 | fy2 = FT_UDIV( prod, dx ); |
965 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
966 | fx1 = 0; |
967 | fy1 = fy2; |
968 | ex1++; |
969 | } |
970 | else /* ( prod > 0 && |
971 | prod + dy * ONE_PIXEL < 0 ) down */ |
972 | { |
973 | fx2 = FT_UDIV( prod, -dy ); |
974 | fy2 = 0; |
975 | prod += dx * ONE_PIXEL; |
976 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
977 | fx1 = fx2; |
978 | fy1 = ONE_PIXEL; |
979 | ey1--; |
980 | } |
981 | |
982 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
983 | |
984 | } while ( ex1 != ex2 || ey1 != ey2 ); |
985 | } |
986 | |
987 | fx2 = FRACT( to_x ); |
988 | fy2 = FRACT( to_y ); |
989 | |
990 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
991 | |
992 | End: |
993 | ras.x = to_x; |
994 | ras.y = to_y; |
995 | } |
996 | |
997 | #endif |
998 | |
999 | /* |
1000 | * Benchmarking shows that using DDA to flatten the quadratic Bézier arcs |
1001 | * is slightly faster in the following cases: |
1002 | * |
1003 | * - When the host CPU is 64-bit. |
1004 | * - When SSE2 SIMD registers and instructions are available (even on |
1005 | * x86). |
1006 | * |
1007 | * For other cases, using binary splits is actually slightly faster. |
1008 | */ |
1009 | #if ( defined( __SSE2__ ) || \ |
1010 | defined( __x86_64__ ) || \ |
1011 | defined( _M_AMD64 ) || \ |
1012 | ( defined( _M_IX86_FP ) && _M_IX86_FP >= 2 ) ) && \ |
1013 | !defined( __VMS ) |
1014 | # define FT_SSE2 1 |
1015 | #else |
1016 | # define FT_SSE2 0 |
1017 | #endif |
1018 | |
1019 | #if FT_SSE2 || \ |
1020 | defined( __aarch64__ ) || \ |
1021 | defined( _M_ARM64 ) |
1022 | # define BEZIER_USE_DDA 1 |
1023 | #else |
1024 | # define BEZIER_USE_DDA 0 |
1025 | #endif |
1026 | |
1027 | /* |
1028 | * For now, the code that depends on `BEZIER_USE_DDA` requires `FT_Int64` |
1029 | * to be defined. If `FT_INT64` is not defined, meaning there is no |
1030 | * 64-bit type available, disable it to avoid compilation errors. See for |
1031 | * example https://gitlab.freedesktop.org/freetype/freetype/-/issues/1071. |
1032 | */ |
1033 | #if !defined( FT_INT64 ) |
1034 | # undef BEZIER_USE_DDA |
1035 | # define BEZIER_USE_DDA 0 |
1036 | #endif |
1037 | |
1038 | #if BEZIER_USE_DDA |
1039 | |
1040 | #if FT_SSE2 |
1041 | # include <emmintrin.h> |
1042 | #endif |
1043 | |
1044 | #define LEFT_SHIFT( a, b ) (FT_Int64)( (FT_UInt64)(a) << (b) ) |
1045 | |
1046 | |
1047 | static void |
1048 | gray_render_conic( RAS_ARG_ const FT_Vector* control, |
1049 | const FT_Vector* to ) |
1050 | { |
1051 | FT_Vector p0, p1, p2; |
1052 | TPos ax, ay, bx, by, dx, dy; |
1053 | int shift; |
1054 | |
1055 | FT_Int64 rx, ry; |
1056 | FT_Int64 qx, qy; |
1057 | FT_Int64 px, py; |
1058 | |
1059 | FT_UInt count; |
1060 | |
1061 | |
1062 | p0.x = ras.x; |
1063 | p0.y = ras.y; |
1064 | p1.x = UPSCALE( control->x ); |
1065 | p1.y = UPSCALE( control->y ); |
1066 | p2.x = UPSCALE( to->x ); |
1067 | p2.y = UPSCALE( to->y ); |
1068 | |
1069 | /* short-cut the arc that crosses the current band */ |
1070 | if ( ( TRUNC( p0.y ) >= ras.max_ey && |
1071 | TRUNC( p1.y ) >= ras.max_ey && |
1072 | TRUNC( p2.y ) >= ras.max_ey ) || |
1073 | ( TRUNC( p0.y ) < ras.min_ey && |
1074 | TRUNC( p1.y ) < ras.min_ey && |
1075 | TRUNC( p2.y ) < ras.min_ey ) ) |
1076 | { |
1077 | ras.x = p2.x; |
1078 | ras.y = p2.y; |
1079 | return; |
1080 | } |
1081 | |
1082 | bx = p1.x - p0.x; |
1083 | by = p1.y - p0.y; |
1084 | ax = p2.x - p1.x - bx; /* p0.x + p2.x - 2 * p1.x */ |
1085 | ay = p2.y - p1.y - by; /* p0.y + p2.y - 2 * p1.y */ |
1086 | |
1087 | dx = FT_ABS( ax ); |
1088 | dy = FT_ABS( ay ); |
1089 | if ( dx < dy ) |
1090 | dx = dy; |
1091 | |
1092 | if ( dx <= ONE_PIXEL / 4 ) |
1093 | { |
1094 | gray_render_line( RAS_VAR_ p2.x, p2.y ); |
1095 | return; |
1096 | } |
1097 | |
1098 | /* We can calculate the number of necessary bisections because */ |
1099 | /* each bisection predictably reduces deviation exactly 4-fold. */ |
1100 | /* Even 32-bit deviation would vanish after 16 bisections. */ |
1101 | shift = 0; |
1102 | do |
1103 | { |
1104 | dx >>= 2; |
1105 | shift += 1; |
1106 | |
1107 | } while ( dx > ONE_PIXEL / 4 ); |
1108 | |
1109 | /* |
1110 | * The (P0,P1,P2) arc equation, for t in [0,1] range: |
1111 | * |
1112 | * P(t) = P0*(1-t)^2 + P1*2*t*(1-t) + P2*t^2 |
1113 | * |
1114 | * P(t) = P0 + 2*(P1-P0)*t + (P0+P2-2*P1)*t^2 |
1115 | * = P0 + 2*B*t + A*t^2 |
1116 | * |
1117 | * for A = P0 + P2 - 2*P1 |
1118 | * and B = P1 - P0 |
1119 | * |
1120 | * Let's consider the difference when advancing by a small |
1121 | * parameter h: |
1122 | * |
1123 | * Q(h,t) = P(t+h) - P(t) = 2*B*h + A*h^2 + 2*A*h*t |
1124 | * |
1125 | * And then its own difference: |
1126 | * |
1127 | * R(h,t) = Q(h,t+h) - Q(h,t) = 2*A*h*h = R (constant) |
1128 | * |
1129 | * Since R is always a constant, it is possible to compute |
1130 | * successive positions with: |
1131 | * |
1132 | * P = P0 |
1133 | * Q = Q(h,0) = 2*B*h + A*h*h |
1134 | * R = 2*A*h*h |
1135 | * |
1136 | * loop: |
1137 | * P += Q |
1138 | * Q += R |
1139 | * EMIT(P) |
1140 | * |
1141 | * To ensure accurate results, perform computations on 64-bit |
1142 | * values, after scaling them by 2^32. |
1143 | * |
1144 | * h = 1 / 2^N |
1145 | * |
1146 | * R << 32 = 2 * A << (32 - N - N) |
1147 | * = A << (33 - 2*N) |
1148 | * |
1149 | * Q << 32 = (2 * B << (32 - N)) + (A << (32 - N - N)) |
1150 | * = (B << (33 - N)) + (A << (32 - 2*N)) |
1151 | */ |
1152 | |
1153 | #if FT_SSE2 |
1154 | /* Experience shows that for small shift values, */ |
1155 | /* SSE2 is actually slower. */ |
1156 | if ( shift > 2 ) |
1157 | { |
1158 | union |
1159 | { |
1160 | struct { FT_Int64 ax, ay, bx, by; } i; |
1161 | struct { __m128i a, b; } vec; |
1162 | |
1163 | } u; |
1164 | |
1165 | union |
1166 | { |
1167 | struct { FT_Int32 px_lo, px_hi, py_lo, py_hi; } i; |
1168 | __m128i vec; |
1169 | |
1170 | } v; |
1171 | |
1172 | __m128i a, b; |
1173 | __m128i r, q, q2; |
1174 | __m128i p; |
1175 | |
1176 | |
1177 | u.i.ax = ax; |
1178 | u.i.ay = ay; |
1179 | u.i.bx = bx; |
1180 | u.i.by = by; |
1181 | |
1182 | a = _mm_load_si128( &u.vec.a ); |
1183 | b = _mm_load_si128( &u.vec.b ); |
1184 | |
1185 | r = _mm_slli_epi64( a, 33 - 2 * shift ); |
1186 | q = _mm_slli_epi64( b, 33 - shift ); |
1187 | q2 = _mm_slli_epi64( a, 32 - 2 * shift ); |
1188 | |
1189 | q = _mm_add_epi64( q2, q ); |
1190 | |
1191 | v.i.px_lo = 0; |
1192 | v.i.px_hi = p0.x; |
1193 | v.i.py_lo = 0; |
1194 | v.i.py_hi = p0.y; |
1195 | |
1196 | p = _mm_load_si128( &v.vec ); |
1197 | |
1198 | for ( count = 1U << shift; count > 0; count-- ) |
1199 | { |
1200 | p = _mm_add_epi64( p, q ); |
1201 | q = _mm_add_epi64( q, r ); |
1202 | |
1203 | _mm_store_si128( &v.vec, p ); |
1204 | |
1205 | gray_render_line( RAS_VAR_ v.i.px_hi, v.i.py_hi ); |
1206 | } |
1207 | |
1208 | return; |
1209 | } |
1210 | #endif /* FT_SSE2 */ |
1211 | |
1212 | rx = LEFT_SHIFT( ax, 33 - 2 * shift ); |
1213 | ry = LEFT_SHIFT( ay, 33 - 2 * shift ); |
1214 | |
1215 | qx = LEFT_SHIFT( bx, 33 - shift ) + LEFT_SHIFT( ax, 32 - 2 * shift ); |
1216 | qy = LEFT_SHIFT( by, 33 - shift ) + LEFT_SHIFT( ay, 32 - 2 * shift ); |
1217 | |
1218 | px = LEFT_SHIFT( p0.x, 32 ); |
1219 | py = LEFT_SHIFT( p0.y, 32 ); |
1220 | |
1221 | for ( count = 1U << shift; count > 0; count-- ) |
1222 | { |
1223 | px += qx; |
1224 | py += qy; |
1225 | qx += rx; |
1226 | qy += ry; |
1227 | |
1228 | gray_render_line( RAS_VAR_ (FT_Pos)( px >> 32 ), |
1229 | (FT_Pos)( py >> 32 ) ); |
1230 | } |
1231 | } |
1232 | |
1233 | #else /* !BEZIER_USE_DDA */ |
1234 | |
1235 | /* |
1236 | * Note that multiple attempts to speed up the function below |
1237 | * with SSE2 intrinsics, using various data layouts, have turned |
1238 | * out to be slower than the non-SIMD code below. |
1239 | */ |
1240 | static void |
1241 | gray_split_conic( FT_Vector* base ) |
1242 | { |
1243 | TPos a, b; |
1244 | |
1245 | |
1246 | base[4].x = base[2].x; |
1247 | a = base[0].x + base[1].x; |
1248 | b = base[1].x + base[2].x; |
1249 | base[3].x = b >> 1; |
1250 | base[2].x = ( a + b ) >> 2; |
1251 | base[1].x = a >> 1; |
1252 | |
1253 | base[4].y = base[2].y; |
1254 | a = base[0].y + base[1].y; |
1255 | b = base[1].y + base[2].y; |
1256 | base[3].y = b >> 1; |
1257 | base[2].y = ( a + b ) >> 2; |
1258 | base[1].y = a >> 1; |
1259 | } |
1260 | |
1261 | |
1262 | static void |
1263 | gray_render_conic( RAS_ARG_ const FT_Vector* control, |
1264 | const FT_Vector* to ) |
1265 | { |
1266 | FT_Vector bez_stack[16 * 2 + 1]; /* enough to accommodate bisections */ |
1267 | FT_Vector* arc = bez_stack; |
1268 | TPos dx, dy; |
1269 | int draw; |
1270 | |
1271 | |
1272 | arc[0].x = UPSCALE( to->x ); |
1273 | arc[0].y = UPSCALE( to->y ); |
1274 | arc[1].x = UPSCALE( control->x ); |
1275 | arc[1].y = UPSCALE( control->y ); |
1276 | arc[2].x = ras.x; |
1277 | arc[2].y = ras.y; |
1278 | |
1279 | /* short-cut the arc that crosses the current band */ |
1280 | if ( ( TRUNC( arc[0].y ) >= ras.max_ey && |
1281 | TRUNC( arc[1].y ) >= ras.max_ey && |
1282 | TRUNC( arc[2].y ) >= ras.max_ey ) || |
1283 | ( TRUNC( arc[0].y ) < ras.min_ey && |
1284 | TRUNC( arc[1].y ) < ras.min_ey && |
1285 | TRUNC( arc[2].y ) < ras.min_ey ) ) |
1286 | { |
1287 | ras.x = arc[0].x; |
1288 | ras.y = arc[0].y; |
1289 | return; |
1290 | } |
1291 | |
1292 | dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x ); |
1293 | dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y ); |
1294 | if ( dx < dy ) |
1295 | dx = dy; |
1296 | |
1297 | /* We can calculate the number of necessary bisections because */ |
1298 | /* each bisection predictably reduces deviation exactly 4-fold. */ |
1299 | /* Even 32-bit deviation would vanish after 16 bisections. */ |
1300 | draw = 1; |
1301 | while ( dx > ONE_PIXEL / 4 ) |
1302 | { |
1303 | dx >>= 2; |
1304 | draw <<= 1; |
1305 | } |
1306 | |
1307 | /* We use decrement counter to count the total number of segments */ |
1308 | /* to draw starting from 2^level. Before each draw we split as */ |
1309 | /* many times as there are trailing zeros in the counter. */ |
1310 | do |
1311 | { |
1312 | int split = draw & ( -draw ); /* isolate the rightmost 1-bit */ |
1313 | |
1314 | |
1315 | while ( ( split >>= 1 ) ) |
1316 | { |
1317 | gray_split_conic( arc ); |
1318 | arc += 2; |
1319 | } |
1320 | |
1321 | gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); |
1322 | arc -= 2; |
1323 | |
1324 | } while ( --draw ); |
1325 | } |
1326 | |
1327 | #endif /* !BEZIER_USE_DDA */ |
1328 | |
1329 | |
1330 | /* |
1331 | * For cubic Bézier, binary splits are still faster than DDA |
1332 | * because the splits are adaptive to how quickly each sub-arc |
1333 | * approaches their chord trisection points. |
1334 | * |
1335 | * It might be useful to experiment with SSE2 to speed up |
1336 | * `gray_split_cubic`, though. |
1337 | */ |
1338 | static void |
1339 | gray_split_cubic( FT_Vector* base ) |
1340 | { |
1341 | TPos a, b, c; |
1342 | |
1343 | |
1344 | base[6].x = base[3].x; |
1345 | a = base[0].x + base[1].x; |
1346 | b = base[1].x + base[2].x; |
1347 | c = base[2].x + base[3].x; |
1348 | base[5].x = c >> 1; |
1349 | c += b; |
1350 | base[4].x = c >> 2; |
1351 | base[1].x = a >> 1; |
1352 | a += b; |
1353 | base[2].x = a >> 2; |
1354 | base[3].x = ( a + c ) >> 3; |
1355 | |
1356 | base[6].y = base[3].y; |
1357 | a = base[0].y + base[1].y; |
1358 | b = base[1].y + base[2].y; |
1359 | c = base[2].y + base[3].y; |
1360 | base[5].y = c >> 1; |
1361 | c += b; |
1362 | base[4].y = c >> 2; |
1363 | base[1].y = a >> 1; |
1364 | a += b; |
1365 | base[2].y = a >> 2; |
1366 | base[3].y = ( a + c ) >> 3; |
1367 | } |
1368 | |
1369 | |
1370 | static void |
1371 | gray_render_cubic( RAS_ARG_ const FT_Vector* control1, |
1372 | const FT_Vector* control2, |
1373 | const FT_Vector* to ) |
1374 | { |
1375 | FT_Vector bez_stack[16 * 3 + 1]; /* enough to accommodate bisections */ |
1376 | FT_Vector* arc = bez_stack; |
1377 | |
1378 | |
1379 | arc[0].x = UPSCALE( to->x ); |
1380 | arc[0].y = UPSCALE( to->y ); |
1381 | arc[1].x = UPSCALE( control2->x ); |
1382 | arc[1].y = UPSCALE( control2->y ); |
1383 | arc[2].x = UPSCALE( control1->x ); |
1384 | arc[2].y = UPSCALE( control1->y ); |
1385 | arc[3].x = ras.x; |
1386 | arc[3].y = ras.y; |
1387 | |
1388 | /* short-cut the arc that crosses the current band */ |
1389 | if ( ( TRUNC( arc[0].y ) >= ras.max_ey && |
1390 | TRUNC( arc[1].y ) >= ras.max_ey && |
1391 | TRUNC( arc[2].y ) >= ras.max_ey && |
1392 | TRUNC( arc[3].y ) >= ras.max_ey ) || |
1393 | ( TRUNC( arc[0].y ) < ras.min_ey && |
1394 | TRUNC( arc[1].y ) < ras.min_ey && |
1395 | TRUNC( arc[2].y ) < ras.min_ey && |
1396 | TRUNC( arc[3].y ) < ras.min_ey ) ) |
1397 | { |
1398 | ras.x = arc[0].x; |
1399 | ras.y = arc[0].y; |
1400 | return; |
1401 | } |
1402 | |
1403 | for (;;) |
1404 | { |
1405 | /* with each split, control points quickly converge towards */ |
1406 | /* chord trisection points and the vanishing distances below */ |
1407 | /* indicate when the segment is flat enough to draw */ |
1408 | if ( FT_ABS( 2 * arc[0].x - 3 * arc[1].x + arc[3].x ) > ONE_PIXEL / 2 || |
1409 | FT_ABS( 2 * arc[0].y - 3 * arc[1].y + arc[3].y ) > ONE_PIXEL / 2 || |
1410 | FT_ABS( arc[0].x - 3 * arc[2].x + 2 * arc[3].x ) > ONE_PIXEL / 2 || |
1411 | FT_ABS( arc[0].y - 3 * arc[2].y + 2 * arc[3].y ) > ONE_PIXEL / 2 ) |
1412 | goto Split; |
1413 | |
1414 | gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); |
1415 | |
1416 | if ( arc == bez_stack ) |
1417 | return; |
1418 | |
1419 | arc -= 3; |
1420 | continue; |
1421 | |
1422 | Split: |
1423 | gray_split_cubic( arc ); |
1424 | arc += 3; |
1425 | } |
1426 | } |
1427 | |
1428 | |
1429 | static int |
1430 | gray_move_to( const FT_Vector* to, |
1431 | void* worker_ ) /* gray_PWorker */ |
1432 | { |
1433 | gray_PWorker worker = (gray_PWorker)worker_; |
1434 | |
1435 | TPos x, y; |
1436 | |
1437 | |
1438 | /* start to a new position */ |
1439 | x = UPSCALE( to->x ); |
1440 | y = UPSCALE( to->y ); |
1441 | |
1442 | gray_set_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) ); |
1443 | |
1444 | ras.x = x; |
1445 | ras.y = y; |
1446 | return 0; |
1447 | } |
1448 | |
1449 | |
1450 | static int |
1451 | gray_line_to( const FT_Vector* to, |
1452 | void* worker_ ) /* gray_PWorker */ |
1453 | { |
1454 | gray_PWorker worker = (gray_PWorker)worker_; |
1455 | |
1456 | |
1457 | gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) ); |
1458 | return 0; |
1459 | } |
1460 | |
1461 | |
1462 | static int |
1463 | gray_conic_to( const FT_Vector* control, |
1464 | const FT_Vector* to, |
1465 | void* worker_ ) /* gray_PWorker */ |
1466 | { |
1467 | gray_PWorker worker = (gray_PWorker)worker_; |
1468 | |
1469 | |
1470 | gray_render_conic( RAS_VAR_ control, to ); |
1471 | return 0; |
1472 | } |
1473 | |
1474 | |
1475 | static int |
1476 | gray_cubic_to( const FT_Vector* control1, |
1477 | const FT_Vector* control2, |
1478 | const FT_Vector* to, |
1479 | void* worker_ ) /* gray_PWorker */ |
1480 | { |
1481 | gray_PWorker worker = (gray_PWorker)worker_; |
1482 | |
1483 | |
1484 | gray_render_cubic( RAS_VAR_ control1, control2, to ); |
1485 | return 0; |
1486 | } |
1487 | |
1488 | |
1489 | static void |
1490 | gray_sweep( RAS_ARG ) |
1491 | { |
1492 | int fill = ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) ? 0x100 |
1493 | : INT_MIN; |
1494 | int coverage; |
1495 | int y; |
1496 | |
1497 | |
1498 | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
1499 | { |
1500 | PCell cell = ras.ycells[y - ras.min_ey]; |
1501 | TCoord x = ras.min_ex; |
1502 | TArea cover = 0; |
1503 | |
1504 | unsigned char* line = ras.target.origin - ras.target.pitch * y; |
1505 | |
1506 | |
1507 | for ( ; cell != ras.cell_null; cell = cell->next ) |
1508 | { |
1509 | TArea area; |
1510 | |
1511 | |
1512 | if ( cover != 0 && cell->x > x ) |
1513 | { |
1514 | FT_FILL_RULE( coverage, cover, fill ); |
1515 | FT_GRAY_SET( line + x, coverage, cell->x - x ); |
1516 | } |
1517 | |
1518 | cover += (TArea)cell->cover * ( ONE_PIXEL * 2 ); |
1519 | area = cover - cell->area; |
1520 | |
1521 | if ( area != 0 && cell->x >= ras.min_ex ) |
1522 | { |
1523 | FT_FILL_RULE( coverage, area, fill ); |
1524 | line[cell->x] = (unsigned char)coverage; |
1525 | } |
1526 | |
1527 | x = cell->x + 1; |
1528 | } |
1529 | |
1530 | if ( cover != 0 ) /* only if cropped */ |
1531 | { |
1532 | FT_FILL_RULE( coverage, cover, fill ); |
1533 | FT_GRAY_SET( line + x, coverage, ras.max_ex - x ); |
1534 | } |
1535 | } |
1536 | } |
1537 | |
1538 | |
1539 | static void |
1540 | gray_sweep_direct( RAS_ARG ) |
1541 | { |
1542 | int fill = ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) ? 0x100 |
1543 | : INT_MIN; |
1544 | int coverage; |
1545 | int y; |
1546 | |
1547 | FT_Span span[FT_MAX_GRAY_SPANS]; |
1548 | int n = 0; |
1549 | |
1550 | |
1551 | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
1552 | { |
1553 | PCell cell = ras.ycells[y - ras.min_ey]; |
1554 | TCoord x = ras.min_ex; |
1555 | TArea cover = 0; |
1556 | |
1557 | |
1558 | for ( ; cell != ras.cell_null; cell = cell->next ) |
1559 | { |
1560 | TArea area; |
1561 | |
1562 | |
1563 | if ( cover != 0 && cell->x > x ) |
1564 | { |
1565 | FT_FILL_RULE( coverage, cover, fill ); |
1566 | |
1567 | span[n].coverage = (unsigned char)coverage; |
1568 | span[n].x = (short)x; |
1569 | span[n].len = (unsigned short)( cell->x - x ); |
1570 | |
1571 | if ( ++n == FT_MAX_GRAY_SPANS ) |
1572 | { |
1573 | /* flush the span buffer and reset the count */ |
1574 | ras.render_span( y, n, span, ras.render_span_data ); |
1575 | n = 0; |
1576 | } |
1577 | } |
1578 | |
1579 | cover += (TArea)cell->cover * ( ONE_PIXEL * 2 ); |
1580 | area = cover - cell->area; |
1581 | |
1582 | if ( area != 0 && cell->x >= ras.min_ex ) |
1583 | { |
1584 | FT_FILL_RULE( coverage, area, fill ); |
1585 | |
1586 | span[n].coverage = (unsigned char)coverage; |
1587 | span[n].x = (short)cell->x; |
1588 | span[n].len = 1; |
1589 | |
1590 | if ( ++n == FT_MAX_GRAY_SPANS ) |
1591 | { |
1592 | /* flush the span buffer and reset the count */ |
1593 | ras.render_span( y, n, span, ras.render_span_data ); |
1594 | n = 0; |
1595 | } |
1596 | } |
1597 | |
1598 | x = cell->x + 1; |
1599 | } |
1600 | |
1601 | if ( cover != 0 ) /* only if cropped */ |
1602 | { |
1603 | FT_FILL_RULE( coverage, cover, fill ); |
1604 | |
1605 | span[n].coverage = (unsigned char)coverage; |
1606 | span[n].x = (short)x; |
1607 | span[n].len = (unsigned short)( ras.max_ex - x ); |
1608 | |
1609 | ++n; |
1610 | } |
1611 | |
1612 | if ( n ) |
1613 | { |
1614 | /* flush the span buffer and reset the count */ |
1615 | ras.render_span( y, n, span, ras.render_span_data ); |
1616 | n = 0; |
1617 | } |
1618 | } |
1619 | } |
1620 | |
1621 | |
1622 | #ifdef STANDALONE_ |
1623 | |
1624 | /************************************************************************** |
1625 | * |
1626 | * The following functions should only compile in stand-alone mode, |
1627 | * i.e., when building this component without the rest of FreeType. |
1628 | * |
1629 | */ |
1630 | |
1631 | /************************************************************************** |
1632 | * |
1633 | * @Function: |
1634 | * FT_Outline_Decompose |
1635 | * |
1636 | * @Description: |
1637 | * Walk over an outline's structure to decompose it into individual |
1638 | * segments and Bézier arcs. This function is also able to emit |
1639 | * `move to' and `close to' operations to indicate the start and end |
1640 | * of new contours in the outline. |
1641 | * |
1642 | * @Input: |
1643 | * outline :: |
1644 | * A pointer to the source target. |
1645 | * |
1646 | * func_interface :: |
1647 | * A table of `emitters', i.e., function pointers |
1648 | * called during decomposition to indicate path |
1649 | * operations. |
1650 | * |
1651 | * @InOut: |
1652 | * user :: |
1653 | * A typeless pointer which is passed to each |
1654 | * emitter during the decomposition. It can be |
1655 | * used to store the state during the |
1656 | * decomposition. |
1657 | * |
1658 | * @Return: |
1659 | * Error code. 0 means success. |
1660 | */ |
1661 | static int |
1662 | FT_Outline_Decompose( const FT_Outline* outline, |
1663 | const FT_Outline_Funcs* func_interface, |
1664 | void* user ) |
1665 | { |
1666 | #undef SCALED |
1667 | #define SCALED( x ) ( (x) * ( 1L << shift ) - delta ) |
1668 | |
1669 | FT_Vector v_last; |
1670 | FT_Vector v_control; |
1671 | FT_Vector v_start; |
1672 | |
1673 | FT_Vector* point; |
1674 | FT_Vector* limit; |
1675 | char* tags; |
1676 | |
1677 | int error; |
1678 | |
1679 | int n; /* index of contour in outline */ |
1680 | int first; /* index of first point in contour */ |
1681 | int last; /* index of last point in contour */ |
1682 | |
1683 | char tag; /* current point's state */ |
1684 | |
1685 | int shift; |
1686 | TPos delta; |
1687 | |
1688 | |
1689 | if ( !outline ) |
1690 | return FT_THROW( Invalid_Outline ); |
1691 | |
1692 | if ( !func_interface ) |
1693 | return FT_THROW( Invalid_Argument ); |
1694 | |
1695 | shift = func_interface->shift; |
1696 | delta = func_interface->delta; |
1697 | |
1698 | last = -1; |
1699 | for ( n = 0; n < outline->n_contours; n++ ) |
1700 | { |
1701 | FT_TRACE5(( "FT_Outline_Decompose: Contour %d\n" , n )); |
1702 | |
1703 | first = last + 1; |
1704 | last = outline->contours[n]; |
1705 | if ( last < first ) |
1706 | goto Invalid_Outline; |
1707 | |
1708 | limit = outline->points + last; |
1709 | |
1710 | v_start = outline->points[first]; |
1711 | v_start.x = SCALED( v_start.x ); |
1712 | v_start.y = SCALED( v_start.y ); |
1713 | |
1714 | v_last = outline->points[last]; |
1715 | v_last.x = SCALED( v_last.x ); |
1716 | v_last.y = SCALED( v_last.y ); |
1717 | |
1718 | v_control = v_start; |
1719 | |
1720 | point = outline->points + first; |
1721 | tags = outline->tags + first; |
1722 | tag = FT_CURVE_TAG( tags[0] ); |
1723 | |
1724 | /* A contour cannot start with a cubic control point! */ |
1725 | if ( tag == FT_CURVE_TAG_CUBIC ) |
1726 | goto Invalid_Outline; |
1727 | |
1728 | /* check first point to determine origin */ |
1729 | if ( tag == FT_CURVE_TAG_CONIC ) |
1730 | { |
1731 | /* first point is conic control. Yes, this happens. */ |
1732 | if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON ) |
1733 | { |
1734 | /* start at last point if it is on the curve */ |
1735 | v_start = v_last; |
1736 | limit--; |
1737 | } |
1738 | else |
1739 | { |
1740 | /* if both first and last points are conic, */ |
1741 | /* start at their middle and record its position */ |
1742 | /* for closure */ |
1743 | v_start.x = ( v_start.x + v_last.x ) / 2; |
1744 | v_start.y = ( v_start.y + v_last.y ) / 2; |
1745 | |
1746 | v_last = v_start; |
1747 | } |
1748 | point--; |
1749 | tags--; |
1750 | } |
1751 | |
1752 | FT_TRACE5(( " move to (%.2f, %.2f)\n" , |
1753 | v_start.x / 64.0, v_start.y / 64.0 )); |
1754 | error = func_interface->move_to( &v_start, user ); |
1755 | if ( error ) |
1756 | goto Exit; |
1757 | |
1758 | while ( point < limit ) |
1759 | { |
1760 | point++; |
1761 | tags++; |
1762 | |
1763 | tag = FT_CURVE_TAG( tags[0] ); |
1764 | switch ( tag ) |
1765 | { |
1766 | case FT_CURVE_TAG_ON: /* emit a single line_to */ |
1767 | { |
1768 | FT_Vector vec; |
1769 | |
1770 | |
1771 | vec.x = SCALED( point->x ); |
1772 | vec.y = SCALED( point->y ); |
1773 | |
1774 | FT_TRACE5(( " line to (%.2f, %.2f)\n" , |
1775 | vec.x / 64.0, vec.y / 64.0 )); |
1776 | error = func_interface->line_to( &vec, user ); |
1777 | if ( error ) |
1778 | goto Exit; |
1779 | continue; |
1780 | } |
1781 | |
1782 | case FT_CURVE_TAG_CONIC: /* consume conic arcs */ |
1783 | v_control.x = SCALED( point->x ); |
1784 | v_control.y = SCALED( point->y ); |
1785 | |
1786 | Do_Conic: |
1787 | if ( point < limit ) |
1788 | { |
1789 | FT_Vector vec; |
1790 | FT_Vector v_middle; |
1791 | |
1792 | |
1793 | point++; |
1794 | tags++; |
1795 | tag = FT_CURVE_TAG( tags[0] ); |
1796 | |
1797 | vec.x = SCALED( point->x ); |
1798 | vec.y = SCALED( point->y ); |
1799 | |
1800 | if ( tag == FT_CURVE_TAG_ON ) |
1801 | { |
1802 | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1803 | " with control (%.2f, %.2f)\n" , |
1804 | vec.x / 64.0, vec.y / 64.0, |
1805 | v_control.x / 64.0, v_control.y / 64.0 )); |
1806 | error = func_interface->conic_to( &v_control, &vec, user ); |
1807 | if ( error ) |
1808 | goto Exit; |
1809 | continue; |
1810 | } |
1811 | |
1812 | if ( tag != FT_CURVE_TAG_CONIC ) |
1813 | goto Invalid_Outline; |
1814 | |
1815 | v_middle.x = ( v_control.x + vec.x ) / 2; |
1816 | v_middle.y = ( v_control.y + vec.y ) / 2; |
1817 | |
1818 | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1819 | " with control (%.2f, %.2f)\n" , |
1820 | v_middle.x / 64.0, v_middle.y / 64.0, |
1821 | v_control.x / 64.0, v_control.y / 64.0 )); |
1822 | error = func_interface->conic_to( &v_control, &v_middle, user ); |
1823 | if ( error ) |
1824 | goto Exit; |
1825 | |
1826 | v_control = vec; |
1827 | goto Do_Conic; |
1828 | } |
1829 | |
1830 | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1831 | " with control (%.2f, %.2f)\n" , |
1832 | v_start.x / 64.0, v_start.y / 64.0, |
1833 | v_control.x / 64.0, v_control.y / 64.0 )); |
1834 | error = func_interface->conic_to( &v_control, &v_start, user ); |
1835 | goto Close; |
1836 | |
1837 | default: /* FT_CURVE_TAG_CUBIC */ |
1838 | { |
1839 | FT_Vector vec1, vec2; |
1840 | |
1841 | |
1842 | if ( point + 1 > limit || |
1843 | FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC ) |
1844 | goto Invalid_Outline; |
1845 | |
1846 | point += 2; |
1847 | tags += 2; |
1848 | |
1849 | vec1.x = SCALED( point[-2].x ); |
1850 | vec1.y = SCALED( point[-2].y ); |
1851 | |
1852 | vec2.x = SCALED( point[-1].x ); |
1853 | vec2.y = SCALED( point[-1].y ); |
1854 | |
1855 | if ( point <= limit ) |
1856 | { |
1857 | FT_Vector vec; |
1858 | |
1859 | |
1860 | vec.x = SCALED( point->x ); |
1861 | vec.y = SCALED( point->y ); |
1862 | |
1863 | FT_TRACE5(( " cubic to (%.2f, %.2f)" |
1864 | " with controls (%.2f, %.2f) and (%.2f, %.2f)\n" , |
1865 | vec.x / 64.0, vec.y / 64.0, |
1866 | vec1.x / 64.0, vec1.y / 64.0, |
1867 | vec2.x / 64.0, vec2.y / 64.0 )); |
1868 | error = func_interface->cubic_to( &vec1, &vec2, &vec, user ); |
1869 | if ( error ) |
1870 | goto Exit; |
1871 | continue; |
1872 | } |
1873 | |
1874 | FT_TRACE5(( " cubic to (%.2f, %.2f)" |
1875 | " with controls (%.2f, %.2f) and (%.2f, %.2f)\n" , |
1876 | v_start.x / 64.0, v_start.y / 64.0, |
1877 | vec1.x / 64.0, vec1.y / 64.0, |
1878 | vec2.x / 64.0, vec2.y / 64.0 )); |
1879 | error = func_interface->cubic_to( &vec1, &vec2, &v_start, user ); |
1880 | goto Close; |
1881 | } |
1882 | } |
1883 | } |
1884 | |
1885 | /* close the contour with a line segment */ |
1886 | FT_TRACE5(( " line to (%.2f, %.2f)\n" , |
1887 | v_start.x / 64.0, v_start.y / 64.0 )); |
1888 | error = func_interface->line_to( &v_start, user ); |
1889 | |
1890 | Close: |
1891 | if ( error ) |
1892 | goto Exit; |
1893 | } |
1894 | |
1895 | FT_TRACE5(( "FT_Outline_Decompose: Done\n" , n )); |
1896 | return Smooth_Err_Ok; |
1897 | |
1898 | Exit: |
1899 | FT_TRACE5(( "FT_Outline_Decompose: Error 0x%x\n" , error )); |
1900 | return error; |
1901 | |
1902 | Invalid_Outline: |
1903 | return FT_THROW( Invalid_Outline ); |
1904 | } |
1905 | |
1906 | #endif /* STANDALONE_ */ |
1907 | |
1908 | |
1909 | FT_DEFINE_OUTLINE_FUNCS( |
1910 | func_interface, |
1911 | |
1912 | (FT_Outline_MoveTo_Func) gray_move_to, /* move_to */ |
1913 | (FT_Outline_LineTo_Func) gray_line_to, /* line_to */ |
1914 | (FT_Outline_ConicTo_Func)gray_conic_to, /* conic_to */ |
1915 | (FT_Outline_CubicTo_Func)gray_cubic_to, /* cubic_to */ |
1916 | |
1917 | 0, /* shift */ |
1918 | 0 /* delta */ |
1919 | ) |
1920 | |
1921 | |
1922 | static int |
1923 | gray_convert_glyph_inner( RAS_ARG_ |
1924 | int continued ) |
1925 | { |
1926 | volatile int error; |
1927 | |
1928 | |
1929 | if ( ft_setjmp( ras.jump_buffer ) == 0 ) |
1930 | { |
1931 | if ( continued ) |
1932 | FT_Trace_Disable(); |
1933 | error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras ); |
1934 | if ( continued ) |
1935 | FT_Trace_Enable(); |
1936 | |
1937 | FT_TRACE7(( "band [%d..%d]: %td cell%s remaining/\n" , |
1938 | ras.min_ey, |
1939 | ras.max_ey, |
1940 | ras.cell_null - ras.cell_free, |
1941 | ras.cell_null - ras.cell_free == 1 ? "" : "s" )); |
1942 | } |
1943 | else |
1944 | { |
1945 | error = FT_THROW( Raster_Overflow ); |
1946 | |
1947 | FT_TRACE7(( "band [%d..%d]: to be bisected\n" , |
1948 | ras.min_ey, ras.max_ey )); |
1949 | } |
1950 | |
1951 | return error; |
1952 | } |
1953 | |
1954 | |
1955 | static int |
1956 | gray_convert_glyph( RAS_ARG ) |
1957 | { |
1958 | const TCoord yMin = ras.min_ey; |
1959 | const TCoord yMax = ras.max_ey; |
1960 | |
1961 | TCell buffer[FT_MAX_GRAY_POOL]; |
1962 | size_t height = (size_t)( yMax - yMin ); |
1963 | size_t n = FT_MAX_GRAY_POOL / 8; |
1964 | TCoord y; |
1965 | TCoord bands[32]; /* enough to accommodate bisections */ |
1966 | TCoord* band; |
1967 | |
1968 | int continued = 0; |
1969 | |
1970 | |
1971 | /* Initialize the null cell at the end of the poll. */ |
1972 | ras.cell_null = buffer + FT_MAX_GRAY_POOL - 1; |
1973 | ras.cell_null->x = CELL_MAX_X_VALUE; |
1974 | ras.cell_null->area = 0; |
1975 | ras.cell_null->cover = 0; |
1976 | ras.cell_null->next = NULL; |
1977 | |
1978 | /* set up vertical bands */ |
1979 | ras.ycells = (PCell*)buffer; |
1980 | |
1981 | if ( height > n ) |
1982 | { |
1983 | /* two divisions rounded up */ |
1984 | n = ( height + n - 1 ) / n; |
1985 | height = ( height + n - 1 ) / n; |
1986 | } |
1987 | |
1988 | for ( y = yMin; y < yMax; ) |
1989 | { |
1990 | ras.min_ey = y; |
1991 | y += height; |
1992 | ras.max_ey = FT_MIN( y, yMax ); |
1993 | |
1994 | band = bands; |
1995 | band[1] = ras.min_ey; |
1996 | band[0] = ras.max_ey; |
1997 | |
1998 | do |
1999 | { |
2000 | TCoord width = band[0] - band[1]; |
2001 | TCoord w; |
2002 | int error; |
2003 | |
2004 | |
2005 | for ( w = 0; w < width; ++w ) |
2006 | ras.ycells[w] = ras.cell_null; |
2007 | |
2008 | /* memory management: skip ycells */ |
2009 | n = ( (size_t)width * sizeof ( PCell ) + sizeof ( TCell ) - 1 ) / |
2010 | sizeof ( TCell ); |
2011 | |
2012 | ras.cell_free = buffer + n; |
2013 | ras.cell = ras.cell_null; |
2014 | ras.min_ey = band[1]; |
2015 | ras.max_ey = band[0]; |
2016 | ras.count_ey = width; |
2017 | |
2018 | error = gray_convert_glyph_inner( RAS_VAR_ continued ); |
2019 | continued = 1; |
2020 | |
2021 | if ( !error ) |
2022 | { |
2023 | if ( ras.render_span ) /* for FT_RASTER_FLAG_DIRECT only */ |
2024 | gray_sweep_direct( RAS_VAR ); |
2025 | else |
2026 | gray_sweep( RAS_VAR ); |
2027 | band--; |
2028 | continue; |
2029 | } |
2030 | else if ( error != Smooth_Err_Raster_Overflow ) |
2031 | return error; |
2032 | |
2033 | /* render pool overflow; we will reduce the render band by half */ |
2034 | width >>= 1; |
2035 | |
2036 | /* this should never happen even with tiny rendering pool */ |
2037 | if ( width == 0 ) |
2038 | { |
2039 | FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" )); |
2040 | return FT_THROW( Raster_Overflow ); |
2041 | } |
2042 | |
2043 | band++; |
2044 | band[1] = band[0]; |
2045 | band[0] += width; |
2046 | } while ( band >= bands ); |
2047 | } |
2048 | |
2049 | return Smooth_Err_Ok; |
2050 | } |
2051 | |
2052 | |
2053 | static int |
2054 | gray_raster_render( FT_Raster raster, |
2055 | const FT_Raster_Params* params ) |
2056 | { |
2057 | const FT_Outline* outline = (const FT_Outline*)params->source; |
2058 | const FT_Bitmap* target_map = params->target; |
2059 | |
2060 | #ifndef FT_STATIC_RASTER |
2061 | gray_TWorker worker[1]; |
2062 | #endif |
2063 | |
2064 | |
2065 | if ( !raster ) |
2066 | return FT_THROW( Invalid_Argument ); |
2067 | |
2068 | /* this version does not support monochrome rendering */ |
2069 | if ( !( params->flags & FT_RASTER_FLAG_AA ) ) |
2070 | return FT_THROW( Cannot_Render_Glyph ); |
2071 | |
2072 | if ( !outline ) |
2073 | return FT_THROW( Invalid_Outline ); |
2074 | |
2075 | /* return immediately if the outline is empty */ |
2076 | if ( outline->n_points == 0 || outline->n_contours <= 0 ) |
2077 | return Smooth_Err_Ok; |
2078 | |
2079 | if ( !outline->contours || !outline->points ) |
2080 | return FT_THROW( Invalid_Outline ); |
2081 | |
2082 | if ( outline->n_points != |
2083 | outline->contours[outline->n_contours - 1] + 1 ) |
2084 | return FT_THROW( Invalid_Outline ); |
2085 | |
2086 | ras.outline = *outline; |
2087 | |
2088 | if ( params->flags & FT_RASTER_FLAG_DIRECT ) |
2089 | { |
2090 | if ( !params->gray_spans ) |
2091 | return Smooth_Err_Ok; |
2092 | |
2093 | ras.render_span = (FT_Raster_Span_Func)params->gray_spans; |
2094 | ras.render_span_data = params->user; |
2095 | |
2096 | ras.min_ex = params->clip_box.xMin; |
2097 | ras.min_ey = params->clip_box.yMin; |
2098 | ras.max_ex = params->clip_box.xMax; |
2099 | ras.max_ey = params->clip_box.yMax; |
2100 | } |
2101 | else |
2102 | { |
2103 | /* if direct mode is not set, we must have a target bitmap */ |
2104 | if ( !target_map ) |
2105 | return FT_THROW( Invalid_Argument ); |
2106 | |
2107 | /* nothing to do */ |
2108 | if ( !target_map->width || !target_map->rows ) |
2109 | return Smooth_Err_Ok; |
2110 | |
2111 | if ( !target_map->buffer ) |
2112 | return FT_THROW( Invalid_Argument ); |
2113 | |
2114 | if ( target_map->pitch < 0 ) |
2115 | ras.target.origin = target_map->buffer; |
2116 | else |
2117 | ras.target.origin = target_map->buffer |
2118 | + ( target_map->rows - 1 ) * (unsigned int)target_map->pitch; |
2119 | |
2120 | ras.target.pitch = target_map->pitch; |
2121 | |
2122 | ras.render_span = (FT_Raster_Span_Func)NULL; |
2123 | ras.render_span_data = NULL; |
2124 | |
2125 | ras.min_ex = 0; |
2126 | ras.min_ey = 0; |
2127 | ras.max_ex = (FT_Pos)target_map->width; |
2128 | ras.max_ey = (FT_Pos)target_map->rows; |
2129 | } |
2130 | |
2131 | /* exit if nothing to do */ |
2132 | if ( ras.max_ex <= ras.min_ex || ras.max_ey <= ras.min_ey ) |
2133 | return Smooth_Err_Ok; |
2134 | |
2135 | return gray_convert_glyph( RAS_VAR ); |
2136 | } |
2137 | |
2138 | |
2139 | /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/ |
2140 | /**** a static object. *****/ |
2141 | |
2142 | #ifdef STANDALONE_ |
2143 | |
2144 | static int |
2145 | gray_raster_new( void* memory, |
2146 | FT_Raster* araster ) |
2147 | { |
2148 | static gray_TRaster the_raster; |
2149 | |
2150 | FT_UNUSED( memory ); |
2151 | |
2152 | |
2153 | *araster = (FT_Raster)&the_raster; |
2154 | FT_ZERO( &the_raster ); |
2155 | |
2156 | return 0; |
2157 | } |
2158 | |
2159 | |
2160 | static void |
2161 | gray_raster_done( FT_Raster raster ) |
2162 | { |
2163 | /* nothing */ |
2164 | FT_UNUSED( raster ); |
2165 | } |
2166 | |
2167 | #else /* !STANDALONE_ */ |
2168 | |
2169 | static int |
2170 | gray_raster_new( void* memory_, |
2171 | FT_Raster* araster_ ) |
2172 | { |
2173 | FT_Memory memory = (FT_Memory)memory_; |
2174 | gray_PRaster* araster = (gray_PRaster*)araster_; |
2175 | |
2176 | FT_Error error; |
2177 | gray_PRaster raster = NULL; |
2178 | |
2179 | |
2180 | if ( !FT_NEW( raster ) ) |
2181 | raster->memory = memory; |
2182 | |
2183 | *araster = raster; |
2184 | |
2185 | return error; |
2186 | } |
2187 | |
2188 | |
2189 | static void |
2190 | gray_raster_done( FT_Raster raster ) |
2191 | { |
2192 | FT_Memory memory = (FT_Memory)((gray_PRaster)raster)->memory; |
2193 | |
2194 | |
2195 | FT_FREE( raster ); |
2196 | } |
2197 | |
2198 | #endif /* !STANDALONE_ */ |
2199 | |
2200 | |
2201 | static void |
2202 | gray_raster_reset( FT_Raster raster, |
2203 | unsigned char* pool_base, |
2204 | unsigned long pool_size ) |
2205 | { |
2206 | FT_UNUSED( raster ); |
2207 | FT_UNUSED( pool_base ); |
2208 | FT_UNUSED( pool_size ); |
2209 | } |
2210 | |
2211 | |
2212 | static int |
2213 | gray_raster_set_mode( FT_Raster raster, |
2214 | unsigned long mode, |
2215 | void* args ) |
2216 | { |
2217 | FT_UNUSED( raster ); |
2218 | FT_UNUSED( mode ); |
2219 | FT_UNUSED( args ); |
2220 | |
2221 | |
2222 | return 0; /* nothing to do */ |
2223 | } |
2224 | |
2225 | |
2226 | FT_DEFINE_RASTER_FUNCS( |
2227 | ft_grays_raster, |
2228 | |
2229 | FT_GLYPH_FORMAT_OUTLINE, |
2230 | |
2231 | (FT_Raster_New_Func) gray_raster_new, /* raster_new */ |
2232 | (FT_Raster_Reset_Func) gray_raster_reset, /* raster_reset */ |
2233 | (FT_Raster_Set_Mode_Func)gray_raster_set_mode, /* raster_set_mode */ |
2234 | (FT_Raster_Render_Func) gray_raster_render, /* raster_render */ |
2235 | (FT_Raster_Done_Func) gray_raster_done /* raster_done */ |
2236 | ) |
2237 | |
2238 | |
2239 | /* END */ |
2240 | |
2241 | |
2242 | /* Local Variables: */ |
2243 | /* coding: utf-8 */ |
2244 | /* End: */ |
2245 | |