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