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