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