[freetype2] GSoC-2020-anuj 644a6c2: [sdf] Added brief technical overview of both the rasterizers.

[Anuj Verma]

branch: GSoC-2020-anuj
commit 644a6c24fdcc539cee5c2e669fca45cdbe89c829
Author: Anuj Verma <anujv@iitbhilai.ac.in>
Commit: Anuj Verma <anujv@iitbhilai.ac.in>

    [sdf] Added brief technical overview of both the rasterizers.
    
    * src/sdf/ftsdf.c (*): Added a technical overview of the working of the 
`sdf' rasterizer.
    
    * src/sdf/ftbsdf,c (*) : Added a technical overview of the working of the 
`bsdf'
      rasterizer.
---
 src/sdf/ftbsdf.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/sdf/ftsdf.c  | 71 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 166 insertions(+)

diff --git a/src/sdf/ftbsdf.c b/src/sdf/ftbsdf.c
index fb11b64..b31530c 100644
--- a/src/sdf/ftbsdf.c
+++ b/src/sdf/ftbsdf.c
@@ -10,6 +10,101 @@
 
   /**************************************************************************
    *
+   * A brief technical overview of how the BSDF rasterizer works.
+   * ------------------------------------------------------------
+   * 
+   * [Notes]:
+   *   * SDF stands for Signed Distance Field everywhere.
+   * 
+   *   * BSDF stands for Bitmap to Signed Distance Field rasterizer.
+   * 
+   *   * This renderer convert rasterized bitmaps to SDF. There is another
+   *     renderer `sdf' which generate SDF directly from outlines, see
+   *     `ftsdf.c' for more details on the `sdf' rasterizer.
+   * 
+   *   * The idea of generating SDF from bitmaps is taken from two research 
+   *     papers, where one is dependent on the other:
+   *     
+   *     - First paper:
+   *         Euclidean Distance Mapping, PER-ERIK DANIELSSON.
+   *         Link: http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf
+   *         From this paper we use the he eight-point sequential Euclidean
+   *         distance mapping (8SED). This is the heart of the process used
+   *         in this rasterizer.
+   *         The 8SED algorithm is the basic algorithm which generate SDF
+   *         (distance map) from binary bitmaps.
+   *         
+   *     - Second paper:
+   *         Anti-aliased Euclidean distance transform. Stefan Gustavson,
+   *         Robin Strand.
+   *         Link: http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf
+   *         The 8SED discards the pixel's alpha values which can contain
+   *         information about the actual outline of the glyph. So, this
+   *         paper takes advantage of those alpha values and approximate
+   *         outline pretty accurately.
+   * 
+   *   * The two algorithms together generate pretty accurate SDF from only
+   *     bitmaps.
+   * 
+   *   * This rasterizer will work for monochrome bitmaps but the result will
+   *     not be as accurate since we don't have any way to approximate outli-
+   *     nes from binary bitmaps.
+   * 
+   * ========================================================================
+   * 
+   *   Generating SDF from bitmap is done in several steps:
+   * 
+   *   1 - First, the only information we have is the bitmap itself. It can
+   *       be monochrome or anti-aliased. If it is anti-aliased the pixel
+   *       values are nothing but the coverage values. There coverage values
+   *       can be used to extract information about the outline of the image.
+   *       For example: If the pixel's alpha value is 0.5, then we can safely
+   *       assume that the outline pass through the center of the pixel.
+   *
+   *   2 - Now we find the edge pixels in the bitmap (see `bsdf_is_edge' for
+   *       more details about how we find edge pixels). For all edge pixels
+   *       we use the Anti-aliased Euclidean distance transform algorithm and
+   *       compute approximate edge distances (see `compute_edge_distance'
+   *       and/or the second paper about how we compute approximate edge
+   *       distances).
+   *       
+   *   3 - Now that we have computed approximate distance for edge pixels we
+   *       use the 8SED algorithm to basically sweep the entire bitmap and
+   *       compute distances for the rest of the pixels. (Since the algorithm
+   *       is pretty large it is only explained briefly in the file, the
+   *       function for which is `edt8'. To see the actual algorithm refer
+   *       to the first paper).
+   *
+   *   4 - And finally we compute the sign for each pixel. This is done in
+   *       the `finalize_sdf' function. The basic idea is that if the pixel's
+   *       original alpha/coverage value is greater than 0.5 then it is
+   *       'inside' otherwise it is 'outside'.
+   *
+   *   5 - This concludes the algorithm.
+   *
+   *   Pseudo Code:
+   *
+   *     b  = source bitmap;
+   *     t  = target bitmap;
+   *     dm = list of distances; // dimension equal to b
+   *
+   *     foreach grid_point (x, y) in b:
+   *       if ( is_edge(x, y) ):
+   *         dm = approximate_edge_distance(b, x, y);
+   *     
+   *     // do the 8SED on the distances
+   *     edt8(dm);
+   *
+   *     // determine the signs
+   *     determine_signs(dm):
+   *
+   *     // copy SDF data to the target bitmap
+   *     copy(dm to t);
+   *
+   */
+
+  /**************************************************************************
+   *
    * useful macros
    *
    */
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 6367def..1b9d33b 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -6,6 +6,77 @@
 
 #include "ftsdferrs.h"
 
