projects / reactos.git / blob
? search:


a85e16086e79b78c195aaf645e0f4b9b353631df
[reactos.git] / lib / 3rdparty / freetype / src / smooth / ftgrays.c
1 /***************************************************************************/
2 /* */
3 /* ftgrays.c */
4 /* */
5 /* A new `perfect' anti-aliasing renderer (body). */
6 /* */
7 /* Copyright 2000-2001, 2002, 2003, 2005, 2006, 2007, 2008, 2009, 2010 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 `ftgrays.h' and `ftimage.h' into the current */
23 /* compilation directory. Typically, you could do something like */
24 /* */
25 /* - copy `src/smooth/ftgrays.c' (this file) to your current directory */
26 /* */
27 /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
28 /* same directory */
29 /* */
30 /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in */
31 /* */
32 /* cc -c -D_STANDALONE_ ftgrays.c */
33 /* */
34 /* The renderer can be initialized with a call to */
35 /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated */
36 /* with a call to `ft_gray_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 /* This is a new anti-aliasing scan-converter for FreeType 2. The */
46 /* algorithm used here is _very_ different from the one in the standard */
47 /* `ftraster' module. Actually, `ftgrays' computes the _exact_ */
48 /* coverage of the outline on each pixel cell. */
49 /* */
50 /* It is based on ideas that I initially found in Raph Levien's */
51 /* excellent LibArt graphics library (see http://www.levien.com/libart */
52 /* for more information, though the web pages do not tell anything */
53 /* about the renderer; you'll have to dive into the source code to */
54 /* understand how it works). */
55 /* */
56 /* Note, however, that this is a _very_ different implementation */
57 /* compared to Raph's. Coverage information is stored in a very */
58 /* different way, and I don't use sorted vector paths. Also, it doesn't */
59 /* use floating point values. */
60 /* */
61 /* This renderer has the following advantages: */
62 /* */
63 /* - It doesn't need an intermediate bitmap. Instead, one can supply a */
64 /* callback function that will be called by the renderer to draw gray */
65 /* spans on any target surface. You can thus do direct composition on */
66 /* any kind of bitmap, provided that you give the renderer the right */
67 /* callback. */
68 /* */
69 /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */
70 /* each pixel cell. */
71 /* */
72 /* - It performs a single pass on the outline (the `standard' FT2 */
73 /* renderer makes two passes). */
74 /* */
75 /* - It can easily be modified to render to _any_ number of gray levels */
76 /* cheaply. */
77 /* */
78 /* - For small (< 20) pixel sizes, it is faster than the standard */
79 /* renderer. */
80 /* */
81 /*************************************************************************/
82
83
84 /*************************************************************************/
85 /* */
86 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
87 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
88 /* messages during execution. */
89 /* */
90 #undef FT_COMPONENT
91 #define FT_COMPONENT trace_smooth
92
93
94 #ifdef _STANDALONE_
95
96
97 /* define this to dump debugging information */
98 /* #define FT_DEBUG_LEVEL_TRACE */
99
100
101 #ifdef FT_DEBUG_LEVEL_TRACE
102 #include <stdio.h>
103 #include <stdarg.h>
104 #endif
105
106 #include <stddef.h>
107 #include <string.h>
108 #include <setjmp.h>
109 #include <limits.h>
110 #define FT_UINT_MAX UINT_MAX
111 #define FT_INT_MAX INT_MAX
112
113 #define ft_memset memset
114
115 #define ft_setjmp setjmp
116 #define ft_longjmp longjmp
117 #define ft_jmp_buf jmp_buf
118
119 typedef ptrdiff_t FT_PtrDist;
120
121
122 #define ErrRaster_Invalid_Mode -2
123 #define ErrRaster_Invalid_Outline -1
124 #define ErrRaster_Invalid_Argument -3
125 #define ErrRaster_Memory_Overflow -4
126
127 #define FT_BEGIN_HEADER
128 #define FT_END_HEADER
129
130 #include "ftimage.h"
131 #include "ftgrays.h"
132
133
134 /* This macro is used to indicate that a function parameter is unused. */
135 /* Its purpose is simply to reduce compiler warnings. Note also that */
136 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
137 /* ANSI compilers (e.g. LCC). */
138 #define FT_UNUSED( x ) (x) = (x)
139
140
141 /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */
142
143 #ifdef FT_DEBUG_LEVEL_TRACE
144
145 void
146 FT_Message( const char* fmt,
147 ... )
148 {
149 va_list ap;
150
151
152 va_start( ap, fmt );
153 vfprintf( stderr, fmt, ap );
154 va_end( ap );
155 }
156
157 /* we don't handle tracing levels in stand-alone mode; */
158 #ifndef FT_TRACE5
159 #define FT_TRACE5( varformat ) FT_Message varformat
160 #endif
161 #ifndef FT_TRACE7
162 #define FT_TRACE7( varformat ) FT_Message varformat
163 #endif
164 #ifndef FT_ERROR
165 #define FT_ERROR( varformat ) FT_Message varformat
166 #endif
167
168 #else /* !FT_DEBUG_LEVEL_TRACE */
169
170 #define FT_TRACE5( x ) do { } while ( 0 ) /* nothing */
171 #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */
172 #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */
173
174 #endif /* !FT_DEBUG_LEVEL_TRACE */
175
176
177 #define FT_DEFINE_OUTLINE_FUNCS( class_, \
178 move_to_, line_to_, \
179 conic_to_, cubic_to_, \
180 shift_, delta_ ) \
181 static const FT_Outline_Funcs class_ = \
182 { \
183 move_to_, \
184 line_to_, \
185 conic_to_, \
186 cubic_to_, \
187 shift_, \
188 delta_ \
189 };
190
191 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, \
192 raster_new_, raster_reset_, \
193 raster_set_mode_, raster_render_, \
194 raster_done_ ) \
195 const FT_Raster_Funcs class_ = \
196 { \
197 glyph_format_, \
198 raster_new_, \
199 raster_reset_, \
200 raster_set_mode_, \
201 raster_render_, \
202 raster_done_ \
203 };
204
205 #else /* !_STANDALONE_ */
206
207
208 #include <ft2build.h>
209 #include "ftgrays.h"
210 #include FT_INTERNAL_OBJECTS_H
211 #include FT_INTERNAL_DEBUG_H
212 #include FT_OUTLINE_H
213
214 #include "ftsmerrs.h"
215
216 #include "ftspic.h"
217
218 #define ErrRaster_Invalid_Mode Smooth_Err_Cannot_Render_Glyph
219 #define ErrRaster_Invalid_Outline Smooth_Err_Invalid_Outline
220 #define ErrRaster_Memory_Overflow Smooth_Err_Out_Of_Memory
221 #define ErrRaster_Invalid_Argument Smooth_Err_Invalid_Argument
222
223 #endif /* !_STANDALONE_ */
224
225 #ifndef FT_MEM_SET
226 #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c )
227 #endif
228
229 #ifndef FT_MEM_ZERO
230 #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count )
231 #endif
232
233 /* as usual, for the speed hungry :-) */
234
235 #ifndef FT_STATIC_RASTER
236
237 #define RAS_ARG PWorker worker
238 #define RAS_ARG_ PWorker worker,
239
240 #define RAS_VAR worker
241 #define RAS_VAR_ worker,
242
243 #else /* FT_STATIC_RASTER */
244
245 #define RAS_ARG /* empty */
246 #define RAS_ARG_ /* empty */
247 #define RAS_VAR /* empty */
248 #define RAS_VAR_ /* empty */
249
250 #endif /* FT_STATIC_RASTER */
251
252
253 /* must be at least 6 bits! */
254 #define PIXEL_BITS 8
255
256 #define ONE_PIXEL ( 1L << PIXEL_BITS )
257 #define PIXEL_MASK ( -1L << PIXEL_BITS )
258 #define TRUNC( x ) ( (TCoord)( (x) >> PIXEL_BITS ) )
259 #define SUBPIXELS( x ) ( (TPos)(x) << PIXEL_BITS )
260 #define FLOOR( x ) ( (x) & -ONE_PIXEL )
261 #define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
262 #define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
263
264 #if PIXEL_BITS >= 6
265 #define UPSCALE( x ) ( (x) << ( PIXEL_BITS - 6 ) )
266 #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
267 #else
268 #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
269 #define DOWNSCALE( x ) ( (x) << ( 6 - PIXEL_BITS ) )
270 #endif
271
272
273 /*************************************************************************/
274 /* */
275 /* TYPE DEFINITIONS */
276 /* */
277
278 /* don't change the following types to FT_Int or FT_Pos, since we might */
279 /* need to define them to "float" or "double" when experimenting with */
280 /* new algorithms */
281
282 typedef long TCoord; /* integer scanline/pixel coordinate */
283 typedef long TPos; /* sub-pixel coordinate */
284
285 /* determine the type used to store cell areas. This normally takes at */
286 /* least PIXEL_BITS*2 + 1 bits. On 16-bit systems, we need to use */
287 /* `long' instead of `int', otherwise bad things happen */
288
289 #if PIXEL_BITS <= 7
290
291 typedef int TArea;
292
293 #else /* PIXEL_BITS >= 8 */
294
295 /* approximately determine the size of integers using an ANSI-C header */
296 #if FT_UINT_MAX == 0xFFFFU
297 typedef long TArea;
298 #else
299 typedef int TArea;
300 #endif
301
302 #endif /* PIXEL_BITS >= 8 */
303
304
305 /* maximal number of gray spans in a call to the span callback */
306 #define FT_MAX_GRAY_SPANS 32
307
308
309 typedef struct TCell_* PCell;
310
311 typedef struct TCell_
312 {
313 TPos x; /* same with TWorker.ex */
314 TCoord cover; /* same with TWorker.cover */
315 TArea area;
316 PCell next;
317
318 } TCell;
319
320
321 typedef struct TWorker_
322 {
323 TCoord ex, ey;
324 TPos min_ex, max_ex;
325 TPos min_ey, max_ey;
326 TPos count_ex, count_ey;
327
328 TArea area;
329 TCoord cover;
330 int invalid;
331
332 PCell cells;
333 FT_PtrDist max_cells;
334 FT_PtrDist num_cells;
335
336 TCoord cx, cy;
337 TPos x, y;
338
339 TPos last_ey;
340
341 FT_Vector bez_stack[32 * 3 + 1];
342 int lev_stack[32];
343
344 FT_Outline outline;
345 FT_Bitmap target;
346 FT_BBox clip_box;
347
348 FT_Span gray_spans[FT_MAX_GRAY_SPANS];
349 int num_gray_spans;
350
351 FT_Raster_Span_Func render_span;
352 void* render_span_data;
353 int span_y;
354
355 int band_size;
356 int band_shoot;
357
358 ft_jmp_buf jump_buffer;
359
360 void* buffer;
361 long buffer_size;
362
363 PCell* ycells;
364 TPos ycount;
365
366 } TWorker, *PWorker;
367
368
369 #ifndef FT_STATIC_RASTER
370 #define ras (*worker)
371 #else
372 static TWorker ras;
373 #endif
374
375
376 typedef struct TRaster_
377 {
378 void* buffer;
379 long buffer_size;
380 int band_size;
381 void* memory;
382 PWorker worker;
383
384 } TRaster, *PRaster;
385
386
387
388 /*************************************************************************/
389 /* */
390 /* Initialize the cells table. */
391 /* */
392 static void
393 gray_init_cells( RAS_ARG_ void* buffer,
394 long byte_size )
395 {
396 ras.buffer = buffer;
397 ras.buffer_size = byte_size;
398
399 ras.ycells = (PCell*) buffer;
400 ras.cells = NULL;
401 ras.max_cells = 0;
402 ras.num_cells = 0;
403 ras.area = 0;
404 ras.cover = 0;
405 ras.invalid = 1;
406 }
407
408
409 /*************************************************************************/
410 /* */
411 /* Compute the outline bounding box. */
412 /* */
413 static void
414 gray_compute_cbox( RAS_ARG )
415 {
416 FT_Outline* outline = &ras.outline;
417 FT_Vector* vec = outline->points;
418 FT_Vector* limit = vec + outline->n_points;
419
420
421 if ( outline->n_points <= 0 )
422 {
423 ras.min_ex = ras.max_ex = 0;
424 ras.min_ey = ras.max_ey = 0;
425 return;
426 }
427
428 ras.min_ex = ras.max_ex = vec->x;
429 ras.min_ey = ras.max_ey = vec->y;
430
431 vec++;
432
433 for ( ; vec < limit; vec++ )
434 {
435 TPos x = vec->x;
436 TPos y = vec->y;
437
438
439 if ( x < ras.min_ex ) ras.min_ex = x;
440 if ( x > ras.max_ex ) ras.max_ex = x;
441 if ( y < ras.min_ey ) ras.min_ey = y;
442 if ( y > ras.max_ey ) ras.max_ey = y;
443 }
444
445 /* truncate the bounding box to integer pixels */
446 ras.min_ex = ras.min_ex >> 6;
447 ras.min_ey = ras.min_ey >> 6;
448 ras.max_ex = ( ras.max_ex + 63 ) >> 6;
449 ras.max_ey = ( ras.max_ey + 63 ) >> 6;
450 }
451
452
453 /*************************************************************************/
454 /* */
455 /* Record the current cell in the table. */
456 /* */
457 static PCell
458 gray_find_cell( RAS_ARG )
459 {
460 PCell *pcell, cell;
461 TPos x = ras.ex;
462
463
464 if ( x > ras.count_ex )
465 x = ras.count_ex;
466
467 pcell = &ras.ycells[ras.ey];
468 for (;;)
469 {
470 cell = *pcell;
471 if ( cell == NULL || cell->x > x )
472 break;
473
474 if ( cell->x == x )
475 goto Exit;
476
477 pcell = &cell->next;
478 }
479
480 if ( ras.num_cells >= ras.max_cells )
481 ft_longjmp( ras.jump_buffer, 1 );
482
483 cell = ras.cells + ras.num_cells++;
484 cell->x = x;
485 cell->area = 0;
486 cell->cover = 0;
487
488 cell->next = *pcell;
489 *pcell = cell;
490
491 Exit:
492 return cell;
493 }
494
495
496 static void
497 gray_record_cell( RAS_ARG )
498 {
499 if ( !ras.invalid && ( ras.area | ras.cover ) )
500 {
501 PCell cell = gray_find_cell( RAS_VAR );
502
503
504 cell->area += ras.area;
505 cell->cover += ras.cover;
506 }
507 }
508
509
510 /*************************************************************************/
511 /* */
512 /* Set the current cell to a new position. */
513 /* */
514 static void
515 gray_set_cell( RAS_ARG_ TCoord ex,
516 TCoord ey )
517 {
518 /* Move the cell pointer to a new position. We set the `invalid' */
519 /* flag to indicate that the cell isn't part of those we're interested */
520 /* in during the render phase. This means that: */
521 /* */
522 /* . the new vertical position must be within min_ey..max_ey-1. */
523 /* . the new horizontal position must be strictly less than max_ex */
524 /* */
525 /* Note that if a cell is to the left of the clipping region, it is */
526 /* actually set to the (min_ex-1) horizontal position. */
527
528 /* All cells that are on the left of the clipping region go to the */
529 /* min_ex - 1 horizontal position. */
530 ey -= ras.min_ey;
531
532 if ( ex > ras.max_ex )
533 ex = ras.max_ex;
534
535 ex -= ras.min_ex;
536 if ( ex < 0 )
537 ex = -1;
538
539 /* are we moving to a different cell ? */
540 if ( ex != ras.ex || ey != ras.ey )
541 {
542 /* record the current one if it is valid */
543 if ( !ras.invalid )
544 gray_record_cell( RAS_VAR );
545
546 ras.area = 0;
547 ras.cover = 0;
548 }
549
550 ras.ex = ex;
551 ras.ey = ey;
552 ras.invalid = ( (unsigned)ey >= (unsigned)ras.count_ey ||
553 ex >= ras.count_ex );
554 }
555
556
557 /*************************************************************************/
558 /* */
559 /* Start a new contour at a given cell. */
560 /* */
561 static void
562 gray_start_cell( RAS_ARG_ TCoord ex,
563 TCoord ey )
564 {
565 if ( ex > ras.max_ex )
566 ex = (TCoord)( ras.max_ex );
567
568 if ( ex < ras.min_ex )
569 ex = (TCoord)( ras.min_ex - 1 );
570
571 ras.area = 0;
572 ras.cover = 0;
573 ras.ex = ex - ras.min_ex;
574 ras.ey = ey - ras.min_ey;
575 ras.last_ey = SUBPIXELS( ey );
576 ras.invalid = 0;
577
578 gray_set_cell( RAS_VAR_ ex, ey );
579 }
580
581
582 /*************************************************************************/
583 /* */
584 /* Render a scanline as one or more cells. */
585 /* */
586 static void
587 gray_render_scanline( RAS_ARG_ TCoord ey,
588 TPos x1,
589 TCoord y1,
590 TPos x2,
591 TCoord y2 )
592 {
593 TCoord ex1, ex2, fx1, fx2, delta, mod, lift, rem;
594 long p, first, dx;
595 int incr;
596
597
598 dx = x2 - x1;
599
600 ex1 = TRUNC( x1 );
601 ex2 = TRUNC( x2 );
602 fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );
603 fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );
604
605 /* trivial case. Happens often */
606 if ( y1 == y2 )
607 {
608 gray_set_cell( RAS_VAR_ ex2, ey );
609 return;
610 }
611
612 /* everything is located in a single cell. That is easy! */
613 /* */
614 if ( ex1 == ex2 )
615 {
616 delta = y2 - y1;
617 ras.area += (TArea)(( fx1 + fx2 ) * delta);
618 ras.cover += delta;
619 return;
620 }
621
622 /* ok, we'll have to render a run of adjacent cells on the same */
623 /* scanline... */
624 /* */
625 p = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
626 first = ONE_PIXEL;
627 incr = 1;
628
629 if ( dx < 0 )
630 {
631 p = fx1 * ( y2 - y1 );
632 first = 0;
633 incr = -1;
634 dx = -dx;
635 }
636
637 delta = (TCoord)( p / dx );
638 mod = (TCoord)( p % dx );
639 if ( mod < 0 )
640 {
641 delta--;
642 mod += (TCoord)dx;
643 }
644
645 ras.area += (TArea)(( fx1 + first ) * delta);
646 ras.cover += delta;
647
648 ex1 += incr;
649 gray_set_cell( RAS_VAR_ ex1, ey );
650 y1 += delta;
651
652 if ( ex1 != ex2 )
653 {
654 p = ONE_PIXEL * ( y2 - y1 + delta );
655 lift = (TCoord)( p / dx );
656 rem = (TCoord)( p % dx );
657 if ( rem < 0 )
658 {
659 lift--;
660 rem += (TCoord)dx;
661 }
662
663 mod -= (int)dx;
664
665 while ( ex1 != ex2 )
666 {
667 delta = lift;
668 mod += rem;
669 if ( mod >= 0 )
670 {
671 mod -= (TCoord)dx;
672 delta++;
673 }
674
675 ras.area += (TArea)(ONE_PIXEL * delta);
676 ras.cover += delta;
677 y1 += delta;
678 ex1 += incr;
679 gray_set_cell( RAS_VAR_ ex1, ey );
680 }
681 }
682
683 delta = y2 - y1;
684 ras.area += (TArea)(( fx2 + ONE_PIXEL - first ) * delta);
685 ras.cover += delta;
686 }
687
688
689 /*************************************************************************/
690 /* */
691 /* Render a given line as a series of scanlines. */
692 /* */
693 static void
694 gray_render_line( RAS_ARG_ TPos to_x,
695 TPos to_y )
696 {
697 TCoord ey1, ey2, fy1, fy2, mod;
698 TPos dx, dy, x, x2;
699 long p, first;
700 int delta, rem, lift, incr;
701
702
703 ey1 = TRUNC( ras.last_ey );
704 ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
705 fy1 = (TCoord)( ras.y - ras.last_ey );
706 fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );
707
708 dx = to_x - ras.x;
709 dy = to_y - ras.y;
710
711 /* XXX: we should do something about the trivial case where dx == 0, */
712 /* as it happens very often! */
713
714 /* perform vertical clipping */
715 {
716 TCoord min, max;
717
718
719 min = ey1;
720 max = ey2;
721 if ( ey1 > ey2 )
722 {
723 min = ey2;
724 max = ey1;
725 }
726 if ( min >= ras.max_ey || max < ras.min_ey )
727 goto End;
728 }
729
730 /* everything is on a single scanline */
731 if ( ey1 == ey2 )
732 {
733 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );
734 goto End;
735 }
736
737 /* vertical line - avoid calling gray_render_scanline */
738 incr = 1;
739
740 if ( dx == 0 )
741 {
742 TCoord ex = TRUNC( ras.x );
743 TCoord two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );
744 TArea area;
745
746
747 first = ONE_PIXEL;
748 if ( dy < 0 )
749 {
750 first = 0;
751 incr = -1;
752 }
753
754 delta = (int)( first - fy1 );
755 ras.area += (TArea)two_fx * delta;
756 ras.cover += delta;
757 ey1 += incr;
758
759 gray_set_cell( RAS_VAR_ ex, ey1 );
760
761 delta = (int)( first + first - ONE_PIXEL );
762 area = (TArea)two_fx * delta;
763 while ( ey1 != ey2 )
764 {
765 ras.area += area;
766 ras.cover += delta;
767 ey1 += incr;
768
769 gray_set_cell( RAS_VAR_ ex, ey1 );
770 }
771
772 delta = (int)( fy2 - ONE_PIXEL + first );
773 ras.area += (TArea)two_fx * delta;
774 ras.cover += delta;
775
776 goto End;
777 }
778
779 /* ok, we have to render several scanlines */
780 p = ( ONE_PIXEL - fy1 ) * dx;
781 first = ONE_PIXEL;
782 incr = 1;
783
784 if ( dy < 0 )
785 {
786 p = fy1 * dx;
787 first = 0;
788 incr = -1;
789 dy = -dy;
790 }
791
792 delta = (int)( p / dy );
793 mod = (int)( p % dy );
794 if ( mod < 0 )
795 {
796 delta--;
797 mod += (TCoord)dy;
798 }
799
800 x = ras.x + delta;
801 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );
802
803 ey1 += incr;
804 gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
805
806 if ( ey1 != ey2 )
807 {
808 p = ONE_PIXEL * dx;
809 lift = (int)( p / dy );
810 rem = (int)( p % dy );
811 if ( rem < 0 )
812 {
813 lift--;
814 rem += (int)dy;
815 }
816 mod -= (int)dy;
817
818 while ( ey1 != ey2 )
819 {
820 delta = lift;
821 mod += rem;
822 if ( mod >= 0 )
823 {
824 mod -= (int)dy;
825 delta++;
826 }
827
828 x2 = x + delta;
829 gray_render_scanline( RAS_VAR_ ey1, x,
830 (TCoord)( ONE_PIXEL - first ), x2,
831 (TCoord)first );
832 x = x2;
833
834 ey1 += incr;
835 gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );
836 }
837 }
838
839 gray_render_scanline( RAS_VAR_ ey1, x,
840 (TCoord)( ONE_PIXEL - first ), to_x,
841 fy2 );
842
843 End:
844 ras.x = to_x;
845 ras.y = to_y;
846 ras.last_ey = SUBPIXELS( ey2 );
847 }
848
849
850 static void
851 gray_split_conic( FT_Vector* base )
852 {
853 TPos a, b;
854
855
856 base[4].x = base[2].x;
857 b = base[1].x;
858 a = base[3].x = ( base[2].x + b ) / 2;
859 b = base[1].x = ( base[0].x + b ) / 2;
860 base[2].x = ( a + b ) / 2;
861
862 base[4].y = base[2].y;
863 b = base[1].y;
864 a = base[3].y = ( base[2].y + b ) / 2;
865 b = base[1].y = ( base[0].y + b ) / 2;
866 base[2].y = ( a + b ) / 2;
867 }
868
869
870 static void
871 gray_render_conic( RAS_ARG_ const FT_Vector* control,
872 const FT_Vector* to )
873 {
874 TPos dx, dy;
875 int top, level;
876 int* levels;
877 FT_Vector* arc;
878
879
880 arc = ras.bez_stack;
881 arc[0].x = UPSCALE( to->x );
882 arc[0].y = UPSCALE( to->y );
883 arc[1].x = UPSCALE( control->x );
884 arc[1].y = UPSCALE( control->y );
885 arc[2].x = ras.x;
886 arc[2].y = ras.y;
887
888 dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x );
889 dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y );
890 if ( dx < dy )
891 dx = dy;
892
893 if ( dx <= ONE_PIXEL / 4 )
894 {
895 gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
896 return;
897 }
898
899 level = 0;
900 while ( dx > ONE_PIXEL / 4 )
901 {
902 dx >>= 2;
903 level++;
904 }
905
906 levels = ras.lev_stack;
907 levels[0] = level;
908 top = 0;
909
910 while ( top >= 0 )
911 {
912 level = levels[top];
913 if ( level > 1 )
914 {
915 /* check that the arc crosses the current band */
916 TPos min, max, y;
917
918
919 min = max = arc[0].y;
920
921 y = arc[1].y;
922 if ( y < min ) min = y;
923 if ( y > max ) max = y;
924
925 y = arc[2].y;
926 if ( y < min ) min = y;
927 if ( y > max ) max = y;
928
929 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
930 goto Draw;
931
932 gray_split_conic( arc );
933 arc += 2;
934 top++;
935 levels[top] = levels[top - 1] = level - 1;
936 continue;
937 }
938
939 Draw:
940 gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
941 top--;
942 arc -= 2;
943 }
944
945 return;
946 }
947
948
949 static void
950 gray_split_cubic( FT_Vector* base )
951 {
952 TPos a, b, c, d;
953
954
955 base[6].x = base[3].x;
956 c = base[1].x;
957 d = base[2].x;
958 base[1].x = a = ( base[0].x + c ) / 2;
959 base[5].x = b = ( base[3].x + d ) / 2;
960 c = ( c + d ) / 2;
961 base[2].x = a = ( a + c ) / 2;
962 base[4].x = b = ( b + c ) / 2;
963 base[3].x = ( a + b ) / 2;
964
965 base[6].y = base[3].y;
966 c = base[1].y;
967 d = base[2].y;
968 base[1].y = a = ( base[0].y + c ) / 2;
969 base[5].y = b = ( base[3].y + d ) / 2;
970 c = ( c + d ) / 2;
971 base[2].y = a = ( a + c ) / 2;
972 base[4].y = b = ( b + c ) / 2;
973 base[3].y = ( a + b ) / 2;
974 }
975
976
977 static void
978 gray_render_cubic( RAS_ARG_ const FT_Vector* control1,
979 const FT_Vector* control2,
980 const FT_Vector* to )
981 {
982 FT_Vector* arc;
983
984
985 arc = ras.bez_stack;
986 arc[0].x = UPSCALE( to->x );
987 arc[0].y = UPSCALE( to->y );
988 arc[1].x = UPSCALE( control2->x );
989 arc[1].y = UPSCALE( control2->y );
990 arc[2].x = UPSCALE( control1->x );
991 arc[2].y = UPSCALE( control1->y );
992 arc[3].x = ras.x;
993 arc[3].y = ras.y;
994
995 for (;;)
996 {
997 /* Check that the arc crosses the current band. */
998 TPos min, max, y;
999
1000
1001 min = max = arc[0].y;
1002
1003 y = arc[1].y;
1004 if ( y < min )
1005 min = y;
1006 if ( y > max )
1007 max = y;
1008
1009 y = arc[2].y;
1010 if ( y < min )
1011 min = y;
1012 if ( y > max )
1013 max = y;
1014
1015 y = arc[3].y;
1016 if ( y < min )
1017 min = y;
1018 if ( y > max )
1019 max = y;
1020
1021 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )
1022 goto Draw;
1023
1024 /* Decide whether to split or draw. See `Rapid Termination */
1025 /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
1026 /* F. Hain, at */
1027 /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
1028
1029 {
1030 TPos dx, dy, dx_, dy_;
1031 TPos dx1, dy1, dx2, dy2;
1032 TPos L, s, s_limit;
1033
1034
1035 /* dx and dy are x and y components of the P0-P3 chord vector. */
1036 dx = arc[3].x - arc[0].x;
1037 dy = arc[3].y - arc[0].y;
1038
1039 /* L is an (under)estimate of the Euclidean distance P0-P3. */
1040 /* */
1041 /* If dx >= dy, then r = sqrt(dx^2 + dy^2) can be overestimated */
1042 /* with least maximum error by */
1043 /* */
1044 /* r_upperbound = dx + (sqrt(2) - 1) * dy , */
1045 /* */
1046 /* where sqrt(2) - 1 can be (over)estimated by 107/256, giving an */
1047 /* error of no more than 8.4%. */
1048 /* */
1049 /* Similarly, some elementary calculus shows that r can be */
1050 /* underestimated with least maximum error by */
1051 /* */
1052 /* r_lowerbound = sqrt(2 + sqrt(2)) / 2 * dx */
1053 /* + sqrt(2 - sqrt(2)) / 2 * dy . */
1054 /* */
1055 /* 236/256 and 97/256 are (under)estimates of the two algebraic */
1056 /* numbers, giving an error of no more than 8.1%. */
1057
1058 dx_ = FT_ABS( dx );
1059 dy_ = FT_ABS( dy );
1060
1061 /* This is the same as */
1062 /* */
1063 /* L = ( 236 * FT_MAX( dx_, dy_ ) */
1064 /* + 97 * FT_MIN( dx_, dy_ ) ) >> 8; */
1065 L = ( dx_ > dy_ ? 236 * dx_ + 97 * dy_
1066 : 97 * dx_ + 236 * dy_ ) >> 8;
1067
1068 /* Avoid possible arithmetic overflow below by splitting. */
1069 if ( L > 32767 )
1070 goto Split;
1071
1072 /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */
1073 s_limit = L * (TPos)( ONE_PIXEL / 6 );
1074
1075 /* s is L * the perpendicular distance from P1 to the line P0-P3. */
1076 dx1 = arc[1].x - arc[0].x;
1077 dy1 = arc[1].y - arc[0].y;
1078 s = FT_ABS( dy * dx1 - dx * dy1 );
1079
1080 if ( s > s_limit )
1081 goto Split;
1082
1083 /* s is L * the perpendicular distance from P2 to the line P0-P3. */
1084 dx2 = arc[2].x - arc[0].x;
1085 dy2 = arc[2].y - arc[0].y;
1086 s = FT_ABS( dy * dx2 - dx * dy2 );
1087
1088 if ( s > s_limit )
1089 goto Split;
1090
1091 /* If P1 or P2 is outside P0-P3, split the curve. */
1092 if ( dy * dy1 + dx * dx1 < 0 ||
1093 dy * dy2 + dx * dx2 < 0 ||
1094 dy * (arc[3].y - arc[1].y) + dx * (arc[3].x - arc[1].x) < 0 ||
1095 dy * (arc[3].y - arc[2].y) + dx * (arc[3].x - arc[2].x) < 0 )
1096 goto Split;
1097
1098 /* No reason to split. */
1099 goto Draw;
1100 }
1101
1102 Split:
1103 gray_split_cubic( arc );
1104 arc += 3;
1105 continue;
1106
1107 Draw:
1108 gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
1109
1110 if ( arc == ras.bez_stack )
1111 return;
1112
1113 arc -= 3;
1114 }
1115 }
1116
1117
1118 static int
1119 gray_move_to( const FT_Vector* to,
1120 PWorker worker )
1121 {
1122 TPos x, y;
1123
1124
1125 /* record current cell, if any */
1126 gray_record_cell( RAS_VAR );
1127
1128 /* start to a new position */
1129 x = UPSCALE( to->x );
1130 y = UPSCALE( to->y );
1131
1132 gray_start_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) );
1133
1134 worker->x = x;
1135 worker->y = y;
1136 return 0;
1137 }
1138
1139
1140 static int
1141 gray_line_to( const FT_Vector* to,
1142 PWorker worker )
1143 {
1144 gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) );
1145 return 0;
1146 }
1147
1148
1149 static int
1150 gray_conic_to( const FT_Vector* control,
1151 const FT_Vector* to,
1152 PWorker worker )
1153 {
1154 gray_render_conic( RAS_VAR_ control, to );
1155 return 0;
1156 }
1157
1158
1159 static int
1160 gray_cubic_to( const FT_Vector* control1,
1161 const FT_Vector* control2,
1162 const FT_Vector* to,
1163 PWorker worker )
1164 {
1165 gray_render_cubic( RAS_VAR_ control1, control2, to );
1166 return 0;
1167 }
1168
1169
1170 static void
1171 gray_render_span( int y,
1172 int count,
1173 const FT_Span* spans,
1174 PWorker worker )
1175 {
1176 unsigned char* p;
1177 FT_Bitmap* map = &worker->target;
1178
1179
1180 /* first of all, compute the scanline offset */
1181 p = (unsigned char*)map->buffer - y * map->pitch;
1182 if ( map->pitch >= 0 )
1183 p += (unsigned)( ( map->rows - 1 ) * map->pitch );
1184
1185 for ( ; count > 0; count--, spans++ )
1186 {
1187 unsigned char coverage = spans->coverage;
1188
1189
1190 if ( coverage )
1191 {
1192 /* For small-spans it is faster to do it by ourselves than
1193 * calling `memset'. This is mainly due to the cost of the
1194 * function call.
1195 */
1196 if ( spans->len >= 8 )
1197 FT_MEM_SET( p + spans->x, (unsigned char)coverage, spans->len );
1198 else
1199 {
1200 unsigned char* q = p + spans->x;
1201
1202
1203 switch ( spans->len )
1204 {
1205 case 7: *q++ = (unsigned char)coverage;
1206 case 6: *q++ = (unsigned char)coverage;
1207 case 5: *q++ = (unsigned char)coverage;
1208 case 4: *q++ = (unsigned char)coverage;
1209 case 3: *q++ = (unsigned char)coverage;
1210 case 2: *q++ = (unsigned char)coverage;
1211 case 1: *q = (unsigned char)coverage;
1212 default:
1213 ;
1214 }
1215 }
1216 }
1217 }
1218 }
1219
1220
1221 static void
1222 gray_hline( RAS_ARG_ TCoord x,
1223 TCoord y,
1224 TPos area,
1225 TCoord acount )
1226 {
1227 FT_Span* span;
1228 int count;
1229 int coverage;
1230
1231
1232 /* compute the coverage line's coverage, depending on the */
1233 /* outline fill rule */
1234 /* */
1235 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1236 /* */
1237 coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1238 /* use range 0..256 */
1239 if ( coverage < 0 )
1240 coverage = -coverage;
1241
1242 if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL )
1243 {
1244 coverage &= 511;
1245
1246 if ( coverage > 256 )
1247 coverage = 512 - coverage;
1248 else if ( coverage == 256 )
1249 coverage = 255;
1250 }
1251 else
1252 {
1253 /* normal non-zero winding rule */
1254 if ( coverage >= 256 )
1255 coverage = 255;
1256 }
1257
1258 y += (TCoord)ras.min_ey;
1259 x += (TCoord)ras.min_ex;
1260
1261 /* FT_Span.x is a 16-bit short, so limit our coordinates appropriately */
1262 if ( x >= 32767 )
1263 x = 32767;
1264
1265 /* FT_Span.y is an integer, so limit our coordinates appropriately */
1266 if ( y >= FT_INT_MAX )
1267 y = FT_INT_MAX;
1268
1269 if ( coverage )
1270 {
1271 /* see whether we can add this span to the current list */
1272 count = ras.num_gray_spans;
1273 span = ras.gray_spans + count - 1;
1274 if ( count > 0 &&
1275 ras.span_y == y &&
1276 (int)span->x + span->len == (int)x &&
1277 span->coverage == coverage )
1278 {
1279 span->len = (unsigned short)( span->len + acount );
1280 return;
1281 }
1282
1283 if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
1284 {
1285 if ( ras.render_span && count > 0 )
1286 ras.render_span( ras.span_y, count, ras.gray_spans,
1287 ras.render_span_data );
1288
1289 #ifdef FT_DEBUG_LEVEL_TRACE
1290
1291 if ( count > 0 )
1292 {
1293 int n;
1294
1295
1296 FT_TRACE7(( "y = %3d ", ras.span_y ));
1297 span = ras.gray_spans;
1298 for ( n = 0; n < count; n++, span++ )
1299 FT_TRACE7(( "[%d..%d]:%02x ",
1300 span->x, span->x + span->len - 1, span->coverage ));
1301 FT_TRACE7(( "\n" ));
1302 }
1303
1304 #endif /* FT_DEBUG_LEVEL_TRACE */
1305
1306 ras.num_gray_spans = 0;
1307 ras.span_y = (int)y;
1308
1309 count = 0;
1310 span = ras.gray_spans;
1311 }
1312 else
1313 span++;
1314
1315 /* add a gray span to the current list */
1316 span->x = (short)x;
1317 span->len = (unsigned short)acount;
1318 span->coverage = (unsigned char)coverage;
1319
1320 ras.num_gray_spans++;
1321 }
1322 }
1323
1324
1325 #ifdef FT_DEBUG_LEVEL_TRACE
1326
1327 /* to be called while in the debugger -- */
1328 /* this function causes a compiler warning since it is unused otherwise */
1329 static void
1330 gray_dump_cells( RAS_ARG )
1331 {
1332 int yindex;
1333
1334
1335 for ( yindex = 0; yindex < ras.ycount; yindex++ )
1336 {
1337 PCell cell;
1338
1339
1340 printf( "%3d:", yindex );
1341
1342 for ( cell = ras.ycells[yindex]; cell != NULL; cell = cell->next )
1343 printf( " (%3ld, c:%4ld, a:%6d)", cell->x, cell->cover, cell->area );
1344 printf( "\n" );
1345 }
1346 }
1347
1348 #endif /* FT_DEBUG_LEVEL_TRACE */
1349
1350
1351 static void
1352 gray_sweep( RAS_ARG_ const FT_Bitmap* target )
1353 {
1354 int yindex;
1355
1356 FT_UNUSED( target );
1357
1358
1359 if ( ras.num_cells == 0 )
1360 return;
1361
1362 ras.num_gray_spans = 0;
1363
1364 FT_TRACE7(( "gray_sweep: start\n" ));
1365
1366 for ( yindex = 0; yindex < ras.ycount; yindex++ )
1367 {
1368 PCell cell = ras.ycells[yindex];
1369 TCoord cover = 0;
1370 TCoord x = 0;
1371
1372
1373 for ( ; cell != NULL; cell = cell->next )
1374 {
1375 TPos area;
1376
1377
1378 if ( cell->x > x && cover != 0 )
1379 gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1380 cell->x - x );
1381
1382 cover += cell->cover;
1383 area = cover * ( ONE_PIXEL * 2 ) - cell->area;
1384
1385 if ( area != 0 && cell->x >= 0 )
1386 gray_hline( RAS_VAR_ cell->x, yindex, area, 1 );
1387
1388 x = cell->x + 1;
1389 }
1390
1391 if ( cover != 0 )
1392 gray_hline( RAS_VAR_ x, yindex, cover * ( ONE_PIXEL * 2 ),
1393 ras.count_ex - x );
1394 }
1395
1396 if ( ras.render_span && ras.num_gray_spans > 0 )
1397 ras.render_span( ras.span_y, ras.num_gray_spans,
1398 ras.gray_spans, ras.render_span_data );
1399
1400 FT_TRACE7(( "gray_sweep: end\n" ));
1401 }
1402
1403
1404 #ifdef _STANDALONE_
1405
1406 /*************************************************************************/
1407 /* */
1408 /* The following function should only compile in stand-alone mode, */
1409 /* i.e., when building this component without the rest of FreeType. */
1410 /* */
1411 /*************************************************************************/
1412
1413 /*************************************************************************/
1414 /* */
1415 /* <Function> */
1416 /* FT_Outline_Decompose */
1417 /* */
1418 /* <Description> */
1419 /* Walk over an outline's structure to decompose it into individual */
1420 /* segments and Bézier arcs. This function is also able to emit */
1421 /* `move to' and `close to' operations to indicate the start and end */
1422 /* of new contours in the outline. */
1423 /* */
1424 /* <Input> */
1425 /* outline :: A pointer to the source target. */
1426 /* */
1427 /* func_interface :: A table of `emitters', i.e., function pointers */
1428 /* called during decomposition to indicate path */
1429 /* operations. */
1430 /* */
1431 /* <InOut> */
1432 /* user :: A typeless pointer which is passed to each */
1433 /* emitter during the decomposition. It can be */
1434 /* used to store the state during the */
1435 /* decomposition. */
1436 /* */
1437 /* <Return> */
1438 /* Error code. 0 means success. */
1439 /* */
1440 static int
1441 FT_Outline_Decompose( const FT_Outline* outline,
1442 const FT_Outline_Funcs* func_interface,
1443 void* user )
1444 {
1445 #undef SCALED
1446 #define SCALED( x ) ( ( (x) << shift ) - delta )
1447
1448 FT_Vector v_last;
1449 FT_Vector v_control;
1450 FT_Vector v_start;
1451
1452 FT_Vector* point;
1453 FT_Vector* limit;
1454 char* tags;
1455
1456 int error;
1457
1458 int n; /* index of contour in outline */
1459 int first; /* index of first point in contour */
1460 char tag; /* current point's state */
1461
1462 int shift;
1463 TPos delta;
1464
1465
1466 if ( !outline || !func_interface )
1467 return ErrRaster_Invalid_Argument;
1468
1469 shift = func_interface->shift;
1470 delta = func_interface->delta;
1471 first = 0;
1472
1473 for ( n = 0; n < outline->n_contours; n++ )
1474 {
1475 int last; /* index of last point in contour */
1476
1477
1478 FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));
1479
1480 last = outline->contours[n];
1481 if ( last < 0 )
1482 goto Invalid_Outline;
1483 limit = outline->points + last;
1484
1485 v_start = outline->points[first];
1486 v_start.x = SCALED( v_start.x );
1487 v_start.y = SCALED( v_start.y );
1488
1489 v_last = outline->points[last];
1490 v_last.x = SCALED( v_last.x );
1491 v_last.y = SCALED( v_last.y );
1492
1493 v_control = v_start;
1494
1495 point = outline->points + first;
1496 tags = outline->tags + first;
1497 tag = FT_CURVE_TAG( tags[0] );
1498
1499 /* A contour cannot start with a cubic control point! */
1500 if ( tag == FT_CURVE_TAG_CUBIC )
1501 goto Invalid_Outline;
1502
1503 /* check first point to determine origin */
1504 if ( tag == FT_CURVE_TAG_CONIC )
1505 {
1506 /* first point is conic control. Yes, this happens. */
1507 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
1508 {
1509 /* start at last point if it is on the curve */
1510 v_start = v_last;
1511 limit--;
1512 }
1513 else
1514 {
1515 /* if both first and last points are conic, */
1516 /* start at their middle and record its position */
1517 /* for closure */
1518 v_start.x = ( v_start.x + v_last.x ) / 2;
1519 v_start.y = ( v_start.y + v_last.y ) / 2;
1520
1521 v_last = v_start;
1522 }
1523 point--;
1524 tags--;
1525 }
1526
1527 FT_TRACE5(( " move to (%.2f, %.2f)\n",
1528 v_start.x / 64.0, v_start.y / 64.0 ));
1529 error = func_interface->move_to( &v_start, user );
1530 if ( error )
1531 goto Exit;
1532
1533 while ( point < limit )
1534 {
1535 point++;
1536 tags++;
1537
1538 tag = FT_CURVE_TAG( tags[0] );
1539 switch ( tag )
1540 {
1541 case FT_CURVE_TAG_ON: /* emit a single line_to */
1542 {
1543 FT_Vector vec;
1544
1545
1546 vec.x = SCALED( point->x );
1547 vec.y = SCALED( point->y );
1548
1549 FT_TRACE5(( " line to (%.2f, %.2f)\n",
1550 vec.x / 64.0, vec.y / 64.0 ));
1551 error = func_interface->line_to( &vec, user );
1552 if ( error )
1553 goto Exit;
1554 continue;
1555 }
1556
1557 case FT_CURVE_TAG_CONIC: /* consume conic arcs */
1558 v_control.x = SCALED( point->x );
1559 v_control.y = SCALED( point->y );
1560
1561 Do_Conic:
1562 if ( point < limit )
1563 {
1564 FT_Vector vec;
1565 FT_Vector v_middle;
1566
1567
1568 point++;
1569 tags++;
1570 tag = FT_CURVE_TAG( tags[0] );
1571
1572 vec.x = SCALED( point->x );
1573 vec.y = SCALED( point->y );
1574
1575 if ( tag == FT_CURVE_TAG_ON )
1576 {
1577 FT_TRACE5(( " conic to (%.2f, %.2f)"
1578 " with control (%.2f, %.2f)\n",
1579 vec.x / 64.0, vec.y / 64.0,
1580 v_control.x / 64.0, v_control.y / 64.0 ));
1581 error = func_interface->conic_to( &v_control, &vec, user );
1582 if ( error )
1583 goto Exit;
1584 continue;
1585 }
1586
1587 if ( tag != FT_CURVE_TAG_CONIC )
1588 goto Invalid_Outline;
1589
1590 v_middle.x = ( v_control.x + vec.x ) / 2;
1591 v_middle.y = ( v_control.y + vec.y ) / 2;
1592
1593 FT_TRACE5(( " conic to (%.2f, %.2f)"
1594 " with control (%.2f, %.2f)\n",
1595 v_middle.x / 64.0, v_middle.y / 64.0,
1596 v_control.x / 64.0, v_control.y / 64.0 ));
1597 error = func_interface->conic_to( &v_control, &v_middle, user );
1598 if ( error )
1599 goto Exit;
1600
1601 v_control = vec;
1602 goto Do_Conic;
1603 }
1604
1605 FT_TRACE5(( " conic to (%.2f, %.2f)"
1606 " with control (%.2f, %.2f)\n",
1607 v_start.x / 64.0, v_start.y / 64.0,
1608 v_control.x / 64.0, v_control.y / 64.0 ));
1609 error = func_interface->conic_to( &v_control, &v_start, user );
1610 goto Close;
1611
1612 default: /* FT_CURVE_TAG_CUBIC */
1613 {
1614 FT_Vector vec1, vec2;
1615
1616
1617 if ( point + 1 > limit ||
1618 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
1619 goto Invalid_Outline;
1620
1621 point += 2;
1622 tags += 2;
1623
1624 vec1.x = SCALED( point[-2].x );
1625 vec1.y = SCALED( point[-2].y );
1626
1627 vec2.x = SCALED( point[-1].x );
1628 vec2.y = SCALED( point[-1].y );
1629
1630 if ( point <= limit )
1631 {
1632 FT_Vector vec;
1633
1634
1635 vec.x = SCALED( point->x );
1636 vec.y = SCALED( point->y );
1637
1638 FT_TRACE5(( " cubic to (%.2f, %.2f)"
1639 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1640 vec.x / 64.0, vec.y / 64.0,
1641 vec1.x / 64.0, vec1.y / 64.0,
1642 vec2.x / 64.0, vec2.y / 64.0 ));
1643 error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
1644 if ( error )
1645 goto Exit;
1646 continue;
1647 }
1648
1649 FT_TRACE5(( " cubic to (%.2f, %.2f)"
1650 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1651 v_start.x / 64.0, v_start.y / 64.0,
1652 vec1.x / 64.0, vec1.y / 64.0,
1653 vec2.x / 64.0, vec2.y / 64.0 ));
1654 error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
1655 goto Close;
1656 }
1657 }
1658 }
1659
1660 /* close the contour with a line segment */
1661 FT_TRACE5(( " line to (%.2f, %.2f)\n",
1662 v_start.x / 64.0, v_start.y / 64.0 ));
1663 error = func_interface->line_to( &v_start, user );
1664
1665 Close:
1666 if ( error )
1667 goto Exit;
1668
1669 first = last + 1;
1670 }
1671
1672 FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
1673 return 0;
1674
1675 Exit:
1676 FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
1677 return error;
1678
1679 Invalid_Outline:
1680 return ErrRaster_Invalid_Outline;
1681 }
1682
1683 #endif /* _STANDALONE_ */
1684
1685
1686 typedef struct TBand_
1687 {
1688 TPos min, max;
1689
1690 } TBand;
1691
1692 FT_DEFINE_OUTLINE_FUNCS(func_interface,
1693 (FT_Outline_MoveTo_Func) gray_move_to,
1694 (FT_Outline_LineTo_Func) gray_line_to,
1695 (FT_Outline_ConicTo_Func)gray_conic_to,
1696 (FT_Outline_CubicTo_Func)gray_cubic_to,
1697 0,
1698 0
1699 )
1700
1701 static int
1702 gray_convert_glyph_inner( RAS_ARG )
1703 {
1704
1705 volatile int error = 0;
1706
1707 #ifdef FT_CONFIG_OPTION_PIC
1708 FT_Outline_Funcs func_interface;
1709 Init_Class_func_interface(&func_interface);
1710 #endif
1711
1712 if ( ft_setjmp( ras.jump_buffer ) == 0 )
1713 {
1714 error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras );
1715 gray_record_cell( RAS_VAR );
1716 }
1717 else
1718 error = ErrRaster_Memory_Overflow;
1719
1720 return error;
1721 }
1722
1723
1724 static int
1725 gray_convert_glyph( RAS_ARG )
1726 {
1727 TBand bands[40];
1728 TBand* volatile band;
1729 int volatile n, num_bands;
1730 TPos volatile min, max, max_y;
1731 FT_BBox* clip;
1732
1733
1734 /* Set up state in the raster object */
1735 gray_compute_cbox( RAS_VAR );
1736
1737 /* clip to target bitmap, exit if nothing to do */
1738 clip = &ras.clip_box;
1739
1740 if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1741 ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1742 return 0;
1743
1744 if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1745 if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1746
1747 if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1748 if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1749
1750 ras.count_ex = ras.max_ex - ras.min_ex;
1751 ras.count_ey = ras.max_ey - ras.min_ey;
1752
1753 /* set up vertical bands */
1754 num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1755 if ( num_bands == 0 )
1756 num_bands = 1;
1757 if ( num_bands >= 39 )
1758 num_bands = 39;
1759
1760 ras.band_shoot = 0;
1761
1762 min = ras.min_ey;
1763 max_y = ras.max_ey;
1764
1765 for ( n = 0; n < num_bands; n++, min = max )
1766 {
1767 max = min + ras.band_size;
1768 if ( n == num_bands - 1 || max > max_y )
1769 max = max_y;
1770
1771 bands[0].min = min;
1772 bands[0].max = max;
1773 band = bands;
1774
1775 while ( band >= bands )
1776 {
1777 TPos bottom, top, middle;
1778 int error;
1779
1780 {
1781 PCell cells_max;
1782 int yindex;
1783 long cell_start, cell_end, cell_mod;
1784
1785
1786 ras.ycells = (PCell*)ras.buffer;
1787 ras.ycount = band->max - band->min;
1788
1789 cell_start = sizeof ( PCell ) * ras.ycount;
1790 cell_mod = cell_start % sizeof ( TCell );
1791 if ( cell_mod > 0 )
1792 cell_start += sizeof ( TCell ) - cell_mod;
1793
1794 cell_end = ras.buffer_size;
1795 cell_end -= cell_end % sizeof( TCell );
1796
1797 cells_max = (PCell)( (char*)ras.buffer + cell_end );
1798 ras.cells = (PCell)( (char*)ras.buffer + cell_start );
1799 if ( ras.cells >= cells_max )
1800 goto ReduceBands;
1801
1802 ras.max_cells = cells_max - ras.cells;
1803 if ( ras.max_cells < 2 )
1804 goto ReduceBands;
1805
1806 for ( yindex = 0; yindex < ras.ycount; yindex++ )
1807 ras.ycells[yindex] = NULL;
1808 }
1809
1810 ras.num_cells = 0;
1811 ras.invalid = 1;
1812 ras.min_ey = band->min;
1813 ras.max_ey = band->max;
1814 ras.count_ey = band->max - band->min;
1815
1816 error = gray_convert_glyph_inner( RAS_VAR );
1817
1818 if ( !error )
1819 {
1820 gray_sweep( RAS_VAR_ &ras.target );
1821 band--;
1822 continue;
1823 }
1824 else if ( error != ErrRaster_Memory_Overflow )
1825 return 1;
1826
1827 ReduceBands:
1828 /* render pool overflow; we will reduce the render band by half */
1829 bottom = band->min;
1830 top = band->max;
1831 middle = bottom + ( ( top - bottom ) >> 1 );
1832
1833 /* This is too complex for a single scanline; there must */
1834 /* be some problems. */
1835 if ( middle == bottom )
1836 {
1837 #ifdef FT_DEBUG_LEVEL_TRACE
1838 FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" ));
1839 #endif
1840 return 1;
1841 }
1842
1843 if ( bottom-top >= ras.band_size )
1844 ras.band_shoot++;
1845
1846 band[1].min = bottom;
1847 band[1].max = middle;
1848 band[0].min = middle;
1849 band[0].max = top;
1850 band++;
1851 }
1852 }
1853
1854 if ( ras.band_shoot > 8 && ras.band_size > 16 )
1855 ras.band_size = ras.band_size / 2;
1856
1857 return 0;
1858 }
1859
1860
1861 static int
1862 gray_raster_render( PRaster raster,
1863 const FT_Raster_Params* params )
1864 {
1865 const FT_Outline* outline = (const FT_Outline*)params->source;
1866 const FT_Bitmap* target_map = params->target;
1867 PWorker worker;
1868
1869
1870 if ( !raster || !raster->buffer || !raster->buffer_size )
1871 return ErrRaster_Invalid_Argument;
1872
1873 if ( !outline )
1874 return ErrRaster_Invalid_Outline;
1875
1876 /* return immediately if the outline is empty */
1877 if ( outline->n_points == 0 || outline->n_contours <= 0 )
1878 return 0;
1879
1880 if ( !outline->contours || !outline->points )
1881 return ErrRaster_Invalid_Outline;
1882
1883 if ( outline->n_points !=
1884 outline->contours[outline->n_contours - 1] + 1 )
1885 return ErrRaster_Invalid_Outline;
1886
1887 worker = raster->worker;
1888
1889 /* if direct mode is not set, we must have a target bitmap */
1890 if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) )
1891 {
1892 if ( !target_map )
1893 return ErrRaster_Invalid_Argument;
1894
1895 /* nothing to do */
1896 if ( !target_map->width || !target_map->rows )
1897 return 0;
1898
1899 if ( !target_map->buffer )
1900 return ErrRaster_Invalid_Argument;
1901 }
1902
1903 /* this version does not support monochrome rendering */
1904 if ( !( params->flags & FT_RASTER_FLAG_AA ) )
1905 return ErrRaster_Invalid_Mode;
1906
1907 /* compute clipping box */
1908 if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) )
1909 {
1910 /* compute clip box from target pixmap */
1911 ras.clip_box.xMin = 0;
1912 ras.clip_box.yMin = 0;
1913 ras.clip_box.xMax = target_map->width;
1914 ras.clip_box.yMax = target_map->rows;
1915 }
1916 else if ( params->flags & FT_RASTER_FLAG_CLIP )
1917 ras.clip_box = params->clip_box;
1918 else
1919 {
1920 ras.clip_box.xMin = -32768L;
1921 ras.clip_box.yMin = -32768L;
1922 ras.clip_box.xMax = 32767L;
1923 ras.clip_box.yMax = 32767L;
1924 }
1925
1926 gray_init_cells( RAS_VAR_ raster->buffer, raster->buffer_size );
1927
1928 ras.outline = *outline;
1929 ras.num_cells = 0;
1930 ras.invalid = 1;
1931 ras.band_size = raster->band_size;
1932 ras.num_gray_spans = 0;
1933
1934 if ( params->flags & FT_RASTER_FLAG_DIRECT )
1935 {
1936 ras.render_span = (FT_Raster_Span_Func)params->gray_spans;
1937 ras.render_span_data = params->user;
1938 }
1939 else
1940 {
1941 ras.target = *target_map;
1942 ras.render_span = (FT_Raster_Span_Func)gray_render_span;
1943 ras.render_span_data = &ras;
1944 }
1945
1946 return gray_convert_glyph( RAS_VAR );
1947 }
1948
1949
1950 /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/
1951 /**** a static object. *****/
1952
1953 #ifdef _STANDALONE_
1954
1955 static int
1956 gray_raster_new( void* memory,
1957 FT_Raster* araster )
1958 {
1959 static TRaster the_raster;
1960
1961 FT_UNUSED( memory );
1962
1963
1964 *araster = (FT_Raster)&the_raster;
1965 FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) );
1966
1967 return 0;
1968 }
1969
1970
1971 static void
1972 gray_raster_done( FT_Raster raster )
1973 {
1974 /* nothing */
1975 FT_UNUSED( raster );
1976 }
1977
1978 #else /* !_STANDALONE_ */
1979
1980 static int
1981 gray_raster_new( FT_Memory memory,
1982 FT_Raster* araster )
1983 {
1984 FT_Error error;
1985 PRaster raster = NULL;
1986
1987
1988 *araster = 0;
1989 if ( !FT_ALLOC( raster, sizeof ( TRaster ) ) )
1990 {
1991 raster->memory = memory;
1992 *araster = (FT_Raster)raster;
1993 }
1994
1995 return error;
1996 }
1997
1998
1999 static void
2000 gray_raster_done( FT_Raster raster )
2001 {
2002 FT_Memory memory = (FT_Memory)((PRaster)raster)->memory;
2003
2004
2005 FT_FREE( raster );
2006 }
2007
2008 #endif /* !_STANDALONE_ */
2009
2010
2011 static void
2012 gray_raster_reset( FT_Raster raster,
2013 char* pool_base,
2014 long pool_size )
2015 {
2016 PRaster rast = (PRaster)raster;
2017
2018
2019 if ( raster )
2020 {
2021 if ( pool_base && pool_size >= (long)sizeof ( TWorker ) + 2048 )
2022 {
2023 PWorker worker = (PWorker)pool_base;
2024
2025
2026 rast->worker = worker;
2027 rast->buffer = pool_base +
2028 ( ( sizeof ( TWorker ) + sizeof ( TCell ) - 1 ) &
2029 ~( sizeof ( TCell ) - 1 ) );
2030 rast->buffer_size = (long)( ( pool_base + pool_size ) -
2031 (char*)rast->buffer ) &
2032 ~( sizeof ( TCell ) - 1 );
2033 rast->band_size = (int)( rast->buffer_size /
2034 ( sizeof ( TCell ) * 8 ) );
2035 }
2036 else
2037 {
2038 rast->buffer = NULL;
2039 rast->buffer_size = 0;
2040 rast->worker = NULL;
2041 }
2042 }
2043 }
2044
2045
2046 FT_DEFINE_RASTER_FUNCS(ft_grays_raster,
2047 FT_GLYPH_FORMAT_OUTLINE,
2048
2049 (FT_Raster_New_Func) gray_raster_new,
2050 (FT_Raster_Reset_Func) gray_raster_reset,
2051 (FT_Raster_Set_Mode_Func)0,
2052 (FT_Raster_Render_Func) gray_raster_render,
2053 (FT_Raster_Done_Func) gray_raster_done
2054 )
2055
2056
2057 /* END */
2058
2059
2060 /* Local Variables: */
2061 /* coding: utf-8 */
2062 /* End: */
A free Windows-compatible Operating System