Commit 6444875f68b05a906ba91c917970b8df2b436d4a
2020-08-21T03:59:23
[sdf] Add brief technical overview of both rasterizers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
diff --git a/src/sdf/ftbsdf.c b/src/sdf/ftbsdf.c
index 5102733..13dbd45 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 29bc0c3..1edb000 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
*
*/