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