1 /**************************************************************************** 2 * 3 * ftraster.c 4 * 5 * The FreeType glyph rasterizer (body). 6 * 7 * Copyright (C) 1996-2019 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 `ftimage.h' and `ftmisc.h' into the $(incdir) 23 * directory. Typically, you should do something like 24 * 25 * - copy `src/raster/ftraster.c' (this file) to your current directory 26 * 27 * - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h' to your 28 * current directory 29 * 30 * - compile `ftraster' with the STANDALONE_ macro defined, as in 31 * 32 * cc -c -DSTANDALONE_ ftraster.c 33 * 34 * The renderer can be initialized with a call to 35 * `ft_standard_raster.raster_new'; a bitmap can be generated 36 * with a call to `ft_standard_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 * 46 * This is a rewrite of the FreeType 1.x scan-line converter 47 * 48 */ 49 50 #ifdef STANDALONE_ 51 52 /* The size in bytes of the render pool used by the scan-line converter */ 53 /* to do all of its work. */ 54 #define FT_RENDER_POOL_SIZE 16384L 55 56 #define FT_CONFIG_STANDARD_LIBRARY_H <stdlib.h> 57 58 #include <string.h> /* for memset */ 59 60 #include "ftmisc.h" 61 #include "ftimage.h" 62 63 #else /* !STANDALONE_ */ 64 65 #include <ft2build.h> 66 #include "ftraster.h" 67 #include FT_INTERNAL_CALC_H /* for FT_MulDiv and FT_MulDiv_No_Round */ 68 #include FT_OUTLINE_H /* for FT_Outline_Get_CBox */ 69 70 #endif /* !STANDALONE_ */ 71 72 73 /************************************************************************** 74 * 75 * A simple technical note on how the raster works 76 * ----------------------------------------------- 77 * 78 * Converting an outline into a bitmap is achieved in several steps: 79 * 80 * 1 - Decomposing the outline into successive `profiles'. Each 81 * profile is simply an array of scanline intersections on a given 82 * dimension. A profile's main attributes are 83 * 84 * o its scanline position boundaries, i.e. `Ymin' and `Ymax' 85 * 86 * o an array of intersection coordinates for each scanline 87 * between `Ymin' and `Ymax' 88 * 89 * o a direction, indicating whether it was built going `up' or 90 * `down', as this is very important for filling rules 91 * 92 * o its drop-out mode 93 * 94 * 2 - Sweeping the target map's scanlines in order to compute segment 95 * `spans' which are then filled. Additionally, this pass 96 * performs drop-out control. 97 * 98 * The outline data is parsed during step 1 only. The profiles are 99 * built from the bottom of the render pool, used as a stack. The 100 * following graphics shows the profile list under construction: 101 * 102 * __________________________________________________________ _ _ 103 * | | | | | 104 * | profile | coordinates for | profile | coordinates for |--> 105 * | 1 | profile 1 | 2 | profile 2 |--> 106 * |_________|_________________|_________|_________________|__ _ _ 107 * 108 * ^ ^ 109 * | | 110 * start of render pool top 111 * 112 * The top of the profile stack is kept in the `top' variable. 113 * 114 * As you can see, a profile record is pushed on top of the render 115 * pool, which is then followed by its coordinates/intersections. If 116 * a change of direction is detected in the outline, a new profile is 117 * generated until the end of the outline. 118 * 119 * Note that when all profiles have been generated, the function 120 * Finalize_Profile_Table() is used to record, for each profile, its 121 * bottom-most scanline as well as the scanline above its upmost 122 * boundary. These positions are called `y-turns' because they (sort 123 * of) correspond to local extrema. They are stored in a sorted list 124 * built from the top of the render pool as a downwards stack: 125 * 126 * _ _ _______________________________________ 127 * | | 128 * <--| sorted list of | 129 * <--| extrema scanlines | 130 * _ _ __________________|____________________| 131 * 132 * ^ ^ 133 * | | 134 * maxBuff sizeBuff = end of pool 135 * 136 * This list is later used during the sweep phase in order to 137 * optimize performance (see technical note on the sweep below). 138 * 139 * Of course, the raster detects whether the two stacks collide and 140 * handles the situation properly. 141 * 142 */ 143 144 145 /*************************************************************************/ 146 /*************************************************************************/ 147 /** **/ 148 /** CONFIGURATION MACROS **/ 149 /** **/ 150 /*************************************************************************/ 151 /*************************************************************************/ 152 153 /* define DEBUG_RASTER if you want to compile a debugging version */ 154 /* #define DEBUG_RASTER */ 155 156 157 /*************************************************************************/ 158 /*************************************************************************/ 159 /** **/ 160 /** OTHER MACROS (do not change) **/ 161 /** **/ 162 /*************************************************************************/ 163 /*************************************************************************/ 164 165 /************************************************************************** 166 * 167 * The macro FT_COMPONENT is used in trace mode. It is an implicit 168 * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log 169 * messages during execution. 170 */ 171 #undef FT_COMPONENT 172 #define FT_COMPONENT raster 173 174 175 #ifdef STANDALONE_ 176 177 /* Auxiliary macros for token concatenation. */ 178 #define FT_ERR_XCAT( x, y ) x ## y 179 #define FT_ERR_CAT( x, y ) FT_ERR_XCAT( x, y ) 180 181 /* This macro is used to indicate that a function parameter is unused. */ 182 /* Its purpose is simply to reduce compiler warnings. Note also that */ 183 /* simply defining it as `(void)x' doesn't avoid warnings with certain */ 184 /* ANSI compilers (e.g. LCC). */ 185 #define FT_UNUSED( x ) (x) = (x) 186 187 /* Disable the tracing mechanism for simplicity -- developers can */ 188 /* activate it easily by redefining these macros. */ 189 #ifndef FT_ERROR 190 #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */ 191 #endif 192 193 #ifndef FT_TRACE 194 #define FT_TRACE( x ) do { } while ( 0 ) /* nothing */ 195 #define FT_TRACE1( x ) do { } while ( 0 ) /* nothing */ 196 #define FT_TRACE6( x ) do { } while ( 0 ) /* nothing */ 197 #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */ 198 #endif 199 200 #ifndef FT_THROW 201 #define FT_THROW( e ) FT_ERR_CAT( Raster_Err_, e ) 202 #endif 203 204 #define Raster_Err_None 0 205 #define Raster_Err_Not_Ini -1 206 #define Raster_Err_Overflow -2 207 #define Raster_Err_Neg_Height -3 208 #define Raster_Err_Invalid -4 209 #define Raster_Err_Unsupported -5 210 211 #define ft_memset memset 212 213 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, raster_new_, \ 214 raster_reset_, raster_set_mode_, \ 215 raster_render_, raster_done_ ) \ 216 const FT_Raster_Funcs class_ = \ 217 { \ 218 glyph_format_, \ 219 raster_new_, \ 220 raster_reset_, \ 221 raster_set_mode_, \ 222 raster_render_, \ 223 raster_done_ \ 224 }; 225 226 #else /* !STANDALONE_ */ 227 228 229 #include FT_INTERNAL_OBJECTS_H 230 #include FT_INTERNAL_DEBUG_H /* for FT_TRACE, FT_ERROR, and FT_THROW */ 231 232 #include "rasterrs.h" 233 234 #define Raster_Err_None FT_Err_Ok 235 #define Raster_Err_Not_Ini Raster_Err_Raster_Uninitialized 236 #define Raster_Err_Overflow Raster_Err_Raster_Overflow 237 #define Raster_Err_Neg_Height Raster_Err_Raster_Negative_Height 238 #define Raster_Err_Invalid Raster_Err_Invalid_Outline 239 #define Raster_Err_Unsupported Raster_Err_Cannot_Render_Glyph 240 241 242 #endif /* !STANDALONE_ */ 243 244 245 #ifndef FT_MEM_SET 246 #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c ) 247 #endif 248 249 #ifndef FT_MEM_ZERO 250 #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count ) 251 #endif 252 253 #ifndef FT_ZERO 254 #define FT_ZERO( p ) FT_MEM_ZERO( p, sizeof ( *(p) ) ) 255 #endif 256 257 /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is */ 258 /* typically a small value and the result of a*b is known to fit into */ 259 /* 32 bits. */ 260 #define FMulDiv( a, b, c ) ( (a) * (b) / (c) ) 261 262 /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */ 263 /* for clipping computations. It simply uses the FT_MulDiv() function */ 264 /* defined in `ftcalc.h'. */ 265 #define SMulDiv FT_MulDiv 266 #define SMulDiv_No_Round FT_MulDiv_No_Round 267 268 /* The rasterizer is a very general purpose component; please leave */ 269 /* the following redefinitions there (you never know your target */ 270 /* environment). */ 271 272 #ifndef TRUE 273 #define TRUE 1 274 #endif 275 276 #ifndef FALSE 277 #define FALSE 0 278 #endif 279 280 #ifndef NULL 281 #define NULL (void*)0 282 #endif 283 284 #ifndef SUCCESS 285 #define SUCCESS 0 286 #endif 287 288 #ifndef FAILURE 289 #define FAILURE 1 290 #endif 291 292 293 #define MaxBezier 32 /* The maximum number of stacked Bezier curves. */ 294 /* Setting this constant to more than 32 is a */ 295 /* pure waste of space. */ 296 297 #define Pixel_Bits 6 /* fractional bits of *input* coordinates */ 298 299 300 /*************************************************************************/ 301 /*************************************************************************/ 302 /** **/ 303 /** SIMPLE TYPE DECLARATIONS **/ 304 /** **/ 305 /*************************************************************************/ 306 /*************************************************************************/ 307 308 typedef int Int; 309 typedef unsigned int UInt; 310 typedef short Short; 311 typedef unsigned short UShort, *PUShort; 312 typedef long Long, *PLong; 313 typedef unsigned long ULong; 314 315 typedef unsigned char Byte, *PByte; 316 typedef char Bool; 317 318 319 typedef union Alignment_ 320 { 321 Long l; 322 void* p; 323 void (*f)(void); 324 325 } Alignment, *PAlignment; 326 327 328 typedef struct TPoint_ 329 { 330 Long x; 331 Long y; 332 333 } TPoint; 334 335 336 /* values for the `flags' bit field */ 337 #define Flow_Up 0x08U 338 #define Overshoot_Top 0x10U 339 #define Overshoot_Bottom 0x20U 340 341 342 /* States of each line, arc, and profile */ 343 typedef enum TStates_ 344 { 345 Unknown_State, 346 Ascending_State, 347 Descending_State, 348 Flat_State 349 350 } TStates; 351 352 353 typedef struct TProfile_ TProfile; 354 typedef TProfile* PProfile; 355 356 struct TProfile_ 357 { 358 FT_F26Dot6 X; /* current coordinate during sweep */ 359 PProfile link; /* link to next profile (various purposes) */ 360 PLong offset; /* start of profile's data in render pool */ 361 UShort flags; /* Bit 0-2: drop-out mode */ 362 /* Bit 3: profile orientation (up/down) */ 363 /* Bit 4: is top profile? */ 364 /* Bit 5: is bottom profile? */ 365 Long height; /* profile's height in scanlines */ 366 Long start; /* profile's starting scanline */ 367 368 Int countL; /* number of lines to step before this */ 369 /* profile becomes drawable */ 370 371 PProfile next; /* next profile in same contour, used */ 372 /* during drop-out control */ 373 }; 374 375 typedef PProfile TProfileList; 376 typedef PProfile* PProfileList; 377 378 379 /* Simple record used to implement a stack of bands, required */ 380 /* by the sub-banding mechanism */ 381 typedef struct black_TBand_ 382 { 383 Short y_min; /* band's minimum */ 384 Short y_max; /* band's maximum */ 385 386 } black_TBand; 387 388 389 #define AlignProfileSize \ 390 ( ( sizeof ( TProfile ) + sizeof ( Alignment ) - 1 ) / sizeof ( Long ) ) 391 392 393 #undef RAS_ARG 394 #undef RAS_ARGS 395 #undef RAS_VAR 396 #undef RAS_VARS 397 398 #ifdef FT_STATIC_RASTER 399 400 401 #define RAS_ARGS /* void */ 402 #define RAS_ARG void 403 404 #define RAS_VARS /* void */ 405 #define RAS_VAR /* void */ 406 407 #define FT_UNUSED_RASTER do { } while ( 0 ) 408 409 410 #else /* !FT_STATIC_RASTER */ 411 412 413 #define RAS_ARGS black_PWorker worker, 414 #define RAS_ARG black_PWorker worker 415 416 #define RAS_VARS worker, 417 #define RAS_VAR worker 418 419 #define FT_UNUSED_RASTER FT_UNUSED( worker ) 420 421 422 #endif /* !FT_STATIC_RASTER */ 423 424 425 typedef struct black_TWorker_ black_TWorker, *black_PWorker; 426 427 428 /* prototypes used for sweep function dispatch */ 429 typedef void 430 Function_Sweep_Init( RAS_ARGS Short* min, 431 Short* max ); 432 433 typedef void 434 Function_Sweep_Span( RAS_ARGS Short y, 435 FT_F26Dot6 x1, 436 FT_F26Dot6 x2, 437 PProfile left, 438 PProfile right ); 439 440 typedef void 441 Function_Sweep_Step( RAS_ARG ); 442 443 444 /* NOTE: These operations are only valid on 2's complement processors */ 445 #undef FLOOR 446 #undef CEILING 447 #undef TRUNC 448 #undef SCALED 449 450 #define FLOOR( x ) ( (x) & -ras.precision ) 451 #define CEILING( x ) ( ( (x) + ras.precision - 1 ) & -ras.precision ) 452 #define TRUNC( x ) ( (Long)(x) >> ras.precision_bits ) 453 #define FRAC( x ) ( (x) & ( ras.precision - 1 ) ) 454 455 /* scale and shift grid to pixel centers */ 456 #define SCALED( x ) ( (x) * ras.precision_scale - ras.precision_half ) 457 458 #define IS_BOTTOM_OVERSHOOT( x ) \ 459 (Bool)( CEILING( x ) - x >= ras.precision_half ) 460 #define IS_TOP_OVERSHOOT( x ) \ 461 (Bool)( x - FLOOR( x ) >= ras.precision_half ) 462 463 #if FT_RENDER_POOL_SIZE > 2048 464 #define FT_MAX_BLACK_POOL ( FT_RENDER_POOL_SIZE / sizeof ( Long ) ) 465 #else 466 #define FT_MAX_BLACK_POOL ( 2048 / sizeof ( Long ) ) 467 #endif 468 469 /* The most used variables are positioned at the top of the structure. */ 470 /* Thus, their offset can be coded with less opcodes, resulting in a */ 471 /* smaller executable. */ 472 473 struct black_TWorker_ 474 { 475 Int precision_bits; /* precision related variables */ 476 Int precision; 477 Int precision_half; 478 Int precision_scale; 479 Int precision_step; 480 Int precision_jitter; 481 482 PLong buff; /* The profiles buffer */ 483 PLong sizeBuff; /* Render pool size */ 484 PLong maxBuff; /* Profiles buffer size */ 485 PLong top; /* Current cursor in buffer */ 486 487 FT_Error error; 488 489 Int numTurns; /* number of Y-turns in outline */ 490 491 TPoint* arc; /* current Bezier arc pointer */ 492 493 UShort bWidth; /* target bitmap width */ 494 PByte bOrigin; /* target bitmap bottom-left origin */ 495 496 Long lastX, lastY; 497 Long minY, maxY; 498 499 UShort num_Profs; /* current number of profiles */ 500 501 Bool fresh; /* signals a fresh new profile which */ 502 /* `start' field must be completed */ 503 Bool joint; /* signals that the last arc ended */ 504 /* exactly on a scanline. Allows */ 505 /* removal of doublets */ 506 PProfile cProfile; /* current profile */ 507 PProfile fProfile; /* head of linked list of profiles */ 508 PProfile gProfile; /* contour's first profile in case */ 509 /* of impact */ 510 511 TStates state; /* rendering state */ 512 513 FT_Bitmap target; /* description of target bit/pixmap */ 514 FT_Outline outline; 515 516 Long traceOfs; /* current offset in target bitmap */ 517 Short traceIncr; /* sweep's increment in target bitmap */ 518 519 /* dispatch variables */ 520 521 Function_Sweep_Init* Proc_Sweep_Init; 522 Function_Sweep_Span* Proc_Sweep_Span; 523 Function_Sweep_Span* Proc_Sweep_Drop; 524 Function_Sweep_Step* Proc_Sweep_Step; 525 526 Byte dropOutControl; /* current drop_out control method */ 527 528 Bool second_pass; /* indicates whether a horizontal pass */ 529 /* should be performed to control */ 530 /* drop-out accurately when calling */ 531 /* Render_Glyph. */ 532 533 TPoint arcs[3 * MaxBezier + 1]; /* The Bezier stack */ 534 535 black_TBand band_stack[16]; /* band stack used for sub-banding */ 536 Int band_top; /* band stack top */ 537 538 }; 539 540 541 typedef struct black_TRaster_ 542 { 543 void* memory; 544 545 } black_TRaster, *black_PRaster; 546 547 #ifdef FT_STATIC_RASTER 548 549 static black_TWorker ras; 550 551 #else /* !FT_STATIC_RASTER */ 552 553 #define ras (*worker) 554 555 #endif /* !FT_STATIC_RASTER */ 556 557 558 /*************************************************************************/ 559 /*************************************************************************/ 560 /** **/ 561 /** PROFILES COMPUTATION **/ 562 /** **/ 563 /*************************************************************************/ 564 /*************************************************************************/ 565 566 567 /************************************************************************** 568 * 569 * @Function: 570 * Set_High_Precision 571 * 572 * @Description: 573 * Set precision variables according to param flag. 574 * 575 * @Input: 576 * High :: 577 * Set to True for high precision (typically for ppem < 24), 578 * false otherwise. 579 */ 580 static void 581 Set_High_Precision( RAS_ARGS Int High ) 582 { 583 /* 584 * `precision_step' is used in `Bezier_Up' to decide when to split a 585 * given y-monotonous Bezier arc that crosses a scanline before 586 * approximating it as a straight segment. The default value of 32 (for 587 * low accuracy) corresponds to 588 * 589 * 32 / 64 == 0.5 pixels, 590 * 591 * while for the high accuracy case we have 592 * 593 * 256 / (1 << 12) = 0.0625 pixels. 594 * 595 * `precision_jitter' is an epsilon threshold used in 596 * `Vertical_Sweep_Span' to deal with small imperfections in the Bezier 597 * decomposition (after all, we are working with approximations only); 598 * it avoids switching on additional pixels which would cause artifacts 599 * otherwise. 600 * 601 * The value of `precision_jitter' has been determined heuristically. 602 * 603 */ 604 605 if ( High ) 606 { 607 ras.precision_bits = 12; 608 ras.precision_step = 256; 609 ras.precision_jitter = 30; 610 } 611 else 612 { 613 ras.precision_bits = 6; 614 ras.precision_step = 32; 615 ras.precision_jitter = 2; 616 } 617 618 FT_TRACE6(( "Set_High_Precision(%s)\n", High ? "true" : "false" )); 619 620 ras.precision = 1 << ras.precision_bits; 621 ras.precision_half = ras.precision >> 1; 622 ras.precision_scale = ras.precision >> Pixel_Bits; 623 } 624 625 626 /************************************************************************** 627 * 628 * @Function: 629 * New_Profile 630 * 631 * @Description: 632 * Create a new profile in the render pool. 633 * 634 * @Input: 635 * aState :: 636 * The state/orientation of the new profile. 637 * 638 * overshoot :: 639 * Whether the profile's unrounded start position 640 * differs by at least a half pixel. 641 * 642 * @Return: 643 * SUCCESS on success. FAILURE in case of overflow or of incoherent 644 * profile. 645 */ 646 static Bool 647 New_Profile( RAS_ARGS TStates aState, 648 Bool overshoot ) 649 { 650 if ( !ras.fProfile ) 651 { 652 ras.cProfile = (PProfile)ras.top; 653 ras.fProfile = ras.cProfile; 654 ras.top += AlignProfileSize; 655 } 656 657 if ( ras.top >= ras.maxBuff ) 658 { 659 ras.error = FT_THROW( Overflow ); 660 return FAILURE; 661 } 662 663 ras.cProfile->start = 0; 664 ras.cProfile->height = 0; 665 ras.cProfile->offset = ras.top; 666 ras.cProfile->link = (PProfile)0; 667 ras.cProfile->next = (PProfile)0; 668 ras.cProfile->flags = ras.dropOutControl; 669 670 switch ( aState ) 671 { 672 case Ascending_State: 673 ras.cProfile->flags |= Flow_Up; 674 if ( overshoot ) 675 ras.cProfile->flags |= Overshoot_Bottom; 676 677 FT_TRACE6(( " new ascending profile = %p\n", ras.cProfile )); 678 break; 679 680 case Descending_State: 681 if ( overshoot ) 682 ras.cProfile->flags |= Overshoot_Top; 683 FT_TRACE6(( " new descending profile = %p\n", ras.cProfile )); 684 break; 685 686 default: 687 FT_ERROR(( "New_Profile: invalid profile direction\n" )); 688 ras.error = FT_THROW( Invalid ); 689 return FAILURE; 690 } 691 692 if ( !ras.gProfile ) 693 ras.gProfile = ras.cProfile; 694 695 ras.state = aState; 696 ras.fresh = TRUE; 697 ras.joint = FALSE; 698 699 return SUCCESS; 700 } 701 702 703 /************************************************************************** 704 * 705 * @Function: 706 * End_Profile 707 * 708 * @Description: 709 * Finalize the current profile. 710 * 711 * @Input: 712 * overshoot :: 713 * Whether the profile's unrounded end position differs 714 * by at least a half pixel. 715 * 716 * @Return: 717 * SUCCESS on success. FAILURE in case of overflow or incoherency. 718 */ 719 static Bool 720 End_Profile( RAS_ARGS Bool overshoot ) 721 { 722 Long h; 723 724 725 h = (Long)( ras.top - ras.cProfile->offset ); 726 727 if ( h < 0 ) 728 { 729 FT_ERROR(( "End_Profile: negative height encountered\n" )); 730 ras.error = FT_THROW( Neg_Height ); 731 return FAILURE; 732 } 733 734 if ( h > 0 ) 735 { 736 PProfile oldProfile; 737 738 739 FT_TRACE6(( " ending profile %p, start = %ld, height = %ld\n", 740 ras.cProfile, ras.cProfile->start, h )); 741 742 ras.cProfile->height = h; 743 if ( overshoot ) 744 { 745 if ( ras.cProfile->flags & Flow_Up ) 746 ras.cProfile->flags |= Overshoot_Top; 747 else 748 ras.cProfile->flags |= Overshoot_Bottom; 749 } 750 751 oldProfile = ras.cProfile; 752 ras.cProfile = (PProfile)ras.top; 753 754 ras.top += AlignProfileSize; 755 756 ras.cProfile->height = 0; 757 ras.cProfile->offset = ras.top; 758 759 oldProfile->next = ras.cProfile; 760 ras.num_Profs++; 761 } 762 763 if ( ras.top >= ras.maxBuff ) 764 { 765 FT_TRACE1(( "overflow in End_Profile\n" )); 766 ras.error = FT_THROW( Overflow ); 767 return FAILURE; 768 } 769 770 ras.joint = FALSE; 771 772 return SUCCESS; 773 } 774 775 776 /************************************************************************** 777 * 778 * @Function: 779 * Insert_Y_Turn 780 * 781 * @Description: 782 * Insert a salient into the sorted list placed on top of the render 783 * pool. 784 * 785 * @Input: 786 * New y scanline position. 787 * 788 * @Return: 789 * SUCCESS on success. FAILURE in case of overflow. 790 */ 791 static Bool 792 Insert_Y_Turn( RAS_ARGS Int y ) 793 { 794 PLong y_turns; 795 Int n; 796 797 798 n = ras.numTurns - 1; 799 y_turns = ras.sizeBuff - ras.numTurns; 800 801 /* look for first y value that is <= */ 802 while ( n >= 0 && y < y_turns[n] ) 803 n--; 804 805 /* if it is <, simply insert it, ignore if == */ 806 if ( n >= 0 && y > y_turns[n] ) 807 do 808 { 809 Int y2 = (Int)y_turns[n]; 810 811 812 y_turns[n] = y; 813 y = y2; 814 } while ( --n >= 0 ); 815 816 if ( n < 0 ) 817 { 818 ras.maxBuff--; 819 if ( ras.maxBuff <= ras.top ) 820 { 821 ras.error = FT_THROW( Overflow ); 822 return FAILURE; 823 } 824 ras.numTurns++; 825 ras.sizeBuff[-ras.numTurns] = y; 826 } 827 828 return SUCCESS; 829 } 830 831 832 /************************************************************************** 833 * 834 * @Function: 835 * Finalize_Profile_Table 836 * 837 * @Description: 838 * Adjust all links in the profiles list. 839 * 840 * @Return: 841 * SUCCESS on success. FAILURE in case of overflow. 842 */ 843 static Bool 844 Finalize_Profile_Table( RAS_ARG ) 845 { 846 UShort n; 847 PProfile p; 848 849 850 n = ras.num_Profs; 851 p = ras.fProfile; 852 853 if ( n > 1 && p ) 854 { 855 do 856 { 857 Int bottom, top; 858 859 860 if ( n > 1 ) 861 p->link = (PProfile)( p->offset + p->height ); 862 else 863 p->link = NULL; 864 865 if ( p->flags & Flow_Up ) 866 { 867 bottom = (Int)p->start; 868 top = (Int)( p->start + p->height - 1 ); 869 } 870 else 871 { 872 bottom = (Int)( p->start - p->height + 1 ); 873 top = (Int)p->start; 874 p->start = bottom; 875 p->offset += p->height - 1; 876 } 877 878 if ( Insert_Y_Turn( RAS_VARS bottom ) || 879 Insert_Y_Turn( RAS_VARS top + 1 ) ) 880 return FAILURE; 881 882 p = p->link; 883 } while ( --n ); 884 } 885 else 886 ras.fProfile = NULL; 887 888 return SUCCESS; 889 } 890 891 892 /************************************************************************** 893 * 894 * @Function: 895 * Split_Conic 896 * 897 * @Description: 898 * Subdivide one conic Bezier into two joint sub-arcs in the Bezier 899 * stack. 900 * 901 * @Input: 902 * None (subdivided Bezier is taken from the top of the stack). 903 * 904 * @Note: 905 * This routine is the `beef' of this component. It is _the_ inner 906 * loop that should be optimized to hell to get the best performance. 907 */ 908 static void 909 Split_Conic( TPoint* base ) 910 { 911 Long a, b; 912 913 914 base[4].x = base[2].x; 915 a = base[0].x + base[1].x; 916 b = base[1].x + base[2].x; 917 base[3].x = b >> 1; 918 base[2].x = ( a + b ) >> 2; 919 base[1].x = a >> 1; 920 921 base[4].y = base[2].y; 922 a = base[0].y + base[1].y; 923 b = base[1].y + base[2].y; 924 base[3].y = b >> 1; 925 base[2].y = ( a + b ) >> 2; 926 base[1].y = a >> 1; 927 928 /* hand optimized. gcc doesn't seem to be too good at common */ 929 /* expression substitution and instruction scheduling ;-) */ 930 } 931 932 933 /************************************************************************** 934 * 935 * @Function: 936 * Split_Cubic 937 * 938 * @Description: 939 * Subdivide a third-order Bezier arc into two joint sub-arcs in the 940 * Bezier stack. 941 * 942 * @Note: 943 * This routine is the `beef' of the component. It is one of _the_ 944 * inner loops that should be optimized like hell to get the best 945 * performance. 946 */ 947 static void 948 Split_Cubic( TPoint* base ) 949 { 950 Long a, b, c; 951 952 953 base[6].x = base[3].x; 954 a = base[0].x + base[1].x; 955 b = base[1].x + base[2].x; 956 c = base[2].x + base[3].x; 957 base[5].x = c >> 1; 958 c += b; 959 base[4].x = c >> 2; 960 base[1].x = a >> 1; 961 a += b; 962 base[2].x = a >> 2; 963 base[3].x = ( a + c ) >> 3; 964 965 base[6].y = base[3].y; 966 a = base[0].y + base[1].y; 967 b = base[1].y + base[2].y; 968 c = base[2].y + base[3].y; 969 base[5].y = c >> 1; 970 c += b; 971 base[4].y = c >> 2; 972 base[1].y = a >> 1; 973 a += b; 974 base[2].y = a >> 2; 975 base[3].y = ( a + c ) >> 3; 976 } 977 978 979 /************************************************************************** 980 * 981 * @Function: 982 * Line_Up 983 * 984 * @Description: 985 * Compute the x-coordinates of an ascending line segment and store 986 * them in the render pool. 987 * 988 * @Input: 989 * x1 :: 990 * The x-coordinate of the segment's start point. 991 * 992 * y1 :: 993 * The y-coordinate of the segment's start point. 994 * 995 * x2 :: 996 * The x-coordinate of the segment's end point. 997 * 998 * y2 :: 999 * The y-coordinate of the segment's end point. 1000 * 1001 * miny :: 1002 * A lower vertical clipping bound value. 1003 * 1004 * maxy :: 1005 * An upper vertical clipping bound value. 1006 * 1007 * @Return: 1008 * SUCCESS on success, FAILURE on render pool overflow. 1009 */ 1010 static Bool 1011 Line_Up( RAS_ARGS Long x1, 1012 Long y1, 1013 Long x2, 1014 Long y2, 1015 Long miny, 1016 Long maxy ) 1017 { 1018 Long Dx, Dy; 1019 Int e1, e2, f1, f2, size; /* XXX: is `Short' sufficient? */ 1020 Long Ix, Rx, Ax; 1021 1022 PLong top; 1023 1024 1025 Dx = x2 - x1; 1026 Dy = y2 - y1; 1027 1028 if ( Dy <= 0 || y2 < miny || y1 > maxy ) 1029 return SUCCESS; 1030 1031 if ( y1 < miny ) 1032 { 1033 /* Take care: miny-y1 can be a very large value; we use */ 1034 /* a slow MulDiv function to avoid clipping bugs */ 1035 x1 += SMulDiv( Dx, miny - y1, Dy ); 1036 e1 = (Int)TRUNC( miny ); 1037 f1 = 0; 1038 } 1039 else 1040 { 1041 e1 = (Int)TRUNC( y1 ); 1042 f1 = (Int)FRAC( y1 ); 1043 } 1044 1045 if ( y2 > maxy ) 1046 { 1047 /* x2 += FMulDiv( Dx, maxy - y2, Dy ); UNNECESSARY */ 1048 e2 = (Int)TRUNC( maxy ); 1049 f2 = 0; 1050 } 1051 else 1052 { 1053 e2 = (Int)TRUNC( y2 ); 1054 f2 = (Int)FRAC( y2 ); 1055 } 1056 1057 if ( f1 > 0 ) 1058 { 1059 if ( e1 == e2 ) 1060 return SUCCESS; 1061 else 1062 { 1063 x1 += SMulDiv( Dx, ras.precision - f1, Dy ); 1064 e1 += 1; 1065 } 1066 } 1067 else 1068 if ( ras.joint ) 1069 { 1070 ras.top--; 1071 ras.joint = FALSE; 1072 } 1073 1074 ras.joint = (char)( f2 == 0 ); 1075 1076 if ( ras.fresh ) 1077 { 1078 ras.cProfile->start = e1; 1079 ras.fresh = FALSE; 1080 } 1081 1082 size = e2 - e1 + 1; 1083 if ( ras.top + size >= ras.maxBuff ) 1084 { 1085 ras.error = FT_THROW( Overflow ); 1086 return FAILURE; 1087 } 1088 1089 if ( Dx > 0 ) 1090 { 1091 Ix = SMulDiv_No_Round( ras.precision, Dx, Dy ); 1092 Rx = ( ras.precision * Dx ) % Dy; 1093 Dx = 1; 1094 } 1095 else 1096 { 1097 Ix = -SMulDiv_No_Round( ras.precision, -Dx, Dy ); 1098 Rx = ( ras.precision * -Dx ) % Dy; 1099 Dx = -1; 1100 } 1101 1102 Ax = -Dy; 1103 top = ras.top; 1104 1105 while ( size > 0 ) 1106 { 1107 *top++ = x1; 1108 1109 x1 += Ix; 1110 Ax += Rx; 1111 if ( Ax >= 0 ) 1112 { 1113 Ax -= Dy; 1114 x1 += Dx; 1115 } 1116 size--; 1117 } 1118 1119 ras.top = top; 1120 return SUCCESS; 1121 } 1122 1123 1124 /************************************************************************** 1125 * 1126 * @Function: 1127 * Line_Down 1128 * 1129 * @Description: 1130 * Compute the x-coordinates of an descending line segment and store 1131 * them in the render pool. 1132 * 1133 * @Input: 1134 * x1 :: 1135 * The x-coordinate of the segment's start point. 1136 * 1137 * y1 :: 1138 * The y-coordinate of the segment's start point. 1139 * 1140 * x2 :: 1141 * The x-coordinate of the segment's end point. 1142 * 1143 * y2 :: 1144 * The y-coordinate of the segment's end point. 1145 * 1146 * miny :: 1147 * A lower vertical clipping bound value. 1148 * 1149 * maxy :: 1150 * An upper vertical clipping bound value. 1151 * 1152 * @Return: 1153 * SUCCESS on success, FAILURE on render pool overflow. 1154 */ 1155 static Bool 1156 Line_Down( RAS_ARGS Long x1, 1157 Long y1, 1158 Long x2, 1159 Long y2, 1160 Long miny, 1161 Long maxy ) 1162 { 1163 Bool result, fresh; 1164 1165 1166 fresh = ras.fresh; 1167 1168 result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny ); 1169 1170 if ( fresh && !ras.fresh ) 1171 ras.cProfile->start = -ras.cProfile->start; 1172 1173 return result; 1174 } 1175 1176 1177 /* A function type describing the functions used to split Bezier arcs */ 1178 typedef void (*TSplitter)( TPoint* base ); 1179 1180 1181 /************************************************************************** 1182 * 1183 * @Function: 1184 * Bezier_Up 1185 * 1186 * @Description: 1187 * Compute the x-coordinates of an ascending Bezier arc and store 1188 * them in the render pool. 1189 * 1190 * @Input: 1191 * degree :: 1192 * The degree of the Bezier arc (either 2 or 3). 1193 * 1194 * splitter :: 1195 * The function to split Bezier arcs. 1196 * 1197 * miny :: 1198 * A lower vertical clipping bound value. 1199 * 1200 * maxy :: 1201 * An upper vertical clipping bound value. 1202 * 1203 * @Return: 1204 * SUCCESS on success, FAILURE on render pool overflow. 1205 */ 1206 static Bool 1207 Bezier_Up( RAS_ARGS Int degree, 1208 TSplitter splitter, 1209 Long miny, 1210 Long maxy ) 1211 { 1212 Long y1, y2, e, e2, e0; 1213 Short f1; 1214 1215 TPoint* arc; 1216 TPoint* start_arc; 1217 1218 PLong top; 1219 1220 1221 arc = ras.arc; 1222 y1 = arc[degree].y; 1223 y2 = arc[0].y; 1224 top = ras.top; 1225 1226 if ( y2 < miny || y1 > maxy ) 1227 goto Fin; 1228 1229 e2 = FLOOR( y2 ); 1230 1231 if ( e2 > maxy ) 1232 e2 = maxy; 1233 1234 e0 = miny; 1235 1236 if ( y1 < miny ) 1237 e = miny; 1238 else 1239 { 1240 e = CEILING( y1 ); 1241 f1 = (Short)( FRAC( y1 ) ); 1242 e0 = e; 1243 1244 if ( f1 == 0 ) 1245 { 1246 if ( ras.joint ) 1247 { 1248 top--; 1249 ras.joint = FALSE; 1250 } 1251 1252 *top++ = arc[degree].x; 1253 1254 e += ras.precision; 1255 } 1256 } 1257 1258 if ( ras.fresh ) 1259 { 1260 ras.cProfile->start = TRUNC( e0 ); 1261 ras.fresh = FALSE; 1262 } 1263 1264 if ( e2 < e ) 1265 goto Fin; 1266 1267 if ( ( top + TRUNC( e2 - e ) + 1 ) >= ras.maxBuff ) 1268 { 1269 ras.top = top; 1270 ras.error = FT_THROW( Overflow ); 1271 return FAILURE; 1272 } 1273 1274 start_arc = arc; 1275 1276 do 1277 { 1278 ras.joint = FALSE; 1279 1280 y2 = arc[0].y; 1281 1282 if ( y2 > e ) 1283 { 1284 y1 = arc[degree].y; 1285 if ( y2 - y1 >= ras.precision_step ) 1286 { 1287 splitter( arc ); 1288 arc += degree; 1289 } 1290 else 1291 { 1292 *top++ = arc[degree].x + FMulDiv( arc[0].x - arc[degree].x, 1293 e - y1, y2 - y1 ); 1294 arc -= degree; 1295 e += ras.precision; 1296 } 1297 } 1298 else 1299 { 1300 if ( y2 == e ) 1301 { 1302 ras.joint = TRUE; 1303 *top++ = arc[0].x; 1304 1305 e += ras.precision; 1306 } 1307 arc -= degree; 1308 } 1309 } while ( arc >= start_arc && e <= e2 ); 1310 1311 Fin: 1312 ras.top = top; 1313 ras.arc -= degree; 1314 return SUCCESS; 1315 } 1316 1317 1318 /************************************************************************** 1319 * 1320 * @Function: 1321 * Bezier_Down 1322 * 1323 * @Description: 1324 * Compute the x-coordinates of an descending Bezier arc and store 1325 * them in the render pool. 1326 * 1327 * @Input: 1328 * degree :: 1329 * The degree of the Bezier arc (either 2 or 3). 1330 * 1331 * splitter :: 1332 * The function to split Bezier arcs. 1333 * 1334 * miny :: 1335 * A lower vertical clipping bound value. 1336 * 1337 * maxy :: 1338 * An upper vertical clipping bound value. 1339 * 1340 * @Return: 1341 * SUCCESS on success, FAILURE on render pool overflow. 1342 */ 1343 static Bool 1344 Bezier_Down( RAS_ARGS Int degree, 1345 TSplitter splitter, 1346 Long miny, 1347 Long maxy ) 1348 { 1349 TPoint* arc = ras.arc; 1350 Bool result, fresh; 1351 1352 1353 arc[0].y = -arc[0].y; 1354 arc[1].y = -arc[1].y; 1355 arc[2].y = -arc[2].y; 1356 if ( degree > 2 ) 1357 arc[3].y = -arc[3].y; 1358 1359 fresh = ras.fresh; 1360 1361 result = Bezier_Up( RAS_VARS degree, splitter, -maxy, -miny ); 1362 1363 if ( fresh && !ras.fresh ) 1364 ras.cProfile->start = -ras.cProfile->start; 1365 1366 arc[0].y = -arc[0].y; 1367 return result; 1368 } 1369 1370 1371 /************************************************************************** 1372 * 1373 * @Function: 1374 * Line_To 1375 * 1376 * @Description: 1377 * Inject a new line segment and adjust the Profiles list. 1378 * 1379 * @Input: 1380 * x :: 1381 * The x-coordinate of the segment's end point (its start point 1382 * is stored in `lastX'). 1383 * 1384 * y :: 1385 * The y-coordinate of the segment's end point (its start point 1386 * is stored in `lastY'). 1387 * 1388 * @Return: 1389 * SUCCESS on success, FAILURE on render pool overflow or incorrect 1390 * profile. 1391 */ 1392 static Bool 1393 Line_To( RAS_ARGS Long x, 1394 Long y ) 1395 { 1396 /* First, detect a change of direction */ 1397 1398 switch ( ras.state ) 1399 { 1400 case Unknown_State: 1401 if ( y > ras.lastY ) 1402 { 1403 if ( New_Profile( RAS_VARS Ascending_State, 1404 IS_BOTTOM_OVERSHOOT( ras.lastY ) ) ) 1405 return FAILURE; 1406 } 1407 else 1408 { 1409 if ( y < ras.lastY ) 1410 if ( New_Profile( RAS_VARS Descending_State, 1411 IS_TOP_OVERSHOOT( ras.lastY ) ) ) 1412 return FAILURE; 1413 } 1414 break; 1415 1416 case Ascending_State: 1417 if ( y < ras.lastY ) 1418 { 1419 if ( End_Profile( RAS_VARS IS_TOP_OVERSHOOT( ras.lastY ) ) || 1420 New_Profile( RAS_VARS Descending_State, 1421 IS_TOP_OVERSHOOT( ras.lastY ) ) ) 1422 return FAILURE; 1423 } 1424 break; 1425 1426 case Descending_State: 1427 if ( y > ras.lastY ) 1428 { 1429 if ( End_Profile( RAS_VARS IS_BOTTOM_OVERSHOOT( ras.lastY ) ) || 1430 New_Profile( RAS_VARS Ascending_State, 1431 IS_BOTTOM_OVERSHOOT( ras.lastY ) ) ) 1432 return FAILURE; 1433 } 1434 break; 1435 1436 default: 1437 ; 1438 } 1439 1440 /* Then compute the lines */ 1441 1442 switch ( ras.state ) 1443 { 1444 case Ascending_State: 1445 if ( Line_Up( RAS_VARS ras.lastX, ras.lastY, 1446 x, y, ras.minY, ras.maxY ) ) 1447 return FAILURE; 1448 break; 1449 1450 case Descending_State: 1451 if ( Line_Down( RAS_VARS ras.lastX, ras.lastY, 1452 x, y, ras.minY, ras.maxY ) ) 1453 return FAILURE; 1454 break; 1455 1456 default: 1457 ; 1458 } 1459 1460 ras.lastX = x; 1461 ras.lastY = y; 1462 1463 return SUCCESS; 1464 } 1465 1466 1467 /************************************************************************** 1468 * 1469 * @Function: 1470 * Conic_To 1471 * 1472 * @Description: 1473 * Inject a new conic arc and adjust the profile list. 1474 * 1475 * @Input: 1476 * cx :: 1477 * The x-coordinate of the arc's new control point. 1478 * 1479 * cy :: 1480 * The y-coordinate of the arc's new control point. 1481 * 1482 * x :: 1483 * The x-coordinate of the arc's end point (its start point is 1484 * stored in `lastX'). 1485 * 1486 * y :: 1487 * The y-coordinate of the arc's end point (its start point is 1488 * stored in `lastY'). 1489 * 1490 * @Return: 1491 * SUCCESS on success, FAILURE on render pool overflow or incorrect 1492 * profile. 1493 */ 1494 static Bool 1495 Conic_To( RAS_ARGS Long cx, 1496 Long cy, 1497 Long x, 1498 Long y ) 1499 { 1500 Long y1, y2, y3, x3, ymin, ymax; 1501 TStates state_bez; 1502 1503 1504 ras.arc = ras.arcs; 1505 ras.arc[2].x = ras.lastX; 1506 ras.arc[2].y = ras.lastY; 1507 ras.arc[1].x = cx; 1508 ras.arc[1].y = cy; 1509 ras.arc[0].x = x; 1510 ras.arc[0].y = y; 1511 1512 do 1513 { 1514 y1 = ras.arc[2].y; 1515 y2 = ras.arc[1].y; 1516 y3 = ras.arc[0].y; 1517 x3 = ras.arc[0].x; 1518 1519 /* first, categorize the Bezier arc */ 1520 1521 if ( y1 <= y3 ) 1522 { 1523 ymin = y1; 1524 ymax = y3; 1525 } 1526 else 1527 { 1528 ymin = y3; 1529 ymax = y1; 1530 } 1531 1532 if ( y2 < ymin || y2 > ymax ) 1533 { 1534 /* this arc has no given direction, split it! */ 1535 Split_Conic( ras.arc ); 1536 ras.arc += 2; 1537 } 1538 else if ( y1 == y3 ) 1539 { 1540 /* this arc is flat, ignore it and pop it from the Bezier stack */ 1541 ras.arc -= 2; 1542 } 1543 else 1544 { 1545 /* the arc is y-monotonous, either ascending or descending */ 1546 /* detect a change of direction */ 1547 state_bez = y1 < y3 ? Ascending_State : Descending_State; 1548 if ( ras.state != state_bez ) 1549 { 1550 Bool o = ( state_bez == Ascending_State ) 1551 ? IS_BOTTOM_OVERSHOOT( y1 ) 1552 : IS_TOP_OVERSHOOT( y1 ); 1553 1554 1555 /* finalize current profile if any */ 1556 if ( ras.state != Unknown_State && 1557 End_Profile( RAS_VARS o ) ) 1558 goto Fail; 1559 1560 /* create a new profile */ 1561 if ( New_Profile( RAS_VARS state_bez, o ) ) 1562 goto Fail; 1563 } 1564 1565 /* now call the appropriate routine */ 1566 if ( state_bez == Ascending_State ) 1567 { 1568 if ( Bezier_Up( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) ) 1569 goto Fail; 1570 } 1571 else 1572 if ( Bezier_Down( RAS_VARS 2, Split_Conic, ras.minY, ras.maxY ) ) 1573 goto Fail; 1574 } 1575 1576 } while ( ras.arc >= ras.arcs ); 1577 1578 ras.lastX = x3; 1579 ras.lastY = y3; 1580 1581 return SUCCESS; 1582 1583 Fail: 1584 return FAILURE; 1585 } 1586 1587 1588 /************************************************************************** 1589 * 1590 * @Function: 1591 * Cubic_To 1592 * 1593 * @Description: 1594 * Inject a new cubic arc and adjust the profile list. 1595 * 1596 * @Input: 1597 * cx1 :: 1598 * The x-coordinate of the arc's first new control point. 1599 * 1600 * cy1 :: 1601 * The y-coordinate of the arc's first new control point. 1602 * 1603 * cx2 :: 1604 * The x-coordinate of the arc's second new control point. 1605 * 1606 * cy2 :: 1607 * The y-coordinate of the arc's second new control point. 1608 * 1609 * x :: 1610 * The x-coordinate of the arc's end point (its start point is 1611 * stored in `lastX'). 1612 * 1613 * y :: 1614 * The y-coordinate of the arc's end point (its start point is 1615 * stored in `lastY'). 1616 * 1617 * @Return: 1618 * SUCCESS on success, FAILURE on render pool overflow or incorrect 1619 * profile. 1620 */ 1621 static Bool 1622 Cubic_To( RAS_ARGS Long cx1, 1623 Long cy1, 1624 Long cx2, 1625 Long cy2, 1626 Long x, 1627 Long y ) 1628 { 1629 Long y1, y2, y3, y4, x4, ymin1, ymax1, ymin2, ymax2; 1630 TStates state_bez; 1631 1632 1633 ras.arc = ras.arcs; 1634 ras.arc[3].x = ras.lastX; 1635 ras.arc[3].y = ras.lastY; 1636 ras.arc[2].x = cx1; 1637 ras.arc[2].y = cy1; 1638 ras.arc[1].x = cx2; 1639 ras.arc[1].y = cy2; 1640 ras.arc[0].x = x; 1641 ras.arc[0].y = y; 1642 1643 do 1644 { 1645 y1 = ras.arc[3].y; 1646 y2 = ras.arc[2].y; 1647 y3 = ras.arc[1].y; 1648 y4 = ras.arc[0].y; 1649 x4 = ras.arc[0].x; 1650 1651 /* first, categorize the Bezier arc */ 1652 1653 if ( y1 <= y4 ) 1654 { 1655 ymin1 = y1; 1656 ymax1 = y4; 1657 } 1658 else 1659 { 1660 ymin1 = y4; 1661 ymax1 = y1; 1662 } 1663 1664 if ( y2 <= y3 ) 1665 { 1666 ymin2 = y2; 1667 ymax2 = y3; 1668 } 1669 else 1670 { 1671 ymin2 = y3; 1672 ymax2 = y2; 1673 } 1674 1675 if ( ymin2 < ymin1 || ymax2 > ymax1 ) 1676 { 1677 /* this arc has no given direction, split it! */ 1678 Split_Cubic( ras.arc ); 1679 ras.arc += 3; 1680 } 1681 else if ( y1 == y4 ) 1682 { 1683 /* this arc is flat, ignore it and pop it from the Bezier stack */ 1684 ras.arc -= 3; 1685 } 1686 else 1687 { 1688 state_bez = ( y1 <= y4 ) ? Ascending_State : Descending_State; 1689 1690 /* detect a change of direction */ 1691 if ( ras.state != state_bez ) 1692 { 1693 Bool o = ( state_bez == Ascending_State ) 1694 ? IS_BOTTOM_OVERSHOOT( y1 ) 1695 : IS_TOP_OVERSHOOT( y1 ); 1696 1697 1698 /* finalize current profile if any */ 1699 if ( ras.state != Unknown_State && 1700 End_Profile( RAS_VARS o ) ) 1701 goto Fail; 1702 1703 if ( New_Profile( RAS_VARS state_bez, o ) ) 1704 goto Fail; 1705 } 1706 1707 /* compute intersections */ 1708 if ( state_bez == Ascending_State ) 1709 { 1710 if ( Bezier_Up( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) ) 1711 goto Fail; 1712 } 1713 else 1714 if ( Bezier_Down( RAS_VARS 3, Split_Cubic, ras.minY, ras.maxY ) ) 1715 goto Fail; 1716 } 1717 1718 } while ( ras.arc >= ras.arcs ); 1719 1720 ras.lastX = x4; 1721 ras.lastY = y4; 1722 1723 return SUCCESS; 1724 1725 Fail: 1726 return FAILURE; 1727 } 1728 1729 1730 #undef SWAP_ 1731 #define SWAP_( x, y ) do \ 1732 { \ 1733 Long swap = x; \ 1734 \ 1735 \ 1736 x = y; \ 1737 y = swap; \ 1738 } while ( 0 ) 1739 1740 1741 /************************************************************************** 1742 * 1743 * @Function: 1744 * Decompose_Curve 1745 * 1746 * @Description: 1747 * Scan the outline arrays in order to emit individual segments and 1748 * Beziers by calling Line_To() and Bezier_To(). It handles all 1749 * weird cases, like when the first point is off the curve, or when 1750 * there are simply no `on' points in the contour! 1751 * 1752 * @Input: 1753 * first :: 1754 * The index of the first point in the contour. 1755 * 1756 * last :: 1757 * The index of the last point in the contour. 1758 * 1759 * flipped :: 1760 * If set, flip the direction of the curve. 1761 * 1762 * @Return: 1763 * SUCCESS on success, FAILURE on error. 1764 */ 1765 static Bool 1766 Decompose_Curve( RAS_ARGS UShort first, 1767 UShort last, 1768 Int flipped ) 1769 { 1770 FT_Vector v_last; 1771 FT_Vector v_control; 1772 FT_Vector v_start; 1773 1774 FT_Vector* points; 1775 FT_Vector* point; 1776 FT_Vector* limit; 1777 char* tags; 1778 1779 UInt tag; /* current point's state */ 1780 1781 1782 points = ras.outline.points; 1783 limit = points + last; 1784 1785 v_start.x = SCALED( points[first].x ); 1786 v_start.y = SCALED( points[first].y ); 1787 v_last.x = SCALED( points[last].x ); 1788 v_last.y = SCALED( points[last].y ); 1789 1790 if ( flipped ) 1791 { 1792 SWAP_( v_start.x, v_start.y ); 1793 SWAP_( v_last.x, v_last.y ); 1794 } 1795 1796 v_control = v_start; 1797 1798 point = points + first; 1799 tags = ras.outline.tags + first; 1800 1801 /* set scan mode if necessary */ 1802 if ( tags[0] & FT_CURVE_TAG_HAS_SCANMODE ) 1803 ras.dropOutControl = (Byte)tags[0] >> 5; 1804 1805 tag = FT_CURVE_TAG( tags[0] ); 1806 1807 /* A contour cannot start with a cubic control point! */ 1808 if ( tag == FT_CURVE_TAG_CUBIC ) 1809 goto Invalid_Outline; 1810 1811 /* check first point to determine origin */ 1812 if ( tag == FT_CURVE_TAG_CONIC ) 1813 { 1814 /* first point is conic control. Yes, this happens. */ 1815 if ( FT_CURVE_TAG( ras.outline.tags[last] ) == FT_CURVE_TAG_ON ) 1816 { 1817 /* start at last point if it is on the curve */ 1818 v_start = v_last; 1819 limit--; 1820 } 1821 else 1822 { 1823 /* if both first and last points are conic, */ 1824 /* start at their middle and record its position */ 1825 /* for closure */ 1826 v_start.x = ( v_start.x + v_last.x ) / 2; 1827 v_start.y = ( v_start.y + v_last.y ) / 2; 1828 1829 /* v_last = v_start; */ 1830 } 1831 point--; 1832 tags--; 1833 } 1834 1835 ras.lastX = v_start.x; 1836 ras.lastY = v_start.y; 1837 1838 while ( point < limit ) 1839 { 1840 point++; 1841 tags++; 1842 1843 tag = FT_CURVE_TAG( tags[0] ); 1844 1845 switch ( tag ) 1846 { 1847 case FT_CURVE_TAG_ON: /* emit a single line_to */ 1848 { 1849 Long x, y; 1850 1851 1852 x = SCALED( point->x ); 1853 y = SCALED( point->y ); 1854 if ( flipped ) 1855 SWAP_( x, y ); 1856 1857 if ( Line_To( RAS_VARS x, y ) ) 1858 goto Fail; 1859 continue; 1860 } 1861 1862 case FT_CURVE_TAG_CONIC: /* consume conic arcs */ 1863 v_control.x = SCALED( point[0].x ); 1864 v_control.y = SCALED( point[0].y ); 1865 1866 if ( flipped ) 1867 SWAP_( v_control.x, v_control.y ); 1868 1869 Do_Conic: 1870 if ( point < limit ) 1871 { 1872 FT_Vector v_middle; 1873 Long x, y; 1874 1875 1876 point++; 1877 tags++; 1878 tag = FT_CURVE_TAG( tags[0] ); 1879 1880 x = SCALED( point[0].x ); 1881 y = SCALED( point[0].y ); 1882 1883 if ( flipped ) 1884 SWAP_( x, y ); 1885 1886 if ( tag == FT_CURVE_TAG_ON ) 1887 { 1888 if ( Conic_To( RAS_VARS v_control.x, v_control.y, x, y ) ) 1889 goto Fail; 1890 continue; 1891 } 1892 1893 if ( tag != FT_CURVE_TAG_CONIC ) 1894 goto Invalid_Outline; 1895 1896 v_middle.x = ( v_control.x + x ) / 2; 1897 v_middle.y = ( v_control.y + y ) / 2; 1898 1899 if ( Conic_To( RAS_VARS v_control.x, v_control.y, 1900 v_middle.x, v_middle.y ) ) 1901 goto Fail; 1902 1903 v_control.x = x; 1904 v_control.y = y; 1905 1906 goto Do_Conic; 1907 } 1908 1909 if ( Conic_To( RAS_VARS v_control.x, v_control.y, 1910 v_start.x, v_start.y ) ) 1911 goto Fail; 1912 1913 goto Close; 1914 1915 default: /* FT_CURVE_TAG_CUBIC */ 1916 { 1917 Long x1, y1, x2, y2, x3, y3; 1918 1919 1920 if ( point + 1 > limit || 1921 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC ) 1922 goto Invalid_Outline; 1923 1924 point += 2; 1925 tags += 2; 1926 1927 x1 = SCALED( point[-2].x ); 1928 y1 = SCALED( point[-2].y ); 1929 x2 = SCALED( point[-1].x ); 1930 y2 = SCALED( point[-1].y ); 1931 1932 if ( flipped ) 1933 { 1934 SWAP_( x1, y1 ); 1935 SWAP_( x2, y2 ); 1936 } 1937 1938 if ( point <= limit ) 1939 { 1940 x3 = SCALED( point[0].x ); 1941 y3 = SCALED( point[0].y ); 1942 1943 if ( flipped ) 1944 SWAP_( x3, y3 ); 1945 1946 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, x3, y3 ) ) 1947 goto Fail; 1948 continue; 1949 } 1950 1951 if ( Cubic_To( RAS_VARS x1, y1, x2, y2, v_start.x, v_start.y ) ) 1952 goto Fail; 1953 goto Close; 1954 } 1955 } 1956 } 1957 1958 /* close the contour with a line segment */ 1959 if ( Line_To( RAS_VARS v_start.x, v_start.y ) ) 1960 goto Fail; 1961 1962 Close: 1963 return SUCCESS; 1964 1965 Invalid_Outline: 1966 ras.error = FT_THROW( Invalid ); 1967 1968 Fail: 1969 return FAILURE; 1970 } 1971 1972 1973 /************************************************************************** 1974 * 1975 * @Function: 1976 * Convert_Glyph 1977 * 1978 * @Description: 1979 * Convert a glyph into a series of segments and arcs and make a 1980 * profiles list with them. 1981 * 1982 * @Input: 1983 * flipped :: 1984 * If set, flip the direction of curve. 1985 * 1986 * @Return: 1987 * SUCCESS on success, FAILURE if any error was encountered during 1988 * rendering. 1989 */ 1990 static Bool 1991 Convert_Glyph( RAS_ARGS Int flipped ) 1992 { 1993 Int i; 1994 UInt start; 1995 1996 1997 ras.fProfile = NULL; 1998 ras.joint = FALSE; 1999 ras.fresh = FALSE; 2000 2001 ras.maxBuff = ras.sizeBuff - AlignProfileSize; 2002 2003 ras.numTurns = 0; 2004 2005 ras.cProfile = (PProfile)ras.top; 2006 ras.cProfile->offset = ras.top; 2007 ras.num_Profs = 0; 2008 2009 start = 0; 2010 2011 for ( i = 0; i < ras.outline.n_contours; i++ ) 2012 { 2013 PProfile lastProfile; 2014 Bool o; 2015 2016 2017 ras.state = Unknown_State; 2018 ras.gProfile = NULL; 2019 2020 if ( Decompose_Curve( RAS_VARS (UShort)start, 2021 (UShort)ras.outline.contours[i], 2022 flipped ) ) 2023 return FAILURE; 2024 2025 start = (UShort)ras.outline.contours[i] + 1; 2026 2027 /* we must now check whether the extreme arcs join or not */ 2028 if ( FRAC( ras.lastY ) == 0 && 2029 ras.lastY >= ras.minY && 2030 ras.lastY <= ras.maxY ) 2031 if ( ras.gProfile && 2032 ( ras.gProfile->flags & Flow_Up ) == 2033 ( ras.cProfile->flags & Flow_Up ) ) 2034 ras.top--; 2035 /* Note that ras.gProfile can be nil if the contour was too small */ 2036 /* to be drawn. */ 2037 2038 lastProfile = ras.cProfile; 2039 if ( ras.top != ras.cProfile->offset && 2040 ( ras.cProfile->flags & Flow_Up ) ) 2041 o = IS_TOP_OVERSHOOT( ras.lastY ); 2042 else 2043 o = IS_BOTTOM_OVERSHOOT( ras.lastY ); 2044 if ( End_Profile( RAS_VARS o ) ) 2045 return FAILURE; 2046 2047 /* close the `next profile in contour' linked list */ 2048 if ( ras.gProfile ) 2049 lastProfile->next = ras.gProfile; 2050 } 2051 2052 if ( Finalize_Profile_Table( RAS_VAR ) ) 2053 return FAILURE; 2054 2055 return (Bool)( ras.top < ras.maxBuff ? SUCCESS : FAILURE ); 2056 } 2057 2058 2059 /*************************************************************************/ 2060 /*************************************************************************/ 2061 /** **/ 2062 /** SCAN-LINE SWEEPS AND DRAWING **/ 2063 /** **/ 2064 /*************************************************************************/ 2065 /*************************************************************************/ 2066 2067 2068 /************************************************************************** 2069 * 2070 * Init_Linked 2071 * 2072 * Initializes an empty linked list. 2073 */ 2074 static void 2075 Init_Linked( TProfileList* l ) 2076 { 2077 *l = NULL; 2078 } 2079 2080 2081 /************************************************************************** 2082 * 2083 * InsNew 2084 * 2085 * Inserts a new profile in a linked list. 2086 */ 2087 static void 2088 InsNew( PProfileList list, 2089 PProfile profile ) 2090 { 2091 PProfile *old, current; 2092 Long x; 2093 2094 2095 old = list; 2096 current = *old; 2097 x = profile->X; 2098 2099 while ( current ) 2100 { 2101 if ( x < current->X ) 2102 break; 2103 old = ¤t->link; 2104 current = *old; 2105 } 2106 2107 profile->link = current; 2108 *old = profile; 2109 } 2110 2111 2112 /************************************************************************** 2113 * 2114 * DelOld 2115 * 2116 * Removes an old profile from a linked list. 2117 */ 2118 static void 2119 DelOld( PProfileList list, 2120 PProfile profile ) 2121 { 2122 PProfile *old, current; 2123 2124 2125 old = list; 2126 current = *old; 2127 2128 while ( current ) 2129 { 2130 if ( current == profile ) 2131 { 2132 *old = current->link; 2133 return; 2134 } 2135 2136 old = ¤t->link; 2137 current = *old; 2138 } 2139 2140 /* we should never get there, unless the profile was not part of */ 2141 /* the list. */ 2142 } 2143 2144 2145 /************************************************************************** 2146 * 2147 * Sort 2148 * 2149 * Sorts a trace list. In 95%, the list is already sorted. We need 2150 * an algorithm which is fast in this case. Bubble sort is enough 2151 * and simple. 2152 */ 2153 static void 2154 Sort( PProfileList list ) 2155 { 2156 PProfile *old, current, next; 2157 2158 2159 /* First, set the new X coordinate of each profile */ 2160 current = *list; 2161 while ( current ) 2162 { 2163 current->X = *current->offset; 2164 current->offset += ( current->flags & Flow_Up ) ? 1 : -1; 2165 current->height--; 2166 current = current->link; 2167 } 2168 2169 /* Then sort them */ 2170 old = list; 2171 current = *old; 2172 2173 if ( !current ) 2174 return; 2175 2176 next = current->link; 2177 2178 while ( next ) 2179 { 2180 if ( current->X <= next->X ) 2181 { 2182 old = ¤t->link; 2183 current = *old; 2184 2185 if ( !current ) 2186 return; 2187 } 2188 else 2189 { 2190 *old = next; 2191 current->link = next->link; 2192 next->link = current; 2193 2194 old = list; 2195 current = *old; 2196 } 2197 2198 next = current->link; 2199 } 2200 } 2201 2202 2203 /************************************************************************** 2204 * 2205 * Vertical Sweep Procedure Set 2206 * 2207 * These four routines are used during the vertical black/white sweep 2208 * phase by the generic Draw_Sweep() function. 2209 * 2210 */ 2211 2212 static void 2213 Vertical_Sweep_Init( RAS_ARGS Short* min, 2214 Short* max ) 2215 { 2216 Long pitch = ras.target.pitch; 2217 2218 FT_UNUSED( max ); 2219 2220 2221 ras.traceIncr = (Short)-pitch; 2222 ras.traceOfs = -*min * pitch; 2223 } 2224 2225 2226 static void 2227 Vertical_Sweep_Span( RAS_ARGS Short y, 2228 FT_F26Dot6 x1, 2229 FT_F26Dot6 x2, 2230 PProfile left, 2231 PProfile right ) 2232 { 2233 Long e1, e2; 2234 Byte* target; 2235 2236 Int dropOutControl = left->flags & 7; 2237 2238 FT_UNUSED( y ); 2239 FT_UNUSED( left ); 2240 FT_UNUSED( right ); 2241 2242 2243 /* in high-precision mode, we need 12 digits after the comma to */ 2244 /* represent multiples of 1/(1<<12) = 1/4096 */ 2245 FT_TRACE7(( " y=%d x=[%.12f;%.12f], drop-out=%d", 2246 y, 2247 x1 / (double)ras.precision, 2248 x2 / (double)ras.precision, 2249 dropOutControl )); 2250 2251 /* Drop-out control */ 2252 2253 e1 = CEILING( x1 ); 2254 e2 = FLOOR( x2 ); 2255 2256 /* take care of the special case where both the left */ 2257 /* and right contour lie exactly on pixel centers */ 2258 if ( dropOutControl != 2 && 2259 x2 - x1 - ras.precision <= ras.precision_jitter && 2260 e1 != x1 && e2 != x2 ) 2261 e2 = e1; 2262 2263 e1 = TRUNC( e1 ); 2264 e2 = TRUNC( e2 ); 2265 2266 if ( e2 >= 0 && e1 < ras.bWidth ) 2267 { 2268 Int c1, c2; 2269 Byte f1, f2; 2270 2271 2272 if ( e1 < 0 ) 2273 e1 = 0; 2274 if ( e2 >= ras.bWidth ) 2275 e2 = ras.bWidth - 1; 2276 2277 FT_TRACE7(( " -> x=[%d;%d]", e1, e2 )); 2278 2279 c1 = (Short)( e1 >> 3 ); 2280 c2 = (Short)( e2 >> 3 ); 2281 2282 f1 = (Byte) ( 0xFF >> ( e1 & 7 ) ); 2283 f2 = (Byte) ~( 0x7F >> ( e2 & 7 ) ); 2284 2285 target = ras.bOrigin + ras.traceOfs + c1; 2286 c2 -= c1; 2287 2288 if ( c2 > 0 ) 2289 { 2290 target[0] |= f1; 2291 2292 /* memset() is slower than the following code on many platforms. */ 2293 /* This is due to the fact that, in the vast majority of cases, */ 2294 /* the span length in bytes is relatively small. */ 2295 while ( --c2 > 0 ) 2296 *(++target) = 0xFF; 2297 2298 target[1] |= f2; 2299 } 2300 else 2301 *target |= ( f1 & f2 ); 2302 } 2303 2304 FT_TRACE7(( "\n" )); 2305 } 2306 2307 2308 static void 2309 Vertical_Sweep_Drop( RAS_ARGS Short y, 2310 FT_F26Dot6 x1, 2311 FT_F26Dot6 x2, 2312 PProfile left, 2313 PProfile right ) 2314 { 2315 Long e1, e2, pxl; 2316 Short c1, f1; 2317 2318 2319 FT_TRACE7(( " y=%d x=[%.12f;%.12f]", 2320 y, 2321 x1 / (double)ras.precision, 2322 x2 / (double)ras.precision )); 2323 2324 /* Drop-out control */ 2325 2326 /* e2 x2 x1 e1 */ 2327 /* */ 2328 /* ^ | */ 2329 /* | | */ 2330 /* +-------------+---------------------+------------+ */ 2331 /* | | */ 2332 /* | v */ 2333 /* */ 2334 /* pixel contour contour pixel */ 2335 /* center center */ 2336 2337 /* drop-out mode scan conversion rules (as defined in OpenType) */ 2338 /* --------------------------------------------------------------- */ 2339 /* 0 1, 2, 3 */ 2340 /* 1 1, 2, 4 */ 2341 /* 2 1, 2 */ 2342 /* 3 same as mode 2 */ 2343 /* 4 1, 2, 5 */ 2344 /* 5 1, 2, 6 */ 2345 /* 6, 7 same as mode 2 */ 2346 2347 e1 = CEILING( x1 ); 2348 e2 = FLOOR ( x2 ); 2349 pxl = e1; 2350 2351 if ( e1 > e2 ) 2352 { 2353 Int dropOutControl = left->flags & 7; 2354 2355 2356 FT_TRACE7(( ", drop-out=%d", dropOutControl )); 2357 2358 if ( e1 == e2 + ras.precision ) 2359 { 2360 switch ( dropOutControl ) 2361 { 2362 case 0: /* simple drop-outs including stubs */ 2363 pxl = e2; 2364 break; 2365 2366 case 4: /* smart drop-outs including stubs */ 2367 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half ); 2368 break; 2369 2370 case 1: /* simple drop-outs excluding stubs */ 2371 case 5: /* smart drop-outs excluding stubs */ 2372 2373 /* Drop-out Control Rules #4 and #6 */ 2374 2375 /* The specification neither provides an exact definition */ 2376 /* of a `stub' nor gives exact rules to exclude them. */ 2377 /* */ 2378 /* Here the constraints we use to recognize a stub. */ 2379 /* */ 2380 /* upper stub: */ 2381 /* */ 2382 /* - P_Left and P_Right are in the same contour */ 2383 /* - P_Right is the successor of P_Left in that contour */ 2384 /* - y is the top of P_Left and P_Right */ 2385 /* */ 2386 /* lower stub: */ 2387 /* */ 2388 /* - P_Left and P_Right are in the same contour */ 2389 /* - P_Left is the successor of P_Right in that contour */ 2390 /* - y is the bottom of P_Left */ 2391 /* */ 2392 /* We draw a stub if the following constraints are met. */ 2393 /* */ 2394 /* - for an upper or lower stub, there is top or bottom */ 2395 /* overshoot, respectively */ 2396 /* - the covered interval is greater or equal to a half */ 2397 /* pixel */ 2398 2399 /* upper stub test */ 2400 if ( left->next == right && 2401 left->height <= 0 && 2402 !( left->flags & Overshoot_Top && 2403 x2 - x1 >= ras.precision_half ) ) 2404 goto Exit; 2405 2406 /* lower stub test */ 2407 if ( right->next == left && 2408 left->start == y && 2409 !( left->flags & Overshoot_Bottom && 2410 x2 - x1 >= ras.precision_half ) ) 2411 goto Exit; 2412 2413 if ( dropOutControl == 1 ) 2414 pxl = e2; 2415 else 2416 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half ); 2417 break; 2418 2419 default: /* modes 2, 3, 6, 7 */ 2420 goto Exit; /* no drop-out control */ 2421 } 2422 2423 /* undocumented but confirmed: If the drop-out would result in a */ 2424 /* pixel outside of the bounding box, use the pixel inside of the */ 2425 /* bounding box instead */ 2426 if ( pxl < 0 ) 2427 pxl = e1; 2428 else if ( TRUNC( pxl ) >= ras.bWidth ) 2429 pxl = e2; 2430 2431 /* check that the other pixel isn't set */ 2432 e1 = ( pxl == e1 ) ? e2 : e1; 2433 2434 e1 = TRUNC( e1 ); 2435 2436 c1 = (Short)( e1 >> 3 ); 2437 f1 = (Short)( e1 & 7 ); 2438 2439 if ( e1 >= 0 && e1 < ras.bWidth && 2440 ras.bOrigin[ras.traceOfs + c1] & ( 0x80 >> f1 ) ) 2441 goto Exit; 2442 } 2443 else 2444 goto Exit; 2445 } 2446 2447 e1 = TRUNC( pxl ); 2448 2449 if ( e1 >= 0 && e1 < ras.bWidth ) 2450 { 2451 FT_TRACE7(( " -> x=%d (drop-out)", e1 )); 2452 2453 c1 = (Short)( e1 >> 3 ); 2454 f1 = (Short)( e1 & 7 ); 2455 2456 ras.bOrigin[ras.traceOfs + c1] |= (char)( 0x80 >> f1 ); 2457 } 2458 2459 Exit: 2460 FT_TRACE7(( "\n" )); 2461 } 2462 2463 2464 static void 2465 Vertical_Sweep_Step( RAS_ARG ) 2466 { 2467 ras.traceOfs += ras.traceIncr; 2468 } 2469 2470 2471 /************************************************************************ 2472 * 2473 * Horizontal Sweep Procedure Set 2474 * 2475 * These four routines are used during the horizontal black/white 2476 * sweep phase by the generic Draw_Sweep() function. 2477 * 2478 */ 2479 2480 static void 2481 Horizontal_Sweep_Init( RAS_ARGS Short* min, 2482 Short* max ) 2483 { 2484 /* nothing, really */ 2485 FT_UNUSED_RASTER; 2486 FT_UNUSED( min ); 2487 FT_UNUSED( max ); 2488 } 2489 2490 2491 static void 2492 Horizontal_Sweep_Span( RAS_ARGS Short y, 2493 FT_F26Dot6 x1, 2494 FT_F26Dot6 x2, 2495 PProfile left, 2496 PProfile right ) 2497 { 2498 FT_UNUSED( left ); 2499 FT_UNUSED( right ); 2500 2501 2502 if ( x2 - x1 < ras.precision ) 2503 { 2504 Long e1, e2; 2505 2506 2507 FT_TRACE7(( " x=%d y=[%.12f;%.12f]", 2508 y, 2509 x1 / (double)ras.precision, 2510 x2 / (double)ras.precision )); 2511 2512 e1 = CEILING( x1 ); 2513 e2 = FLOOR ( x2 ); 2514 2515 if ( e1 == e2 ) 2516 { 2517 e1 = TRUNC( e1 ); 2518 2519 if ( e1 >= 0 && (ULong)e1 < ras.target.rows ) 2520 { 2521 Byte f1; 2522 PByte bits; 2523 2524 2525 FT_TRACE7(( " -> y=%d (drop-out)", e1 )); 2526 2527 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch; 2528 f1 = (Byte)( 0x80 >> ( y & 7 ) ); 2529 2530 bits[0] |= f1; 2531 } 2532 } 2533 2534 FT_TRACE7(( "\n" )); 2535 } 2536 } 2537 2538 2539 static void 2540 Horizontal_Sweep_Drop( RAS_ARGS Short y, 2541 FT_F26Dot6 x1, 2542 FT_F26Dot6 x2, 2543 PProfile left, 2544 PProfile right ) 2545 { 2546 Long e1, e2, pxl; 2547 PByte bits; 2548 Byte f1; 2549 2550 2551 FT_TRACE7(( " x=%d y=[%.12f;%.12f]", 2552 y, 2553 x1 / (double)ras.precision, 2554 x2 / (double)ras.precision )); 2555 2556 /* During the horizontal sweep, we only take care of drop-outs */ 2557 2558 /* e1 + <-- pixel center */ 2559 /* | */ 2560 /* x1 ---+--> <-- contour */ 2561 /* | */ 2562 /* | */ 2563 /* x2 <--+--- <-- contour */ 2564 /* | */ 2565 /* | */ 2566 /* e2 + <-- pixel center */ 2567 2568 e1 = CEILING( x1 ); 2569 e2 = FLOOR ( x2 ); 2570 pxl = e1; 2571 2572 if ( e1 > e2 ) 2573 { 2574 Int dropOutControl = left->flags & 7; 2575 2576 2577 FT_TRACE7(( ", dropout=%d", dropOutControl )); 2578 2579 if ( e1 == e2 + ras.precision ) 2580 { 2581 switch ( dropOutControl ) 2582 { 2583 case 0: /* simple drop-outs including stubs */ 2584 pxl = e2; 2585 break; 2586 2587 case 4: /* smart drop-outs including stubs */ 2588 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half ); 2589 break; 2590 2591 case 1: /* simple drop-outs excluding stubs */ 2592 case 5: /* smart drop-outs excluding stubs */ 2593 /* see Vertical_Sweep_Drop for details */ 2594 2595 /* rightmost stub test */ 2596 if ( left->next == right && 2597 left->height <= 0 && 2598 !( left->flags & Overshoot_Top && 2599 x2 - x1 >= ras.precision_half ) ) 2600 goto Exit; 2601 2602 /* leftmost stub test */ 2603 if ( right->next == left && 2604 left->start == y && 2605 !( left->flags & Overshoot_Bottom && 2606 x2 - x1 >= ras.precision_half ) ) 2607 goto Exit; 2608 2609 if ( dropOutControl == 1 ) 2610 pxl = e2; 2611 else 2612 pxl = FLOOR( ( x1 + x2 - 1 ) / 2 + ras.precision_half ); 2613 break; 2614 2615 default: /* modes 2, 3, 6, 7 */ 2616 goto Exit; /* no drop-out control */ 2617 } 2618 2619 /* undocumented but confirmed: If the drop-out would result in a */ 2620 /* pixel outside of the bounding box, use the pixel inside of the */ 2621 /* bounding box instead */ 2622 if ( pxl < 0 ) 2623 pxl = e1; 2624 else if ( (ULong)( TRUNC( pxl ) ) >= ras.target.rows ) 2625 pxl = e2; 2626 2627 /* check that the other pixel isn't set */ 2628 e1 = ( pxl == e1 ) ? e2 : e1; 2629 2630 e1 = TRUNC( e1 ); 2631 2632 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch; 2633 f1 = (Byte)( 0x80 >> ( y & 7 ) ); 2634 2635 if ( e1 >= 0 && 2636 (ULong)e1 < ras.target.rows && 2637 *bits & f1 ) 2638 goto Exit; 2639 } 2640 else 2641 goto Exit; 2642 } 2643 2644 e1 = TRUNC( pxl ); 2645 2646 if ( e1 >= 0 && (ULong)e1 < ras.target.rows ) 2647 { 2648 FT_TRACE7(( " -> y=%d (drop-out)", e1 )); 2649 2650 bits = ras.bOrigin + ( y >> 3 ) - e1 * ras.target.pitch; 2651 f1 = (Byte)( 0x80 >> ( y & 7 ) ); 2652 2653 bits[0] |= f1; 2654 } 2655 2656 Exit: 2657 FT_TRACE7(( "\n" )); 2658 } 2659 2660 2661 static void 2662 Horizontal_Sweep_Step( RAS_ARG ) 2663 { 2664 /* Nothing, really */ 2665 FT_UNUSED_RASTER; 2666 } 2667 2668 2669 /************************************************************************** 2670 * 2671 * Generic Sweep Drawing routine 2672 * 2673 */ 2674 2675 static Bool 2676 Draw_Sweep( RAS_ARG ) 2677 { 2678 Short y, y_change, y_height; 2679 2680 PProfile P, Q, P_Left, P_Right; 2681 2682 Short min_Y, max_Y, top, bottom, dropouts; 2683 2684 Long x1, x2, xs, e1, e2; 2685 2686 TProfileList waiting; 2687 TProfileList draw_left, draw_right; 2688 2689 2690 /* initialize empty linked lists */ 2691 2692 Init_Linked( &waiting ); 2693 2694 Init_Linked( &draw_left ); 2695 Init_Linked( &draw_right ); 2696 2697 /* first, compute min and max Y */ 2698 2699 P = ras.fProfile; 2700 max_Y = (Short)TRUNC( ras.minY ); 2701 min_Y = (Short)TRUNC( ras.maxY ); 2702 2703 while ( P ) 2704 { 2705 Q = P->link; 2706 2707 bottom = (Short)P->start; 2708 top = (Short)( P->start + P->height - 1 ); 2709 2710 if ( min_Y > bottom ) 2711 min_Y = bottom; 2712 if ( max_Y < top ) 2713 max_Y = top; 2714 2715 P->X = 0; 2716 InsNew( &waiting, P ); 2717 2718 P = Q; 2719 } 2720 2721 /* check the Y-turns */ 2722 if ( ras.numTurns == 0 ) 2723 { 2724 ras.error = FT_THROW( Invalid ); 2725 return FAILURE; 2726 } 2727 2728 /* now initialize the sweep */ 2729 2730 ras.Proc_Sweep_Init( RAS_VARS &min_Y, &max_Y ); 2731 2732 /* then compute the distance of each profile from min_Y */ 2733 2734 P = waiting; 2735 2736 while ( P ) 2737 { 2738 P->countL = P->start - min_Y; 2739 P = P->link; 2740 } 2741 2742 /* let's go */ 2743 2744 y = min_Y; 2745 y_height = 0; 2746 2747 if ( ras.numTurns > 0 && 2748 ras.sizeBuff[-ras.numTurns] == min_Y ) 2749 ras.numTurns--; 2750 2751 while ( ras.numTurns > 0 ) 2752 { 2753 /* check waiting list for new activations */ 2754 2755 P = waiting; 2756 2757 while ( P ) 2758 { 2759 Q = P->link; 2760 P->countL -= y_height; 2761 if ( P->countL == 0 ) 2762 { 2763 DelOld( &waiting, P ); 2764 2765 if ( P->flags & Flow_Up ) 2766 InsNew( &draw_left, P ); 2767 else 2768 InsNew( &draw_right, P ); 2769 } 2770 2771 P = Q; 2772 } 2773 2774 /* sort the drawing lists */ 2775 2776 Sort( &draw_left ); 2777 Sort( &draw_right ); 2778 2779 y_change = (Short)ras.sizeBuff[-ras.numTurns--]; 2780 y_height = (Short)( y_change - y ); 2781 2782 while ( y < y_change ) 2783 { 2784 /* let's trace */ 2785 2786 dropouts = 0; 2787 2788 P_Left = draw_left; 2789 P_Right = draw_right; 2790 2791 while ( P_Left && P_Right ) 2792 { 2793 x1 = P_Left ->X; 2794 x2 = P_Right->X; 2795 2796 if ( x1 > x2 ) 2797 { 2798 xs = x1; 2799 x1 = x2; 2800 x2 = xs; 2801 } 2802 2803 e1 = FLOOR( x1 ); 2804 e2 = CEILING( x2 ); 2805 2806 if ( x2 - x1 <= ras.precision && 2807 e1 != x1 && e2 != x2 ) 2808 { 2809 if ( e1 > e2 || e2 == e1 + ras.precision ) 2810 { 2811 Int dropOutControl = P_Left->flags & 7; 2812 2813 2814 if ( dropOutControl != 2 ) 2815 { 2816 /* a drop-out was detected */ 2817 2818 P_Left ->X = x1; 2819 P_Right->X = x2; 2820 2821 /* mark profile for drop-out processing */ 2822 P_Left->countL = 1; 2823 dropouts++; 2824 } 2825 2826 goto Skip_To_Next; 2827 } 2828 } 2829 2830 ras.Proc_Sweep_Span( RAS_VARS y, x1, x2, P_Left, P_Right ); 2831 2832 Skip_To_Next: 2833 2834 P_Left = P_Left->link; 2835 P_Right = P_Right->link; 2836 } 2837 2838 /* handle drop-outs _after_ the span drawing -- */ 2839 /* drop-out processing has been moved out of the loop */ 2840 /* for performance tuning */ 2841 if ( dropouts > 0 ) 2842 goto Scan_DropOuts; 2843 2844 Next_Line: 2845 2846 ras.Proc_Sweep_Step( RAS_VAR ); 2847 2848 y++; 2849 2850 if ( y < y_change ) 2851 { 2852 Sort( &draw_left ); 2853 Sort( &draw_right ); 2854 } 2855 } 2856 2857 /* now finalize the profiles that need it */ 2858 2859 P = draw_left; 2860 while ( P ) 2861 { 2862 Q = P->link; 2863 if ( P->height == 0 ) 2864 DelOld( &draw_left, P ); 2865 P = Q; 2866 } 2867 2868 P = draw_right; 2869 while ( P ) 2870 { 2871 Q = P->link; 2872 if ( P->height == 0 ) 2873 DelOld( &draw_right, P ); 2874 P = Q; 2875 } 2876 } 2877 2878 /* for gray-scaling, flush the bitmap scanline cache */ 2879 while ( y <= max_Y ) 2880 { 2881 ras.Proc_Sweep_Step( RAS_VAR ); 2882 y++; 2883 } 2884 2885 return SUCCESS; 2886 2887 Scan_DropOuts: 2888 2889 P_Left = draw_left; 2890 P_Right = draw_right; 2891 2892 while ( P_Left && P_Right ) 2893 { 2894 if ( P_Left->countL ) 2895 { 2896 P_Left->countL = 0; 2897 #if 0 2898 dropouts--; /* -- this is useful when debugging only */ 2899 #endif 2900 ras.Proc_Sweep_Drop( RAS_VARS y, 2901 P_Left->X, 2902 P_Right->X, 2903 P_Left, 2904 P_Right ); 2905 } 2906 2907 P_Left = P_Left->link; 2908 P_Right = P_Right->link; 2909 } 2910 2911 goto Next_Line; 2912 } 2913 2914 2915 #ifdef STANDALONE_ 2916 2917 /************************************************************************** 2918 * 2919 * The following functions should only compile in stand-alone mode, 2920 * i.e., when building this component without the rest of FreeType. 2921 * 2922 */ 2923 2924 /************************************************************************** 2925 * 2926 * @Function: 2927 * FT_Outline_Get_CBox 2928 * 2929 * @Description: 2930 * Return an outline's `control box'. The control box encloses all 2931 * the outline's points, including Bézier control points. Though it 2932 * coincides with the exact bounding box for most glyphs, it can be 2933 * slightly larger in some situations (like when rotating an outline 2934 * that contains Bézier outside arcs). 2935 * 2936 * Computing the control box is very fast, while getting the bounding 2937 * box can take much more time as it needs to walk over all segments 2938 * and arcs in the outline. To get the latter, you can use the 2939 * `ftbbox' component, which is dedicated to this single task. 2940 * 2941 * @Input: 2942 * outline :: 2943 * A pointer to the source outline descriptor. 2944 * 2945 * @Output: 2946 * acbox :: 2947 * The outline's control box. 2948 * 2949 * @Note: 2950 * See @FT_Glyph_Get_CBox for a discussion of tricky fonts. 2951 */ 2952 2953 static void 2954 FT_Outline_Get_CBox( const FT_Outline* outline, 2955 FT_BBox *acbox ) 2956 { 2957 Long xMin, yMin, xMax, yMax; 2958 2959 2960 if ( outline && acbox ) 2961 { 2962 if ( outline->n_points == 0 ) 2963 { 2964 xMin = 0; 2965 yMin = 0; 2966 xMax = 0; 2967 yMax = 0; 2968 } 2969 else 2970 { 2971 FT_Vector* vec = outline->points; 2972 FT_Vector* limit = vec + outline->n_points; 2973 2974 2975 xMin = xMax = vec->x; 2976 yMin = yMax = vec->y; 2977 vec++; 2978 2979 for ( ; vec < limit; vec++ ) 2980 { 2981 Long x, y; 2982 2983 2984 x = vec->x; 2985 if ( x < xMin ) xMin = x; 2986 if ( x > xMax ) xMax = x; 2987 2988 y = vec->y; 2989 if ( y < yMin ) yMin = y; 2990 if ( y > yMax ) yMax = y; 2991 } 2992 } 2993 acbox->xMin = xMin; 2994 acbox->xMax = xMax; 2995 acbox->yMin = yMin; 2996 acbox->yMax = yMax; 2997 } 2998 } 2999 3000 #endif /* STANDALONE_ */ 3001 3002 3003 /************************************************************************** 3004 * 3005 * @Function: 3006 * Render_Single_Pass 3007 * 3008 * @Description: 3009 * Perform one sweep with sub-banding. 3010 * 3011 * @Input: 3012 * flipped :: 3013 * If set, flip the direction of the outline. 3014 * 3015 * @Return: 3016 * Renderer error code. 3017 */ 3018 static int 3019 Render_Single_Pass( RAS_ARGS Bool flipped ) 3020 { 3021 Short i, j, k; 3022 3023 3024 while ( ras.band_top >= 0 ) 3025 { 3026 ras.maxY = (Long)ras.band_stack[ras.band_top].y_max * ras.precision; 3027 ras.minY = (Long)ras.band_stack[ras.band_top].y_min * ras.precision; 3028 3029 ras.top = ras.buff; 3030 3031 ras.error = Raster_Err_None; 3032 3033 if ( Convert_Glyph( RAS_VARS flipped ) ) 3034 { 3035 if ( ras.error != Raster_Err_Overflow ) 3036 return FAILURE; 3037 3038 ras.error = Raster_Err_None; 3039 3040 /* sub-banding */ 3041 3042 #ifdef DEBUG_RASTER 3043 ClearBand( RAS_VARS TRUNC( ras.minY ), TRUNC( ras.maxY ) ); 3044 #endif 3045 3046 i = ras.band_stack[ras.band_top].y_min; 3047 j = ras.band_stack[ras.band_top].y_max; 3048 3049 k = (Short)( ( i + j ) / 2 ); 3050 3051 if ( ras.band_top >= 7 || k < i ) 3052 { 3053 ras.band_top = 0; 3054 ras.error = FT_THROW( Invalid ); 3055 3056 return ras.error; 3057 } 3058 3059 ras.band_stack[ras.band_top + 1].y_min = k; 3060 ras.band_stack[ras.band_top + 1].y_max = j; 3061 3062 ras.band_stack[ras.band_top].y_max = (Short)( k - 1 ); 3063 3064 ras.band_top++; 3065 } 3066 else 3067 { 3068 if ( ras.fProfile ) 3069 if ( Draw_Sweep( RAS_VAR ) ) 3070 return ras.error; 3071 ras.band_top--; 3072 } 3073 } 3074 3075 return SUCCESS; 3076 } 3077 3078 3079 /************************************************************************** 3080 * 3081 * @Function: 3082 * Render_Glyph 3083 * 3084 * @Description: 3085 * Render a glyph in a bitmap. Sub-banding if needed. 3086 * 3087 * @Return: 3088 * FreeType error code. 0 means success. 3089 */ 3090 static FT_Error 3091 Render_Glyph( RAS_ARG ) 3092 { 3093 FT_Error error; 3094 3095 3096 Set_High_Precision( RAS_VARS ras.outline.flags & 3097 FT_OUTLINE_HIGH_PRECISION ); 3098 3099 if ( ras.outline.flags & FT_OUTLINE_IGNORE_DROPOUTS ) 3100 ras.dropOutControl = 2; 3101 else 3102 { 3103 if ( ras.outline.flags & FT_OUTLINE_SMART_DROPOUTS ) 3104 ras.dropOutControl = 4; 3105 else 3106 ras.dropOutControl = 0; 3107 3108 if ( !( ras.outline.flags & FT_OUTLINE_INCLUDE_STUBS ) ) 3109 ras.dropOutControl += 1; 3110 } 3111 3112 ras.second_pass = (Bool)( !( ras.outline.flags & 3113 FT_OUTLINE_SINGLE_PASS ) ); 3114 3115 /* Vertical Sweep */ 3116 FT_TRACE7(( "Vertical pass (ftraster)\n" )); 3117 3118 ras.Proc_Sweep_Init = Vertical_Sweep_Init; 3119 ras.Proc_Sweep_Span = Vertical_Sweep_Span; 3120 ras.Proc_Sweep_Drop = Vertical_Sweep_Drop; 3121 ras.Proc_Sweep_Step = Vertical_Sweep_Step; 3122 3123 ras.band_top = 0; 3124 ras.band_stack[0].y_min = 0; 3125 ras.band_stack[0].y_max = (Short)( ras.target.rows - 1 ); 3126 3127 ras.bWidth = (UShort)ras.target.width; 3128 ras.bOrigin = (Byte*)ras.target.buffer; 3129 3130 if ( ras.target.pitch > 0 ) 3131 ras.bOrigin += (Long)( ras.target.rows - 1 ) * ras.target.pitch; 3132 3133 if ( ( error = Render_Single_Pass( RAS_VARS 0 ) ) != 0 ) 3134 return error; 3135 3136 /* Horizontal Sweep */ 3137 if ( ras.second_pass && ras.dropOutControl != 2 ) 3138 { 3139 FT_TRACE7(( "Horizontal pass (ftraster)\n" )); 3140 3141 ras.Proc_Sweep_Init = Horizontal_Sweep_Init; 3142 ras.Proc_Sweep_Span = Horizontal_Sweep_Span; 3143 ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop; 3144 ras.Proc_Sweep_Step = Horizontal_Sweep_Step; 3145 3146 ras.band_top = 0; 3147 ras.band_stack[0].y_min = 0; 3148 ras.band_stack[0].y_max = (Short)( ras.target.width - 1 ); 3149 3150 if ( ( error = Render_Single_Pass( RAS_VARS 1 ) ) != 0 ) 3151 return error; 3152 } 3153 3154 return Raster_Err_None; 3155 } 3156 3157 3158 static void 3159 ft_black_init( black_PRaster raster ) 3160 { 3161 FT_UNUSED( raster ); 3162 } 3163 3164 3165 /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/ 3166 /**** a static object. *****/ 3167 3168 3169 #ifdef STANDALONE_ 3170 3171 3172 static int 3173 ft_black_new( void* memory, 3174 FT_Raster *araster ) 3175 { 3176 static black_TRaster the_raster; 3177 FT_UNUSED( memory ); 3178 3179 3180 *araster = (FT_Raster)&the_raster; 3181 FT_ZERO( &the_raster ); 3182 ft_black_init( &the_raster ); 3183 3184 return 0; 3185 } 3186 3187 3188 static void 3189 ft_black_done( FT_Raster raster ) 3190 { 3191 /* nothing */ 3192 FT_UNUSED( raster ); 3193 } 3194 3195 3196 #else /* !STANDALONE_ */ 3197 3198 3199 static int 3200 ft_black_new( FT_Memory memory, 3201 black_PRaster *araster ) 3202 { 3203 FT_Error error; 3204 black_PRaster raster = NULL; 3205 3206 3207 *araster = 0; 3208 if ( !FT_NEW( raster ) ) 3209 { 3210 raster->memory = memory; 3211 ft_black_init( raster ); 3212 3213 *araster = raster; 3214 } 3215 3216 return error; 3217 } 3218 3219 3220 static void 3221 ft_black_done( black_PRaster raster ) 3222 { 3223 FT_Memory memory = (FT_Memory)raster->memory; 3224 3225 3226 FT_FREE( raster ); 3227 } 3228 3229 3230 #endif /* !STANDALONE_ */ 3231 3232 3233 static void 3234 ft_black_reset( FT_Raster raster, 3235 PByte pool_base, 3236 ULong pool_size ) 3237 { 3238 FT_UNUSED( raster ); 3239 FT_UNUSED( pool_base ); 3240 FT_UNUSED( pool_size ); 3241 } 3242 3243 3244 static int 3245 ft_black_set_mode( FT_Raster raster, 3246 ULong mode, 3247 void* args ) 3248 { 3249 FT_UNUSED( raster ); 3250 FT_UNUSED( mode ); 3251 FT_UNUSED( args ); 3252 3253 return 0; 3254 } 3255 3256 3257 static int 3258 ft_black_render( FT_Raster raster, 3259 const FT_Raster_Params* params ) 3260 { 3261 const FT_Outline* outline = (const FT_Outline*)params->source; 3262 const FT_Bitmap* target_map = params->target; 3263 3264 #ifndef FT_STATIC_RASTER 3265 black_TWorker worker[1]; 3266 #endif 3267 3268 Long buffer[FT_MAX_BLACK_POOL]; 3269 3270 3271 if ( !raster ) 3272 return FT_THROW( Not_Ini ); 3273 3274 if ( !outline ) 3275 return FT_THROW( Invalid ); 3276 3277 /* return immediately if the outline is empty */ 3278 if ( outline->n_points == 0 || outline->n_contours <= 0 ) 3279 return Raster_Err_None; 3280 3281 if ( !outline->contours || !outline->points ) 3282 return FT_THROW( Invalid ); 3283 3284 if ( outline->n_points != 3285 outline->contours[outline->n_contours - 1] + 1 ) 3286 return FT_THROW( Invalid ); 3287 3288 /* this version of the raster does not support direct rendering, sorry */ 3289 if ( params->flags & FT_RASTER_FLAG_DIRECT ) 3290 return FT_THROW( Unsupported ); 3291 3292 if ( params->flags & FT_RASTER_FLAG_AA ) 3293 return FT_THROW( Unsupported ); 3294 3295 if ( !target_map ) 3296 return FT_THROW( Invalid ); 3297 3298 /* nothing to do */ 3299 if ( !target_map->width || !target_map->rows ) 3300 return Raster_Err_None; 3301 3302 if ( !target_map->buffer ) 3303 return FT_THROW( Invalid ); 3304 3305 ras.outline = *outline; 3306 ras.target = *target_map; 3307 3308 ras.buff = buffer; 3309 ras.sizeBuff = (&buffer)[1]; /* Points to right after buffer. */ 3310 3311 return Render_Glyph( RAS_VAR ); 3312 } 3313 3314 3315 FT_DEFINE_RASTER_FUNCS( 3316 ft_standard_raster, 3317 3318 FT_GLYPH_FORMAT_OUTLINE, 3319 3320 (FT_Raster_New_Func) ft_black_new, /* raster_new */ 3321 (FT_Raster_Reset_Func) ft_black_reset, /* raster_reset */ 3322 (FT_Raster_Set_Mode_Func)ft_black_set_mode, /* raster_set_mode */ 3323 (FT_Raster_Render_Func) ft_black_render, /* raster_render */ 3324 (FT_Raster_Done_Func) ft_black_done /* raster_done */ 3325 ) 3326 3327 3328 /* END */