src/sdf/ftbsdf.c

   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
 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
 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
 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     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
 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
 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
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
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
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
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
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
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
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 */