1 /***************************************************************************/
5 /* The FreeType glyph rasterizer (body). */
7 /* Copyright 1996-2001, 2002, 2003, 2005, 2007 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 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 `ftimage.h' and `ftmisc.h' into the $(incdir) */
23 /* directory. Typically, you should do something like */
25 /* - copy `src/raster/ftraster.c' (this file) to your current directory */
27 /* - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h' */
28 /* to your current directory */
30 /* - compile `ftraster' with the _STANDALONE_ macro defined, as in */
32 /* cc -c -D_STANDALONE_ ftraster.c */
34 /* The renderer can be initialized with a call to */
35 /* `ft_standard_raster.raster_new'; a bitmap can be generated */
36 /* with a call to `ft_standard_raster.raster_render'. */
38 /* See the comments and documentation in the file `ftimage.h' for more */
39 /* details on how the raster works. */
41 /*************************************************************************/
44 /*************************************************************************/
46 /* This is a rewrite of the FreeType 1.x scan-line converter */
48 /*************************************************************************/
55 #else /* !_STANDALONE_ */
59 #include FT_INTERNAL_CALC_H /* for FT_MulDiv only */
61 #endif /* !_STANDALONE_ */
64 /*************************************************************************/
66 /* A simple technical note on how the raster works */
67 /* ----------------------------------------------- */
69 /* Converting an outline into a bitmap is achieved in several steps: */
71 /* 1 - Decomposing the outline into successive `profiles'. Each */
72 /* profile is simply an array of scanline intersections on a given */
73 /* dimension. A profile's main attributes are */
75 /* o its scanline position boundaries, i.e. `Ymin' and `Ymax'. */
77 /* o an array of intersection coordinates for each scanline */
78 /* between `Ymin' and `Ymax'. */
80 /* o a direction, indicating whether it was built going `up' or */
81 /* `down', as this is very important for filling rules. */
83 /* 2 - Sweeping the target map's scanlines in order to compute segment */
84 /* `spans' which are then filled. Additionally, this pass */
85 /* performs drop-out control. */
87 /* The outline data is parsed during step 1 only. The profiles are */
88 /* built from the bottom of the render pool, used as a stack. The */
89 /* following graphics shows the profile list under construction: */
91 /* ____________________________________________________________ _ _ */
93 /* | profile | coordinates for | profile | coordinates for |--> */
94 /* | 1 | profile 1 | 2 | profile 2 |--> */
95 /* |_________|___________________|_________|_________________|__ _ _ */
99 /* start of render pool top */
101 /* The top of the profile stack is kept in the `top' variable. */
103 /* As you can see, a profile record is pushed on top of the render */
104 /* pool, which is then followed by its coordinates/intersections. If */
105 /* a change of direction is detected in the outline, a new profile is */
106 /* generated until the end of the outline. */
108 /* Note that when all profiles have been generated, the function */
109 /* Finalize_Profile_Table() is used to record, for each profile, its */
110 /* bottom-most scanline as well as the scanline above its upmost */
111 /* boundary. These positions are called `y-turns' because they (sort */
112 /* of) correspond to local extrema. They are stored in a sorted list */
113 /* built from the top of the render pool as a downwards stack: */
115 /* _ _ _______________________________________ */
117 /* <--| sorted list of | */
118 /* <--| extrema scanlines | */
119 /* _ _ __________________|____________________| */
123 /* maxBuff sizeBuff = end of pool */
125 /* This list is later used during the sweep phase in order to */
126 /* optimize performance (see technical note on the sweep below). */
128 /* Of course, the raster detects whether the two stacks collide and */
129 /* handles the situation properly. */
131 /*************************************************************************/
134 /*************************************************************************/
135 /*************************************************************************/
137 /** CONFIGURATION MACROS **/
139 /*************************************************************************/
140 /*************************************************************************/
142 /* define DEBUG_RASTER if you want to compile a debugging version */
143 #define xxxDEBUG_RASTER
145 /* undefine FT_RASTER_OPTION_ANTI_ALIASING if you do not want to support */
146 /* 5-levels anti-aliasing */
147 #ifdef FT_CONFIG_OPTION_5_GRAY_LEVELS
148 #define FT_RASTER_OPTION_ANTI_ALIASING
151 /* The size of the two-lines intermediate bitmap used */
152 /* for anti-aliasing, in bytes. */
153 #define RASTER_GRAY_LINES 2048
156 /*************************************************************************/
157 /*************************************************************************/
159 /** OTHER MACROS (do not change) **/
161 /*************************************************************************/
162 /*************************************************************************/
164 /*************************************************************************/
166 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
167 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
168 /* messages during execution. */
171 #define FT_COMPONENT trace_raster
177 /* This macro is used to indicate that a function parameter is unused. */
178 /* Its purpose is simply to reduce compiler warnings. Note also that */
179 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
180 /* ANSI compilers (e.g. LCC). */
181 #define FT_UNUSED( x ) (x) = (x)
183 /* Disable the tracing mechanism for simplicity -- developers can */
184 /* activate it easily by redefining these two macros. */
186 #define FT_ERROR( x ) do ; while ( 0 ) /* nothing */
190 #define FT_TRACE( x ) do ; while ( 0 ) /* nothing */
191 #define FT_TRACE1( x ) do ; while ( 0 ) /* nothing */
192 #define FT_TRACE6( x ) do ; while ( 0 ) /* nothing */
195 #define Raster_Err_None 0
196 #define Raster_Err_Not_Ini -1
197 #define Raster_Err_Overflow -2
198 #define Raster_Err_Neg_Height -3
199 #define Raster_Err_Invalid -4
200 #define Raster_Err_Unsupported -5
202 #define ft_memset memset
204 #else /* _STANDALONE_ */
207 #include FT_INTERNAL_OBJECTS_H
208 #include FT_INTERNAL_DEBUG_H /* for FT_TRACE() and FT_ERROR() */
210 #include "rasterrs.h"
212 #define Raster_Err_None Raster_Err_Ok
213 #define Raster_Err_Not_Ini Raster_Err_Raster_Uninitialized
214 #define Raster_Err_Overflow Raster_Err_Raster_Overflow
215 #define Raster_Err_Neg_Height Raster_Err_Raster_Negative_Height
216 #define Raster_Err_Invalid Raster_Err_Invalid_Outline
217 #define Raster_Err_Unsupported Raster_Err_Cannot_Render_Glyph
220 #endif /* _STANDALONE_ */
224 #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c )
228 #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count )
231 /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is */
232 /* typically a small value and the result of a*b is known to fit into */
234 #define FMulDiv( a, b, c ) ( (a) * (b) / (c) )
236 /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */
237 /* for clipping computations. It simply uses the FT_MulDiv() function */
238 /* defined in `ftcalc.h'. */
239 #define SMulDiv FT_MulDiv
241 /* The rasterizer is a very general purpose component; please leave */
242 /* the following redefinitions there (you never know your target */
254 #define NULL (void*)0
266 #define MaxBezier 32 /* The maximum number of stacked Bezier curves. */
267 /* Setting this constant to more than 32 is a */
268 /* pure waste of space. */
270 #define Pixel_Bits 6 /* fractional bits of *input* coordinates */
273 /*************************************************************************/
274 /*************************************************************************/
276 /** SIMPLE TYPE DECLARATIONS **/
278 /*************************************************************************/
279 /*************************************************************************/
282 typedef unsigned int UInt
;
284 typedef unsigned short UShort
, *PUShort
;
285 typedef long Long
, *PLong
;
286 typedef unsigned long ULong
;
288 typedef unsigned char Byte
, *PByte
;
292 typedef union Alignment_
298 } Alignment
, *PAlignment
;
301 typedef struct TPoint_
318 /* States of each line, arc, and profile */
319 typedef enum TStates_
329 typedef struct TProfile_ TProfile
;
330 typedef TProfile
* PProfile
;
334 FT_F26Dot6 X
; /* current coordinate during sweep */
335 PProfile link
; /* link to next profile - various purpose */
336 PLong offset
; /* start of profile's data in render pool */
337 int flow
; /* Profile orientation: Asc/Descending */
338 long height
; /* profile's height in scanlines */
339 long start
; /* profile's starting scanline */
341 unsigned countL
; /* number of lines to step before this */
342 /* profile becomes drawable */
344 PProfile next
; /* next profile in same contour, used */
345 /* during drop-out control */
348 typedef PProfile TProfileList
;
349 typedef PProfile
* PProfileList
;
352 /* Simple record used to implement a stack of bands, required */
353 /* by the sub-banding mechanism */
354 typedef struct TBand_
356 Short y_min
; /* band's minimum */
357 Short y_max
; /* band's maximum */
362 #define AlignProfileSize \
363 ( ( sizeof ( TProfile ) + sizeof ( Alignment ) - 1 ) / sizeof ( long ) )
366 #ifdef FT_STATIC_RASTER
369 #define RAS_ARGS /* void */
370 #define RAS_ARG /* void */
372 #define RAS_VARS /* void */
373 #define RAS_VAR /* void */
375 #define FT_UNUSED_RASTER do ; while ( 0 )
378 #else /* FT_STATIC_RASTER */
381 #define RAS_ARGS PWorker worker,
382 #define RAS_ARG PWorker worker
384 #define RAS_VARS worker,
385 #define RAS_VAR worker
387 #define FT_UNUSED_RASTER FT_UNUSED( worker )
390 #endif /* FT_STATIC_RASTER */
393 typedef struct TWorker_ TWorker
, *PWorker
;
396 /* prototypes used for sweep function dispatch */
398 Function_Sweep_Init( RAS_ARGS Short
* min
,
402 Function_Sweep_Span( RAS_ARGS Short y
,
409 Function_Sweep_Step( RAS_ARG
);
412 /* NOTE: These operations are only valid on 2's complement processors */
414 #define FLOOR( x ) ( (x) & -ras.precision )
415 #define CEILING( x ) ( ( (x) + ras.precision - 1 ) & -ras.precision )
416 #define TRUNC( x ) ( (signed long)(x) >> ras.precision_bits )
417 #define FRAC( x ) ( (x) & ( ras.precision - 1 ) )
418 #define SCALED( x ) ( ( (x) << ras.scale_shift ) - ras.precision_half )
420 /* Note that I have moved the location of some fields in the */
421 /* structure to ensure that the most used variables are used */
422 /* at the top. Thus, their offset can be coded with less */
423 /* opcodes, and it results in a smaller executable. */
427 Int precision_bits
; /* precision related variables */
433 Int precision_jitter
;
435 Int scale_shift
; /* == precision_shift for bitmaps */
436 /* == precision_shift+1 for pixmaps */
438 PLong buff
; /* The profiles buffer */
439 PLong sizeBuff
; /* Render pool size */
440 PLong maxBuff
; /* Profiles buffer size */
441 PLong top
; /* Current cursor in buffer */
445 Int numTurns
; /* number of Y-turns in outline */
447 TPoint
* arc
; /* current Bezier arc pointer */
449 UShort bWidth
; /* target bitmap width */
450 PByte bTarget
; /* target bitmap buffer */
451 PByte gTarget
; /* target pixmap buffer */
453 Long lastX
, lastY
, minY
, maxY
;
455 UShort num_Profs
; /* current number of profiles */
457 Bool fresh
; /* signals a fresh new profile which */
458 /* 'start' field must be completed */
459 Bool joint
; /* signals that the last arc ended */
460 /* exactly on a scanline. Allows */
461 /* removal of doublets */
462 PProfile cProfile
; /* current profile */
463 PProfile fProfile
; /* head of linked list of profiles */
464 PProfile gProfile
; /* contour's first profile in case */
467 TStates state
; /* rendering state */
469 FT_Bitmap target
; /* description of target bit/pixmap */
472 Long traceOfs
; /* current offset in target bitmap */
473 Long traceG
; /* current offset in target pixmap */
475 Short traceIncr
; /* sweep's increment in target bitmap */
477 Short gray_min_x
; /* current min x during gray rendering */
478 Short gray_max_x
; /* current max x during gray rendering */
480 /* dispatch variables */
482 Function_Sweep_Init
* Proc_Sweep_Init
;
483 Function_Sweep_Span
* Proc_Sweep_Span
;
484 Function_Sweep_Span
* Proc_Sweep_Drop
;
485 Function_Sweep_Step
* Proc_Sweep_Step
;
487 Byte dropOutControl
; /* current drop_out control method */
489 Bool second_pass
; /* indicates whether a horizontal pass */
490 /* should be performed to control */
491 /* drop-out accurately when calling */
492 /* Render_Glyph. Note that there is */
493 /* no horizontal pass during gray */
496 TPoint arcs
[3 * MaxBezier
+ 1]; /* The Bezier stack */
498 TBand band_stack
[16]; /* band stack used for sub-banding */
499 Int band_top
; /* band stack top */
501 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
505 Byte gray_lines
[RASTER_GRAY_LINES
];
506 /* Intermediate table used to render the */
507 /* graylevels pixmaps. */
508 /* gray_lines is a buffer holding two */
509 /* monochrome scanlines */
511 Short gray_width
; /* width in bytes of one monochrome */
512 /* intermediate scanline of gray_lines. */
513 /* Each gray pixel takes 2 bits long there */
515 /* The gray_lines must hold 2 lines, thus with size */
516 /* in bytes of at least `gray_width*2'. */
518 #endif /* FT_RASTER_ANTI_ALIASING */
523 typedef struct TRaster_
534 #ifdef FT_STATIC_RASTER
536 static TWorker cur_ras
;
541 #define ras (*worker)
543 #endif /* FT_STATIC_RASTER */
546 static const char count_table
[256] =
548 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4,
549 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5,
550 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5,
551 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
552 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5,
553 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
554 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
555 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7,
556 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5,
557 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
558 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
559 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7,
560 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6,
561 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7,
562 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7,
563 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 5 , 6 , 6 , 7 , 6 , 7 , 7 , 8 };
567 /*************************************************************************/
568 /*************************************************************************/
570 /** PROFILES COMPUTATION **/
572 /*************************************************************************/
573 /*************************************************************************/
576 /*************************************************************************/
579 /* Set_High_Precision */
582 /* Sets precision variables according to param flag. */
585 /* High :: Set to True for high precision (typically for ppem < 18), */
586 /* false otherwise. */
589 Set_High_Precision( RAS_ARGS Int High
)
593 ras
.precision_bits
= 10;
594 ras
.precision_step
= 128;
595 ras
.precision_jitter
= 24;
599 ras
.precision_bits
= 6;
600 ras
.precision_step
= 32;
601 ras
.precision_jitter
= 2;
604 FT_TRACE6(( "Set_High_Precision(%s)\n", High
? "true" : "false" ));
606 ras
.precision
= 1 << ras
.precision_bits
;
607 ras
.precision_half
= ras
.precision
/ 2;
608 ras
.precision_shift
= ras
.precision_bits
- Pixel_Bits
;
609 ras
.precision_mask
= -ras
.precision
;
613 /*************************************************************************/
619 /* Creates a new profile in the render pool. */
622 /* aState :: The state/orientation of the new profile. */
625 /* SUCCESS on success. FAILURE in case of overflow or of incoherent */
629 New_Profile( RAS_ARGS TStates aState
)
633 ras
.cProfile
= (PProfile
)ras
.top
;
634 ras
.fProfile
= ras
.cProfile
;
635 ras
.top
+= AlignProfileSize
;
638 if ( ras
.top
>= ras
.maxBuff
)
640 ras
.error
= Raster_Err_Overflow
;
646 case Ascending_State
:
647 ras
.cProfile
->flow
= Flow_Up
;
648 FT_TRACE6(( "New ascending profile = %lx\n", (long)ras
.cProfile
));
651 case Descending_State
:
652 ras
.cProfile
->flow
= Flow_Down
;
653 FT_TRACE6(( "New descending profile = %lx\n", (long)ras
.cProfile
));
657 FT_ERROR(( "New_Profile: invalid profile direction!\n" ));
658 ras
.error
= Raster_Err_Invalid
;
662 ras
.cProfile
->start
= 0;
663 ras
.cProfile
->height
= 0;
664 ras
.cProfile
->offset
= ras
.top
;
665 ras
.cProfile
->link
= (PProfile
)0;
666 ras
.cProfile
->next
= (PProfile
)0;
669 ras
.gProfile
= ras
.cProfile
;
679 /*************************************************************************/
685 /* Finalizes the current profile. */
688 /* SUCCESS on success. FAILURE in case of overflow or incoherency. */
691 End_Profile( RAS_ARG
)
697 h
= (Long
)( ras
.top
- ras
.cProfile
->offset
);
701 FT_ERROR(( "End_Profile: negative height encountered!\n" ));
702 ras
.error
= Raster_Err_Neg_Height
;
708 FT_TRACE6(( "Ending profile %lx, start = %ld, height = %ld\n",
709 (long)ras
.cProfile
, ras
.cProfile
->start
, h
));
711 oldProfile
= ras
.cProfile
;
712 ras
.cProfile
->height
= h
;
713 ras
.cProfile
= (PProfile
)ras
.top
;
715 ras
.top
+= AlignProfileSize
;
717 ras
.cProfile
->height
= 0;
718 ras
.cProfile
->offset
= ras
.top
;
719 oldProfile
->next
= ras
.cProfile
;
723 if ( ras
.top
>= ras
.maxBuff
)
725 FT_TRACE1(( "overflow in End_Profile\n" ));
726 ras
.error
= Raster_Err_Overflow
;
736 /*************************************************************************/
742 /* Inserts a salient into the sorted list placed on top of the render */
746 /* New y scanline position. */
749 /* SUCCESS on success. FAILURE in case of overflow. */
752 Insert_Y_Turn( RAS_ARGS Int y
)
758 n
= ras
.numTurns
- 1;
759 y_turns
= ras
.sizeBuff
- ras
.numTurns
;
761 /* look for first y value that is <= */
762 while ( n
>= 0 && y
< y_turns
[n
] )
765 /* if it is <, simply insert it, ignore if == */
766 if ( n
>= 0 && y
> y_turns
[n
] )
769 y2
= (Int
)y_turns
[n
];
778 if ( ras
.maxBuff
<= ras
.top
)
780 ras
.error
= Raster_Err_Overflow
;
784 ras
.sizeBuff
[-ras
.numTurns
] = y
;
791 /*************************************************************************/
794 /* Finalize_Profile_Table */
797 /* Adjusts all links in the profiles list. */
800 /* SUCCESS on success. FAILURE in case of overflow. */
803 Finalize_Profile_Table( RAS_ARG
)
818 p
->link
= (PProfile
)( p
->offset
+ p
->height
);
825 bottom
= (Int
)( p
->start
- p
->height
+ 1 );
828 p
->offset
+= p
->height
- 1;
833 bottom
= (Int
)p
->start
;
834 top
= (Int
)( p
->start
+ p
->height
- 1 );
837 if ( Insert_Y_Turn( RAS_VARS bottom
) ||
838 Insert_Y_Turn( RAS_VARS top
+ 1 ) )
852 /*************************************************************************/
858 /* Subdivides one conic Bezier into two joint sub-arcs in the Bezier */
862 /* None (subdivided Bezier is taken from the top of the stack). */
865 /* This routine is the `beef' of this component. It is _the_ inner */
866 /* loop that should be optimized to hell to get the best performance. */
869 Split_Conic( TPoint
* base
)
874 base
[4].x
= base
[2].x
;
876 a
= base
[3].x
= ( base
[2].x
+ b
) / 2;
877 b
= base
[1].x
= ( base
[0].x
+ b
) / 2;
878 base
[2].x
= ( a
+ b
) / 2;
880 base
[4].y
= base
[2].y
;
882 a
= base
[3].y
= ( base
[2].y
+ b
) / 2;
883 b
= base
[1].y
= ( base
[0].y
+ b
) / 2;
884 base
[2].y
= ( a
+ b
) / 2;
886 /* hand optimized. gcc doesn't seem to be too good at common */
887 /* expression substitution and instruction scheduling ;-) */
891 /*************************************************************************/
897 /* Subdivides a third-order Bezier arc into two joint sub-arcs in the */
901 /* This routine is the `beef' of the component. It is one of _the_ */
902 /* inner loops that should be optimized like hell to get the best */
906 Split_Cubic( TPoint
* base
)
911 base
[6].x
= base
[3].x
;
914 base
[1].x
= a
= ( base
[0].x
+ c
+ 1 ) >> 1;
915 base
[5].x
= b
= ( base
[3].x
+ d
+ 1 ) >> 1;
916 c
= ( c
+ d
+ 1 ) >> 1;
917 base
[2].x
= a
= ( a
+ c
+ 1 ) >> 1;
918 base
[4].x
= b
= ( b
+ c
+ 1 ) >> 1;
919 base
[3].x
= ( a
+ b
+ 1 ) >> 1;
921 base
[6].y
= base
[3].y
;
924 base
[1].y
= a
= ( base
[0].y
+ c
+ 1 ) >> 1;
925 base
[5].y
= b
= ( base
[3].y
+ d
+ 1 ) >> 1;
926 c
= ( c
+ d
+ 1 ) >> 1;
927 base
[2].y
= a
= ( a
+ c
+ 1 ) >> 1;
928 base
[4].y
= b
= ( b
+ c
+ 1 ) >> 1;
929 base
[3].y
= ( a
+ b
+ 1 ) >> 1;
933 /*************************************************************************/
939 /* Computes the x-coordinates of an ascending line segment and stores */
940 /* them in the render pool. */
943 /* x1 :: The x-coordinate of the segment's start point. */
945 /* y1 :: The y-coordinate of the segment's start point. */
947 /* x2 :: The x-coordinate of the segment's end point. */
949 /* y2 :: The y-coordinate of the segment's end point. */
951 /* miny :: A lower vertical clipping bound value. */
953 /* maxy :: An upper vertical clipping bound value. */
956 /* SUCCESS on success, FAILURE on render pool overflow. */
959 Line_Up( RAS_ARGS Long x1
,
967 Int e1
, e2
, f1
, f2
, size
; /* XXX: is `Short' sufficient? */
976 if ( Dy
<= 0 || y2
< miny
|| y1
> maxy
)
981 /* Take care: miny-y1 can be a very large value; we use */
982 /* a slow MulDiv function to avoid clipping bugs */
983 x1
+= SMulDiv( Dx
, miny
- y1
, Dy
);
984 e1
= (Int
)TRUNC( miny
);
989 e1
= (Int
)TRUNC( y1
);
990 f1
= (Int
)FRAC( y1
);
995 /* x2 += FMulDiv( Dx, maxy - y2, Dy ); UNNECESSARY */
996 e2
= (Int
)TRUNC( maxy
);
1001 e2
= (Int
)TRUNC( y2
);
1002 f2
= (Int
)FRAC( y2
);
1011 x1
+= FMulDiv( Dx
, ras
.precision
- f1
, Dy
);
1022 ras
.joint
= (char)( f2
== 0 );
1026 ras
.cProfile
->start
= e1
;
1031 if ( ras
.top
+ size
>= ras
.maxBuff
)
1033 ras
.error
= Raster_Err_Overflow
;
1039 Ix
= ( ras
.precision
* Dx
) / Dy
;
1040 Rx
= ( ras
.precision
* Dx
) % Dy
;
1045 Ix
= -( ( ras
.precision
* -Dx
) / Dy
);
1046 Rx
= ( ras
.precision
* -Dx
) % Dy
;
1072 /*************************************************************************/
1078 /* Computes the x-coordinates of an descending line segment and */
1079 /* stores them in the render pool. */
1082 /* x1 :: The x-coordinate of the segment's start point. */
1084 /* y1 :: The y-coordinate of the segment's start point. */
1086 /* x2 :: The x-coordinate of the segment's end point. */
1088 /* y2 :: The y-coordinate of the segment's end point. */
1090 /* miny :: A lower vertical clipping bound value. */
1092 /* maxy :: An upper vertical clipping bound value. */
1095 /* SUCCESS on success, FAILURE on render pool overflow. */
1098 Line_Down( RAS_ARGS Long x1
,
1110 result
= Line_Up( RAS_VARS x1
, -y1
, x2
, -y2
, -maxy
, -miny
);
1112 if ( fresh
&& !ras
.fresh
)
1113 ras
.cProfile
->start
= -ras
.cProfile
->start
;
1119 /* A function type describing the functions used to split Bezier arcs */
1120 typedef void (*TSplitter
)( TPoint
* base
);
1123 /*************************************************************************/
1129 /* Computes the x-coordinates of an ascending Bezier arc and stores */
1130 /* them in the render pool. */
1133 /* degree :: The degree of the Bezier arc (either 2 or 3). */
1135 /* splitter :: The function to split Bezier arcs. */
1137 /* miny :: A lower vertical clipping bound value. */
1139 /* maxy :: An upper vertical clipping bound value. */
1142 /* SUCCESS on success, FAILURE on render pool overflow. */
1145 Bezier_Up( RAS_ARGS Int degree
,
1150 Long y1
, y2
, e
, e2
, e0
;
1164 if ( y2
< miny
|| y1
> maxy
)
1179 f1
= (Short
)( FRAC( y1
) );
1190 *top
++ = arc
[degree
].x
;
1198 ras
.cProfile
->start
= TRUNC( e0
);
1205 if ( ( top
+ TRUNC( e2
- e
) + 1 ) >= ras
.maxBuff
)
1208 ras
.error
= Raster_Err_Overflow
;
1214 while ( arc
>= start_arc
&& e
<= e2
)
1223 if ( y2
- y1
>= ras
.precision_step
)
1230 *top
++ = arc
[degree
].x
+ FMulDiv( arc
[0].x
-arc
[degree
].x
,
1256 /*************************************************************************/
1262 /* Computes the x-coordinates of an descending Bezier arc and stores */
1263 /* them in the render pool. */
1266 /* degree :: The degree of the Bezier arc (either 2 or 3). */
1268 /* splitter :: The function to split Bezier arcs. */
1270 /* miny :: A lower vertical clipping bound value. */
1272 /* maxy :: An upper vertical clipping bound value. */
1275 /* SUCCESS on success, FAILURE on render pool overflow. */
1278 Bezier_Down( RAS_ARGS Int degree
,
1283 TPoint
* arc
= ras
.arc
;
1287 arc
[0].y
= -arc
[0].y
;
1288 arc
[1].y
= -arc
[1].y
;
1289 arc
[2].y
= -arc
[2].y
;
1291 arc
[3].y
= -arc
[3].y
;
1295 result
= Bezier_Up( RAS_VARS degree
, splitter
, -maxy
, -miny
);
1297 if ( fresh
&& !ras
.fresh
)
1298 ras
.cProfile
->start
= -ras
.cProfile
->start
;
1300 arc
[0].y
= -arc
[0].y
;
1305 /*************************************************************************/
1311 /* Injects a new line segment and adjusts Profiles list. */
1314 /* x :: The x-coordinate of the segment's end point (its start point */
1315 /* is stored in `lastX'). */
1317 /* y :: The y-coordinate of the segment's end point (its start point */
1318 /* is stored in `lastY'). */
1321 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1325 Line_To( RAS_ARGS Long x
,
1328 /* First, detect a change of direction */
1330 switch ( ras
.state
)
1333 if ( y
> ras
.lastY
)
1335 if ( New_Profile( RAS_VARS Ascending_State
) )
1340 if ( y
< ras
.lastY
)
1341 if ( New_Profile( RAS_VARS Descending_State
) )
1346 case Ascending_State
:
1347 if ( y
< ras
.lastY
)
1349 if ( End_Profile( RAS_VAR
) ||
1350 New_Profile( RAS_VARS Descending_State
) )
1355 case Descending_State
:
1356 if ( y
> ras
.lastY
)
1358 if ( End_Profile( RAS_VAR
) ||
1359 New_Profile( RAS_VARS Ascending_State
) )
1368 /* Then compute the lines */
1370 switch ( ras
.state
)
1372 case Ascending_State
:
1373 if ( Line_Up( RAS_VARS ras
.lastX
, ras
.lastY
,
1374 x
, y
, ras
.minY
, ras
.maxY
) )
1378 case Descending_State
:
1379 if ( Line_Down( RAS_VARS ras
.lastX
, ras
.lastY
,
1380 x
, y
, ras
.minY
, ras
.maxY
) )
1395 /*************************************************************************/
1401 /* Injects a new conic arc and adjusts the profile list. */
1404 /* cx :: The x-coordinate of the arc's new control point. */
1406 /* cy :: The y-coordinate of the arc's new control point. */
1408 /* x :: The x-coordinate of the arc's end point (its start point is */
1409 /* stored in `lastX'). */
1411 /* y :: The y-coordinate of the arc's end point (its start point is */
1412 /* stored in `lastY'). */
1415 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1419 Conic_To( RAS_ARGS Long cx
,
1424 Long y1
, y2
, y3
, x3
, ymin
, ymax
;
1429 ras
.arc
[2].x
= ras
.lastX
;
1430 ras
.arc
[2].y
= ras
.lastY
;
1431 ras
.arc
[1].x
= cx
; ras
.arc
[1].y
= cy
;
1432 ras
.arc
[0].x
= x
; ras
.arc
[0].y
= y
;
1441 /* first, categorize the Bezier arc */
1454 if ( y2
< ymin
|| y2
> ymax
)
1456 /* this arc has no given direction, split it! */
1457 Split_Conic( ras
.arc
);
1460 else if ( y1
== y3
)
1462 /* this arc is flat, ignore it and pop it from the Bezier stack */
1467 /* the arc is y-monotonous, either ascending or descending */
1468 /* detect a change of direction */
1469 state_bez
= y1
< y3
? Ascending_State
: Descending_State
;
1470 if ( ras
.state
!= state_bez
)
1472 /* finalize current profile if any */
1473 if ( ras
.state
!= Unknown_State
&&
1474 End_Profile( RAS_VAR
) )
1477 /* create a new profile */
1478 if ( New_Profile( RAS_VARS state_bez
) )
1482 /* now call the appropriate routine */
1483 if ( state_bez
== Ascending_State
)
1485 if ( Bezier_Up( RAS_VARS
2, Split_Conic
, ras
.minY
, ras
.maxY
) )
1489 if ( Bezier_Down( RAS_VARS
2, Split_Conic
, ras
.minY
, ras
.maxY
) )
1493 } while ( ras
.arc
>= ras
.arcs
);
1505 /*************************************************************************/
1511 /* Injects a new cubic arc and adjusts the profile list. */
1514 /* cx1 :: The x-coordinate of the arc's first new control point. */
1516 /* cy1 :: The y-coordinate of the arc's first new control point. */
1518 /* cx2 :: The x-coordinate of the arc's second new control point. */
1520 /* cy2 :: The y-coordinate of the arc's second new control point. */
1522 /* x :: The x-coordinate of the arc's end point (its start point is */
1523 /* stored in `lastX'). */
1525 /* y :: The y-coordinate of the arc's end point (its start point is */
1526 /* stored in `lastY'). */
1529 /* SUCCESS on success, FAILURE on render pool overflow or incorrect */
1533 Cubic_To( RAS_ARGS Long cx1
,
1540 Long y1
, y2
, y3
, y4
, x4
, ymin1
, ymax1
, ymin2
, ymax2
;
1545 ras
.arc
[3].x
= ras
.lastX
;
1546 ras
.arc
[3].y
= ras
.lastY
;
1547 ras
.arc
[2].x
= cx1
; ras
.arc
[2].y
= cy1
;
1548 ras
.arc
[1].x
= cx2
; ras
.arc
[1].y
= cy2
;
1549 ras
.arc
[0].x
= x
; ras
.arc
[0].y
= y
;
1559 /* first, categorize the Bezier arc */
1583 if ( ymin2
< ymin1
|| ymax2
> ymax1
)
1585 /* this arc has no given direction, split it! */
1586 Split_Cubic( ras
.arc
);
1589 else if ( y1
== y4
)
1591 /* this arc is flat, ignore it and pop it from the Bezier stack */
1596 state_bez
= ( y1
<= y4
) ? Ascending_State
: Descending_State
;
1598 /* detect a change of direction */
1599 if ( ras
.state
!= state_bez
)
1601 if ( ras
.state
!= Unknown_State
&&
1602 End_Profile( RAS_VAR
) )
1605 if ( New_Profile( RAS_VARS state_bez
) )
1609 /* compute intersections */
1610 if ( state_bez
== Ascending_State
)
1612 if ( Bezier_Up( RAS_VARS
3, Split_Cubic
, ras
.minY
, ras
.maxY
) )
1616 if ( Bezier_Down( RAS_VARS
3, Split_Cubic
, ras
.minY
, ras
.maxY
) )
1620 } while ( ras
.arc
>= ras
.arcs
);
1633 #define SWAP_( x, y ) do \
1643 /*************************************************************************/
1646 /* Decompose_Curve */
1649 /* Scans the outline arrays in order to emit individual segments and */
1650 /* Beziers by calling Line_To() and Bezier_To(). It handles all */
1651 /* weird cases, like when the first point is off the curve, or when */
1652 /* there are simply no `on' points in the contour! */
1655 /* first :: The index of the first point in the contour. */
1657 /* last :: The index of the last point in the contour. */
1659 /* flipped :: If set, flip the direction of the curve. */
1662 /* SUCCESS on success, FAILURE on error. */
1665 Decompose_Curve( RAS_ARGS UShort first
,
1670 FT_Vector v_control
;
1678 unsigned tag
; /* current point's state */
1681 points
= ras
.outline
.points
;
1682 limit
= points
+ last
;
1684 v_start
.x
= SCALED( points
[first
].x
);
1685 v_start
.y
= SCALED( points
[first
].y
);
1686 v_last
.x
= SCALED( points
[last
].x
);
1687 v_last
.y
= SCALED( points
[last
].y
);
1691 SWAP_( v_start
.x
, v_start
.y
);
1692 SWAP_( v_last
.x
, v_last
.y
);
1695 v_control
= v_start
;
1697 point
= points
+ first
;
1698 tags
= ras
.outline
.tags
+ first
;
1699 tag
= FT_CURVE_TAG( tags
[0] );
1701 /* A contour cannot start with a cubic control point! */
1702 if ( tag
== FT_CURVE_TAG_CUBIC
)
1703 goto Invalid_Outline
;
1705 /* check first point to determine origin */
1706 if ( tag
== FT_CURVE_TAG_CONIC
)
1708 /* first point is conic control. Yes, this happens. */
1709 if ( FT_CURVE_TAG( ras
.outline
.tags
[last
] ) == FT_CURVE_TAG_ON
)
1711 /* start at last point if it is on the curve */
1717 /* if both first and last points are conic, */
1718 /* start at their middle and record its position */
1720 v_start
.x
= ( v_start
.x
+ v_last
.x
) / 2;
1721 v_start
.y
= ( v_start
.y
+ v_last
.y
) / 2;
1729 ras
.lastX
= v_start
.x
;
1730 ras
.lastY
= v_start
.y
;
1732 while ( point
< limit
)
1737 tag
= FT_CURVE_TAG( tags
[0] );
1741 case FT_CURVE_TAG_ON
: /* emit a single line_to */
1746 x
= SCALED( point
->x
);
1747 y
= SCALED( point
->y
);
1751 if ( Line_To( RAS_VARS x
, y
) )
1756 case FT_CURVE_TAG_CONIC
: /* consume conic arcs */
1757 v_control
.x
= SCALED( point
[0].x
);
1758 v_control
.y
= SCALED( point
[0].y
);
1761 SWAP_( v_control
.x
, v_control
.y
);
1764 if ( point
< limit
)
1772 tag
= FT_CURVE_TAG( tags
[0] );
1774 x
= SCALED( point
[0].x
);
1775 y
= SCALED( point
[0].y
);
1780 if ( tag
== FT_CURVE_TAG_ON
)
1782 if ( Conic_To( RAS_VARS v_control
.x
, v_control
.y
, x
, y
) )
1787 if ( tag
!= FT_CURVE_TAG_CONIC
)
1788 goto Invalid_Outline
;
1790 v_middle
.x
= ( v_control
.x
+ x
) / 2;
1791 v_middle
.y
= ( v_control
.y
+ y
) / 2;
1793 if ( Conic_To( RAS_VARS v_control
.x
, v_control
.y
,
1794 v_middle
.x
, v_middle
.y
) )
1803 if ( Conic_To( RAS_VARS v_control
.x
, v_control
.y
,
1804 v_start
.x
, v_start
.y
) )
1809 default: /* FT_CURVE_TAG_CUBIC */
1811 Long x1
, y1
, x2
, y2
, x3
, y3
;
1814 if ( point
+ 1 > limit
||
1815 FT_CURVE_TAG( tags
[1] ) != FT_CURVE_TAG_CUBIC
)
1816 goto Invalid_Outline
;
1821 x1
= SCALED( point
[-2].x
);
1822 y1
= SCALED( point
[-2].y
);
1823 x2
= SCALED( point
[-1].x
);
1824 y2
= SCALED( point
[-1].y
);
1825 x3
= SCALED( point
[ 0].x
);
1826 y3
= SCALED( point
[ 0].y
);
1835 if ( point
<= limit
)
1837 if ( Cubic_To( RAS_VARS x1
, y1
, x2
, y2
, x3
, y3
) )
1842 if ( Cubic_To( RAS_VARS x1
, y1
, x2
, y2
, v_start
.x
, v_start
.y
) )
1849 /* close the contour with a line segment */
1850 if ( Line_To( RAS_VARS v_start
.x
, v_start
.y
) )
1857 ras
.error
= Raster_Err_Invalid
;
1864 /*************************************************************************/
1870 /* Converts a glyph into a series of segments and arcs and makes a */
1871 /* profiles list with them. */
1874 /* flipped :: If set, flip the direction of curve. */
1877 /* SUCCESS on success, FAILURE if any error was encountered during */
1881 Convert_Glyph( RAS_ARGS
int flipped
)
1886 PProfile lastProfile
;
1889 ras
.fProfile
= NULL
;
1893 ras
.maxBuff
= ras
.sizeBuff
- AlignProfileSize
;
1897 ras
.cProfile
= (PProfile
)ras
.top
;
1898 ras
.cProfile
->offset
= ras
.top
;
1903 for ( i
= 0; i
< ras
.outline
.n_contours
; i
++ )
1905 ras
.state
= Unknown_State
;
1906 ras
.gProfile
= NULL
;
1908 if ( Decompose_Curve( RAS_VARS (unsigned short)start
,
1909 ras
.outline
.contours
[i
],
1913 start
= ras
.outline
.contours
[i
] + 1;
1915 /* We must now see whether the extreme arcs join or not */
1916 if ( FRAC( ras
.lastY
) == 0 &&
1917 ras
.lastY
>= ras
.minY
&&
1918 ras
.lastY
<= ras
.maxY
)
1919 if ( ras
.gProfile
&& ras
.gProfile
->flow
== ras
.cProfile
->flow
)
1921 /* Note that ras.gProfile can be nil if the contour was too small */
1924 lastProfile
= ras
.cProfile
;
1925 if ( End_Profile( RAS_VAR
) )
1928 /* close the `next profile in contour' linked list */
1930 lastProfile
->next
= ras
.gProfile
;
1933 if ( Finalize_Profile_Table( RAS_VAR
) )
1936 return (Bool
)( ras
.top
< ras
.maxBuff
? SUCCESS
: FAILURE
);
1940 /*************************************************************************/
1941 /*************************************************************************/
1943 /** SCAN-LINE SWEEPS AND DRAWING **/
1945 /*************************************************************************/
1946 /*************************************************************************/
1949 /*************************************************************************/
1953 /* Initializes an empty linked list. */
1956 Init_Linked( TProfileList
* l
)
1962 /*************************************************************************/
1966 /* Inserts a new profile in a linked list. */
1969 InsNew( PProfileList list
,
1972 PProfile
*old
, current
;
1982 if ( x
< current
->X
)
1984 old
= ¤t
->link
;
1988 profile
->link
= current
;
1993 /*************************************************************************/
1997 /* Removes an old profile from a linked list. */
2000 DelOld( PProfileList list
,
2003 PProfile
*old
, current
;
2011 if ( current
== profile
)
2013 *old
= current
->link
;
2017 old
= ¤t
->link
;
2021 /* we should never get there, unless the profile was not part of */
2026 /*************************************************************************/
2030 /* Sorts a trace list. In 95%, the list is already sorted. We need */
2031 /* an algorithm which is fast in this case. Bubble sort is enough */
2035 Sort( PProfileList list
)
2037 PProfile
*old
, current
, next
;
2040 /* First, set the new X coordinate of each profile */
2044 current
->X
= *current
->offset
;
2045 current
->offset
+= current
->flow
;
2047 current
= current
->link
;
2050 /* Then sort them */
2057 next
= current
->link
;
2061 if ( current
->X
<= next
->X
)
2063 old
= ¤t
->link
;
2072 current
->link
= next
->link
;
2073 next
->link
= current
;
2079 next
= current
->link
;
2084 /*************************************************************************/
2086 /* Vertical Sweep Procedure Set */
2088 /* These four routines are used during the vertical black/white sweep */
2089 /* phase by the generic Draw_Sweep() function. */
2091 /*************************************************************************/
2094 Vertical_Sweep_Init( RAS_ARGS Short
* min
,
2097 Long pitch
= ras
.target
.pitch
;
2102 ras
.traceIncr
= (Short
)-pitch
;
2103 ras
.traceOfs
= -*min
* pitch
;
2105 ras
.traceOfs
+= ( ras
.target
.rows
- 1 ) * pitch
;
2113 Vertical_Sweep_Span( RAS_ARGS Short y
,
2129 /* Drop-out control */
2131 e1
= TRUNC( CEILING( x1
) );
2133 if ( x2
- x1
- ras
.precision
<= ras
.precision_jitter
)
2136 e2
= TRUNC( FLOOR( x2
) );
2138 if ( e2
>= 0 && e1
< ras
.bWidth
)
2142 if ( e2
>= ras
.bWidth
)
2143 e2
= ras
.bWidth
- 1;
2145 c1
= (Short
)( e1
>> 3 );
2146 c2
= (Short
)( e2
>> 3 );
2148 f1
= (Byte
) ( 0xFF >> ( e1
& 7 ) );
2149 f2
= (Byte
) ~( 0x7F >> ( e2
& 7 ) );
2151 if ( ras
.gray_min_x
> c1
) ras
.gray_min_x
= (short)c1
;
2152 if ( ras
.gray_max_x
< c2
) ras
.gray_max_x
= (short)c2
;
2154 target
= ras
.bTarget
+ ras
.traceOfs
+ c1
;
2161 /* memset() is slower than the following code on many platforms. */
2162 /* This is due to the fact that, in the vast majority of cases, */
2163 /* the span length in bytes is relatively small. */
2173 *target
|= ( f1
& f2
);
2179 Vertical_Sweep_Drop( RAS_ARGS Short y
,
2189 /* Drop-out control */
2196 if ( e1
== e2
+ ras
.precision
)
2198 switch ( ras
.dropOutControl
)
2205 e1
= CEILING( (x1
+ x2
+ 1) / 2 );
2210 /* Drop-out Control Rule #4 */
2212 /* The spec is not very clear regarding rule #4. It */
2213 /* presents a method that is way too costly to implement */
2214 /* while the general idea seems to get rid of `stubs'. */
2216 /* Here, we only get rid of stubs recognized if: */
2220 /* - P_Left and P_Right are in the same contour */
2221 /* - P_Right is the successor of P_Left in that contour */
2222 /* - y is the top of P_Left and P_Right */
2226 /* - P_Left and P_Right are in the same contour */
2227 /* - P_Left is the successor of P_Right in that contour */
2228 /* - y is the bottom of P_Left */
2231 /* FIXXXME: uncommenting this line solves the disappearing */
2232 /* bit problem in the `7' of verdana 10pts, but */
2233 /* makes a new one in the `C' of arial 14pts */
2236 if ( x2
- x1
< ras
.precision_half
)
2239 /* upper stub test */
2240 if ( left
->next
== right
&& left
->height
<= 0 )
2243 /* lower stub test */
2244 if ( right
->next
== left
&& left
->start
== y
)
2248 /* check that the rightmost pixel isn't set */
2252 c1
= (Short
)( e1
>> 3 );
2253 f1
= (Short
)( e1
& 7 );
2255 if ( e1
>= 0 && e1
< ras
.bWidth
&&
2256 ras
.bTarget
[ras
.traceOfs
+ c1
] & ( 0x80 >> f1
) )
2259 if ( ras
.dropOutControl
== 2 )
2262 e1
= CEILING( ( x1
+ x2
+ 1 ) / 2 );
2267 return; /* unsupported mode */
2276 if ( e1
>= 0 && e1
< ras
.bWidth
)
2278 c1
= (Short
)( e1
>> 3 );
2279 f1
= (Short
)( e1
& 7 );
2281 if ( ras
.gray_min_x
> c1
) ras
.gray_min_x
= c1
;
2282 if ( ras
.gray_max_x
< c1
) ras
.gray_max_x
= c1
;
2284 ras
.bTarget
[ras
.traceOfs
+ c1
] |= (char)( 0x80 >> f1
);
2290 Vertical_Sweep_Step( RAS_ARG
)
2292 ras
.traceOfs
+= ras
.traceIncr
;
2296 /***********************************************************************/
2298 /* Horizontal Sweep Procedure Set */
2300 /* These four routines are used during the horizontal black/white */
2301 /* sweep phase by the generic Draw_Sweep() function. */
2303 /***********************************************************************/
2306 Horizontal_Sweep_Init( RAS_ARGS Short
* min
,
2309 /* nothing, really */
2317 Horizontal_Sweep_Span( RAS_ARGS Short y
,
2331 if ( x2
- x1
< ras
.precision
)
2338 bits
= ras
.bTarget
+ ( y
>> 3 );
2339 f1
= (Byte
)( 0x80 >> ( y
& 7 ) );
2343 if ( e1
>= 0 && e1
< ras
.target
.rows
)
2348 p
= bits
- e1
*ras
.target
.pitch
;
2349 if ( ras
.target
.pitch
> 0 )
2350 p
+= ( ras
.target
.rows
- 1 ) * ras
.target
.pitch
;
2360 Horizontal_Sweep_Drop( RAS_ARGS Short y
,
2371 /* During the horizontal sweep, we only take care of drop-outs */
2378 if ( e1
== e2
+ ras
.precision
)
2380 switch ( ras
.dropOutControl
)
2387 e1
= CEILING( ( x1
+ x2
+ 1 ) / 2 );
2393 /* Drop-out Control Rule #4 */
2395 /* The spec is not very clear regarding rule #4. It */
2396 /* presents a method that is way too costly to implement */
2397 /* while the general idea seems to get rid of `stubs'. */
2400 /* rightmost stub test */
2401 if ( left
->next
== right
&& left
->height
<= 0 )
2404 /* leftmost stub test */
2405 if ( right
->next
== left
&& left
->start
== y
)
2408 /* check that the rightmost pixel isn't set */
2412 bits
= ras
.bTarget
+ ( y
>> 3 );
2413 f1
= (Byte
)( 0x80 >> ( y
& 7 ) );
2415 bits
-= e1
* ras
.target
.pitch
;
2416 if ( ras
.target
.pitch
> 0 )
2417 bits
+= ( ras
.target
.rows
- 1 ) * ras
.target
.pitch
;
2420 e1
< ras
.target
.rows
&&
2424 if ( ras
.dropOutControl
== 2 )
2427 e1
= CEILING( ( x1
+ x2
+ 1 ) / 2 );
2432 return; /* unsupported mode */
2439 bits
= ras
.bTarget
+ ( y
>> 3 );
2440 f1
= (Byte
)( 0x80 >> ( y
& 7 ) );
2444 if ( e1
>= 0 && e1
< ras
.target
.rows
)
2446 bits
-= e1
* ras
.target
.pitch
;
2447 if ( ras
.target
.pitch
> 0 )
2448 bits
+= ( ras
.target
.rows
- 1 ) * ras
.target
.pitch
;
2456 Horizontal_Sweep_Step( RAS_ARG
)
2458 /* Nothing, really */
2463 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
2466 /*************************************************************************/
2468 /* Vertical Gray Sweep Procedure Set */
2470 /* These two routines are used during the vertical gray-levels sweep */
2471 /* phase by the generic Draw_Sweep() function. */
2475 /* - The target pixmap's width *must* be a multiple of 4. */
2477 /* - You have to use the function Vertical_Sweep_Span() for the gray */
2480 /*************************************************************************/
2483 Vertical_Gray_Sweep_Init( RAS_ARGS Short
* min
,
2486 Long pitch
, byte_len
;
2490 *max
= ( *max
+ 3 ) & -2;
2493 pitch
= ras
.target
.pitch
;
2495 ras
.traceIncr
= (Short
)byte_len
;
2496 ras
.traceG
= ( *min
/ 2 ) * byte_len
;
2500 ras
.traceG
+= ( ras
.target
.rows
- 1 ) * pitch
;
2501 byte_len
= -byte_len
;
2504 ras
.gray_min_x
= (Short
)byte_len
;
2505 ras
.gray_max_x
= -(Short
)byte_len
;
2510 Vertical_Gray_Sweep_Step( RAS_ARG
)
2513 PByte pix
, bit
, bit2
;
2514 char* count
= (char*)count_table
;
2518 ras
.traceOfs
+= ras
.gray_width
;
2520 if ( ras
.traceOfs
> ras
.gray_width
)
2522 pix
= ras
.gTarget
+ ras
.traceG
+ ras
.gray_min_x
* 4;
2525 if ( ras
.gray_max_x
>= 0 )
2527 Long last_pixel
= ras
.target
.width
- 1;
2528 Int last_cell
= last_pixel
>> 2;
2529 Int last_bit
= last_pixel
& 3;
2533 if ( ras
.gray_max_x
>= last_cell
&& last_bit
!= 3 )
2535 ras
.gray_max_x
= last_cell
- 1;
2539 if ( ras
.gray_min_x
< 0 )
2542 bit
= ras
.bTarget
+ ras
.gray_min_x
;
2543 bit2
= bit
+ ras
.gray_width
;
2545 c1
= ras
.gray_max_x
- ras
.gray_min_x
;
2549 c2
= count
[*bit
] + count
[*bit2
];
2553 pix
[0] = grays
[(c2
>> 12) & 0x000F];
2554 pix
[1] = grays
[(c2
>> 8 ) & 0x000F];
2555 pix
[2] = grays
[(c2
>> 4 ) & 0x000F];
2556 pix
[3] = grays
[ c2
& 0x000F];
2570 c2
= count
[*bit
] + count
[*bit2
];
2576 pix
[2] = grays
[(c2
>> 4 ) & 0x000F];
2578 pix
[1] = grays
[(c2
>> 8 ) & 0x000F];
2580 pix
[0] = grays
[(c2
>> 12) & 0x000F];
2590 ras
.traceG
+= ras
.traceIncr
;
2592 ras
.gray_min_x
= 32000;
2593 ras
.gray_max_x
= -32000;
2599 Horizontal_Gray_Sweep_Span( RAS_ARGS Short y
,
2605 /* nothing, really */
2616 Horizontal_Gray_Sweep_Drop( RAS_ARGS Short y
,
2627 /* During the horizontal sweep, we only take care of drop-outs */
2633 if ( e1
== e2
+ ras
.precision
)
2635 switch ( ras
.dropOutControl
)
2642 e1
= CEILING( ( x1
+ x2
+ 1 ) / 2 );
2648 /* Drop-out Control Rule #4 */
2650 /* The spec is not very clear regarding rule #4. It */
2651 /* presents a method that is way too costly to implement */
2652 /* while the general idea seems to get rid of `stubs'. */
2655 /* rightmost stub test */
2656 if ( left
->next
== right
&& left
->height
<= 0 )
2659 /* leftmost stub test */
2660 if ( right
->next
== left
&& left
->start
== y
)
2663 if ( ras
.dropOutControl
== 2 )
2666 e1
= CEILING( ( x1
+ x2
+ 1 ) / 2 );
2671 return; /* unsupported mode */
2680 if ( x2
- x1
>= ras
.precision_half
)
2681 color
= ras
.grays
[2];
2683 color
= ras
.grays
[1];
2685 e1
= TRUNC( e1
) / 2;
2686 if ( e1
< ras
.target
.rows
)
2688 pixel
= ras
.gTarget
- e1
* ras
.target
.pitch
+ y
/ 2;
2689 if ( ras
.target
.pitch
> 0 )
2690 pixel
+= ( ras
.target
.rows
- 1 ) * ras
.target
.pitch
;
2692 if ( pixel
[0] == ras
.grays
[0] )
2699 #endif /* FT_RASTER_OPTION_ANTI_ALIASING */
2702 /*************************************************************************/
2704 /* Generic Sweep Drawing routine */
2706 /*************************************************************************/
2709 Draw_Sweep( RAS_ARG
)
2711 Short y
, y_change
, y_height
;
2713 PProfile P
, Q
, P_Left
, P_Right
;
2715 Short min_Y
, max_Y
, top
, bottom
, dropouts
;
2717 Long x1
, x2
, xs
, e1
, e2
;
2719 TProfileList waiting
;
2720 TProfileList draw_left
, draw_right
;
2723 /* Init empty linked lists */
2725 Init_Linked( &waiting
);
2727 Init_Linked( &draw_left
);
2728 Init_Linked( &draw_right
);
2730 /* first, compute min and max Y */
2733 max_Y
= (Short
)TRUNC( ras
.minY
);
2734 min_Y
= (Short
)TRUNC( ras
.maxY
);
2740 bottom
= (Short
)P
->start
;
2741 top
= (Short
)( P
->start
+ P
->height
- 1 );
2743 if ( min_Y
> bottom
) min_Y
= bottom
;
2744 if ( max_Y
< top
) max_Y
= top
;
2747 InsNew( &waiting
, P
);
2752 /* Check the Y-turns */
2753 if ( ras
.numTurns
== 0 )
2755 ras
.error
= Raster_Err_Invalid
;
2759 /* Now inits the sweep */
2761 ras
.Proc_Sweep_Init( RAS_VARS
&min_Y
, &max_Y
);
2763 /* Then compute the distance of each profile from min_Y */
2769 P
->countL
= (UShort
)( P
->start
- min_Y
);
2778 if ( ras
.numTurns
> 0 &&
2779 ras
.sizeBuff
[-ras
.numTurns
] == min_Y
)
2782 while ( ras
.numTurns
> 0 )
2784 /* look in the waiting list for new activations */
2791 P
->countL
-= y_height
;
2792 if ( P
->countL
== 0 )
2794 DelOld( &waiting
, P
);
2799 InsNew( &draw_left
, P
);
2803 InsNew( &draw_right
, P
);
2811 /* Sort the drawing lists */
2814 Sort( &draw_right
);
2816 y_change
= (Short
)ras
.sizeBuff
[-ras
.numTurns
--];
2817 y_height
= (Short
)( y_change
- y
);
2819 while ( y
< y_change
)
2826 P_Right
= draw_right
;
2840 if ( x2
- x1
<= ras
.precision
)
2845 if ( ras
.dropOutControl
!= 0 &&
2846 ( e1
> e2
|| e2
== e1
+ ras
.precision
) )
2848 /* a drop out was detected */
2853 /* mark profile for drop-out processing */
2861 ras
.Proc_Sweep_Span( RAS_VARS y
, x1
, x2
, P_Left
, P_Right
);
2865 P_Left
= P_Left
->link
;
2866 P_Right
= P_Right
->link
;
2869 /* now perform the dropouts _after_ the span drawing -- */
2870 /* drop-outs processing has been moved out of the loop */
2871 /* for performance tuning */
2877 ras
.Proc_Sweep_Step( RAS_VAR
);
2884 Sort( &draw_right
);
2888 /* Now finalize the profiles that needs it */
2894 if ( P
->height
== 0 )
2895 DelOld( &draw_left
, P
);
2903 if ( P
->height
== 0 )
2904 DelOld( &draw_right
, P
);
2909 /* for gray-scaling, flushes the bitmap scanline cache */
2910 while ( y
<= max_Y
)
2912 ras
.Proc_Sweep_Step( RAS_VAR
);
2921 P_Right
= draw_right
;
2925 if ( P_Left
->countL
)
2929 dropouts
--; /* -- this is useful when debugging only */
2931 ras
.Proc_Sweep_Drop( RAS_VARS y
,
2938 P_Left
= P_Left
->link
;
2939 P_Right
= P_Right
->link
;
2946 /*************************************************************************/
2949 /* Render_Single_Pass */
2952 /* Performs one sweep with sub-banding. */
2955 /* flipped :: If set, flip the direction of the outline. */
2958 /* Renderer error code. */
2961 Render_Single_Pass( RAS_ARGS Bool flipped
)
2966 while ( ras
.band_top
>= 0 )
2968 ras
.maxY
= (Long
)ras
.band_stack
[ras
.band_top
].y_max
* ras
.precision
;
2969 ras
.minY
= (Long
)ras
.band_stack
[ras
.band_top
].y_min
* ras
.precision
;
2973 ras
.error
= Raster_Err_None
;
2975 if ( Convert_Glyph( RAS_VARS flipped
) )
2977 if ( ras
.error
!= Raster_Err_Overflow
)
2980 ras
.error
= Raster_Err_None
;
2985 ClearBand( RAS_VARS
TRUNC( ras
.minY
), TRUNC( ras
.maxY
) );
2988 i
= ras
.band_stack
[ras
.band_top
].y_min
;
2989 j
= ras
.band_stack
[ras
.band_top
].y_max
;
2991 k
= (Short
)( ( i
+ j
) / 2 );
2993 if ( ras
.band_top
>= 7 || k
< i
)
2996 ras
.error
= Raster_Err_Invalid
;
3001 ras
.band_stack
[ras
.band_top
+ 1].y_min
= k
;
3002 ras
.band_stack
[ras
.band_top
+ 1].y_max
= j
;
3004 ras
.band_stack
[ras
.band_top
].y_max
= (Short
)( k
- 1 );
3011 if ( Draw_Sweep( RAS_VAR
) )
3021 /*************************************************************************/
3027 /* Renders a glyph in a bitmap. Sub-banding if needed. */
3030 /* FreeType error code. 0 means success. */
3032 FT_LOCAL_DEF( FT_Error
)
3033 Render_Glyph( RAS_ARG
)
3038 Set_High_Precision( RAS_VARS ras
.outline
.flags
&
3039 FT_OUTLINE_HIGH_PRECISION
);
3040 ras
.scale_shift
= ras
.precision_shift
;
3041 /* Drop-out mode 2 is hard-coded since this is the only mode used */
3042 /* on Windows platforms. Using other modes, as specified by the */
3043 /* font, results in misplaced pixels. */
3044 ras
.dropOutControl
= 2;
3045 ras
.second_pass
= (FT_Byte
)( !( ras
.outline
.flags
&
3046 FT_OUTLINE_SINGLE_PASS
) );
3048 /* Vertical Sweep */
3049 ras
.Proc_Sweep_Init
= Vertical_Sweep_Init
;
3050 ras
.Proc_Sweep_Span
= Vertical_Sweep_Span
;
3051 ras
.Proc_Sweep_Drop
= Vertical_Sweep_Drop
;
3052 ras
.Proc_Sweep_Step
= Vertical_Sweep_Step
;
3055 ras
.band_stack
[0].y_min
= 0;
3056 ras
.band_stack
[0].y_max
= (short)( ras
.target
.rows
- 1 );
3058 ras
.bWidth
= (unsigned short)ras
.target
.width
;
3059 ras
.bTarget
= (Byte
*)ras
.target
.buffer
;
3061 if ( ( error
= Render_Single_Pass( RAS_VARS
0 ) ) != 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_Sweep_Span
;
3069 ras
.Proc_Sweep_Drop
= Horizontal_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
= (short)( ras
.target
.width
- 1 );
3076 if ( ( error
= Render_Single_Pass( RAS_VARS
1 ) ) != 0 )
3080 return Raster_Err_None
;
3084 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3087 /*************************************************************************/
3090 /* Render_Gray_Glyph */
3093 /* Renders a glyph with grayscaling. Sub-banding if needed. */
3096 /* FreeType error code. 0 means success. */
3098 FT_LOCAL_DEF( FT_Error
)
3099 Render_Gray_Glyph( RAS_ARG
)
3105 Set_High_Precision( RAS_VARS ras
.outline
.flags
&
3106 FT_OUTLINE_HIGH_PRECISION
);
3107 ras
.scale_shift
= ras
.precision_shift
+ 1;
3108 /* Drop-out mode 2 is hard-coded since this is the only mode used */
3109 /* on Windows platforms. Using other modes, as specified by the */
3110 /* font, results in misplaced pixels. */
3111 ras
.dropOutControl
= 2;
3112 ras
.second_pass
= !( ras
.outline
.flags
& FT_OUTLINE_SINGLE_PASS
);
3114 /* Vertical Sweep */
3117 ras
.band_stack
[0].y_min
= 0;
3118 ras
.band_stack
[0].y_max
= 2 * ras
.target
.rows
- 1;
3120 ras
.bWidth
= ras
.gray_width
;
3121 pixel_width
= 2 * ( ( ras
.target
.width
+ 3 ) >> 2 );
3123 if ( ras
.bWidth
> pixel_width
)
3124 ras
.bWidth
= pixel_width
;
3126 ras
.bWidth
= ras
.bWidth
* 8;
3127 ras
.bTarget
= (Byte
*)ras
.gray_lines
;
3128 ras
.gTarget
= (Byte
*)ras
.target
.buffer
;
3130 ras
.Proc_Sweep_Init
= Vertical_Gray_Sweep_Init
;
3131 ras
.Proc_Sweep_Span
= Vertical_Sweep_Span
;
3132 ras
.Proc_Sweep_Drop
= Vertical_Sweep_Drop
;
3133 ras
.Proc_Sweep_Step
= Vertical_Gray_Sweep_Step
;
3135 error
= Render_Single_Pass( RAS_VARS
0 );
3139 /* Horizontal Sweep */
3140 if ( ras
.second_pass
&& ras
.dropOutControl
!= 0 )
3142 ras
.Proc_Sweep_Init
= Horizontal_Sweep_Init
;
3143 ras
.Proc_Sweep_Span
= Horizontal_Gray_Sweep_Span
;
3144 ras
.Proc_Sweep_Drop
= Horizontal_Gray_Sweep_Drop
;
3145 ras
.Proc_Sweep_Step
= Horizontal_Sweep_Step
;
3148 ras
.band_stack
[0].y_min
= 0;
3149 ras
.band_stack
[0].y_max
= ras
.target
.width
* 2 - 1;
3151 error
= Render_Single_Pass( RAS_VARS
1 );
3156 return Raster_Err_None
;
3159 #else /* !FT_RASTER_OPTION_ANTI_ALIASING */
3161 FT_LOCAL_DEF( FT_Error
)
3162 Render_Gray_Glyph( RAS_ARG
)
3166 return Raster_Err_Unsupported
;
3169 #endif /* !FT_RASTER_OPTION_ANTI_ALIASING */
3173 ft_black_init( PRaster raster
)
3175 FT_UNUSED( raster
);
3177 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3181 /* set default 5-levels gray palette */
3182 for ( n
= 0; n
< 5; n
++ )
3183 raster
->grays
[n
] = n
* 255 / 4;
3185 raster
->gray_width
= RASTER_GRAY_LINES
/ 2;
3191 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
3192 /**** a static object. *****/
3199 ft_black_new( void* memory
,
3200 FT_Raster
*araster
)
3202 static TRaster the_raster
;
3205 *araster
= (FT_Raster
)&the_raster
;
3206 FT_MEM_ZERO( &the_raster
, sizeof ( the_raster
) );
3207 ft_black_init( &the_raster
);
3214 ft_black_done( FT_Raster raster
)
3217 FT_UNUSED( raster
);
3221 #else /* _STANDALONE_ */
3225 ft_black_new( FT_Memory memory
,
3233 if ( !FT_NEW( raster
) )
3235 raster
->memory
= memory
;
3236 ft_black_init( raster
);
3246 ft_black_done( PRaster raster
)
3248 FT_Memory memory
= (FT_Memory
)raster
->memory
;
3253 #endif /* _STANDALONE_ */
3257 ft_black_reset( PRaster raster
,
3263 if ( pool_base
&& pool_size
>= (long)sizeof(TWorker
) + 2048 )
3265 PWorker worker
= (PWorker
)pool_base
;
3268 raster
->buffer
= pool_base
+ ( (sizeof ( *worker
) + 7 ) & ~7 );
3269 raster
->buffer_size
= ( ( pool_base
+ pool_size
) -
3270 (char*)raster
->buffer
) / sizeof ( Long
);
3271 raster
->worker
= worker
;
3275 raster
->buffer
= NULL
;
3276 raster
->buffer_size
= 0;
3277 raster
->worker
= NULL
;
3284 ft_black_set_mode( PRaster raster
,
3286 const char* palette
)
3288 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3290 if ( mode
== FT_MAKE_TAG( 'p', 'a', 'l', '5' ) )
3292 /* set 5-levels gray palette */
3293 raster
->grays
[0] = palette
[0];
3294 raster
->grays
[1] = palette
[1];
3295 raster
->grays
[2] = palette
[2];
3296 raster
->grays
[3] = palette
[3];
3297 raster
->grays
[4] = palette
[4];
3302 FT_UNUSED( raster
);
3304 FT_UNUSED( palette
);
3311 ft_black_render( PRaster raster
,
3312 const FT_Raster_Params
* params
)
3314 const FT_Outline
* outline
= (const FT_Outline
*)params
->source
;
3315 const FT_Bitmap
* target_map
= params
->target
;
3319 if ( !raster
|| !raster
->buffer
|| !raster
->buffer_size
)
3320 return Raster_Err_Not_Ini
;
3322 /* return immediately if the outline is empty */
3323 if ( outline
->n_points
== 0 || outline
->n_contours
<= 0 )
3324 return Raster_Err_None
;
3326 if ( !outline
|| !outline
->contours
|| !outline
->points
)
3327 return Raster_Err_Invalid
;
3329 if ( outline
->n_points
!= outline
->contours
[outline
->n_contours
- 1] + 1 )
3330 return Raster_Err_Invalid
;
3332 worker
= raster
->worker
;
3334 /* this version of the raster does not support direct rendering, sorry */
3335 if ( params
->flags
& FT_RASTER_FLAG_DIRECT
)
3336 return Raster_Err_Unsupported
;
3338 if ( !target_map
|| !target_map
->buffer
)
3339 return Raster_Err_Invalid
;
3341 ras
.outline
= *outline
;
3342 ras
.target
= *target_map
;
3344 worker
->buff
= (PLong
) raster
->buffer
;
3345 worker
->sizeBuff
= worker
->buff
+
3346 raster
->buffer_size
/ sizeof ( Long
);
3347 #ifdef FT_RASTER_OPTION_ANTI_ALIASING
3348 worker
->grays
= raster
->grays
;
3349 worker
->gray_width
= raster
->gray_width
;
3352 return ( ( params
->flags
& FT_RASTER_FLAG_AA
)
3353 ? Render_Gray_Glyph( RAS_VAR
)
3354 : Render_Glyph( RAS_VAR
) );
3358 const FT_Raster_Funcs ft_standard_raster
=
3360 FT_GLYPH_FORMAT_OUTLINE
,
3361 (FT_Raster_New_Func
) ft_black_new
,
3362 (FT_Raster_Reset_Func
) ft_black_reset
,
3363 (FT_Raster_Set_Mode_Func
)ft_black_set_mode
,
3364 (FT_Raster_Render_Func
) ft_black_render
,
3365 (FT_Raster_Done_Func
) ft_black_done