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