[sdf] Add brief technical overview of both rasterizers.

2 files changed, 166 insertions, 0 deletions

diff --git a/src/sdf/ftbsdf.c b/src/sdf/ftbsdf.c
index 510273367..13dbd4511 100644
--- a/src/sdf/ftbsdf.c
+++ b/src/sdf/ftbsdf.c
@@ -11,6 +11,95 @@
 
   /**************************************************************************
    *
+   * 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 converts rasterized bitmaps to SDF.  There is another
+   *     renderer called 'sdf', which generates SDF directly from outlines;
+   *     see file `ftsdf.c` for more.
+   *
+   *   * The idea of generating SDF from bitmaps is taken from two research
+   *     papers, where one is dependent on the other:
+   *
+   *     - Per-Erik Danielsson: Euclidean Distance Mapping
+   *       http://webstaff.itn.liu.se/~stegu/JFA/Danielsson.pdf
+   *
+   *       From this paper we use the eight-point sequential Euclidean
+   *       distance mapping (8SED).  This is the heart of the process used
+   *       in this rasterizer.
+   *
+   *     - Stefan Gustavson, Robin Strand: Anti-aliased Euclidean distance transform.
+   *       http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf
+   *
+   *       The original 8SED algorithm discards the pixels' alpha values,
+   *       which can contain information about the actual outline of the
+   *       glyph.  This paper takes advantage of those alpha values and
+   *       approximates outline pretty accurately.
+   *
+   *   * This rasterizer also works for monochrome bitmaps.  However, the
+   *     result is not as accurate since we don't have any way to
+   *     approximate outlines from binary bitmaps.
+   *
+   * ========================================================================
+   *
+   * Generating SDF from bitmap is done in several steps.
+   *
+   * (1) The only information we have is the bitmap itself.  It can
+   *     be monochrome or anti-aliased.  If it is anti-aliased, pixel values
+   *     are nothing but coverage values.  These 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 passes through the center of the pixel.
+   *
+   * (2) Find edge pixels in the bitmap (see `bsdf_is_edge` for more).  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 for more).
+   *
+   * (3) Now that we have computed approximate distances 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 convoluted it is only explained briefly in a comment to
+   *     function `edt8`.  To see the actual algorithm refer to the first
+   *     paper.)
+   *
+   * (4) Finally, compute the sign for each pixel.  This is done in function
+   *     `finalize_sdf`.  The basic idea is that if a pixel's original
+   *     alpha/coverage value is greater than 0.5 then it is 'inside' (and
+   *     'outside' otherwise).
+   *
+   * 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 29bc0c3ca..1edb00064 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -9,6 +9,83 @@
 
   /**************************************************************************
    *
+   * A brief technical overview of how the SDF rasterizer works
+   * ----------------------------------------------------------
+   *
+   * [Notes]:
+   *   * SDF stands for Signed Distance Field everywhere.
+   *
+   *   * This renderer generates SDF directly from outlines.  There is
+   *     another renderer called 'bsdf', which converts bitmaps to SDF; see
+   *     file `ftbsdf.c` for more.
+   *
+   *   * The basic idea of generating the SDF is taken from Viktor Chlumsky's
+   *     research paper.
+   *
+   *       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 that make the outline of a shape/glyph.
+   *     Each contour comprises of several edges, with three types of edges.
+   *
+   *     * line segments
+   *     * conic Bezier curves
+   *     * cubic Bezier curves
+   *
+   * (2) Apart from the outlines we also have a two-dimensional grid, namely
+   *     the bitmap that is used to represent the final SDF data.
+   *
+   * (3) 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 its sign is positive, otherwise it is 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 running this algorithm the bitmap contain sinformation about the closest
+   *     point from each point to the outline of the shape.  Of course,
+   *     while this is the most straightforward way of generating SDF, we
+   *     use various optimizations in this rasterizer.  See the
+   *     `sdf_generate_*' functions in this file for all details.
+   *
+   *     The optimization currently used by default is subdivision; see
+   *     function `sdf_generate_subdivision` for more.
+   *
+   *     Also, to see how we compute the shortest distance from a point to
+   *     each type of edge, check out the `get_min_distance_*' functions.
+   *
+   */
+
+
+  /**************************************************************************
+   *
    * for tracking used memory
    *
    */