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