| ftbsdf.c |
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);
}
|
38453 |
| ftsdf.c |
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. The paper explains both single and multi-channel
SDF, however, this implementation only generates single-channel SDF.
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 contains information about
the shortest distance 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 our implementation. 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.
|
112098 |
| ftsdf.h |
common properties and function |
2914 |
| ftsdfcommon.c |
format and sign manipulating functions
|
3485 |
| ftsdfcommon.h |
This file contains common functions and properties
for both the 'sdf' and 'bsdf' renderers.
|
4021 |
| ftsdferrs.h |
FTSDFERRS_H_ |
848 |
| ftsdfrend.c |
The macro FT_COMPONENT is used in trace mode. It is an implicit
parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
messages during execution.
|
16209 |
| ftsdfrend.h |
@struct:
SDF_Renderer_Module
@description:
This struct extends the native renderer struct `FT_RendererRec`. It
is basically used to store various parameters required by the
renderer and some additional parameters that can be used to tweak the
output of the renderer.
@fields:
root ::
The native rendere struct.
spread ::
This is an essential parameter/property required by the renderer.
`spread` defines the maximum unsigned value that is present in the
final SDF output. For the default value check file
`ftsdfcommon.h`.
flip_sign ::
By default positive values indicate positions inside of contours,
i.e., filled by a contour. If this property is true then that
output will be the opposite of the default, i.e., negative values
indicate positions inside of contours.
flip_y ::
Setting this parameter to true makes the output image flipped
along the y-axis.
overlaps ::
Set this to true to generate SDF for glyphs having overlapping
contours. The overlapping support is limited to glyphs that do not
have self-intersecting contours. Also, removing overlaps require a
considerable amount of extra memory; additionally, it will not work
if generating SDF from bitmap.
@note:
All properties except `overlaps` are valid for both the 'sdf' and
'bsdf' renderers.
|
3386 |
| module.mk |
|
924 |
| rules.mk |
|
1901 |
| sdf.c |
END |
735 |