1 /**************************************************************************** 2 * 3 * ftbsdf.c 4 * 5 * Signed Distance Field support for bitmap fonts (body only). 6 * 7 * Copyright (C) 2020-2021 by 8 * David Turner, Robert Wilhelm, and Werner Lemberg. 9 * 10 * Written by Anuj Verma. 11 * 12 * This file is part of the FreeType project, and may only be used, 13 * modified, and distributed under the terms of the FreeType project 14 * license, LICENSE.TXT. By continuing to use, modify, or distribute 15 * this file you indicate that you have read the license and 16 * understand and accept it fully. 17 * 18 */ 19 20 21 #include <freetype/internal/ftobjs.h> 22 #include <freetype/internal/ftdebug.h> 23 #include <freetype/internal/ftmemory.h> 24 #include <freetype/fttrigon.h> 25 26 #include "ftsdf.h" 27 #include "ftsdferrs.h" 28 #include "ftsdfcommon.h" 29 30 31 /************************************************************************** 32 * 33 * A brief technical overview of how the BSDF rasterizer works 34 * ----------------------------------------------------------- 35 * 36 * [Notes]: 37 * * SDF stands for Signed Distance Field everywhere. 38 * 39 * * BSDF stands for Bitmap to Signed Distance Field rasterizer. 40 * 41 * * This renderer converts rasterized bitmaps to SDF. There is another 42 * renderer called 'sdf', which generates SDF directly from outlines; 43 * see file `ftsdf.c` for more. 44 * 45 * * The idea of generating SDF from bitmaps is taken from two research 46 * papers, where one is dependent on the other: 47 * 48 * - Per-Erik Danielsson: Euclidean Distance Mapping 49 * http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf 50 * 51 * From this paper we use the eight-point sequential Euclidean 52 * distance mapping (8SED). This is the heart of the process used 53 * in this rasterizer. 54 * 55 * - Stefan Gustavson, Robin Strand: Anti-aliased Euclidean distance transform. 56 * http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf 57 * 58 * The original 8SED algorithm discards the pixels' alpha values, 59 * which can contain information about the actual outline of the 60 * glyph. This paper takes advantage of those alpha values and 61 * approximates outline pretty accurately. 62 * 63 * * This rasterizer also works for monochrome bitmaps. However, the 64 * result is not as accurate since we don't have any way to 65 * approximate outlines from binary bitmaps. 66 * 67 * ======================================================================== 68 * 69 * Generating SDF from bitmap is done in several steps. 70 * 71 * (1) The only information we have is the bitmap itself. It can 72 * be monochrome or anti-aliased. If it is anti-aliased, pixel values 73 * are nothing but coverage values. These coverage values can be used 74 * to extract information about the outline of the image. For 75 * example, if the pixel's alpha value is 0.5, then we can safely 76 * assume that the outline passes through the center of the pixel. 77 * 78 * (2) Find edge pixels in the bitmap (see `bsdf_is_edge` for more). For 79 * all edge pixels we use the Anti-aliased Euclidean distance 80 * transform algorithm and compute approximate edge distances (see 81 * `compute_edge_distance` and/or the second paper for more). 82 * 83 * (3) Now that we have computed approximate distances for edge pixels we 84 * use the 8SED algorithm to basically sweep the entire bitmap and 85 * compute distances for the rest of the pixels. (Since the algorithm 86 * is pretty convoluted it is only explained briefly in a comment to 87 * function `edt8`. To see the actual algorithm refer to the first 88 * paper.) 89 * 90 * (4) Finally, compute the sign for each pixel. This is done in function 91 * `finalize_sdf`. The basic idea is that if a pixel's original 92 * alpha/coverage value is greater than 0.5 then it is 'inside' (and 93 * 'outside' otherwise). 94 * 95 * Pseudo Code: 96 * 97 * ``` 98 * b = source bitmap; 99 * t = target bitmap; 100 * dm = list of distances; // dimension equal to b 101 * 102 * foreach grid_point (x, y) in b: 103 * { 104 * if (is_edge(x, y)): 105 * dm = approximate_edge_distance(b, x, y); 106 * 107 * // do the 8SED on the distances 108 * edt8(dm); 109 * 110 * // determine the signs 111 * determine_signs(dm): 112 * 113 * // copy SDF data to the target bitmap 114 * copy(dm to t); 115 * } 116 * 117 */ 118 119 120 /************************************************************************** 121 * 122 * The macro FT_COMPONENT is used in trace mode. It is an implicit 123 * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log 124 * messages during execution. 125 */ 126 #undef FT_COMPONENT 127 #define FT_COMPONENT bsdf 128 129 130 /************************************************************************** 131 * 132 * useful macros 133 * 134 */ 135 136 #define ONE 65536 /* 1 in 16.16 */ 137 138 139 /************************************************************************** 140 * 141 * structs 142 * 143 */ 144 145 146 /************************************************************************** 147 * 148 * @Struct: 149 * BSDF_TRaster 150 * 151 * @Description: 152 * This struct is used in place of @FT_Raster and is stored within the 153 * internal FreeType renderer struct. While rasterizing this is passed 154 * to the @FT_Raster_RenderFunc function, which then can be used however 155 * we want. 156 * 157 * @Fields: 158 * memory :: 159 * Used internally to allocate intermediate memory while raterizing. 160 * 161 */ 162 typedef struct BSDF_TRaster_ 163 { 164 FT_Memory memory; 165 166 } BSDF_TRaster, *BSDF_PRaster; 167 168 169 /************************************************************************** 170 * 171 * @Struct: 172 * ED 173 * 174 * @Description: 175 * Euclidean distance. It gets used for Euclidean distance transforms; 176 * it can also be interpreted as an edge distance. 177 * 178 * @Fields: 179 * dist :: 180 * Vector length of the `near` parameter. Can be squared or absolute 181 * depending on the `USE_SQUARED_DISTANCES` macro defined in file 182 * `ftsdfcommon.h`. 183 * 184 * near :: 185 * Vector to the nearest edge. Can also be interpreted as shortest 186 * distance of a point. 187 * 188 * alpha :: 189 * Alpha value of the original bitmap from which we generate SDF. 190 * Needed for computing the gradient and determining the proper sign 191 * of a pixel. 192 * 193 */ 194 typedef struct ED_ 195 { 196 FT_16D16 dist; 197 FT_16D16_Vec near; 198 FT_Byte alpha; 199 200 } ED; 201 202 203 /************************************************************************** 204 * 205 * @Struct: 206 * BSDF_Worker 207 * 208 * @Description: 209 * A convenience struct that is passed to functions while generating 210 * SDF; most of those functions require the same parameters. 211 * 212 * @Fields: 213 * distance_map :: 214 * A one-dimensional array that gets interpreted as two-dimensional 215 * one. It contains the Euclidean distances of all points of the 216 * bitmap. 217 * 218 * width :: 219 * Width of the above `distance_map`. 220 * 221 * rows :: 222 * Number of rows in the above `distance_map`. 223 * 224 * params :: 225 * Internal parameters and properties required by the rasterizer. See 226 * file `ftsdf.h` for more. 227 * 228 */ 229 typedef struct BSDF_Worker_ 230 { 231 ED* distance_map; 232 233 FT_Int width; 234 FT_Int rows; 235 236 SDF_Raster_Params params; 237 238 } BSDF_Worker; 239 240 241 /************************************************************************** 242 * 243 * initializer 244 * 245 */ 246 247 static const ED zero_ed = { 0, { 0, 0 }, 0 }; 248 249 250 /************************************************************************** 251 * 252 * rasterizer functions 253 * 254 */ 255 256 /************************************************************************** 257 * 258 * @Function: 259 * bsdf_is_edge 260 * 261 * @Description: 262 * Check whether a pixel is an edge pixel, i.e., whether it is 263 * surrounded by a completely black pixel (zero alpha), and the current 264 * pixel is not a completely black pixel. 265 * 266 * @Input: 267 * dm :: 268 * Array of distances. The parameter must point to the current 269 * pixel, i.e., the pixel that is to be checked for being an edge. 270 * 271 * x :: 272 * The x position of the current pixel. 273 * 274 * y :: 275 * The y position of the current pixel. 276 * 277 * w :: 278 * Width of the bitmap. 279 * 280 * r :: 281 * Number of rows in the bitmap. 282 * 283 * @Return: 284 * 1~if the current pixel is an edge pixel, 0~otherwise. 285 * 286 */ 287 288 #ifdef CHECK_NEIGHBOR 289 #undef CHECK_NEIGHBOR 290 #endif 291 292 #define CHECK_NEIGHBOR( x_offset, y_offset ) \ 293 do \ 294 { \ 295 if ( x + x_offset >= 0 && x + x_offset < w && \ 296 y + y_offset >= 0 && y + y_offset < r ) \ 297 { \ 298 num_neighbors++; \ 299 \ 300 to_check = dm + y_offset * w + x_offset; \ 301 if ( to_check->alpha == 0 ) \ 302 { \ 303 is_edge = 1; \ 304 goto Done; \ 305 } \ 306 } \ 307 } while ( 0 ) 308 309 static FT_Bool bsdf_is_edge(ED * dm,FT_Int x,FT_Int y,FT_Int w,FT_Int r)310 bsdf_is_edge( ED* dm, /* distance map */ 311 FT_Int x, /* x index of point to check */ 312 FT_Int y, /* y index of point to check */ 313 FT_Int w, /* width */ 314 FT_Int r ) /* rows */ 315 { 316 FT_Bool is_edge = 0; 317 ED* to_check = NULL; 318 FT_Int num_neighbors = 0; 319 320 321 if ( dm->alpha == 0 ) 322 goto Done; 323 324 if ( dm->alpha > 0 && dm->alpha < 255 ) 325 { 326 is_edge = 1; 327 goto Done; 328 } 329 330 /* up */ 331 CHECK_NEIGHBOR( 0, -1 ); 332 333 /* down */ 334 CHECK_NEIGHBOR( 0, 1 ); 335 336 /* left */ 337 CHECK_NEIGHBOR( -1, 0 ); 338 339 /* right */ 340 CHECK_NEIGHBOR( 1, 0 ); 341 342 /* up left */ 343 CHECK_NEIGHBOR( -1, -1 ); 344 345 /* up right */ 346 CHECK_NEIGHBOR( 1, -1 ); 347 348 /* down left */ 349 CHECK_NEIGHBOR( -1, 1 ); 350 351 /* down right */ 352 CHECK_NEIGHBOR( 1, 1 ); 353 354 if ( num_neighbors != 8 ) 355 is_edge = 1; 356 357 Done: 358 return is_edge; 359 } 360 361 #undef CHECK_NEIGHBOR 362 363 364 /************************************************************************** 365 * 366 * @Function: 367 * compute_edge_distance 368 * 369 * @Description: 370 * Approximate the outline and compute the distance from `current` 371 * to the approximated outline. 372 * 373 * @Input: 374 * current :: 375 * Array of Euclidean distances. `current` must point to the position 376 * for which the distance is to be caculated. We treat this array as 377 * a two-dimensional array mapped to a one-dimensional array. 378 * 379 * x :: 380 * The x coordinate of the `current` parameter in the array. 381 * 382 * y :: 383 * The y coordinate of the `current` parameter in the array. 384 * 385 * w :: 386 * The width of the distances array. 387 * 388 * r :: 389 * Number of rows in the distances array. 390 * 391 * @Return: 392 * A vector pointing to the approximate edge distance. 393 * 394 * @Note: 395 * This is a computationally expensive function. Try to reduce the 396 * number of calls to this function. Moreover, this must only be used 397 * for edge pixel positions. 398 * 399 */ 400 static FT_16D16_Vec compute_edge_distance(ED * current,FT_Int x,FT_Int y,FT_Int w,FT_Int r)401 compute_edge_distance( ED* current, 402 FT_Int x, 403 FT_Int y, 404 FT_Int w, 405 FT_Int r ) 406 { 407 /* 408 * This function, based on the paper presented by Stefan Gustavson and 409 * Robin Strand, gets used to approximate edge distances from 410 * anti-aliased bitmaps. 411 * 412 * The algorithm is as follows. 413 * 414 * (1) In anti-aliased images, the pixel's alpha value is the coverage 415 * of the pixel by the outline. For example, if the alpha value is 416 * 0.5f we can assume that the outline passes through the center of 417 * the pixel. 418 * 419 * (2) For this reason we can use that alpha value to approximate the real 420 * distance of the pixel to edge pretty accurately. A simple 421 * approximation is `(0.5f - alpha)`, assuming that the outline is 422 * parallel to the x or y~axis. However, in this algorithm we use a 423 * different approximation which is quite accurate even for 424 * non-axis-aligned edges. 425 * 426 * (3) The only remaining piece of information that we cannot 427 * approximate directly from the alpha is the direction of the edge. 428 * This is where we use Sobel's operator to compute the gradient of 429 * the pixel. The gradient give us a pretty good approximation of 430 * the edge direction. We use a 3x3 kernel filter to compute the 431 * gradient. 432 * 433 * (4) After the above two steps we have both the direction and the 434 * distance to the edge which is used to generate the Signed 435 * Distance Field. 436 * 437 * References: 438 * 439 * - Anti-Aliased Euclidean Distance Transform: 440 * http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf 441 * - Sobel Operator: 442 * https://en.wikipedia.org/wiki/Sobel_operator 443 */ 444 445 FT_16D16_Vec g = { 0, 0 }; 446 FT_16D16 dist, current_alpha; 447 FT_16D16 a1, temp; 448 FT_16D16 gx, gy; 449 FT_16D16 alphas[9]; 450 451 452 /* Since our spread cannot be 0, this condition */ 453 /* can never be true. */ 454 if ( x <= 0 || x >= w - 1 || 455 y <= 0 || y >= r - 1 ) 456 return g; 457 458 /* initialize the alphas */ 459 alphas[0] = 256 * (FT_16D16)current[-w - 1].alpha; 460 alphas[1] = 256 * (FT_16D16)current[-w ].alpha; 461 alphas[2] = 256 * (FT_16D16)current[-w + 1].alpha; 462 alphas[3] = 256 * (FT_16D16)current[ -1].alpha; 463 alphas[4] = 256 * (FT_16D16)current[ 0].alpha; 464 alphas[5] = 256 * (FT_16D16)current[ 1].alpha; 465 alphas[6] = 256 * (FT_16D16)current[ w - 1].alpha; 466 alphas[7] = 256 * (FT_16D16)current[ w ].alpha; 467 alphas[8] = 256 * (FT_16D16)current[ w + 1].alpha; 468 469 current_alpha = alphas[4]; 470 471 /* Compute the gradient using the Sobel operator. */ 472 /* In this case we use the following 3x3 filters: */ 473 /* */ 474 /* For x: | -1 0 -1 | */ 475 /* | -root(2) 0 root(2) | */ 476 /* | -1 0 1 | */ 477 /* */ 478 /* For y: | -1 -root(2) -1 | */ 479 /* | 0 0 0 | */ 480 /* | 1 root(2) 1 | */ 481 /* */ 482 /* [Note]: 92681 is root(2) in 16.16 format. */ 483 g.x = -alphas[0] - 484 FT_MulFix( alphas[3], 92681 ) - 485 alphas[6] + 486 alphas[2] + 487 FT_MulFix( alphas[5], 92681 ) + 488 alphas[8]; 489 490 g.y = -alphas[0] - 491 FT_MulFix( alphas[1], 92681 ) - 492 alphas[2] + 493 alphas[6] + 494 FT_MulFix( alphas[7], 92681 ) + 495 alphas[8]; 496 497 FT_Vector_NormLen( &g ); 498 499 /* The gradient gives us the direction of the */ 500 /* edge for the current pixel. Once we have the */ 501 /* approximate direction of the edge, we can */ 502 /* approximate the edge distance much better. */ 503 504 if ( g.x == 0 || g.y == 0 ) 505 dist = ONE / 2 - alphas[4]; 506 else 507 { 508 gx = g.x; 509 gy = g.y; 510 511 gx = FT_ABS( gx ); 512 gy = FT_ABS( gy ); 513 514 if ( gx < gy ) 515 { 516 temp = gx; 517 gx = gy; 518 gy = temp; 519 } 520 521 a1 = FT_DivFix( gy, gx ) / 2; 522 523 if ( current_alpha < a1 ) 524 dist = ( gx + gy ) / 2 - 525 square_root( 2 * FT_MulFix( gx, 526 FT_MulFix( gy, 527 current_alpha ) ) ); 528 529 else if ( current_alpha < ( ONE - a1 ) ) 530 dist = FT_MulFix( ONE / 2 - current_alpha, gx ); 531 532 else 533 dist = -( gx + gy ) / 2 + 534 square_root( 2 * FT_MulFix( gx, 535 FT_MulFix( gy, 536 ONE - current_alpha ) ) ); 537 } 538 539 g.x = FT_MulFix( g.x, dist ); 540 g.y = FT_MulFix( g.y, dist ); 541 542 return g; 543 } 544 545 546 /************************************************************************** 547 * 548 * @Function: 549 * bsdf_approximate_edge 550 * 551 * @Description: 552 * Loops over all the pixels and call `compute_edge_distance` only for 553 * edge pixels. This maked the process a lot faster since 554 * `compute_edge_distance` uses functions such as `FT_Vector_NormLen', 555 * which are quite slow. 556 * 557 * @InOut: 558 * worker :: 559 * Contains the distance map as well as all the relevant parameters 560 * required by the function. 561 * 562 * @Return: 563 * FreeType error, 0 means success. 564 * 565 * @Note: 566 * The function directly manipulates `worker->distance_map`. 567 * 568 */ 569 static FT_Error bsdf_approximate_edge(BSDF_Worker * worker)570 bsdf_approximate_edge( BSDF_Worker* worker ) 571 { 572 FT_Error error = FT_Err_Ok; 573 FT_Int i, j; 574 FT_Int index; 575 ED* ed; 576 577 578 if ( !worker || !worker->distance_map ) 579 { 580 error = FT_THROW( Invalid_Argument ); 581 goto Exit; 582 } 583 584 ed = worker->distance_map; 585 586 for ( j = 0; j < worker->rows; j++ ) 587 { 588 for ( i = 0; i < worker->width; i++ ) 589 { 590 index = j * worker->width + i; 591 592 if ( bsdf_is_edge( worker->distance_map + index, 593 i, j, 594 worker->width, 595 worker->rows ) ) 596 { 597 /* approximate the edge distance for edge pixels */ 598 ed[index].near = compute_edge_distance( ed + index, 599 i, j, 600 worker->width, 601 worker->rows ); 602 ed[index].dist = VECTOR_LENGTH_16D16( ed[index].near ); 603 } 604 else 605 { 606 /* for non-edge pixels assign far away distances */ 607 ed[index].dist = 400 * ONE; 608 ed[index].near.x = 200 * ONE; 609 ed[index].near.y = 200 * ONE; 610 } 611 } 612 } 613 614 Exit: 615 return error; 616 } 617 618 619 /************************************************************************** 620 * 621 * @Function: 622 * bsdf_init_distance_map 623 * 624 * @Description: 625 * Initialize the distance map according to the '8-point sequential 626 * Euclidean distance mapping' (8SED) algorithm. Basically it copies 627 * the `source` bitmap alpha values to the `distance_map->alpha` 628 * parameter of `worker`. 629 * 630 * @Input: 631 * source :: 632 * Source bitmap to copy the data from. 633 * 634 * @Output: 635 * worker :: 636 * Target distance map to copy the data to. 637 * 638 * @Return: 639 * FreeType error, 0 means success. 640 * 641 */ 642 static FT_Error bsdf_init_distance_map(const FT_Bitmap * source,BSDF_Worker * worker)643 bsdf_init_distance_map( const FT_Bitmap* source, 644 BSDF_Worker* worker ) 645 { 646 FT_Error error = FT_Err_Ok; 647 648 FT_Int x_diff, y_diff; 649 FT_Int t_i, t_j, s_i, s_j; 650 FT_Byte* s; 651 ED* t; 652 653 654 /* again check the parameters (probably unnecessary) */ 655 if ( !source || !worker ) 656 { 657 error = FT_THROW( Invalid_Argument ); 658 goto Exit; 659 } 660 661 /* Because of the way we convert a bitmap to SDF, */ 662 /* i.e., aligning the source to the center of the */ 663 /* target, the target's width and rows must be */ 664 /* checked before copying. */ 665 if ( worker->width < (FT_Int)source->width || 666 worker->rows < (FT_Int)source->rows ) 667 { 668 error = FT_THROW( Invalid_Argument ); 669 goto Exit; 670 } 671 672 /* check pixel mode */ 673 if ( source->pixel_mode == FT_PIXEL_MODE_NONE ) 674 { 675 FT_ERROR(( "bsdf_copy_source_to_target:" 676 " Invalid pixel mode of source bitmap" )); 677 error = FT_THROW( Invalid_Argument ); 678 goto Exit; 679 } 680 681 #ifdef FT_DEBUG_LEVEL_TRACE 682 if ( source->pixel_mode == FT_PIXEL_MODE_MONO ) 683 { 684 FT_TRACE0(( "bsdf_copy_source_to_target:" 685 " The `bsdf' renderer can convert monochrome\n" )); 686 FT_TRACE0(( " " 687 " bitmaps to SDF but the results are not perfect\n" )); 688 FT_TRACE0(( " " 689 " because there is no way to approximate actual\n" )); 690 FT_TRACE0(( " " 691 " outlines from monochrome bitmaps. Consider\n" )); 692 FT_TRACE0(( " " 693 " using an anti-aliased bitmap instead.\n" )); 694 } 695 #endif 696 697 /* Calculate the width and row differences */ 698 /* between target and source. */ 699 x_diff = worker->width - (int)source->width; 700 y_diff = worker->rows - (int)source->rows; 701 702 x_diff /= 2; 703 y_diff /= 2; 704 705 t = (ED*)worker->distance_map; 706 s = source->buffer; 707 708 /* For now we only support pixel mode `FT_PIXEL_MODE_MONO` */ 709 /* and `FT_PIXEL_MODE_GRAY`. More will be added later. */ 710 /* */ 711 /* [NOTE]: We can also use @FT_Bitmap_Convert to convert */ 712 /* bitmap to 8bpp. To avoid extra allocation and */ 713 /* since the target bitmap can be 16bpp we manually */ 714 /* convert the source bitmap to the desired bpp. */ 715 716 switch ( source->pixel_mode ) 717 { 718 case FT_PIXEL_MODE_MONO: 719 { 720 FT_Int t_width = worker->width; 721 FT_Int t_rows = worker->rows; 722 FT_Int s_width = (int)source->width; 723 FT_Int s_rows = (int)source->rows; 724 725 726 for ( t_j = 0; t_j < t_rows; t_j++ ) 727 { 728 for ( t_i = 0; t_i < t_width; t_i++ ) 729 { 730 FT_Int t_index = t_j * t_width + t_i; 731 FT_Int s_index; 732 FT_Int div, mod; 733 FT_Byte pixel, byte; 734 735 736 t[t_index] = zero_ed; 737 738 s_i = t_i - x_diff; 739 s_j = t_j - y_diff; 740 741 /* Assign 0 to padding similar to */ 742 /* the source bitmap. */ 743 if ( s_i < 0 || s_i >= s_width || 744 s_j < 0 || s_j >= s_rows ) 745 continue; 746 747 if ( worker->params.flip_y ) 748 s_index = ( s_rows - s_j - 1 ) * source->pitch; 749 else 750 s_index = s_j * source->pitch; 751 752 div = s_index + s_i / 8; 753 mod = 7 - s_i % 8; 754 755 pixel = s[div]; 756 byte = (FT_Byte)( 1 << mod ); 757 758 t[t_index].alpha = pixel & byte ? 255 : 0; 759 760 pixel = 0; 761 } 762 } 763 } 764 break; 765 766 case FT_PIXEL_MODE_GRAY: 767 { 768 FT_Int t_width = worker->width; 769 FT_Int t_rows = worker->rows; 770 FT_Int s_width = (int)source->width; 771 FT_Int s_rows = (int)source->rows; 772 773 774 /* loop over all pixels and assign pixel values from source */ 775 for ( t_j = 0; t_j < t_rows; t_j++ ) 776 { 777 for ( t_i = 0; t_i < t_width; t_i++ ) 778 { 779 FT_Int t_index = t_j * t_width + t_i; 780 FT_Int s_index; 781 782 783 t[t_index] = zero_ed; 784 785 s_i = t_i - x_diff; 786 s_j = t_j - y_diff; 787 788 /* Assign 0 to padding similar to */ 789 /* the source bitmap. */ 790 if ( s_i < 0 || s_i >= s_width || 791 s_j < 0 || s_j >= s_rows ) 792 continue; 793 794 if ( worker->params.flip_y ) 795 s_index = ( s_rows - s_j - 1 ) * s_width + s_i; 796 else 797 s_index = s_j * s_width + s_i; 798 799 /* simply copy the alpha values */ 800 t[t_index].alpha = s[s_index]; 801 } 802 } 803 } 804 break; 805 806 default: 807 FT_ERROR(( "bsdf_copy_source_to_target:" 808 " unsopported pixel mode of source bitmap\n" )); 809 810 error = FT_THROW( Unimplemented_Feature ); 811 break; 812 } 813 814 Exit: 815 return error; 816 } 817 818 819 /************************************************************************** 820 * 821 * @Function: 822 * compare_neighbor 823 * 824 * @Description: 825 * Compare neighbor pixel (which is defined by the offset) and update 826 * `current` distance if the new distance is shorter than the original. 827 * 828 * @Input: 829 * x_offset :: 830 * X offset of the neighbor to be checked. The offset is relative to 831 * the `current`. 832 * 833 * y_offset :: 834 * Y offset of the neighbor to be checked. The offset is relative to 835 * the `current`. 836 * 837 * width :: 838 * Width of the `current` array. 839 * 840 * @InOut: 841 * current :: 842 * Pointer into array of distances. This parameter must point to the 843 * position whose neighbor is to be checked. The array is treated as 844 * a two-dimensional array. 845 * 846 */ 847 static void compare_neighbor(ED * current,FT_Int x_offset,FT_Int y_offset,FT_Int width)848 compare_neighbor( ED* current, 849 FT_Int x_offset, 850 FT_Int y_offset, 851 FT_Int width ) 852 { 853 ED* to_check; 854 FT_16D16 dist; 855 FT_16D16_Vec dist_vec; 856 857 858 to_check = current + ( y_offset * width ) + x_offset; 859 860 /* 861 * While checking for the nearest point we first approximate the 862 * distance of `current` by adding the deviation (which is sqrt(2) at 863 * most). Only if the new value is less than the current value we 864 * calculate the actual distances using `FT_Vector_Length`. This last 865 * step can be omitted by using squared distances. 866 */ 867 868 /* 869 * Approximate the distance. We subtract 1 to avoid precision errors, 870 * which could happen because the two directions can be opposite. 871 */ 872 dist = to_check->dist - ONE; 873 874 if ( dist < current->dist ) 875 { 876 dist_vec = to_check->near; 877 878 dist_vec.x += x_offset * ONE; 879 dist_vec.y += y_offset * ONE; 880 dist = VECTOR_LENGTH_16D16( dist_vec ); 881 882 if ( dist < current->dist ) 883 { 884 current->dist = dist; 885 current->near = dist_vec; 886 } 887 } 888 } 889 890 891 /************************************************************************** 892 * 893 * @Function: 894 * first_pass 895 * 896 * @Description: 897 * First pass of the 8SED algorithm. Loop over the bitmap from top to 898 * bottom and scan each row left to right, updating the distances in 899 * `worker->distance_map`. 900 * 901 * @InOut: 902 * worker:: 903 * Contains all the relevant parameters. 904 * 905 */ 906 static void first_pass(BSDF_Worker * worker)907 first_pass( BSDF_Worker* worker ) 908 { 909 FT_Int i, j; /* iterators */ 910 FT_Int w, r; /* width, rows */ 911 ED* dm; /* distance map */ 912 913 914 dm = worker->distance_map; 915 w = worker->width; 916 r = worker->rows; 917 918 /* Start scanning from top to bottom and sweep each */ 919 /* row back and forth comparing the distances of the */ 920 /* neighborhood. Leave the first row as it has no top */ 921 /* neighbor; it will be covered in the second scan of */ 922 /* the image (from bottom to top). */ 923 for ( j = 1; j < r; j++ ) 924 { 925 FT_Int index; 926 ED* current; 927 928 929 /* Forward pass of rows (left -> right). Leave the first */ 930 /* column, which gets covered in the backward pass. */ 931 for ( i = 1; i < w - 1; i++ ) 932 { 933 index = j * w + i; 934 current = dm + index; 935 936 /* left-up */ 937 compare_neighbor( current, -1, -1, w ); 938 /* up */ 939 compare_neighbor( current, 0, -1, w ); 940 /* up-right */ 941 compare_neighbor( current, 1, -1, w ); 942 /* left */ 943 compare_neighbor( current, -1, 0, w ); 944 } 945 946 /* Backward pass of rows (right -> left). Leave the last */ 947 /* column, which was already covered in the forward pass. */ 948 for ( i = w - 2; i >= 0; i-- ) 949 { 950 index = j * w + i; 951 current = dm + index; 952 953 /* right */ 954 compare_neighbor( current, 1, 0, w ); 955 } 956 } 957 } 958 959 960 /************************************************************************** 961 * 962 * @Function: 963 * second_pass 964 * 965 * @Description: 966 * Second pass of the 8SED algorithm. Loop over the bitmap from bottom 967 * to top and scan each row left to right, updating the distances in 968 * `worker->distance_map`. 969 * 970 * @InOut: 971 * worker:: 972 * Contains all the relevant parameters. 973 * 974 */ 975 static void second_pass(BSDF_Worker * worker)976 second_pass( BSDF_Worker* worker ) 977 { 978 FT_Int i, j; /* iterators */ 979 FT_Int w, r; /* width, rows */ 980 ED* dm; /* distance map */ 981 982 983 dm = worker->distance_map; 984 w = worker->width; 985 r = worker->rows; 986 987 /* Start scanning from bottom to top and sweep each */ 988 /* row back and forth comparing the distances of the */ 989 /* neighborhood. Leave the last row as it has no down */ 990 /* neighbor; it is already covered in the first scan */ 991 /* of the image (from top to bottom). */ 992 for ( j = r - 2; j >= 0; j-- ) 993 { 994 FT_Int index; 995 ED* current; 996 997 998 /* Forward pass of rows (left -> right). Leave the first */ 999 /* column, which gets covered in the backward pass. */ 1000 for ( i = 1; i < w - 1; i++ ) 1001 { 1002 index = j * w + i; 1003 current = dm + index; 1004 1005 /* left-up */ 1006 compare_neighbor( current, -1, 1, w ); 1007 /* up */ 1008 compare_neighbor( current, 0, 1, w ); 1009 /* up-right */ 1010 compare_neighbor( current, 1, 1, w ); 1011 /* left */ 1012 compare_neighbor( current, -1, 0, w ); 1013 } 1014 1015 /* Backward pass of rows (right -> left). Leave the last */ 1016 /* column, which was already covered in the forward pass. */ 1017 for ( i = w - 2; i >= 0; i-- ) 1018 { 1019 index = j * w + i; 1020 current = dm + index; 1021 1022 /* right */ 1023 compare_neighbor( current, 1, 0, w ); 1024 } 1025 } 1026 } 1027 1028 1029 /************************************************************************** 1030 * 1031 * @Function: 1032 * edt8 1033 * 1034 * @Description: 1035 * Compute the distance map of the a bitmap. Execute both first and 1036 * second pass of the 8SED algorithm. 1037 * 1038 * @InOut: 1039 * worker:: 1040 * Contains all the relevant parameters. 1041 * 1042 * @Return: 1043 * FreeType error, 0 means success. 1044 * 1045 */ 1046 static FT_Error edt8(BSDF_Worker * worker)1047 edt8( BSDF_Worker* worker ) 1048 { 1049 FT_Error error = FT_Err_Ok; 1050 1051 1052 if ( !worker || !worker->distance_map ) 1053 { 1054 error = FT_THROW( Invalid_Argument ); 1055 goto Exit; 1056 } 1057 1058 /* first scan of the image */ 1059 first_pass( worker ); 1060 1061 /* second scan of the image */ 1062 second_pass( worker ); 1063 1064 Exit: 1065 return error; 1066 } 1067 1068 1069 /************************************************************************** 1070 * 1071 * @Function: 1072 * finalize_sdf 1073 * 1074 * @Description: 1075 * Copy the SDF data from `worker->distance_map` to the `target` bitmap. 1076 * Also transform the data to output format, (which is 6.10 fixed-point 1077 * format at the moment). 1078 * 1079 * @Input: 1080 * worker :: 1081 * Contains source distance map and other SDF data. 1082 * 1083 * @Output: 1084 * target :: 1085 * Target bitmap to which the SDF data is copied to. 1086 * 1087 * @Return: 1088 * FreeType error, 0 means success. 1089 * 1090 */ 1091 static FT_Error finalize_sdf(BSDF_Worker * worker,const FT_Bitmap * target)1092 finalize_sdf( BSDF_Worker* worker, 1093 const FT_Bitmap* target ) 1094 { 1095 FT_Error error = FT_Err_Ok; 1096 1097 FT_Int w, r; 1098 FT_Int i, j; 1099 1100 FT_SDFFormat* t_buffer; 1101 FT_16D16 spread; 1102 1103 1104 if ( !worker || !target ) 1105 { 1106 error = FT_THROW( Invalid_Argument ); 1107 goto Exit; 1108 } 1109 1110 w = (int)target->width; 1111 r = (int)target->rows; 1112 t_buffer = (FT_SDFFormat*)target->buffer; 1113 1114 if ( w != worker->width || 1115 r != worker->rows ) 1116 { 1117 error = FT_THROW( Invalid_Argument ); 1118 goto Exit; 1119 } 1120 1121 #if USE_SQUARED_DISTANCES 1122 spread = FT_INT_16D16( worker->params.spread * 1123 worker->params.spread ); 1124 #else 1125 spread = FT_INT_16D16( worker->params.spread ); 1126 #endif 1127 1128 for ( j = 0; j < r; j++ ) 1129 { 1130 for ( i = 0; i < w; i++ ) 1131 { 1132 FT_Int index; 1133 FT_16D16 dist; 1134 FT_SDFFormat final_dist; 1135 FT_Char sign; 1136 1137 1138 index = j * w + i; 1139 dist = worker->distance_map[index].dist; 1140 1141 if ( dist < 0 || dist > spread ) 1142 dist = spread; 1143 1144 #if USE_SQUARED_DISTANCES 1145 dist = square_root( dist ); 1146 #endif 1147 1148 /* We assume that if the pixel is inside a contour */ 1149 /* its coverage value must be > 127. */ 1150 sign = worker->distance_map[index].alpha < 127 ? -1 : 1; 1151 1152 /* flip the sign according to the property */ 1153 if ( worker->params.flip_sign ) 1154 sign = -sign; 1155 1156 /* concatenate from 16.16 to appropriate format */ 1157 final_dist = map_fixed_to_sdf( dist * sign, spread ); 1158 1159 t_buffer[index] = final_dist; 1160 } 1161 } 1162 1163 Exit: 1164 return error; 1165 } 1166 1167 1168 /************************************************************************** 1169 * 1170 * interface functions 1171 * 1172 */ 1173 1174 /* called when adding a new module through @FT_Add_Module */ 1175 static FT_Error bsdf_raster_new(FT_Memory memory,BSDF_PRaster * araster)1176 bsdf_raster_new( FT_Memory memory, 1177 BSDF_PRaster* araster ) 1178 { 1179 FT_Error error; 1180 BSDF_PRaster raster = NULL; 1181 1182 1183 if ( !FT_NEW( raster ) ) 1184 raster->memory = memory; 1185 1186 *araster = raster; 1187 1188 return error; 1189 } 1190 1191 1192 /* unused */ 1193 static void bsdf_raster_reset(FT_Raster raster,unsigned char * pool_base,unsigned long pool_size)1194 bsdf_raster_reset( FT_Raster raster, 1195 unsigned char* pool_base, 1196 unsigned long pool_size ) 1197 { 1198 FT_UNUSED( raster ); 1199 FT_UNUSED( pool_base ); 1200 FT_UNUSED( pool_size ); 1201 } 1202 1203 1204 /* unused */ 1205 static FT_Error bsdf_raster_set_mode(FT_Raster raster,unsigned long mode,void * args)1206 bsdf_raster_set_mode( FT_Raster raster, 1207 unsigned long mode, 1208 void* args ) 1209 { 1210 FT_UNUSED( raster ); 1211 FT_UNUSED( mode ); 1212 FT_UNUSED( args ); 1213 1214 return FT_Err_Ok; 1215 } 1216 1217 1218 /* called while rendering through @FT_Render_Glyph */ 1219 static FT_Error bsdf_raster_render(FT_Raster raster,const FT_Raster_Params * params)1220 bsdf_raster_render( FT_Raster raster, 1221 const FT_Raster_Params* params ) 1222 { 1223 FT_Error error = FT_Err_Ok; 1224 FT_Memory memory = NULL; 1225 1226 const FT_Bitmap* source = NULL; 1227 const FT_Bitmap* target = NULL; 1228 1229 BSDF_TRaster* bsdf_raster = (BSDF_TRaster*)raster; 1230 BSDF_Worker worker; 1231 1232 const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params; 1233 1234 1235 worker.distance_map = NULL; 1236 1237 /* check for valid parameters */ 1238 if ( !raster || !params ) 1239 { 1240 error = FT_THROW( Invalid_Argument ); 1241 goto Exit; 1242 } 1243 1244 /* check whether the flag is set */ 1245 if ( sdf_params->root.flags != FT_RASTER_FLAG_SDF ) 1246 { 1247 error = FT_THROW( Raster_Corrupted ); 1248 goto Exit; 1249 } 1250 1251 source = (const FT_Bitmap*)sdf_params->root.source; 1252 target = (const FT_Bitmap*)sdf_params->root.target; 1253 1254 /* check source and target bitmap */ 1255 if ( !source || !target ) 1256 { 1257 error = FT_THROW( Invalid_Argument ); 1258 goto Exit; 1259 } 1260 1261 memory = bsdf_raster->memory; 1262 if ( !memory ) 1263 { 1264 FT_TRACE0(( "bsdf_raster_render: Raster not set up properly,\n" )); 1265 FT_TRACE0(( " unable to find memory handle.\n" )); 1266 1267 error = FT_THROW( Invalid_Handle ); 1268 goto Exit; 1269 } 1270 1271 /* check whether spread is set properly */ 1272 if ( sdf_params->spread > MAX_SPREAD || 1273 sdf_params->spread < MIN_SPREAD ) 1274 { 1275 FT_TRACE0(( "bsdf_raster_render:" 1276 " The `spread' field of `SDF_Raster_Params'\n" )); 1277 FT_TRACE0(( " " 1278 " is invalid; the value of this field must be\n" )); 1279 FT_TRACE0(( " " 1280 " within [%d, %d].\n", 1281 MIN_SPREAD, MAX_SPREAD )); 1282 FT_TRACE0(( " " 1283 " Also, you must pass `SDF_Raster_Params'\n" )); 1284 FT_TRACE0(( " " 1285 " instead of the default `FT_Raster_Params'\n" )); 1286 FT_TRACE0(( " " 1287 " while calling this function and set the fields\n" )); 1288 FT_TRACE0(( " " 1289 " accordingly.\n" )); 1290 1291 error = FT_THROW( Invalid_Argument ); 1292 goto Exit; 1293 } 1294 1295 /* set up the worker */ 1296 1297 /* allocate the distance map */ 1298 if ( FT_QALLOC_MULT( worker.distance_map, target->rows, 1299 target->width * sizeof ( *worker.distance_map ) ) ) 1300 goto Exit; 1301 1302 worker.width = (int)target->width; 1303 worker.rows = (int)target->rows; 1304 worker.params = *sdf_params; 1305 1306 FT_CALL( bsdf_init_distance_map( source, &worker ) ); 1307 FT_CALL( bsdf_approximate_edge( &worker ) ); 1308 FT_CALL( edt8( &worker ) ); 1309 FT_CALL( finalize_sdf( &worker, target ) ); 1310 1311 FT_TRACE0(( "bsdf_raster_render: Total memory used = %ld\n", 1312 worker.width * worker.rows * 1313 (long)sizeof ( *worker.distance_map ) )); 1314 1315 Exit: 1316 if ( worker.distance_map ) 1317 FT_FREE( worker.distance_map ); 1318 1319 return error; 1320 } 1321 1322 1323 /* called while deleting `FT_Library` only if the module is added */ 1324 static void bsdf_raster_done(FT_Raster raster)1325 bsdf_raster_done( FT_Raster raster ) 1326 { 1327 FT_Memory memory = (FT_Memory)((BSDF_TRaster*)raster)->memory; 1328 1329 1330 FT_FREE( raster ); 1331 } 1332 1333 1334 FT_DEFINE_RASTER_FUNCS( 1335 ft_bitmap_sdf_raster, 1336 1337 FT_GLYPH_FORMAT_BITMAP, 1338 1339 (FT_Raster_New_Func) bsdf_raster_new, /* raster_new */ 1340 (FT_Raster_Reset_Func) bsdf_raster_reset, /* raster_reset */ 1341 (FT_Raster_Set_Mode_Func)bsdf_raster_set_mode, /* raster_set_mode */ 1342 (FT_Raster_Render_Func) bsdf_raster_render, /* raster_render */ 1343 (FT_Raster_Done_Func) bsdf_raster_done /* raster_done */ 1344 ) 1345 1346 1347 /* END */ 1348