/**************************************************************************** * * ftbsdf.c * * Signed Distance Field support for bitmap fonts (body only). * * Copyright (C) 2020-2023 by * David Turner, Robert Wilhelm, and Werner Lemberg. * * Written by Anuj Verma. * * This file is part of the FreeType project, and may only be used, * modified, and distributed under the terms of the FreeType project * license, LICENSE.TXT. By continuing to use, modify, or distribute * this file you indicate that you have read the license and * understand and accept it fully. * */ #include <freetype/internal/ftobjs.h> #include <freetype/internal/ftdebug.h> #include <freetype/internal/ftmemory.h> #include <freetype/fttrigon.h> #include "ftsdf.h" #include "ftsdferrs.h" #include "ftsdfcommon.h" /************************************************************************** * * 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); * } * */ /************************************************************************** * * 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. */ #undef FT_COMPONENT #define FT_COMPONENT … /************************************************************************** * * useful macros * */ #define ONE … /************************************************************************** * * structs * */ /************************************************************************** * * @Struct: * BSDF_TRaster * * @Description: * This struct is used in place of @FT_Raster and is stored within the * internal FreeType renderer struct. While rasterizing this is passed * to the @FT_Raster_RenderFunc function, which then can be used however * we want. * * @Fields: * memory :: * Used internally to allocate intermediate memory while raterizing. * */ BSDF_PRaster; /************************************************************************** * * @Struct: * ED * * @Description: * Euclidean distance. It gets used for Euclidean distance transforms; * it can also be interpreted as an edge distance. * * @Fields: * dist :: * Vector length of the `prox` parameter. Can be squared or absolute * depending on the `USE_SQUARED_DISTANCES` macro defined in file * `ftsdfcommon.h`. * * prox :: * Vector to the nearest edge. Can also be interpreted as shortest * distance of a point. * * alpha :: * Alpha value of the original bitmap from which we generate SDF. * Needed for computing the gradient and determining the proper sign * of a pixel. * */ ED; /************************************************************************** * * @Struct: * BSDF_Worker * * @Description: * A convenience struct that is passed to functions while generating * SDF; most of those functions require the same parameters. * * @Fields: * distance_map :: * A one-dimensional array that gets interpreted as two-dimensional * one. It contains the Euclidean distances of all points of the * bitmap. * * width :: * Width of the above `distance_map`. * * rows :: * Number of rows in the above `distance_map`. * * params :: * Internal parameters and properties required by the rasterizer. See * file `ftsdf.h` for more. * */ BSDF_Worker; /************************************************************************** * * initializer * */ static const ED zero_ed = …; /************************************************************************** * * rasterizer functions * */ /************************************************************************** * * @Function: * bsdf_is_edge * * @Description: * Check whether a pixel is an edge pixel, i.e., whether it is * surrounded by a completely black pixel (zero alpha), and the current * pixel is not a completely black pixel. * * @Input: * dm :: * Array of distances. The parameter must point to the current * pixel, i.e., the pixel that is to be checked for being an edge. * * x :: * The x position of the current pixel. * * y :: * The y position of the current pixel. * * w :: * Width of the bitmap. * * r :: * Number of rows in the bitmap. * * @Return: * 1~if the current pixel is an edge pixel, 0~otherwise. * */ #ifdef CHECK_NEIGHBOR #undef CHECK_NEIGHBOR #endif #define CHECK_NEIGHBOR … static FT_Bool bsdf_is_edge( ED* dm, /* distance map */ FT_Int x, /* x index of point to check */ FT_Int y, /* y index of point to check */ FT_Int w, /* width */ FT_Int r ) /* rows */ { … } #undef CHECK_NEIGHBOR /************************************************************************** * * @Function: * compute_edge_distance * * @Description: * Approximate the outline and compute the distance from `current` * to the approximated outline. * * @Input: * current :: * Array of Euclidean distances. `current` must point to the position * for which the distance is to be caculated. We treat this array as * a two-dimensional array mapped to a one-dimensional array. * * x :: * The x coordinate of the `current` parameter in the array. * * y :: * The y coordinate of the `current` parameter in the array. * * w :: * The width of the distances array. * * r :: * Number of rows in the distances array. * * @Return: * A vector pointing to the approximate edge distance. * * @Note: * This is a computationally expensive function. Try to reduce the * number of calls to this function. Moreover, this must only be used * for edge pixel positions. * */ static FT_16D16_Vec compute_edge_distance( ED* current, FT_Int x, FT_Int y, FT_Int w, FT_Int r ) { … } /************************************************************************** * * @Function: * bsdf_approximate_edge * * @Description: * Loops over all the pixels and call `compute_edge_distance` only for * edge pixels. This maked the process a lot faster since * `compute_edge_distance` uses functions such as `FT_Vector_NormLen', * which are quite slow. * * @InOut: * worker :: * Contains the distance map as well as all the relevant parameters * required by the function. * * @Return: * FreeType error, 0 means success. * * @Note: * The function directly manipulates `worker->distance_map`. * */ static FT_Error bsdf_approximate_edge( BSDF_Worker* worker ) { … } /************************************************************************** * * @Function: * bsdf_init_distance_map * * @Description: * Initialize the distance map according to the '8-point sequential * Euclidean distance mapping' (8SED) algorithm. Basically it copies * the `source` bitmap alpha values to the `distance_map->alpha` * parameter of `worker`. * * @Input: * source :: * Source bitmap to copy the data from. * * @Output: * worker :: * Target distance map to copy the data to. * * @Return: * FreeType error, 0 means success. * */ static FT_Error bsdf_init_distance_map( const FT_Bitmap* source, BSDF_Worker* worker ) { … } /************************************************************************** * * @Function: * compare_neighbor * * @Description: * Compare neighbor pixel (which is defined by the offset) and update * `current` distance if the new distance is shorter than the original. * * @Input: * x_offset :: * X offset of the neighbor to be checked. The offset is relative to * the `current`. * * y_offset :: * Y offset of the neighbor to be checked. The offset is relative to * the `current`. * * width :: * Width of the `current` array. * * @InOut: * current :: * Pointer into array of distances. This parameter must point to the * position whose neighbor is to be checked. The array is treated as * a two-dimensional array. * */ static void compare_neighbor( ED* current, FT_Int x_offset, FT_Int y_offset, FT_Int width ) { … } /************************************************************************** * * @Function: * first_pass * * @Description: * First pass of the 8SED algorithm. Loop over the bitmap from top to * bottom and scan each row left to right, updating the distances in * `worker->distance_map`. * * @InOut: * worker:: * Contains all the relevant parameters. * */ static void first_pass( BSDF_Worker* worker ) { … } /************************************************************************** * * @Function: * second_pass * * @Description: * Second pass of the 8SED algorithm. Loop over the bitmap from bottom * to top and scan each row left to right, updating the distances in * `worker->distance_map`. * * @InOut: * worker:: * Contains all the relevant parameters. * */ static void second_pass( BSDF_Worker* worker ) { … } /************************************************************************** * * @Function: * edt8 * * @Description: * Compute the distance map of the a bitmap. Execute both first and * second pass of the 8SED algorithm. * * @InOut: * worker:: * Contains all the relevant parameters. * * @Return: * FreeType error, 0 means success. * */ static FT_Error edt8( BSDF_Worker* worker ) { … } /************************************************************************** * * @Function: * finalize_sdf * * @Description: * Copy the SDF data from `worker->distance_map` to the `target` bitmap. * Also transform the data to output format, (which is 6.10 fixed-point * format at the moment). * * @Input: * worker :: * Contains source distance map and other SDF data. * * @Output: * target :: * Target bitmap to which the SDF data is copied to. * * @Return: * FreeType error, 0 means success. * */ static FT_Error finalize_sdf( BSDF_Worker* worker, const FT_Bitmap* target ) { … } /************************************************************************** * * interface functions * */ /* called when adding a new module through @FT_Add_Module */ static FT_Error bsdf_raster_new( void* memory_, /* FT_Memory */ FT_Raster* araster_ ) /* BSDF_PRaster* */ { … } /* unused */ static void bsdf_raster_reset( FT_Raster raster, unsigned char* pool_base, unsigned long pool_size ) { … } /* unused */ static FT_Error bsdf_raster_set_mode( FT_Raster raster, unsigned long mode, void* args ) { … } /* called while rendering through @FT_Render_Glyph */ static FT_Error bsdf_raster_render( FT_Raster raster, const FT_Raster_Params* params ) { … } /* called while deleting `FT_Library` only if the module is added */ static void bsdf_raster_done( FT_Raster raster ) { … } FT_DEFINE_RASTER_FUNCS( ft_bitmap_sdf_raster, FT_GLYPH_FORMAT_BITMAP, (FT_Raster_New_Func) bsdf_raster_new, /* raster_new */ (FT_Raster_Reset_Func) bsdf_raster_reset, /* raster_reset */ (FT_Raster_Set_Mode_Func)bsdf_raster_set_mode, /* raster_set_mode */ (FT_Raster_Render_Func) bsdf_raster_render, /* raster_render */ (FT_Raster_Done_Func) bsdf_raster_done /* raster_done */ ) /* END */
Codebase Browser
godot