1 /****************************************************************************
2 *
3 * ftraster.c
4 *
5 * The FreeType glyph rasterizer (body).
6 *
7 * Copyright (C) 1996-2019 by
8 * David Turner, Robert Wilhelm, and Werner Lemberg.
9 *
10 * This file is part of the FreeType project, and may only be used,
11 * modified, and distributed under the terms of the FreeType project
12 * license, LICENSE.TXT. By continuing to use, modify, or distribute
13 * this file you indicate that you have read the license and
14 * understand and accept it fully.
15 *
16 */
17
18 /**************************************************************************
19 *
20 * This file can be compiled without the rest of the FreeType engine, by
21 * defining the STANDALONE_ macro when compiling it. You also need to
22 * put the files `ftimage.h' and `ftmisc.h' into the $(incdir)
23 * directory. Typically, you should do something like
24 *
25 * - copy `src/raster/ftraster.c' (this file) to your current directory
26 *
27 * - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h' to your
28 * current directory
29 *
30 * - compile `ftraster' with the STANDALONE_ macro defined, as in
31 *
32 * cc -c -DSTANDALONE_ ftraster.c
33 *
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'.
37 *
38 * See the comments and documentation in the file `ftimage.h' for more
39 * details on how the raster works.
40 *
41 */
42
43
44 /**************************************************************************
45 *
46 * This is a rewrite of the FreeType 1.x scan-line converter
47 *
48 */
49
50 #ifdef STANDALONE_
51
52 /* The size in bytes of the render pool used by the scan-line converter */
53 /* to do all of its work. */
54 #define FT_RENDER_POOL_SIZE 16384L
55
56 #define FT_CONFIG_STANDARD_LIBRARY_H <stdlib.h>
57
58 #include <string.h> /* for memset */
59
60 #include "ftmisc.h"
61 #include "ftimage.h"
62
63 #else /* !STANDALONE_ */
64
65 #include <ft2build.h>
66 #include "ftraster.h"
67 #include FT_INTERNAL_CALC_H /* for FT_MulDiv and FT_MulDiv_No_Round */
68 #include FT_OUTLINE_H /* for FT_Outline_Get_CBox */
69
70 #endif /* !STANDALONE_ */
71
72
73 /**************************************************************************
74 *
75 * A simple technical note on how the raster works
76 * -----------------------------------------------
77 *
78 * Converting an outline into a bitmap is achieved in several steps:
79 *
80 * 1 - Decomposing the outline into successive `profiles'. Each
81 * profile is simply an array of scanline intersections on a given
82 * dimension. A profile's main attributes are
83 *
84 * o its scanline position boundaries, i.e. `Ymin' and `Ymax'
85 *
86 * o an array of intersection coordinates for each scanline
87 * between `Ymin' and `Ymax'
88 *
89 * o a direction, indicating whether it was built going `up' or
90 * `down', as this is very important for filling rules
91 *
92 * o its drop-out mode
93 *
94 * 2 - Sweeping the target map's scanlines in order to compute segment
95 * `spans' which are then filled. Additionally, this pass
96 * performs drop-out control.
97 *
98 * The outline data is parsed during step 1 only. The profiles are
99 * built from the bottom of the render pool, used as a stack. The
100 * following graphics shows the profile list under construction:
101 *
102 * __________________________________________________________ _ _
103 * | | | | |
104 * | profile | coordinates for | profile | coordinates for |-->
105 * | 1 | profile 1 | 2 | profile 2 |-->
106 * |_________|_________________|_________|_________________|__ _ _
107 *
108 * ^ ^
109 * | |
110 * start of render pool top
111 *
112 * The top of the profile stack is kept in the `top' variable.
113 *
114 * As you can see, a profile record is pushed on top of the render
115 * pool, which is then followed by its coordinates/intersections. If
116 * a change of direction is detected in the outline, a new profile is
117 * generated until the end of the outline.
118 *
119 * Note that when all profiles have been generated, the function
120 * Finalize_Profile_Table() is used to record, for each profile, its
121 * bottom-most scanline as well as the scanline above its upmost
122 * boundary. These positions are called `y-turns' because they (sort
123 * of) correspond to local extrema. They are stored in a sorted list
124 * built from the top of the render pool as a downwards stack:
125 *
126 * _ _ _______________________________________
127 * | |
128 * <--| sorted list of |
129 * <--| extrema scanlines |
130 * _ _ __________________|____________________|
131 *
132 * ^ ^
133 * | |
134 * maxBuff sizeBuff = end of pool
135 *
136 * This list is later used during the sweep phase in order to
137 * optimize performance (see technical note on the sweep below).
138 *
139 * Of course, the raster detects whether the two stacks collide and
140 * handles the situation properly.
141 *
142 */
143
144
145 /*************************************************************************/
146 /*************************************************************************/
147 /** **/
148 /** CONFIGURATION MACROS **/
149 /** **/
150 /*************************************************************************/
151 /*************************************************************************/
152
153 /* define DEBUG_RASTER if you want to compile a debugging version */
154 /* #define DEBUG_RASTER */
155
156
157 /*************************************************************************/
158 /*************************************************************************/
159 /** **/
160 /** OTHER MACROS (do not change) **/
161 /** **/
162 /*************************************************************************/
163 /*************************************************************************/
164
165 /**************************************************************************
166 *
167 * The macro FT_COMPONENT is used in trace mode. It is an implicit
168 * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
169 * messages during execution.
170 */
171 #undef FT_COMPONENT
172 #define FT_COMPONENT raster
173
174
175 #ifdef STANDALONE_
176
177 /* Auxiliary macros for token concatenation. */
178 #define FT_ERR_XCAT( x, y ) x ## y
179 #define FT_ERR_CAT( x, y ) FT_ERR_XCAT( x, y )
180
181 /* This macro is used to indicate that a function parameter is unused. */
182 /* Its purpose is simply to reduce compiler warnings. Note also that */
183 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
184 /* ANSI compilers (e.g. LCC). */
185 #define FT_UNUSED( x ) (x) = (x)
186
187 /* Disable the tracing mechanism for simplicity -- developers can */
188 /* activate it easily by redefining these macros. */
189 #ifndef FT_ERROR
190 #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */
191 #endif
192
193 #ifndef FT_TRACE
194 #define FT_TRACE( x ) do { } while ( 0 ) /* nothing */
195 #define FT_TRACE1( x ) do { } while ( 0 ) /* nothing */
196 #define FT_TRACE6( x ) do { } while ( 0 ) /* nothing */
197 #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */
198 #endif
199
200 #ifndef FT_THROW
201 #define FT_THROW( e ) FT_ERR_CAT( Raster_Err_, e )
202 #endif
203
204 #define Raster_Err_None 0
205 #define Raster_Err_Not_Ini -1
206 #define Raster_Err_Overflow -2
207 #define Raster_Err_Neg_Height -3
208 #define Raster_Err_Invalid -4
209 #define Raster_Err_Unsupported -5
210
211 #define ft_memset memset
212
213 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, raster_new_, \
214 raster_reset_, raster_set_mode_, \
215 raster_render_, raster_done_ ) \
216 const FT_Raster_Funcs class_ = \
217 { \
218 glyph_format_, \
219 raster_new_, \
220 raster_reset_, \
221 raster_set_mode_, \
222 raster_render_, \
223 raster_done_ \
224 };
225
226 #else /* !STANDALONE_ */
227
228
229 #include FT_INTERNAL_OBJECTS_H
230 #include FT_INTERNAL_DEBUG_H /* for FT_TRACE, FT_ERROR, and FT_THROW */
231
232 #include "rasterrs.h"
233
234 #define Raster_Err_None FT_Err_Ok
235 #define Raster_Err_Not_Ini Raster_Err_Raster_Uninitialized
236 #define Raster_Err_Overflow Raster_Err_Raster_Overflow
237 #define Raster_Err_Neg_Height Raster_Err_Raster_Negative_Height
238 #define Raster_Err_Invalid Raster_Err_Invalid_Outline
239 #define Raster_Err_Unsupported Raster_Err_Cannot_Render_Glyph
240
241
242 #endif /* !STANDALONE_ */
243
244
245 #ifndef FT_MEM_SET
246 #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c )
247 #endif
248
249 #ifndef FT_MEM_ZERO
250 #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count )
251 #endif
252
253 #ifndef FT_ZERO
254 #define FT_ZERO( p ) FT_MEM_ZERO( p, sizeof ( *(p) ) )
255 #endif
256
257 /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is */
258 /* typically a small value and the result of a*b is known to fit into */
259 /* 32 bits. */
260 #define FMulDiv( a, b, c ) ( (a) * (b) / (c) )
261
262 /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */
263 /* for clipping computations. It simply uses the FT_MulDiv() function */
264 /* defined in `ftcalc.h'. */
265 #define SMulDiv FT_MulDiv
266 #define SMulDiv_No_Round FT_MulDiv_No_Round
267
268 /* The rasterizer is a very general purpose component; please leave */
269 /* the following redefinitions there (you never know your target */
270 /* environment). */
271
272 #ifndef TRUE
273 #define TRUE 1
274 #endif
275
276 #ifndef FALSE
277 #define FALSE 0
278 #endif
279
280 #ifndef NULL
281 #define NULL (void*)0
282 #endif
283
284 #ifndef SUCCESS
285 #define SUCCESS 0
286 #endif
287
288 #ifndef FAILURE
289 #define FAILURE 1
290 #endif
291
292
293 #define MaxBezier 32 /* The maximum number of stacked Bezier curves. */
294 /* Setting this constant to more than 32 is a */
295 /* pure waste of space. */
296
297 #define Pixel_Bits 6 /* fractional bits of *input* coordinates */
298
299
300 /*************************************************************************/
301 /*************************************************************************/
302 /** **/
303 /** SIMPLE TYPE DECLARATIONS **/
304 /** **/
305 /*************************************************************************/
306 /*************************************************************************/
307
308 typedef int Int;
309 typedef unsigned int UInt;
310 typedef short Short;
311 typedef unsigned short UShort, *PUShort;
312 typedef long Long, *PLong;
313 typedef unsigned long ULong;
314
315 typedef unsigned char Byte, *PByte;
316 typedef char Bool;
317
318
319 typedef union Alignment_
320 {
321 Long l;
322 void* p;
323 void (*f)(void);
324
325 } Alignment, *PAlignment;
326
327
328 typedef struct TPoint_
329 {
330 Long x;
331 Long y;
332
333 } TPoint;
334
335
336 /* values for the `flags' bit field */
337 #define Flow_Up 0x08U
338 #define Overshoot_Top 0x10U
339 #define Overshoot_Bottom 0x20U
340
341
342 /* States of each line, arc, and profile */
343 typedef enum TStates_
344 {
345 Unknown_State,
346 Ascending_State,
347 Descending_State,
348 Flat_State
349
350 } TStates;
351
352
353 typedef struct TProfile_ TProfile;
354 typedef TProfile* PProfile;
355
356 struct TProfile_
357 {
358 FT_F26Dot6 X; /* current coordinate during sweep */
359 PProfile link; /* link to next profile (various purposes) */
360 PLong offset; /* start of profile's data in render pool */
361 UShort flags; /* Bit 0-2: drop-out mode */
362 /* Bit 3: profile orientation (up/down) */
363 /* Bit 4: is top profile? */
364 /* Bit 5: is bottom profile? */
365 Long height; /* profile's height in scanlines */
366 Long start; /* profile's starting scanline */
367
368 Int countL; /* number of lines to step before this */
369 /* profile becomes drawable */
370
371 PProfile next; /* next profile in same contour, used */
372 /* during drop-out control */
373 };
374
375 typedef PProfile TProfileList;
376 typedef PProfile* PProfileList;
377
378
379 /* Simple record used to implement a stack of bands, required */
380 /* by the sub-banding mechanism */
381 typedef struct black_TBand_
382 {
383 Short y_min; /* band's minimum */
384 Short y_max; /* band's maximum */
385
386 } black_TBand;
387
388
389 #define AlignProfileSize \
390 ( ( sizeof ( TProfile ) + sizeof ( Alignment ) - 1 ) / sizeof ( Long ) )
391
392
393 #undef RAS_ARG
394 #undef RAS_ARGS
395 #undef RAS_VAR
396 #undef RAS_VARS
397
398 #ifdef FT_STATIC_RASTER
399
400
401 #define RAS_ARGS /* void */
402 #define RAS_ARG /* void */
403
404 #define RAS_VARS /* void */
405 #define RAS_VAR /* void */
406
407 #define FT_UNUSED_RASTER do { } while ( 0 )
408
409
410 #else /* !FT_STATIC_RASTER */
411
412
413 #define RAS_ARGS black_PWorker worker,
414 #define RAS_ARG black_PWorker worker
415
416 #define RAS_VARS worker,
417 #define RAS_VAR worker
418
419 #define FT_UNUSED_RASTER FT_UNUSED( worker )
420
421
422 #endif /* !FT_STATIC_RASTER */
423
424
425 typedef struct black_TWorker_ black_TWorker, *black_PWorker;
426
427
428 /* prototypes used for sweep function dispatch */
429 typedef void
430 Function_Sweep_Init( RAS_ARGS Short* min,
431 Short* max );
432
433 typedef void
434 Function_Sweep_Span( RAS_ARGS Short y,
435 FT_F26Dot6 x1,
436 FT_F26Dot6 x2,
437 PProfile left,
438 PProfile right );
439
440 typedef void
441 Function_Sweep_Step( RAS_ARG );
442
443
444 /* NOTE: These operations are only valid on 2's complement processors */
445 #undef FLOOR
446 #undef CEILING
447 #undef TRUNC
448 #undef SCALED
449
450 #define FLOOR( x ) ( (x) & -ras.precision )
451 #define CEILING( x ) ( ( (x) + ras.precision - 1 ) & -ras.precision )
452 #define TRUNC( x ) ( (Long)(x) >> ras.precision_bits )
453 #define FRAC( x ) ( (x) & ( ras.precision - 1 ) )
454
455 /* scale and shift grid to pixel centers */
456 #define SCALED( x ) ( (x) * ras.precision_scale - ras.precision_half )
457
458 #define IS_BOTTOM_OVERSHOOT( x ) \
459 (Bool)( CEILING( x ) - x >= ras.precision_half )
460 #define IS_TOP_OVERSHOOT( x ) \
461 (Bool)( x - FLOOR( x ) >= ras.precision_half )
462
463 #if FT_RENDER_POOL_SIZE > 2048
464 #define FT_MAX_BLACK_POOL ( FT_RENDER_POOL_SIZE / sizeof ( Long ) )
465 #else
466 #define FT_MAX_BLACK_POOL ( 2048 / sizeof ( Long ) )
467 #endif
468
469 /* The most used variables are positioned at the top of the structure. */
470 /* Thus, their offset can be coded with less opcodes, resulting in a */
471 /* smaller executable. */
472
473 struct black_TWorker_
474 {
475 Int precision_bits; /* precision related variables */
476 Int precision;
477 Int precision_half;
478 Int precision_scale;
479 Int precision_step;
480 Int precision_jitter;
481
482 PLong buff; /* The profiles buffer */
483 PLong sizeBuff; /* Render pool size */
484 PLong maxBuff; /* Profiles buffer size */
485 PLong top; /* Current cursor in buffer */
486
487 FT_Error error;
488
489 Int numTurns; /* number of Y-turns in outline */
490
491 TPoint* arc; /* current Bezier arc pointer */
492
493 UShort bWidth; /* target bitmap width */
494 PByte bOrigin; /* target bitmap bottom-left origin */
495
496 Long lastX, lastY;
497 Long minY, maxY;
498
499 UShort num_Profs; /* current number of profiles */
500
501 Bool fresh; /* signals a fresh new profile which */
502 /* `start' field must be completed */
503 Bool joint; /* signals that the last arc ended */
504 /* exactly on a scanline. Allows */
505 /* removal of doublets */
506 PProfile cProfile; /* current profile */
507 PProfile fProfile; /* head of linked list of profiles */
508 PProfile gProfile; /* contour's first profile in case */
509 /* of impact */
510
511 TStates state; /* rendering state */
512
513 FT_Bitmap target; /* description of target bit/pixmap */
514 FT_Outline outline;
515
516 Long traceOfs; /* current offset in target bitmap */
517 Short traceIncr; /* sweep's increment in target bitmap */
518
519 /* dispatch variables */
520
521 Function_Sweep_Init* Proc_Sweep_Init;
522 Function_Sweep_Span* Proc_Sweep_Span;
523 Function_Sweep_Span* Proc_Sweep_Drop;
524 Function_Sweep_Step* Proc_Sweep_Step;
525
526 Byte dropOutControl; /* current drop_out control method */
527
528 Bool second_pass; /* indicates whether a horizontal pass */
529 /* should be performed to control */
530 /* drop-out accurately when calling */
531 /* Render_Glyph. */
532
533 TPoint arcs[3 * MaxBezier + 1]; /* The Bezier stack */
534
535 black_TBand band_stack[16]; /* band stack used for sub-banding */
536 Int band_top; /* band stack top */
537
538 };
539
540
541 typedef struct black_TRaster_
542 {
543 void* memory;
544
545 } black_TRaster, *black_PRaster;
546
547 #ifdef FT_STATIC_RASTER
548
549 static black_TWorker cur_ras;
550 #define ras cur_ras
551
552 #else /* !FT_STATIC_RASTER */
553
554 #define ras (*worker)
555
556 #endif /* !FT_STATIC_RASTER */
557
558
559 /*************************************************************************/
560 /*************************************************************************/
561 /** **/
562 /** PROFILES COMPUTATION **/
563 /** **/
564 /*************************************************************************/
565 /*************************************************************************/
566
567
568 /**************************************************************************
569 *
570 * @Function:
571 * Set_High_Precision
572 *
573 * @Description:
574 * Set precision variables according to param flag.
575 *
576 * @Input:
577 * High ::
578 * Set to True for high precision (typically for ppem < 24),
579 * false otherwise.
580 */
581 static void
582 Set_High_Precision( RAS_ARGS Int High )
583 {
584 /*
585 * `precision_step' is used in `Bezier_Up' to decide when to split a
586 * given y-monotonous Bezier arc that crosses a scanline before
587 * approximating it as a straight segment. The default value of 32 (for
588 * low accuracy) corresponds to
589 *
590 * 32 / 64 == 0.5 pixels,
591 *
592 * while for the high accuracy case we have
593 *
594 * 256 / (1 << 12) = 0.0625 pixels.
595 *
596 * `precision_jitter' is an epsilon threshold used in
597 * `Vertical_Sweep_Span' to deal with small imperfections in the Bezier
598 * decomposition (after all, we are working with approximations only);
599 * it avoids switching on additional pixels which would cause artifacts
600 * otherwise.
601 *
602 * The value of `precision_jitter' has been determined heuristically.
603 *
604 */
605
606 if ( High )
607 {
608 ras.precision_bits = 12;
609 ras.precision_step = 256;
610 ras.precision_jitter = 30;
611 }
612 else
613 {
614 ras.precision_bits = 6;
615 ras.precision_step = 32;
616 ras.precision_jitter = 2;
617 }
618
619 FT_TRACE6(( "Set_High_Precision(%s)\n", High ? "true" : "false" ));
620
621 ras.precision = 1 << ras.precision_bits;
622 ras.precision_half = ras.precision >> 1;
623 ras.precision_scale = ras.precision >> Pixel_Bits;
624 }
625
626
627 /**************************************************************************
628 *
629 * @Function:
630 * New_Profile
631 *
632 * @Description:
633 * Create a new profile in the render pool.
634 *
635 * @Input:
636 * aState ::
637 * The state/orientation of the new profile.
638 *
639 * overshoot ::
640 * Whether the profile's unrounded start position
641 * differs by at least a half pixel.
642 *
643 * @Return:
644 * SUCCESS on success. FAILURE in case of overflow or of incoherent
645 * profile.
646 */
647 static Bool
648 New_Profile( RAS_ARGS TStates aState,
649 Bool overshoot )
650 {
651 if ( !ras.fProfile )
652 {
653 ras.cProfile = (PProfile)ras.top;
654 ras.fProfile = ras.cProfile;
655 ras.top += AlignProfileSize;
656 }
657
658 if ( ras.top >= ras.maxBuff )
659 {
660 ras.error = FT_THROW( Overflow );
661 return FAILURE;
662 }
663
664 ras.cProfile->flags = 0;
665 ras.cProfile->start = 0;
666 ras.cProfile->height = 0;
667 ras.cProfile->offset = ras.top;
668 ras.cProfile->link = (PProfile)0;
669 ras.cProfile->next = (PProfile)0;
670 ras.cProfile->flags = ras.dropOutControl;
671
672 switch ( aState )
673 {
674 case Ascending_State:
675 ras.cProfile->flags |= Flow_Up;
676 if ( overshoot )
677 ras.cProfile->flags |= Overshoot_Bottom;
678
679 FT_TRACE6(( " new ascending profile = %p\n", ras.cProfile ));
680 break;
681
682 case Descending_State:
683 if ( overshoot )
684 ras.cProfile->flags |= Overshoot_Top;
685 FT_TRACE6(( " new descending profile = %p\n", ras.cProfile ));
686 break;
687
688 default:
689 FT_ERROR(( "New_Profile: invalid profile direction\n" ));
690 ras.error = FT_THROW( Invalid );
691 return FAILURE;
692 }
693
694 if ( !ras.gProfile )
695 ras.gProfile = ras.cProfile;
696
697 ras.state = aState;
698 ras.fresh = TRUE;
699 ras.joint = FALSE;
700
701 return SUCCESS;
702 }
703
704
705 /**************************************************************************
706 *
707 * @Function:
708 * End_Profile
709 *
710 * @Description:
711 * Finalize the current profile.
712 *
713 * @Input:
714 * overshoot ::
715 * Whether the profile's unrounded end position differs
716 * by at least a half pixel.
717 *
718 * @Return:
719 * SUCCESS on success. FAILURE in case of overflow or incoherency.
720 */
721 static Bool
722 End_Profile( RAS_ARGS Bool overshoot )
723 {
724 Long h;
725
726
727 h = (Long)( ras.top - ras.cProfile->offset );
728
729 if ( h < 0 )
730 {
731 FT_ERROR(( "End_Profile: negative height encountered\n" ));
732 ras.error = FT_THROW( Neg_Height );
733 return FAILURE;
734 }
735
736 if ( h > 0 )
737 {
738 PProfile oldProfile;
739
740
741 FT_TRACE6(( " ending profile %p, start = %ld, height = %ld\n",
742 ras.cProfile, ras.cProfile->start, h ));
743
744 ras.cProfile->height = h;
745 if ( overshoot )
746 {
747 if ( ras.cProfile->flags & Flow_Up )
748 ras.cProfile->flags |= Overshoot_Top;
749 else
750 ras.cProfile->flags |= Overshoot_Bottom;
751 }
752
753 oldProfile = ras.cProfile;
754 ras.cProfile = (PProfile)ras.top;
755
756 ras.top += AlignProfileSize;
757
758 ras.cProfile->height = 0;
759 ras.cProfile->offset = ras.top;
760
761 oldProfile->next = ras.cProfile;
762 ras.num_Profs++;
763 }
764
765 if ( ras.top >= ras.maxBuff )
766 {
767 FT_TRACE1(( "overflow in End_Profile\n" ));
768 ras.error = FT_THROW( Overflow );
769 return FAILURE;
770 }
771
772 ras.joint = FALSE;
773
774 return SUCCESS;
775 }
776
777
778 /**************************************************************************
779 *
780 * @Function:
781 * Insert_Y_Turn
782 *
783 * @Description:
784 * Insert a salient into the sorted list placed on top of the render
785 * pool.
786 *
787 * @Input:
788 * New y scanline position.
789 *
790 * @Return:
791 * SUCCESS on success. FAILURE in case of overflow.
792 */
793 static Bool
794 Insert_Y_Turn( RAS_ARGS Int y )
795 {
796 PLong y_turns;
797 Int n;
798
799
800 n = ras.numTurns - 1;
801 y_turns = ras.sizeBuff - ras.numTurns;
802
803 /* look for first y value that is <= */
804 while ( n >= 0 && y < y_turns[n] )
805 n--;
806
807 /* if it is <, simply insert it, ignore if == */
808 if ( n >= 0 && y > y_turns[n] )
809 do
810 {
811 Int y2 = (Int)y_turns[n];
812
813
814 y_turns[n] = y;
815 y = y2;
816 } while ( --n >= 0 );
817
818 if ( n < 0 )
819 {
820 ras.maxBuff--;
821 if ( ras.maxBuff <= ras.top )
822 {
823 ras.error = FT_THROW( Overflow );
824 return FAILURE;
825 }
826 ras.numTurns++;
827 ras.sizeBuff[-ras.numTurns] = y;
828 }
829
830 return SUCCESS;
831 }
832
833
834 /**************************************************************************
835 *
836 * @Function:
837 * Finalize_Profile_Table
838 *
839 * @Description:
840 * Adjust all links in the profiles list.
841 *
842 * @Return:
843 * SUCCESS on success. FAILURE in case of overflow.
844 */
845 static Bool
846 Finalize_Profile_Table( RAS_ARG )
847 {
848 UShort n;
849 PProfile p;
850
851
852 n = ras.num_Profs;
853 p = ras.fProfile;
854
855 if ( n > 1 && p )
856 {
857 do
858 {
859 Int bottom, top;
860
861
862 if ( n > 1 )
863 p->link = (PProfile)( p->offset + p->height );
864 else
865 p->link = NULL;
866
867 if ( p->flags & Flow_Up )
868 {
869 bottom = (Int)p->start;
870 top = (Int)( p->start + p->height - 1 );
871 }
872 else
873 {
874 bottom = (Int)( p->start - p->height + 1 );
875 top = (Int)p->start;
876 p->start = bottom;
877 p->offset += p->height - 1;
878 }
879
880 if ( Insert_Y_Turn( RAS_VARS bottom ) ||
881 Insert_Y_Turn( RAS_VARS top + 1 ) )
882 return FAILURE;
883
884 p = p->link;
885 } while ( --n );
886 }
887 else
888 ras.fProfile = NULL;
889
890 return SUCCESS;
891 }
892
893
894 /**************************************************************************
895 *
896 * @Function:
897 * Split_Conic
898 *
899 * @Description:
900 * Subdivide one conic Bezier into two joint sub-arcs in the Bezier
901 * stack.
902 *
903 * @Input:
904 * None (subdivided Bezier is taken from the top of the stack).
905 *
906 * @Note:
907 * This routine is the `beef' of this component. It is _the_ inner
908 * loop that should be optimized to hell to get the best performance.
909 */
910 static void
911 Split_Conic( TPoint* base )
912 {
913 Long a, b;
914
915
916 base[4].x = base[2].x;
917 b = base[1].x;
918 a = base[3].x = ( base[2].x + b ) / 2;
919 b = base[1].x = ( base[0].x + b ) / 2;
920 base[2].x = ( a + b ) / 2;
921
922 base[4].y = base[2].y;
923 b = base[1].y;
924 a = base[3].y = ( base[2].y + b ) / 2;
925 b = base[1].y = ( base[0].y + b ) / 2;
926 base[2].y = ( a + b ) / 2;
927
928 /* hand optimized. gcc doesn't seem to be too good at common */
929 /* expression substitution and instruction scheduling ;-) */
930 }
931
932
933 /**************************************************************************
934 *
935 * @Function:
936 * Split_Cubic
937 *
938 * @Description:
939 * Subdivide a third-order Bezier arc into two joint sub-arcs in the
940 * Bezier stack.
941 *
942 * @Note:
943 * This routine is the `beef' of the component. It is one of _the_
944 * inner loops that should be optimized like hell to get the best
945 * performance.
946 */
947 static void
948 Split_Cubic( TPoint* base )
949 {
950 Long a, b, c, d;
951
952
953 base[6].x = base[3].x;
954 c = base[1].x;
955 d = base[2].x;
956 base[1].x = a = ( base[0].x + c + 1 ) >> 1;
957 base[5].x = b = ( base[3].x + d + 1 ) >> 1;
958 c = ( c + d + 1 ) >> 1;
959 base[2].x = a = ( a + c + 1 ) >> 1;
960 base[4].x = b = ( b + c + 1 ) >> 1;
961 base[3].x = ( a + b + 1 ) >> 1;
962
963 base[6].y = base[3].y;
964 c = base[1].y;
965 d = base[2].y;
966 base[1].y = a = ( base[0].y + c + 1 ) >> 1;
967 base[5].y = b = ( base[3].y + d + 1 ) >> 1;
968 c = ( c + d + 1 ) >> 1;
969 base[2].y = a = ( a + c + 1 ) >> 1;
970 base[4].y = b = ( b + c + 1 ) >> 1;
971 base[3].y = ( a + b + 1 ) >> 1;
972 }
973
974
975 /**************************************************************************
976 *
977 * @Function:
978 * Line_Up
979 *
980 * @Description:
981 * Compute the x-coordinates of an ascending line segment and store
982 * them in the render pool.
983 *
984 * @Input:
985 * x1 ::
986 * The x-coordinate of the segment's start point.
987 *
988 * y1 ::
989 * The y-coordinate of the segment's start point.
990 *
991 * x2 ::
992 * The x-coordinate of the segment's end point.
993 *
994 * y2 ::
995 * The y-coordinate of the segment's end point.
996 *
997 * miny ::
998 * A lower vertical clipping bound value.
999 *
1000 * maxy ::
1001 * An upper vertical clipping bound value.
1002 *
1003 * @Return:
1004 * SUCCESS on success, FAILURE on render pool overflow.
1005 */
1006 static Bool
1007 Line_Up( RAS_ARGS Long x1,
1008 Long y1,
1009 Long x2,
1010 Long y2,
1011 Long miny,
1012 Long maxy )
1013 {
1014 Long Dx, Dy;
1015 Int e1, e2, f1, f2, size; /* XXX: is `Short' sufficient? */
1016 Long Ix, Rx, Ax;
1017
1018 PLong top;
1019
1020
1021 Dx = x2 - x1;
1022 Dy = y2 - y1;
1023
1024 if ( Dy <= 0 || y2 < miny || y1 > maxy )
1025 return SUCCESS;
1026
1027 if ( y1 < miny )
1028 {
1029 /* Take care: miny-y1 can be a very large value; we use */
1030 /* a slow MulDiv function to avoid clipping bugs */
1031 x1 += SMulDiv( Dx, miny - y1, Dy );
1032 e1 = (Int)TRUNC( miny );
1033 f1 = 0;
1034 }
1035 else
1036 {
1037 e1 = (Int)TRUNC( y1 );
1038 f1 = (Int)FRAC( y1 );
1039 }
1040
1041 if ( y2 > maxy )
1042 {
1043 /* x2 += FMulDiv( Dx, maxy - y2, Dy ); UNNECESSARY */
1044 e2 = (Int)TRUNC( maxy );
1045 f2 = 0;
1046 }
1047 else
1048 {
1049 e2 = (Int)TRUNC( y2 );
1050 f2 = (Int)FRAC( y2 );
1051 }
1052
1053 if ( f1 > 0 )
1054 {
1055 if ( e1 == e2 )
1056 return SUCCESS;
1057 else
1058 {
1059 x1 += SMulDiv( Dx, ras.precision - f1, Dy );
1060 e1 += 1;
1061 }
1062 }
1063 else
1064 if ( ras.joint )
1065 {
1066 ras.top--;
1067 ras.joint = FALSE;
1068 }
1069
1070 ras.joint = (char)( f2 == 0 );
1071
1072 if ( ras.fresh )
1073 {
1074 ras.cProfile->start = e1;
1075 ras.fresh = FALSE;
1076 }
1077
1078 size = e2 - e1 + 1;
1079 if ( ras.top + size >= ras.maxBuff )
1080 {
1081 ras.error = FT_THROW( Overflow );
1082 return FAILURE;
1083 }
1084
1085 if ( Dx > 0 )
1086 {
1087 Ix = SMulDiv_No_Round( ras.precision, Dx, Dy );
1088 Rx = ( ras.precision * Dx ) % Dy;
1089 Dx = 1;
1090 }
1091 else
1092 {
1093 Ix = -SMulDiv_No_Round( ras.precision, -Dx, Dy );
1094 Rx = ( ras.precision * -Dx ) % Dy;
1095 Dx = -1;
1096 }
1097
1098 Ax = -Dy;
1099 top = ras.top;
1100
1101 while ( size > 0 )
1102 {
1103 *top++ = x1;
1104
1105 x1 += Ix;
1106 Ax += Rx;
1107 if ( Ax >= 0 )
1108 {
1109 Ax -= Dy;
1110 x1 += Dx;
1111 }
1112 size--;
1113 }
1114
1115 ras.top = top;
1116 return SUCCESS;
1117 }
1118
1119
1120 /**************************************************************************
1121 *
1122 * @Function:
1123 * Line_Down
1124 *
1125 * @Description:
1126 * Compute the x-coordinates of an descending line segment and store
1127 * them in the render pool.
1128 *
1129 * @Input:
1130 * x1 ::
1131 * The x-coordinate of the segment's start point.
1132 *
1133 * y1 ::
1134 * The y-coordinate of the segment's start point.
1135 *
1136 * x2 ::
1137 * The x-coordinate of the segment's end point.
1138 *
1139 * y2 ::
1140 * The y-coordinate of the segment's end point.
1141 *
1142 * miny ::
1143 * A lower vertical clipping bound value.
1144 *
1145 * maxy ::
1146 * An upper vertical clipping bound value.
1147 *
1148 * @Return:
1149 * SUCCESS on success, FAILURE on render pool overflow.
1150 */
1151 static Bool
1152 Line_Down( RAS_ARGS Long x1,
1153 Long y1,
1154 Long x2,
1155 Long y2,
1156 Long miny,
1157 Long maxy )
1158 {
1159 Bool result, fresh;
1160
1161
1162 fresh = ras.fresh;
1163
1164 result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny );
1165
1166 if ( fresh && !ras.fresh )
1167 ras.cProfile->start = -ras.cProfile->start;
1168
1169 return result;
1170 }
1171
1172
1173 /* A function type describing the functions used to split Bezier arcs */
1174 typedef void (*TSplitter)( TPoint* base );
1175
1176
1177 /**************************************************************************
1178 *
1179 * @Function:
1180 * Bezier_Up
1181 *
1182 * @Description:
1183 * Compute the x-coordinates of an ascending Bezier arc and store
1184 * them in the render pool.
1185 *
1186 * @Input:
1187 * degree ::
1188 * The degree of the Bezier arc (either 2 or 3).
1189 *
1190 * splitter ::
1191 * The function to split Bezier arcs.
1192 *
1193 * miny ::
1194 * A lower vertical clipping bound value.
1195 *
1196 * maxy ::
1197 * An upper vertical clipping bound value.
1198 *
1199 * @Return:
1200 * SUCCESS on success, FAILURE on render pool overflow.
1201 */
1202 static Bool
1203 Bezier_Up( RAS_ARGS Int degree,
1204 TSplitter splitter,
1205 Long miny,
1206 Long maxy )
1207 {
1208 Long y1, y2, e, e2, e0;
1209 Short f1;
1210
1211 TPoint* arc;
1212 TPoint* start_arc;
1213
1214 PLong top;
1215
1216
1217 arc = ras.arc;
1218 y1 = arc[degree].y;
1219 y2 = arc[0].y;
1220 top = ras.top;
1221
1222 if ( y2 < miny || y1 > maxy )
1223 goto Fin;
1224
1225 e2 = FLOOR( y2 );
1226
1227 if ( e2 > maxy )
1228 e2 = maxy;
1229
1230 e0 = miny;
1231
1232 if ( y1 < miny )
1233 e = miny;
1234 else
1235 {
1236 e = CEILING( y1 );
1237 f1 = (Short)( FRAC( y1 ) );
1238 e0 = e;
1239
1240 if ( f1 == 0 )
1241 {
1242 if ( ras.joint )
1243 {
1244 top--;
1245 ras.joint = FALSE;
1246 }
1247
1248 *top++ = arc[degree].x;
1249
1250 e += ras.precision;
1251 }
1252 }
1253
1254 if ( ras.fresh )
1255 {
1256 ras.cProfile->start = TRUNC( e0 );
1257 ras.fresh = FALSE;
1258 }
1259
1260 if ( e2 < e )
1261 goto Fin;
1262
1263 if ( ( top + TRUNC( e2 - e ) + 1 ) >= ras.maxBuff )
1264 {
1265 ras.top = top;
1266 ras.error = FT_THROW( Overflow );
1267 return FAILURE;
1268 }
1269
1270 start_arc = arc;
1271
1272 do
1273 {
1274 ras.joint = FALSE;
1275
1276 y2 = arc[0].y;
1277
1278 if ( y2 > e )
1279 {
1280 y1 = arc[degree].y;
1281 if ( y2 - y1 >= ras.precision_step )
1282 {
1283 splitter( arc );
1284 arc += degree;
1285 }
1286 else
1287 {
1288 *top++ = arc[degree].x + FMulDiv( arc[0].x - arc[degree].x,
1289 e - y1, y2 - y1 );
1290 arc -= degree;
1291 e += ras.precision;
1292 }
1293 }
1294 else
1295 {
1296 if ( y2 == e )
1297 {
1298 ras.joint = TRUE;
1299 *top++ = arc[0].x;
1300
1301 e += ras.precision;
1302 }
1303 arc -= degree;
1304 }
1305 } while ( arc >= start_arc && e <= e2 );
1306
1307 Fin:
1308 ras.top = top;
1309 ras.arc -= degree;
1310 return SUCCESS;
1311 }
1312
1313
1314 /**************************************************************************
1315 *
1316 * @Function:
1317 * Bezier_Down
1318 *
1319 * @Description:
1320 * Compute the x-coordinates of an descending Bezier arc and store
1321 * them in the render pool.
1322 *
1323 * @Input:
1324 * degree ::
1325 * The degree of the Bezier arc (either 2 or 3).
1326 *
1327 * splitter ::
1328 * The function to split Bezier arcs.
1329 *
1330 * miny ::
1331 * A lower vertical clipping bound value.
1332 *
1333 * maxy ::
1334 * An upper vertical clipping bound value.
1335 *
1336 * @Return:
1337 * SUCCESS on success, FAILURE on render pool overflow.
1338 */
1339 static Bool
1340 Bezier_Down( RAS_ARGS Int degree,
1341 TSplitter splitter,
1342 Long miny,
1343 Long maxy )
1344 {
1345 TPoint* arc = ras.arc;
1346 Bool result, fresh;
1347
1348
1349 arc[0].y = -arc[0].y;
1350 arc[1].y = -arc[1].y;
1351 arc[2].y = -arc[2].y;
1352 if ( degree > 2 )
1353 arc[3].y = -arc[3].y;
1354
1355 fresh = ras.fresh;
1356
1357 result = Bezier_Up( RAS_VARS degree, splitter, -maxy, -miny );
1358
1359 if ( fresh && !ras.fresh )
1360 ras.cProfile->start = -ras.cProfile->start;
1361
1362 arc[0].y = -arc[0].y;
1363 return result;
1364 }
1365
1366
1367 /**************************************************************************
1368 *
1369 * @Function:
1370 * Line_To
1371 *
1372 * @Description:
1373 * Inject a new line segment and adjust the Profiles list.
1374 *
1375 * @Input:
1376 * x ::
1377 * The x-coordinate of the segment's end point (its start point
1378 * is stored in `lastX').
1379 *
1380 * y ::
1381 * The y-coordinate of the segment's end point (its start point
1382 * is stored in `lastY').
1383 *
1384 * @Return:
1385 * SUCCESS on success, FAILURE on render pool overflow or incorrect
1386 * profile.
1387 */
1388 static Bool
1389 Line_To( RAS_ARGS Long x,
1390 Long y )
1391 {
1392 /* First, detect a change of direction */
1393
1394 switch ( ras.state )
1395 {
1396 case Unknown_State:
1397 if ( y > ras.lastY )
1398 {
1399 if ( New_Profile( RAS_VARS Ascending_State,
1400 IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1401 return FAILURE;
1402 }
1403 else
1404 {
1405 if ( y < ras.lastY )
1406 if ( New_Profile( RAS_VARS Descending_State,
1407 IS_TOP_OVERSHOOT( ras.lastY ) ) )
1408 return FAILURE;
1409 }
1410 break;
1411
1412 case Ascending_State:
1413 if ( y < ras.lastY )
1414 {
1415 if ( End_Profile( RAS_VARS IS_TOP_OVERSHOOT( ras.lastY ) ) ||
1416 New_Profile( RAS_VARS Descending_State,
1417 IS_TOP_OVERSHOOT( ras.lastY ) ) )
1418 return FAILURE;
1419 }
1420 break;
1421
1422 case Descending_State:
1423 if ( y > ras.lastY )
1424 {
1425 if ( End_Profile( RAS_VARS IS_BOTTOM_OVERSHOOT( ras.lastY ) ) ||
1426 New_Profile( RAS_VARS Ascending_State,
1427 IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1428 return FAILURE;
1429 }
1430 break;
1431
1432 default:
1433 ;
1434 }
1435
1436 /* Then compute the lines */
1437
1438 switch ( ras.state )
1439 {
1440 case Ascending_State:
1441 if ( Line_Up( RAS_VARS ras.lastX, ras.lastY,
1442 x, y, ras.minY, ras.maxY ) )
1443 return FAILURE;
1444 break;
1445
1446 case Descending_State:
1447 if ( Line_Down( RAS_VARS ras.lastX, ras.lastY,
1448 x, y, ras.minY, ras.maxY ) )
1449 return FAILURE;
1450 break;
1451
1452 default:
1453 ;
1454 }
1455
1456 ras.lastX = x;
1457 ras.lastY = y;
1458
1459 return SUCCESS;
1460 }
1461
1462
1463 /**************************************************************************
1464 *
1465 * @Function:
1466 * Conic_To
1467 *
1468 * @Description:
1469 * Inject a new conic arc and adjust the profile list.
1470 *
1471 * @Input:
1472 * cx ::
1473 * The x-coordinate of the arc's new control point.
1474 *
1475 * cy ::
1476 * The y-coordinate of the arc's new control point.
1477 *
1478 * x ::
1479 * The x-coordinate of the arc's end point (its start point is
1480 * stored in `lastX').
1481 *
1482 * y ::
1483 * The y-coordinate of the arc's end point (its start point is
1484 * stored in `lastY').
1485 *
1486 * @Return:
1487 * SUCCESS on success, FAILURE on render pool overflow or incorrect
1488 * profile.
1489 */
1490 static Bool
1491 Conic_To( RAS_ARGS Long cx,
1492 Long cy,
1493 Long x,
1494 Long y )
1495 {
1496 Long y1, y2, y3, x3, ymin, ymax;
1497 TStates state_bez;
1498
1499
1500 ras.arc = ras.arcs;
1501 ras.arc[2].x = ras.lastX;
1502 ras.arc[2].y = ras.lastY;
1503 ras.arc[1].x = cx;
1504 ras.arc[1].y = cy;
1505 ras.arc[0].x = x;
1506 ras.arc[0].y = y;
1507
1508 do
1509 {
1510 y1 = ras.arc[2].y;
1511 y2 = ras.arc[1].y;
1512 y3 = ras.arc[0].y;
1513 x3 = ras.arc[0].x;
1514
1515 /* first, categorize the Bezier arc */
1516
1517 if ( y1 <= y3 )
1518 {
1519 ymin = y1;
1520 ymax = y3;
1521 }
1522 else
1523 {
1524 ymin = y3;
1525 ymax = y1;
1526 }
1527
1528 if ( y2 < ymin || y2 > ymax )
1529 {
1530 /* this arc has no given direction, split it! */
1531 Split_Conic( ras.arc );
1532 ras.arc += 2;
1533 }
1534 else if ( y1 == y3 )
1535 {
1536 /* this arc is flat, ignore it and pop it from the Bezier stack */
1537 ras.arc -= 2;
1538 }
1539 else
1540 {
1541 /* the arc is y-monotonous, either ascending or descending */
1542 /* detect a change of direction */
1543 state_bez = y1 < y3 ? Ascending_State : Descending_State;
1544 if ( ras.state != state_bez )
1545 {
1546 Bool o = ( state_bez == Ascending_State )
1547 ? IS_BOTTOM_OVERSHOOT( y1 )
1548 : IS_TOP_OVERSHOOT( y1 );
1549
1550
1551 /* finalize current profile if any */
1552 if ( ras.state != Unknown_State &&
1553 End_Profile( RAS_VARS o ) )
1554 goto Fail;
1555
1556 /* create a new profile */
1557 if ( New_Profile( RAS_VARS state_bez, o ) )
1558 goto Fail;
1559 }
1560
1561 /* now call the appropriate routine */
1562 if ( state_bez == Ascending_State )
1563 {
1564 if ( Bezier_Up( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1565 goto Fail;
1566 }
1567 else
1568 if ( Bezier_Down( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) )
1569 goto Fail;
1570 }
1571
1572 } while ( ras.arc >= ras.arcs );
1573
1574 ras.lastX = x3;
1575 ras.lastY = y3;
1576
1577 return SUCCESS;
1578
1579 Fail:
1580 return FAILURE;
1581 }
1582
1583
1584 /**************************************************************************
1585 *
1586 * @Function:
1587 * Cubic_To
1588 *
1589 * @Description:
1590 * Inject a new cubic arc and adjust the profile list.
1591 *
1592 * @Input:
1593 * cx1 ::
1594 * The x-coordinate of the arc's first new control point.
1595 *
1596 * cy1 ::
1597 * The y-coordinate of the arc's first new control point.
1598 *
1599 * cx2 ::
1600 * The x-coordinate of the arc's second new control point.
1601 *
1602 * cy2 ::
1603 * The y-coordinate of the arc's second new control point.
1604 *
1605 * x ::
1606 * The x-coordinate of the arc's end point (its start point is
1607 * stored in `lastX').
1608 *
1609 * y ::
1610 * The y-coordinate of the arc's end point (its start point is
1611 * stored in `lastY').
1612 *
1613 * @Return:
1614 * SUCCESS on success, FAILURE on render pool overflow or incorrect
1615 * profile.
1616 */
1617 static Bool
1618 Cubic_To( RAS_ARGS Long cx1,
1619 Long cy1,
1620 Long cx2,
1621 Long cy2,
1622 Long x,
1623 Long y )
1624 {
1625 Long y1, y2, y3, y4, x4, ymin1, ymax1, ymin2, ymax2;
1626 TStates state_bez;
1627
1628
1629 ras.arc = ras.arcs;
1630 ras.arc[3].x = ras.lastX;
1631 ras.arc[3].y = ras.lastY;
1632 ras.arc[2].x = cx1;
1633 ras.arc[2].y = cy1;
1634 ras.arc[1].x = cx2;
1635 ras.arc[1].y = cy2;
1636 ras.arc[0].x = x;
1637 ras.arc[0].y = y;
1638
1639 do
1640 {
1641 y1 = ras.arc[3].y;
1642 y2 = ras.arc[2].y;
1643 y3 = ras.arc[1].y;
1644 y4 = ras.arc[0].y;
1645 x4 = ras.arc[0].x;
1646
1647 /* first, categorize the Bezier arc */
1648
1649 if ( y1 <= y4 )
1650 {
1651 ymin1 = y1;
1652 ymax1 = y4;
1653 }
1654 else
1655 {
1656 ymin1 = y4;
1657 ymax1 = y1;
1658 }
1659
1660 if ( y2 <= y3 )
1661 {
1662 ymin2 = y2;
1663 ymax2 = y3;
1664 }
1665 else
1666 {
1667 ymin2 = y3;
1668 ymax2 = y2;
1669 }
1670
1671 if ( ymin2 < ymin1 || ymax2 > ymax1 )
1672 {
1673 /* this arc has no given direction, split it! */
1674 Split_Cubic( ras.arc );
1675 ras.arc += 3;
1676 }
1677 else if ( y1 == y4 )
1678 {
1679 /* this arc is flat, ignore it and pop it from the Bezier stack */
1680 ras.arc -= 3;
1681 }
1682 else
1683 {
1684 state_bez = ( y1 <= y4 ) ? Ascending_State : Descending_State;
1685
1686 /* detect a change of direction */
1687 if ( ras.state != state_bez )
1688 {
1689 Bool o = ( state_bez == Ascending_State )
1690 ? IS_BOTTOM_OVERSHOOT( y1 )
1691 : IS_TOP_OVERSHOOT( y1 );
1692
1693
1694 /* finalize current profile if any */
1695 if ( ras.state != Unknown_State &&
1696 End_Profile( RAS_VARS o ) )
1697 goto Fail;
1698
1699 if ( New_Profile( RAS_VARS state_bez, o ) )
1700 goto Fail;
1701 }
1702
1703 /* compute intersections */
1704 if ( state_bez == Ascending_State )
1705 {
1706 if ( Bezier_Up( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1707 goto Fail;
1708 }
1709 else
1710 if ( Bezier_Down( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) )
1711 goto Fail;
1712 }
1713
1714 } while ( ras.arc >= ras.arcs );
1715
1716 ras.lastX = x4;
1717 ras.lastY = y4;
1718
1719 return SUCCESS;
1720
1721 Fail:
1722 return FAILURE;
1723 }
1724
1725
1726 #undef SWAP_
1727 #define SWAP_( x, y ) do \
1728 { \
1729 Long swap = x; \
1730 \
1731 \
1732 x = y; \
1733 y = swap; \
1734 } while ( 0 )
1735
1736
1737 /**************************************************************************
1738 *
1739 * @Function:
1740 * Decompose_Curve
1741 *
1742 * @Description:
1743 * Scan the outline arrays in order to emit individual segments and
1744 * Beziers by calling Line_To() and Bezier_To(). It handles all
1745 * weird cases, like when the first point is off the curve, or when
1746 * there are simply no `on' points in the contour!
1747 *
1748 * @Input:
1749 * first ::
1750 * The index of the first point in the contour.
1751 *
1752 * last ::
1753 * The index of the last point in the contour.
1754 *
1755 * flipped ::
1756 * If set, flip the direction of the curve.
1757 *
1758 * @Return:
1759 * SUCCESS on success, FAILURE on error.
1760 */
1761 static Bool
1762 Decompose_Curve( RAS_ARGS UShort first,
1763 UShort last,
1764 Int flipped )
1765 {
1766 FT_Vector v_last;
1767 FT_Vector v_control;
1768 FT_Vector v_start;
1769
1770 FT_Vector* points;
1771 FT_Vector* point;
1772 FT_Vector* limit;
1773 char* tags;
1774
1775 UInt tag; /* current point's state */
1776
1777
1778 points = ras.outline.points;
1779 limit = points + last;
1780
1781 v_start.x = SCALED( points[first].x );
1782 v_start.y = SCALED( points[first].y );
1783 v_last.x = SCALED( points[last].x );
1784 v_last.y = SCALED( points[last].y );
1785
1786 if ( flipped )
1787 {
1788 SWAP_( v_start.x, v_start.y );
1789 SWAP_( v_last.x, v_last.y );
1790 }
1791
1792 v_control = v_start;
1793
1794 point = points + first;
1795 tags = ras.outline.tags + first;
1796
1797 /* set scan mode if necessary */
1798 if ( tags[0] & FT_CURVE_TAG_HAS_SCANMODE )
1799 ras.dropOutControl = (Byte)tags[0] >> 5;
1800
1801 tag = FT_CURVE_TAG( tags[0] );
1802
1803 /* A contour cannot start with a cubic control point! */
1804 if ( tag == FT_CURVE_TAG_CUBIC )
1805 goto Invalid_Outline;
1806
1807 /* check first point to determine origin */
1808 if ( tag == FT_CURVE_TAG_CONIC )
1809 {
1810 /* first point is conic control. Yes, this happens. */
1811 if ( FT_CURVE_TAG( ras.outline.tags[last] ) == FT_CURVE_TAG_ON )
1812 {
1813 /* start at last point if it is on the curve */
1814 v_start = v_last;
1815 limit--;
1816 }
1817 else
1818 {
1819 /* if both first and last points are conic, */
1820 /* start at their middle and record its position */
1821 /* for closure */
1822 v_start.x = ( v_start.x + v_last.x ) / 2;
1823 v_start.y = ( v_start.y + v_last.y ) / 2;
1824
1825 /* v_last = v_start; */
1826 }
1827 point--;
1828 tags--;
1829 }
1830
1831 ras.lastX = v_start.x;
1832 ras.lastY = v_start.y;
1833
1834 while ( point < limit )
1835 {
1836 point++;
1837 tags++;
1838
1839 tag = FT_CURVE_TAG( tags[0] );
1840
1841 switch ( tag )
1842 {
1843 case FT_CURVE_TAG_ON: /* emit a single line_to */
1844 {
1845 Long x, y;
1846
1847
1848 x = SCALED( point->x );
1849 y = SCALED( point->y );
1850 if ( flipped )
1851 SWAP_( x, y );
1852
1853 if ( Line_To( RAS_VARS x, y ) )
1854 goto Fail;
1855 continue;
1856 }
1857
1858 case FT_CURVE_TAG_CONIC: /* consume conic arcs */
1859 v_control.x = SCALED( point[0].x );
1860 v_control.y = SCALED( point[0].y );
1861
1862 if ( flipped )
1863 SWAP_( v_control.x, v_control.y );
1864
1865 Do_Conic:
1866 if ( point < limit )
1867 {
1868 FT_Vector v_middle;
1869 Long x, y;
1870
1871
1872 point++;
1873 tags++;
1874 tag = FT_CURVE_TAG( tags[0] );
1875
1876 x = SCALED( point[0].x );
1877 y = SCALED( point[0].y );
1878
1879 if ( flipped )
1880 SWAP_( x, y );
1881
1882 if ( tag == FT_CURVE_TAG_ON )
1883 {
1884 if ( Conic_To( RAS_VARS v_control.x, v_control.y, x, y ) )
1885 goto Fail;
1886 continue;
1887 }
1888
1889 if ( tag != FT_CURVE_TAG_CONIC )
1890 goto Invalid_Outline;
1891
1892 v_middle.x = ( v_control.x + x ) / 2;
1893 v_middle.y = ( v_control.y + y ) / 2;
1894
1895 if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1896 v_middle.x, v_middle.y ) )
1897 goto Fail;
1898
1899 v_control.x = x;
1900 v_control.y = y;
1901
1902 goto Do_Conic;
1903 }
1904
1905 if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1906 v_start.x, v_start.y ) )
1907 goto Fail;
1908
1909 goto Close;
1910
1911 default: /* FT_CURVE_TAG_CUBIC */
1912 {
1913 Long x1, y1, x2, y2, x3, y3;
1914
1915
1916 if ( point + 1 > limit ||
1917 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1918 goto Invalid_Outline;
1919
1920 point += 2;
1921 tags += 2;
1922
1923 x1 = SCALED( point[-2].x );
1924 y1 = SCALED( point[-2].y );
1925 x2 = SCALED( point[-1].x );
1926 y2 = SCALED( point[-1].y );
1927
1928 if ( flipped )
1929 {
1930 SWAP_( x1, y1 );
1931 SWAP_( x2, y2 );
1932 }
1933
1934 if ( point <= limit )
1935 {
1936 x3 = SCALED( point[0].x );
1937 y3 = SCALED( point[0].y );
1938
1939 if ( flipped )
1940 SWAP_( x3, y3 );
1941
1942 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, x3, y3 ) )
1943 goto Fail;
1944 continue;
1945 }
1946
1947 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, v_start.x, v_start.y ) )
1948 goto Fail;
1949 goto Close;
1950 }
1951 }
1952 }
1953
1954 /* close the contour with a line segment */
1955 if ( Line_To( RAS_VARS v_start.x, v_start.y ) )
1956 goto Fail;
1957
1958 Close:
1959 return SUCCESS;
1960
1961 Invalid_Outline:
1962 ras.error = FT_THROW( Invalid );
1963
1964 Fail:
1965 return FAILURE;
1966 }
1967
1968
1969 /**************************************************************************
1970 *
1971 * @Function:
1972 * Convert_Glyph
1973 *
1974 * @Description:
1975 * Convert a glyph into a series of segments and arcs and make a
1976 * profiles list with them.
1977 *
1978 * @Input:
1979 * flipped ::
1980 * If set, flip the direction of curve.
1981 *
1982 * @Return:
1983 * SUCCESS on success, FAILURE if any error was encountered during
1984 * rendering.
1985 */
1986 static Bool
1987 Convert_Glyph( RAS_ARGS Int flipped )
1988 {
1989 Int i;
1990 UInt start;
1991
1992
1993 ras.fProfile = NULL;
1994 ras.joint = FALSE;
1995 ras.fresh = FALSE;
1996
1997 ras.maxBuff = ras.sizeBuff - AlignProfileSize;
1998
1999 ras.numTurns = 0;
2000
2001 ras.cProfile = (PProfile)ras.top;
2002 ras.cProfile->offset = ras.top;
2003 ras.num_Profs = 0;
2004
2005 start = 0;
2006
2007 for ( i = 0; i < ras.outline.n_contours; i++ )
2008 {
2009 PProfile lastProfile;
2010 Bool o;
2011
2012
2013 ras.state = Unknown_State;
2014 ras.gProfile = NULL;
2015
2016 if ( Decompose_Curve( RAS_VARS (UShort)start,
2017 (UShort)ras.outline.contours[i],
2018 flipped ) )
2019 return FAILURE;
2020
2021 start = (UShort)ras.outline.contours[i] + 1;
2022
2023 /* we must now check whether the extreme arcs join or not */
2024 if ( FRAC( ras.lastY ) == 0 &&
2025 ras.lastY >= ras.minY &&
2026 ras.lastY <= ras.maxY )
2027 if ( ras.gProfile &&
2028 ( ras.gProfile->flags & Flow_Up ) ==
2029 ( ras.cProfile->flags & Flow_Up ) )
2030 ras.top--;
2031 /* Note that ras.gProfile can be nil if the contour was too small */
2032 /* to be drawn. */
2033
2034 lastProfile = ras.cProfile;
2035 if ( ras.top != ras.cProfile->offset &&
2036 ( ras.cProfile->flags & Flow_Up ) )
2037 o = IS_TOP_OVERSHOOT( ras.lastY );
2038 else
2039 o = IS_BOTTOM_OVERSHOOT( ras.lastY );
2040 if ( End_Profile( RAS_VARS o ) )
2041 return FAILURE;
2042
2043 /* close the `next profile in contour' linked list */
2044 if ( ras.gProfile )
2045 lastProfile->next = ras.gProfile;
2046 }
2047
2048 if ( Finalize_Profile_Table( RAS_VAR ) )
2049 return FAILURE;
2050
2051 return (Bool)( ras.top < ras.maxBuff ? SUCCESS : FAILURE );
2052 }
2053
2054
2055 /*************************************************************************/
2056 /*************************************************************************/
2057 /** **/
2058 /** SCAN-LINE SWEEPS AND DRAWING **/
2059 /** **/
2060 /*************************************************************************/
2061 /*************************************************************************/
2062
2063
2064 /**************************************************************************
2065 *
2066 * Init_Linked
2067 *
2068 * Initializes an empty linked list.
2069 */
2070 static void
2071 Init_Linked( TProfileList* l )
2072 {
2073 *l = NULL;
2074 }
2075
2076
2077 /**************************************************************************
2078 *
2079 * InsNew
2080 *
2081 * Inserts a new profile in a linked list.
2082 */
2083 static void
2084 InsNew( PProfileList list,
2085 PProfile profile )
2086 {
2087 PProfile *old, current;
2088 Long x;
2089
2090
2091 old = list;
2092 current = *old;
2093 x = profile->X;
2094
2095 while ( current )
2096 {
2097 if ( x < current->X )
2098 break;
2099 old = ¤t->link;
2100 current = *old;
2101 }
2102
2103 profile->link = current;
2104 *old = profile;
2105 }
2106
2107
2108 /**************************************************************************
2109 *
2110 * DelOld
2111 *
2112 * Removes an old profile from a linked list.
2113 */
2114 static void
2115 DelOld( PProfileList list,
2116 PProfile profile )
2117 {
2118 PProfile *old, current;
2119
2120
2121 old = list;
2122 current = *old;
2123
2124 while ( current )
2125 {
2126 if ( current == profile )
2127 {
2128 *old = current->link;
2129 return;
2130 }
2131
2132 old = ¤t->link;
2133 current = *old;
2134 }
2135
2136 /* we should never get there, unless the profile was not part of */
2137 /* the list. */
2138 }
2139
2140
2141 /**************************************************************************
2142 *
2143 * Sort
2144 *
2145 * Sorts a trace list. In 95%, the list is already sorted. We need
2146 * an algorithm which is fast in this case. Bubble sort is enough
2147 * and simple.
2148 */
2149 static void
2150 Sort( PProfileList list )
2151 {
2152 PProfile *old, current, next;
2153
2154
2155 /* First, set the new X coordinate of each profile */
2156 current = *list;
2157 while ( current )
2158 {
2159 current->X = *current->offset;
2160 current->offset += ( current->flags & Flow_Up ) ? 1 : -1;
2161 current->height--;
2162 current = current->link;
2163 }
2164
2165 /* Then sort them */
2166 old = list;
2167 current = *old;
2168
2169 if ( !current )
2170 return;
2171
2172 next = current->link;
2173
2174 while ( next )
2175 {
2176 if ( current->X <= next->X )
2177 {
2178 old = ¤t->link;
2179 current = *old;
2180
2181 if ( !current )
2182 return;
2183 }
2184 else
2185 {
2186 *old = next;
2187 current->link = next->link;
2188 next->link = current;
2189
2190 old = list;
2191 current = *old;
2192 }
2193
2194 next = current->link;
2195 }
2196 }
2197
2198
2199 /**************************************************************************
2200 *
2201 * Vertical Sweep Procedure Set
2202 *
2203 * These four routines are used during the vertical black/white sweep
2204 * phase by the generic Draw_Sweep() function.
2205 *
2206 */
2207
2208 static void
2209 Vertical_Sweep_Init( RAS_ARGS Short* min,
2210 Short* max )
2211 {
2212 Long pitch = ras.target.pitch;
2213
2214 FT_UNUSED( max );
2215
2216
2217 ras.traceIncr = (Short)-pitch;
2218 ras.traceOfs = -*min * pitch;
2219 }
2220
2221
2222 static void
2223 Vertical_Sweep_Span( RAS_ARGS Short y,
2224 FT_F26Dot6 x1,
2225 FT_F26Dot6 x2,
2226 PProfile left,
2227 PProfile right )
2228 {
2229 Long e1, e2;
2230 Byte* target;
2231
2232 Int dropOutControl = left->flags & 7;
2233
2234 FT_UNUSED( y );
2235 FT_UNUSED( left );
2236 FT_UNUSED( right );
2237
2238
2239 /* in high-precision mode, we need 12 digits after the comma to */
2240 /* represent multiples of 1/(1<<12) = 1/4096 */
2241 FT_TRACE7(( " y=%d x=[%.12f;%.12f], drop-out=%d",
2242 y,
2243 x1 / (double)ras.precision,
2244 x2 / (double)ras.precision,
2245 dropOutControl ));
2246
2247 /* Drop-out control */
2248
2249 e1 = CEILING( x1 );
2250 e2 = FLOOR( x2 );
2251
2252 /* take care of the special case where both the left */
2253 /* and right contour lie exactly on pixel centers */
2254 if ( dropOutControl != 2 &&
2255 x2 - x1 - ras.precision <= ras.precision_jitter &&
2256 e1 != x1 && e2 != x2 )
2257 e2 = e1;
2258
2259 e1 = TRUNC( e1 );
2260 e2 = TRUNC( e2 );
2261
2262 if ( e2 >= 0 && e1 < ras.bWidth )
2263 {
2264 Int c1, c2;
2265 Byte f1, f2;
2266
2267
2268 if ( e1 < 0 )
2269 e1 = 0;
2270 if ( e2 >= ras.bWidth )
2271 e2 = ras.bWidth - 1;
2272
2273 FT_TRACE7(( " -> x=[%d;%d]", e1, e2 ));
2274
2275 c1 = (Short)( e1 >> 3 );
2276 c2 = (Short)( e2 >> 3 );
2277
2278 f1 = (Byte) ( 0xFF >> ( e1 & 7 ) );
2279 f2 = (Byte) ~( 0x7F >> ( e2 & 7 ) );
2280
2281 target = ras.bOrigin + ras.traceOfs + c1;
2282 c2 -= c1;
2283
2284 if ( c2 > 0 )
2285 {
2286 target[0] |= f1;
2287
2288 /* memset() is slower than the following code on many platforms. */
2289 /* This is due to the fact that, in the vast majority of cases, */
2290 /* the span length in bytes is relatively small. */
2291 while ( --c2 > 0 )
2292 *(++target) = 0xFF;
2293
2294 target[1] |= f2;
2295 }
2296 else
2297 *target |= ( f1 & f2 );
2298 }
2299
2300 FT_TRACE7(( "\n" ));
2301 }
2302
2303
2304 static void
2305 Vertical_Sweep_Drop( RAS_ARGS Short y,
2306 FT_F26Dot6 x1,
2307 FT_F26Dot6 x2,
2308 PProfile left,
2309 PProfile right )
2310 {
2311 Long e1, e2, pxl;
2312 Short c1, f1;
2313
2314
2315 FT_TRACE7(( " y=%d x=[%.12f;%.12f]",
2316 y,
2317 x1 / (double)ras.precision,
2318 x2 / (double)ras.precision ));
2319
2320 /* Drop-out control */
2321
2322 /* e2 x2 x1 e1 */
2323 /* */
2324 /* ^ | */
2325 /* | | */
2326 /* +-------------+---------------------+------------+ */
2327 /* | | */
2328 /* | v */
2329 /* */
2330 /* pixel contour contour pixel */
2331 /* center center */
2332
2333 /* drop-out mode scan conversion rules (as defined in OpenType) */
2334 /* --------------------------------------------------------------- */
2335 /* 0 1, 2, 3 */
2336 /* 1 1, 2, 4 */
2337 /* 2 1, 2 */
2338 /* 3 same as mode 2 */
2339 /* 4 1, 2, 5 */
2340 /* 5 1, 2, 6 */
2341 /* 6, 7 same as mode 2 */
2342
2343 e1 = CEILING( x1 );
2344 e2 = FLOOR ( x2 );
2345 pxl = e1;
2346
2347 if ( e1 > e2 )
2348 {
2349 Int dropOutControl = left->flags & 7;
2350
2351
2352 FT_TRACE7(( ", drop-out=%d", dropOutControl ));
2353
2354 if ( e1 == e2 + ras.precision )
2355 {
2356 switch ( dropOutControl )
2357 {
2358 case 0: /* simple drop-outs including stubs */
2359 pxl = e2;
2360 break;
2361
2362 case 4: /* smart drop-outs including stubs */
2363 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2364 break;
2365
2366 case 1: /* simple drop-outs excluding stubs */
2367 case 5: /* smart drop-outs excluding stubs */
2368
2369 /* Drop-out Control Rules #4 and #6 */
2370
2371 /* The specification neither provides an exact definition */
2372 /* of a `stub' nor gives exact rules to exclude them. */
2373 /* */
2374 /* Here the constraints we use to recognize a stub. */
2375 /* */
2376 /* upper stub: */
2377 /* */
2378 /* - P_Left and P_Right are in the same contour */
2379 /* - P_Right is the successor of P_Left in that contour */
2380 /* - y is the top of P_Left and P_Right */
2381 /* */
2382 /* lower stub: */
2383 /* */
2384 /* - P_Left and P_Right are in the same contour */
2385 /* - P_Left is the successor of P_Right in that contour */
2386 /* - y is the bottom of P_Left */
2387 /* */
2388 /* We draw a stub if the following constraints are met. */
2389 /* */
2390 /* - for an upper or lower stub, there is top or bottom */
2391 /* overshoot, respectively */
2392 /* - the covered interval is greater or equal to a half */
2393 /* pixel */
2394
2395 /* upper stub test */
2396 if ( left->next == right &&
2397 left->height <= 0 &&
2398 !( left->flags & Overshoot_Top &&
2399 x2 - x1 >= ras.precision_half ) )
2400 goto Exit;
2401
2402 /* lower stub test */
2403 if ( right->next == left &&
2404 left->start == y &&
2405 !( left->flags & Overshoot_Bottom &&
2406 x2 - x1 >= ras.precision_half ) )
2407 goto Exit;
2408
2409 if ( dropOutControl == 1 )
2410 pxl = e2;
2411 else
2412 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2413 break;
2414
2415 default: /* modes 2, 3, 6, 7 */
2416 goto Exit; /* no drop-out control */
2417 }
2418
2419 /* undocumented but confirmed: If the drop-out would result in a */
2420 /* pixel outside of the bounding box, use the pixel inside of the */
2421 /* bounding box instead */
2422 if ( pxl < 0 )
2423 pxl = e1;
2424 else if ( TRUNC( pxl ) >= ras.bWidth )
2425 pxl = e2;
2426
2427 /* check that the other pixel isn't set */
2428 e1 = ( pxl == e1 ) ? e2 : e1;
2429
2430 e1 = TRUNC( e1 );
2431
2432 c1 = (Short)( e1 >> 3 );
2433 f1 = (Short)( e1 & 7 );
2434
2435 if ( e1 >= 0 && e1 < ras.bWidth &&
2436 ras.bOrigin[ras.traceOfs + c1] & ( 0x80 >> f1 ) )
2437 goto Exit;
2438 }
2439 else
2440 goto Exit;
2441 }
2442
2443 e1 = TRUNC( pxl );
2444
2445 if ( e1 >= 0 && e1 < ras.bWidth )
2446 {
2447 FT_TRACE7(( " -> x=%d (drop-out)", e1 ));
2448
2449 c1 = (Short)( e1 >> 3 );
2450 f1 = (Short)( e1 & 7 );
2451
2452 ras.bOrigin[ras.traceOfs + c1] |= (char)( 0x80 >> f1 );
2453 }
2454
2455 Exit:
2456 FT_TRACE7(( "\n" ));
2457 }
2458
2459
2460 static void
2461 Vertical_Sweep_Step( RAS_ARG )
2462 {
2463 ras.traceOfs += ras.traceIncr;
2464 }
2465
2466
2467 /************************************************************************
2468 *
2469 * Horizontal Sweep Procedure Set
2470 *
2471 * These four routines are used during the horizontal black/white
2472 * sweep phase by the generic Draw_Sweep() function.
2473 *
2474 */
2475
2476 static void
2477 Horizontal_Sweep_Init( RAS_ARGS Short* min,
2478 Short* max )
2479 {
2480 /* nothing, really */
2481 FT_UNUSED_RASTER;
2482 FT_UNUSED( min );
2483 FT_UNUSED( max );
2484 }
2485
2486
2487 static void
2488 Horizontal_Sweep_Span( RAS_ARGS Short y,
2489 FT_F26Dot6 x1,
2490 FT_F26Dot6 x2,
2491 PProfile left,
2492 PProfile right )
2493 {
2494 FT_UNUSED( left );
2495 FT_UNUSED( right );
2496
2497
2498 if ( x2 - x1 < ras.precision )
2499 {
2500 Long e1, e2;
2501
2502
2503 FT_TRACE7(( " x=%d y=[%.12f;%.12f]",
2504 y,
2505 x1 / (double)ras.precision,
2506 x2 / (double)ras.precision ));
2507
2508 e1 = CEILING( x1 );
2509 e2 = FLOOR ( x2 );
2510
2511 if ( e1 == e2 )
2512 {
2513 e1 = TRUNC( e1 );
2514
2515 if ( e1 >= 0 && (ULong)e1 < ras.target.rows )
2516 {
2517 Byte f1;
2518 PByte bits;
2519
2520
2521 FT_TRACE7(( " -> y=%d (drop-out)", e1 ));
2522
2523 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch;
2524 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2525
2526 bits[0] |= f1;
2527 }
2528 }
2529
2530 FT_TRACE7(( "\n" ));
2531 }
2532 }
2533
2534
2535 static void
2536 Horizontal_Sweep_Drop( RAS_ARGS Short y,
2537 FT_F26Dot6 x1,
2538 FT_F26Dot6 x2,
2539 PProfile left,
2540 PProfile right )
2541 {
2542 Long e1, e2, pxl;
2543 PByte bits;
2544 Byte f1;
2545
2546
2547 FT_TRACE7(( " x=%d y=[%.12f;%.12f]",
2548 y,
2549 x1 / (double)ras.precision,
2550 x2 / (double)ras.precision ));
2551
2552 /* During the horizontal sweep, we only take care of drop-outs */
2553
2554 /* e1 + <-- pixel center */
2555 /* | */
2556 /* x1 ---+--> <-- contour */
2557 /* | */
2558 /* | */
2559 /* x2 <--+--- <-- contour */
2560 /* | */
2561 /* | */
2562 /* e2 + <-- pixel center */
2563
2564 e1 = CEILING( x1 );
2565 e2 = FLOOR ( x2 );
2566 pxl = e1;
2567
2568 if ( e1 > e2 )
2569 {
2570 Int dropOutControl = left->flags & 7;
2571
2572
2573 FT_TRACE7(( ", dropout=%d", dropOutControl ));
2574
2575 if ( e1 == e2 + ras.precision )
2576 {
2577 switch ( dropOutControl )
2578 {
2579 case 0: /* simple drop-outs including stubs */
2580 pxl = e2;
2581 break;
2582
2583 case 4: /* smart drop-outs including stubs */
2584 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2585 break;
2586
2587 case 1: /* simple drop-outs excluding stubs */
2588 case 5: /* smart drop-outs excluding stubs */
2589 /* see Vertical_Sweep_Drop for details */
2590
2591 /* rightmost stub test */
2592 if ( left->next == right &&
2593 left->height <= 0 &&
2594 !( left->flags & Overshoot_Top &&
2595 x2 - x1 >= ras.precision_half ) )
2596 goto Exit;
2597
2598 /* leftmost stub test */
2599 if ( right->next == left &&
2600 left->start == y &&
2601 !( left->flags & Overshoot_Bottom &&
2602 x2 - x1 >= ras.precision_half ) )
2603 goto Exit;
2604
2605 if ( dropOutControl == 1 )
2606 pxl = e2;
2607 else
2608 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half );
2609 break;
2610
2611 default: /* modes 2, 3, 6, 7 */
2612 goto Exit; /* no drop-out control */
2613 }
2614
2615 /* undocumented but confirmed: If the drop-out would result in a */
2616 /* pixel outside of the bounding box, use the pixel inside of the */
2617 /* bounding box instead */
2618 if ( pxl < 0 )
2619 pxl = e1;
2620 else if ( (ULong)( TRUNC( pxl ) ) >= ras.target.rows )
2621 pxl = e2;
2622
2623 /* check that the other pixel isn't set */
2624 e1 = ( pxl == e1 ) ? e2 : e1;
2625
2626 e1 = TRUNC( e1 );
2627
2628 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch;
2629 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2630
2631 if ( e1 >= 0 &&
2632 (ULong)e1 < ras.target.rows &&
2633 *bits & f1 )
2634 goto Exit;
2635 }
2636 else
2637 goto Exit;
2638 }
2639
2640 e1 = TRUNC( pxl );
2641
2642 if ( e1 >= 0 && (ULong)e1 < ras.target.rows )
2643 {
2644 FT_TRACE7(( " -> y=%d (drop-out)", e1 ));
2645
2646 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch;
2647 f1 = (Byte)( 0x80 >> ( y & 7 ) );
2648
2649 bits[0] |= f1;
2650 }
2651
2652 Exit:
2653 FT_TRACE7(( "\n" ));
2654 }
2655
2656
2657 static void
2658 Horizontal_Sweep_Step( RAS_ARG )
2659 {
2660 /* Nothing, really */
2661 FT_UNUSED_RASTER;
2662 }
2663
2664
2665 /**************************************************************************
2666 *
2667 * Generic Sweep Drawing routine
2668 *
2669 */
2670
2671 static Bool
2672 Draw_Sweep( RAS_ARG )
2673 {
2674 Short y, y_change, y_height;
2675
2676 PProfile P, Q, P_Left, P_Right;
2677
2678 Short min_Y, max_Y, top, bottom, dropouts;
2679
2680 Long x1, x2, xs, e1, e2;
2681
2682 TProfileList waiting;
2683 TProfileList draw_left, draw_right;
2684
2685
2686 /* initialize empty linked lists */
2687
2688 Init_Linked( &waiting );
2689
2690 Init_Linked( &draw_left );
2691 Init_Linked( &draw_right );
2692
2693 /* first, compute min and max Y */
2694
2695 P = ras.fProfile;
2696 max_Y = (Short)TRUNC( ras.minY );
2697 min_Y = (Short)TRUNC( ras.maxY );
2698
2699 while ( P )
2700 {
2701 Q = P->link;
2702
2703 bottom = (Short)P->start;
2704 top = (Short)( P->start + P->height - 1 );
2705
2706 if ( min_Y > bottom )
2707 min_Y = bottom;
2708 if ( max_Y < top )
2709 max_Y = top;
2710
2711 P->X = 0;
2712 InsNew( &waiting, P );
2713
2714 P = Q;
2715 }
2716
2717 /* check the Y-turns */
2718 if ( ras.numTurns == 0 )
2719 {
2720 ras.error = FT_THROW( Invalid );
2721 return FAILURE;
2722 }
2723
2724 /* now initialize the sweep */
2725
2726 ras.Proc_Sweep_Init( RAS_VARS &min_Y, &max_Y );
2727
2728 /* then compute the distance of each profile from min_Y */
2729
2730 P = waiting;
2731
2732 while ( P )
2733 {
2734 P->countL = P->start - min_Y;
2735 P = P->link;
2736 }
2737
2738 /* let's go */
2739
2740 y = min_Y;
2741 y_height = 0;
2742
2743 if ( ras.numTurns > 0 &&
2744 ras.sizeBuff[-ras.numTurns] == min_Y )
2745 ras.numTurns--;
2746
2747 while ( ras.numTurns > 0 )
2748 {
2749 /* check waiting list for new activations */
2750
2751 P = waiting;
2752
2753 while ( P )
2754 {
2755 Q = P->link;
2756 P->countL -= y_height;
2757 if ( P->countL == 0 )
2758 {
2759 DelOld( &waiting, P );
2760
2761 if ( P->flags & Flow_Up )
2762 InsNew( &draw_left, P );
2763 else
2764 InsNew( &draw_right, P );
2765 }
2766
2767 P = Q;
2768 }
2769
2770 /* sort the drawing lists */
2771
2772 Sort( &draw_left );
2773 Sort( &draw_right );
2774
2775 y_change = (Short)ras.sizeBuff[-ras.numTurns--];
2776 y_height = (Short)( y_change - y );
2777
2778 while ( y < y_change )
2779 {
2780 /* let's trace */
2781
2782 dropouts = 0;
2783
2784 P_Left = draw_left;
2785 P_Right = draw_right;
2786
2787 while ( P_Left )
2788 {
2789 x1 = P_Left ->X;
2790 x2 = P_Right->X;
2791
2792 if ( x1 > x2 )
2793 {
2794 xs = x1;
2795 x1 = x2;
2796 x2 = xs;
2797 }
2798
2799 e1 = FLOOR( x1 );
2800 e2 = CEILING( x2 );
2801
2802 if ( x2 - x1 <= ras.precision &&
2803 e1 != x1 && e2 != x2 )
2804 {
2805 if ( e1 > e2 || e2 == e1 + ras.precision )
2806 {
2807 Int dropOutControl = P_Left->flags & 7;
2808
2809
2810 if ( dropOutControl != 2 )
2811 {
2812 /* a drop-out was detected */
2813
2814 P_Left ->X = x1;
2815 P_Right->X = x2;
2816
2817 /* mark profile for drop-out processing */
2818 P_Left->countL = 1;
2819 dropouts++;
2820 }
2821
2822 goto Skip_To_Next;
2823 }
2824 }
2825
2826 ras.Proc_Sweep_Span( RAS_VARS y, x1, x2, P_Left, P_Right );
2827
2828 Skip_To_Next:
2829
2830 P_Left = P_Left->link;
2831 P_Right = P_Right->link;
2832 }
2833
2834 /* handle drop-outs _after_ the span drawing -- */
2835 /* drop-out processing has been moved out of the loop */
2836 /* for performance tuning */
2837 if ( dropouts > 0 )
2838 goto Scan_DropOuts;
2839
2840 Next_Line:
2841
2842 ras.Proc_Sweep_Step( RAS_VAR );
2843
2844 y++;
2845
2846 if ( y < y_change )
2847 {
2848 Sort( &draw_left );
2849 Sort( &draw_right );
2850 }
2851 }
2852
2853 /* now finalize the profiles that need it */
2854
2855 P = draw_left;
2856 while ( P )
2857 {
2858 Q = P->link;
2859 if ( P->height == 0 )
2860 DelOld( &draw_left, P );
2861 P = Q;
2862 }
2863
2864 P = draw_right;
2865 while ( P )
2866 {
2867 Q = P->link;
2868 if ( P->height == 0 )
2869 DelOld( &draw_right, P );
2870 P = Q;
2871 }
2872 }
2873
2874 /* for gray-scaling, flush the bitmap scanline cache */
2875 while ( y <= max_Y )
2876 {
2877 ras.Proc_Sweep_Step( RAS_VAR );
2878 y++;
2879 }
2880
2881 return SUCCESS;
2882
2883 Scan_DropOuts:
2884
2885 P_Left = draw_left;
2886 P_Right = draw_right;
2887
2888 while ( P_Left )
2889 {
2890 if ( P_Left->countL )
2891 {
2892 P_Left->countL = 0;
2893 #if 0
2894 dropouts--; /* -- this is useful when debugging only */
2895 #endif
2896 ras.Proc_Sweep_Drop( RAS_VARS y,
2897 P_Left->X,
2898 P_Right->X,
2899 P_Left,
2900 P_Right );
2901 }
2902
2903 P_Left = P_Left->link;
2904 P_Right = P_Right->link;
2905 }
2906
2907 goto Next_Line;
2908 }
2909
2910
2911 #ifdef STANDALONE_
2912
2913 /**************************************************************************
2914 *
2915 * The following functions should only compile in stand-alone mode,
2916 * i.e., when building this component without the rest of FreeType.
2917 *
2918 */
2919
2920 /**************************************************************************
2921 *
2922 * @Function:
2923 * FT_Outline_Get_CBox
2924 *
2925 * @Description:
2926 * Return an outline's `control box'. The control box encloses all
2927 * the outline's points, including Bézier control points. Though it
2928 * coincides with the exact bounding box for most glyphs, it can be
2929 * slightly larger in some situations (like when rotating an outline
2930 * that contains Bézier outside arcs).
2931 *
2932 * Computing the control box is very fast, while getting the bounding
2933 * box can take much more time as it needs to walk over all segments
2934 * and arcs in the outline. To get the latter, you can use the
2935 * `ftbbox' component, which is dedicated to this single task.
2936 *
2937 * @Input:
2938 * outline ::
2939 * A pointer to the source outline descriptor.
2940 *
2941 * @Output:
2942 * acbox ::
2943 * The outline's control box.
2944 *
2945 * @Note:
2946 * See @FT_Glyph_Get_CBox for a discussion of tricky fonts.
2947 */
2948
2949 static void
2950 FT_Outline_Get_CBox( const FT_Outline* outline,
2951 FT_BBox *acbox )
2952 {
2953 Long xMin, yMin, xMax, yMax;
2954
2955
2956 if ( outline && acbox )
2957 {
2958 if ( outline->n_points == 0 )
2959 {
2960 xMin = 0;
2961 yMin = 0;
2962 xMax = 0;
2963 yMax = 0;
2964 }
2965 else
2966 {
2967 FT_Vector* vec = outline->points;
2968 FT_Vector* limit = vec + outline->n_points;
2969
2970
2971 xMin = xMax = vec->x;
2972 yMin = yMax = vec->y;
2973 vec++;
2974
2975 for ( ; vec < limit; vec++ )
2976 {
2977 Long x, y;
2978
2979
2980 x = vec->x;
2981 if ( x < xMin ) xMin = x;
2982 if ( x > xMax ) xMax = x;
2983
2984 y = vec->y;
2985 if ( y < yMin ) yMin = y;
2986 if ( y > yMax ) yMax = y;
2987 }
2988 }
2989 acbox->xMin = xMin;
2990 acbox->xMax = xMax;
2991 acbox->yMin = yMin;
2992 acbox->yMax = yMax;
2993 }
2994 }
2995
2996 #endif /* STANDALONE_ */
2997
2998
2999 /**************************************************************************
3000 *
3001 * @Function:
3002 * Render_Single_Pass
3003 *
3004 * @Description:
3005 * Perform one sweep with sub-banding.
3006 *
3007 * @Input:
3008 * flipped ::
3009 * If set, flip the direction of the outline.
3010 *
3011 * @Return:
3012 * Renderer error code.
3013 */
3014 static int
3015 Render_Single_Pass( RAS_ARGS Bool flipped )
3016 {
3017 Short i, j, k;
3018
3019
3020 while ( ras.band_top >= 0 )
3021 {
3022 ras.maxY = (Long)ras.band_stack[ras.band_top].y_max * ras.precision;
3023 ras.minY = (Long)ras.band_stack[ras.band_top].y_min * ras.precision;
3024
3025 ras.top = ras.buff;
3026
3027 ras.error = Raster_Err_None;
3028
3029 if ( Convert_Glyph( RAS_VARS flipped ) )
3030 {
3031 if ( ras.error != Raster_Err_Overflow )
3032 return FAILURE;
3033
3034 ras.error = Raster_Err_None;
3035
3036 /* sub-banding */
3037
3038 #ifdef DEBUG_RASTER
3039 ClearBand( RAS_VARS TRUNC( ras.minY ), TRUNC( ras.maxY ) );
3040 #endif
3041
3042 i = ras.band_stack[ras.band_top].y_min;
3043 j = ras.band_stack[ras.band_top].y_max;
3044
3045 k = (Short)( ( i + j ) / 2 );
3046
3047 if ( ras.band_top >= 7 || k < i )
3048 {
3049 ras.band_top = 0;
3050 ras.error = FT_THROW( Invalid );
3051
3052 return ras.error;
3053 }
3054
3055 ras.band_stack[ras.band_top + 1].y_min = k;
3056 ras.band_stack[ras.band_top + 1].y_max = j;
3057
3058 ras.band_stack[ras.band_top].y_max = (Short)( k - 1 );
3059
3060 ras.band_top++;
3061 }
3062 else
3063 {
3064 if ( ras.fProfile )
3065 if ( Draw_Sweep( RAS_VAR ) )
3066 return ras.error;
3067 ras.band_top--;
3068 }
3069 }
3070
3071 return SUCCESS;
3072 }
3073
3074
3075 /**************************************************************************
3076 *
3077 * @Function:
3078 * Render_Glyph
3079 *
3080 * @Description:
3081 * Render a glyph in a bitmap. Sub-banding if needed.
3082 *
3083 * @Return:
3084 * FreeType error code. 0 means success.
3085 */
3086 static FT_Error
3087 Render_Glyph( RAS_ARG )
3088 {
3089 FT_Error error;
3090
3091
3092 Set_High_Precision( RAS_VARS ras.outline.flags &
3093 FT_OUTLINE_HIGH_PRECISION );
3094
3095 if ( ras.outline.flags & FT_OUTLINE_IGNORE_DROPOUTS )
3096 ras.dropOutControl = 2;
3097 else
3098 {
3099 if ( ras.outline.flags & FT_OUTLINE_SMART_DROPOUTS )
3100 ras.dropOutControl = 4;
3101 else
3102 ras.dropOutControl = 0;
3103
3104 if ( !( ras.outline.flags & FT_OUTLINE_INCLUDE_STUBS ) )
3105 ras.dropOutControl += 1;
3106 }
3107
3108 ras.second_pass = (Bool)( !( ras.outline.flags &
3109 FT_OUTLINE_SINGLE_PASS ) );
3110
3111 /* Vertical Sweep */
3112 FT_TRACE7(( "Vertical pass (ftraster)\n" ));
3113
3114 ras.Proc_Sweep_Init = Vertical_Sweep_Init;
3115 ras.Proc_Sweep_Span = Vertical_Sweep_Span;
3116 ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
3117 ras.Proc_Sweep_Step = Vertical_Sweep_Step;
3118
3119 ras.band_top = 0;
3120 ras.band_stack[0].y_min = 0;
3121 ras.band_stack[0].y_max = (Short)( ras.target.rows - 1 );
3122
3123 ras.bWidth = (UShort)ras.target.width;
3124 ras.bOrigin = (Byte*)ras.target.buffer;
3125
3126 if ( ras.target.pitch > 0 )
3127 ras.bOrigin += (Long)( ras.target.rows - 1 ) * ras.target.pitch;
3128
3129 if ( ( error = Render_Single_Pass( RAS_VARS 0 ) ) != 0 )
3130 return error;
3131
3132 /* Horizontal Sweep */
3133 if ( ras.second_pass && ras.dropOutControl != 2 )
3134 {
3135 FT_TRACE7(( "Horizontal pass (ftraster)\n" ));
3136
3137 ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
3138 ras.Proc_Sweep_Span = Horizontal_Sweep_Span;
3139 ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop;
3140 ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3141
3142 ras.band_top = 0;
3143 ras.band_stack[0].y_min = 0;
3144 ras.band_stack[0].y_max = (Short)( ras.target.width - 1 );
3145
3146 if ( ( error = Render_Single_Pass( RAS_VARS 1 ) ) != 0 )
3147 return error;
3148 }
3149
3150 return Raster_Err_None;
3151 }
3152
3153
3154 static void
3155 ft_black_init( black_PRaster raster )
3156 {
3157 FT_UNUSED( raster );
3158 }
3159
3160
3161 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
3162 /**** a static object. *****/
3163
3164
3165 #ifdef STANDALONE_
3166
3167
3168 static int
3169 ft_black_new( void* memory,
3170 FT_Raster *araster )
3171 {
3172 static black_TRaster the_raster;
3173 FT_UNUSED( memory );
3174
3175
3176 *araster = (FT_Raster)&the_raster;
3177 FT_ZERO( &the_raster );
3178 ft_black_init( &the_raster );
3179
3180 return 0;
3181 }
3182
3183
3184 static void
3185 ft_black_done( FT_Raster raster )
3186 {
3187 /* nothing */
3188 FT_UNUSED( raster );
3189 }
3190
3191
3192 #else /* !STANDALONE_ */
3193
3194
3195 static int
3196 ft_black_new( FT_Memory memory,
3197 black_PRaster *araster )
3198 {
3199 FT_Error error;
3200 black_PRaster raster = NULL;
3201
3202
3203 *araster = 0;
3204 if ( !FT_NEW( raster ) )
3205 {
3206 raster->memory = memory;
3207 ft_black_init( raster );
3208
3209 *araster = raster;
3210 }
3211
3212 return error;
3213 }
3214
3215
3216 static void
3217 ft_black_done( black_PRaster raster )
3218 {
3219 FT_Memory memory = (FT_Memory)raster->memory;
3220
3221
3222 FT_FREE( raster );
3223 }
3224
3225
3226 #endif /* !STANDALONE_ */
3227
3228
3229 static void
3230 ft_black_reset( FT_Raster raster,
3231 PByte pool_base,
3232 ULong pool_size )
3233 {
3234 FT_UNUSED( raster );
3235 FT_UNUSED( pool_base );
3236 FT_UNUSED( pool_size );
3237 }
3238
3239
3240 static int
3241 ft_black_set_mode( FT_Raster raster,
3242 ULong mode,
3243 void* args )
3244 {
3245 FT_UNUSED( raster );
3246 FT_UNUSED( mode );
3247 FT_UNUSED( args );
3248
3249 return 0;
3250 }
3251
3252
3253 static int
3254 ft_black_render( FT_Raster raster,
3255 const FT_Raster_Params* params )
3256 {
3257 const FT_Outline* outline = (const FT_Outline*)params->source;
3258 const FT_Bitmap* target_map = params->target;
3259
3260 black_TWorker worker[1];
3261
3262 Long buffer[FT_MAX_BLACK_POOL];
3263
3264
3265 if ( !raster )
3266 return FT_THROW( Not_Ini );
3267
3268 if ( !outline )
3269 return FT_THROW( Invalid );
3270
3271 /* return immediately if the outline is empty */
3272 if ( outline->n_points == 0 || outline->n_contours <= 0 )
3273 return Raster_Err_None;
3274
3275 if ( !outline->contours || !outline->points )
3276 return FT_THROW( Invalid );
3277
3278 if ( outline->n_points !=
3279 outline->contours[outline->n_contours - 1] + 1 )
3280 return FT_THROW( Invalid );
3281
3282 /* this version of the raster does not support direct rendering, sorry */
3283 if ( params->flags & FT_RASTER_FLAG_DIRECT )
3284 return FT_THROW( Unsupported );
3285
3286 if ( params->flags & FT_RASTER_FLAG_AA )
3287 return FT_THROW( Unsupported );
3288
3289 if ( !target_map )
3290 return FT_THROW( Invalid );
3291
3292 /* nothing to do */
3293 if ( !target_map->width || !target_map->rows )
3294 return Raster_Err_None;
3295
3296 if ( !target_map->buffer )
3297 return FT_THROW( Invalid );
3298
3299 ras.outline = *outline;
3300 ras.target = *target_map;
3301
3302 worker->buff = buffer;
3303 worker->sizeBuff = (&buffer)[1]; /* Points to right after buffer. */
3304
3305 return Render_Glyph( RAS_VAR );
3306 }
3307
3308
3309 FT_DEFINE_RASTER_FUNCS(
3310 ft_standard_raster,
3311
3312 FT_GLYPH_FORMAT_OUTLINE,
3313
3314 (FT_Raster_New_Func) ft_black_new, /* raster_new */
3315 (FT_Raster_Reset_Func) ft_black_reset, /* raster_reset */
3316 (FT_Raster_Set_Mode_Func)ft_black_set_mode, /* raster_set_mode */
3317 (FT_Raster_Render_Func) ft_black_render, /* raster_render */
3318 (FT_Raster_Done_Func) ft_black_done /* raster_done */
3319 )
3320
3321
3322 /* END */