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