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