1 /***************************************************************************/
5 /* The FreeType glyph rasterizer (body). */
7 /* Copyright 1996-2001 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
18 /*************************************************************************/
20 /* This is a rewrite of the FreeType 1.x scan-line converter */
22 /*************************************************************************/
27 #include FT_INTERNAL_CALC_H /* for FT_MulDiv only */
30 /*************************************************************************/
32 /* A simple technical note on how the raster works */
33 /* ----------------------------------------------- */
35 /* Converting an outline into a bitmap is achieved in several steps: */
37 /* 1 - Decomposing the outline into successive `profiles'. Each */
38 /* profile is simply an array of scanline intersections on a given */
39 /* dimension. A profile's main attributes are */
41 /* o its scanline position boundaries, i.e. `Ymin' and `Ymax'. */
43 /* o an array of intersection coordinates for each scanline */
44 /* between `Ymin' and `Ymax'. */
46 /* o a direction, indicating whether it was built going `up' or */
47 /* `down', as this is very important for filling rules. */
49 /* 2 - Sweeping the target map's scanlines in order to compute segment */
50 /* `spans' which are then filled. Additionally, this pass */
51 /* performs drop-out control. */
53 /* The outline data is parsed during step 1 only. The profiles are */
54 /* built from the bottom of the render pool, used as a stack. The */
55 /* following graphics shows the profile list under construction: */
57 /* ____________________________________________________________ _ _ */
59 /* | profile | coordinates for | profile | coordinates for |--> */
60 /* | 1 | profile 1 | 2 | profile 2 |--> */
61 /* |_________|___________________|_________|_________________|__ _ _ */
65 /* start of render pool top */
67 /* The top of the profile stack is kept in the `top' variable. */
69 /* As you can see, a profile record is pushed on top of the render */
70 /* pool, which is then followed by its coordinates/intersections. If */
71 /* a change of direction is detected in the outline, a new profile is */
72 /* generated until the end of the outline. */
74 /* Note that when all profiles have been generated, the function */
75 /* Finalize_Profile_Table() is used to record, for each profile, its */
76 /* bottom-most scanline as well as the scanline above its upmost */
77 /* boundary. These positions are called `y-turns' because they (sort */
78 /* of) correspond to local extrema. They are stored in a sorted list */
79 /* built from the top of the render pool as a downwards stack: */
81 /* _ _ _______________________________________ */
83 /* <--| sorted list of | */
84 /* <--| extrema scanlines | */
85 /* _ _ __________________|____________________| */
89 /* maxBuff sizeBuff = end of pool */
91 /* This list is later used during the sweep phase in order to */
92 /* optimize performance (see technical note on the sweep below). */
94 /* Of course, the raster detects whether the two stacks collide and */
95 /* handles the situation propertly. */
97 /*************************************************************************/
100 /*************************************************************************/
101 /*************************************************************************/
103 /** CONFIGURATION MACROS **/
105 /*************************************************************************/
106 /*************************************************************************/
108 /* define DEBUG_RASTER if you want to compile a debugging version */
109 #define xxxDEBUG_RASTER
111 /* The default render pool size in bytes */
112 #define RASTER_RENDER_POOL 8192
114 /* undefine FT_RASTER_OPTION_ANTI_ALIASING if you do not want to support */
115 /* 5-levels anti-aliasing */
116 #ifdef FT_CONFIG_OPTION_5_GRAY_LEVELS
117 #define FT_RASTER_OPTION_ANTI_ALIASING
120 /* The size of the two-lines intermediate bitmap used */
121 /* for anti-aliasing, in bytes. */
122 #define RASTER_GRAY_LINES 2048
125 /*************************************************************************/
126 /*************************************************************************/
128 /** OTHER MACROS (do not change) **/
130 /*************************************************************************/
131 /*************************************************************************/
133 /*************************************************************************/
135 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
136 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
137 /* messages during execution. */
140 #define FT_COMPONENT trace_raster
146 /* This macro is used to indicate that a function parameter is unused. */
147 /* Its purpose is simply to reduce compiler warnings. Note also that */
148 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
149 /* ANSI compilers (e.g. LCC). */
150 #define FT_UNUSED( x ) (x) = (x)
152 /* Disable the tracing mechanism for simplicity -- developers can */
153 /* activate it easily by redefining these two macros. */
155 #define FT_ERROR( x ) do ; while ( 0 ) /* nothing */
159 #define FT_TRACE( x ) do ; while ( 0 ) /* nothing */
162 #define Raster_Err_None 0
163 #define Raster_Err_Not_Ini -1
164 #define Raster_Err_Overflow -2
165 #define Raster_Err_Neg_Height -3
166 #define Raster_Err_Invalid -4
167 #define Raster_Err_Unsupported -5
170 #else /* _STANDALONE_ */
173 #include FT_INTERNAL_OBJECTS_H
174 #include FT_INTERNAL_DEBUG_H /* for FT_TRACE() and FT_ERROR() */
176 #include "rasterrs.h"
178 #define Raster_Err_None Raster_Err_Ok
179 #define Raster_Err_Not_Ini Raster_Err_Raster_Uninitialized
180 #define Raster_Err_Overflow Raster_Err_Raster_Overflow
181 #define Raster_Err_Neg_Height Raster_Err_Raster_Negative_Height
182 #define Raster_Err_Invalid Raster_Err_Invalid_Outline
183 #define Raster_Err_Unsupported Raster_Err_Cannot_Render_Glyph
186 #endif /* _STANDALONE_ */
189 /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is */
190 /* typically a small value and the result of a*b is known to fit into */
192 #define FMulDiv( a, b, c ) ( (a) * (b) / (c) )
194 /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */
195 /* for clipping computations. It simply uses the FT_MulDiv() function */
196 /* defined in `ftcalc.h'. */
197 #define SMulDiv FT_MulDiv
199 /* The rasterizer is a very general purpose component; please leave */
200 /* the following redefinitions there (you never know your target */
212 #define NULL (void*)0
224 #define MaxBezier 32 /* The maximum number of stacked Bezier curves. */
225 /* Setting this constant to more than 32 is a */
226 /* pure waste of space. */
228 #define Pixel_Bits 6 /* fractional bits of *input* coordinates */
231 /*************************************************************************/
232 /*************************************************************************/
234 /** SIMPLE TYPE DECLARATIONS **/
236 /*************************************************************************/
237 /*************************************************************************/
240 typedef unsigned int UInt;
242 typedef unsigned short UShort, *PUShort;
243 typedef long Long, *PLong;
244 typedef unsigned long ULong;
246 typedef unsigned char Byte, *PByte;
249 typedef struct TPoint_
266 /* States of each line, arc, and profile */
267 typedef enum TStates_
277 typedef struct TProfile_ TProfile;
278 typedef TProfile* PProfile;
282 FT_F26Dot6 X; /* current coordinate during sweep */
283 PProfile link; /* link to next profile - various purpose */
284 PLong offset; /* start of profile's data in render pool */
285 int flow; /* Profile orientation: Asc/Descending */
286 long height; /* profile's height in scanlines */
287 long start; /* profile's starting scanline */
289 unsigned countL; /* number of lines to step before this */
290 /* profile becomes drawable */
292 PProfile next; /* next profile in same contour, used */
293 /* during drop-out control */
296 typedef PProfile TProfileList;
297 typedef PProfile* PProfileList;
300 /* Simple record used to implement a stack of bands, required */
301 /* by the sub-banding mechanism */
302 typedef struct TBand_
304 Short y_min; /* band's minimum */
305 Short y_max; /* band's maximum */
310 #define AlignProfileSize \
311 ( ( sizeof ( TProfile ) + sizeof ( long ) - 1 ) / sizeof ( long ) )
314 #ifdef TT_STATIC_RASTER
317 #define RAS_ARGS /* void */
318 #define RAS_ARG /* void */
320 #define RAS_VARS /* void */
321 #define RAS_VAR /* void */
323 #define FT_UNUSED_RASTER do ; while ( 0 )
326 #else /* TT_STATIC_RASTER */
329 #define RAS_ARGS TRaster_Instance* raster,
330 #define RAS_ARG TRaster_Instance* raster
332 #define RAS_VARS raster,
333 #define RAS_VAR raster
335 #define FT_UNUSED_RASTER FT_UNUSED( raster )
338 #endif /* TT_STATIC_RASTER */
341 typedef struct TRaster_Instance_ TRaster_Instance;
344 /* prototypes used for sweep function dispatch */
346 Function_Sweep_Init( RAS_ARGS Short* min,
350 Function_Sweep_Span( RAS_ARGS Short y,
357 Function_Sweep_Step( RAS_ARG );
360 /* NOTE: These operations are only valid on 2's complement processors */
362 #define FLOOR( x ) ( (x) & -ras.precision )
363 #define CEILING( x ) ( ( (x) + ras.precision - 1 ) & -ras.precision )
364 #define TRUNC( x ) ( (signed long)(x) >> ras.precision_bits )
365 #define FRAC( x ) ( (x) & ( ras.precision - 1 ) )
366 #define SCALED( x ) ( ( (x) << ras.scale_shift ) - ras.precision_half )
368 /* Note that I have moved the location of some fields in the */
369 /* structure to ensure that the most used variables are used */
370 /* at the top. Thus, their offset can be coded with less */
371 /* opcodes, and it results in a smaller executable. */
373 struct TRaster_Instance_
375 Int precision_bits; /* precision related variables */
381 Int precision_jitter;
383 Int scale_shift; /* == precision_shift for bitmaps */
384 /* == precision_shift+1 for pixmaps */
386 PLong buff; /* The profiles buffer */
387 PLong sizeBuff; /* Render pool size */
388 PLong maxBuff; /* Profiles buffer size */
389 PLong top; /* Current cursor in buffer */
393 Int numTurns; /* number of Y-turns in outline */
395 TPoint* arc; /* current Bezier arc pointer */
397 UShort bWidth; /* target bitmap width */
398 PByte bTarget; /* target bitmap buffer */
399 PByte gTarget; /* target pixmap buffer */
401 Long lastX, lastY, minY, maxY;
403 UShort num_Profs; /* current number of profiles */
405 Bool fresh; /* signals a fresh new profile which */
406 /* 'start' field must be completed */
407 Bool joint; /* signals that the last arc ended */
408 /* exactly on a scanline. Allows */
409 /* removal of doublets */
410 PProfile cProfile; /* current profile */
411 PProfile fProfile; /* head of linked list of profiles */
412 PProfile gProfile; /* contour's first profile in case */
415 TStates state; /* rendering state */
417 FT_Bitmap target; /* description of target bit/pixmap */
420 Long traceOfs; /* current offset in target bitmap */
421 Long traceG; /* current offset in target pixmap */
423 Short traceIncr; /* sweep's increment in target bitmap */
425 Short gray_min_x; /* current min x during gray rendering */
426 Short gray_max_x; /* current max x during gray rendering */
428 /* dispatch variables */
430 Function_Sweep_Init* Proc_Sweep_Init;
431 Function_Sweep_Span* Proc_Sweep_Span;
432 Function_Sweep_Span* Proc_Sweep_Drop;
433 Function_Sweep_Step* Proc_Sweep_Step;
435 Byte dropOutControl; /* current drop_out control method */
437 Bool second_pass; /* indicates wether a horizontal pass */
438 /* should be performed to control */
439 /* drop-out accurately when calling */
440 /* Render_Glyph. Note that there is */
441 /* no horizontal pass during gray */
444 TPoint arcs[3 * MaxBezier + 1]; /* The Bezier stack */
446 TBand band_stack[16]; /* band stack used for sub-banding */
447 Int band_top; /* band stack top */
449 Int count_table[256]; /* Look-up table used to quickly count */
450 /* set bits in a gray 2x2 cell */
454 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
456 Byte grays[5]; /* Palette of gray levels used for */
459 Byte gray_lines[RASTER_GRAY_LINES];
460 /* Intermediate table used to render the */
461 /* graylevels pixmaps. */
462 /* gray_lines is a buffer holding two */
463 /* monochrome scanlines */
465 Short gray_width; /* width in bytes of one monochrome */
466 /* intermediate scanline of gray_lines. */
467 /* Each gray pixel takes 2 bits long there */
469 /* The gray_lines must hold 2 lines, thus with size */
470 /* in bytes of at least `gray_width*2'. */
472 #endif /* FT_RASTER_ANTI_ALIASING */
475 PByte flags; /* current flags table */
476 PUShort outs; /* current outlines table */
479 UShort nPoints; /* number of points in current glyph */
480 Short nContours; /* number of contours in current glyph */
486 #ifdef FT_CONFIG_OPTION_STATIC_RASTER
488 static TRaster_Instance cur_ras;
493 #define ras (*raster)
495 #endif /* FT_CONFIG_OPTION_STATIC_RASTER */
498 /*************************************************************************/
499 /*************************************************************************/
501 /** PROFILES COMPUTATION **/
503 /*************************************************************************/
504 /*************************************************************************/
507 /*************************************************************************/
510 /* Set_High_Precision */
513 /* Sets precision variables according to param flag. */
516 /* High :: Set to True for high precision (typically for ppem < 18), */
517 /* false otherwise. */
520 Set_High_Precision( RAS_ARGS Int High )
524 ras.precision_bits = 10;
525 ras.precision_step = 128;
526 ras.precision_jitter = 24;
530 ras.precision_bits = 6;
531 ras.precision_step = 32;
532 ras.precision_jitter = 2;
535 FT_TRACE6(( "Set_High_Precision(%s)\n", High ? "true" : "false" ));
537 ras.precision = 1L << ras.precision_bits;
538 ras.precision_half = ras.precision / 2;
539 ras.precision_shift = ras.precision_bits - Pixel_Bits;
540 ras.precision_mask = -ras.precision;
544 /*************************************************************************/
550 /* Creates a new profile in the render pool. */
553 /* aState :: The state/orientation of the new profile. */
556 /* SUCCESS on success. FAILURE in case of overflow or of incoherent */
560 New_Profile( RAS_ARGS TStates aState )
564 ras.cProfile = (PProfile)ras.top;
565 ras.fProfile = ras.cProfile;
566 ras.top += AlignProfileSize;
569 if ( ras.top >= ras.maxBuff )
571 ras.error = Raster_Err_Overflow;
578 ras.cProfile->flow = Flow_Up;
579 FT_TRACE6(( "New ascending profile = %lx\n", (long)ras.cProfile ));
583 ras.cProfile->flow = Flow_Down;
584 FT_TRACE6(( "New descending profile = %lx\n", (long)ras.cProfile ));
588 FT_ERROR(( "New_Profile: invalid profile direction!\n" ));
589 ras.error = Raster_Err_Invalid;
593 ras.cProfile->start = 0;
594 ras.cProfile->height = 0;
595 ras.cProfile->offset = ras.top;
596 ras.cProfile->link = (PProfile)0;
597 ras.cProfile->next = (PProfile)0;
600 ras.gProfile = ras.cProfile;
610 /*************************************************************************/
616 /* Finalizes the current profile. */
619 /* SUCCESS on success. FAILURE in case of overflow or incoherency. */
622 End_Profile( RAS_ARG )
628 h = (Long)( ras.top - ras.cProfile->offset );
632 FT_ERROR(( "End_Profile: negative height encountered!\n" ));
633 ras.error = Raster_Err_Neg_Height;
639 FT_TRACE6(( "Ending profile %lx, start = %ld, height = %ld\n",
640 (long)ras.cProfile, ras.cProfile->start, h ));
642 oldProfile = ras.cProfile;
643 ras.cProfile->height = h;
644 ras.cProfile = (PProfile)ras.top;
646 ras.top += AlignProfileSize;
648 ras.cProfile->height = 0;
649 ras.cProfile->offset = ras.top;
650 oldProfile->next = ras.cProfile;
654 if ( ras.top >= ras.maxBuff )
656 FT_TRACE1(( "overflow in End_Profile\n" ));
657 ras.error = Raster_Err_Overflow;
667 /*************************************************************************/
673 /* Inserts a salient into the sorted list placed on top of the render */
677 /* New y scanline position. */
680 /* SUCCESS on success. FAILURE in case of overflow. */
683 Insert_Y_Turn( RAS_ARGS Int y )
689 n = ras.numTurns - 1;
690 y_turns = ras.sizeBuff - ras.numTurns;
692 /* look for first y value that is <= */
693 while ( n >= 0 && y < y_turns[n] )
696 /* if it is <, simply insert it, ignore if == */
697 if ( n >= 0 && y > y_turns[n] )
708 if ( ras.maxBuff <= ras.top )
710 ras.error = Raster_Err_Overflow;
715 ras.sizeBuff[-ras.numTurns] = y;
722 /*************************************************************************/
725 /* Finalize_Profile_Table */
728 /* Adjusts all links in the profiles list. */
731 /* SUCCESS on success. FAILURE in case of overflow. */
734 Finalize_Profile_Table( RAS_ARG )
749 p->link = (PProfile)( p->offset + p->height );
756 bottom = p->start - p->height+1;
759 p->offset += p->height - 1;
765 top = p->start + p->height - 1;
768 if ( Insert_Y_Turn( RAS_VARS bottom ) ||
769 Insert_Y_Turn( RAS_VARS top + 1 ) )
783 /*************************************************************************/
789 /* Subdivides one conic Bezier into two joint sub-arcs in the Bezier */
793 /* None (subdivided Bezier is taken from the top of the stack). */
796 /* This routine is the `beef' of this component. It is _the_ inner */
797 /* loop that should be optimized to hell to get the best performance. */
800 Split_Conic( TPoint* base )
805 base[4].x = base[2].x;
807 a = base[3].x = ( base[2].x + b ) / 2;
808 b = base[1].x = ( base[0].x + b ) / 2;
809 base[2].x = ( a + b ) / 2;
811 base[4].y = base[2].y;
813 a = base[3].y = ( base[2].y + b ) / 2;
814 b = base[1].y = ( base[0].y + b ) / 2;
815 base[2].y = ( a + b ) / 2;
817 /* hand optimized. gcc doesn't seem to be too good at common */
818 /* expression substitution and instruction scheduling ;-) */
822 /*************************************************************************/
828 /* Subdivides a third-order Bezier arc into two joint sub-arcs in the */
832 /* This routine is the `beef' of the component. It is one of _the_ */
833 /* inner loops that should be optimized like hell to get the best */
837 Split_Cubic( TPoint* base )
842 base[6].x = base[3].x;
845 base[1].x = a = ( base[0].x + c + 1 ) >> 1;
846 base[5].x = b = ( base[3].x + d + 1 ) >> 1;
847 c = ( c + d + 1 ) >> 1;
848 base[2].x = a = ( a + c + 1 ) >> 1;
849 base[4].x = b = ( b + c + 1 ) >> 1;
850 base[3].x = ( a + b + 1 ) >> 1;
852 base[6].y = base[3].y;
855 base[1].y = a = ( base[0].y + c + 1 ) >> 1;
856 base[5].y = b = ( base[3].y + d + 1 ) >> 1;
857 c = ( c + d + 1 ) >> 1;
858 base[2].y = a = ( a + c + 1 ) >> 1;
859 base[4].y = b = ( b + c + 1 ) >> 1;
860 base[3].y = ( a + b + 1 ) >> 1;
864 /*************************************************************************/
870 /* Computes the x-coordinates of an ascending line segment and stores */
871 /* them in the render pool. */
874 /* x1 :: The x-coordinate of the segment's start point. */
876 /* y1 :: The y-coordinate of the segment's start point. */
878 /* x2 :: The x-coordinate of the segment's end point. */
880 /* y2 :: The y-coordinate of the segment's end point. */
882 /* miny :: A lower vertical clipping bound value. */
884 /* maxy :: An upper vertical clipping bound value. */
887 /* SUCCESS on success, FAILURE on render pool overflow. */
890 Line_Up( RAS_ARGS Long x1,
898 Int e1, e2, f1, f2, size; /* XXX: is `Short' sufficient? */
907 if ( Dy <= 0 || y2 < miny || y1 > maxy )
912 /* Take care: miny-y1 can be a very large value; we use */
913 /* a slow MulDiv function to avoid clipping bugs */
914 x1 += SMulDiv( Dx, miny - y1, Dy );
926 /* x2 += FMulDiv( Dx, maxy - y2, Dy ); UNNECESSARY */
942 x1 += FMulDiv( Dx, ras.precision - f1, Dy );
953 ras.joint = (char)( f2 == 0 );
957 ras.cProfile->start = e1;
962 if ( ras.top + size >= ras.maxBuff )
964 ras.error = Raster_Err_Overflow;
970 Ix = ( ras.precision * Dx ) / Dy;
971 Rx = ( ras.precision * Dx ) % Dy;
976 Ix = -( ( ras.precision * -Dx ) / Dy );
977 Rx = ( ras.precision * -Dx ) % Dy;
1003 /*************************************************************************/
1009 /* Computes the x-coordinates of an descending line segment and */
1010 /* stores them in the render pool. */
1013 /* x1 :: The x-coordinate of the segment's start point. */
1015 /* y1 :: The y-coordinate of the segment's start point. */
1017 /* x2 :: The x-coordinate of the segment's end point. */
1019 /* y2 :: The y-coordinate of the segment's end point. */
1021 /* miny :: A lower vertical clipping bound value. */
1023 /* maxy :: An upper vertical clipping bound value. */
1026 /* SUCCESS on success, FAILURE on render pool overflow. */
1029 Line_Down( RAS_ARGS Long x1,
1041 result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny );
1043 if ( fresh && !ras.fresh )
1044 ras.cProfile->start = -ras.cProfile->start;
1050 /* A function type describing the functions used to split Bezier arcs */
1051 typedef void (*TSplitter)( TPoint* base );
1054 /*************************************************************************/
1060 /* Computes the x-coordinates of an ascending Bezier arc and stores */
1061 /* them in the render pool. */
1064 /* degree :: The degree of the Bezier arc (either 2 or 3). */
1066 /* splitter :: The function to split Bezier arcs. */
1068 /* miny :: A lower vertical clipping bound value. */
1070 /* maxy :: An upper vertical clipping bound value. */
1073 /* SUCCESS on success, FAILURE on render pool overflow. */
1076 Bezier_Up( RAS_ARGS Int degree,
1081 Long y1, y2, e, e2, e0;
1095 if ( y2 < miny || y1 > maxy )
1110 f1 = (Short)( FRAC( y1 ) );
1121 *top++ = arc[degree].x;
1129 ras.cProfile->start = TRUNC( e0 );
1136 if ( ( top + TRUNC( e2 - e ) + 1 ) >= ras.maxBuff )
1139 ras.error = Raster_Err_Overflow;
1145 while ( arc >= start_arc && e <= e2 )
1154 if ( y2 - y1 >= ras.precision_step )
1161 *top++ = arc[degree].x + FMulDiv( arc[0].x-arc[degree].x,
1187 /*************************************************************************/
1193 /* Computes the x-coordinates of an descending Bezier arc and stores */
1194 /* them in the render pool. */
1197 /* degree :: The degree of the Bezier arc (either 2 or 3). */
1199 /* splitter :: The function to split Bezier arcs. */
1201 /* miny :: A lower vertical clipping bound value. */
1203 /* maxy :: An upper vertical clipping bound value. */
1206 /* SUCCESS on success, FAILURE on render pool overflow. */
1209 Bezier_Down( RAS_ARGS Int degree,
1214 TPoint* arc = ras.arc;
1218 arc[0].y = -arc[0].y;
1219 arc[1].y = -arc[1].y;
1220 arc[2].y = -arc[2].y;
1222 arc[3].y = -arc[3].y;
1226 result = Bezier_Up( RAS_VARS degree, splitter, -maxy, -miny );
1228 if ( fresh && !ras.fresh )
1229 ras.cProfile->start = -ras.cProfile->start;
1231 arc[0].y = -arc[0].y;
1236 /*************************************************************************/
1242 /* Injects a new line segment and adjusts Profiles list. */
1245 /* x :: The x-coordinate of the segment's end point (its start point */
1246 /* is stored in `LastX'). */
1248 /* y :: The y-coordinate of the segment's end point (its start point */
1249 /* is stored in `LastY'). */
1252 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1256 Line_To( RAS_ARGS Long x,
1259 /* First, detect a change of direction */
1261 switch ( ras.state )
1264 if ( y > ras.lastY )
1266 if ( New_Profile( RAS_VARS Ascending ) )
1271 if ( y < ras.lastY )
1272 if ( New_Profile( RAS_VARS Descending ) )
1278 if ( y < ras.lastY )
1280 if ( End_Profile( RAS_VAR ) ||
1281 New_Profile( RAS_VARS Descending ) )
1287 if ( y > ras.lastY )
1289 if ( End_Profile( RAS_VAR ) ||
1290 New_Profile( RAS_VARS Ascending ) )
1299 /* Then compute the lines */
1301 switch ( ras.state )
1304 if ( Line_Up( RAS_VARS ras.lastX, ras.lastY,
1305 x, y, ras.minY, ras.maxY ) )
1310 if ( Line_Down( RAS_VARS ras.lastX, ras.lastY,
1311 x, y, ras.minY, ras.maxY ) )
1326 /*************************************************************************/
1332 /* Injects a new conic arc and adjusts the profile list. */
1335 /* cx :: The x-coordinate of the arc's new control point. */
1337 /* cy :: The y-coordinate of the arc's new control point. */
1339 /* x :: The x-coordinate of the arc's end point (its start point is */
1340 /* stored in `LastX'). */
1342 /* y :: The y-coordinate of the arc's end point (its start point is */
1343 /* stored in `LastY'). */
1346 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1350 Conic_To( RAS_ARGS Long cx,
1355 Long y1, y2, y3, x3, ymin, ymax;
1360 ras.arc[2].x = ras.lastX;
1361 ras.arc[2].y = ras.lastY;
1362 ras.arc[1].x = cx; ras.arc[1].y = cy;
1363 ras.arc[0].x = x; ras.arc[0].y = y;
1372 /* first, categorize the Bezier arc */
1385 if ( y2 < ymin || y2 > ymax )
1387 /* this arc has no given direction, split it! */
1388 Split_Conic( ras.arc );
1391 else if ( y1 == y3 )
1393 /* this arc is flat, ignore it and pop it from the Bezier stack */
1398 /* the arc is y-monotonous, either ascending or descending */
1399 /* detect a change of direction */
1400 state_bez = y1 < y3 ? Ascending : Descending;
1401 if ( ras.state != state_bez )
1403 /* finalize current profile if any */
1404 if ( ras.state != Unknown &&
1405 End_Profile( RAS_VAR ) )
1408 /* create a new profile */
1409 if ( New_Profile( RAS_VARS state_bez ) )
1413 /* now call the appropriate routine */
1414 if ( state_bez == Ascending )
1416 if ( Bezier_Up( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1420 if ( Bezier_Down( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1424 } while ( ras.arc >= ras.arcs );
1436 /*************************************************************************/
1442 /* Injects a new cubic arc and adjusts the profile list. */
1445 /* cx1 :: The x-coordinate of the arc's first new control point. */
1447 /* cy1 :: The y-coordinate of the arc's first new control point. */
1449 /* cx2 :: The x-coordinate of the arc's second new control point. */
1451 /* cy2 :: The y-coordinate of the arc's second new control point. */
1453 /* x :: The x-coordinate of the arc's end point (its start point is */
1454 /* stored in `LastX'). */
1456 /* y :: The y-coordinate of the arc's end point (its start point is */
1457 /* stored in `LastY'). */
1460 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1464 Cubic_To( RAS_ARGS Long cx1,
1471 Long y1, y2, y3, y4, x4, ymin1, ymax1, ymin2, ymax2;
1476 ras.arc[3].x = ras.lastX;
1477 ras.arc[3].y = ras.lastY;
1478 ras.arc[2].x = cx1; ras.arc[2].y = cy1;
1479 ras.arc[1].x = cx2; ras.arc[1].y = cy2;
1480 ras.arc[0].x = x; ras.arc[0].y = y;
1490 /* first, categorize the Bezier arc */
1514 if ( ymin2 < ymin1 || ymax2 > ymax1 )
1516 /* this arc has no given direction, split it! */
1517 Split_Cubic( ras.arc );
1520 else if ( y1 == y4 )
1522 /* this arc is flat, ignore it and pop it from the Bezier stack */
1527 state_bez = ( y1 <= y4 ) ? Ascending : Descending;
1529 /* detect a change of direction */
1530 if ( ras.state != state_bez )
1532 if ( ras.state != Unknown &&
1533 End_Profile( RAS_VAR ) )
1536 if ( New_Profile( RAS_VARS state_bez ) )
1540 /* compute intersections */
1541 if ( state_bez == Ascending )
1543 if ( Bezier_Up( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1547 if ( Bezier_Down( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1551 } while ( ras.arc >= ras.arcs );
1564 #define SWAP_( x, y ) do \
1574 /*************************************************************************/
1577 /* Decompose_Curve */
1580 /* Scans the outline arays in order to emit individual segments and */
1581 /* Beziers by calling Line_To() and Bezier_To(). It handles all */
1582 /* weird cases, like when the first point is off the curve, or when */
1583 /* there are simply no `on' points in the contour! */
1586 /* first :: The index of the first point in the contour. */
1588 /* last :: The index of the last point in the contour. */
1590 /* flipped :: If set, flip the direction of the curve. */
1593 /* SUCCESS on success, FAILURE on error. */
1596 Decompose_Curve( RAS_ARGS UShort first,
1601 FT_Vector v_control;
1609 unsigned tag; /* current point's state */
1612 points = ras.outline.points;
1613 limit = points + last;
1615 v_start.x = SCALED( points[first].x );
1616 v_start.y = SCALED( points[first].y );
1617 v_last.x = SCALED( points[last].x );
1618 v_last.y = SCALED( points[last].y );
1622 SWAP_( v_start.x, v_start.y );
1623 SWAP_( v_last.x, v_last.y );
1626 v_control = v_start;
1628 point = points + first;
1629 tags = ras.outline.tags + first;
1630 tag = FT_CURVE_TAG( tags[0] );
1632 /* A contour cannot start with a cubic control point! */
1633 if ( tag == FT_Curve_Tag_Cubic )
1634 goto Invalid_Outline;
1636 /* check first point to determine origin */
1637 if ( tag == FT_Curve_Tag_Conic )
1639 /* first point is conic control. Yes, this happens. */
1640 if ( FT_CURVE_TAG( ras.outline.tags[last] ) == FT_Curve_Tag_On )
1642 /* start at last point if it is on the curve */
1648 /* if both first and last points are conic, */
1649 /* start at their middle and record its position */
1651 v_start.x = ( v_start.x + v_last.x ) / 2;
1652 v_start.y = ( v_start.y + v_last.y ) / 2;
1660 ras.lastX = v_start.x;
1661 ras.lastY = v_start.y;
1663 while ( point < limit )
1668 tag = FT_CURVE_TAG( tags[0] );
1672 case FT_Curve_Tag_On: /* emit a single line_to */
1677 x = SCALED( point->x );
1678 y = SCALED( point->y );
1682 if ( Line_To( RAS_VARS x, y ) )
1687 case FT_Curve_Tag_Conic: /* consume conic arcs */
1688 v_control.x = SCALED( point[0].x );
1689 v_control.y = SCALED( point[0].y );
1692 SWAP_( v_control.x, v_control.y );
1695 if ( point < limit )
1703 tag = FT_CURVE_TAG( tags[0] );
1705 x = SCALED( point[0].x );
1706 y = SCALED( point[0].y );
1711 if ( tag == FT_Curve_Tag_On )
1713 if ( Conic_To( RAS_VARS v_control.x, v_control.y, x, y ) )
1718 if ( tag != FT_Curve_Tag_Conic )
1719 goto Invalid_Outline;
1721 v_middle.x = ( v_control.x + x ) / 2;
1722 v_middle.y = ( v_control.y + y ) / 2;
1724 if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1725 v_middle.x, v_middle.y ) )
1734 if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1735 v_start.x, v_start.y ) )
1740 default: /* FT_Curve_Tag_Cubic */
1742 Long x1, y1, x2, y2, x3, y3;
1745 if ( point + 1 > limit ||
1746 FT_CURVE_TAG( tags[1] ) != FT_Curve_Tag_Cubic )
1747 goto Invalid_Outline;
1752 x1 = SCALED( point[-2].x );
1753 y1 = SCALED( point[-2].y );
1754 x2 = SCALED( point[-1].x );
1755 y2 = SCALED( point[-1].y );
1756 x3 = SCALED( point[ 0].x );
1757 y3 = SCALED( point[ 0].y );
1766 if ( point <= limit )
1768 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, x3, y3 ) )
1773 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, v_start.x, v_start.y ) )
1780 /* close the contour with a line segment */
1781 if ( Line_To( RAS_VARS v_start.x, v_start.y ) )
1788 ras.error = Raster_Err_Invalid;
1795 /*************************************************************************/
1801 /* Converts a glyph into a series of segments and arcs and makes a */
1802 /* profiles list with them. */
1805 /* flipped :: If set, flip the direction of curve. */
1808 /* SUCCESS on success, FAILURE if any error was encountered during */
1812 Convert_Glyph( RAS_ARGS int flipped )
1817 PProfile lastProfile;
1820 ras.fProfile = NULL;
1824 ras.maxBuff = ras.sizeBuff - AlignProfileSize;
1828 ras.cProfile = (PProfile)ras.top;
1829 ras.cProfile->offset = ras.top;
1834 for ( i = 0; i < ras.outline.n_contours; i++ )
1836 ras.state = Unknown;
1837 ras.gProfile = NULL;
1839 if ( Decompose_Curve( RAS_VARS (unsigned short)start,
1840 ras.outline.contours[i],
1844 start = ras.outline.contours[i] + 1;
1846 /* We must now see whether the extreme arcs join or not */
1847 if ( FRAC( ras.lastY ) == 0 &&
1848 ras.lastY >= ras.minY &&
1849 ras.lastY <= ras.maxY )
1850 if ( ras.gProfile && ras.gProfile->flow == ras.cProfile->flow )
1852 /* Note that ras.gProfile can be nil if the contour was too small */
1855 lastProfile = ras.cProfile;
1856 if ( End_Profile( RAS_VAR ) )
1859 /* close the `next profile in contour' linked list */
1861 lastProfile->next = ras.gProfile;
1864 if ( Finalize_Profile_Table( RAS_VAR ) )
1867 return (Bool)( ras.top < ras.maxBuff ? SUCCESS : FAILURE );
1871 /*************************************************************************/
1872 /*************************************************************************/
1874 /** SCAN-LINE SWEEPS AND DRAWING **/
1876 /*************************************************************************/
1877 /*************************************************************************/
1880 /*************************************************************************/
1884 /* Initializes an empty linked list. */
1887 Init_Linked( TProfileList* l )
1893 /*************************************************************************/
1897 /* Inserts a new profile in a linked list. */
1900 InsNew( PProfileList list,
1903 PProfile *old, current;
1913 if ( x < current->X )
1915 old = ¤t->link;
1919 profile->link = current;
1924 /*************************************************************************/
1928 /* Removes an old profile from a linked list. */
1931 DelOld( PProfileList list,
1934 PProfile *old, current;
1942 if ( current == profile )
1944 *old = current->link;
1948 old = ¤t->link;
1952 /* we should never get there, unless the profile was not part of */
1957 /*************************************************************************/
1961 /* Sorts a trace list. In 95%, the list is already sorted. We need */
1962 /* an algorithm which is fast in this case. Bubble sort is enough */
1966 Sort( PProfileList list )
1968 PProfile *old, current, next;
1971 /* First, set the new X coordinate of each profile */
1975 current->X = *current->offset;
1976 current->offset += current->flow;
1978 current = current->link;
1981 /* Then sort them */
1988 next = current->link;
1992 if ( current->X <= next->X )
1994 old = ¤t->link;
2003 current->link = next->link;
2004 next->link = current;
2010 next = current->link;
2015 /*************************************************************************/
2017 /* Vertical Sweep Procedure Set */
2019 /* These four routines are used during the vertical black/white sweep */
2020 /* phase by the generic Draw_Sweep() function. */
2022 /*************************************************************************/
2025 Vertical_Sweep_Init( RAS_ARGS Short* min,
2028 Long pitch = ras.target.pitch;
2033 ras.traceIncr = (Short)-pitch;
2034 ras.traceOfs = -*min * pitch;
2036 ras.traceOfs += ( ras.target.rows - 1 ) * pitch;
2044 Vertical_Sweep_Span( RAS_ARGS Short y,
2060 /* Drop-out control */
2062 e1 = TRUNC( CEILING( x1 ) );
2064 if ( x2 - x1 - ras.precision <= ras.precision_jitter )
2067 e2 = TRUNC( FLOOR( x2 ) );
2069 if ( e2 >= 0 && e1 < ras.bWidth )
2073 if ( e2 >= ras.bWidth )
2074 e2 = ras.bWidth - 1;
2076 c1 = (Short)( e1 >> 3 );
2077 c2 = (Short)( e2 >> 3 );
2079 f1 = (Byte) ( 0xFF >> ( e1 & 7 ) );
2080 f2 = (Byte) ~( 0x7F >> ( e2 & 7 ) );
2082 if ( ras.gray_min_x > c1 ) ras.gray_min_x = (short)c1;
2083 if ( ras.gray_max_x < c2 ) ras.gray_max_x = (short)c2;
2085 target = ras.bTarget + ras.traceOfs + c1;
2092 /* memset() is slower than the following code on many platforms. */
2093 /* This is due to the fact that, in the vast majority of cases, */
2094 /* the span length in bytes is relatively small. */
2104 *target |= ( f1 & f2 );
2110 Vertical_Sweep_Drop( RAS_ARGS Short y,
2120 /* Drop-out control */
2127 if ( e1 == e2 + ras.precision )
2129 switch ( ras.dropOutControl )
2136 e1 = CEILING( (x1 + x2 + 1) / 2 );
2141 /* Drop-out Control Rule #4 */
2143 /* The spec is not very clear regarding rule #4. It */
2144 /* presents a method that is way too costly to implement */
2145 /* while the general idea seems to get rid of `stubs'. */
2147 /* Here, we only get rid of stubs recognized if: */
2151 /* - P_Left and P_Right are in the same contour */
2152 /* - P_Right is the successor of P_Left in that contour */
2153 /* - y is the top of P_Left and P_Right */
2157 /* - P_Left and P_Right are in the same contour */
2158 /* - P_Left is the successor of P_Right in that contour */
2159 /* - y is the bottom of P_Left */
2162 /* FIXXXME: uncommenting this line solves the disappearing */
2163 /* bit problem in the `7' of verdana 10pts, but */
2164 /* makes a new one in the `C' of arial 14pts */
2167 if ( x2 - x1 < ras.precision_half )
2170 /* upper stub test */
2171 if ( left->next == right && left->height <= 0 )
2174 /* lower stub test */
2175 if ( right->next == left && left->start == y )
2179 /* check that the rightmost pixel isn't set */
2183 c1 = (Short)( e1 >> 3 );
2184 f1 = (Short)( e1 & 7 );
2186 if ( e1 >= 0 && e1 < ras.bWidth &&
2187 ras.bTarget[ras.traceOfs + c1] & ( 0x80 >> f1 ) )
2190 if ( ras.dropOutControl == 2 )
2193 e1 = CEILING( ( x1 + x2 + 1 ) / 2 );
2198 return; /* unsupported mode */
2207 if ( e1 >= 0 && e1 < ras.bWidth )
2209 c1 = (Short)( e1 >> 3 );
2210 f1 = (Short)( e1 & 7 );
2212 if ( ras.gray_min_x > c1 ) ras.gray_min_x = c1;
2213 if ( ras.gray_max_x < c1 ) ras.gray_max_x = c1;
2215 ras.bTarget[ras.traceOfs + c1] |= (char)( 0x80 >> f1 );
2221 Vertical_Sweep_Step( RAS_ARG )
2223 ras.traceOfs += ras.traceIncr;
2227 /***********************************************************************/
2229 /* Horizontal Sweep Procedure Set */
2231 /* These four routines are used during the horizontal black/white */
2232 /* sweep phase by the generic Draw_Sweep() function. */
2234 /***********************************************************************/
2237 Horizontal_Sweep_Init( RAS_ARGS Short* min,
2240 /* nothing, really */
2241 FT_UNUSED( raster );
2248 Horizontal_Sweep_Span( RAS_ARGS Short y,
2262 if ( x2 - x1 < ras.precision )
2269 bits = ras.bTarget + ( y >> 3 );
2270 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2274 if ( e1 >= 0 && e1 < ras.target.rows )
2279 p = bits - e1*ras.target.pitch;
2280 if ( ras.target.pitch > 0 )
2281 p += ( ras.target.rows - 1 ) * ras.target.pitch;
2291 Horizontal_Sweep_Drop( RAS_ARGS Short y,
2302 /* During the horizontal sweep, we only take care of drop-outs */
2309 if ( e1 == e2 + ras.precision )
2311 switch ( ras.dropOutControl )
2318 e1 = CEILING( ( x1 + x2 + 1 ) / 2 );
2324 /* Drop-out Control Rule #4 */
2326 /* The spec is not very clear regarding rule #4. It */
2327 /* presents a method that is way too costly to implement */
2328 /* while the general idea seems to get rid of `stubs'. */
2331 /* rightmost stub test */
2332 if ( left->next == right && left->height <= 0 )
2335 /* leftmost stub test */
2336 if ( right->next == left && left->start == y )
2339 /* check that the rightmost pixel isn't set */
2343 bits = ras.bTarget + ( y >> 3 );
2344 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2346 bits -= e1 * ras.target.pitch;
2347 if ( ras.target.pitch > 0 )
2348 bits += ( ras.target.rows - 1 ) * ras.target.pitch;
2351 e1 < ras.target.rows &&
2355 if ( ras.dropOutControl == 2 )
2358 e1 = CEILING( ( x1 + x2 + 1 ) / 2 );
2363 return; /* unsupported mode */
2370 bits = ras.bTarget + ( y >> 3 );
2371 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2375 if ( e1 >= 0 && e1 < ras.target.rows )
2377 bits -= e1 * ras.target.pitch;
2378 if ( ras.target.pitch > 0 )
2379 bits += ( ras.target.rows - 1 ) * ras.target.pitch;
2387 Horizontal_Sweep_Step( RAS_ARG )
2389 /* Nothing, really */
2390 FT_UNUSED( raster );
2394 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
2397 /*************************************************************************/
2399 /* Vertical Gray Sweep Procedure Set */
2401 /* These two routines are used during the vertical gray-levels sweep */
2402 /* phase by the generic Draw_Sweep() function. */
2406 /* - The target pixmap's width *must* be a multiple of 4. */
2408 /* - You have to use the function Vertical_Sweep_Span() for the gray */
2411 /*************************************************************************/
2414 Vertical_Gray_Sweep_Init( RAS_ARGS Short* min,
2417 Long pitch, byte_len;
2421 *max = ( *max + 3 ) & -2;
2424 pitch = ras.target.pitch;
2426 ras.traceIncr = (Short)byte_len;
2427 ras.traceG = ( *min / 2 ) * byte_len;
2431 ras.traceG += ( ras.target.rows - 1 ) * pitch;
2432 byte_len = -byte_len;
2435 ras.gray_min_x = (Short)byte_len;
2436 ras.gray_max_x = -(Short)byte_len;
2441 Vertical_Gray_Sweep_Step( RAS_ARG )
2444 PByte pix, bit, bit2;
2445 Int* count = ras.count_table;
2449 ras.traceOfs += ras.gray_width;
2451 if ( ras.traceOfs > ras.gray_width )
2453 pix = ras.gTarget + ras.traceG + ras.gray_min_x * 4;
2456 if ( ras.gray_max_x >= 0 )
2458 Long last_pixel = ras.target.width - 1;
2459 Int last_cell = last_pixel >> 2;
2460 Int last_bit = last_pixel & 3;
2464 if ( ras.gray_max_x >= last_cell && last_bit != 3 )
2466 ras.gray_max_x = last_cell - 1;
2470 if ( ras.gray_min_x < 0 )
2473 bit = ras.bTarget + ras.gray_min_x;
2474 bit2 = bit + ras.gray_width;
2476 c1 = ras.gray_max_x - ras.gray_min_x;
2480 c2 = count[*bit] + count[*bit2];
2484 pix[0] = grays[(c2 >> 12) & 0x000F];
2485 pix[1] = grays[(c2 >> 8 ) & 0x000F];
2486 pix[2] = grays[(c2 >> 4 ) & 0x000F];
2487 pix[3] = grays[ c2 & 0x000F];
2501 c2 = count[*bit] + count[*bit2];
2507 pix[2] = grays[(c2 >> 4 ) & 0x000F];
2509 pix[1] = grays[(c2 >> 8 ) & 0x000F];
2511 pix[0] = grays[(c2 >> 12) & 0x000F];
2521 ras.traceG += ras.traceIncr;
2523 ras.gray_min_x = 32000;
2524 ras.gray_max_x = -32000;
2530 Horizontal_Gray_Sweep_Span( RAS_ARGS Short y,
2536 /* nothing, really */
2537 FT_UNUSED( raster );
2547 Horizontal_Gray_Sweep_Drop( RAS_ARGS Short y,
2558 /* During the horizontal sweep, we only take care of drop-outs */
2564 if ( e1 == e2 + ras.precision )
2566 switch ( ras.dropOutControl )
2573 e1 = CEILING( ( x1 + x2 + 1 ) / 2 );
2579 /* Drop-out Control Rule #4 */
2581 /* The spec is not very clear regarding rule #4. It */
2582 /* presents a method that is way too costly to implement */
2583 /* while the general idea seems to get rid of `stubs'. */
2586 /* rightmost stub test */
2587 if ( left->next == right && left->height <= 0 )
2590 /* leftmost stub test */
2591 if ( right->next == left && left->start == y )
2594 if ( ras.dropOutControl == 2 )
2597 e1 = CEILING( ( x1 + x2 + 1 ) / 2 );
2602 return; /* unsupported mode */
2611 if ( x2 - x1 >= ras.precision_half )
2612 color = ras.grays[2];
2614 color = ras.grays[1];
2616 e1 = TRUNC( e1 ) / 2;
2617 if ( e1 < ras.target.rows )
2619 pixel = ras.gTarget - e1 * ras.target.pitch + y / 2;
2620 if ( ras.target.pitch > 0 )
2621 pixel += ( ras.target.rows - 1 ) * ras.target.pitch;
2623 if ( pixel[0] == ras.grays[0] )
2630 #endif /* FT_RASTER_OPTION_ANTI_ALIASING */
2633 /*************************************************************************/
2635 /* Generic Sweep Drawing routine */
2637 /*************************************************************************/
2640 Draw_Sweep( RAS_ARG )
2642 Short y, y_change, y_height;
2644 PProfile P, Q, P_Left, P_Right;
2646 Short min_Y, max_Y, top, bottom, dropouts;
2648 Long x1, x2, xs, e1, e2;
2651 TProfileList draw_left, draw_right;
2654 /* Init empty linked lists */
2656 Init_Linked( &wait );
2658 Init_Linked( &draw_left );
2659 Init_Linked( &draw_right );
2661 /* first, compute min and max Y */
2664 max_Y = (Short)TRUNC( ras.minY );
2665 min_Y = (Short)TRUNC( ras.maxY );
2671 bottom = (Short)P->start;
2672 top = (Short)( P->start + P->height - 1 );
2674 if ( min_Y > bottom ) min_Y = bottom;
2675 if ( max_Y < top ) max_Y = top;
2683 /* Check the Y-turns */
2684 if ( ras.numTurns == 0 )
2686 ras.error = Raster_Err_Invalid;
2690 /* Now inits the sweep */
2692 ras.Proc_Sweep_Init( RAS_VARS &min_Y, &max_Y );
2694 /* Then compute the distance of each profile from min_Y */
2700 P->countL = (UShort)( P->start - min_Y );
2709 if ( ras.numTurns > 0 &&
2710 ras.sizeBuff[-ras.numTurns] == min_Y )
2713 while ( ras.numTurns > 0 )
2715 /* look in the wait list for new activations */
2722 P->countL -= y_height;
2723 if ( P->countL == 0 )
2730 InsNew( &draw_left, P );
2734 InsNew( &draw_right, P );
2742 /* Sort the drawing lists */
2745 Sort( &draw_right );
2747 y_change = (Short)ras.sizeBuff[-ras.numTurns--];
2748 y_height = (Short)( y_change - y );
2750 while ( y < y_change )
2757 P_Right = draw_right;
2771 if ( x2 - x1 <= ras.precision )
2776 if ( ras.dropOutControl != 0 &&
2777 ( e1 > e2 || e2 == e1 + ras.precision ) )
2779 /* a drop out was detected */
2784 /* mark profile for drop-out processing */
2792 ras.Proc_Sweep_Span( RAS_VARS y, x1, x2, P_Left, P_Right );
2796 P_Left = P_Left->link;
2797 P_Right = P_Right->link;
2800 /* now perform the dropouts _after_ the span drawing -- */
2801 /* drop-outs processing has been moved out of the loop */
2802 /* for performance tuning */
2808 ras.Proc_Sweep_Step( RAS_VAR );
2815 Sort( &draw_right );
2819 /* Now finalize the profiles that needs it */
2825 if ( P->height == 0 )
2826 DelOld( &draw_left, P );
2834 if ( P->height == 0 )
2835 DelOld( &draw_right, P );
2840 /* for gray-scaling, flushes the bitmap scanline cache */
2841 while ( y <= max_Y )
2843 ras.Proc_Sweep_Step( RAS_VAR );
2852 P_Right = draw_right;
2856 if ( P_Left->countL )
2860 dropouts--; /* -- this is useful when debugging only */
2862 ras.Proc_Sweep_Drop( RAS_VARS y,
2869 P_Left = P_Left->link;
2870 P_Right = P_Right->link;
2877 /*************************************************************************/
2880 /* Render_Single_Pass */
2883 /* Performs one sweep with sub-banding. */
2886 /* flipped :: If set, flip the direction of the outline. */
2889 /* Renderer error code. */
2892 Render_Single_Pass( RAS_ARGS Bool flipped )
2897 while ( ras.band_top >= 0 )
2899 ras.maxY = (Long)ras.band_stack[ras.band_top].y_max * ras.precision;
2900 ras.minY = (Long)ras.band_stack[ras.band_top].y_min * ras.precision;
2904 ras.error = Raster_Err_None;
2906 if ( Convert_Glyph( RAS_VARS flipped ) )
2908 if ( ras.error != Raster_Err_Overflow )
2911 ras.error = Raster_Err_None;
2916 ClearBand( RAS_VARS TRUNC( ras.minY ), TRUNC( ras.maxY ) );
2919 i = ras.band_stack[ras.band_top].y_min;
2920 j = ras.band_stack[ras.band_top].y_max;
2922 k = (Short)( ( i + j ) / 2 );
2924 if ( ras.band_top >= 7 || k < i )
2927 ras.error = Raster_Err_Invalid;
2932 ras.band_stack[ras.band_top + 1].y_min = k;
2933 ras.band_stack[ras.band_top + 1].y_max = j;
2935 ras.band_stack[ras.band_top].y_max = (Short)( k - 1 );
2942 if ( Draw_Sweep( RAS_VAR ) )
2952 /*************************************************************************/
2958 /* Renders a glyph in a bitmap. Sub-banding if needed. */
2961 /* FreeType error code. 0 means success. */
2963 FT_LOCAL_DEF FT_Error
2964 Render_Glyph( RAS_ARG )
2969 Set_High_Precision( RAS_VARS ras.outline.flags &
2970 ft_outline_high_precision );
2971 ras.scale_shift = ras.precision_shift;
2972 ras.dropOutControl = 2;
2973 ras.second_pass = (FT_Byte)( !( ras.outline.flags &
2974 ft_outline_single_pass ) );
2976 /* Vertical Sweep */
2977 ras.Proc_Sweep_Init = Vertical_Sweep_Init;
2978 ras.Proc_Sweep_Span = Vertical_Sweep_Span;
2979 ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
2980 ras.Proc_Sweep_Step = Vertical_Sweep_Step;
2983 ras.band_stack[0].y_min = 0;
2984 ras.band_stack[0].y_max = (short)( ras.target.rows - 1 );
2986 ras.bWidth = (unsigned short)ras.target.width;
2987 ras.bTarget = (Byte*)ras.target.buffer;
2989 if ( ( error = Render_Single_Pass( RAS_VARS 0 ) ) != 0 )
2992 /* Horizontal Sweep */
2993 if ( ras.second_pass && ras.dropOutControl != 0 )
2995 ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
2996 ras.Proc_Sweep_Span = Horizontal_Sweep_Span;
2997 ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop;
2998 ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3001 ras.band_stack[0].y_min = 0;
3002 ras.band_stack[0].y_max = (short)( ras.target.width - 1 );
3004 if ( ( error = Render_Single_Pass( RAS_VARS 1 ) ) != 0 )
3008 return Raster_Err_Ok;
3012 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3015 /*************************************************************************/
3018 /* Render_Gray_Glyph */
3021 /* Renders a glyph with grayscaling. Sub-banding if needed. */
3024 /* FreeType error code. 0 means success. */
3026 FT_LOCAL_DEF FT_Error
3027 Render_Gray_Glyph( RAS_ARG )
3033 Set_High_Precision( RAS_VARS ras.outline.flags &
3034 ft_outline_high_precision );
3035 ras.scale_shift = ras.precision_shift + 1;
3036 ras.dropOutControl = 2;
3037 ras.second_pass = !( ras.outline.flags & ft_outline_single_pass );
3039 /* Vertical Sweep */
3042 ras.band_stack[0].y_min = 0;
3043 ras.band_stack[0].y_max = 2 * ras.target.rows - 1;
3045 ras.bWidth = ras.gray_width;
3046 pixel_width = 2 * ( ( ras.target.width + 3 ) >> 2 );
3048 if ( ras.bWidth > pixel_width )
3049 ras.bWidth = pixel_width;
3051 ras.bWidth = ras.bWidth * 8;
3052 ras.bTarget = (Byte*)ras.gray_lines;
3053 ras.gTarget = (Byte*)ras.target.buffer;
3055 ras.Proc_Sweep_Init = Vertical_Gray_Sweep_Init;
3056 ras.Proc_Sweep_Span = Vertical_Sweep_Span;
3057 ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
3058 ras.Proc_Sweep_Step = Vertical_Gray_Sweep_Step;
3060 error = Render_Single_Pass( RAS_VARS 0 );
3064 /* Horizontal Sweep */
3065 if ( ras.second_pass && ras.dropOutControl != 0 )
3067 ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
3068 ras.Proc_Sweep_Span = Horizontal_Gray_Sweep_Span;
3069 ras.Proc_Sweep_Drop = Horizontal_Gray_Sweep_Drop;
3070 ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3073 ras.band_stack[0].y_min = 0;
3074 ras.band_stack[0].y_max = ras.target.width * 2 - 1;
3076 error = Render_Single_Pass( RAS_VARS 1 );
3081 return Raster_Err_Ok;
3084 #else /* FT_RASTER_OPTION_ANTI_ALIASING */
3087 FT_Error Render_Gray_Glyph( RAS_ARG )
3091 return Raster_Err_Cannot_Render_Glyph;
3094 #endif /* FT_RASTER_OPTION_ANTI_ALIASING */
3098 ft_black_init( TRaster_Instance* raster )
3104 /* setup count table */
3105 for ( n = 0; n < 256; n++ )
3107 c = ( n & 0x55 ) + ( ( n & 0xAA ) >> 1 );
3109 c = ( ( c << 6 ) & 0x3000 ) |
3110 ( ( c << 4 ) & 0x0300 ) |
3111 ( ( c << 2 ) & 0x0030 ) |
3114 raster->count_table[n] = c;
3117 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3119 /* set default 5-levels gray palette */
3120 for ( n = 0; n < 5; n++ )
3121 raster->grays[n] = n * 255 / 4;
3123 raster->gray_width = RASTER_GRAY_LINES / 2;
3129 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
3130 /**** a static object. *****/
3137 ft_black_new( void* memory,
3138 FT_Raster *araster )
3140 static FT_RasterRec_ the_raster;
3143 *araster = &the_raster;
3144 memset( &the_raster, sizeof ( the_raster ), 0 );
3145 ft_black_init( &the_raster );
3152 ft_black_done( FT_Raster raster )
3159 #else /* _STANDALONE_ */
3163 ft_black_new( FT_Memory memory,
3164 TRaster_Instance** araster )
3167 TRaster_Instance* raster;
3171 if ( !ALLOC( raster, sizeof ( *raster ) ) )
3173 raster->memory = memory;
3174 ft_black_init( raster );
3184 ft_black_done( TRaster_Instance* raster )
3186 FT_Memory memory = (FT_Memory)raster->memory;
3191 #endif /* _STANDALONE_ */
3195 ft_black_reset( TRaster_Instance* raster,
3196 const char* pool_base,
3199 if ( raster && pool_base && pool_size >= 4096 )
3202 raster->buff = (PLong)pool_base;
3203 raster->sizeBuff = raster->buff + pool_size / sizeof ( Long );
3209 ft_black_set_mode( TRaster_Instance* raster,
3211 const char* palette )
3213 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3215 if ( mode == FT_MAKE_TAG( 'p', 'a', 'l', '5' ) )
3217 /* set 5-levels gray palette */
3218 raster->grays[0] = palette[0];
3219 raster->grays[1] = palette[1];
3220 raster->grays[2] = palette[2];
3221 raster->grays[3] = palette[3];
3222 raster->grays[4] = palette[4];
3227 FT_UNUSED( raster );
3229 FT_UNUSED( palette );
3236 ft_black_render( TRaster_Instance* raster,
3237 FT_Raster_Params* params )
3239 FT_Outline* outline = (FT_Outline*)params->source;
3240 FT_Bitmap* target_map = params->target;
3243 if ( !raster || !raster->buff || !raster->sizeBuff )
3244 return Raster_Err_Not_Ini;
3246 /* return immediately if the outline is empty */
3247 if ( outline->n_points == 0 || outline->n_contours <= 0 )
3248 return Raster_Err_None;
3250 if ( !outline || !outline->contours || !outline->points )
3251 return Raster_Err_Invalid;
3253 if ( outline->n_points != outline->contours[outline->n_contours - 1] + 1 )
3254 return Raster_Err_Invalid;
3256 /* this version of the raster does not support direct rendering, sorry */
3257 if ( params->flags & ft_raster_flag_direct )
3258 return Raster_Err_Unsupported;
3260 if ( !target_map || !target_map->buffer )
3261 return Raster_Err_Invalid;
3263 ras.outline = *outline;
3264 ras.target = *target_map;
3266 return ( ( params->flags & ft_raster_flag_aa )
3267 ? Render_Gray_Glyph( raster )
3268 : Render_Glyph( raster ) );
3272 const FT_Raster_Funcs ft_standard_raster =
3274 ft_glyph_format_outline,
3275 (FT_Raster_New_Func) ft_black_new,
3276 (FT_Raster_Reset_Func) ft_black_reset,
3277 (FT_Raster_Set_Mode_Func)ft_black_set_mode,
3278 (FT_Raster_Render_Func) ft_black_render,
3279 (FT_Raster_Done_Func) ft_black_done