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