ftbsdf.c (38804B)
1 /**************************************************************************** 2 * 3 * ftbsdf.c 4 * 5 * Signed Distance Field support for bitmap fonts (body only). 6 * 7 * Copyright (C) 2020-2025 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 `prox` parameter. Can be squared or absolute 181 * depending on the `USE_SQUARED_DISTANCES` macro defined in file 182 * `ftsdfcommon.h`. 183 * 184 * prox :: 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 prox; 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 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 calculated. 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 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 makes 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 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].prox = compute_edge_distance( ed + index, 599 i, j, 600 worker->width, 601 worker->rows ); 602 ed[index].dist = VECTOR_LENGTH_16D16( ed[index].prox ); 603 } 604 else 605 { 606 /* for non-edge pixels assign far away distances */ 607 ed[index].dist = 400 * ONE; 608 ed[index].prox.x = 200 * ONE; 609 ed[index].prox.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 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 } 761 } 762 break; 763 764 case FT_PIXEL_MODE_GRAY: 765 { 766 FT_Int t_width = worker->width; 767 FT_Int t_rows = worker->rows; 768 FT_Int s_width = (int)source->width; 769 FT_Int s_rows = (int)source->rows; 770 771 772 /* loop over all pixels and assign pixel values from source */ 773 for ( t_j = 0; t_j < t_rows; t_j++ ) 774 { 775 for ( t_i = 0; t_i < t_width; t_i++ ) 776 { 777 FT_Int t_index = t_j * t_width + t_i; 778 FT_Int s_index; 779 780 781 t[t_index] = zero_ed; 782 783 s_i = t_i - x_diff; 784 s_j = t_j - y_diff; 785 786 /* Assign 0 to padding similar to */ 787 /* the source bitmap. */ 788 if ( s_i < 0 || s_i >= s_width || 789 s_j < 0 || s_j >= s_rows ) 790 continue; 791 792 if ( worker->params.flip_y ) 793 s_index = ( s_rows - s_j - 1 ) * s_width + s_i; 794 else 795 s_index = s_j * s_width + s_i; 796 797 /* simply copy the alpha values */ 798 t[t_index].alpha = s[s_index]; 799 } 800 } 801 } 802 break; 803 804 default: 805 FT_ERROR(( "bsdf_copy_source_to_target:" 806 " unsopported pixel mode of source bitmap\n" )); 807 808 error = FT_THROW( Unimplemented_Feature ); 809 break; 810 } 811 812 Exit: 813 return error; 814 } 815 816 817 /************************************************************************** 818 * 819 * @Function: 820 * compare_neighbor 821 * 822 * @Description: 823 * Compare neighbor pixel (which is defined by the offset) and update 824 * `current` distance if the new distance is shorter than the original. 825 * 826 * @Input: 827 * x_offset :: 828 * X offset of the neighbor to be checked. The offset is relative to 829 * the `current`. 830 * 831 * y_offset :: 832 * Y offset of the neighbor to be checked. The offset is relative to 833 * the `current`. 834 * 835 * width :: 836 * Width of the `current` array. 837 * 838 * @InOut: 839 * current :: 840 * Pointer into array of distances. This parameter must point to the 841 * position whose neighbor is to be checked. The array is treated as 842 * a two-dimensional array. 843 * 844 */ 845 static void 846 compare_neighbor( ED* current, 847 FT_Int x_offset, 848 FT_Int y_offset, 849 FT_Int width ) 850 { 851 #if USE_SQUARED_DISTANCES 852 FT_16D16 edge_threshold = ONE / 4; 853 #else 854 FT_16D16 edge_threshold = ONE / 2; 855 #endif 856 ED* to_check; 857 FT_16D16 dist; 858 FT_16D16_Vec dist_vec; 859 860 861 /* 862 * Skip neighbor comparison if the distance is less than or equal to 0.5. 863 * When using squared distances, compare to 0.25 (= 0.5^2) instead. 864 */ 865 if ( current->dist <= edge_threshold ) 866 return; 867 868 to_check = current + ( y_offset * width ) + x_offset; 869 870 /* 871 * While checking for the nearest point we first approximate the 872 * distance of `current` by adding the deviation (which is sqrt(2) at 873 * most). Only if the new value is less than the current value we 874 * calculate the actual distances using `FT_Vector_Length`. This last 875 * step can be omitted by using squared distances. 876 */ 877 878 /* 879 * Approximate the distance. We subtract 1 to avoid precision errors, 880 * which could happen because the two directions can be opposite. 881 */ 882 dist = to_check->dist - ONE; 883 884 if ( dist < current->dist ) 885 { 886 dist_vec = to_check->prox; 887 888 dist_vec.x += x_offset * ONE; 889 dist_vec.y += y_offset * ONE; 890 dist = VECTOR_LENGTH_16D16( dist_vec ); 891 892 if ( dist < current->dist ) 893 { 894 current->dist = dist; 895 current->prox = dist_vec; 896 } 897 } 898 } 899 900 901 /************************************************************************** 902 * 903 * @Function: 904 * first_pass 905 * 906 * @Description: 907 * First pass of the 8SED algorithm. Loop over the bitmap from top to 908 * bottom and scan each row left to right, updating the distances in 909 * `worker->distance_map`. 910 * 911 * @InOut: 912 * worker:: 913 * Contains all the relevant parameters. 914 * 915 */ 916 static void 917 first_pass( BSDF_Worker* worker ) 918 { 919 FT_Int i, j; /* iterators */ 920 FT_Int w, r; /* width, rows */ 921 ED* dm; /* distance map */ 922 923 924 dm = worker->distance_map; 925 w = worker->width; 926 r = worker->rows; 927 928 /* Start scanning from top to bottom and sweep each */ 929 /* row back and forth comparing the distances of the */ 930 /* neighborhood. Leave the first row as it has no top */ 931 /* neighbor; it will be covered in the second scan of */ 932 /* the image (from bottom to top). */ 933 for ( j = 1; j < r; j++ ) 934 { 935 FT_Int index; 936 ED* current; 937 938 939 /* Forward pass of rows (left -> right). Leave the first */ 940 /* column, which gets covered in the backward pass. */ 941 for ( i = 1; i < w - 1; i++ ) 942 { 943 index = j * w + i; 944 current = dm + index; 945 946 /* left-up */ 947 compare_neighbor( current, -1, -1, w ); 948 /* up */ 949 compare_neighbor( current, 0, -1, w ); 950 /* up-right */ 951 compare_neighbor( current, 1, -1, w ); 952 /* left */ 953 compare_neighbor( current, -1, 0, w ); 954 } 955 956 /* Backward pass of rows (right -> left). Leave the last */ 957 /* column, which was already covered in the forward pass. */ 958 for ( i = w - 2; i >= 0; i-- ) 959 { 960 index = j * w + i; 961 current = dm + index; 962 963 /* right */ 964 compare_neighbor( current, 1, 0, w ); 965 } 966 } 967 } 968 969 970 /************************************************************************** 971 * 972 * @Function: 973 * second_pass 974 * 975 * @Description: 976 * Second pass of the 8SED algorithm. Loop over the bitmap from bottom 977 * to top and scan each row left to right, updating the distances in 978 * `worker->distance_map`. 979 * 980 * @InOut: 981 * worker:: 982 * Contains all the relevant parameters. 983 * 984 */ 985 static void 986 second_pass( BSDF_Worker* worker ) 987 { 988 FT_Int i, j; /* iterators */ 989 FT_Int w, r; /* width, rows */ 990 ED* dm; /* distance map */ 991 992 993 dm = worker->distance_map; 994 w = worker->width; 995 r = worker->rows; 996 997 /* Start scanning from bottom to top and sweep each */ 998 /* row back and forth comparing the distances of the */ 999 /* neighborhood. Leave the last row as it has no down */ 1000 /* neighbor; it is already covered in the first scan */ 1001 /* of the image (from top to bottom). */ 1002 for ( j = r - 2; j >= 0; j-- ) 1003 { 1004 FT_Int index; 1005 ED* current; 1006 1007 1008 /* Forward pass of rows (left -> right). Leave the first */ 1009 /* column, which gets covered in the backward pass. */ 1010 for ( i = 1; i < w - 1; i++ ) 1011 { 1012 index = j * w + i; 1013 current = dm + index; 1014 1015 /* left-up */ 1016 compare_neighbor( current, -1, 1, w ); 1017 /* up */ 1018 compare_neighbor( current, 0, 1, w ); 1019 /* up-right */ 1020 compare_neighbor( current, 1, 1, w ); 1021 /* left */ 1022 compare_neighbor( current, -1, 0, w ); 1023 } 1024 1025 /* Backward pass of rows (right -> left). Leave the last */ 1026 /* column, which was already covered in the forward pass. */ 1027 for ( i = w - 2; i >= 0; i-- ) 1028 { 1029 index = j * w + i; 1030 current = dm + index; 1031 1032 /* right */ 1033 compare_neighbor( current, 1, 0, w ); 1034 } 1035 } 1036 } 1037 1038 1039 /************************************************************************** 1040 * 1041 * @Function: 1042 * edt8 1043 * 1044 * @Description: 1045 * Compute the distance map of the a bitmap. Execute both first and 1046 * second pass of the 8SED algorithm. 1047 * 1048 * @InOut: 1049 * worker:: 1050 * Contains all the relevant parameters. 1051 * 1052 * @Return: 1053 * FreeType error, 0 means success. 1054 * 1055 */ 1056 static FT_Error 1057 edt8( BSDF_Worker* worker ) 1058 { 1059 FT_Error error = FT_Err_Ok; 1060 1061 1062 if ( !worker || !worker->distance_map ) 1063 { 1064 error = FT_THROW( Invalid_Argument ); 1065 goto Exit; 1066 } 1067 1068 /* first scan of the image */ 1069 first_pass( worker ); 1070 1071 /* second scan of the image */ 1072 second_pass( worker ); 1073 1074 Exit: 1075 return error; 1076 } 1077 1078 1079 /************************************************************************** 1080 * 1081 * @Function: 1082 * finalize_sdf 1083 * 1084 * @Description: 1085 * Copy the SDF data from `worker->distance_map` to the `target` bitmap. 1086 * Also transform the data to output format, (which is 6.10 fixed-point 1087 * format at the moment). 1088 * 1089 * @Input: 1090 * worker :: 1091 * Contains source distance map and other SDF data. 1092 * 1093 * @Output: 1094 * target :: 1095 * Target bitmap to which the SDF data is copied to. 1096 * 1097 * @Return: 1098 * FreeType error, 0 means success. 1099 * 1100 */ 1101 static FT_Error 1102 finalize_sdf( BSDF_Worker* worker, 1103 const FT_Bitmap* target ) 1104 { 1105 FT_Error error = FT_Err_Ok; 1106 1107 FT_Int w, r; 1108 FT_Int i, j; 1109 1110 FT_SDFFormat* t_buffer; 1111 FT_16D16 sp_sq, spread; 1112 1113 1114 if ( !worker || !target ) 1115 { 1116 error = FT_THROW( Invalid_Argument ); 1117 goto Exit; 1118 } 1119 1120 w = (int)target->width; 1121 r = (int)target->rows; 1122 t_buffer = (FT_SDFFormat*)target->buffer; 1123 1124 if ( w != worker->width || 1125 r != worker->rows ) 1126 { 1127 error = FT_THROW( Invalid_Argument ); 1128 goto Exit; 1129 } 1130 1131 spread = (FT_16D16)FT_INT_16D16( worker->params.spread ); 1132 1133 #if USE_SQUARED_DISTANCES 1134 sp_sq = (FT_16D16)FT_INT_16D16( worker->params.spread * 1135 worker->params.spread ); 1136 #else 1137 sp_sq = (FT_16D16)FT_INT_16D16( worker->params.spread ); 1138 #endif 1139 1140 for ( j = 0; j < r; j++ ) 1141 { 1142 for ( i = 0; i < w; i++ ) 1143 { 1144 FT_Int index; 1145 FT_16D16 dist; 1146 FT_SDFFormat final_dist; 1147 FT_Char sign; 1148 1149 1150 index = j * w + i; 1151 dist = worker->distance_map[index].dist; 1152 1153 if ( dist < 0 || dist > sp_sq ) 1154 dist = sp_sq; 1155 1156 #if USE_SQUARED_DISTANCES 1157 dist = square_root( dist ); 1158 #endif 1159 1160 /* We assume that if the pixel is inside a contour */ 1161 /* its coverage value must be > 127. */ 1162 sign = worker->distance_map[index].alpha < 127 ? -1 : 1; 1163 1164 /* flip the sign according to the property */ 1165 if ( worker->params.flip_sign ) 1166 sign = -sign; 1167 1168 /* concatenate from 16.16 to appropriate format */ 1169 final_dist = map_fixed_to_sdf( dist * sign, spread ); 1170 1171 t_buffer[index] = final_dist; 1172 } 1173 } 1174 1175 Exit: 1176 return error; 1177 } 1178 1179 1180 /************************************************************************** 1181 * 1182 * interface functions 1183 * 1184 */ 1185 1186 /* called when adding a new module through @FT_Add_Module */ 1187 static FT_Error 1188 bsdf_raster_new( void* memory_, /* FT_Memory */ 1189 FT_Raster* araster_ ) /* BSDF_PRaster* */ 1190 { 1191 FT_Memory memory = (FT_Memory)memory_; 1192 BSDF_PRaster* araster = (BSDF_PRaster*)araster_; 1193 1194 FT_Error error; 1195 BSDF_PRaster raster = NULL; 1196 1197 1198 if ( !FT_NEW( raster ) ) 1199 raster->memory = memory; 1200 1201 *araster = raster; 1202 1203 return error; 1204 } 1205 1206 1207 /* unused */ 1208 static void 1209 bsdf_raster_reset( FT_Raster raster, 1210 unsigned char* pool_base, 1211 unsigned long pool_size ) 1212 { 1213 FT_UNUSED( raster ); 1214 FT_UNUSED( pool_base ); 1215 FT_UNUSED( pool_size ); 1216 } 1217 1218 1219 /* unused */ 1220 static FT_Error 1221 bsdf_raster_set_mode( FT_Raster raster, 1222 unsigned long mode, 1223 void* args ) 1224 { 1225 FT_UNUSED( raster ); 1226 FT_UNUSED( mode ); 1227 FT_UNUSED( args ); 1228 1229 return FT_Err_Ok; 1230 } 1231 1232 1233 /* called while rendering through @FT_Render_Glyph */ 1234 static FT_Error 1235 bsdf_raster_render( FT_Raster raster, 1236 const FT_Raster_Params* params ) 1237 { 1238 FT_Error error = FT_Err_Ok; 1239 FT_Memory memory = NULL; 1240 1241 const FT_Bitmap* source = NULL; 1242 const FT_Bitmap* target = NULL; 1243 1244 BSDF_TRaster* bsdf_raster = (BSDF_TRaster*)raster; 1245 BSDF_Worker worker; 1246 1247 const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params; 1248 1249 1250 worker.distance_map = NULL; 1251 1252 /* check for valid parameters */ 1253 if ( !raster || !params ) 1254 { 1255 error = FT_THROW( Invalid_Argument ); 1256 goto Exit; 1257 } 1258 1259 /* check whether the flag is set */ 1260 if ( sdf_params->root.flags != FT_RASTER_FLAG_SDF ) 1261 { 1262 error = FT_THROW( Raster_Corrupted ); 1263 goto Exit; 1264 } 1265 1266 source = (const FT_Bitmap*)sdf_params->root.source; 1267 target = (const FT_Bitmap*)sdf_params->root.target; 1268 1269 /* check source and target bitmap */ 1270 if ( !source || !target ) 1271 { 1272 error = FT_THROW( Invalid_Argument ); 1273 goto Exit; 1274 } 1275 1276 memory = bsdf_raster->memory; 1277 if ( !memory ) 1278 { 1279 FT_TRACE0(( "bsdf_raster_render: Raster not set up properly,\n" )); 1280 FT_TRACE0(( " unable to find memory handle.\n" )); 1281 1282 error = FT_THROW( Invalid_Handle ); 1283 goto Exit; 1284 } 1285 1286 /* check whether spread is set properly */ 1287 if ( sdf_params->spread > MAX_SPREAD || 1288 sdf_params->spread < MIN_SPREAD ) 1289 { 1290 FT_TRACE0(( "bsdf_raster_render:" 1291 " The `spread' field of `SDF_Raster_Params'\n" )); 1292 FT_TRACE0(( " " 1293 " is invalid; the value of this field must be\n" )); 1294 FT_TRACE0(( " " 1295 " within [%d, %d].\n", 1296 MIN_SPREAD, MAX_SPREAD )); 1297 FT_TRACE0(( " " 1298 " Also, you must pass `SDF_Raster_Params'\n" )); 1299 FT_TRACE0(( " " 1300 " instead of the default `FT_Raster_Params'\n" )); 1301 FT_TRACE0(( " " 1302 " while calling this function and set the fields\n" )); 1303 FT_TRACE0(( " " 1304 " accordingly.\n" )); 1305 1306 error = FT_THROW( Invalid_Argument ); 1307 goto Exit; 1308 } 1309 1310 /* set up the worker */ 1311 1312 /* allocate the distance map */ 1313 if ( FT_QALLOC_MULT( worker.distance_map, target->rows, 1314 target->width * sizeof ( *worker.distance_map ) ) ) 1315 goto Exit; 1316 1317 worker.width = (int)target->width; 1318 worker.rows = (int)target->rows; 1319 worker.params = *sdf_params; 1320 1321 FT_CALL( bsdf_init_distance_map( source, &worker ) ); 1322 FT_CALL( bsdf_approximate_edge( &worker ) ); 1323 FT_CALL( edt8( &worker ) ); 1324 FT_CALL( finalize_sdf( &worker, target ) ); 1325 1326 FT_TRACE0(( "bsdf_raster_render: Total memory used = %ld\n", 1327 worker.width * worker.rows * 1328 (long)sizeof ( *worker.distance_map ) )); 1329 1330 Exit: 1331 if ( worker.distance_map ) 1332 FT_FREE( worker.distance_map ); 1333 1334 return error; 1335 } 1336 1337 1338 /* called while deleting `FT_Library` only if the module is added */ 1339 static void 1340 bsdf_raster_done( FT_Raster raster ) 1341 { 1342 FT_Memory memory = (FT_Memory)((BSDF_TRaster*)raster)->memory; 1343 1344 1345 FT_FREE( raster ); 1346 } 1347 1348 1349 FT_DEFINE_RASTER_FUNCS( 1350 ft_bitmap_sdf_raster, 1351 1352 FT_GLYPH_FORMAT_BITMAP, 1353 1354 (FT_Raster_New_Func) bsdf_raster_new, /* raster_new */ 1355 (FT_Raster_Reset_Func) bsdf_raster_reset, /* raster_reset */ 1356 (FT_Raster_Set_Mode_Func)bsdf_raster_set_mode, /* raster_set_mode */ 1357 (FT_Raster_Render_Func) bsdf_raster_render, /* raster_render */ 1358 (FT_Raster_Done_Func) bsdf_raster_done /* raster_done */ 1359 ) 1360 1361 1362 /* END */