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