1 /**************************************************************************** 2 * 3 * ftbsdf.c 4 * 5 * Signed Distance Field support for bitmap fonts (body only). 6 * 7 * Copyright (C) 2020-2023 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 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].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 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 } 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 compare_neighbor(ED * current,FT_Int x_offset,FT_Int y_offset,FT_Int width)846 compare_neighbor( ED* current, 847 FT_Int x_offset, 848 FT_Int y_offset, 849 FT_Int width ) 850 { 851 ED* to_check; 852 FT_16D16 dist; 853 FT_16D16_Vec dist_vec; 854 855 856 to_check = current + ( y_offset * width ) + x_offset; 857 858 /* 859 * While checking for the nearest point we first approximate the 860 * distance of `current` by adding the deviation (which is sqrt(2) at 861 * most). Only if the new value is less than the current value we 862 * calculate the actual distances using `FT_Vector_Length`. This last 863 * step can be omitted by using squared distances. 864 */ 865 866 /* 867 * Approximate the distance. We subtract 1 to avoid precision errors, 868 * which could happen because the two directions can be opposite. 869 */ 870 dist = to_check->dist - ONE; 871 872 if ( dist < current->dist ) 873 { 874 dist_vec = to_check->prox; 875 876 dist_vec.x += x_offset * ONE; 877 dist_vec.y += y_offset * ONE; 878 dist = VECTOR_LENGTH_16D16( dist_vec ); 879 880 if ( dist < current->dist ) 881 { 882 current->dist = dist; 883 current->prox = dist_vec; 884 } 885 } 886 } 887 888 889 /************************************************************************** 890 * 891 * @Function: 892 * first_pass 893 * 894 * @Description: 895 * First pass of the 8SED algorithm. Loop over the bitmap from top to 896 * bottom and scan each row left to right, updating the distances in 897 * `worker->distance_map`. 898 * 899 * @InOut: 900 * worker:: 901 * Contains all the relevant parameters. 902 * 903 */ 904 static void first_pass(BSDF_Worker * worker)905 first_pass( BSDF_Worker* worker ) 906 { 907 FT_Int i, j; /* iterators */ 908 FT_Int w, r; /* width, rows */ 909 ED* dm; /* distance map */ 910 911 912 dm = worker->distance_map; 913 w = worker->width; 914 r = worker->rows; 915 916 /* Start scanning from top to bottom and sweep each */ 917 /* row back and forth comparing the distances of the */ 918 /* neighborhood. Leave the first row as it has no top */ 919 /* neighbor; it will be covered in the second scan of */ 920 /* the image (from bottom to top). */ 921 for ( j = 1; j < r; j++ ) 922 { 923 FT_Int index; 924 ED* current; 925 926 927 /* Forward pass of rows (left -> right). Leave the first */ 928 /* column, which gets covered in the backward pass. */ 929 for ( i = 1; i < w - 1; i++ ) 930 { 931 index = j * w + i; 932 current = dm + index; 933 934 /* left-up */ 935 compare_neighbor( current, -1, -1, w ); 936 /* up */ 937 compare_neighbor( current, 0, -1, w ); 938 /* up-right */ 939 compare_neighbor( current, 1, -1, w ); 940 /* left */ 941 compare_neighbor( current, -1, 0, w ); 942 } 943 944 /* Backward pass of rows (right -> left). Leave the last */ 945 /* column, which was already covered in the forward pass. */ 946 for ( i = w - 2; i >= 0; i-- ) 947 { 948 index = j * w + i; 949 current = dm + index; 950 951 /* right */ 952 compare_neighbor( current, 1, 0, w ); 953 } 954 } 955 } 956 957 958 /************************************************************************** 959 * 960 * @Function: 961 * second_pass 962 * 963 * @Description: 964 * Second pass of the 8SED algorithm. Loop over the bitmap from bottom 965 * to top and scan each row left to right, updating the distances in 966 * `worker->distance_map`. 967 * 968 * @InOut: 969 * worker:: 970 * Contains all the relevant parameters. 971 * 972 */ 973 static void second_pass(BSDF_Worker * worker)974 second_pass( BSDF_Worker* worker ) 975 { 976 FT_Int i, j; /* iterators */ 977 FT_Int w, r; /* width, rows */ 978 ED* dm; /* distance map */ 979 980 981 dm = worker->distance_map; 982 w = worker->width; 983 r = worker->rows; 984 985 /* Start scanning from bottom to top and sweep each */ 986 /* row back and forth comparing the distances of the */ 987 /* neighborhood. Leave the last row as it has no down */ 988 /* neighbor; it is already covered in the first scan */ 989 /* of the image (from top to bottom). */ 990 for ( j = r - 2; j >= 0; j-- ) 991 { 992 FT_Int index; 993 ED* current; 994 995 996 /* Forward pass of rows (left -> right). Leave the first */ 997 /* column, which gets covered in the backward pass. */ 998 for ( i = 1; i < w - 1; i++ ) 999 { 1000 index = j * w + i; 1001 current = dm + index; 1002 1003 /* left-up */ 1004 compare_neighbor( current, -1, 1, w ); 1005 /* up */ 1006 compare_neighbor( current, 0, 1, w ); 1007 /* up-right */ 1008 compare_neighbor( current, 1, 1, w ); 1009 /* left */ 1010 compare_neighbor( current, -1, 0, w ); 1011 } 1012 1013 /* Backward pass of rows (right -> left). Leave the last */ 1014 /* column, which was already covered in the forward pass. */ 1015 for ( i = w - 2; i >= 0; i-- ) 1016 { 1017 index = j * w + i; 1018 current = dm + index; 1019 1020 /* right */ 1021 compare_neighbor( current, 1, 0, w ); 1022 } 1023 } 1024 } 1025 1026 1027 /************************************************************************** 1028 * 1029 * @Function: 1030 * edt8 1031 * 1032 * @Description: 1033 * Compute the distance map of the a bitmap. Execute both first and 1034 * second pass of the 8SED algorithm. 1035 * 1036 * @InOut: 1037 * worker:: 1038 * Contains all the relevant parameters. 1039 * 1040 * @Return: 1041 * FreeType error, 0 means success. 1042 * 1043 */ 1044 static FT_Error edt8(BSDF_Worker * worker)1045 edt8( BSDF_Worker* worker ) 1046 { 1047 FT_Error error = FT_Err_Ok; 1048 1049 1050 if ( !worker || !worker->distance_map ) 1051 { 1052 error = FT_THROW( Invalid_Argument ); 1053 goto Exit; 1054 } 1055 1056 /* first scan of the image */ 1057 first_pass( worker ); 1058 1059 /* second scan of the image */ 1060 second_pass( worker ); 1061 1062 Exit: 1063 return error; 1064 } 1065 1066 1067 /************************************************************************** 1068 * 1069 * @Function: 1070 * finalize_sdf 1071 * 1072 * @Description: 1073 * Copy the SDF data from `worker->distance_map` to the `target` bitmap. 1074 * Also transform the data to output format, (which is 6.10 fixed-point 1075 * format at the moment). 1076 * 1077 * @Input: 1078 * worker :: 1079 * Contains source distance map and other SDF data. 1080 * 1081 * @Output: 1082 * target :: 1083 * Target bitmap to which the SDF data is copied to. 1084 * 1085 * @Return: 1086 * FreeType error, 0 means success. 1087 * 1088 */ 1089 static FT_Error finalize_sdf(BSDF_Worker * worker,const FT_Bitmap * target)1090 finalize_sdf( BSDF_Worker* worker, 1091 const FT_Bitmap* target ) 1092 { 1093 FT_Error error = FT_Err_Ok; 1094 1095 FT_Int w, r; 1096 FT_Int i, j; 1097 1098 FT_SDFFormat* t_buffer; 1099 FT_16D16 sp_sq, spread; 1100 1101 1102 if ( !worker || !target ) 1103 { 1104 error = FT_THROW( Invalid_Argument ); 1105 goto Exit; 1106 } 1107 1108 w = (int)target->width; 1109 r = (int)target->rows; 1110 t_buffer = (FT_SDFFormat*)target->buffer; 1111 1112 if ( w != worker->width || 1113 r != worker->rows ) 1114 { 1115 error = FT_THROW( Invalid_Argument ); 1116 goto Exit; 1117 } 1118 1119 spread = (FT_16D16)FT_INT_16D16( worker->params.spread ); 1120 1121 #if USE_SQUARED_DISTANCES 1122 sp_sq = (FT_16D16)FT_INT_16D16( worker->params.spread * 1123 worker->params.spread ); 1124 #else 1125 sp_sq = (FT_16D16)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 > sp_sq ) 1142 dist = sp_sq; 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(void * memory_,FT_Raster * araster_)1176 bsdf_raster_new( void* memory_, /* FT_Memory */ 1177 FT_Raster* araster_ ) /* BSDF_PRaster* */ 1178 { 1179 FT_Memory memory = (FT_Memory)memory_; 1180 BSDF_PRaster* araster = (BSDF_PRaster*)araster_; 1181 1182 FT_Error error; 1183 BSDF_PRaster raster = NULL; 1184 1185 1186 if ( !FT_NEW( raster ) ) 1187 raster->memory = memory; 1188 1189 *araster = raster; 1190 1191 return error; 1192 } 1193 1194 1195 /* unused */ 1196 static void bsdf_raster_reset(FT_Raster raster,unsigned char * pool_base,unsigned long pool_size)1197 bsdf_raster_reset( FT_Raster raster, 1198 unsigned char* pool_base, 1199 unsigned long pool_size ) 1200 { 1201 FT_UNUSED( raster ); 1202 FT_UNUSED( pool_base ); 1203 FT_UNUSED( pool_size ); 1204 } 1205 1206 1207 /* unused */ 1208 static FT_Error bsdf_raster_set_mode(FT_Raster raster,unsigned long mode,void * args)1209 bsdf_raster_set_mode( FT_Raster raster, 1210 unsigned long mode, 1211 void* args ) 1212 { 1213 FT_UNUSED( raster ); 1214 FT_UNUSED( mode ); 1215 FT_UNUSED( args ); 1216 1217 return FT_Err_Ok; 1218 } 1219 1220 1221 /* called while rendering through @FT_Render_Glyph */ 1222 static FT_Error bsdf_raster_render(FT_Raster raster,const FT_Raster_Params * params)1223 bsdf_raster_render( FT_Raster raster, 1224 const FT_Raster_Params* params ) 1225 { 1226 FT_Error error = FT_Err_Ok; 1227 FT_Memory memory = NULL; 1228 1229 const FT_Bitmap* source = NULL; 1230 const FT_Bitmap* target = NULL; 1231 1232 BSDF_TRaster* bsdf_raster = (BSDF_TRaster*)raster; 1233 BSDF_Worker worker; 1234 1235 const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params; 1236 1237 1238 worker.distance_map = NULL; 1239 1240 /* check for valid parameters */ 1241 if ( !raster || !params ) 1242 { 1243 error = FT_THROW( Invalid_Argument ); 1244 goto Exit; 1245 } 1246 1247 /* check whether the flag is set */ 1248 if ( sdf_params->root.flags != FT_RASTER_FLAG_SDF ) 1249 { 1250 error = FT_THROW( Raster_Corrupted ); 1251 goto Exit; 1252 } 1253 1254 source = (const FT_Bitmap*)sdf_params->root.source; 1255 target = (const FT_Bitmap*)sdf_params->root.target; 1256 1257 /* check source and target bitmap */ 1258 if ( !source || !target ) 1259 { 1260 error = FT_THROW( Invalid_Argument ); 1261 goto Exit; 1262 } 1263 1264 memory = bsdf_raster->memory; 1265 if ( !memory ) 1266 { 1267 FT_TRACE0(( "bsdf_raster_render: Raster not set up properly,\n" )); 1268 FT_TRACE0(( " unable to find memory handle.\n" )); 1269 1270 error = FT_THROW( Invalid_Handle ); 1271 goto Exit; 1272 } 1273 1274 /* check whether spread is set properly */ 1275 if ( sdf_params->spread > MAX_SPREAD || 1276 sdf_params->spread < MIN_SPREAD ) 1277 { 1278 FT_TRACE0(( "bsdf_raster_render:" 1279 " The `spread' field of `SDF_Raster_Params'\n" )); 1280 FT_TRACE0(( " " 1281 " is invalid; the value of this field must be\n" )); 1282 FT_TRACE0(( " " 1283 " within [%d, %d].\n", 1284 MIN_SPREAD, MAX_SPREAD )); 1285 FT_TRACE0(( " " 1286 " Also, you must pass `SDF_Raster_Params'\n" )); 1287 FT_TRACE0(( " " 1288 " instead of the default `FT_Raster_Params'\n" )); 1289 FT_TRACE0(( " " 1290 " while calling this function and set the fields\n" )); 1291 FT_TRACE0(( " " 1292 " accordingly.\n" )); 1293 1294 error = FT_THROW( Invalid_Argument ); 1295 goto Exit; 1296 } 1297 1298 /* set up the worker */ 1299 1300 /* allocate the distance map */ 1301 if ( FT_QALLOC_MULT( worker.distance_map, target->rows, 1302 target->width * sizeof ( *worker.distance_map ) ) ) 1303 goto Exit; 1304 1305 worker.width = (int)target->width; 1306 worker.rows = (int)target->rows; 1307 worker.params = *sdf_params; 1308 1309 FT_CALL( bsdf_init_distance_map( source, &worker ) ); 1310 FT_CALL( bsdf_approximate_edge( &worker ) ); 1311 FT_CALL( edt8( &worker ) ); 1312 FT_CALL( finalize_sdf( &worker, target ) ); 1313 1314 FT_TRACE0(( "bsdf_raster_render: Total memory used = %ld\n", 1315 worker.width * worker.rows * 1316 (long)sizeof ( *worker.distance_map ) )); 1317 1318 Exit: 1319 if ( worker.distance_map ) 1320 FT_FREE( worker.distance_map ); 1321 1322 return error; 1323 } 1324 1325 1326 /* called while deleting `FT_Library` only if the module is added */ 1327 static void bsdf_raster_done(FT_Raster raster)1328 bsdf_raster_done( FT_Raster raster ) 1329 { 1330 FT_Memory memory = (FT_Memory)((BSDF_TRaster*)raster)->memory; 1331 1332 1333 FT_FREE( raster ); 1334 } 1335 1336 1337 FT_DEFINE_RASTER_FUNCS( 1338 ft_bitmap_sdf_raster, 1339 1340 FT_GLYPH_FORMAT_BITMAP, 1341 1342 (FT_Raster_New_Func) bsdf_raster_new, /* raster_new */ 1343 (FT_Raster_Reset_Func) bsdf_raster_reset, /* raster_reset */ 1344 (FT_Raster_Set_Mode_Func)bsdf_raster_set_mode, /* raster_set_mode */ 1345 (FT_Raster_Render_Func) bsdf_raster_render, /* raster_render */ 1346 (FT_Raster_Done_Func) bsdf_raster_done /* raster_done */ 1347 ) 1348 1349 1350 /* END */ 1351