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