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