ref: 6444875f68b05a906ba91c917970b8df2b436d4a
parent: 6cd6df55c9f23d1d01aa466e7265ec06aea062e2
author: Anuj Verma <anujv@iitbhilai.ac.in>
date: Thu Aug 20 23:59:23 EDT 2020
[sdf] Add brief technical overview of both rasterizers.
--- 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
*
*/
--- 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
*
*/