[freetype2] anuj-distance-field c3a5a07: [sdf] Added a basic overview of the `sdf' rasterizer.

[Anuj Verma]

branch: anuj-distance-field
commit c3a5a07839c31524112ecb26048ca9482b815a31
Author: Anuj Verma <anujv@iitbhilai.ac.in>
Commit: Anuj Verma <anujv@iitbhilai.ac.in>

    [sdf] Added a basic overview of the `sdf' rasterizer.
    
    * src/sdf/ftsdf.c: Added the citation of the original paper
      and added a overview of the process for generating SDF
      from outlines.
    
    * src/sdf/ftsdf.c (sdf_generate_subdivision): Added comment
      explaining how the optimization works.
---
 [GSoC]ChangeLog |  11 +++++++
 src/sdf/ftsdf.c | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 109 insertions(+), 2 deletions(-)

diff --git a/[GSoC]ChangeLog b/[GSoC]ChangeLog
index 2caa603..92cbe70 100644
--- a/[GSoC]ChangeLog
+++ b/[GSoC]ChangeLog
@@ -1,3 +1,14 @@
+2020-08-15  Anuj Verma  <anujv@iitbhilai.ac.in>
+
+       [sdf] Added a basic overview of the `sdf' rasterizer.
+
+       * src/sdf/ftsdf.c: Added the citation of the original paper
+         and added a overview of the process for generating SDF
+         from outlines.
+
+       * src/sdf/ftsdf.c (sdf_generate_subdivision): Added comment
+         explaining how the optimization works.
+
 2020-08-13  Anuj Verma  <anujv@iitbhilai.ac.in>
 
        [sdf] Fix gcc compiler warnings.
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 8404a9c..13242e7 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -8,6 +8,76 @@
 
   /**************************************************************************
    *
+   * 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
    *
    */
@@ -2910,8 +2980,8 @@
    *   all the directions. Anything outside the control box will naturally
    *   be more than the `spread' and shouldn't be computed.
    *   Lastly to determine the sign of unchecked pixels we do a single pass
-   *   of all the rows starting with a + sign and flipping when we come
-   *   across a - sign and continue.
+   *   of all the rows starting with a '+' sign and flipping when we come
+   *   across a '-' sign and continue.
    *   This also eliminate the chance of overflow because we only check the
    *   proximity of the curve. Therefore we can use squared distanced
    *   safely.
@@ -3152,6 +3222,32 @@
                             FT_UInt           spread,
                             const FT_Bitmap*  bitmap )
   {
+    /* Thanks to Alexei for providing the idea of this optimization. */
+    /*                                                               */
+    /* This optimiztion mode take advantage of two facts:            */
+    /*                                                               */
+    /*   - Computing shortest distance froma point to a line segment */
+    /*     is super fast.                                            */
+    /*   - We don't have to compute shortest distance for the entire */
+    /*     2D grid.                                                  */
+    /*                                                               */
+    /* This is how it works:                                         */
+    /*                                                               */
+    /*   - We split the outlines into a number of line segments.     */
+    /*                                                               */
+    /*   - For each line segment we only process the neighborhood of */
+    /*     the line segment.                                         */
+    /*                                                               */
+    /*   - Now, only for the neighborhood grid points we compute the */
+    /*     closest distance to the line.                             */
+    /*                                                               */
+    /*   - This way we do not have to check all grid points against  */
+    /*     all the edges. Instead for each line's neighborhood we    */
+    /*     only compute shortest distance for that one line only.    */
+    /*                                                               */
+    /* All in all, it reduces the number of grid point to edge check */
+    /*                                                               */
+
     FT_Error   error = FT_Err_Ok;
 
     FT_CALL( split_sdf_shape( shape ) );