1 /***************************************************************************/ 2 /* */ 3 /* ftgrays.c */ 4 /* */ 5 /* A new `perfect' anti-aliasing renderer (body). */ 6 /* */ 7 /* Copyright 2000-2016 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 ft_memset memset 145 146 #define ft_setjmp setjmp 147 #define ft_longjmp longjmp 148 #define ft_jmp_buf jmp_buf 149 150 typedef ptrdiff_t FT_PtrDist; 151 152 153 #define ErrRaster_Invalid_Mode -2 154 #define ErrRaster_Invalid_Outline -1 155 #define ErrRaster_Invalid_Argument -3 156 #define ErrRaster_Memory_Overflow -4 157 158 #define FT_BEGIN_HEADER 159 #define FT_END_HEADER 160 161 #include "ftimage.h" 162 #include "ftgrays.h" 163 164 165 /* This macro is used to indicate that a function parameter is unused. */ 166 /* Its purpose is simply to reduce compiler warnings. Note also that */ 167 /* simply defining it as `(void)x' doesn't avoid warnings with certain */ 168 /* ANSI compilers (e.g. LCC). */ 169 #define FT_UNUSED( x ) (x) = (x) 170 171 172 /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */ 173 174 #ifdef FT_DEBUG_LEVEL_TRACE 175 176 void FT_Message(const char * fmt,...)177 FT_Message( const char* fmt, 178 ... ) 179 { 180 va_list ap; 181 182 183 va_start( ap, fmt ); 184 vfprintf( stderr, fmt, ap ); 185 va_end( ap ); 186 } 187 188 189 /* empty function useful for setting a breakpoint to catch errors */ 190 int FT_Throw(int error,int line,const char * file)191 FT_Throw( int error, 192 int line, 193 const char* file ) 194 { 195 FT_UNUSED( error ); 196 FT_UNUSED( line ); 197 FT_UNUSED( file ); 198 199 return 0; 200 } 201 202 203 /* we don't handle tracing levels in stand-alone mode; */ 204 #ifndef FT_TRACE5 205 #define FT_TRACE5( varformat ) FT_Message varformat 206 #endif 207 #ifndef FT_TRACE7 208 #define FT_TRACE7( varformat ) FT_Message varformat 209 #endif 210 #ifndef FT_ERROR 211 #define FT_ERROR( varformat ) FT_Message varformat 212 #endif 213 214 #define FT_THROW( e ) \ 215 ( FT_Throw( FT_ERR_CAT( ErrRaster, e ), \ 216 __LINE__, \ 217 __FILE__ ) | \ 218 FT_ERR_CAT( ErrRaster, e ) ) 219 220 #else /* !FT_DEBUG_LEVEL_TRACE */ 221 222 #define FT_TRACE5( x ) do { } while ( 0 ) /* nothing */ 223 #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */ 224 #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */ 225 #define FT_THROW( e ) FT_ERR_CAT( ErrRaster_, e ) 226 227 228 #endif /* !FT_DEBUG_LEVEL_TRACE */ 229 230 231 #define FT_DEFINE_OUTLINE_FUNCS( class_, \ 232 move_to_, line_to_, \ 233 conic_to_, cubic_to_, \ 234 shift_, delta_ ) \ 235 static const FT_Outline_Funcs class_ = \ 236 { \ 237 move_to_, \ 238 line_to_, \ 239 conic_to_, \ 240 cubic_to_, \ 241 shift_, \ 242 delta_ \ 243 }; 244 245 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, \ 246 raster_new_, raster_reset_, \ 247 raster_set_mode_, raster_render_, \ 248 raster_done_ ) \ 249 const FT_Raster_Funcs class_ = \ 250 { \ 251 glyph_format_, \ 252 raster_new_, \ 253 raster_reset_, \ 254 raster_set_mode_, \ 255 raster_render_, \ 256 raster_done_ \ 257 }; 258 259 260 #else /* !STANDALONE_ */ 261 262 263 #include <ft2build.h> 264 #include "ftgrays.h" 265 #include FT_INTERNAL_OBJECTS_H 266 #include FT_INTERNAL_DEBUG_H 267 #include FT_OUTLINE_H 268 269 #include "ftsmerrs.h" 270 271 #include "ftspic.h" 272 273 #define Smooth_Err_Invalid_Mode Smooth_Err_Cannot_Render_Glyph 274 #define Smooth_Err_Memory_Overflow Smooth_Err_Out_Of_Memory 275 #define ErrRaster_Memory_Overflow Smooth_Err_Out_Of_Memory 276 277 278 #endif /* !STANDALONE_ */ 279 280 281 #ifndef FT_MEM_SET 282 #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c ) 283 #endif 284 285 #ifndef FT_MEM_ZERO 286 #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count ) 287 #endif 288 289 /* as usual, for the speed hungry :-) */ 290 291 #undef RAS_ARG 292 #undef RAS_ARG_ 293 #undef RAS_VAR 294 #undef RAS_VAR_ 295 296 #ifndef FT_STATIC_RASTER 297 298 #define RAS_ARG gray_PWorker worker 299 #define RAS_ARG_ gray_PWorker worker, 300 301 #define RAS_VAR worker 302 #define RAS_VAR_ worker, 303 304 #else /* FT_STATIC_RASTER */ 305 306 #define RAS_ARG void 307 #define RAS_ARG_ /* empty */ 308 #define RAS_VAR /* empty */ 309 #define RAS_VAR_ /* empty */ 310 311 #endif /* FT_STATIC_RASTER */ 312 313 314 /* must be at least 6 bits! */ 315 #define PIXEL_BITS 8 316 317 #undef FLOOR 318 #undef CEILING 319 #undef TRUNC 320 #undef SCALED 321 322 #define ONE_PIXEL ( 1 << PIXEL_BITS ) 323 #define TRUNC( x ) ( (TCoord)( (x) >> PIXEL_BITS ) ) 324 #define SUBPIXELS( x ) ( (TPos)(x) * ONE_PIXEL ) 325 #define FLOOR( x ) ( (x) & -ONE_PIXEL ) 326 #define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL ) 327 #define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL ) 328 329 #if PIXEL_BITS >= 6 330 #define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) ) 331 #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) ) 332 #else 333 #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) ) 334 #define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) ) 335 #endif 336 337 338 /* Compute `dividend / divisor' and return both its quotient and */ 339 /* remainder, cast to a specific type. This macro also ensures that */ 340 /* the remainder is always positive. */ 341 #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ 342 FT_BEGIN_STMNT \ 343 (quotient) = (type)( (dividend) / (divisor) ); \ 344 (remainder) = (type)( (dividend) % (divisor) ); \ 345 if ( (remainder) < 0 ) \ 346 { \ 347 (quotient)--; \ 348 (remainder) += (type)(divisor); \ 349 } \ 350 FT_END_STMNT 351 352 #ifdef __arm__ 353 /* Work around a bug specific to GCC which make the compiler fail to */ 354 /* optimize a division and modulo operation on the same parameters */ 355 /* into a single call to `__aeabi_idivmod'. See */ 356 /* */ 357 /* http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 */ 358 #undef FT_DIV_MOD 359 #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ 360 FT_BEGIN_STMNT \ 361 (quotient) = (type)( (dividend) / (divisor) ); \ 362 (remainder) = (type)( (dividend) - (quotient) * (divisor) ); \ 363 if ( (remainder) < 0 ) \ 364 { \ 365 (quotient)--; \ 366 (remainder) += (type)(divisor); \ 367 } \ 368 FT_END_STMNT 369 #endif /* __arm__ */ 370 371 372 /* These macros speed up repetitive divisions by replacing them */ 373 /* with multiplications and right shifts. */ 374 #define FT_UDIVPREP( b ) \ 375 long b ## _r = (long)( FT_ULONG_MAX >> PIXEL_BITS ) / ( b ) 376 #define FT_UDIV( a, b ) \ 377 ( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \ 378 ( sizeof( long ) * FT_CHAR_BIT - PIXEL_BITS ) ) 379 380 381 /*************************************************************************/ 382 /* */ 383 /* TYPE DEFINITIONS */ 384 /* */ 385 386 /* don't change the following types to FT_Int or FT_Pos, since we might */ 387 /* need to define them to "float" or "double" when experimenting with */ 388 /* new algorithms */ 389 390 typedef long TPos; /* sub-pixel coordinate */ 391 typedef int TCoord; /* integer scanline/pixel coordinate */ 392 typedef int TArea; /* cell areas, coordinate products */ 393 394 395 typedef struct TCell_* PCell; 396 397 typedef struct TCell_ 398 { 399 TCoord x; /* same with gray_TWorker.ex */ 400 TCoord cover; /* same with gray_TWorker.cover */ 401 TArea area; 402 PCell next; 403 404 } TCell; 405 406 typedef struct TPixmap_ 407 { 408 unsigned char* origin; /* pixmap origin at the bottom-left */ 409 int pitch; /* pitch to go down one row */ 410 411 } TPixmap; 412 413 /* maximum number of gray cells in the buffer */ 414 #if FT_RENDER_POOL_SIZE > 2048 415 #define FT_MAX_GRAY_POOL ( FT_RENDER_POOL_SIZE / sizeof ( TCell ) ) 416 #else 417 #define FT_MAX_GRAY_POOL ( 2048 / sizeof ( TCell ) ) 418 #endif 419 420 421 #if defined( _MSC_VER ) /* Visual C++ (and Intel C++) */ 422 /* We disable the warning `structure was padded due to */ 423 /* __declspec(align())' in order to compile cleanly with */ 424 /* the maximum level of warnings. */ 425 #pragma warning( push ) 426 #pragma warning( disable : 4324 ) 427 #endif /* _MSC_VER */ 428 429 typedef struct gray_TWorker_ 430 { 431 ft_jmp_buf jump_buffer; 432 433 TCoord ex, ey; 434 TCoord min_ex, max_ex; 435 TCoord min_ey, max_ey; 436 437 TArea area; 438 TCoord cover; 439 int invalid; 440 441 PCell cells; 442 FT_PtrDist max_cells; 443 FT_PtrDist num_cells; 444 445 TPos x, y; 446 447 FT_Outline outline; 448 TPixmap target; 449 450 FT_Raster_Span_Func render_span; 451 void* render_span_data; 452 453 PCell* ycells; 454 455 } gray_TWorker, *gray_PWorker; 456 457 #if defined( _MSC_VER ) 458 #pragma warning( pop ) 459 #endif 460 461 462 #ifndef FT_STATIC_RASTER 463 #define ras (*worker) 464 #else 465 static gray_TWorker ras; 466 #endif 467 468 469 typedef struct gray_TRaster_ 470 { 471 void* memory; 472 473 } gray_TRaster, *gray_PRaster; 474 475 476 #ifdef FT_DEBUG_LEVEL_TRACE 477 478 /* to be called while in the debugger -- */ 479 /* this function causes a compiler warning since it is unused otherwise */ 480 static void gray_dump_cells(RAS_ARG)481 gray_dump_cells( RAS_ARG ) 482 { 483 int y; 484 485 486 for ( y = ras.min_ey; y < ras.max_ey; y++ ) 487 { 488 PCell cell = ras.ycells[y - ras.min_ey]; 489 490 491 printf( "%3d:", y ); 492 493 for ( ; cell != NULL; cell = cell->next ) 494 printf( " (%3d, c:%4d, a:%6d)", 495 cell->x, cell->cover, cell->area ); 496 printf( "\n" ); 497 } 498 } 499 500 #endif /* FT_DEBUG_LEVEL_TRACE */ 501 502 503 /*************************************************************************/ 504 /* */ 505 /* Record the current cell in the table. */ 506 /* */ 507 static PCell gray_find_cell(RAS_ARG)508 gray_find_cell( RAS_ARG ) 509 { 510 PCell *pcell, cell; 511 TCoord x = ras.ex; 512 513 514 pcell = &ras.ycells[ras.ey - ras.min_ey]; 515 for (;;) 516 { 517 cell = *pcell; 518 if ( cell == NULL || cell->x > x ) 519 break; 520 521 if ( cell->x == x ) 522 goto Exit; 523 524 pcell = &cell->next; 525 } 526 527 if ( ras.num_cells >= ras.max_cells ) 528 ft_longjmp( ras.jump_buffer, 1 ); 529 530 cell = ras.cells + ras.num_cells++; 531 cell->x = x; 532 cell->area = 0; 533 cell->cover = 0; 534 535 cell->next = *pcell; 536 *pcell = cell; 537 538 Exit: 539 return cell; 540 } 541 542 543 static void gray_record_cell(RAS_ARG)544 gray_record_cell( RAS_ARG ) 545 { 546 if ( ras.area | ras.cover ) 547 { 548 PCell cell = gray_find_cell( RAS_VAR ); 549 550 551 cell->area += ras.area; 552 cell->cover += ras.cover; 553 } 554 } 555 556 557 /*************************************************************************/ 558 /* */ 559 /* Set the current cell to a new position. */ 560 /* */ 561 static void gray_set_cell(RAS_ARG_ TCoord ex,TCoord ey)562 gray_set_cell( RAS_ARG_ TCoord ex, 563 TCoord ey ) 564 { 565 /* Move the cell pointer to a new position. We set the `invalid' */ 566 /* flag to indicate that the cell isn't part of those we're interested */ 567 /* in during the render phase. This means that: */ 568 /* */ 569 /* . the new vertical position must be within min_ey..max_ey-1. */ 570 /* . the new horizontal position must be strictly less than max_ex */ 571 /* */ 572 /* Note that if a cell is to the left of the clipping region, it is */ 573 /* actually set to the (min_ex-1) horizontal position. */ 574 575 /* All cells that are on the left of the clipping region go to the */ 576 /* min_ex - 1 horizontal position. */ 577 578 if ( ex < ras.min_ex ) 579 ex = ras.min_ex - 1; 580 581 /* record the current one if it is valid */ 582 if ( !ras.invalid ) 583 gray_record_cell( RAS_VAR ); 584 585 ras.area = 0; 586 ras.cover = 0; 587 ras.ex = ex; 588 ras.ey = ey; 589 590 ras.invalid = ( ey >= ras.max_ey || ey < ras.min_ey || 591 ex >= ras.max_ex ); 592 } 593 594 595 #ifndef FT_LONG64 596 597 /*************************************************************************/ 598 /* */ 599 /* Render a scanline as one or more cells. */ 600 /* */ 601 static void gray_render_scanline(RAS_ARG_ TCoord ey,TPos x1,TCoord y1,TPos x2,TCoord y2)602 gray_render_scanline( RAS_ARG_ TCoord ey, 603 TPos x1, 604 TCoord y1, 605 TPos x2, 606 TCoord y2 ) 607 { 608 TCoord ex1, ex2, fx1, fx2, first, delta, mod; 609 TPos p, dx; 610 int incr; 611 612 613 ex1 = TRUNC( x1 ); 614 ex2 = TRUNC( x2 ); 615 616 /* trivial case. Happens often */ 617 if ( y1 == y2 ) 618 { 619 gray_set_cell( RAS_VAR_ ex2, ey ); 620 return; 621 } 622 623 fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) ); 624 fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) ); 625 delta = y2 - y1; 626 627 /* everything is located in a single cell. That is easy! */ 628 /* */ 629 if ( ex1 == ex2 ) 630 { 631 ras.area += (TArea)(( fx1 + fx2 ) * delta); 632 ras.cover += delta; 633 return; 634 } 635 636 /* ok, we'll have to render a run of adjacent cells on the same */ 637 /* scanline... */ 638 /* */ 639 dx = x2 - x1; 640 641 if ( dx > 0 ) 642 { 643 p = ( ONE_PIXEL - fx1 ) * delta; 644 first = ONE_PIXEL; 645 incr = 1; 646 } 647 else 648 { 649 p = fx1 * delta; 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 660 ex1 += incr; 661 gray_set_cell( RAS_VAR_ ex1, ey ); 662 y1 += delta; 663 664 if ( ex1 != ex2 ) 665 { 666 TCoord lift, rem; 667 668 669 p = ONE_PIXEL * ( y2 - y1 + delta ); 670 FT_DIV_MOD( TCoord, p, dx, lift, rem ); 671 672 mod -= (int)dx; 673 674 do 675 { 676 delta = lift; 677 mod += rem; 678 if ( mod >= 0 ) 679 { 680 mod -= (TCoord)dx; 681 delta++; 682 } 683 684 ras.area += (TArea)(ONE_PIXEL * delta); 685 ras.cover += delta; 686 y1 += delta; 687 ex1 += incr; 688 gray_set_cell( RAS_VAR_ ex1, ey ); 689 } while ( ex1 != ex2 ); 690 } 691 692 delta = y2 - y1; 693 ras.area += (TArea)(( fx2 + ONE_PIXEL - first ) * delta); 694 ras.cover += delta; 695 } 696 697 698 /*************************************************************************/ 699 /* */ 700 /* Render a given line as a series of scanlines. */ 701 /* */ 702 static void gray_render_line(RAS_ARG_ TPos to_x,TPos to_y)703 gray_render_line( RAS_ARG_ TPos to_x, 704 TPos to_y ) 705 { 706 TCoord ey1, ey2, fy1, fy2, first, delta, mod; 707 TPos p, dx, dy, x, x2; 708 int incr; 709 710 711 ey1 = TRUNC( ras.y ); 712 ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */ 713 714 /* perform vertical clipping */ 715 if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || 716 ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) 717 goto End; 718 719 fy1 = (TCoord)( ras.y - SUBPIXELS( ey1 ) ); 720 fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) ); 721 722 /* everything is on a single scanline */ 723 if ( ey1 == ey2 ) 724 { 725 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 ); 726 goto End; 727 } 728 729 dx = to_x - ras.x; 730 dy = to_y - ras.y; 731 732 /* vertical line - avoid calling gray_render_scanline */ 733 if ( dx == 0 ) 734 { 735 TCoord ex = TRUNC( ras.x ); 736 TCoord two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 ); 737 TArea area; 738 739 740 if ( dy > 0) 741 { 742 first = ONE_PIXEL; 743 incr = 1; 744 } 745 else 746 { 747 first = 0; 748 incr = -1; 749 } 750 751 delta = first - fy1; 752 ras.area += (TArea)two_fx * delta; 753 ras.cover += delta; 754 ey1 += incr; 755 756 gray_set_cell( RAS_VAR_ ex, ey1 ); 757 758 delta = first + first - ONE_PIXEL; 759 area = (TArea)two_fx * delta; 760 while ( ey1 != ey2 ) 761 { 762 ras.area += area; 763 ras.cover += delta; 764 ey1 += incr; 765 766 gray_set_cell( RAS_VAR_ ex, ey1 ); 767 } 768 769 delta = fy2 - ONE_PIXEL + first; 770 ras.area += (TArea)two_fx * delta; 771 ras.cover += delta; 772 773 goto End; 774 } 775 776 /* ok, we have to render several scanlines */ 777 if ( dy > 0) 778 { 779 p = ( ONE_PIXEL - fy1 ) * dx; 780 first = ONE_PIXEL; 781 incr = 1; 782 } 783 else 784 { 785 p = fy1 * dx; 786 first = 0; 787 incr = -1; 788 dy = -dy; 789 } 790 791 FT_DIV_MOD( TCoord, p, dy, delta, mod ); 792 793 x = ras.x + delta; 794 gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first ); 795 796 ey1 += incr; 797 gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); 798 799 if ( ey1 != ey2 ) 800 { 801 TCoord lift, rem; 802 803 804 p = ONE_PIXEL * dx; 805 FT_DIV_MOD( TCoord, p, dy, lift, rem ); 806 mod -= (TCoord)dy; 807 808 do 809 { 810 delta = lift; 811 mod += rem; 812 if ( mod >= 0 ) 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 gray_render_line(RAS_ARG_ TPos to_x,TPos to_y)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( dx ); 903 FT_UDIVPREP( 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 gray_split_conic(FT_Vector * base)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 gray_render_conic(RAS_ARG_ const FT_Vector * control,const FT_Vector * to)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 gray_split_cubic(FT_Vector * base)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 gray_render_cubic(RAS_ARG_ const FT_Vector * control1,const FT_Vector * control2,const FT_Vector * to)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( dy * dx1 - 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( dy * dx2 - 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 gray_move_to(const FT_Vector * to,gray_PWorker worker)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 gray_line_to(const FT_Vector * to,gray_PWorker worker)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 gray_conic_to(const FT_Vector * control,const FT_Vector * to,gray_PWorker worker)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 gray_cubic_to(const FT_Vector * control1,const FT_Vector * control2,const FT_Vector * to,gray_PWorker worker)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 gray_hline(RAS_ARG_ TCoord x,TCoord y,TArea area,TCoord acount)1234 gray_hline( RAS_ARG_ TCoord x, 1235 TCoord y, 1236 TArea area, 1237 TCoord acount ) 1238 { 1239 int coverage; 1240 FT_Span span; 1241 1242 1243 /* compute the coverage line's coverage, depending on the */ 1244 /* outline fill rule */ 1245 /* */ 1246 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */ 1247 /* */ 1248 coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) ); 1249 /* use range 0..256 */ 1250 if ( coverage < 0 ) 1251 coverage = -coverage; 1252 1253 if ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) 1254 { 1255 coverage &= 511; 1256 1257 if ( coverage > 256 ) 1258 coverage = 512 - coverage; 1259 else if ( coverage == 256 ) 1260 coverage = 255; 1261 } 1262 else 1263 { 1264 /* normal non-zero winding rule */ 1265 if ( coverage >= 256 ) 1266 coverage = 255; 1267 } 1268 1269 if ( ras.render_span ) /* for FT_RASTER_FLAG_DIRECT only */ 1270 { 1271 span.x = (short)x; 1272 span.len = (unsigned short)acount; 1273 span.coverage = (unsigned char)coverage; 1274 1275 ras.render_span( y, 1, &span, ras.render_span_data ); 1276 } 1277 else 1278 { 1279 unsigned char* q = ras.target.origin - ras.target.pitch * y + x; 1280 unsigned char c = (unsigned char)coverage; 1281 1282 1283 /* For small-spans it is faster to do it by ourselves than 1284 * calling `memset'. This is mainly due to the cost of the 1285 * function call. 1286 */ 1287 switch ( acount ) 1288 { 1289 case 7: *q++ = c; 1290 case 6: *q++ = c; 1291 case 5: *q++ = c; 1292 case 4: *q++ = c; 1293 case 3: *q++ = c; 1294 case 2: *q++ = c; 1295 case 1: *q = c; 1296 case 0: break; 1297 default: 1298 FT_MEM_SET( q, c, acount ); 1299 } 1300 } 1301 } 1302 1303 1304 static void gray_sweep(RAS_ARG)1305 gray_sweep( RAS_ARG ) 1306 { 1307 int y; 1308 1309 1310 if ( ras.num_cells == 0 ) 1311 return; 1312 1313 FT_TRACE7(( "gray_sweep: start\n" )); 1314 1315 for ( y = ras.min_ey; y < ras.max_ey; y++ ) 1316 { 1317 PCell cell = ras.ycells[y - ras.min_ey]; 1318 TCoord cover = 0; 1319 TCoord x = ras.min_ex; 1320 1321 1322 for ( ; cell != NULL; cell = cell->next ) 1323 { 1324 TArea area; 1325 1326 1327 if ( cover != 0 && cell->x > x ) 1328 gray_hline( RAS_VAR_ x, y, (TArea)cover * ( ONE_PIXEL * 2 ), 1329 cell->x - x ); 1330 1331 cover += cell->cover; 1332 area = (TArea)cover * ( ONE_PIXEL * 2 ) - cell->area; 1333 1334 if ( area != 0 && cell->x >= ras.min_ex ) 1335 gray_hline( RAS_VAR_ cell->x, y, area, 1 ); 1336 1337 x = cell->x + 1; 1338 } 1339 1340 if ( cover != 0 ) 1341 gray_hline( RAS_VAR_ x, y, (TArea)cover * ( ONE_PIXEL * 2 ), 1342 ras.max_ex - x ); 1343 } 1344 1345 FT_TRACE7(( "gray_sweep: end\n" )); 1346 } 1347 1348 1349 #ifdef STANDALONE_ 1350 1351 /*************************************************************************/ 1352 /* */ 1353 /* The following functions should only compile in stand-alone mode, */ 1354 /* i.e., when building this component without the rest of FreeType. */ 1355 /* */ 1356 /*************************************************************************/ 1357 1358 /*************************************************************************/ 1359 /* */ 1360 /* <Function> */ 1361 /* FT_Outline_Decompose */ 1362 /* */ 1363 /* <Description> */ 1364 /* Walk over an outline's structure to decompose it into individual */ 1365 /* segments and Bézier arcs. This function is also able to emit */ 1366 /* `move to' and `close to' operations to indicate the start and end */ 1367 /* of new contours in the outline. */ 1368 /* */ 1369 /* <Input> */ 1370 /* outline :: A pointer to the source target. */ 1371 /* */ 1372 /* func_interface :: A table of `emitters', i.e., function pointers */ 1373 /* called during decomposition to indicate path */ 1374 /* operations. */ 1375 /* */ 1376 /* <InOut> */ 1377 /* user :: A typeless pointer which is passed to each */ 1378 /* emitter during the decomposition. It can be */ 1379 /* used to store the state during the */ 1380 /* decomposition. */ 1381 /* */ 1382 /* <Return> */ 1383 /* Error code. 0 means success. */ 1384 /* */ 1385 static int FT_Outline_Decompose(const FT_Outline * outline,const FT_Outline_Funcs * func_interface,void * user)1386 FT_Outline_Decompose( const FT_Outline* outline, 1387 const FT_Outline_Funcs* func_interface, 1388 void* user ) 1389 { 1390 #undef SCALED 1391 #define SCALED( x ) ( ( (x) << shift ) - delta ) 1392 1393 FT_Vector v_last; 1394 FT_Vector v_control; 1395 FT_Vector v_start; 1396 1397 FT_Vector* point; 1398 FT_Vector* limit; 1399 char* tags; 1400 1401 int error; 1402 1403 int n; /* index of contour in outline */ 1404 int first; /* index of first point in contour */ 1405 char tag; /* current point's state */ 1406 1407 int shift; 1408 TPos delta; 1409 1410 1411 if ( !outline ) 1412 return FT_THROW( Invalid_Outline ); 1413 1414 if ( !func_interface ) 1415 return FT_THROW( Invalid_Argument ); 1416 1417 shift = func_interface->shift; 1418 delta = func_interface->delta; 1419 first = 0; 1420 1421 for ( n = 0; n < outline->n_contours; n++ ) 1422 { 1423 int last; /* index of last point in contour */ 1424 1425 1426 FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n )); 1427 1428 last = outline->contours[n]; 1429 if ( last < 0 ) 1430 goto Invalid_Outline; 1431 limit = outline->points + last; 1432 1433 v_start = outline->points[first]; 1434 v_start.x = SCALED( v_start.x ); 1435 v_start.y = SCALED( v_start.y ); 1436 1437 v_last = outline->points[last]; 1438 v_last.x = SCALED( v_last.x ); 1439 v_last.y = SCALED( v_last.y ); 1440 1441 v_control = v_start; 1442 1443 point = outline->points + first; 1444 tags = outline->tags + first; 1445 tag = FT_CURVE_TAG( tags[0] ); 1446 1447 /* A contour cannot start with a cubic control point! */ 1448 if ( tag == FT_CURVE_TAG_CUBIC ) 1449 goto Invalid_Outline; 1450 1451 /* check first point to determine origin */ 1452 if ( tag == FT_CURVE_TAG_CONIC ) 1453 { 1454 /* first point is conic control. Yes, this happens. */ 1455 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON ) 1456 { 1457 /* start at last point if it is on the curve */ 1458 v_start = v_last; 1459 limit--; 1460 } 1461 else 1462 { 1463 /* if both first and last points are conic, */ 1464 /* start at their middle and record its position */ 1465 /* for closure */ 1466 v_start.x = ( v_start.x + v_last.x ) / 2; 1467 v_start.y = ( v_start.y + v_last.y ) / 2; 1468 1469 v_last = v_start; 1470 } 1471 point--; 1472 tags--; 1473 } 1474 1475 FT_TRACE5(( " move to (%.2f, %.2f)\n", 1476 v_start.x / 64.0, v_start.y / 64.0 )); 1477 error = func_interface->move_to( &v_start, user ); 1478 if ( error ) 1479 goto Exit; 1480 1481 while ( point < limit ) 1482 { 1483 point++; 1484 tags++; 1485 1486 tag = FT_CURVE_TAG( tags[0] ); 1487 switch ( tag ) 1488 { 1489 case FT_CURVE_TAG_ON: /* emit a single line_to */ 1490 { 1491 FT_Vector vec; 1492 1493 1494 vec.x = SCALED( point->x ); 1495 vec.y = SCALED( point->y ); 1496 1497 FT_TRACE5(( " line to (%.2f, %.2f)\n", 1498 vec.x / 64.0, vec.y / 64.0 )); 1499 error = func_interface->line_to( &vec, user ); 1500 if ( error ) 1501 goto Exit; 1502 continue; 1503 } 1504 1505 case FT_CURVE_TAG_CONIC: /* consume conic arcs */ 1506 v_control.x = SCALED( point->x ); 1507 v_control.y = SCALED( point->y ); 1508 1509 Do_Conic: 1510 if ( point < limit ) 1511 { 1512 FT_Vector vec; 1513 FT_Vector v_middle; 1514 1515 1516 point++; 1517 tags++; 1518 tag = FT_CURVE_TAG( tags[0] ); 1519 1520 vec.x = SCALED( point->x ); 1521 vec.y = SCALED( point->y ); 1522 1523 if ( tag == FT_CURVE_TAG_ON ) 1524 { 1525 FT_TRACE5(( " conic to (%.2f, %.2f)" 1526 " with control (%.2f, %.2f)\n", 1527 vec.x / 64.0, vec.y / 64.0, 1528 v_control.x / 64.0, v_control.y / 64.0 )); 1529 error = func_interface->conic_to( &v_control, &vec, user ); 1530 if ( error ) 1531 goto Exit; 1532 continue; 1533 } 1534 1535 if ( tag != FT_CURVE_TAG_CONIC ) 1536 goto Invalid_Outline; 1537 1538 v_middle.x = ( v_control.x + vec.x ) / 2; 1539 v_middle.y = ( v_control.y + vec.y ) / 2; 1540 1541 FT_TRACE5(( " conic to (%.2f, %.2f)" 1542 " with control (%.2f, %.2f)\n", 1543 v_middle.x / 64.0, v_middle.y / 64.0, 1544 v_control.x / 64.0, v_control.y / 64.0 )); 1545 error = func_interface->conic_to( &v_control, &v_middle, user ); 1546 if ( error ) 1547 goto Exit; 1548 1549 v_control = vec; 1550 goto Do_Conic; 1551 } 1552 1553 FT_TRACE5(( " conic to (%.2f, %.2f)" 1554 " with control (%.2f, %.2f)\n", 1555 v_start.x / 64.0, v_start.y / 64.0, 1556 v_control.x / 64.0, v_control.y / 64.0 )); 1557 error = func_interface->conic_to( &v_control, &v_start, user ); 1558 goto Close; 1559 1560 default: /* FT_CURVE_TAG_CUBIC */ 1561 { 1562 FT_Vector vec1, vec2; 1563 1564 1565 if ( point + 1 > limit || 1566 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC ) 1567 goto Invalid_Outline; 1568 1569 point += 2; 1570 tags += 2; 1571 1572 vec1.x = SCALED( point[-2].x ); 1573 vec1.y = SCALED( point[-2].y ); 1574 1575 vec2.x = SCALED( point[-1].x ); 1576 vec2.y = SCALED( point[-1].y ); 1577 1578 if ( point <= limit ) 1579 { 1580 FT_Vector vec; 1581 1582 1583 vec.x = SCALED( point->x ); 1584 vec.y = SCALED( point->y ); 1585 1586 FT_TRACE5(( " cubic to (%.2f, %.2f)" 1587 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n", 1588 vec.x / 64.0, vec.y / 64.0, 1589 vec1.x / 64.0, vec1.y / 64.0, 1590 vec2.x / 64.0, vec2.y / 64.0 )); 1591 error = func_interface->cubic_to( &vec1, &vec2, &vec, user ); 1592 if ( error ) 1593 goto Exit; 1594 continue; 1595 } 1596 1597 FT_TRACE5(( " cubic to (%.2f, %.2f)" 1598 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n", 1599 v_start.x / 64.0, v_start.y / 64.0, 1600 vec1.x / 64.0, vec1.y / 64.0, 1601 vec2.x / 64.0, vec2.y / 64.0 )); 1602 error = func_interface->cubic_to( &vec1, &vec2, &v_start, user ); 1603 goto Close; 1604 } 1605 } 1606 } 1607 1608 /* close the contour with a line segment */ 1609 FT_TRACE5(( " line to (%.2f, %.2f)\n", 1610 v_start.x / 64.0, v_start.y / 64.0 )); 1611 error = func_interface->line_to( &v_start, user ); 1612 1613 Close: 1614 if ( error ) 1615 goto Exit; 1616 1617 first = last + 1; 1618 } 1619 1620 FT_TRACE5(( "FT_Outline_Decompose: Done\n", n )); 1621 return 0; 1622 1623 Exit: 1624 FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error )); 1625 return error; 1626 1627 Invalid_Outline: 1628 return FT_THROW( Invalid_Outline ); 1629 } 1630 1631 1632 /*************************************************************************/ 1633 /* */ 1634 /* <Function> */ 1635 /* FT_Outline_Get_CBox */ 1636 /* */ 1637 /* <Description> */ 1638 /* Return an outline's `control box'. The control box encloses all */ 1639 /* the outline's points, including Bézier control points. Though it */ 1640 /* coincides with the exact bounding box for most glyphs, it can be */ 1641 /* slightly larger in some situations (like when rotating an outline */ 1642 /* that contains Bézier outside arcs). */ 1643 /* */ 1644 /* Computing the control box is very fast, while getting the bounding */ 1645 /* box can take much more time as it needs to walk over all segments */ 1646 /* and arcs in the outline. To get the latter, you can use the */ 1647 /* `ftbbox' component, which is dedicated to this single task. */ 1648 /* */ 1649 /* <Input> */ 1650 /* outline :: A pointer to the source outline descriptor. */ 1651 /* */ 1652 /* <Output> */ 1653 /* acbox :: The outline's control box. */ 1654 /* */ 1655 /* <Note> */ 1656 /* See @FT_Glyph_Get_CBox for a discussion of tricky fonts. */ 1657 /* */ 1658 1659 static void FT_Outline_Get_CBox(const FT_Outline * outline,FT_BBox * acbox)1660 FT_Outline_Get_CBox( const FT_Outline* outline, 1661 FT_BBox *acbox ) 1662 { 1663 TPos xMin, yMin, xMax, yMax; 1664 1665 1666 if ( outline && acbox ) 1667 { 1668 if ( outline->n_points == 0 ) 1669 { 1670 xMin = 0; 1671 yMin = 0; 1672 xMax = 0; 1673 yMax = 0; 1674 } 1675 else 1676 { 1677 FT_Vector* vec = outline->points; 1678 FT_Vector* limit = vec + outline->n_points; 1679 1680 1681 xMin = xMax = vec->x; 1682 yMin = yMax = vec->y; 1683 vec++; 1684 1685 for ( ; vec < limit; vec++ ) 1686 { 1687 TPos x, y; 1688 1689 1690 x = vec->x; 1691 if ( x < xMin ) xMin = x; 1692 if ( x > xMax ) xMax = x; 1693 1694 y = vec->y; 1695 if ( y < yMin ) yMin = y; 1696 if ( y > yMax ) yMax = y; 1697 } 1698 } 1699 acbox->xMin = xMin; 1700 acbox->xMax = xMax; 1701 acbox->yMin = yMin; 1702 acbox->yMax = yMax; 1703 } 1704 } 1705 1706 #endif /* STANDALONE_ */ 1707 1708 1709 FT_DEFINE_OUTLINE_FUNCS( 1710 func_interface, 1711 1712 (FT_Outline_MoveTo_Func) gray_move_to, 1713 (FT_Outline_LineTo_Func) gray_line_to, 1714 (FT_Outline_ConicTo_Func)gray_conic_to, 1715 (FT_Outline_CubicTo_Func)gray_cubic_to, 1716 0, 1717 0 ) 1718 1719 1720 static int gray_convert_glyph_inner(RAS_ARG)1721 gray_convert_glyph_inner( RAS_ARG ) 1722 { 1723 1724 volatile int error = 0; 1725 1726 #ifdef FT_CONFIG_OPTION_PIC 1727 FT_Outline_Funcs func_interface; 1728 Init_Class_func_interface(&func_interface); 1729 #endif 1730 1731 if ( ft_setjmp( ras.jump_buffer ) == 0 ) 1732 { 1733 error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras ); 1734 if ( !ras.invalid ) 1735 gray_record_cell( RAS_VAR ); 1736 1737 FT_TRACE7(( "band [%d..%d]: %d cells\n", 1738 ras.min_ey, ras.max_ey, ras.num_cells )); 1739 } 1740 else 1741 { 1742 error = FT_THROW( Memory_Overflow ); 1743 1744 FT_TRACE7(( "band [%d..%d]: to be bisected\n", 1745 ras.min_ey, ras.max_ey )); 1746 } 1747 1748 return error; 1749 } 1750 1751 1752 static int gray_convert_glyph(RAS_ARG)1753 gray_convert_glyph( RAS_ARG ) 1754 { 1755 TCell buffer[FT_MAX_GRAY_POOL]; 1756 TCoord band_size = FT_MAX_GRAY_POOL / 8; 1757 TCoord count = ras.max_ey - ras.min_ey; 1758 int num_bands; 1759 TCoord min, max, max_y; 1760 TCoord bands[32]; /* enough to accommodate bisections */ 1761 TCoord* band; 1762 1763 1764 /* set up vertical bands */ 1765 if ( count > band_size ) 1766 { 1767 /* two divisions rounded up */ 1768 num_bands = (int)( ( count + band_size - 1) / band_size ); 1769 band_size = ( count + num_bands - 1 ) / num_bands; 1770 } 1771 1772 min = ras.min_ey; 1773 max_y = ras.max_ey; 1774 1775 for ( ; min < max_y; min = max ) 1776 { 1777 max = min + band_size; 1778 if ( max > max_y ) 1779 max = max_y; 1780 1781 band = bands; 1782 band[1] = min; 1783 band[0] = max; 1784 1785 do 1786 { 1787 TCoord width = band[0] - band[1]; 1788 int error; 1789 1790 1791 /* memory management */ 1792 { 1793 size_t ycount = (size_t)width; 1794 size_t cell_start; 1795 1796 1797 cell_start = ( ycount * sizeof ( PCell ) + sizeof ( TCell ) - 1 ) / 1798 sizeof ( TCell ); 1799 1800 if ( FT_MAX_GRAY_POOL - cell_start < 2 ) 1801 goto ReduceBands; 1802 1803 ras.cells = buffer + cell_start; 1804 ras.max_cells = (FT_PtrDist)( FT_MAX_GRAY_POOL - cell_start ); 1805 1806 ras.ycells = (PCell*)buffer; 1807 while ( ycount ) 1808 ras.ycells[--ycount] = NULL; 1809 } 1810 1811 ras.num_cells = 0; 1812 ras.invalid = 1; 1813 ras.min_ey = band[1]; 1814 ras.max_ey = band[0]; 1815 1816 error = gray_convert_glyph_inner( RAS_VAR ); 1817 1818 if ( !error ) 1819 { 1820 gray_sweep( RAS_VAR ); 1821 band--; 1822 continue; 1823 } 1824 else if ( error != ErrRaster_Memory_Overflow ) 1825 return 1; 1826 1827 ReduceBands: 1828 /* render pool overflow; we will reduce the render band by half */ 1829 width >>= 1; 1830 1831 /* This is too complex for a single scanline; there must */ 1832 /* be some problems. */ 1833 if ( width == 0 ) 1834 { 1835 FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" )); 1836 return 1; 1837 } 1838 1839 band++; 1840 band[1] = band[0]; 1841 band[0] += width; 1842 } while ( band >= bands ); 1843 } 1844 1845 return 0; 1846 } 1847 1848 1849 static int gray_raster_render(FT_Raster raster,const FT_Raster_Params * params)1850 gray_raster_render( FT_Raster raster, 1851 const FT_Raster_Params* params ) 1852 { 1853 const FT_Outline* outline = (const FT_Outline*)params->source; 1854 const FT_Bitmap* target_map = params->target; 1855 FT_BBox cbox, clip; 1856 1857 #ifndef FT_STATIC_RASTER 1858 gray_TWorker worker[1]; 1859 #endif 1860 1861 1862 if ( !raster ) 1863 return FT_THROW( Invalid_Argument ); 1864 1865 /* this version does not support monochrome rendering */ 1866 if ( !( params->flags & FT_RASTER_FLAG_AA ) ) 1867 return FT_THROW( Invalid_Mode ); 1868 1869 if ( !outline ) 1870 return FT_THROW( Invalid_Outline ); 1871 1872 /* return immediately if the outline is empty */ 1873 if ( outline->n_points == 0 || outline->n_contours <= 0 ) 1874 return 0; 1875 1876 if ( !outline->contours || !outline->points ) 1877 return FT_THROW( Invalid_Outline ); 1878 1879 if ( outline->n_points != 1880 outline->contours[outline->n_contours - 1] + 1 ) 1881 return FT_THROW( Invalid_Outline ); 1882 1883 ras.outline = *outline; 1884 1885 if ( params->flags & FT_RASTER_FLAG_DIRECT ) 1886 { 1887 if ( !params->gray_spans ) 1888 return 0; 1889 1890 ras.render_span = (FT_Raster_Span_Func)params->gray_spans; 1891 ras.render_span_data = params->user; 1892 } 1893 else 1894 { 1895 /* if direct mode is not set, we must have a target bitmap */ 1896 if ( !target_map ) 1897 return FT_THROW( Invalid_Argument ); 1898 1899 /* nothing to do */ 1900 if ( !target_map->width || !target_map->rows ) 1901 return 0; 1902 1903 if ( !target_map->buffer ) 1904 return FT_THROW( Invalid_Argument ); 1905 1906 if ( target_map->pitch < 0 ) 1907 ras.target.origin = target_map->buffer; 1908 else 1909 ras.target.origin = target_map->buffer 1910 + ( target_map->rows - 1 ) * (unsigned int)target_map->pitch; 1911 1912 ras.target.pitch = target_map->pitch; 1913 1914 ras.render_span = (FT_Raster_Span_Func)NULL; 1915 ras.render_span_data = NULL; 1916 } 1917 1918 FT_Outline_Get_CBox( outline, &cbox ); 1919 1920 /* reject too large outline coordinates */ 1921 if ( cbox.xMin < -0x1000000L || cbox.xMax > 0x1000000L || 1922 cbox.yMin < -0x1000000L || cbox.yMax > 0x1000000L ) 1923 return FT_THROW( Invalid_Outline ); 1924 1925 /* truncate the bounding box to integer pixels */ 1926 cbox.xMin = cbox.xMin >> 6; 1927 cbox.yMin = cbox.yMin >> 6; 1928 cbox.xMax = ( cbox.xMax + 63 ) >> 6; 1929 cbox.yMax = ( cbox.yMax + 63 ) >> 6; 1930 1931 /* compute clipping box */ 1932 if ( !( params->flags & FT_RASTER_FLAG_DIRECT ) ) 1933 { 1934 /* compute clip box from target pixmap */ 1935 clip.xMin = 0; 1936 clip.yMin = 0; 1937 clip.xMax = (FT_Pos)target_map->width; 1938 clip.yMax = (FT_Pos)target_map->rows; 1939 } 1940 else if ( params->flags & FT_RASTER_FLAG_CLIP ) 1941 clip = params->clip_box; 1942 else 1943 { 1944 clip.xMin = -32768L; 1945 clip.yMin = -32768L; 1946 clip.xMax = 32767L; 1947 clip.yMax = 32767L; 1948 } 1949 1950 /* clip to target bitmap, exit if nothing to do */ 1951 ras.min_ex = FT_MAX( cbox.xMin, clip.xMin ); 1952 ras.min_ey = FT_MAX( cbox.yMin, clip.yMin ); 1953 ras.max_ex = FT_MIN( cbox.xMax, clip.xMax ); 1954 ras.max_ey = FT_MIN( cbox.yMax, clip.yMax ); 1955 1956 if ( ras.max_ex <= ras.min_ex || ras.max_ey <= ras.min_ey ) 1957 return 0; 1958 1959 return gray_convert_glyph( RAS_VAR ); 1960 } 1961 1962 1963 /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/ 1964 /**** a static object. *****/ 1965 1966 #ifdef STANDALONE_ 1967 1968 static int gray_raster_new(void * memory,FT_Raster * araster)1969 gray_raster_new( void* memory, 1970 FT_Raster* araster ) 1971 { 1972 static gray_TRaster the_raster; 1973 1974 FT_UNUSED( memory ); 1975 1976 1977 *araster = (FT_Raster)&the_raster; 1978 FT_MEM_ZERO( &the_raster, sizeof ( the_raster ) ); 1979 1980 return 0; 1981 } 1982 1983 1984 static void gray_raster_done(FT_Raster raster)1985 gray_raster_done( FT_Raster raster ) 1986 { 1987 /* nothing */ 1988 FT_UNUSED( raster ); 1989 } 1990 1991 #else /* !STANDALONE_ */ 1992 1993 static int gray_raster_new(FT_Memory memory,FT_Raster * araster)1994 gray_raster_new( FT_Memory memory, 1995 FT_Raster* araster ) 1996 { 1997 FT_Error error; 1998 gray_PRaster raster = NULL; 1999 2000 2001 *araster = 0; 2002 if ( !FT_ALLOC( raster, sizeof ( gray_TRaster ) ) ) 2003 { 2004 raster->memory = memory; 2005 *araster = (FT_Raster)raster; 2006 } 2007 2008 return error; 2009 } 2010 2011 2012 static void gray_raster_done(FT_Raster raster)2013 gray_raster_done( FT_Raster raster ) 2014 { 2015 FT_Memory memory = (FT_Memory)((gray_PRaster)raster)->memory; 2016 2017 2018 FT_FREE( raster ); 2019 } 2020 2021 #endif /* !STANDALONE_ */ 2022 2023 2024 static void gray_raster_reset(FT_Raster raster,unsigned char * pool_base,unsigned long pool_size)2025 gray_raster_reset( FT_Raster raster, 2026 unsigned char* pool_base, 2027 unsigned long pool_size ) 2028 { 2029 FT_UNUSED( raster ); 2030 FT_UNUSED( pool_base ); 2031 FT_UNUSED( pool_size ); 2032 } 2033 2034 2035 static int gray_raster_set_mode(FT_Raster raster,unsigned long mode,void * args)2036 gray_raster_set_mode( FT_Raster raster, 2037 unsigned long mode, 2038 void* args ) 2039 { 2040 FT_UNUSED( raster ); 2041 FT_UNUSED( mode ); 2042 FT_UNUSED( args ); 2043 2044 2045 return 0; /* nothing to do */ 2046 } 2047 2048 2049 FT_DEFINE_RASTER_FUNCS( 2050 ft_grays_raster, 2051 2052 FT_GLYPH_FORMAT_OUTLINE, 2053 2054 (FT_Raster_New_Func) gray_raster_new, 2055 (FT_Raster_Reset_Func) gray_raster_reset, 2056 (FT_Raster_Set_Mode_Func)gray_raster_set_mode, 2057 (FT_Raster_Render_Func) gray_raster_render, 2058 (FT_Raster_Done_Func) gray_raster_done ) 2059 2060 2061 /* END */ 2062 2063 2064 /* Local Variables: */ 2065 /* coding: utf-8 */ 2066 /* End: */ 2067