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