]> git.saurik.com Git - wxWidgets.git/blob - src/freetype/smooth/ftgrays.c
projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
yet another file I added on the wxUniv branch and forgot to merge
[wxWidgets.git] / src / freetype / smooth / ftgrays.c
1 /***************************************************************************/
2 /* */
3 /* ftgrays.c */
4 /* */
5 /* A new `perfect' anti-aliasing renderer (body). */
6 /* */
7 /* Copyright 2000 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, */
21 /* by defining the _STANDALONE_ macro when compiling it. You also need */
22 /* to put the files `ftgrays.h' and `ftimage.h' into the current */
23 /* compilation directory. Typically, you could do something like */
24 /* */
25 /* - copy `src/base/ftgrays.c' to your current directory */
26 /* */
27 /* - copy `include/freetype/ftimage.h' and */
28 /* `include/freetype/ftgrays.h' to the 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_grays_raster.grays_raster_new'; an anti-aliased bitmap can be */
36 /* generated with a call to `ft_grays_raster.grays_raster_render'. */
37 /* */
38 /* See the comments and documentation in the file `ftimage.h' for */
39 /* more 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 */
59 /* doesn't 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 */
64 /* a callback function that will be called by the renderer to draw */
65 /* gray spans on any target surface. You can thus do direct */
66 /* composition on any kind of bitmap, provided that you give the */
67 /* renderer the right 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 #include <string.h> /* for memcpy() */
85
86
87 /*************************************************************************/
88 /* */
89 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
90 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
91 /* messages during execution. */
92 /* */
93 #undef FT_COMPONENT
94 #define FT_COMPONENT trace_aaraster
95
96
97 #ifdef _STANDALONE_
98
99
100 #define ErrRaster_Invalid_Mode -2
101 #define ErrRaster_Invalid_Outline -1
102
103 #include "ftimage.h"
104 #include "ftgrays.h"
105
106 /* This macro is used to indicate that a function parameter is unused. */
107 /* Its purpose is simply to reduce compiler warnings. Note also that */
108 /* simply defining it as `(void)x' doesn't avoid warnings with certain */
109 /* ANSI compilers (e.g. LCC). */
110 #define FT_UNUSED( x ) (x) = (x)
111
112 /* Disable the tracing mechanism for simplicity -- developers can */
113 /* activate it easily by redefining these two macros. */
114 #ifndef FT_ERROR
115 #define FT_ERROR( x ) do ; while ( 0 ) /* nothing */
116 #endif
117
118 #ifndef FT_TRACE
119 #define FT_TRACE( x ) do ; while ( 0 ) /* nothing */
120 #endif
121
122
123 #else /* _STANDALONE_ */
124
125
126 #ifdef FT_FLAT_COMPILE
127
128 #include "ftgrays.h"
129
130 #else
131
132 #include <smooth/ftgrays.h>
133
134 #endif
135
136
137 #include <freetype/internal/ftobjs.h> /* for FT_UNUSED() */
138 #include <freetype/internal/ftdebug.h> /* for FT_TRACE() and FT_ERROR() */
139 #include <freetype/ftoutln.h> /* for FT_Outline_Decompose() */
140
141 #define ErrRaster_Invalid_Mode FT_Err_Cannot_Render_Glyph
142 #define ErrRaster_Invalid_Outline FT_Err_Invalid_Outline
143
144
145 #endif /* _STANDALONE_ */
146
147
148 /* define this to dump debugging information */
149 #define xxxDEBUG_GRAYS
150
151 /* as usual, for the speed hungry :-) */
152
153 #ifndef FT_STATIC_RASTER
154
155
156 #define RAS_ARG PRaster raster
157 #define RAS_ARG_ PRaster raster,
158
159 #define RAS_VAR raster
160 #define RAS_VAR_ raster,
161
162 #define ras (*raster)
163
164
165 #else /* FT_STATIC_RASTER */
166
167
168 #define RAS_ARG /* empty */
169 #define RAS_ARG_ /* empty */
170 #define RAS_VAR /* empty */
171 #define RAS_VAR_ /* empty */
172
173 static TRaster ras;
174
175
176 #endif /* FT_STATIC_RASTER */
177
178
179 /* must be at least 6 bits! */
180 #define PIXEL_BITS 8
181
182 #define ONE_PIXEL ( 1L << PIXEL_BITS )
183 #define PIXEL_MASK ( -1L << PIXEL_BITS )
184 #define TRUNC( x ) ( (x) >> PIXEL_BITS )
185 #define SUBPIXELS( x ) ( (x) << PIXEL_BITS )
186 #define FLOOR( x ) ( (x) & -ONE_PIXEL )
187 #define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )
188 #define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )
189
190 #if PIXEL_BITS >= 6
191 #define UPSCALE( x ) ( (x) << ( PIXEL_BITS - 6 ) )
192 #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
193 #else
194 #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
195 #define DOWNSCALE( x ) ( (x) << ( 6 - PIXEL_BITS ) )
196 #endif
197
198 /* Define this if you want to use a more compact storage scheme. This */
199 /* increases the number of cells available in the render pool but slows */
200 /* down the rendering a bit. It is useful if you have a really tiny */
201 /* render pool. */
202 #define xxxGRAYS_COMPACT
203
204
205 /*************************************************************************/
206 /* */
207 /* TYPE DEFINITIONS */
208 /* */
209 typedef int TScan; /* integer scanline/pixel coordinate */
210 typedef long TPos; /* sub-pixel coordinate */
211
212 /* maximal number of gray spans in a call to the span callback */
213 #define FT_MAX_GRAY_SPANS 32
214
215
216 #ifdef GRAYS_COMPACT
217
218 typedef struct TCell_
219 {
220 short x : 14;
221 short y : 14;
222 int cover : PIXEL_BITS + 2;
223 int area : PIXEL_BITS * 2 + 2;
224
225 } TCell, *PCell;
226
227 #else /* GRAYS_COMPACT */
228
229 typedef struct TCell_
230 {
231 TScan x;
232 TScan y;
233 int cover;
234 int area;
235
236 } TCell, *PCell;
237
238 #endif /* GRAYS_COMPACT */
239
240
241 typedef struct TRaster_
242 {
243 PCell cells;
244 int max_cells;
245 int num_cells;
246
247 TScan min_ex, max_ex;
248 TScan min_ey, max_ey;
249
250 int area;
251 int cover;
252 int invalid;
253
254 TScan ex, ey;
255 TScan cx, cy;
256 TPos x, y;
257
258 TScan last_ey;
259
260 FT_Vector bez_stack[32 * 3];
261 int lev_stack[32];
262
263 FT_Outline outline;
264 FT_Bitmap target;
265
266 FT_Span gray_spans[FT_MAX_GRAY_SPANS];
267 int num_gray_spans;
268
269 FT_Raster_Span_Func render_span;
270 void* render_span_data;
271 int span_y;
272
273 int band_size;
274 int band_shoot;
275 int conic_level;
276 int cubic_level;
277
278 void* memory;
279
280 } TRaster, *PRaster;
281
282
283 /*************************************************************************/
284 /* */
285 /* Initialize the cells table. */
286 /* */
287 static
288 void init_cells( RAS_ARG_ void* buffer,
289 long byte_size )
290 {
291 ras.cells = (PCell)buffer;
292 ras.max_cells = byte_size / sizeof ( TCell );
293 ras.num_cells = 0;
294 ras.area = 0;
295 ras.cover = 0;
296 ras.invalid = 1;
297 }
298
299
300 /*************************************************************************/
301 /* */
302 /* Compute the outline bounding box. */
303 /* */
304 static
305 void compute_cbox( RAS_ARG_ FT_Outline* outline )
306 {
307 FT_Vector* vec = outline->points;
308 FT_Vector* limit = vec + outline->n_points;
309
310
311 if ( outline->n_points <= 0 )
312 {
313 ras.min_ex = ras.max_ex = 0;
314 ras.min_ey = ras.max_ey = 0;
315 return;
316 }
317
318 ras.min_ex = ras.max_ex = vec->x;
319 ras.min_ey = ras.max_ey = vec->y;
320
321 vec++;
322
323 for ( ; vec < limit; vec++ )
324 {
325 TPos x = vec->x;
326 TPos y = vec->y;
327
328
329 if ( x < ras.min_ex ) ras.min_ex = x;
330 if ( x > ras.max_ex ) ras.max_ex = x;
331 if ( y < ras.min_ey ) ras.min_ey = y;
332 if ( y > ras.max_ey ) ras.max_ey = y;
333 }
334
335 /* truncate the bounding box to integer pixels */
336 ras.min_ex = ras.min_ex >> 6;
337 ras.min_ey = ras.min_ey >> 6;
338 ras.max_ex = ( ras.max_ex + 63 ) >> 6;
339 ras.max_ey = ( ras.max_ey + 63 ) >> 6;
340 }
341
342
343 /*************************************************************************/
344 /* */
345 /* Record the current cell in the table. */
346 /* */
347 static
348 int record_cell( RAS_ARG )
349 {
350 PCell cell;
351
352
353 if ( !ras.invalid && ( ras.area | ras.cover ) )
354 {
355 if ( ras.num_cells >= ras.max_cells )
356 return 1;
357
358 cell = ras.cells + ras.num_cells++;
359 cell->x = ras.ex - ras.min_ex;
360 cell->y = ras.ey - ras.min_ey;
361 cell->area = ras.area;
362 cell->cover = ras.cover;
363 }
364
365 return 0;
366 }
367
368
369 /*************************************************************************/
370 /* */
371 /* Set the current cell to a new position. */
372 /* */
373 static
374 int set_cell( RAS_ARG_ TScan ex,
375 TScan ey )
376 {
377 int invalid, record, clean;
378
379
380 /* Move the cell pointer to a new position. We set the `invalid' */
381 /* flag to indicate that the cell isn't part of those we're interested */
382 /* in during the render phase. This means that: */
383 /* */
384 /* . the new vertical position must be within min_ey..max_ey-1. */
385 /* . the new horizontal position must be strictly less than max_ex */
386 /* */
387 /* Note that if a cell is to the left of the clipping region, it is */
388 /* actually set to the (min_ex-1) horizontal position. */
389
390 record = 0;
391 clean = 1;
392
393 invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );
394 if ( !invalid )
395 {
396 /* All cells that are on the left of the clipping region go to the */
397 /* min_ex - 1 horizontal position. */
398 if ( ex < ras.min_ex )
399 ex = ras.min_ex - 1;
400
401 /* if our position is new, then record the previous cell */
402 if ( ex != ras.ex || ey != ras.ey )
403 record = 1;
404 else
405 clean = ras.invalid; /* do not clean if we didn't move from */
406 /* a valid cell */
407 }
408
409 /* record the previous cell if needed (i.e., if we changed the cell */
410 /* position, of changed the `invalid' flag) */
411 if ( ( ras.invalid != invalid || record ) && record_cell( RAS_VAR ) )
412 return 1;
413
414 if ( clean )
415 {
416 ras.area = 0;
417 ras.cover = 0;
418 }
419
420 ras.invalid = invalid;
421 ras.ex = ex;
422 ras.ey = ey;
423 return 0;
424 }
425
426
427 /*************************************************************************/
428 /* */
429 /* Start a new contour at a given cell. */
430 /* */
431 static
432 void start_cell( RAS_ARG_ TScan ex,
433 TScan ey )
434 {
435 if ( ex < ras.min_ex )
436 ex = ras.min_ex - 1;
437
438 ras.area = 0;
439 ras.cover = 0;
440 ras.ex = ex;
441 ras.ey = ey;
442 ras.last_ey = SUBPIXELS( ey );
443 ras.invalid = 0;
444
445 (void)set_cell( RAS_VAR_ ex, ey );
446 }
447
448
449 /*************************************************************************/
450 /* */
451 /* Render a scanline as one or more cells. */
452 /* */
453 static
454 int render_scanline( RAS_ARG_ TScan ey,
455 TPos x1,
456 TScan y1,
457 TPos x2,
458 TScan y2 )
459 {
460 TScan ex1, ex2, fx1, fx2, delta;
461 long p, first, dx;
462 int incr, lift, mod, rem;
463
464
465 dx = x2 - x1;
466
467 ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */
468 ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */
469 fx1 = x1 - SUBPIXELS( ex1 );
470 fx2 = x2 - SUBPIXELS( ex2 );
471
472 /* trivial case. Happens often */
473 if ( y1 == y2 )
474 return set_cell( RAS_VAR_ ex2, ey );
475
476 /* everything is located in a single cell. That is easy! */
477 /* */
478 if ( ex1 == ex2 )
479 {
480 delta = y2 - y1;
481 ras.area += ( fx1 + fx2 ) * delta;
482 ras.cover += delta;
483 return 0;
484 }
485
486 /* ok, we'll have to render a run of adjacent cells on the same */
487 /* scanline... */
488 /* */
489 p = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );
490 first = ONE_PIXEL;
491 incr = 1;
492
493 if ( dx < 0 )
494 {
495 p = fx1 * ( y2 - y1 );
496 first = 0;
497 incr = -1;
498 dx = -dx;
499 }
500
501 delta = p / dx;
502 mod = p % dx;
503 if ( mod < 0 )
504 {
505 delta--;
506 mod += dx;
507 }
508
509 ras.area += ( fx1 + first ) * delta;
510 ras.cover += delta;
511
512 ex1 += incr;
513 if ( set_cell( RAS_VAR_ ex1, ey ) )
514 goto Error;
515 y1 += delta;
516
517 if ( ex1 != ex2 )
518 {
519 p = ONE_PIXEL * ( y2 - y1 );
520 lift = p / dx;
521 rem = p % dx;
522 if ( rem < 0 )
523 {
524 lift--;
525 rem += dx;
526 }
527
528 mod -= dx;
529
530 while ( ex1 != ex2 )
531 {
532 delta = lift;
533 mod += rem;
534 if ( mod >= 0 )
535 {
536 mod -= dx;
537 delta++;
538 }
539
540 ras.area += ONE_PIXEL * delta;
541 ras.cover += delta;
542 y1 += delta;
543 ex1 += incr;
544 if ( set_cell( RAS_VAR_ ex1, ey ) )
545 goto Error;
546 }
547 }
548
549 delta = y2 - y1;
550 ras.area += ( fx2 + ONE_PIXEL - first ) * delta;
551 ras.cover += delta;
552
553 return 0;
554
555 Error:
556 return 1;
557 }
558
559
560 /*************************************************************************/
561 /* */
562 /* Render a given line as a series of scanlines. */
563 /* */
564 static
565 int render_line( RAS_ARG_ TPos to_x,
566 TPos to_y )
567 {
568 TScan ey1, ey2, fy1, fy2;
569 TPos dx, dy, x, x2;
570 int p, rem, mod, lift, delta, first, incr;
571
572
573 ey1 = TRUNC( ras.last_ey );
574 ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
575 fy1 = ras.y - ras.last_ey;
576 fy2 = to_y - SUBPIXELS( ey2 );
577
578 dx = to_x - ras.x;
579 dy = to_y - ras.y;
580
581 /* XXX: we should do something about the trivial case where dx == 0, */
582 /* as it happens very often! */
583
584 /* perform vertical clipping */
585 {
586 TScan min, max;
587
588
589 min = ey1;
590 max = ey2;
591 if ( ey1 > ey2 )
592 {
593 min = ey2;
594 max = ey1;
595 }
596 if ( min >= ras.max_ey || max < ras.min_ey )
597 goto End;
598 }
599
600 /* everything is on a single scanline */
601 if ( ey1 == ey2 )
602 {
603 if ( render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 ) )
604 goto Error;
605 goto End;
606 }
607
608 /* ok, we have to render several scanlines */
609 p = ( ONE_PIXEL - fy1 ) * dx;
610 first = ONE_PIXEL;
611 incr = 1;
612
613 if ( dy < 0 )
614 {
615 p = fy1 * dx;
616 first = 0;
617 incr = -1;
618 dy = -dy;
619 }
620
621 delta = p / dy;
622 mod = p % dy;
623 if ( mod < 0 )
624 {
625 delta--;
626 mod += dy;
627 }
628
629 x = ras.x + delta;
630 if ( render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first ) )
631 goto Error;
632
633 ey1 += incr;
634 if ( set_cell( RAS_VAR_ TRUNC( x ), ey1 ) )
635 goto Error;
636
637 if ( ey1 != ey2 )
638 {
639 p = ONE_PIXEL * dx;
640 lift = p / dy;
641 rem = p % dy;
642 if ( rem < 0 )
643 {
644 lift--;
645 rem += dy;
646 }
647 mod -= dy;
648
649 while ( ey1 != ey2 )
650 {
651 delta = lift;
652 mod += rem;
653 if ( mod >= 0 )
654 {
655 mod -= dy;
656 delta++;
657 }
658
659 x2 = x + delta;
660 if ( render_scanline( RAS_VAR_ ey1,
661 x, ONE_PIXEL - first, x2, first ) )
662 goto Error;
663 x = x2;
664 ey1 += incr;
665 if ( set_cell( RAS_VAR_ TRUNC( x ), ey1 ) )
666 goto Error;
667 }
668 }
669
670 if ( render_scanline( RAS_VAR_ ey1,
671 x, ONE_PIXEL - first, to_x, fy2 ) )
672 goto Error;
673
674 End:
675 ras.x = to_x;
676 ras.y = to_y;
677 ras.last_ey = SUBPIXELS( ey2 );
678
679 return 0;
680
681 Error:
682 return 1;
683 }
684
685
686 static
687 void split_conic( FT_Vector* base )
688 {
689 TPos a, b;
690
691
692 base[4].x = base[2].x;
693 b = base[1].x;
694 a = base[3].x = ( base[2].x + b ) / 2;
695 b = base[1].x = ( base[0].x + b ) / 2;
696 base[2].x = ( a + b ) / 2;
697
698 base[4].y = base[2].y;
699 b = base[1].y;
700 a = base[3].y = ( base[2].y + b ) / 2;
701 b = base[1].y = ( base[0].y + b ) / 2;
702 base[2].y = ( a + b ) / 2;
703 }
704
705
706 static
707 int render_conic( RAS_ARG_ FT_Vector* control,
708 FT_Vector* to )
709 {
710 TPos dx, dy;
711 int top, level;
712 int* levels;
713 FT_Vector* arc;
714
715
716 dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
717 if ( dx < 0 )
718 dx = -dx;
719 dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
720 if ( dy < 0 )
721 dy = -dy;
722 if ( dx < dy )
723 dx = dy;
724
725 level = 1;
726 dx = dx / ras.conic_level;
727 while ( dx > 0 )
728 {
729 dx >>= 1;
730 level++;
731 }
732
733 /* a shortcut to speed things up */
734 if ( level <= 1 )
735 {
736 /* we compute the mid-point directly in order to avoid */
737 /* calling split_conic() */
738 TPos to_x, to_y, mid_x, mid_y;
739
740
741 to_x = UPSCALE( to->x );
742 to_y = UPSCALE( to->y );
743 mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
744 mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
745
746 return render_line( RAS_VAR_ mid_x, mid_y ) ||
747 render_line( RAS_VAR_ to_x, to_y );
748 }
749
750 arc = ras.bez_stack;
751 levels = ras.lev_stack;
752 top = 0;
753 levels[0] = level;
754
755 arc[0].x = UPSCALE( to->x );
756 arc[0].y = UPSCALE( to->y );
757 arc[1].x = UPSCALE( control->x );
758 arc[1].y = UPSCALE( control->y );
759 arc[2].x = ras.x;
760 arc[2].y = ras.y;
761
762 while ( top >= 0 )
763 {
764 level = levels[top];
765 if ( level > 1 )
766 {
767 /* check that the arc crosses the current band */
768 TPos min, max, y;
769
770
771 min = max = arc[0].y;
772
773 y = arc[1].y;
774 if ( y < min ) min = y;
775 if ( y > max ) max = y;
776
777 y = arc[2].y;
778 if ( y < min ) min = y;
779 if ( y > max ) max = y;
780
781 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
782 goto Draw;
783
784 split_conic( arc );
785 arc += 2;
786 top++;
787 levels[top] = levels[top - 1] = level - 1;
788 continue;
789 }
790
791 Draw:
792 {
793 TPos to_x, to_y, mid_x, mid_y;
794
795
796 to_x = arc[0].x;
797 to_y = arc[0].y;
798 mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
799 mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
800
801 if ( render_line( RAS_VAR_ mid_x, mid_y ) ||
802 render_line( RAS_VAR_ to_x, to_y ) )
803 return 1;
804
805 top--;
806 arc -= 2;
807 }
808 }
809 return 0;
810 }
811
812
813 static
814 void split_cubic( FT_Vector* base )
815 {
816 TPos a, b, c, d;
817
818
819 base[6].x = base[3].x;
820 c = base[1].x;
821 d = base[2].x;
822 base[1].x = a = ( base[0].x + c ) / 2;
823 base[5].x = b = ( base[3].x + d ) / 2;
824 c = ( c + d ) / 2;
825 base[2].x = a = ( a + c ) / 2;
826 base[4].x = b = ( b + c ) / 2;
827 base[3].x = ( a + b ) / 2;
828
829 base[6].y = base[3].y;
830 c = base[1].y;
831 d = base[2].y;
832 base[1].y = a = ( base[0].y + c ) / 2;
833 base[5].y = b = ( base[3].y + d ) / 2;
834 c = ( c + d ) / 2;
835 base[2].y = a = ( a + c ) / 2;
836 base[4].y = b = ( b + c ) / 2;
837 base[3].y = ( a + b ) / 2;
838 }
839
840
841 static
842 int render_cubic( RAS_ARG_ FT_Vector* control1,
843 FT_Vector* control2,
844 FT_Vector* to )
845 {
846 TPos dx, dy, da, db;
847 int top, level;
848 int* levels;
849 FT_Vector* arc;
850
851
852 dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
853 if ( dx < 0 )
854 dx = -dx;
855 dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
856 if ( dy < 0 )
857 dy = -dy;
858 if ( dx < dy )
859 dx = dy;
860 da = dx;
861
862 dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
863 if ( dx < 0 )
864 dx = -dx;
865 dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
866 if ( dy < 0 )
867 dy = -dy;
868 if ( dx < dy )
869 dx = dy;
870 db = dx;
871
872 level = 1;
873 da = da / ras.cubic_level;
874 db = db / ras.conic_level;
875 while ( da > 0 || db > 0 )
876 {
877 da >>= 1;
878 db >>= 2;
879 level++;
880 }
881
882 if ( level <= 1 )
883 {
884 TPos to_x, to_y, mid_x, mid_y;
885
886
887 to_x = UPSCALE( to->x );
888 to_y = UPSCALE( to->y );
889 mid_x = ( ras.x + to_x +
890 3 * UPSCALE( control1->x + control2->x ) ) / 8;
891 mid_y = ( ras.y + to_y +
892 3 * UPSCALE( control1->y + control2->y ) ) / 8;
893
894 return render_line( RAS_VAR_ mid_x, mid_y ) ||
895 render_line( RAS_VAR_ to_x, to_y );
896 }
897
898 arc = ras.bez_stack;
899 arc[0].x = UPSCALE( to->x );
900 arc[0].y = UPSCALE( to->y );
901 arc[1].x = UPSCALE( control2->x );
902 arc[1].y = UPSCALE( control2->y );
903 arc[2].x = UPSCALE( control1->x );
904 arc[2].y = UPSCALE( control1->y );
905 arc[3].x = ras.x;
906 arc[3].y = ras.y;
907
908 levels = ras.lev_stack;
909 top = 0;
910 levels[0] = level;
911
912 while ( top >= 0 )
913 {
914 level = levels[top];
915 if ( level > 1 )
916 {
917 /* check that the arc crosses the current band */
918 TPos min, max, y;
919
920
921 min = max = arc[0].y;
922 y = arc[1].y;
923 if ( y < min ) min = y;
924 if ( y > max ) max = y;
925 y = arc[2].y;
926 if ( y < min ) min = y;
927 if ( y > max ) max = y;
928 y = arc[3].y;
929 if ( y < min ) min = y;
930 if ( y > max ) max = y;
931 if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
932 goto Draw;
933 split_cubic( arc );
934 arc += 3;
935 top ++;
936 levels[top] = levels[top - 1] = level - 1;
937 continue;
938 }
939
940 Draw:
941 {
942 TPos to_x, to_y, mid_x, mid_y;
943
944
945 to_x = arc[0].x;
946 to_y = arc[0].y;
947 mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
948 mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
949
950 if ( render_line( RAS_VAR_ mid_x, mid_y ) ||
951 render_line( RAS_VAR_ to_x, to_y ) )
952 return 1;
953 top --;
954 arc -= 3;
955 }
956 }
957 return 0;
958 }
959
960
961 /* a macro comparing two cell pointers. Returns true if a <= b. */
962 #if 1
963
964 #define PACK( a ) ( ( (long)(a)->y << 16 ) + (a)->x )
965 #define LESS_THAN( a, b ) ( PACK( a ) < PACK( b ) )
966
967 #else /* 1 */
968
969 #define LESS_THAN( a, b ) ( (a)->y < (b)->y || \
970 ( (a)->y == (b)->y && (a)->x < (b)->x ) )
971
972 #endif /* 1 */
973
974 #define SWAP_CELLS( a, b, temp ) do \
975 { \
976 temp = *(a); \
977 *(a) = *(b); \
978 *(b) = temp; \
979 } while ( 0 )
980 #define DEBUG_SORT
981 #define QUICK_SORT
982
983 #ifdef SHELL_SORT
984
985 /* a simple shell sort algorithm that works directly on our */
986 /* cells table */
987 static
988 void shell_sort ( PCell cells,
989 int count )
990 {
991 PCell i, j, limit = cells + count;
992 TCell temp;
993 int gap;
994
995
996 /* compute initial gap */
997 for ( gap = 0; ++gap < count; gap *= 3 )
998 ;
999
1000 while ( gap /= 3 )
1001 {
1002 for ( i = cells + gap; i < limit; i++ )
1003 {
1004 for ( j = i - gap; ; j -= gap )
1005 {
1006 PCell k = j + gap;
1007
1008
1009 if ( LESS_THAN( j, k ) )
1010 break;
1011
1012 SWAP_CELLS( j, k, temp );
1013
1014 if ( j < cells + gap )
1015 break;
1016 }
1017 }
1018 }
1019 }
1020
1021 #endif /* SHELL_SORT */
1022
1023
1024 #ifdef QUICK_SORT
1025
1026 /* This is a non-recursive quicksort that directly process our cells */
1027 /* array. It should be faster than calling the stdlib qsort(), and we */
1028 /* can even tailor our insertion threshold... */
1029
1030 #define QSORT_THRESHOLD 9 /* below this size, a sub-array will be sorted */
1031 /* through a normal insertion sort */
1032
1033 static
1034 void quick_sort( PCell cells,
1035 int count )
1036 {
1037 PCell stack[40]; /* should be enough ;-) */
1038 PCell* top; /* top of stack */
1039 PCell base, limit;
1040 TCell temp;
1041
1042
1043 limit = cells + count;
1044 base = cells;
1045 top = stack;
1046
1047 for (;;)
1048 {
1049 int len = limit - base;
1050 PCell i, j, pivot;
1051
1052
1053 if ( len > QSORT_THRESHOLD )
1054 {
1055 /* we use base + len/2 as the pivot */
1056 pivot = base + len / 2;
1057 SWAP_CELLS( base, pivot, temp );
1058
1059 i = base + 1;
1060 j = limit - 1;
1061
1062 /* now ensure that *i <= *base <= *j */
1063 if ( LESS_THAN( j, i ) )
1064 SWAP_CELLS( i, j, temp );
1065
1066 if ( LESS_THAN( base, i ) )
1067 SWAP_CELLS( base, i, temp );
1068
1069 if ( LESS_THAN( j, base ) )
1070 SWAP_CELLS( base, j, temp );
1071
1072 for (;;)
1073 {
1074 do i++; while ( LESS_THAN( i, base ) );
1075 do j--; while ( LESS_THAN( base, j ) );
1076
1077 if ( i > j )
1078 break;
1079
1080 SWAP_CELLS( i, j, temp );
1081 }
1082
1083 SWAP_CELLS( base, j, temp );
1084
1085 /* now, push the largest sub-array */
1086 if ( j - base > limit - i )
1087 {
1088 top[0] = base;
1089 top[1] = j;
1090 base = i;
1091 }
1092 else
1093 {
1094 top[0] = i;
1095 top[1] = limit;
1096 limit = j;
1097 }
1098 top += 2;
1099 }
1100 else
1101 {
1102 /* the sub-array is small, perform insertion sort */
1103 j = base;
1104 i = j + 1;
1105
1106 for ( ; i < limit; j = i, i++ )
1107 {
1108 for ( ; LESS_THAN( j + 1, j ); j-- )
1109 {
1110 SWAP_CELLS( j + 1, j, temp );
1111 if ( j == base )
1112 break;
1113 }
1114 }
1115 if ( top > stack )
1116 {
1117 top -= 2;
1118 base = top[0];
1119 limit = top[1];
1120 }
1121 else
1122 break;
1123 }
1124 }
1125 }
1126
1127 #endif /* QUICK_SORT */
1128
1129
1130 #ifdef DEBUG_GRAYS
1131 #ifdef DEBUG_SORT
1132
1133 static
1134 int check_sort( PCell cells,
1135 int count )
1136 {
1137 PCell p, q;
1138
1139
1140 for ( p = cells + count - 2; p >= cells; p-- )
1141 {
1142 q = p + 1;
1143 if ( !LESS_THAN( p, q ) )
1144 return 0;
1145 }
1146 return 1;
1147 }
1148
1149 #endif /* DEBUG_SORT */
1150 #endif /* DEBUG_GRAYS */
1151
1152
1153 static
1154 int Move_To( FT_Vector* to,
1155 FT_Raster raster )
1156 {
1157 TPos x, y;
1158
1159
1160 /* record current cell, if any */
1161 record_cell( (PRaster)raster );
1162
1163 /* start to a new position */
1164 x = UPSCALE( to->x );
1165 y = UPSCALE( to->y );
1166 start_cell( (PRaster)raster, TRUNC( x ), TRUNC( y ) );
1167 ((PRaster)raster)->x = x;
1168 ((PRaster)raster)->y = y;
1169 return 0;
1170 }
1171
1172
1173 static
1174 int Line_To( FT_Vector* to,
1175 FT_Raster raster )
1176 {
1177 return render_line( (PRaster)raster,
1178 UPSCALE( to->x ), UPSCALE( to->y ) );
1179 }
1180
1181
1182 static
1183 int Conic_To( FT_Vector* control,
1184 FT_Vector* to,
1185 FT_Raster raster )
1186 {
1187 return render_conic( (PRaster)raster, control, to );
1188 }
1189
1190
1191 static
1192 int Cubic_To( FT_Vector* control1,
1193 FT_Vector* control2,
1194 FT_Vector* to,
1195 FT_Raster raster )
1196 {
1197 return render_cubic( (PRaster)raster, control1, control2, to );
1198 }
1199
1200
1201 static
1202 void grays_render_span( int y,
1203 int count,
1204 FT_Span* spans,
1205 PRaster raster )
1206 {
1207 unsigned char* p;
1208 FT_Bitmap* map = &raster->target;
1209
1210
1211 /* first of all, compute the scanline offset */
1212 p = (unsigned char*)map->buffer - y * map->pitch;
1213 if ( map->pitch >= 0 )
1214 p += ( map->rows - 1 ) * map->pitch;
1215
1216 for ( ; count > 0; count--, spans++ )
1217 {
1218 if ( spans->coverage )
1219 #if 1
1220 memset( p + spans->x, (unsigned char)spans->coverage, spans->len );
1221 #else /* 1 */
1222 {
1223 q = p + spans->x;
1224 limit = q + spans->len;
1225 for ( ; q < limit; q++ )
1226 q[0] = (unsigned char)spans->coverage;
1227 }
1228 #endif /* 1 */
1229 }
1230 }
1231
1232
1233 #ifdef DEBUG_GRAYS
1234
1235 #include <stdio.h>
1236
1237 static
1238 void dump_cells( RAS_ARG )
1239 {
1240 PCell cell, limit;
1241 int y = -1;
1242
1243
1244 cell = ras.cells;
1245 limit = cell + ras.num_cells;
1246
1247 for ( ; cell < limit; cell++ )
1248 {
1249 if ( cell->y != y )
1250 {
1251 fprintf( stderr, "\n%2d: ", cell->y );
1252 y = cell->y;
1253 }
1254 fprintf( stderr, "[%d %d %d]",
1255 cell->x, cell->area, cell->cover );
1256 }
1257 fprintf(stderr, "\n" );
1258 }
1259
1260 #endif /* DEBUG_GRAYS */
1261
1262
1263 static
1264 void grays_hline( RAS_ARG_ TScan x,
1265 TScan y,
1266 TPos area,
1267 int acount )
1268 {
1269 FT_Span* span;
1270 int count;
1271 int coverage;
1272
1273
1274 /* compute the coverage line's coverage, depending on the */
1275 /* outline fill rule */
1276 /* */
1277 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1278 /* */
1279 coverage = area >> ( PIXEL_BITS * 2 + 1 - 8); /* use range 0..256 */
1280
1281 if ( ras.outline.flags & ft_outline_even_odd_fill )
1282 {
1283 if ( coverage < 0 )
1284 coverage = -coverage;
1285
1286 while ( coverage >= 512 )
1287 coverage -= 512;
1288
1289 if ( coverage > 256 )
1290 coverage = 512 - coverage;
1291 else if ( coverage == 256 )
1292 coverage = 255;
1293 }
1294 else
1295 {
1296 /* normal non-zero winding rule */
1297 if ( coverage < 0 )
1298 coverage = -coverage;
1299
1300 if ( coverage >= 256 )
1301 coverage = 255;
1302 }
1303
1304 y += ras.min_ey;
1305 x += ras.min_ex;
1306
1307 if ( coverage )
1308 {
1309 /* see if we can add this span to the current list */
1310 count = ras.num_gray_spans;
1311 span = ras.gray_spans + count - 1;
1312 if ( count > 0 &&
1313 ras.span_y == y &&
1314 (int)span->x + span->len == (int)x &&
1315 span->coverage == coverage )
1316 {
1317 span->len += acount;
1318 return;
1319 }
1320
1321 if ( ras.span_y != y || count >= FT_MAX_GRAY_SPANS )
1322 {
1323 if ( ras.render_span )
1324 ras.render_span( ras.span_y, count, ras.gray_spans,
1325 ras.render_span_data );
1326 /* ras.render_span( span->y, ras.gray_spans, count ); */
1327
1328 #ifdef DEBUG_GRAYS
1329
1330 if ( ras.span_y >= 0 )
1331 {
1332 int n;
1333
1334
1335 fprintf( stderr, "y=%3d ", ras.span_y );
1336 span = ras.gray_spans;
1337 for ( n = 0; n < count; n++, span++ )
1338 fprintf( stderr, "[%d..%d]:%02x ",
1339 span->x, span->x + span->len - 1, span->coverage );
1340 fprintf( stderr, "\n" );
1341 }
1342
1343 #endif /* DEBUG_GRAYS */
1344
1345 ras.num_gray_spans = 0;
1346 ras.span_y = y;
1347
1348 count = 0;
1349 span = ras.gray_spans;
1350 }
1351 else
1352 span++;
1353
1354 /* add a gray span to the current list */
1355 span->x = (short)x;
1356 span->len = (unsigned short)acount;
1357 span->coverage = (unsigned char)coverage;
1358 ras.num_gray_spans++;
1359 }
1360 }
1361
1362
1363 static
1364 void grays_sweep( RAS_ARG_ FT_Bitmap* target )
1365 {
1366 TScan x, y, cover, area;
1367 PCell start, cur, limit;
1368
1369 FT_UNUSED( target );
1370
1371
1372 cur = ras.cells;
1373 limit = cur + ras.num_cells;
1374
1375 cover = 0;
1376 ras.span_y = -1;
1377 ras.num_gray_spans = 0;
1378
1379 for (;;)
1380 {
1381 start = cur;
1382 y = start->y;
1383 x = start->x;
1384
1385 area = start->area;
1386 cover += start->cover;
1387
1388 /* accumulate all start cells */
1389 for (;;)
1390 {
1391 ++cur;
1392 if ( cur >= limit || cur->y != start->y || cur->x != start->x )
1393 break;
1394
1395 area += cur->area;
1396 cover += cur->cover;
1397 }
1398
1399 /* if the start cell has a non-null area, we must draw an */
1400 /* individual gray pixel there */
1401 if ( area && x >= 0 )
1402 {
1403 grays_hline( RAS_VAR_ x, y, cover * ( ONE_PIXEL * 2 ) - area, 1 );
1404 x++;
1405 }
1406
1407 if ( x < 0 )
1408 x = 0;
1409
1410 if ( cur < limit && start->y == cur->y )
1411 {
1412 /* draw a gray span between the start cell and the current one */
1413 if ( cur->x > x )
1414 grays_hline( RAS_VAR_ x, y,
1415 cover * ( ONE_PIXEL * 2 ), cur->x - x );
1416 }
1417 else
1418 {
1419 /* draw a gray span until the end of the clipping region */
1420 if ( cover && x < ras.max_ex - ras.min_ex )
1421 grays_hline( RAS_VAR_ x, y,
1422 cover * ( ONE_PIXEL * 2 ),
1423 ras.max_ex - x - ras.min_ex );
1424 cover = 0;
1425 }
1426
1427 if ( cur >= limit )
1428 break;
1429 }
1430
1431 if ( ras.render_span && ras.num_gray_spans > 0 )
1432 ras.render_span( ras.span_y, ras.num_gray_spans,
1433 ras.gray_spans, ras.render_span_data );
1434
1435 #ifdef DEBUG_GRAYS
1436
1437 {
1438 int n;
1439 FT_Span* span;
1440
1441
1442 fprintf( stderr, "y=%3d ", ras.span_y );
1443 span = ras.gray_spans;
1444 for ( n = 0; n < ras.num_gray_spans; n++, span++ )
1445 fprintf( stderr, "[%d..%d]:%02x ",
1446 span->x, span->x + span->len - 1, span->coverage );
1447 fprintf( stderr, "\n" );
1448 }
1449
1450 #endif /* DEBUG_GRAYS */
1451
1452 }
1453
1454
1455 #ifdef _STANDALONE_
1456
1457 /*************************************************************************/
1458 /* */
1459 /* The following function should only compile in stand_alone mode, */
1460 /* i.e., when building this component without the rest of FreeType. */
1461 /* */
1462 /*************************************************************************/
1463
1464 /*************************************************************************/
1465 /* */
1466 /* <Function> */
1467 /* FT_Outline_Decompose */
1468 /* */
1469 /* <Description> */
1470 /* Walks over an outline's structure to decompose it into individual */
1471 /* segments and Bezier arcs. This function is also able to emit */
1472 /* `move to' and `close to' operations to indicate the start and end */
1473 /* of new contours in the outline. */
1474 /* */
1475 /* <Input> */
1476 /* outline :: A pointer to the source target. */
1477 /* */
1478 /* interface :: A table of `emitters', i.e,. function pointers called */
1479 /* during decomposition to indicate path operations. */
1480 /* */
1481 /* user :: A typeless pointer which is passed to each emitter */
1482 /* during the decomposition. It can be used to store */
1483 /* the state during the decomposition. */
1484 /* */
1485 /* <Return> */
1486 /* Error code. 0 means sucess. */
1487 /* */
1488 static
1489 int FT_Outline_Decompose( FT_Outline* outline,
1490 FT_Outline_Funcs* interface,
1491 void* user )
1492 {
1493 #undef SCALED
1494 #define SCALED( x ) ( ( (x) << shift ) - delta )
1495
1496 FT_Vector v_last;
1497 FT_Vector v_control;
1498 FT_Vector v_start;
1499
1500 FT_Vector* point;
1501 FT_Vector* limit;
1502 char* tags;
1503
1504 int n; /* index of contour in outline */
1505 int first; /* index of first point in contour */
1506 int error;
1507 char tag; /* current point's state */
1508
1509 int shift = interface->shift;
1510 FT_Pos delta = interface->delta;
1511
1512
1513 first = 0;
1514
1515 for ( n = 0; n < outline->n_contours; n++ )
1516 {
1517 int last; /* index of last point in contour */
1518
1519
1520 last = outline->contours[n];
1521 limit = outline->points + last;
1522
1523 v_start = outline->points[first];
1524 v_last = outline->points[last];
1525
1526 v_start.x = SCALED( v_start.x ); v_start.y = SCALED( v_start.y );
1527 v_last.x = SCALED( v_last.x ); v_last.y = SCALED( v_last.y );
1528
1529 v_control = v_start;
1530
1531 point = outline->points + first;
1532 tags = outline->tags + first;
1533 tag = FT_CURVE_TAG( tags[0] );
1534
1535 /* A contour cannot start with a cubic control point! */
1536 if ( tag == FT_Curve_Tag_Cubic )
1537 goto Invalid_Outline;
1538
1539 /* check first point to determine origin */
1540 if ( tag == FT_Curve_Tag_Conic )
1541 {
1542 /* first point is conic control. Yes, this happens. */
1543 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_Curve_Tag_On )
1544 {
1545 /* start at last point if it is on the curve */
1546 v_start = v_last;
1547 limit--;
1548 }
1549 else
1550 {
1551 /* if both first and last points are conic, */
1552 /* start at their middle and record its position */
1553 /* for closure */
1554 v_start.x = ( v_start.x + v_last.x ) / 2;
1555 v_start.y = ( v_start.y + v_last.y ) / 2;
1556
1557 v_last = v_start;
1558 }
1559 point--;
1560 tags--;
1561 }
1562
1563 error = interface->move_to( &v_start, user );
1564 if ( error )
1565 goto Exit;
1566
1567 while ( point < limit )
1568 {
1569 point++;
1570 tags++;
1571
1572 tag = FT_CURVE_TAG( tags[0] );
1573 switch ( tag )
1574 {
1575 case FT_Curve_Tag_On: /* emit a single line_to */
1576 {
1577 FT_Vector vec;
1578
1579
1580 vec.x = SCALED( point->x );
1581 vec.y = SCALED( point->y );
1582
1583 error = interface->line_to( &vec, user );
1584 if ( error )
1585 goto Exit;
1586 continue;
1587 }
1588
1589 case FT_Curve_Tag_Conic: /* consume conic arcs */
1590 {
1591 v_control.x = SCALED( point->x );
1592 v_control.y = SCALED( point->y );
1593
1594 Do_Conic:
1595 if ( point < limit )
1596 {
1597 FT_Vector vec;
1598 FT_Vector v_middle;
1599
1600
1601 point++;
1602 tags++;
1603 tag = FT_CURVE_TAG( tags[0] );
1604
1605 vec.x = SCALED( point->x );
1606 vec.y = SCALED( point->y );
1607
1608 if ( tag == FT_Curve_Tag_On )
1609 {
1610 error = interface->conic_to( &v_control, &vec, user );
1611 if ( error )
1612 goto Exit;
1613 continue;
1614 }
1615
1616 if ( tag != FT_Curve_Tag_Conic )
1617 goto Invalid_Outline;
1618
1619 v_middle.x = ( v_control.x + vec.x ) / 2;
1620 v_middle.y = ( v_control.y + vec.y ) / 2;
1621
1622 error = interface->conic_to( &v_control, &v_middle, user );
1623 if ( error )
1624 goto Exit;
1625
1626 v_control = vec;
1627 goto Do_Conic;
1628 }
1629
1630 error = interface->conic_to( &v_control, &v_start, user );
1631 goto Close;
1632 }
1633
1634 default: /* FT_Curve_Tag_Cubic */
1635 {
1636 FT_Vector vec1, vec2;
1637
1638
1639 if ( point + 1 > limit ||
1640 FT_CURVE_TAG( tags[1] ) != FT_Curve_Tag_Cubic )
1641 goto Invalid_Outline;
1642
1643 point += 2;
1644 tags += 2;
1645
1646 vec1.x = SCALED( point[-2].x ); vec1.y = SCALED( point[-2].y );
1647 vec2.x = SCALED( point[-1].x ); vec2.y = SCALED( point[-1].y );
1648
1649 if ( point <= limit )
1650 {
1651 FT_Vector vec;
1652
1653
1654 vec.x = SCALED( point->x );
1655 vec.y = SCALED( point->y );
1656
1657 error = interface->cubic_to( &vec1, &vec2, &vec, user );
1658 if ( error )
1659 goto Exit;
1660 continue;
1661 }
1662
1663 error = interface->cubic_to( &vec1, &vec2, &v_start, user );
1664 goto Close;
1665 }
1666 }
1667 }
1668
1669 /* close the contour with a line segment */
1670 error = interface->line_to( &v_start, user );
1671
1672 Close:
1673 if ( error )
1674 goto Exit;
1675
1676 first = last + 1;
1677 }
1678
1679 return 0;
1680
1681 Exit:
1682 return error;
1683
1684 Invalid_Outline:
1685 return ErrRaster_Invalid_Outline;
1686 }
1687
1688 #endif /* _STANDALONE_ */
1689
1690
1691 typedef struct TBand_
1692 {
1693 FT_Pos min, max;
1694
1695 } TBand;
1696
1697
1698 static
1699 int grays_convert_glyph( RAS_ARG_ FT_Outline* outline )
1700 {
1701 static
1702 FT_Outline_Funcs interface =
1703 {
1704 (FT_Outline_MoveTo_Func) Move_To,
1705 (FT_Outline_LineTo_Func) Line_To,
1706 (FT_Outline_ConicTo_Func)Conic_To,
1707 (FT_Outline_CubicTo_Func)Cubic_To,
1708 0,
1709 0
1710 };
1711
1712 TBand bands[40], *band;
1713 int n, num_bands;
1714 TPos min, max, max_y;
1715
1716
1717 /* Set up state in the raster object */
1718 compute_cbox( RAS_VAR_ outline );
1719
1720 /* clip to target bitmap, exit if nothing to do */
1721 if ( ras.max_ex <= 0 || ras.min_ex >= ras.target.width ||
1722 ras.max_ey <= 0 || ras.min_ey >= ras.target.rows )
1723 return 0;
1724
1725 if ( ras.min_ex < 0 ) ras.min_ex = 0;
1726 if ( ras.min_ey < 0 ) ras.min_ey = 0;
1727
1728 if ( ras.max_ex > ras.target.width ) ras.max_ex = ras.target.width;
1729 if ( ras.max_ey > ras.target.rows ) ras.max_ey = ras.target.rows;
1730
1731 /* simple heuristic used to speed-up the bezier decomposition -- see */
1732 /* the code in render_conic() and render_cubic() for more details */
1733 ras.conic_level = 32;
1734 ras.cubic_level = 16;
1735
1736 {
1737 int level = 0;
1738
1739
1740 if ( ras.max_ex > 24 || ras.max_ey > 24 )
1741 level++;
1742 if ( ras.max_ex > 120 || ras.max_ey > 120 )
1743 level += 2;
1744
1745 ras.conic_level <<= level;
1746 ras.cubic_level <<= level;
1747 }
1748
1749 /* setup vertical bands */
1750 num_bands = ( ras.max_ey - ras.min_ey ) / ras.band_size;
1751 if ( num_bands == 0 ) num_bands = 1;
1752 if ( num_bands >= 39 ) num_bands = 39;
1753
1754 ras.band_shoot = 0;
1755
1756 min = ras.min_ey;
1757 max_y = ras.max_ey;
1758
1759 for ( n = 0; n < num_bands; n++, min = max )
1760 {
1761 max = min + ras.band_size;
1762 if ( n == num_bands - 1 || max > max_y )
1763 max = max_y;
1764
1765 bands[0].min = min;
1766 bands[0].max = max;
1767 band = bands;
1768
1769 while ( band >= bands )
1770 {
1771 FT_Pos bottom, top, middle;
1772 int error;
1773
1774
1775 ras.num_cells = 0;
1776 ras.invalid = 1;
1777 ras.min_ey = band->min;
1778 ras.max_ey = band->max;
1779
1780 error = FT_Outline_Decompose( outline, &interface, &ras ) ||
1781 record_cell( RAS_VAR );
1782
1783 if ( !error )
1784 {
1785 #ifdef SHELL_SORT
1786 shell_sort( ras.cells, ras.num_cells );
1787 #else
1788 quick_sort( ras.cells, ras.num_cells );
1789 #endif
1790
1791 #ifdef DEBUG_GRAYS
1792 check_sort( ras.cells, ras.num_cells );
1793 dump_cells( RAS_VAR );
1794 #endif
1795
1796 grays_sweep( RAS_VAR_ &ras.target );
1797 band--;
1798 continue;
1799 }
1800
1801 /* render pool overflow, we will reduce the render band by half */
1802 bottom = band->min;
1803 top = band->max;
1804 middle = bottom + ( ( top - bottom ) >> 1 );
1805
1806 /* waoow! This is too complex for a single scanline, something */
1807 /* must be really rotten here! */
1808 if ( middle == bottom )
1809 {
1810 #ifdef DEBUG_GRAYS
1811 fprintf( stderr, "Rotten glyph!\n" );
1812 #endif
1813 return 1;
1814 }
1815
1816 if ( bottom-top >= ras.band_size )
1817 ras.band_shoot++;
1818
1819 band[1].min = bottom;
1820 band[1].max = middle;
1821 band[0].min = middle;
1822 band[0].max = top;
1823 band++;
1824 }
1825 }
1826
1827 if ( ras.band_shoot > 8 && ras.band_size > 16 )
1828 ras.band_size = ras.band_size / 2;
1829
1830 return 0;
1831 }
1832
1833
1834 extern
1835 int grays_raster_render( PRaster raster,
1836 FT_Raster_Params* params )
1837 {
1838 FT_Outline* outline = (FT_Outline*)params->source;
1839 FT_Bitmap* target_map = params->target;
1840
1841
1842 if ( !raster || !raster->cells || !raster->max_cells )
1843 return -1;
1844
1845 /* return immediately if the outline is empty */
1846 if ( outline->n_points == 0 || outline->n_contours <= 0 )
1847 return 0;
1848
1849 if ( !outline || !outline->contours || !outline->points )
1850 return ErrRaster_Invalid_Outline;
1851
1852 if ( outline->n_points !=
1853 outline->contours[outline->n_contours - 1] + 1 )
1854 return ErrRaster_Invalid_Outline;
1855
1856 if ( !target_map || !target_map->buffer )
1857 return -1;
1858
1859 /* XXX: this version does not support monochrome rendering yet! */
1860 if ( !(params->flags & ft_raster_flag_aa) )
1861 return ErrRaster_Invalid_Mode;
1862
1863 ras.outline = *outline;
1864 ras.target = *target_map;
1865 ras.num_cells = 0;
1866 ras.invalid = 1;
1867
1868 ras.render_span = (FT_Raster_Span_Func)grays_render_span;
1869 ras.render_span_data = &ras;
1870
1871 if ( params->flags & ft_raster_flag_direct )
1872 {
1873 ras.render_span = (FT_Raster_Span_Func)params->gray_spans;
1874 ras.render_span_data = params->user;
1875 }
1876
1877 return grays_convert_glyph( (PRaster)raster, outline );
1878 }
1879
1880
1881 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
1882 /**** a static object. *****/
1883
1884 #ifdef _STANDALONE_
1885
1886 static
1887 int grays_raster_new( void* memory,
1888 FT_Raster* araster )
1889 {
1890 static TRaster the_raster;
1891
1892 FT_UNUSED( memory );
1893
1894
1895 *araster = (FT_Raster)&the_raster;
1896 memset( &the_raster, 0, sizeof ( the_raster ) );
1897
1898 return 0;
1899 }
1900
1901
1902 static
1903 void grays_raster_done( FT_Raster raster )
1904 {
1905 /* nothing */
1906 FT_UNUSED( raster );
1907 }
1908
1909 #else /* _STANDALONE_ */
1910
1911 static
1912 int grays_raster_new( FT_Memory memory,
1913 FT_Raster* araster )
1914 {
1915 FT_Error error;
1916 PRaster raster;
1917
1918
1919 *araster = 0;
1920 if ( !ALLOC( raster, sizeof ( TRaster ) ) )
1921 {
1922 raster->memory = memory;
1923 *araster = (FT_Raster)raster;
1924 }
1925
1926 return error;
1927 }
1928
1929
1930 static
1931 void grays_raster_done( FT_Raster raster )
1932 {
1933 FT_Memory memory = (FT_Memory)((PRaster)raster)->memory;
1934
1935
1936 FREE( raster );
1937 }
1938
1939 #endif /* _STANDALONE_ */
1940
1941
1942 static
1943 void grays_raster_reset( FT_Raster raster,
1944 const char* pool_base,
1945 long pool_size )
1946 {
1947 PRaster rast = (PRaster)raster;
1948
1949
1950 if ( raster && pool_base && pool_size >= 4096 )
1951 init_cells( rast, (char*)pool_base, pool_size );
1952
1953 rast->band_size = ( pool_size / sizeof ( TCell ) ) / 8;
1954 }
1955
1956
1957 FT_Raster_Funcs ft_grays_raster =
1958 {
1959 ft_glyph_format_outline,
1960
1961 (FT_Raster_New_Func) grays_raster_new,
1962 (FT_Raster_Reset_Func) grays_raster_reset,
1963 (FT_Raster_Set_Mode_Func)0,
1964 (FT_Raster_Render_Func) grays_raster_render,
1965 (FT_Raster_Done_Func) grays_raster_done
1966 };
1967
1968
1969 /* END */
wxWidgets (Impactor)