+
+  /**************************************************************************
+   *
+   * A brief technical overview of how the SDF rasterizer works.
+   * -----------------------------------------------------------
+   * 
+   * [Notes]:
+   *   * SDF stands for Signed Distance Field everywhere.
+   * 
+   *   * This renderer generate SDF directly from outlines. There is another
+   *     renderer `bsdf' which convert bitmaps to SDF, see `ftbsdf.c' for
+   *     more details on the `bsdf' rasterizer.
+   * 
+   *   * The basic idea of generating the SDF is taken from Viktor Chlumsky's
+   *     research paper. Citation:
+   *     Chlumsky, Viktor. Shape Decomposition for Multi-channel Distance
+   *     Fields. Master's thesis. Czech Technical University in Prague,
+   *     Faculty of InformationTechnology, 2015.
+   *     For more information: https://github.com/Chlumsky/msdfgen
+   * 
+   * ========================================================================
+   * 
+   *   Generating SDF from outlines is pretty straightforward:
+   * 
+   *   1 - We have a set of contours which make the outline of a shape/glyph.
+   *       Each contour comprises of several edges and the edges can be of
+   *       three types i.e.
+   *   
+   *       * Line Segments
+   *       * Conic Bezier Curves
+   *       * Cubic Bezier Curves
+   * 
+   *   2 - Apart from the outlines we also have a 2D grid namely the bitmap
+   *       which is used to represent the final SDF data.
+   * 
+   *   3 - Now, in order to generate SDF, our task is to find shortest signed
+   *       distance from each grid point to the outline. The signed distance
+   *       means that if the grid point is filled by any contour then it's
+   *       sign will be positive, otherwise it will be negative. The pseudo
+   *       code is as follows:
+   *
+   *       foreach grid_point (x, y):
+   *       {
+   *         int min_dist = INT_MAX;
+   *
+   *         foreach contour in outline:
+   *           foreach edge in contour:
+   *           {
+   *             // get shortest distance from point (x, y) to the edge
+   *             d = get_min_dist(x, y, edge);
+   *             
+   *             if ( d < min_dist ) min_dist = d;
+   *           }
+   * 
+   *         bitmap[x, y] = min_dist;
+   *       }
+   * 
+   *   4 - After this the bitmap will contain information about the closest
+   *       point from each point to the outline of the shape. Of course, this
+   *       is the most straightforward way of generating SDF, in this raster-
+   *       izer we use various optimizations, to checkout how they works
+   *       see the `sdf_generate_' functions in this file.
+   *       
+   *       The optimization currently used by default is the subdivision opt-
+   *       imization, see `sdf_generate_subdivision' for more details.
+   *       
+   *       Also, to see how we compute the shortest distance from a point to
+   *       each type of edge checkout the `get_min_distance_' functions.
+   *
+   */
+
   /**************************************************************************
    *
    * for tracking memory used