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