summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/freetype/src/sdf
diff options
context:
space:
mode:
authorVolker Hilsheimer <volker.hilsheimer@qt.io>2022-07-18 12:57:14 +0200
committerKai Köhne <kai.koehne@qt.io>2022-07-22 14:25:26 +0200
commite79d7f12e6ca15c499a553e4a701a2887e4b184c (patch)
tree93138f4b91f0e56621836f6a46291cd219bfd641 /src/3rdparty/freetype/src/sdf
parent425a6415e7593c99c779b406ea5b30fd5975767c (diff)
Update freetype to 2.12.1
ftdebug.c files are new, adapted the import script to copy the source file for Windows as well. Replaced the CMakeLists.txt content that was imported from the .pro file with the respective variables and logic from the freetype CMakeLists.txt file, which should make it easier to maintain this next time. Pick-to: 6.4 6.3 6.2 5.15 5.12 Fixes: QTBUG-105032 Change-Id: I1e846167b268df4b1b0a50dcec602def1a0bdcb4 Reviewed-by: Kai Koehne <kai.koehne@qt.io>
Diffstat (limited to 'src/3rdparty/freetype/src/sdf')
-rw-r--r--src/3rdparty/freetype/src/sdf/ftbsdf.c1347
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdf.c3925
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdf.h97
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdfcommon.c147
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdfcommon.h141
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdferrs.h37
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdfrend.c604
-rw-r--r--src/3rdparty/freetype/src/sdf/ftsdfrend.h118
-rw-r--r--src/3rdparty/freetype/src/sdf/module.mk29
-rw-r--r--src/3rdparty/freetype/src/sdf/rules.mk78
-rw-r--r--src/3rdparty/freetype/src/sdf/sdf.c29
11 files changed, 6552 insertions, 0 deletions
diff --git a/src/3rdparty/freetype/src/sdf/ftbsdf.c b/src/3rdparty/freetype/src/sdf/ftbsdf.c
new file mode 100644
index 0000000000..1328ac4988
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftbsdf.c
@@ -0,0 +1,1347 @@
+/****************************************************************************
+ *
+ * ftbsdf.c
+ *
+ * Signed Distance Field support for bitmap fonts (body only).
+ *
+ * Copyright (C) 2020-2022 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 bsdf
+
+
+ /**************************************************************************
+ *
+ * useful macros
+ *
+ */
+
+#define ONE 65536 /* 1 in 16.16 */
+
+
+ /**************************************************************************
+ *
+ * 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.
+ *
+ */
+ typedef struct BSDF_TRaster_
+ {
+ FT_Memory memory;
+
+ } BSDF_TRaster, *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.
+ *
+ */
+ typedef struct ED_
+ {
+ FT_16D16 dist;
+ FT_16D16_Vec prox;
+ FT_Byte alpha;
+
+ } 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.
+ *
+ */
+ typedef struct BSDF_Worker_
+ {
+ ED* distance_map;
+
+ FT_Int width;
+ FT_Int rows;
+
+ SDF_Raster_Params params;
+
+ } BSDF_Worker;
+
+
+ /**************************************************************************
+ *
+ * initializer
+ *
+ */
+
+ static const ED zero_ed = { 0, { 0, 0 }, 0 };
+
+
+ /**************************************************************************
+ *
+ * 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( x_offset, y_offset ) \
+ do \
+ { \
+ if ( x + x_offset >= 0 && x + x_offset < w && \
+ y + y_offset >= 0 && y + y_offset < r ) \
+ { \
+ num_neighbors++; \
+ \
+ to_check = dm + y_offset * w + x_offset; \
+ if ( to_check->alpha == 0 ) \
+ { \
+ is_edge = 1; \
+ goto Done; \
+ } \
+ } \
+ } while ( 0 )
+
+ 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 */
+ {
+ FT_Bool is_edge = 0;
+ ED* to_check = NULL;
+ FT_Int num_neighbors = 0;
+
+
+ if ( dm->alpha == 0 )
+ goto Done;
+
+ if ( dm->alpha > 0 && dm->alpha < 255 )
+ {
+ is_edge = 1;
+ goto Done;
+ }
+
+ /* up */
+ CHECK_NEIGHBOR( 0, -1 );
+
+ /* down */
+ CHECK_NEIGHBOR( 0, 1 );
+
+ /* left */
+ CHECK_NEIGHBOR( -1, 0 );
+
+ /* right */
+ CHECK_NEIGHBOR( 1, 0 );
+
+ /* up left */
+ CHECK_NEIGHBOR( -1, -1 );
+
+ /* up right */
+ CHECK_NEIGHBOR( 1, -1 );
+
+ /* down left */
+ CHECK_NEIGHBOR( -1, 1 );
+
+ /* down right */
+ CHECK_NEIGHBOR( 1, 1 );
+
+ if ( num_neighbors != 8 )
+ is_edge = 1;
+
+ Done:
+ return is_edge;
+ }
+
+#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 )
+ {
+ /*
+ * This function, based on the paper presented by Stefan Gustavson and
+ * Robin Strand, gets used to approximate edge distances from
+ * anti-aliased bitmaps.
+ *
+ * The algorithm is as follows.
+ *
+ * (1) In anti-aliased images, the pixel's alpha value is the coverage
+ * of the pixel by the outline. For example, if the alpha value is
+ * 0.5f we can assume that the outline passes through the center of
+ * the pixel.
+ *
+ * (2) For this reason we can use that alpha value to approximate the real
+ * distance of the pixel to edge pretty accurately. A simple
+ * approximation is `(0.5f - alpha)`, assuming that the outline is
+ * parallel to the x or y~axis. However, in this algorithm we use a
+ * different approximation which is quite accurate even for
+ * non-axis-aligned edges.
+ *
+ * (3) The only remaining piece of information that we cannot
+ * approximate directly from the alpha is the direction of the edge.
+ * This is where we use Sobel's operator to compute the gradient of
+ * the pixel. The gradient give us a pretty good approximation of
+ * the edge direction. We use a 3x3 kernel filter to compute the
+ * gradient.
+ *
+ * (4) After the above two steps we have both the direction and the
+ * distance to the edge which is used to generate the Signed
+ * Distance Field.
+ *
+ * References:
+ *
+ * - Anti-Aliased Euclidean Distance Transform:
+ * http://weber.itn.liu.se/~stegu/aadist/edtaa_preprint.pdf
+ * - Sobel Operator:
+ * https://en.wikipedia.org/wiki/Sobel_operator
+ */
+
+ FT_16D16_Vec g = { 0, 0 };
+ FT_16D16 dist, current_alpha;
+ FT_16D16 a1, temp;
+ FT_16D16 gx, gy;
+ FT_16D16 alphas[9];
+
+
+ /* Since our spread cannot be 0, this condition */
+ /* can never be true. */
+ if ( x <= 0 || x >= w - 1 ||
+ y <= 0 || y >= r - 1 )
+ return g;
+
+ /* initialize the alphas */
+ alphas[0] = 256 * (FT_16D16)current[-w - 1].alpha;
+ alphas[1] = 256 * (FT_16D16)current[-w ].alpha;
+ alphas[2] = 256 * (FT_16D16)current[-w + 1].alpha;
+ alphas[3] = 256 * (FT_16D16)current[ -1].alpha;
+ alphas[4] = 256 * (FT_16D16)current[ 0].alpha;
+ alphas[5] = 256 * (FT_16D16)current[ 1].alpha;
+ alphas[6] = 256 * (FT_16D16)current[ w - 1].alpha;
+ alphas[7] = 256 * (FT_16D16)current[ w ].alpha;
+ alphas[8] = 256 * (FT_16D16)current[ w + 1].alpha;
+
+ current_alpha = alphas[4];
+
+ /* Compute the gradient using the Sobel operator. */
+ /* In this case we use the following 3x3 filters: */
+ /* */
+ /* For x: | -1 0 -1 | */
+ /* | -root(2) 0 root(2) | */
+ /* | -1 0 1 | */
+ /* */
+ /* For y: | -1 -root(2) -1 | */
+ /* | 0 0 0 | */
+ /* | 1 root(2) 1 | */
+ /* */
+ /* [Note]: 92681 is root(2) in 16.16 format. */
+ g.x = -alphas[0] -
+ FT_MulFix( alphas[3], 92681 ) -
+ alphas[6] +
+ alphas[2] +
+ FT_MulFix( alphas[5], 92681 ) +
+ alphas[8];
+
+ g.y = -alphas[0] -
+ FT_MulFix( alphas[1], 92681 ) -
+ alphas[2] +
+ alphas[6] +
+ FT_MulFix( alphas[7], 92681 ) +
+ alphas[8];
+
+ FT_Vector_NormLen( &g );
+
+ /* The gradient gives us the direction of the */
+ /* edge for the current pixel. Once we have the */
+ /* approximate direction of the edge, we can */
+ /* approximate the edge distance much better. */
+
+ if ( g.x == 0 || g.y == 0 )
+ dist = ONE / 2 - alphas[4];
+ else
+ {
+ gx = g.x;
+ gy = g.y;
+
+ gx = FT_ABS( gx );
+ gy = FT_ABS( gy );
+
+ if ( gx < gy )
+ {
+ temp = gx;
+ gx = gy;
+ gy = temp;
+ }
+
+ a1 = FT_DivFix( gy, gx ) / 2;
+
+ if ( current_alpha < a1 )
+ dist = ( gx + gy ) / 2 -
+ square_root( 2 * FT_MulFix( gx,
+ FT_MulFix( gy,
+ current_alpha ) ) );
+
+ else if ( current_alpha < ( ONE - a1 ) )
+ dist = FT_MulFix( ONE / 2 - current_alpha, gx );
+
+ else
+ dist = -( gx + gy ) / 2 +
+ square_root( 2 * FT_MulFix( gx,
+ FT_MulFix( gy,
+ ONE - current_alpha ) ) );
+ }
+
+ g.x = FT_MulFix( g.x, dist );
+ g.y = FT_MulFix( g.y, dist );
+
+ return g;
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Int i, j;
+ FT_Int index;
+ ED* ed;
+
+
+ if ( !worker || !worker->distance_map )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ ed = worker->distance_map;
+
+ for ( j = 0; j < worker->rows; j++ )
+ {
+ for ( i = 0; i < worker->width; i++ )
+ {
+ index = j * worker->width + i;
+
+ if ( bsdf_is_edge( worker->distance_map + index,
+ i, j,
+ worker->width,
+ worker->rows ) )
+ {
+ /* approximate the edge distance for edge pixels */
+ ed[index].prox = compute_edge_distance( ed + index,
+ i, j,
+ worker->width,
+ worker->rows );
+ ed[index].dist = VECTOR_LENGTH_16D16( ed[index].prox );
+ }
+ else
+ {
+ /* for non-edge pixels assign far away distances */
+ ed[index].dist = 400 * ONE;
+ ed[index].prox.x = 200 * ONE;
+ ed[index].prox.y = 200 * ONE;
+ }
+ }
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Error error = FT_Err_Ok;
+
+ FT_Int x_diff, y_diff;
+ FT_Int t_i, t_j, s_i, s_j;
+ FT_Byte* s;
+ ED* t;
+
+
+ /* again check the parameters (probably unnecessary) */
+ if ( !source || !worker )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* Because of the way we convert a bitmap to SDF, */
+ /* i.e., aligning the source to the center of the */
+ /* target, the target's width and rows must be */
+ /* checked before copying. */
+ if ( worker->width < (FT_Int)source->width ||
+ worker->rows < (FT_Int)source->rows )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* check pixel mode */
+ if ( source->pixel_mode == FT_PIXEL_MODE_NONE )
+ {
+ FT_ERROR(( "bsdf_copy_source_to_target:"
+ " Invalid pixel mode of source bitmap" ));
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+#ifdef FT_DEBUG_LEVEL_TRACE
+ if ( source->pixel_mode == FT_PIXEL_MODE_MONO )
+ {
+ FT_TRACE0(( "bsdf_copy_source_to_target:"
+ " The `bsdf' renderer can convert monochrome\n" ));
+ FT_TRACE0(( " "
+ " bitmaps to SDF but the results are not perfect\n" ));
+ FT_TRACE0(( " "
+ " because there is no way to approximate actual\n" ));
+ FT_TRACE0(( " "
+ " outlines from monochrome bitmaps. Consider\n" ));
+ FT_TRACE0(( " "
+ " using an anti-aliased bitmap instead.\n" ));
+ }
+#endif
+
+ /* Calculate the width and row differences */
+ /* between target and source. */
+ x_diff = worker->width - (int)source->width;
+ y_diff = worker->rows - (int)source->rows;
+
+ x_diff /= 2;
+ y_diff /= 2;
+
+ t = (ED*)worker->distance_map;
+ s = source->buffer;
+
+ /* For now we only support pixel mode `FT_PIXEL_MODE_MONO` */
+ /* and `FT_PIXEL_MODE_GRAY`. More will be added later. */
+ /* */
+ /* [NOTE]: We can also use @FT_Bitmap_Convert to convert */
+ /* bitmap to 8bpp. To avoid extra allocation and */
+ /* since the target bitmap can be 16bpp we manually */
+ /* convert the source bitmap to the desired bpp. */
+
+ switch ( source->pixel_mode )
+ {
+ case FT_PIXEL_MODE_MONO:
+ {
+ FT_Int t_width = worker->width;
+ FT_Int t_rows = worker->rows;
+ FT_Int s_width = (int)source->width;
+ FT_Int s_rows = (int)source->rows;
+
+
+ for ( t_j = 0; t_j < t_rows; t_j++ )
+ {
+ for ( t_i = 0; t_i < t_width; t_i++ )
+ {
+ FT_Int t_index = t_j * t_width + t_i;
+ FT_Int s_index;
+ FT_Int div, mod;
+ FT_Byte pixel, byte;
+
+
+ t[t_index] = zero_ed;
+
+ s_i = t_i - x_diff;
+ s_j = t_j - y_diff;
+
+ /* Assign 0 to padding similar to */
+ /* the source bitmap. */
+ if ( s_i < 0 || s_i >= s_width ||
+ s_j < 0 || s_j >= s_rows )
+ continue;
+
+ if ( worker->params.flip_y )
+ s_index = ( s_rows - s_j - 1 ) * source->pitch;
+ else
+ s_index = s_j * source->pitch;
+
+ div = s_index + s_i / 8;
+ mod = 7 - s_i % 8;
+
+ pixel = s[div];
+ byte = (FT_Byte)( 1 << mod );
+
+ t[t_index].alpha = pixel & byte ? 255 : 0;
+ }
+ }
+ }
+ break;
+
+ case FT_PIXEL_MODE_GRAY:
+ {
+ FT_Int t_width = worker->width;
+ FT_Int t_rows = worker->rows;
+ FT_Int s_width = (int)source->width;
+ FT_Int s_rows = (int)source->rows;
+
+
+ /* loop over all pixels and assign pixel values from source */
+ for ( t_j = 0; t_j < t_rows; t_j++ )
+ {
+ for ( t_i = 0; t_i < t_width; t_i++ )
+ {
+ FT_Int t_index = t_j * t_width + t_i;
+ FT_Int s_index;
+
+
+ t[t_index] = zero_ed;
+
+ s_i = t_i - x_diff;
+ s_j = t_j - y_diff;
+
+ /* Assign 0 to padding similar to */
+ /* the source bitmap. */
+ if ( s_i < 0 || s_i >= s_width ||
+ s_j < 0 || s_j >= s_rows )
+ continue;
+
+ if ( worker->params.flip_y )
+ s_index = ( s_rows - s_j - 1 ) * s_width + s_i;
+ else
+ s_index = s_j * s_width + s_i;
+
+ /* simply copy the alpha values */
+ t[t_index].alpha = s[s_index];
+ }
+ }
+ }
+ break;
+
+ default:
+ FT_ERROR(( "bsdf_copy_source_to_target:"
+ " unsopported pixel mode of source bitmap\n" ));
+
+ error = FT_THROW( Unimplemented_Feature );
+ break;
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ ED* to_check;
+ FT_16D16 dist;
+ FT_16D16_Vec dist_vec;
+
+
+ to_check = current + ( y_offset * width ) + x_offset;
+
+ /*
+ * While checking for the nearest point we first approximate the
+ * distance of `current` by adding the deviation (which is sqrt(2) at
+ * most). Only if the new value is less than the current value we
+ * calculate the actual distances using `FT_Vector_Length`. This last
+ * step can be omitted by using squared distances.
+ */
+
+ /*
+ * Approximate the distance. We subtract 1 to avoid precision errors,
+ * which could happen because the two directions can be opposite.
+ */
+ dist = to_check->dist - ONE;
+
+ if ( dist < current->dist )
+ {
+ dist_vec = to_check->prox;
+
+ dist_vec.x += x_offset * ONE;
+ dist_vec.y += y_offset * ONE;
+ dist = VECTOR_LENGTH_16D16( dist_vec );
+
+ if ( dist < current->dist )
+ {
+ current->dist = dist;
+ current->prox = dist_vec;
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Int i, j; /* iterators */
+ FT_Int w, r; /* width, rows */
+ ED* dm; /* distance map */
+
+
+ dm = worker->distance_map;
+ w = worker->width;
+ r = worker->rows;
+
+ /* Start scanning from top to bottom and sweep each */
+ /* row back and forth comparing the distances of the */
+ /* neighborhood. Leave the first row as it has no top */
+ /* neighbor; it will be covered in the second scan of */
+ /* the image (from bottom to top). */
+ for ( j = 1; j < r; j++ )
+ {
+ FT_Int index;
+ ED* current;
+
+
+ /* Forward pass of rows (left -> right). Leave the first */
+ /* column, which gets covered in the backward pass. */
+ for ( i = 1; i < w - 1; i++ )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* left-up */
+ compare_neighbor( current, -1, -1, w );
+ /* up */
+ compare_neighbor( current, 0, -1, w );
+ /* up-right */
+ compare_neighbor( current, 1, -1, w );
+ /* left */
+ compare_neighbor( current, -1, 0, w );
+ }
+
+ /* Backward pass of rows (right -> left). Leave the last */
+ /* column, which was already covered in the forward pass. */
+ for ( i = w - 2; i >= 0; i-- )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* right */
+ compare_neighbor( current, 1, 0, w );
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Int i, j; /* iterators */
+ FT_Int w, r; /* width, rows */
+ ED* dm; /* distance map */
+
+
+ dm = worker->distance_map;
+ w = worker->width;
+ r = worker->rows;
+
+ /* Start scanning from bottom to top and sweep each */
+ /* row back and forth comparing the distances of the */
+ /* neighborhood. Leave the last row as it has no down */
+ /* neighbor; it is already covered in the first scan */
+ /* of the image (from top to bottom). */
+ for ( j = r - 2; j >= 0; j-- )
+ {
+ FT_Int index;
+ ED* current;
+
+
+ /* Forward pass of rows (left -> right). Leave the first */
+ /* column, which gets covered in the backward pass. */
+ for ( i = 1; i < w - 1; i++ )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* left-up */
+ compare_neighbor( current, -1, 1, w );
+ /* up */
+ compare_neighbor( current, 0, 1, w );
+ /* up-right */
+ compare_neighbor( current, 1, 1, w );
+ /* left */
+ compare_neighbor( current, -1, 0, w );
+ }
+
+ /* Backward pass of rows (right -> left). Leave the last */
+ /* column, which was already covered in the forward pass. */
+ for ( i = w - 2; i >= 0; i-- )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* right */
+ compare_neighbor( current, 1, 0, w );
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Error error = FT_Err_Ok;
+
+
+ if ( !worker || !worker->distance_map )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* first scan of the image */
+ first_pass( worker );
+
+ /* second scan of the image */
+ second_pass( worker );
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @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 )
+ {
+ FT_Error error = FT_Err_Ok;
+
+ FT_Int w, r;
+ FT_Int i, j;
+
+ FT_SDFFormat* t_buffer;
+ FT_16D16 sp_sq, spread;
+
+
+ if ( !worker || !target )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ w = (int)target->width;
+ r = (int)target->rows;
+ t_buffer = (FT_SDFFormat*)target->buffer;
+
+ if ( w != worker->width ||
+ r != worker->rows )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ spread = FT_INT_16D16( worker->params.spread );
+
+#if USE_SQUARED_DISTANCES
+ sp_sq = FT_INT_16D16( worker->params.spread *
+ worker->params.spread );
+#else
+ sp_sq = FT_INT_16D16( worker->params.spread );
+#endif
+
+ for ( j = 0; j < r; j++ )
+ {
+ for ( i = 0; i < w; i++ )
+ {
+ FT_Int index;
+ FT_16D16 dist;
+ FT_SDFFormat final_dist;
+ FT_Char sign;
+
+
+ index = j * w + i;
+ dist = worker->distance_map[index].dist;
+
+ if ( dist < 0 || dist > sp_sq )
+ dist = sp_sq;
+
+#if USE_SQUARED_DISTANCES
+ dist = square_root( dist );
+#endif
+
+ /* We assume that if the pixel is inside a contour */
+ /* its coverage value must be > 127. */
+ sign = worker->distance_map[index].alpha < 127 ? -1 : 1;
+
+ /* flip the sign according to the property */
+ if ( worker->params.flip_sign )
+ sign = -sign;
+
+ /* concatenate from 16.16 to appropriate format */
+ final_dist = map_fixed_to_sdf( dist * sign, spread );
+
+ t_buffer[index] = final_dist;
+ }
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * interface functions
+ *
+ */
+
+ /* called when adding a new module through @FT_Add_Module */
+ static FT_Error
+ bsdf_raster_new( FT_Memory memory,
+ BSDF_PRaster* araster )
+ {
+ FT_Error error;
+ BSDF_PRaster raster = NULL;
+
+
+ if ( !FT_NEW( raster ) )
+ raster->memory = memory;
+
+ *araster = raster;
+
+ return error;
+ }
+
+
+ /* unused */
+ static void
+ bsdf_raster_reset( FT_Raster raster,
+ unsigned char* pool_base,
+ unsigned long pool_size )
+ {
+ FT_UNUSED( raster );
+ FT_UNUSED( pool_base );
+ FT_UNUSED( pool_size );
+ }
+
+
+ /* unused */
+ static FT_Error
+ bsdf_raster_set_mode( FT_Raster raster,
+ unsigned long mode,
+ void* args )
+ {
+ FT_UNUSED( raster );
+ FT_UNUSED( mode );
+ FT_UNUSED( args );
+
+ return FT_Err_Ok;
+ }
+
+
+ /* called while rendering through @FT_Render_Glyph */
+ static FT_Error
+ bsdf_raster_render( FT_Raster raster,
+ const FT_Raster_Params* params )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = NULL;
+
+ const FT_Bitmap* source = NULL;
+ const FT_Bitmap* target = NULL;
+
+ BSDF_TRaster* bsdf_raster = (BSDF_TRaster*)raster;
+ BSDF_Worker worker;
+
+ const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params;
+
+
+ worker.distance_map = NULL;
+
+ /* check for valid parameters */
+ if ( !raster || !params )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* check whether the flag is set */
+ if ( sdf_params->root.flags != FT_RASTER_FLAG_SDF )
+ {
+ error = FT_THROW( Raster_Corrupted );
+ goto Exit;
+ }
+
+ source = (const FT_Bitmap*)sdf_params->root.source;
+ target = (const FT_Bitmap*)sdf_params->root.target;
+
+ /* check source and target bitmap */
+ if ( !source || !target )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ memory = bsdf_raster->memory;
+ if ( !memory )
+ {
+ FT_TRACE0(( "bsdf_raster_render: Raster not set up properly,\n" ));
+ FT_TRACE0(( " unable to find memory handle.\n" ));
+
+ error = FT_THROW( Invalid_Handle );
+ goto Exit;
+ }
+
+ /* check whether spread is set properly */
+ if ( sdf_params->spread > MAX_SPREAD ||
+ sdf_params->spread < MIN_SPREAD )
+ {
+ FT_TRACE0(( "bsdf_raster_render:"
+ " The `spread' field of `SDF_Raster_Params'\n" ));
+ FT_TRACE0(( " "
+ " is invalid; the value of this field must be\n" ));
+ FT_TRACE0(( " "
+ " within [%d, %d].\n",
+ MIN_SPREAD, MAX_SPREAD ));
+ FT_TRACE0(( " "
+ " Also, you must pass `SDF_Raster_Params'\n" ));
+ FT_TRACE0(( " "
+ " instead of the default `FT_Raster_Params'\n" ));
+ FT_TRACE0(( " "
+ " while calling this function and set the fields\n" ));
+ FT_TRACE0(( " "
+ " accordingly.\n" ));
+
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* set up the worker */
+
+ /* allocate the distance map */
+ if ( FT_QALLOC_MULT( worker.distance_map, target->rows,
+ target->width * sizeof ( *worker.distance_map ) ) )
+ goto Exit;
+
+ worker.width = (int)target->width;
+ worker.rows = (int)target->rows;
+ worker.params = *sdf_params;
+
+ FT_CALL( bsdf_init_distance_map( source, &worker ) );
+ FT_CALL( bsdf_approximate_edge( &worker ) );
+ FT_CALL( edt8( &worker ) );
+ FT_CALL( finalize_sdf( &worker, target ) );
+
+ FT_TRACE0(( "bsdf_raster_render: Total memory used = %ld\n",
+ worker.width * worker.rows *
+ (long)sizeof ( *worker.distance_map ) ));
+
+ Exit:
+ if ( worker.distance_map )
+ FT_FREE( worker.distance_map );
+
+ return error;
+ }
+
+
+ /* called while deleting `FT_Library` only if the module is added */
+ static void
+ bsdf_raster_done( FT_Raster raster )
+ {
+ FT_Memory memory = (FT_Memory)((BSDF_TRaster*)raster)->memory;
+
+
+ FT_FREE( 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 */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdf.c b/src/3rdparty/freetype/src/sdf/ftsdf.c
new file mode 100644
index 0000000000..ffac8bf465
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdf.c
@@ -0,0 +1,3925 @@
+/****************************************************************************
+ *
+ * ftsdf.c
+ *
+ * Signed Distance Field support for outline fonts (body).
+ *
+ * Copyright (C) 2020-2022 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/ftoutln.h>
+#include <freetype/fttrigon.h>
+#include <freetype/ftbitmap.h>
+#include "ftsdf.h"
+
+#include "ftsdferrs.h"
+
+
+ /**************************************************************************
+ *
+ * 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.
+ *
+ */
+
+
+ /**************************************************************************
+ *
+ * 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 sdf
+
+
+ /**************************************************************************
+ *
+ * definitions
+ *
+ */
+
+ /*
+ * If set to 1, the rasterizer uses Newton-Raphson's method for finding
+ * the shortest distance from a point to a conic curve.
+ *
+ * If set to 0, an analytical method gets used instead, which computes the
+ * roots of a cubic polynomial to find the shortest distance. However,
+ * the analytical method can currently underflow; we thus use Newton's
+ * method by default.
+ */
+#ifndef USE_NEWTON_FOR_CONIC
+#define USE_NEWTON_FOR_CONIC 1
+#endif
+
+ /*
+ * The number of intervals a Bezier curve gets sampled and checked to find
+ * the shortest distance.
+ */
+#define MAX_NEWTON_DIVISIONS 4
+
+ /*
+ * The number of steps of Newton's iterations in each interval of the
+ * Bezier curve. Basically, we run Newton's approximation
+ *
+ * x -= Q(t) / Q'(t)
+ *
+ * for each division to get the shortest distance.
+ */
+#define MAX_NEWTON_STEPS 4
+
+ /*
+ * The epsilon distance (in 16.16 fractional units) used for corner
+ * resolving. If the difference of two distances is less than this value
+ * they will be checked for a corner if they are ambiguous.
+ */
+#define CORNER_CHECK_EPSILON 32
+
+#if 0
+ /*
+ * Coarse grid dimension. Will probably be removed in the future because
+ * coarse grid optimization is the slowest algorithm.
+ */
+#define CG_DIMEN 8
+#endif
+
+
+ /**************************************************************************
+ *
+ * macros
+ *
+ */
+
+#define MUL_26D6( a, b ) ( ( ( a ) * ( b ) ) / 64 )
+#define VEC_26D6_DOT( p, q ) ( MUL_26D6( p.x, q.x ) + \
+ MUL_26D6( p.y, q.y ) )
+
+
+ /**************************************************************************
+ *
+ * structures and enums
+ *
+ */
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_TRaster
+ *
+ * @Description:
+ * This struct is used in place of @FT_Raster and is stored within the
+ * internal FreeType renderer struct. While rasterizing it 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.
+ *
+ */
+ typedef struct SDF_TRaster_
+ {
+ FT_Memory memory;
+
+ } SDF_TRaster, *SDF_PRaster;
+
+
+ /**************************************************************************
+ *
+ * @Enum:
+ * SDF_Edge_Type
+ *
+ * @Description:
+ * Enumeration of all curve types present in fonts.
+ *
+ * @Fields:
+ * SDF_EDGE_UNDEFINED ::
+ * Undefined edge, simply used to initialize and detect errors.
+ *
+ * SDF_EDGE_LINE ::
+ * Line segment with start and end point.
+ *
+ * SDF_EDGE_CONIC ::
+ * A conic/quadratic Bezier curve with start, end, and one control
+ * point.
+ *
+ * SDF_EDGE_CUBIC ::
+ * A cubic Bezier curve with start, end, and two control points.
+ *
+ */
+ typedef enum SDF_Edge_Type_
+ {
+ SDF_EDGE_UNDEFINED = 0,
+ SDF_EDGE_LINE = 1,
+ SDF_EDGE_CONIC = 2,
+ SDF_EDGE_CUBIC = 3
+
+ } SDF_Edge_Type;
+
+
+ /**************************************************************************
+ *
+ * @Enum:
+ * SDF_Contour_Orientation
+ *
+ * @Description:
+ * Enumeration of all orientation values of a contour. We determine the
+ * orientation by calculating the area covered by a contour. Contrary
+ * to values returned by @FT_Outline_Get_Orientation,
+ * `SDF_Contour_Orientation` is independent of the fill rule, which can
+ * be different for different font formats.
+ *
+ * @Fields:
+ * SDF_ORIENTATION_NONE ::
+ * Undefined orientation, used for initialization and error detection.
+ *
+ * SDF_ORIENTATION_CW ::
+ * Clockwise orientation (positive area covered).
+ *
+ * SDF_ORIENTATION_CCW ::
+ * Counter-clockwise orientation (negative area covered).
+ *
+ * @Note:
+ * See @FT_Outline_Get_Orientation for more details.
+ *
+ */
+ typedef enum SDF_Contour_Orientation_
+ {
+ SDF_ORIENTATION_NONE = 0,
+ SDF_ORIENTATION_CW = 1,
+ SDF_ORIENTATION_CCW = 2
+
+ } SDF_Contour_Orientation;
+
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_Edge
+ *
+ * @Description:
+ * Represent an edge of a contour.
+ *
+ * @Fields:
+ * start_pos ::
+ * Start position of an edge. Valid for all types of edges.
+ *
+ * end_pos ::
+ * Etart position of an edge. Valid for all types of edges.
+ *
+ * control_a ::
+ * A control point of the edge. Valid only for `SDF_EDGE_CONIC`
+ * and `SDF_EDGE_CUBIC`.
+ *
+ * control_b ::
+ * Another control point of the edge. Valid only for
+ * `SDF_EDGE_CONIC`.
+ *
+ * edge_type ::
+ * Type of the edge, see @SDF_Edge_Type for all possible edge types.
+ *
+ * next ::
+ * Used to create a singly linked list, which can be interpreted
+ * as a contour.
+ *
+ */
+ typedef struct SDF_Edge_
+ {
+ FT_26D6_Vec start_pos;
+ FT_26D6_Vec end_pos;
+ FT_26D6_Vec control_a;
+ FT_26D6_Vec control_b;
+
+ SDF_Edge_Type edge_type;
+
+ struct SDF_Edge_* next;
+
+ } SDF_Edge;
+
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_Contour
+ *
+ * @Description:
+ * Represent a complete contour, which contains a list of edges.
+ *
+ * @Fields:
+ * last_pos ::
+ * Contains the value of `end_pos' of the last edge in the list of
+ * edges. Useful while decomposing the outline with
+ * @FT_Outline_Decompose.
+ *
+ * edges ::
+ * Linked list of all the edges that make the contour.
+ *
+ * next ::
+ * Used to create a singly linked list, which can be interpreted as a
+ * complete shape or @FT_Outline.
+ *
+ */
+ typedef struct SDF_Contour_
+ {
+ FT_26D6_Vec last_pos;
+ SDF_Edge* edges;
+
+ struct SDF_Contour_* next;
+
+ } SDF_Contour;
+
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_Shape
+ *
+ * @Description:
+ * Represent a complete shape, which is the decomposition of
+ * @FT_Outline.
+ *
+ * @Fields:
+ * memory ::
+ * Used internally to allocate memory.
+ *
+ * contours ::
+ * Linked list of all the contours that make the shape.
+ *
+ */
+ typedef struct SDF_Shape_
+ {
+ FT_Memory memory;
+ SDF_Contour* contours;
+
+ } SDF_Shape;
+
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_Signed_Distance
+ *
+ * @Description:
+ * Represent signed distance of a point, i.e., the distance of the edge
+ * nearest to the point.
+ *
+ * @Fields:
+ * distance ::
+ * Distance of the point from the nearest edge. Can be squared or
+ * absolute depending on the `USE_SQUARED_DISTANCES` macro defined in
+ * file `ftsdfcommon.h`.
+ *
+ * cross ::
+ * Cross product of the shortest distance vector (i.e., the vector
+ * from the point to the nearest edge) and the direction of the edge
+ * at the nearest point. This is used to resolve ambiguities of
+ * `sign`.
+ *
+ * sign ::
+ * A value used to indicate whether the distance vector is outside or
+ * inside the contour corresponding to the edge.
+ *
+ * @Note:
+ * `sign` may or may not be correct, therefore it must be checked
+ * properly in case there is an ambiguity.
+ *
+ */
+ typedef struct SDF_Signed_Distance_
+ {
+ FT_16D16 distance;
+ FT_16D16 cross;
+ FT_Char sign;
+
+ } SDF_Signed_Distance;
+
+
+ /**************************************************************************
+ *
+ * @Struct:
+ * SDF_Params
+ *
+ * @Description:
+ * Yet another internal parameters required by the rasterizer.
+ *
+ * @Fields:
+ * orientation ::
+ * This is not the @SDF_Contour_Orientation value but @FT_Orientation,
+ * which determines whether clockwise-oriented outlines are to be
+ * filled or counter-clockwise-oriented ones.
+ *
+ * flip_sign ::
+ * If set to true, flip the sign. By default the points filled by the
+ * outline are positive.
+ *
+ * flip_y ::
+ * If set to true the output bitmap is upside-down. Can be useful
+ * because OpenGL and DirectX use different coordinate systems for
+ * textures.
+ *
+ * overload_sign ::
+ * In the subdivision and bounding box optimization, the default
+ * outside sign is taken as -1. This parameter can be used to modify
+ * that behaviour. For example, while generating SDF for a single
+ * counter-clockwise contour, the outside sign should be 1.
+ *
+ */
+ typedef struct SDF_Params_
+ {
+ FT_Orientation orientation;
+ FT_Bool flip_sign;
+ FT_Bool flip_y;
+
+ FT_Int overload_sign;
+
+ } SDF_Params;
+
+
+ /**************************************************************************
+ *
+ * constants, initializer, and destructor
+ *
+ */
+
+ static
+ const FT_Vector zero_vector = { 0, 0 };
+
+ static
+ const SDF_Edge null_edge = { { 0, 0 }, { 0, 0 },
+ { 0, 0 }, { 0, 0 },
+ SDF_EDGE_UNDEFINED, NULL };
+
+ static
+ const SDF_Contour null_contour = { { 0, 0 }, NULL, NULL };
+
+ static
+ const SDF_Shape null_shape = { NULL, NULL };
+
+ static
+ const SDF_Signed_Distance max_sdf = { INT_MAX, 0, 0 };
+
+
+ /* Create a new @SDF_Edge on the heap and assigns the `edge` */
+ /* pointer to the newly allocated memory. */
+ static FT_Error
+ sdf_edge_new( FT_Memory memory,
+ SDF_Edge** edge )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Edge* ptr = NULL;
+
+
+ if ( !memory || !edge )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( !FT_QNEW( ptr ) )
+ {
+ *ptr = null_edge;
+ *edge = ptr;
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /* Free the allocated `edge` variable. */
+ static void
+ sdf_edge_done( FT_Memory memory,
+ SDF_Edge** edge )
+ {
+ if ( !memory || !edge || !*edge )
+ return;
+
+ FT_FREE( *edge );
+ }
+
+
+ /* Create a new @SDF_Contour on the heap and assign */
+ /* the `contour` pointer to the newly allocated memory. */
+ static FT_Error
+ sdf_contour_new( FT_Memory memory,
+ SDF_Contour** contour )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Contour* ptr = NULL;
+
+
+ if ( !memory || !contour )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( !FT_QNEW( ptr ) )
+ {
+ *ptr = null_contour;
+ *contour = ptr;
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /* Free the allocated `contour` variable. */
+ /* Also free the list of edges. */
+ static void
+ sdf_contour_done( FT_Memory memory,
+ SDF_Contour** contour )
+ {
+ SDF_Edge* edges;
+ SDF_Edge* temp;
+
+
+ if ( !memory || !contour || !*contour )
+ return;
+
+ edges = (*contour)->edges;
+
+ /* release all edges */
+ while ( edges )
+ {
+ temp = edges;
+ edges = edges->next;
+
+ sdf_edge_done( memory, &temp );
+ }
+
+ FT_FREE( *contour );
+ }
+
+
+ /* Create a new @SDF_Shape on the heap and assign */
+ /* the `shape` pointer to the newly allocated memory. */
+ static FT_Error
+ sdf_shape_new( FT_Memory memory,
+ SDF_Shape** shape )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Shape* ptr = NULL;
+
+
+ if ( !memory || !shape )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( !FT_QNEW( ptr ) )
+ {
+ *ptr = null_shape;
+ ptr->memory = memory;
+ *shape = ptr;
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /* Free the allocated `shape` variable. */
+ /* Also free the list of contours. */
+ static void
+ sdf_shape_done( SDF_Shape** shape )
+ {
+ FT_Memory memory;
+ SDF_Contour* contours;
+ SDF_Contour* temp;
+
+
+ if ( !shape || !*shape )
+ return;
+
+ memory = (*shape)->memory;
+ contours = (*shape)->contours;
+
+ if ( !memory )
+ return;
+
+ /* release all contours */
+ while ( contours )
+ {
+ temp = contours;
+ contours = contours->next;
+
+ sdf_contour_done( memory, &temp );
+ }
+
+ /* release the allocated shape struct */
+ FT_FREE( *shape );
+ }
+
+
+ /**************************************************************************
+ *
+ * shape decomposition functions
+ *
+ */
+
+ /* This function is called when starting a new contour at `to`, */
+ /* which gets added to the shape's list. */
+ static FT_Error
+ sdf_move_to( const FT_26D6_Vec* to,
+ void* user )
+ {
+ SDF_Shape* shape = ( SDF_Shape* )user;
+ SDF_Contour* contour = NULL;
+
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = shape->memory;
+
+
+ if ( !to || !user )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ FT_CALL( sdf_contour_new( memory, &contour ) );
+
+ contour->last_pos = *to;
+ contour->next = shape->contours;
+ shape->contours = contour;
+
+ Exit:
+ return error;
+ }
+
+
+ /* This function is called when there is a line in the */
+ /* contour. The line starts at the previous edge point and */
+ /* stops at `to`. */
+ static FT_Error
+ sdf_line_to( const FT_26D6_Vec* to,
+ void* user )
+ {
+ SDF_Shape* shape = ( SDF_Shape* )user;
+ SDF_Edge* edge = NULL;
+ SDF_Contour* contour = NULL;
+
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = shape->memory;
+
+
+ if ( !to || !user )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ contour = shape->contours;
+
+ if ( contour->last_pos.x == to->x &&
+ contour->last_pos.y == to->y )
+ goto Exit;
+
+ FT_CALL( sdf_edge_new( memory, &edge ) );
+
+ edge->edge_type = SDF_EDGE_LINE;
+ edge->start_pos = contour->last_pos;
+ edge->end_pos = *to;
+
+ edge->next = contour->edges;
+ contour->edges = edge;
+ contour->last_pos = *to;
+
+ Exit:
+ return error;
+ }
+
+
+ /* This function is called when there is a conic Bezier curve */
+ /* in the contour. The curve starts at the previous edge point */
+ /* and stops at `to`, with control point `control_1`. */
+ static FT_Error
+ sdf_conic_to( const FT_26D6_Vec* control_1,
+ const FT_26D6_Vec* to,
+ void* user )
+ {
+ SDF_Shape* shape = ( SDF_Shape* )user;
+ SDF_Edge* edge = NULL;
+ SDF_Contour* contour = NULL;
+
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = shape->memory;
+
+
+ if ( !control_1 || !to || !user )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ contour = shape->contours;
+
+ /* If the control point coincides with any of the end points */
+ /* then it is a line and should be treated as one to avoid */
+ /* unnecessary complexity later in the algorithm. */
+ if ( ( contour->last_pos.x == control_1->x &&
+ contour->last_pos.y == control_1->y ) ||
+ ( control_1->x == to->x &&
+ control_1->y == to->y ) )
+ {
+ sdf_line_to( to, user );
+ goto Exit;
+ }
+
+ FT_CALL( sdf_edge_new( memory, &edge ) );
+
+ edge->edge_type = SDF_EDGE_CONIC;
+ edge->start_pos = contour->last_pos;
+ edge->control_a = *control_1;
+ edge->end_pos = *to;
+
+ edge->next = contour->edges;
+ contour->edges = edge;
+ contour->last_pos = *to;
+
+ Exit:
+ return error;
+ }
+
+
+ /* This function is called when there is a cubic Bezier curve */
+ /* in the contour. The curve starts at the previous edge point */
+ /* and stops at `to`, with two control points `control_1` and */
+ /* `control_2`. */
+ static FT_Error
+ sdf_cubic_to( const FT_26D6_Vec* control_1,
+ const FT_26D6_Vec* control_2,
+ const FT_26D6_Vec* to,
+ void* user )
+ {
+ SDF_Shape* shape = ( SDF_Shape* )user;
+ SDF_Edge* edge = NULL;
+ SDF_Contour* contour = NULL;
+
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = shape->memory;
+
+
+ if ( !control_2 || !control_1 || !to || !user )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ contour = shape->contours;
+
+ FT_CALL( sdf_edge_new( memory, &edge ) );
+
+ edge->edge_type = SDF_EDGE_CUBIC;
+ edge->start_pos = contour->last_pos;
+ edge->control_a = *control_1;
+ edge->control_b = *control_2;
+ edge->end_pos = *to;
+
+ edge->next = contour->edges;
+ contour->edges = edge;
+ contour->last_pos = *to;
+
+ Exit:
+ return error;
+ }
+
+
+ /* Construct the structure to hold all four outline */
+ /* decomposition functions. */
+ FT_DEFINE_OUTLINE_FUNCS(
+ sdf_decompose_funcs,
+
+ (FT_Outline_MoveTo_Func) sdf_move_to, /* move_to */
+ (FT_Outline_LineTo_Func) sdf_line_to, /* line_to */
+ (FT_Outline_ConicTo_Func)sdf_conic_to, /* conic_to */
+ (FT_Outline_CubicTo_Func)sdf_cubic_to, /* cubic_to */
+
+ 0, /* shift */
+ 0 /* delta */
+ )
+
+
+ /* Decompose `outline` and put it into the `shape` structure. */
+ static FT_Error
+ sdf_outline_decompose( FT_Outline* outline,
+ SDF_Shape* shape )
+ {
+ FT_Error error = FT_Err_Ok;
+
+
+ if ( !outline || !shape )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ error = FT_Outline_Decompose( outline,
+ &sdf_decompose_funcs,
+ (void*)shape );
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * utility functions
+ *
+ */
+
+ /* Return the control box of an edge. The control box is a rectangle */
+ /* in which all the control points can fit tightly. */
+ static FT_CBox
+ get_control_box( SDF_Edge edge )
+ {
+ FT_CBox cbox = { 0, 0, 0, 0 };
+ FT_Bool is_set = 0;
+
+
+ switch ( edge.edge_type )
+ {
+ case SDF_EDGE_CUBIC:
+ cbox.xMin = edge.control_b.x;
+ cbox.xMax = edge.control_b.x;
+ cbox.yMin = edge.control_b.y;
+ cbox.yMax = edge.control_b.y;
+
+ is_set = 1;
+ /* fall through */
+
+ case SDF_EDGE_CONIC:
+ if ( is_set )
+ {
+ cbox.xMin = edge.control_a.x < cbox.xMin
+ ? edge.control_a.x
+ : cbox.xMin;
+ cbox.xMax = edge.control_a.x > cbox.xMax
+ ? edge.control_a.x
+ : cbox.xMax;
+
+ cbox.yMin = edge.control_a.y < cbox.yMin
+ ? edge.control_a.y
+ : cbox.yMin;
+ cbox.yMax = edge.control_a.y > cbox.yMax
+ ? edge.control_a.y
+ : cbox.yMax;
+ }
+ else
+ {
+ cbox.xMin = edge.control_a.x;
+ cbox.xMax = edge.control_a.x;
+ cbox.yMin = edge.control_a.y;
+ cbox.yMax = edge.control_a.y;
+
+ is_set = 1;
+ }
+ /* fall through */
+
+ case SDF_EDGE_LINE:
+ if ( is_set )
+ {
+ cbox.xMin = edge.start_pos.x < cbox.xMin
+ ? edge.start_pos.x
+ : cbox.xMin;
+ cbox.xMax = edge.start_pos.x > cbox.xMax
+ ? edge.start_pos.x
+ : cbox.xMax;
+
+ cbox.yMin = edge.start_pos.y < cbox.yMin
+ ? edge.start_pos.y
+ : cbox.yMin;
+ cbox.yMax = edge.start_pos.y > cbox.yMax
+ ? edge.start_pos.y
+ : cbox.yMax;
+ }
+ else
+ {
+ cbox.xMin = edge.start_pos.x;
+ cbox.xMax = edge.start_pos.x;
+ cbox.yMin = edge.start_pos.y;
+ cbox.yMax = edge.start_pos.y;
+ }
+
+ cbox.xMin = edge.end_pos.x < cbox.xMin
+ ? edge.end_pos.x
+ : cbox.xMin;
+ cbox.xMax = edge.end_pos.x > cbox.xMax
+ ? edge.end_pos.x
+ : cbox.xMax;
+
+ cbox.yMin = edge.end_pos.y < cbox.yMin
+ ? edge.end_pos.y
+ : cbox.yMin;
+ cbox.yMax = edge.end_pos.y > cbox.yMax
+ ? edge.end_pos.y
+ : cbox.yMax;
+
+ break;
+
+ default:
+ break;
+ }
+
+ return cbox;
+ }
+
+
+ /* Return orientation of a single contour. */
+ /* Note that the orientation is independent of the fill rule! */
+ /* So, for TTF a clockwise-oriented contour has to be filled */
+ /* and the opposite for OTF fonts. */
+ static SDF_Contour_Orientation
+ get_contour_orientation ( SDF_Contour* contour )
+ {
+ SDF_Edge* head = NULL;
+ FT_26D6 area = 0;
+
+
+ /* return none if invalid parameters */
+ if ( !contour || !contour->edges )
+ return SDF_ORIENTATION_NONE;
+
+ head = contour->edges;
+
+ /* Calculate the area of the control box for all edges. */
+ while ( head )
+ {
+ switch ( head->edge_type )
+ {
+ case SDF_EDGE_LINE:
+ area += MUL_26D6( ( head->end_pos.x - head->start_pos.x ),
+ ( head->end_pos.y + head->start_pos.y ) );
+ break;
+
+ case SDF_EDGE_CONIC:
+ area += MUL_26D6( head->control_a.x - head->start_pos.x,
+ head->control_a.y + head->start_pos.y );
+ area += MUL_26D6( head->end_pos.x - head->control_a.x,
+ head->end_pos.y + head->control_a.y );
+ break;
+
+ case SDF_EDGE_CUBIC:
+ area += MUL_26D6( head->control_a.x - head->start_pos.x,
+ head->control_a.y + head->start_pos.y );
+ area += MUL_26D6( head->control_b.x - head->control_a.x,
+ head->control_b.y + head->control_a.y );
+ area += MUL_26D6( head->end_pos.x - head->control_b.x,
+ head->end_pos.y + head->control_b.y );
+ break;
+
+ default:
+ return SDF_ORIENTATION_NONE;
+ }
+
+ head = head->next;
+ }
+
+ /* Clockwise contours cover a positive area, and counter-clockwise */
+ /* contours cover a negative area. */
+ if ( area > 0 )
+ return SDF_ORIENTATION_CW;
+ else
+ return SDF_ORIENTATION_CCW;
+ }
+
+
+ /* This function is exactly the same as the one */
+ /* in the smooth renderer. It splits a conic */
+ /* into two conics exactly half way at t = 0.5. */
+ static void
+ split_conic( FT_26D6_Vec* base )
+ {
+ FT_26D6 a, b;
+
+
+ base[4].x = base[2].x;
+ a = base[0].x + base[1].x;
+ b = base[1].x + base[2].x;
+ base[3].x = b / 2;
+ base[2].x = ( a + b ) / 4;
+ base[1].x = a / 2;
+
+ base[4].y = base[2].y;
+ a = base[0].y + base[1].y;
+ b = base[1].y + base[2].y;
+ base[3].y = b / 2;
+ base[2].y = ( a + b ) / 4;
+ base[1].y = a / 2;
+ }
+
+
+ /* This function is exactly the same as the one */
+ /* in the smooth renderer. It splits a cubic */
+ /* into two cubics exactly half way at t = 0.5. */
+ static void
+ split_cubic( FT_26D6_Vec* base )
+ {
+ FT_26D6 a, b, c;
+
+
+ base[6].x = base[3].x;
+ a = base[0].x + base[1].x;
+ b = base[1].x + base[2].x;
+ c = base[2].x + base[3].x;
+ base[5].x = c / 2;
+ c += b;
+ base[4].x = c / 4;
+ base[1].x = a / 2;
+ a += b;
+ base[2].x = a / 4;
+ base[3].x = ( a + c ) / 8;
+
+ base[6].y = base[3].y;
+ a = base[0].y + base[1].y;
+ b = base[1].y + base[2].y;
+ c = base[2].y + base[3].y;
+ base[5].y = c / 2;
+ c += b;
+ base[4].y = c / 4;
+ base[1].y = a / 2;
+ a += b;
+ base[2].y = a / 4;
+ base[3].y = ( a + c ) / 8;
+ }
+
+
+ /* Split a conic Bezier curve into a number of lines */
+ /* and add them to `out'. */
+ /* */
+ /* This function uses recursion; we thus need */
+ /* parameter `max_splits' for stopping. */
+ static FT_Error
+ split_sdf_conic( FT_Memory memory,
+ FT_26D6_Vec* control_points,
+ FT_UInt max_splits,
+ SDF_Edge** out )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_26D6_Vec cpos[5];
+ SDF_Edge* left,* right;
+
+
+ if ( !memory || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* split conic outline */
+ cpos[0] = control_points[0];
+ cpos[1] = control_points[1];
+ cpos[2] = control_points[2];
+
+ split_conic( cpos );
+
+ /* If max number of splits is done */
+ /* then stop and add the lines to */
+ /* the list. */
+ if ( max_splits <= 2 )
+ goto Append;
+
+ /* Otherwise keep splitting. */
+ FT_CALL( split_sdf_conic( memory, &cpos[0], max_splits / 2, out ) );
+ FT_CALL( split_sdf_conic( memory, &cpos[2], max_splits / 2, out ) );
+
+ /* [NOTE]: This is not an efficient way of */
+ /* splitting the curve. Check the deviation */
+ /* instead and stop if the deviation is less */
+ /* than a pixel. */
+
+ goto Exit;
+
+ Append:
+ /* Do allocation and add the lines to the list. */
+
+ FT_CALL( sdf_edge_new( memory, &left ) );
+ FT_CALL( sdf_edge_new( memory, &right ) );
+
+ left->start_pos = cpos[0];
+ left->end_pos = cpos[2];
+ left->edge_type = SDF_EDGE_LINE;
+
+ right->start_pos = cpos[2];
+ right->end_pos = cpos[4];
+ right->edge_type = SDF_EDGE_LINE;
+
+ left->next = right;
+ right->next = (*out);
+ *out = left;
+
+ Exit:
+ return error;
+ }
+
+
+ /* Split a cubic Bezier curve into a number of lines */
+ /* and add them to `out`. */
+ /* */
+ /* This function uses recursion; we thus need */
+ /* parameter `max_splits' for stopping. */
+ static FT_Error
+ split_sdf_cubic( FT_Memory memory,
+ FT_26D6_Vec* control_points,
+ FT_UInt max_splits,
+ SDF_Edge** out )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_26D6_Vec cpos[7];
+ SDF_Edge* left, *right;
+ const FT_26D6 threshold = ONE_PIXEL / 4;
+
+
+ if ( !memory || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* split the cubic */
+ cpos[0] = control_points[0];
+ cpos[1] = control_points[1];
+ cpos[2] = control_points[2];
+ cpos[3] = control_points[3];
+
+ /* If the segment is flat enough we won't get any benefit by */
+ /* splitting it further, so we can just stop splitting. */
+ /* */
+ /* Check the deviation of the Bezier curve and stop if it is */
+ /* smaller than the pre-defined `threshold` value. */
+ if ( FT_ABS( 2 * cpos[0].x - 3 * cpos[1].x + cpos[3].x ) < threshold &&
+ FT_ABS( 2 * cpos[0].y - 3 * cpos[1].y + cpos[3].y ) < threshold &&
+ FT_ABS( cpos[0].x - 3 * cpos[2].x + 2 * cpos[3].x ) < threshold &&
+ FT_ABS( cpos[0].y - 3 * cpos[2].y + 2 * cpos[3].y ) < threshold )
+ {
+ split_cubic( cpos );
+ goto Append;
+ }
+
+ split_cubic( cpos );
+
+ /* If max number of splits is done */
+ /* then stop and add the lines to */
+ /* the list. */
+ if ( max_splits <= 2 )
+ goto Append;
+
+ /* Otherwise keep splitting. */
+ FT_CALL( split_sdf_cubic( memory, &cpos[0], max_splits / 2, out ) );
+ FT_CALL( split_sdf_cubic( memory, &cpos[3], max_splits / 2, out ) );
+
+ /* [NOTE]: This is not an efficient way of */
+ /* splitting the curve. Check the deviation */
+ /* instead and stop if the deviation is less */
+ /* than a pixel. */
+
+ goto Exit;
+
+ Append:
+ /* Do allocation and add the lines to the list. */
+
+ FT_CALL( sdf_edge_new( memory, &left) );
+ FT_CALL( sdf_edge_new( memory, &right) );
+
+ left->start_pos = cpos[0];
+ left->end_pos = cpos[3];
+ left->edge_type = SDF_EDGE_LINE;
+
+ right->start_pos = cpos[3];
+ right->end_pos = cpos[6];
+ right->edge_type = SDF_EDGE_LINE;
+
+ left->next = right;
+ right->next = (*out);
+ *out = left;
+
+ Exit:
+ return error;
+ }
+
+
+ /* Subdivide an entire shape into line segments */
+ /* such that it doesn't look visually different */
+ /* from the original curve. */
+ static FT_Error
+ split_sdf_shape( SDF_Shape* shape )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory;
+
+ SDF_Contour* contours;
+ SDF_Contour* new_contours = NULL;
+
+
+ if ( !shape || !shape->memory )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ contours = shape->contours;
+ memory = shape->memory;
+
+ /* for each contour */
+ while ( contours )
+ {
+ SDF_Edge* edges = contours->edges;
+ SDF_Edge* new_edges = NULL;
+
+ SDF_Contour* tempc;
+
+
+ /* for each edge */
+ while ( edges )
+ {
+ SDF_Edge* edge = edges;
+ SDF_Edge* temp;
+
+ switch ( edge->edge_type )
+ {
+ case SDF_EDGE_LINE:
+ /* Just create a duplicate edge in case */
+ /* it is a line. We can use the same edge. */
+ FT_CALL( sdf_edge_new( memory, &temp ) );
+
+ ft_memcpy( temp, edge, sizeof ( *edge ) );
+
+ temp->next = new_edges;
+ new_edges = temp;
+ break;
+
+ case SDF_EDGE_CONIC:
+ /* Subdivide the curve and add it to the list. */
+ {
+ FT_26D6_Vec ctrls[3];
+ FT_26D6 dx, dy;
+ FT_UInt num_splits;
+
+
+ ctrls[0] = edge->start_pos;
+ ctrls[1] = edge->control_a;
+ ctrls[2] = edge->end_pos;
+
+ dx = FT_ABS( ctrls[2].x + ctrls[0].x - 2 * ctrls[1].x );
+ dy = FT_ABS( ctrls[2].y + ctrls[0].y - 2 * ctrls[1].y );
+ if ( dx < dy )
+ dx = dy;
+
+ /* Calculate the number of necessary bisections. Each */
+ /* bisection causes a four-fold reduction of the deviation, */
+ /* hence we bisect the Bezier curve until the deviation */
+ /* becomes less than 1/8th of a pixel. For more details */
+ /* check file `ftgrays.c`. */
+ num_splits = 1;
+ while ( dx > ONE_PIXEL / 8 )
+ {
+ dx >>= 2;
+ num_splits <<= 1;
+ }
+
+ error = split_sdf_conic( memory, ctrls, num_splits, &new_edges );
+ }
+ break;
+
+ case SDF_EDGE_CUBIC:
+ /* Subdivide the curve and add it to the list. */
+ {
+ FT_26D6_Vec ctrls[4];
+
+
+ ctrls[0] = edge->start_pos;
+ ctrls[1] = edge->control_a;
+ ctrls[2] = edge->control_b;
+ ctrls[3] = edge->end_pos;
+
+ error = split_sdf_cubic( memory, ctrls, 32, &new_edges );
+ }
+ break;
+
+ default:
+ error = FT_THROW( Invalid_Argument );
+ }
+
+ if ( error != FT_Err_Ok )
+ goto Exit;
+
+ edges = edges->next;
+ }
+
+ /* add to the contours list */
+ FT_CALL( sdf_contour_new( memory, &tempc ) );
+
+ tempc->next = new_contours;
+ tempc->edges = new_edges;
+ new_contours = tempc;
+ new_edges = NULL;
+
+ /* deallocate the contour */
+ tempc = contours;
+ contours = contours->next;
+
+ sdf_contour_done( memory, &tempc );
+ }
+
+ shape->contours = new_contours;
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * for debugging
+ *
+ */
+
+#ifdef FT_DEBUG_LEVEL_TRACE
+
+ static void
+ sdf_shape_dump( SDF_Shape* shape )
+ {
+ FT_UInt num_contours = 0;
+
+ FT_UInt total_edges = 0;
+ FT_UInt total_lines = 0;
+ FT_UInt total_conic = 0;
+ FT_UInt total_cubic = 0;
+
+ SDF_Contour* contour_list;
+
+
+ if ( !shape )
+ {
+ FT_TRACE5(( "sdf_shape_dump: null shape\n" ));
+ return;
+ }
+
+ contour_list = shape->contours;
+
+ FT_TRACE5(( "sdf_shape_dump (values are in 26.6 format):\n" ));
+
+ while ( contour_list )
+ {
+ FT_UInt num_edges = 0;
+ SDF_Edge* edge_list;
+ SDF_Contour* contour = contour_list;
+
+
+ FT_TRACE5(( " Contour %d\n", num_contours ));
+
+ edge_list = contour->edges;
+
+ while ( edge_list )
+ {
+ SDF_Edge* edge = edge_list;
+
+
+ FT_TRACE5(( " %3d: ", num_edges ));
+
+ switch ( edge->edge_type )
+ {
+ case SDF_EDGE_LINE:
+ FT_TRACE5(( "Line: (%ld, %ld) -- (%ld, %ld)\n",
+ edge->start_pos.x, edge->start_pos.y,
+ edge->end_pos.x, edge->end_pos.y ));
+ total_lines++;
+ break;
+
+ case SDF_EDGE_CONIC:
+ FT_TRACE5(( "Conic: (%ld, %ld) .. (%ld, %ld) .. (%ld, %ld)\n",
+ edge->start_pos.x, edge->start_pos.y,
+ edge->control_a.x, edge->control_a.y,
+ edge->end_pos.x, edge->end_pos.y ));
+ total_conic++;
+ break;
+
+ case SDF_EDGE_CUBIC:
+ FT_TRACE5(( "Cubic: (%ld, %ld) .. (%ld, %ld)"
+ " .. (%ld, %ld) .. (%ld %ld)\n",
+ edge->start_pos.x, edge->start_pos.y,
+ edge->control_a.x, edge->control_a.y,
+ edge->control_b.x, edge->control_b.y,
+ edge->end_pos.x, edge->end_pos.y ));
+ total_cubic++;
+ break;
+
+ default:
+ break;
+ }
+
+ num_edges++;
+ total_edges++;
+ edge_list = edge_list->next;
+ }
+
+ num_contours++;
+ contour_list = contour_list->next;
+ }
+
+ FT_TRACE5(( "\n" ));
+ FT_TRACE5(( " total number of contours = %d\n", num_contours ));
+ FT_TRACE5(( " total number of edges = %d\n", total_edges ));
+ FT_TRACE5(( " |__lines = %d\n", total_lines ));
+ FT_TRACE5(( " |__conic = %d\n", total_conic ));
+ FT_TRACE5(( " |__cubic = %d\n", total_cubic ));
+ }
+
+#endif /* FT_DEBUG_LEVEL_TRACE */
+
+
+ /**************************************************************************
+ *
+ * math functions
+ *
+ */
+
+#if !USE_NEWTON_FOR_CONIC
+
+ /* [NOTE]: All the functions below down until rasterizer */
+ /* can be avoided if we decide to subdivide the */
+ /* curve into lines. */
+
+ /* This function uses Newton's iteration to find */
+ /* the cube root of a fixed-point integer. */
+ static FT_16D16
+ cube_root( FT_16D16 val )
+ {
+ /* [IMPORTANT]: This function is not good as it may */
+ /* not break, so use a lookup table instead. Or we */
+ /* can use an algorithm similar to `square_root`. */
+
+ FT_Int v, g, c;
+
+
+ if ( val == 0 ||
+ val == -FT_INT_16D16( 1 ) ||
+ val == FT_INT_16D16( 1 ) )
+ return val;
+
+ v = val < 0 ? -val : val;
+ g = square_root( v );
+ c = 0;
+
+ while ( 1 )
+ {
+ c = FT_MulFix( FT_MulFix( g, g ), g ) - v;
+ c = FT_DivFix( c, 3 * FT_MulFix( g, g ) );
+
+ g -= c;
+
+ if ( ( c < 0 ? -c : c ) < 30 )
+ break;
+ }
+
+ return val < 0 ? -g : g;
+ }
+
+
+ /* Calculate the perpendicular by using '1 - base^2'. */
+ /* Then use arctan to compute the angle. */
+ static FT_16D16
+ arc_cos( FT_16D16 val )
+ {
+ FT_16D16 p;
+ FT_16D16 b = val;
+ FT_16D16 one = FT_INT_16D16( 1 );
+
+
+ if ( b > one )
+ b = one;
+ if ( b < -one )
+ b = -one;
+
+ p = one - FT_MulFix( b, b );
+ p = square_root( p );
+
+ return FT_Atan2( b, p );
+ }
+
+
+ /* Compute roots of a quadratic polynomial, assign them to `out`, */
+ /* and return number of real roots. */
+ /* */
+ /* The procedure can be found at */
+ /* */
+ /* https://mathworld.wolfram.com/QuadraticFormula.html */
+ static FT_UShort
+ solve_quadratic_equation( FT_26D6 a,
+ FT_26D6 b,
+ FT_26D6 c,
+ FT_16D16 out[2] )
+ {
+ FT_16D16 discriminant = 0;
+
+
+ a = FT_26D6_16D16( a );
+ b = FT_26D6_16D16( b );
+ c = FT_26D6_16D16( c );
+
+ if ( a == 0 )
+ {
+ if ( b == 0 )
+ return 0;
+ else
+ {
+ out[0] = FT_DivFix( -c, b );
+
+ return 1;
+ }
+ }
+
+ discriminant = FT_MulFix( b, b ) - 4 * FT_MulFix( a, c );
+
+ if ( discriminant < 0 )
+ return 0;
+ else if ( discriminant == 0 )
+ {
+ out[0] = FT_DivFix( -b, 2 * a );
+
+ return 1;
+ }
+ else
+ {
+ discriminant = square_root( discriminant );
+
+ out[0] = FT_DivFix( -b + discriminant, 2 * a );
+ out[1] = FT_DivFix( -b - discriminant, 2 * a );
+
+ return 2;
+ }
+ }
+
+
+ /* Compute roots of a cubic polynomial, assign them to `out`, */
+ /* and return number of real roots. */
+ /* */
+ /* The procedure can be found at */
+ /* */
+ /* https://mathworld.wolfram.com/CubicFormula.html */
+ static FT_UShort
+ solve_cubic_equation( FT_26D6 a,
+ FT_26D6 b,
+ FT_26D6 c,
+ FT_26D6 d,
+ FT_16D16 out[3] )
+ {
+ FT_16D16 q = 0; /* intermediate */
+ FT_16D16 r = 0; /* intermediate */
+
+ FT_16D16 a2 = b; /* x^2 coefficients */
+ FT_16D16 a1 = c; /* x coefficients */
+ FT_16D16 a0 = d; /* constant */
+
+ FT_16D16 q3 = 0;
+ FT_16D16 r2 = 0;
+ FT_16D16 a23 = 0;
+ FT_16D16 a22 = 0;
+ FT_16D16 a1x2 = 0;
+
+
+ /* cutoff value for `a` to be a cubic, otherwise solve quadratic */
+ if ( a == 0 || FT_ABS( a ) < 16 )
+ return solve_quadratic_equation( b, c, d, out );
+
+ if ( d == 0 )
+ {
+ out[0] = 0;
+
+ return solve_quadratic_equation( a, b, c, out + 1 ) + 1;
+ }
+
+ /* normalize the coefficients; this also makes them 16.16 */
+ a2 = FT_DivFix( a2, a );
+ a1 = FT_DivFix( a1, a );
+ a0 = FT_DivFix( a0, a );
+
+ /* compute intermediates */
+ a1x2 = FT_MulFix( a1, a2 );
+ a22 = FT_MulFix( a2, a2 );
+ a23 = FT_MulFix( a22, a2 );
+
+ q = ( 3 * a1 - a22 ) / 9;
+ r = ( 9 * a1x2 - 27 * a0 - 2 * a23 ) / 54;
+
+ /* [BUG]: `q3` and `r2` still cause underflow. */
+
+ q3 = FT_MulFix( q, q );
+ q3 = FT_MulFix( q3, q );
+
+ r2 = FT_MulFix( r, r );
+
+ if ( q3 < 0 && r2 < -q3 )
+ {
+ FT_16D16 t = 0;
+
+
+ q3 = square_root( -q3 );
+ t = FT_DivFix( r, q3 );
+
+ if ( t > ( 1 << 16 ) )
+ t = ( 1 << 16 );
+ if ( t < -( 1 << 16 ) )
+ t = -( 1 << 16 );
+
+ t = arc_cos( t );
+ a2 /= 3;
+ q = 2 * square_root( -q );
+
+ out[0] = FT_MulFix( q, FT_Cos( t / 3 ) ) - a2;
+ out[1] = FT_MulFix( q, FT_Cos( ( t + FT_ANGLE_PI * 2 ) / 3 ) ) - a2;
+ out[2] = FT_MulFix( q, FT_Cos( ( t + FT_ANGLE_PI * 4 ) / 3 ) ) - a2;
+
+ return 3;
+ }
+
+ else if ( r2 == -q3 )
+ {
+ FT_16D16 s = 0;
+
+
+ s = cube_root( r );
+ a2 /= -3;
+
+ out[0] = a2 + ( 2 * s );
+ out[1] = a2 - s;
+
+ return 2;
+ }
+
+ else
+ {
+ FT_16D16 s = 0;
+ FT_16D16 t = 0;
+ FT_16D16 dis = 0;
+
+
+ if ( q3 == 0 )
+ dis = FT_ABS( r );
+ else
+ dis = square_root( q3 + r2 );
+
+ s = cube_root( r + dis );
+ t = cube_root( r - dis );
+ a2 /= -3;
+ out[0] = ( a2 + ( s + t ) );
+
+ return 1;
+ }
+ }
+
+#endif /* !USE_NEWTON_FOR_CONIC */
+
+
+ /*************************************************************************/
+ /*************************************************************************/
+ /** **/
+ /** RASTERIZER **/
+ /** **/
+ /*************************************************************************/
+ /*************************************************************************/
+
+ /**************************************************************************
+ *
+ * @Function:
+ * resolve_corner
+ *
+ * @Description:
+ * At some places on the grid two edges can give opposite directions;
+ * this happens when the closest point is on one of the endpoint. In
+ * that case we need to check the proper sign.
+ *
+ * This can be visualized by an example:
+ *
+ * ```
+ * x
+ *
+ * o
+ * ^ \
+ * / \
+ * / \
+ * (a) / \ (b)
+ * / \
+ * / \
+ * / v
+ * ```
+ *
+ * Suppose `x` is the point whose shortest distance from an arbitrary
+ * contour we want to find out. It is clear that `o` is the nearest
+ * point on the contour. Now to determine the sign we do a cross
+ * product of the shortest distance vector and the edge direction, i.e.,
+ *
+ * ```
+ * => sign = cross(x - o, direction(a))
+ * ```
+ *
+ * Using the right hand thumb rule we can see that the sign will be
+ * positive.
+ *
+ * If we use `b', however, we have
+ *
+ * ```
+ * => sign = cross(x - o, direction(b))
+ * ```
+ *
+ * In this case the sign will be negative. To determine the correct
+ * sign we thus divide the plane in two halves and check which plane the
+ * point lies in.
+ *
+ * ```
+ * |
+ * x |
+ * |
+ * o
+ * ^|\
+ * / | \
+ * / | \
+ * (a) / | \ (b)
+ * / | \
+ * / \
+ * / v
+ * ```
+ *
+ * We can see that `x` lies in the plane of `a`, so we take the sign
+ * determined by `a`. This test can be easily done by calculating the
+ * orthogonality and taking the greater one.
+ *
+ * The orthogonality is simply the sinus of the two vectors (i.e.,
+ * x - o) and the corresponding direction. We efficiently pre-compute
+ * the orthogonality with the corresponding `get_min_distance_*`
+ * functions.
+ *
+ * @Input:
+ * sdf1 ::
+ * First signed distance (can be any of `a` or `b`).
+ *
+ * sdf1 ::
+ * Second signed distance (can be any of `a` or `b`).
+ *
+ * @Return:
+ * The correct signed distance, which is computed by using the above
+ * algorithm.
+ *
+ * @Note:
+ * The function does not care about the actual distance, it simply
+ * returns the signed distance which has a larger cross product. As a
+ * consequence, this function should not be used if the two distances
+ * are fairly apart. In that case simply use the signed distance with
+ * a shorter absolute distance.
+ *
+ */
+ static SDF_Signed_Distance
+ resolve_corner( SDF_Signed_Distance sdf1,
+ SDF_Signed_Distance sdf2 )
+ {
+ return FT_ABS( sdf1.cross ) > FT_ABS( sdf2.cross ) ? sdf1 : sdf2;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * get_min_distance_line
+ *
+ * @Description:
+ * Find the shortest distance from the `line` segment to a given `point`
+ * and assign it to `out`. Use it for line segments only.
+ *
+ * @Input:
+ * line ::
+ * The line segment to which the shortest distance is to be computed.
+ *
+ * point ::
+ * Point from which the shortest distance is to be computed.
+ *
+ * @Output:
+ * out ::
+ * Signed distance from `point` to `line`.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ * @Note:
+ * The `line' parameter must have an edge type of `SDF_EDGE_LINE`.
+ *
+ */
+ static FT_Error
+ get_min_distance_line( SDF_Edge* line,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ /*
+ * In order to calculate the shortest distance from a point to
+ * a line segment, we do the following. Let's assume that
+ *
+ * ```
+ * a = start point of the line segment
+ * b = end point of the line segment
+ * p = point from which shortest distance is to be calculated
+ * ```
+ *
+ * (1) Write the parametric equation of the line.
+ *
+ * ```
+ * point_on_line = a + (b - a) * t (t is the factor)
+ * ```
+ *
+ * (2) Find the projection of point `p` on the line. The projection
+ * will be perpendicular to the line, which allows us to get the
+ * solution by making the dot product zero.
+ *
+ * ```
+ * (point_on_line - a) . (p - point_on_line) = 0
+ *
+ * (point_on_line)
+ * (a) x-------o----------------x (b)
+ * |_|
+ * |
+ * |
+ * (p)
+ * ```
+ *
+ * (3) Simplification of the above equation yields the factor of
+ * `point_on_line`:
+ *
+ * ```
+ * t = ((p - a) . (b - a)) / |b - a|^2
+ * ```
+ *
+ * (4) We clamp factor `t` between [0.0f, 1.0f] because `point_on_line`
+ * can be outside of the line segment:
+ *
+ * ```
+ * (point_on_line)
+ * (a) x------------------------x (b) -----o---
+ * |_|
+ * |
+ * |
+ * (p)
+ * ```
+ *
+ * (5) Finally, the distance we are interested in is
+ *
+ * ```
+ * |point_on_line - p|
+ * ```
+ */
+
+ FT_Error error = FT_Err_Ok;
+
+ FT_Vector a; /* start position */
+ FT_Vector b; /* end position */
+ FT_Vector p; /* current point */
+
+ FT_26D6_Vec line_segment; /* `b` - `a` */
+ FT_26D6_Vec p_sub_a; /* `p` - `a` */
+
+ FT_26D6 sq_line_length; /* squared length of `line_segment` */
+ FT_16D16 factor; /* factor of the nearest point */
+ FT_26D6 cross; /* used to determine sign */
+
+ FT_16D16_Vec nearest_point; /* `point_on_line` */
+ FT_16D16_Vec nearest_vector; /* `p` - `nearest_point` */
+
+
+ if ( !line || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( line->edge_type != SDF_EDGE_LINE )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ a = line->start_pos;
+ b = line->end_pos;
+ p = point;
+
+ line_segment.x = b.x - a.x;
+ line_segment.y = b.y - a.y;
+
+ p_sub_a.x = p.x - a.x;
+ p_sub_a.y = p.y - a.y;
+
+ sq_line_length = ( line_segment.x * line_segment.x ) / 64 +
+ ( line_segment.y * line_segment.y ) / 64;
+
+ /* currently factor is 26.6 */
+ factor = ( p_sub_a.x * line_segment.x ) / 64 +
+ ( p_sub_a.y * line_segment.y ) / 64;
+
+ /* now factor is 16.16 */
+ factor = FT_DivFix( factor, sq_line_length );
+
+ /* clamp the factor between 0.0 and 1.0 in fixed point */
+ if ( factor > FT_INT_16D16( 1 ) )
+ factor = FT_INT_16D16( 1 );
+ if ( factor < 0 )
+ factor = 0;
+
+ nearest_point.x = FT_MulFix( FT_26D6_16D16( line_segment.x ),
+ factor );
+ nearest_point.y = FT_MulFix( FT_26D6_16D16( line_segment.y ),
+ factor );
+
+ nearest_point.x = FT_26D6_16D16( a.x ) + nearest_point.x;
+ nearest_point.y = FT_26D6_16D16( a.y ) + nearest_point.y;
+
+ nearest_vector.x = nearest_point.x - FT_26D6_16D16( p.x );
+ nearest_vector.y = nearest_point.y - FT_26D6_16D16( p.y );
+
+ cross = FT_MulFix( nearest_vector.x, line_segment.y ) -
+ FT_MulFix( nearest_vector.y, line_segment.x );
+
+ /* assign the output */
+ out->sign = cross < 0 ? 1 : -1;
+ out->distance = VECTOR_LENGTH_16D16( nearest_vector );
+
+ /* Instead of finding `cross` for checking corner we */
+ /* directly set it here. This is more efficient */
+ /* because if the distance is perpendicular we can */
+ /* directly set it to 1. */
+ if ( factor != 0 && factor != FT_INT_16D16( 1 ) )
+ out->cross = FT_INT_16D16( 1 );
+ else
+ {
+ /* [OPTIMIZATION]: Pre-compute this direction. */
+ /* If not perpendicular then compute `cross`. */
+ FT_Vector_NormLen( &line_segment );
+ FT_Vector_NormLen( &nearest_vector );
+
+ out->cross = FT_MulFix( line_segment.x, nearest_vector.y ) -
+ FT_MulFix( line_segment.y, nearest_vector.x );
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * get_min_distance_conic
+ *
+ * @Description:
+ * Find the shortest distance from the `conic` Bezier curve to a given
+ * `point` and assign it to `out`. Use it for conic/quadratic curves
+ * only.
+ *
+ * @Input:
+ * conic ::
+ * The conic Bezier curve to which the shortest distance is to be
+ * computed.
+ *
+ * point ::
+ * Point from which the shortest distance is to be computed.
+ *
+ * @Output:
+ * out ::
+ * Signed distance from `point` to `conic`.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ * @Note:
+ * The `conic` parameter must have an edge type of `SDF_EDGE_CONIC`.
+ *
+ */
+
+#if !USE_NEWTON_FOR_CONIC
+
+ /*
+ * The function uses an analytical method to find the shortest distance
+ * which is faster than the Newton-Raphson method, but has underflows at
+ * the moment. Use Newton's method if you can see artifacts in the SDF.
+ */
+ static FT_Error
+ get_min_distance_conic( SDF_Edge* conic,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ /*
+ * The procedure to find the shortest distance from a point to a
+ * quadratic Bezier curve is similar to the line segment algorithm. The
+ * shortest distance is perpendicular to the Bezier curve; the only
+ * difference from line is that there can be more than one
+ * perpendicular, and we also have to check the endpoints, because the
+ * perpendicular may not be the shortest.
+ *
+ * Let's assume that
+ * ```
+ * p0 = first endpoint
+ * p1 = control point
+ * p2 = second endpoint
+ * p = point from which shortest distance is to be calculated
+ * ```
+ *
+ * (1) The equation of a quadratic Bezier curve can be written as
+ *
+ * ```
+ * B(t) = (1 - t)^2 * p0 + 2(1 - t)t * p1 + t^2 * p2
+ * ```
+ *
+ * with `t` a factor in the range [0.0f, 1.0f]. This equation can
+ * be rewritten as
+ *
+ * ```
+ * B(t) = t^2 * (p0 - 2p1 + p2) + 2t * (p1 - p0) + p0
+ * ```
+ *
+ * With
+ *
+ * ```
+ * A = p0 - 2p1 + p2
+ * B = p1 - p0
+ * ```
+ *
+ * we have
+ *
+ * ```
+ * B(t) = t^2 * A + 2t * B + p0
+ * ```
+ *
+ * (2) The derivative of the last equation above is
+ *
+ * ```
+ * B'(t) = 2 *(tA + B)
+ * ```
+ *
+ * (3) To find the shortest distance from `p` to `B(t)` we find the
+ * point on the curve at which the shortest distance vector (i.e.,
+ * `B(t) - p`) and the direction (i.e., `B'(t)`) make 90 degrees.
+ * In other words, we make the dot product zero.
+ *
+ * ```
+ * (B(t) - p) . (B'(t)) = 0
+ * (t^2 * A + 2t * B + p0 - p) . (2 * (tA + B)) = 0
+ * ```
+ *
+ * After simplifying we get a cubic equation
+ *
+ * ```
+ * at^3 + bt^2 + ct + d = 0
+ * ```
+ *
+ * with
+ *
+ * ```
+ * a = A.A
+ * b = 3A.B
+ * c = 2B.B + A.p0 - A.p
+ * d = p0.B - p.B
+ * ```
+ *
+ * (4) Now the roots of the equation can be computed using 'Cardano's
+ * Cubic formula'; we clamp the roots in the range [0.0f, 1.0f].
+ *
+ * [note]: `B` and `B(t)` are different in the above equations.
+ */
+
+ FT_Error error = FT_Err_Ok;
+
+ FT_26D6_Vec aA, bB; /* A, B in the above comment */
+ FT_26D6_Vec nearest_point; /* point on curve nearest to `point` */
+ FT_26D6_Vec direction; /* direction of curve at `nearest_point` */
+
+ FT_26D6_Vec p0, p1, p2; /* control points of a conic curve */
+ FT_26D6_Vec p; /* `point` to which shortest distance */
+
+ FT_26D6 a, b, c, d; /* cubic coefficients */
+
+ FT_16D16 roots[3] = { 0, 0, 0 }; /* real roots of the cubic eq. */
+ FT_16D16 min_factor; /* factor at `nearest_point` */
+ FT_16D16 cross; /* to determine the sign */
+ FT_16D16 min = FT_INT_MAX; /* shortest squared distance */
+
+ FT_UShort num_roots; /* number of real roots of cubic */
+ FT_UShort i;
+
+
+ if ( !conic || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( conic->edge_type != SDF_EDGE_CONIC )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ p0 = conic->start_pos;
+ p1 = conic->control_a;
+ p2 = conic->end_pos;
+ p = point;
+
+ /* compute substitution coefficients */
+ aA.x = p0.x - 2 * p1.x + p2.x;
+ aA.y = p0.y - 2 * p1.y + p2.y;
+
+ bB.x = p1.x - p0.x;
+ bB.y = p1.y - p0.y;
+
+ /* compute cubic coefficients */
+ a = VEC_26D6_DOT( aA, aA );
+
+ b = 3 * VEC_26D6_DOT( aA, bB );
+
+ c = 2 * VEC_26D6_DOT( bB, bB ) +
+ VEC_26D6_DOT( aA, p0 ) -
+ VEC_26D6_DOT( aA, p );
+
+ d = VEC_26D6_DOT( p0, bB ) -
+ VEC_26D6_DOT( p, bB );
+
+ /* find the roots */
+ num_roots = solve_cubic_equation( a, b, c, d, roots );
+
+ if ( num_roots == 0 )
+ {
+ roots[0] = 0;
+ roots[1] = FT_INT_16D16( 1 );
+ num_roots = 2;
+ }
+
+ /* [OPTIMIZATION]: Check the roots, clamp them and discard */
+ /* duplicate roots. */
+
+ /* convert these values to 16.16 for further computation */
+ aA.x = FT_26D6_16D16( aA.x );
+ aA.y = FT_26D6_16D16( aA.y );
+
+ bB.x = FT_26D6_16D16( bB.x );
+ bB.y = FT_26D6_16D16( bB.y );
+
+ p0.x = FT_26D6_16D16( p0.x );
+ p0.y = FT_26D6_16D16( p0.y );
+
+ p.x = FT_26D6_16D16( p.x );
+ p.y = FT_26D6_16D16( p.y );
+
+ for ( i = 0; i < num_roots; i++ )
+ {
+ FT_16D16 t = roots[i];
+ FT_16D16 t2 = 0;
+ FT_16D16 dist = 0;
+
+ FT_16D16_Vec curve_point;
+ FT_16D16_Vec dist_vector;
+
+ /*
+ * Ideally we should discard the roots which are outside the range
+ * [0.0, 1.0] and check the endpoints of the Bezier curve, but Behdad
+ * Esfahbod proved the following lemma.
+ *
+ * Lemma:
+ *
+ * (1) If the closest point on the curve [0, 1] is to the endpoint at
+ * `t` = 1 and the cubic has no real roots at `t` = 1 then the
+ * cubic must have a real root at some `t` > 1.
+ *
+ * (2) Similarly, if the closest point on the curve [0, 1] is to the
+ * endpoint at `t` = 0 and the cubic has no real roots at `t` = 0
+ * then the cubic must have a real root at some `t` < 0.
+ *
+ * Now because of this lemma we only need to clamp the roots and that
+ * will take care of the endpoints.
+ *
+ * For more details see
+ *
+ * https://lists.nongnu.org/archive/html/freetype-devel/2020-06/msg00147.html
+ */
+
+ if ( t < 0 )
+ t = 0;
+ if ( t > FT_INT_16D16( 1 ) )
+ t = FT_INT_16D16( 1 );
+
+ t2 = FT_MulFix( t, t );
+
+ /* B(t) = t^2 * A + 2t * B + p0 - p */
+ curve_point.x = FT_MulFix( aA.x, t2 ) +
+ 2 * FT_MulFix( bB.x, t ) + p0.x;
+ curve_point.y = FT_MulFix( aA.y, t2 ) +
+ 2 * FT_MulFix( bB.y, t ) + p0.y;
+
+ /* `curve_point` - `p` */
+ dist_vector.x = curve_point.x - p.x;
+ dist_vector.y = curve_point.y - p.y;
+
+ dist = VECTOR_LENGTH_16D16( dist_vector );
+
+ if ( dist < min )
+ {
+ min = dist;
+ nearest_point = curve_point;
+ min_factor = t;
+ }
+ }
+
+ /* B'(t) = 2 * (tA + B) */
+ direction.x = 2 * FT_MulFix( aA.x, min_factor ) + 2 * bB.x;
+ direction.y = 2 * FT_MulFix( aA.y, min_factor ) + 2 * bB.y;
+
+ /* determine the sign */
+ cross = FT_MulFix( nearest_point.x - p.x, direction.y ) -
+ FT_MulFix( nearest_point.y - p.y, direction.x );
+
+ /* assign the values */
+ out->distance = min;
+ out->sign = cross < 0 ? 1 : -1;
+
+ if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) )
+ out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */
+ else
+ {
+ /* convert to nearest vector */
+ nearest_point.x -= FT_26D6_16D16( p.x );
+ nearest_point.y -= FT_26D6_16D16( p.y );
+
+ /* compute `cross` if not perpendicular */
+ FT_Vector_NormLen( &direction );
+ FT_Vector_NormLen( &nearest_point );
+
+ out->cross = FT_MulFix( direction.x, nearest_point.y ) -
+ FT_MulFix( direction.y, nearest_point.x );
+ }
+
+ Exit:
+ return error;
+ }
+
+#else /* USE_NEWTON_FOR_CONIC */
+
+ /*
+ * The function uses Newton's approximation to find the shortest distance,
+ * which is a bit slower than the analytical method but doesn't cause
+ * underflow.
+ */
+ static FT_Error
+ get_min_distance_conic( SDF_Edge* conic,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ /*
+ * This method uses Newton-Raphson's approximation to find the shortest
+ * distance from a point to a conic curve. It does not involve solving
+ * any cubic equation, that is why there is no risk of underflow.
+ *
+ * Let's assume that
+ *
+ * ```
+ * p0 = first endpoint
+ * p1 = control point
+ * p3 = second endpoint
+ * p = point from which shortest distance is to be calculated
+ * ```
+ *
+ * (1) The equation of a quadratic Bezier curve can be written as
+ *
+ * ```
+ * B(t) = (1 - t)^2 * p0 + 2(1 - t)t * p1 + t^2 * p2
+ * ```
+ *
+ * with `t` the factor in the range [0.0f, 1.0f]. The above
+ * equation can be rewritten as
+ *
+ * ```
+ * B(t) = t^2 * (p0 - 2p1 + p2) + 2t * (p1 - p0) + p0
+ * ```
+ *
+ * With
+ *
+ * ```
+ * A = p0 - 2p1 + p2
+ * B = 2 * (p1 - p0)
+ * ```
+ *
+ * we have
+ *
+ * ```
+ * B(t) = t^2 * A + t * B + p0
+ * ```
+ *
+ * (2) The derivative of the above equation is
+ *
+ * ```
+ * B'(t) = 2t * A + B
+ * ```
+ *
+ * (3) The second derivative of the above equation is
+ *
+ * ```
+ * B''(t) = 2A
+ * ```
+ *
+ * (4) The equation `P(t)` of the distance from point `p` to the curve
+ * can be written as
+ *
+ * ```
+ * P(t) = t^2 * A + t^2 * B + p0 - p
+ * ```
+ *
+ * With
+ *
+ * ```
+ * C = p0 - p
+ * ```
+ *
+ * we have
+ *
+ * ```
+ * P(t) = t^2 * A + t * B + C
+ * ```
+ *
+ * (5) Finally, the equation of the angle between `B(t)` and `P(t)` can
+ * be written as
+ *
+ * ```
+ * Q(t) = P(t) . B'(t)
+ * ```
+ *
+ * (6) Our task is to find a value of `t` such that the above equation
+ * `Q(t)` becomes zero, this is, the point-to-curve vector makes
+ * 90~degrees with the curve. We solve this with the Newton-Raphson
+ * method.
+ *
+ * (7) We first assume an arbitary value of factor `t`, which we then
+ * improve.
+ *
+ * ```
+ * t := Q(t) / Q'(t)
+ * ```
+ *
+ * Putting the value of `Q(t)` from the above equation gives
+ *
+ * ```
+ * t := P(t) . B'(t) / derivative(P(t) . B'(t))
+ * t := P(t) . B'(t) /
+ * (P'(t) . B'(t) + P(t) . B''(t))
+ * ```
+ *
+ * Note that `P'(t)` is the same as `B'(t)` because the constant is
+ * gone due to the derivative.
+ *
+ * (8) Finally we get the equation to improve the factor as
+ *
+ * ```
+ * t := P(t) . B'(t) /
+ * (B'(t) . B'(t) + P(t) . B''(t))
+ * ```
+ *
+ * [note]: `B` and `B(t)` are different in the above equations.
+ */
+
+ FT_Error error = FT_Err_Ok;
+
+ FT_26D6_Vec aA, bB, cC; /* A, B, C in the above comment */
+ FT_26D6_Vec nearest_point; /* point on curve nearest to `point` */
+ FT_26D6_Vec direction; /* direction of curve at `nearest_point` */
+
+ FT_26D6_Vec p0, p1, p2; /* control points of a conic curve */
+ FT_26D6_Vec p; /* `point` to which shortest distance */
+
+ FT_16D16 min_factor = 0; /* factor at `nearest_point' */
+ FT_16D16 cross; /* to determine the sign */
+ FT_16D16 min = FT_INT_MAX; /* shortest squared distance */
+
+ FT_UShort iterations;
+ FT_UShort steps;
+
+
+ if ( !conic || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( conic->edge_type != SDF_EDGE_CONIC )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ p0 = conic->start_pos;
+ p1 = conic->control_a;
+ p2 = conic->end_pos;
+ p = point;
+
+ /* compute substitution coefficients */
+ aA.x = p0.x - 2 * p1.x + p2.x;
+ aA.y = p0.y - 2 * p1.y + p2.y;
+
+ bB.x = 2 * ( p1.x - p0.x );
+ bB.y = 2 * ( p1.y - p0.y );
+
+ cC.x = p0.x;
+ cC.y = p0.y;
+
+ /* do Newton's iterations */
+ for ( iterations = 0; iterations <= MAX_NEWTON_DIVISIONS; iterations++ )
+ {
+ FT_16D16 factor = FT_INT_16D16( iterations ) / MAX_NEWTON_DIVISIONS;
+ FT_16D16 factor2;
+ FT_16D16 length;
+
+ FT_16D16_Vec curve_point; /* point on the curve */
+ FT_16D16_Vec dist_vector; /* `curve_point` - `p` */
+
+ FT_26D6_Vec d1; /* first derivative */
+ FT_26D6_Vec d2; /* second derivative */
+
+ FT_16D16 temp1;
+ FT_16D16 temp2;
+
+
+ for ( steps = 0; steps < MAX_NEWTON_STEPS; steps++ )
+ {
+ factor2 = FT_MulFix( factor, factor );
+
+ /* B(t) = t^2 * A + t * B + p0 */
+ curve_point.x = FT_MulFix( aA.x, factor2 ) +
+ FT_MulFix( bB.x, factor ) + cC.x;
+ curve_point.y = FT_MulFix( aA.y, factor2 ) +
+ FT_MulFix( bB.y, factor ) + cC.y;
+
+ /* convert to 16.16 */
+ curve_point.x = FT_26D6_16D16( curve_point.x );
+ curve_point.y = FT_26D6_16D16( curve_point.y );
+
+ /* P(t) in the comment */
+ dist_vector.x = curve_point.x - FT_26D6_16D16( p.x );
+ dist_vector.y = curve_point.y - FT_26D6_16D16( p.y );
+
+ length = VECTOR_LENGTH_16D16( dist_vector );
+
+ if ( length < min )
+ {
+ min = length;
+ min_factor = factor;
+ nearest_point = curve_point;
+ }
+
+ /* This is Newton's approximation. */
+ /* */
+ /* t := P(t) . B'(t) / */
+ /* (B'(t) . B'(t) + P(t) . B''(t)) */
+
+ /* B'(t) = 2tA + B */
+ d1.x = FT_MulFix( aA.x, 2 * factor ) + bB.x;
+ d1.y = FT_MulFix( aA.y, 2 * factor ) + bB.y;
+
+ /* B''(t) = 2A */
+ d2.x = 2 * aA.x;
+ d2.y = 2 * aA.y;
+
+ dist_vector.x /= 1024;
+ dist_vector.y /= 1024;
+
+ /* temp1 = P(t) . B'(t) */
+ temp1 = VEC_26D6_DOT( dist_vector, d1 );
+
+ /* temp2 = B'(t) . B'(t) + P(t) . B''(t) */
+ temp2 = VEC_26D6_DOT( d1, d1 ) +
+ VEC_26D6_DOT( dist_vector, d2 );
+
+ factor -= FT_DivFix( temp1, temp2 );
+
+ if ( factor < 0 || factor > FT_INT_16D16( 1 ) )
+ break;
+ }
+ }
+
+ /* B'(t) = 2t * A + B */
+ direction.x = 2 * FT_MulFix( aA.x, min_factor ) + bB.x;
+ direction.y = 2 * FT_MulFix( aA.y, min_factor ) + bB.y;
+
+ /* determine the sign */
+ cross = FT_MulFix( nearest_point.x - FT_26D6_16D16( p.x ),
+ direction.y ) -
+ FT_MulFix( nearest_point.y - FT_26D6_16D16( p.y ),
+ direction.x );
+
+ /* assign the values */
+ out->distance = min;
+ out->sign = cross < 0 ? 1 : -1;
+
+ if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) )
+ out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */
+ else
+ {
+ /* convert to nearest vector */
+ nearest_point.x -= FT_26D6_16D16( p.x );
+ nearest_point.y -= FT_26D6_16D16( p.y );
+
+ /* compute `cross` if not perpendicular */
+ FT_Vector_NormLen( &direction );
+ FT_Vector_NormLen( &nearest_point );
+
+ out->cross = FT_MulFix( direction.x, nearest_point.y ) -
+ FT_MulFix( direction.y, nearest_point.x );
+ }
+
+ Exit:
+ return error;
+ }
+
+
+#endif /* USE_NEWTON_FOR_CONIC */
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * get_min_distance_cubic
+ *
+ * @Description:
+ * Find the shortest distance from the `cubic` Bezier curve to a given
+ * `point` and assigns it to `out`. Use it for cubic curves only.
+ *
+ * @Input:
+ * cubic ::
+ * The cubic Bezier curve to which the shortest distance is to be
+ * computed.
+ *
+ * point ::
+ * Point from which the shortest distance is to be computed.
+ *
+ * @Output:
+ * out ::
+ * Signed distance from `point` to `cubic`.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ * @Note:
+ * The function uses Newton's approximation to find the shortest
+ * distance. Another way would be to divide the cubic into conic or
+ * subdivide the curve into lines, but that is not implemented.
+ *
+ * The `cubic` parameter must have an edge type of `SDF_EDGE_CUBIC`.
+ *
+ */
+ static FT_Error
+ get_min_distance_cubic( SDF_Edge* cubic,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ /*
+ * The procedure to find the shortest distance from a point to a cubic
+ * Bezier curve is similar to quadratic curve algorithm. The only
+ * difference is that while calculating factor `t`, instead of a cubic
+ * polynomial equation we have to find the roots of a 5th degree
+ * polynomial equation. Solving this would require a significant amount
+ * of time, and still the results may not be accurate. We are thus
+ * going to directly approximate the value of `t` using the Newton-Raphson
+ * method.
+ *
+ * Let's assume that
+ *
+ * ```
+ * p0 = first endpoint
+ * p1 = first control point
+ * p2 = second control point
+ * p3 = second endpoint
+ * p = point from which shortest distance is to be calculated
+ * ```
+ *
+ * (1) The equation of a cubic Bezier curve can be written as
+ *
+ * ```
+ * B(t) = (1 - t)^3 * p0 + 3(1 - t)^2 t * p1 +
+ * 3(1 - t)t^2 * p2 + t^3 * p3
+ * ```
+ *
+ * The equation can be expanded and written as
+ *
+ * ```
+ * B(t) = t^3 * (-p0 + 3p1 - 3p2 + p3) +
+ * 3t^2 * (p0 - 2p1 + p2) + 3t * (-p0 + p1) + p0
+ * ```
+ *
+ * With
+ *
+ * ```
+ * A = -p0 + 3p1 - 3p2 + p3
+ * B = 3(p0 - 2p1 + p2)
+ * C = 3(-p0 + p1)
+ * ```
+ *
+ * we have
+ *
+ * ```
+ * B(t) = t^3 * A + t^2 * B + t * C + p0
+ * ```
+ *
+ * (2) The derivative of the above equation is
+ *
+ * ```
+ * B'(t) = 3t^2 * A + 2t * B + C
+ * ```
+ *
+ * (3) The second derivative of the above equation is
+ *
+ * ```
+ * B''(t) = 6t * A + 2B
+ * ```
+ *
+ * (4) The equation `P(t)` of the distance from point `p` to the curve
+ * can be written as
+ *
+ * ```
+ * P(t) = t^3 * A + t^2 * B + t * C + p0 - p
+ * ```
+ *
+ * With
+ *
+ * ```
+ * D = p0 - p
+ * ```
+ *
+ * we have
+ *
+ * ```
+ * P(t) = t^3 * A + t^2 * B + t * C + D
+ * ```
+ *
+ * (5) Finally the equation of the angle between `B(t)` and `P(t)` can
+ * be written as
+ *
+ * ```
+ * Q(t) = P(t) . B'(t)
+ * ```
+ *
+ * (6) Our task is to find a value of `t` such that the above equation
+ * `Q(t)` becomes zero, this is, the point-to-curve vector makes
+ * 90~degree with curve. We solve this with the Newton-Raphson
+ * method.
+ *
+ * (7) We first assume an arbitary value of factor `t`, which we then
+ * improve.
+ *
+ * ```
+ * t := Q(t) / Q'(t)
+ * ```
+ *
+ * Putting the value of `Q(t)` from the above equation gives
+ *
+ * ```
+ * t := P(t) . B'(t) / derivative(P(t) . B'(t))
+ * t := P(t) . B'(t) /
+ * (P'(t) . B'(t) + P(t) . B''(t))
+ * ```
+ *
+ * Note that `P'(t)` is the same as `B'(t)` because the constant is
+ * gone due to the derivative.
+ *
+ * (8) Finally we get the equation to improve the factor as
+ *
+ * ```
+ * t := P(t) . B'(t) /
+ * (B'(t) . B'( t ) + P(t) . B''(t))
+ * ```
+ *
+ * [note]: `B` and `B(t)` are different in the above equations.
+ */
+
+ FT_Error error = FT_Err_Ok;
+
+ FT_26D6_Vec aA, bB, cC, dD; /* A, B, C in the above comment */
+ FT_16D16_Vec nearest_point; /* point on curve nearest to `point` */
+ FT_16D16_Vec direction; /* direction of curve at `nearest_point` */
+
+ FT_26D6_Vec p0, p1, p2, p3; /* control points of a cubic curve */
+ FT_26D6_Vec p; /* `point` to which shortest distance */
+
+ FT_16D16 min_factor = 0; /* factor at shortest distance */
+ FT_16D16 min_factor_sq = 0; /* factor at shortest distance */
+ FT_16D16 cross; /* to determine the sign */
+ FT_16D16 min = FT_INT_MAX; /* shortest distance */
+
+ FT_UShort iterations;
+ FT_UShort steps;
+
+
+ if ( !cubic || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( cubic->edge_type != SDF_EDGE_CUBIC )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ p0 = cubic->start_pos;
+ p1 = cubic->control_a;
+ p2 = cubic->control_b;
+ p3 = cubic->end_pos;
+ p = point;
+
+ /* compute substitution coefficients */
+ aA.x = -p0.x + 3 * ( p1.x - p2.x ) + p3.x;
+ aA.y = -p0.y + 3 * ( p1.y - p2.y ) + p3.y;
+
+ bB.x = 3 * ( p0.x - 2 * p1.x + p2.x );
+ bB.y = 3 * ( p0.y - 2 * p1.y + p2.y );
+
+ cC.x = 3 * ( p1.x - p0.x );
+ cC.y = 3 * ( p1.y - p0.y );
+
+ dD.x = p0.x;
+ dD.y = p0.y;
+
+ for ( iterations = 0; iterations <= MAX_NEWTON_DIVISIONS; iterations++ )
+ {
+ FT_16D16 factor = FT_INT_16D16( iterations ) / MAX_NEWTON_DIVISIONS;
+
+ FT_16D16 factor2; /* factor^2 */
+ FT_16D16 factor3; /* factor^3 */
+ FT_16D16 length;
+
+ FT_16D16_Vec curve_point; /* point on the curve */
+ FT_16D16_Vec dist_vector; /* `curve_point' - `p' */
+
+ FT_26D6_Vec d1; /* first derivative */
+ FT_26D6_Vec d2; /* second derivative */
+
+ FT_16D16 temp1;
+ FT_16D16 temp2;
+
+
+ for ( steps = 0; steps < MAX_NEWTON_STEPS; steps++ )
+ {
+ factor2 = FT_MulFix( factor, factor );
+ factor3 = FT_MulFix( factor2, factor );
+
+ /* B(t) = t^3 * A + t^2 * B + t * C + D */
+ curve_point.x = FT_MulFix( aA.x, factor3 ) +
+ FT_MulFix( bB.x, factor2 ) +
+ FT_MulFix( cC.x, factor ) + dD.x;
+ curve_point.y = FT_MulFix( aA.y, factor3 ) +
+ FT_MulFix( bB.y, factor2 ) +
+ FT_MulFix( cC.y, factor ) + dD.y;
+
+ /* convert to 16.16 */
+ curve_point.x = FT_26D6_16D16( curve_point.x );
+ curve_point.y = FT_26D6_16D16( curve_point.y );
+
+ /* P(t) in the comment */
+ dist_vector.x = curve_point.x - FT_26D6_16D16( p.x );
+ dist_vector.y = curve_point.y - FT_26D6_16D16( p.y );
+
+ length = VECTOR_LENGTH_16D16( dist_vector );
+
+ if ( length < min )
+ {
+ min = length;
+ min_factor = factor;
+ min_factor_sq = factor2;
+ nearest_point = curve_point;
+ }
+
+ /* This the Newton's approximation. */
+ /* */
+ /* t := P(t) . B'(t) / */
+ /* (B'(t) . B'(t) + P(t) . B''(t)) */
+
+ /* B'(t) = 3t^2 * A + 2t * B + C */
+ d1.x = FT_MulFix( aA.x, 3 * factor2 ) +
+ FT_MulFix( bB.x, 2 * factor ) + cC.x;
+ d1.y = FT_MulFix( aA.y, 3 * factor2 ) +
+ FT_MulFix( bB.y, 2 * factor ) + cC.y;
+
+ /* B''(t) = 6t * A + 2B */
+ d2.x = FT_MulFix( aA.x, 6 * factor ) + 2 * bB.x;
+ d2.y = FT_MulFix( aA.y, 6 * factor ) + 2 * bB.y;
+
+ dist_vector.x /= 1024;
+ dist_vector.y /= 1024;
+
+ /* temp1 = P(t) . B'(t) */
+ temp1 = VEC_26D6_DOT( dist_vector, d1 );
+
+ /* temp2 = B'(t) . B'(t) + P(t) . B''(t) */
+ temp2 = VEC_26D6_DOT( d1, d1 ) +
+ VEC_26D6_DOT( dist_vector, d2 );
+
+ factor -= FT_DivFix( temp1, temp2 );
+
+ if ( factor < 0 || factor > FT_INT_16D16( 1 ) )
+ break;
+ }
+ }
+
+ /* B'(t) = 3t^2 * A + 2t * B + C */
+ direction.x = FT_MulFix( aA.x, 3 * min_factor_sq ) +
+ FT_MulFix( bB.x, 2 * min_factor ) + cC.x;
+ direction.y = FT_MulFix( aA.y, 3 * min_factor_sq ) +
+ FT_MulFix( bB.y, 2 * min_factor ) + cC.y;
+
+ /* determine the sign */
+ cross = FT_MulFix( nearest_point.x - FT_26D6_16D16( p.x ),
+ direction.y ) -
+ FT_MulFix( nearest_point.y - FT_26D6_16D16( p.y ),
+ direction.x );
+
+ /* assign the values */
+ out->distance = min;
+ out->sign = cross < 0 ? 1 : -1;
+
+ if ( min_factor != 0 && min_factor != FT_INT_16D16( 1 ) )
+ out->cross = FT_INT_16D16( 1 ); /* the two are perpendicular */
+ else
+ {
+ /* convert to nearest vector */
+ nearest_point.x -= FT_26D6_16D16( p.x );
+ nearest_point.y -= FT_26D6_16D16( p.y );
+
+ /* compute `cross` if not perpendicular */
+ FT_Vector_NormLen( &direction );
+ FT_Vector_NormLen( &nearest_point );
+
+ out->cross = FT_MulFix( direction.x, nearest_point.y ) -
+ FT_MulFix( direction.y, nearest_point.x );
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_edge_get_min_distance
+ *
+ * @Description:
+ * Find shortest distance from `point` to any type of `edge`. It checks
+ * the edge type and then calls the relevant `get_min_distance_*`
+ * function.
+ *
+ * @Input:
+ * edge ::
+ * An edge to which the shortest distance is to be computed.
+ *
+ * point ::
+ * Point from which the shortest distance is to be computed.
+ *
+ * @Output:
+ * out ::
+ * Signed distance from `point` to `edge`.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ */
+ static FT_Error
+ sdf_edge_get_min_distance( SDF_Edge* edge,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ FT_Error error = FT_Err_Ok;
+
+
+ if ( !edge || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* edge-specific distance calculation */
+ switch ( edge->edge_type )
+ {
+ case SDF_EDGE_LINE:
+ get_min_distance_line( edge, point, out );
+ break;
+
+ case SDF_EDGE_CONIC:
+ get_min_distance_conic( edge, point, out );
+ break;
+
+ case SDF_EDGE_CUBIC:
+ get_min_distance_cubic( edge, point, out );
+ break;
+
+ default:
+ error = FT_THROW( Invalid_Argument );
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /* `sdf_generate' is not used at the moment */
+#if 0
+
+ #error "DO NOT USE THIS!"
+ #error "The function still outputs 16-bit data, which might cause memory"
+ #error "corruption. If required I will add this later."
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_contour_get_min_distance
+ *
+ * @Description:
+ * Iterate over all edges that make up the contour, find the shortest
+ * distance from a point to this contour, and assigns result to `out`.
+ *
+ * @Input:
+ * contour ::
+ * A contour to which the shortest distance is to be computed.
+ *
+ * point ::
+ * Point from which the shortest distance is to be computed.
+ *
+ * @Output:
+ * out ::
+ * Signed distance from the `point' to the `contour'.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ * @Note:
+ * The function does not return a signed distance for each edge which
+ * makes up the contour, it simply returns the shortest of all the
+ * edges.
+ *
+ */
+ static FT_Error
+ sdf_contour_get_min_distance( SDF_Contour* contour,
+ FT_26D6_Vec point,
+ SDF_Signed_Distance* out )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Signed_Distance min_dist = max_sdf;
+ SDF_Edge* edge_list;
+
+
+ if ( !contour || !out )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ edge_list = contour->edges;
+
+ /* iterate over all the edges manually */
+ while ( edge_list )
+ {
+ SDF_Signed_Distance current_dist = max_sdf;
+ FT_16D16 diff;
+
+
+ FT_CALL( sdf_edge_get_min_distance( edge_list,
+ point,
+ &current_dist ) );
+
+ if ( current_dist.distance >= 0 )
+ {
+ diff = current_dist.distance - min_dist.distance;
+
+
+ if ( FT_ABS( diff ) < CORNER_CHECK_EPSILON )
+ min_dist = resolve_corner( min_dist, current_dist );
+ else if ( diff < 0 )
+ min_dist = current_dist;
+ }
+ else
+ FT_TRACE0(( "sdf_contour_get_min_distance: Overflow.\n" ));
+
+ edge_list = edge_list->next;
+ }
+
+ *out = min_dist;
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate
+ *
+ * @Description:
+ * This is the main function that is responsible for generating signed
+ * distance fields. The function does not align or compute the size of
+ * `bitmap`; therefore the calling application must set up `bitmap`
+ * properly and transform the `shape' appropriately in advance.
+ *
+ * Currently we check all pixels against all contours and all edges.
+ *
+ * @Input:
+ * internal_params ::
+ * Internal parameters and properties required by the rasterizer. See
+ * @SDF_Params for more.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed in the output bitmap.
+ *
+ * @Output:
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ */
+ static FT_Error
+ sdf_generate( const SDF_Params internal_params,
+ const SDF_Shape* shape,
+ FT_UInt spread,
+ const FT_Bitmap* bitmap )
+ {
+ FT_Error error = FT_Err_Ok;
+
+ FT_UInt width = 0;
+ FT_UInt rows = 0;
+ FT_UInt x = 0; /* used to loop in x direction, i.e., width */
+ FT_UInt y = 0; /* used to loop in y direction, i.e., rows */
+ FT_UInt sp_sq = 0; /* `spread` [* `spread`] as a 16.16 fixed value */
+
+ FT_Short* buffer;
+
+
+ if ( !shape || !bitmap )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( spread < MIN_SPREAD || spread > MAX_SPREAD )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ width = bitmap->width;
+ rows = bitmap->rows;
+ buffer = (FT_Short*)bitmap->buffer;
+
+ if ( USE_SQUARED_DISTANCES )
+ sp_sq = FT_INT_16D16( spread * spread );
+ else
+ sp_sq = FT_INT_16D16( spread );
+
+ if ( width == 0 || rows == 0 )
+ {
+ FT_TRACE0(( "sdf_generate:"
+ " Cannot render glyph with width/height == 0\n" ));
+ FT_TRACE0(( " "
+ " (width, height provided [%d, %d])\n",
+ width, rows ));
+
+ error = FT_THROW( Cannot_Render_Glyph );
+ goto Exit;
+ }
+
+ /* loop over all rows */
+ for ( y = 0; y < rows; y++ )
+ {
+ /* loop over all pixels of a row */
+ for ( x = 0; x < width; x++ )
+ {
+ /* `grid_point` is the current pixel position; */
+ /* our task is to find the shortest distance */
+ /* from this point to the entire shape. */
+ FT_26D6_Vec grid_point = zero_vector;
+ SDF_Signed_Distance min_dist = max_sdf;
+ SDF_Contour* contour_list;
+
+ FT_UInt index;
+ FT_Short value;
+
+
+ grid_point.x = FT_INT_26D6( x );
+ grid_point.y = FT_INT_26D6( y );
+
+ /* This `grid_point' is at the corner, but we */
+ /* use the center of the pixel. */
+ grid_point.x += FT_INT_26D6( 1 ) / 2;
+ grid_point.y += FT_INT_26D6( 1 ) / 2;
+
+ contour_list = shape->contours;
+
+ /* iterate over all contours manually */
+ while ( contour_list )
+ {
+ SDF_Signed_Distance current_dist = max_sdf;
+
+
+ FT_CALL( sdf_contour_get_min_distance( contour_list,
+ grid_point,
+ &current_dist ) );
+
+ if ( current_dist.distance < min_dist.distance )
+ min_dist = current_dist;
+
+ contour_list = contour_list->next;
+ }
+
+ /* [OPTIMIZATION]: if (min_dist > sp_sq) then simply clamp */
+ /* the value to spread to avoid square_root */
+
+ /* clamp the values to spread */
+ if ( min_dist.distance > sp_sq )
+ min_dist.distance = sp_sq;
+
+ /* square_root the values and fit in a 6.10 fixed point */
+ if ( USE_SQUARED_DISTANCES )
+ min_dist.distance = square_root( min_dist.distance );
+
+ if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT )
+ min_dist.sign = -min_dist.sign;
+ if ( internal_params.flip_sign )
+ min_dist.sign = -min_dist.sign;
+
+ min_dist.distance /= 64; /* convert from 16.16 to 22.10 */
+
+ value = min_dist.distance & 0x0000FFFF; /* truncate to 6.10 */
+ value *= min_dist.sign;
+
+ if ( internal_params.flip_y )
+ index = y * width + x;
+ else
+ index = ( rows - y - 1 ) * width + x;
+
+ buffer[index] = value;
+ }
+ }
+
+ Exit:
+ return error;
+ }
+
+#endif /* 0 */
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate_bounding_box
+ *
+ * @Description:
+ * This function does basically the same thing as `sdf_generate` above
+ * but more efficiently.
+ *
+ * Instead of checking all pixels against all edges, we loop over all
+ * edges and only check pixels around the control box of the edge; the
+ * control box is increased by the spread in all directions. Anything
+ * outside of the control box that exceeds `spread` doesn't need to be
+ * computed.
+ *
+ * Lastly, to determine the sign of unchecked pixels, we do a single
+ * pass of all rows starting with a '+' sign and flipping when we come
+ * across a '-' sign and continue. This also eliminates the possibility
+ * of overflow because we only check the proximity of the curve.
+ * Therefore we can use squared distanced safely.
+ *
+ * @Input:
+ * internal_params ::
+ * Internal parameters and properties required by the rasterizer.
+ * See @SDF_Params for more.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed in the output bitmap.
+ *
+ * @Output:
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ */
+ static FT_Error
+ sdf_generate_bounding_box( const SDF_Params internal_params,
+ const SDF_Shape* shape,
+ FT_UInt spread,
+ const FT_Bitmap* bitmap )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = NULL;
+
+ FT_Int width, rows, i, j;
+ FT_Int sp_sq; /* max value to check */
+
+ SDF_Contour* contours; /* list of all contours */
+ FT_SDFFormat* buffer; /* the bitmap buffer */
+
+ /* This buffer has the same size in indices as the */
+ /* bitmap buffer. When we check a pixel position for */
+ /* a shortest distance we keep it in this buffer. */
+ /* This way we can find out which pixel is set, */
+ /* and also determine the signs properly. */
+ SDF_Signed_Distance* dists = NULL;
+
+ const FT_16D16 fixed_spread = FT_INT_16D16( spread );
+
+
+ if ( !shape || !bitmap )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( spread < MIN_SPREAD || spread > MAX_SPREAD )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ memory = shape->memory;
+ if ( !memory )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( FT_ALLOC( dists,
+ bitmap->width * bitmap->rows * sizeof ( *dists ) ) )
+ goto Exit;
+
+ contours = shape->contours;
+ width = (FT_Int)bitmap->width;
+ rows = (FT_Int)bitmap->rows;
+ buffer = (FT_SDFFormat*)bitmap->buffer;
+
+ if ( USE_SQUARED_DISTANCES )
+ sp_sq = FT_INT_16D16( (FT_Int)( spread * spread ) );
+ else
+ sp_sq = fixed_spread;
+
+ if ( width == 0 || rows == 0 )
+ {
+ FT_TRACE0(( "sdf_generate:"
+ " Cannot render glyph with width/height == 0\n" ));
+ FT_TRACE0(( " "
+ " (width, height provided [%d, %d])", width, rows ));
+
+ error = FT_THROW( Cannot_Render_Glyph );
+ goto Exit;
+ }
+
+ /* loop over all contours */
+ while ( contours )
+ {
+ SDF_Edge* edges = contours->edges;
+
+
+ /* loop over all edges */
+ while ( edges )
+ {
+ FT_CBox cbox;
+ FT_Int x, y;
+
+
+ /* get the control box and increase it by `spread' */
+ cbox = get_control_box( *edges );
+
+ cbox.xMin = ( cbox.xMin - 63 ) / 64 - ( FT_Pos )spread;
+ cbox.xMax = ( cbox.xMax + 63 ) / 64 + ( FT_Pos )spread;
+ cbox.yMin = ( cbox.yMin - 63 ) / 64 - ( FT_Pos )spread;
+ cbox.yMax = ( cbox.yMax + 63 ) / 64 + ( FT_Pos )spread;
+
+ /* now loop over the pixels in the control box. */
+ for ( y = cbox.yMin; y < cbox.yMax; y++ )
+ {
+ for ( x = cbox.xMin; x < cbox.xMax; x++ )
+ {
+ FT_26D6_Vec grid_point = zero_vector;
+ SDF_Signed_Distance dist = max_sdf;
+ FT_UInt index = 0;
+ FT_16D16 diff = 0;
+
+
+ if ( x < 0 || x >= width )
+ continue;
+ if ( y < 0 || y >= rows )
+ continue;
+
+ grid_point.x = FT_INT_26D6( x );
+ grid_point.y = FT_INT_26D6( y );
+
+ /* This `grid_point` is at the corner, but we */
+ /* use the center of the pixel. */
+ grid_point.x += FT_INT_26D6( 1 ) / 2;
+ grid_point.y += FT_INT_26D6( 1 ) / 2;
+
+ FT_CALL( sdf_edge_get_min_distance( edges,
+ grid_point,
+ &dist ) );
+
+ if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT )
+ dist.sign = -dist.sign;
+
+ /* ignore if the distance is greater than spread; */
+ /* otherwise it creates artifacts due to the wrong sign */
+ if ( dist.distance > sp_sq )
+ continue;
+
+ /* take the square root of the distance if required */
+ if ( USE_SQUARED_DISTANCES )
+ dist.distance = square_root( dist.distance );
+
+ if ( internal_params.flip_y )
+ index = (FT_UInt)( y * width + x );
+ else
+ index = (FT_UInt)( ( rows - y - 1 ) * width + x );
+
+ /* check whether the pixel is set or not */
+ if ( dists[index].sign == 0 )
+ dists[index] = dist;
+ else
+ {
+ diff = FT_ABS( dists[index].distance - dist.distance );
+
+ if ( diff <= CORNER_CHECK_EPSILON )
+ dists[index] = resolve_corner( dists[index], dist );
+ else if ( dists[index].distance > dist.distance )
+ dists[index] = dist;
+ }
+ }
+ }
+
+ edges = edges->next;
+ }
+
+ contours = contours->next;
+ }
+
+ /* final pass */
+ for ( j = 0; j < rows; j++ )
+ {
+ /* We assume the starting pixel of each row is outside. */
+ FT_Char current_sign = -1;
+ FT_UInt index;
+
+
+ if ( internal_params.overload_sign != 0 )
+ current_sign = internal_params.overload_sign < 0 ? -1 : 1;
+
+ for ( i = 0; i < width; i++ )
+ {
+ index = (FT_UInt)( j * width + i );
+
+ /* if the pixel is not set */
+ /* its shortest distance is more than `spread` */
+ if ( dists[index].sign == 0 )
+ dists[index].distance = fixed_spread;
+ else
+ current_sign = dists[index].sign;
+
+ /* clamp the values */
+ if ( dists[index].distance > fixed_spread )
+ dists[index].distance = fixed_spread;
+
+ /* flip sign if required */
+ dists[index].distance *= internal_params.flip_sign ? -current_sign
+ : current_sign;
+
+ /* concatenate to appropriate format */
+ buffer[index] = map_fixed_to_sdf( dists[index].distance,
+ fixed_spread );
+ }
+ }
+
+ Exit:
+ FT_FREE( dists );
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate_subdivision
+ *
+ * @Description:
+ * Subdivide the shape into a number of straight lines, then use the
+ * above `sdf_generate_bounding_box` function to generate the SDF.
+ *
+ * Note: After calling this function `shape` no longer has the original
+ * edges, it only contains lines.
+ *
+ * @Input:
+ * internal_params ::
+ * Internal parameters and properties required by the rasterizer.
+ * See @SDF_Params for more.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed inthe output bitmap.
+ *
+ * @Output:
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ */
+ static FT_Error
+ sdf_generate_subdivision( const SDF_Params internal_params,
+ SDF_Shape* shape,
+ FT_UInt spread,
+ const FT_Bitmap* bitmap )
+ {
+ /*
+ * Thanks to Alexei for providing the idea of this optimization.
+ *
+ * We take advantage of two facts.
+ *
+ * (1) Computing the shortest distance from a point to a line segment is
+ * very fast.
+ * (2) We don't have to compute the shortest distance for the entire
+ * two-dimensional grid.
+ *
+ * Both ideas lead to the following optimization.
+ *
+ * (1) Split the outlines into a number of line segments.
+ *
+ * (2) For each line segment, only process its neighborhood.
+ *
+ * (3) Compute the closest distance to the line only for neighborhood
+ * grid points.
+ *
+ * This greatly reduces the number of grid points to check.
+ */
+
+ FT_Error error = FT_Err_Ok;
+
+
+ FT_CALL( split_sdf_shape( shape ) );
+ FT_CALL( sdf_generate_bounding_box( internal_params,
+ shape, spread, bitmap ) );
+
+ Exit:
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate_with_overlaps
+ *
+ * @Description:
+ * This function can be used to generate SDF for glyphs with overlapping
+ * contours. The function generates SDF for contours separately on
+ * separate bitmaps (to generate SDF it uses
+ * `sdf_generate_subdivision`). At the end it simply combines all the
+ * SDF into the output bitmap; this fixes all the signs and removes
+ * overlaps.
+ *
+ * @Input:
+ * internal_params ::
+ * Internal parameters and properties required by the rasterizer. See
+ * @SDF_Params for more.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed in the output bitmap.
+ *
+ * @Output:
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ * @Note:
+ * The function cannot generate a proper SDF for glyphs with
+ * self-intersecting contours because we cannot separate them into two
+ * separate bitmaps. In case of self-intersecting contours it is
+ * necessary to remove the overlaps before generating the SDF.
+ *
+ */
+ static FT_Error
+ sdf_generate_with_overlaps( SDF_Params internal_params,
+ SDF_Shape* shape,
+ FT_UInt spread,
+ const FT_Bitmap* bitmap )
+ {
+ FT_Error error = FT_Err_Ok;
+
+ FT_Int num_contours; /* total number of contours */
+ FT_Int i, j; /* iterators */
+ FT_Int width, rows; /* width and rows of the bitmap */
+ FT_Bitmap* bitmaps; /* separate bitmaps for contours */
+
+ SDF_Contour* contour; /* temporary variable to iterate */
+ SDF_Contour* temp_contour; /* temporary contour */
+ SDF_Contour* head; /* head of the contour list */
+ SDF_Shape temp_shape; /* temporary shape */
+
+ FT_Memory memory; /* to allocate memory */
+ FT_SDFFormat* t; /* target bitmap buffer */
+ FT_Bool flip_sign; /* flip sign? */
+
+ /* orientation of all the separate contours */
+ SDF_Contour_Orientation* orientations;
+
+
+ bitmaps = NULL;
+ orientations = NULL;
+ head = NULL;
+
+ if ( !shape || !bitmap || !shape->memory )
+ return FT_THROW( Invalid_Argument );
+
+ /* Disable `flip_sign` to avoid extra complication */
+ /* during the combination phase. */
+ flip_sign = internal_params.flip_sign;
+ internal_params.flip_sign = 0;
+
+ contour = shape->contours;
+ memory = shape->memory;
+ temp_shape.memory = memory;
+ width = (FT_Int)bitmap->width;
+ rows = (FT_Int)bitmap->rows;
+ num_contours = 0;
+
+ /* find the number of contours in the shape */
+ while ( contour )
+ {
+ num_contours++;
+ contour = contour->next;
+ }
+
+ /* allocate the bitmaps to generate SDF for separate contours */
+ if ( FT_ALLOC( bitmaps,
+ (FT_UInt)num_contours * sizeof ( *bitmaps ) ) )
+ goto Exit;
+
+ /* allocate array to hold orientation for all contours */
+ if ( FT_ALLOC( orientations,
+ (FT_UInt)num_contours * sizeof ( *orientations ) ) )
+ goto Exit;
+
+ contour = shape->contours;
+
+ /* Iterate over all contours and generate SDF separately. */
+ for ( i = 0; i < num_contours; i++ )
+ {
+ /* initialize the corresponding bitmap */
+ FT_Bitmap_Init( &bitmaps[i] );
+
+ bitmaps[i].width = bitmap->width;
+ bitmaps[i].rows = bitmap->rows;
+ bitmaps[i].pitch = bitmap->pitch;
+ bitmaps[i].num_grays = bitmap->num_grays;
+ bitmaps[i].pixel_mode = bitmap->pixel_mode;
+
+ /* allocate memory for the buffer */
+ if ( FT_ALLOC( bitmaps[i].buffer,
+ bitmap->rows * (FT_UInt)bitmap->pitch ) )
+ goto Exit;
+
+ /* determine the orientation */
+ orientations[i] = get_contour_orientation( contour );
+
+ /* The `overload_sign` property is specific to */
+ /* `sdf_generate_bounding_box`. This basically */
+ /* overloads the default sign of the outside */
+ /* pixels, which is necessary for */
+ /* counter-clockwise contours. */
+ if ( orientations[i] == SDF_ORIENTATION_CCW &&
+ internal_params.orientation == FT_ORIENTATION_FILL_RIGHT )
+ internal_params.overload_sign = 1;
+ else if ( orientations[i] == SDF_ORIENTATION_CW &&
+ internal_params.orientation == FT_ORIENTATION_FILL_LEFT )
+ internal_params.overload_sign = 1;
+ else
+ internal_params.overload_sign = 0;
+
+ /* Make `contour->next` NULL so that there is */
+ /* one contour in the list. Also hold the next */
+ /* contour in a temporary variable so as to */
+ /* restore the original value. */
+ temp_contour = contour->next;
+ contour->next = NULL;
+
+ /* Use `temp_shape` to hold the new contour. */
+ /* Now, `temp_shape` has only one contour. */
+ temp_shape.contours = contour;
+
+ /* finally generate the SDF */
+ FT_CALL( sdf_generate_subdivision( internal_params,
+ &temp_shape,
+ spread,
+ &bitmaps[i] ) );
+
+ /* Restore the original `next` variable. */
+ contour->next = temp_contour;
+
+ /* Since `split_sdf_shape` deallocated the original */
+ /* contours list we need to assign the new value to */
+ /* the shape's contour. */
+ temp_shape.contours->next = head;
+ head = temp_shape.contours;
+
+ /* Simply flip the orientation in case of post-script fonts */
+ /* so as to avoid modificatons in the combining phase. */
+ if ( internal_params.orientation == FT_ORIENTATION_FILL_LEFT )
+ {
+ if ( orientations[i] == SDF_ORIENTATION_CW )
+ orientations[i] = SDF_ORIENTATION_CCW;
+ else if ( orientations[i] == SDF_ORIENTATION_CCW )
+ orientations[i] = SDF_ORIENTATION_CW;
+ }
+
+ contour = contour->next;
+ }
+
+ /* assign the new contour list to `shape->contours` */
+ shape->contours = head;
+
+ /* cast the output bitmap buffer */
+ t = (FT_SDFFormat*)bitmap->buffer;
+
+ /* Iterate over all pixels and combine all separate */
+ /* contours. These are the rules for combining: */
+ /* */
+ /* (1) For all clockwise contours, compute the largest */
+ /* value. Name this as `val_c`. */
+ /* (2) For all counter-clockwise contours, compute the */
+ /* smallest value. Name this as `val_ac`. */
+ /* (3) Now, finally use the smaller value of `val_c' */
+ /* and `val_ac'. */
+ for ( j = 0; j < rows; j++ )
+ {
+ for ( i = 0; i < width; i++ )
+ {
+ FT_Int id = j * width + i; /* index of current pixel */
+ FT_Int c; /* contour iterator */
+
+ FT_SDFFormat val_c = 0; /* max clockwise value */
+ FT_SDFFormat val_ac = UCHAR_MAX; /* min counter-clockwise val */
+
+
+ /* iterate through all the contours */
+ for ( c = 0; c < num_contours; c++ )
+ {
+ /* current contour value */
+ FT_SDFFormat temp = ( (FT_SDFFormat*)bitmaps[c].buffer )[id];
+
+
+ if ( orientations[c] == SDF_ORIENTATION_CW )
+ val_c = FT_MAX( val_c, temp ); /* clockwise */
+ else
+ val_ac = FT_MIN( val_ac, temp ); /* counter-clockwise */
+ }
+
+ /* Finally find the smaller of the two and assign to output. */
+ /* Also apply `flip_sign` if set. */
+ t[id] = FT_MIN( val_c, val_ac );
+
+ if ( flip_sign )
+ t[id] = invert_sign( t[id] );
+ }
+ }
+
+ Exit:
+ /* deallocate orientations array */
+ if ( orientations )
+ FT_FREE( orientations );
+
+ /* deallocate temporary bitmaps */
+ if ( bitmaps )
+ {
+ if ( num_contours == 0 )
+ error = FT_THROW( Raster_Corrupted );
+ else
+ {
+ for ( i = 0; i < num_contours; i++ )
+ FT_FREE( bitmaps[i].buffer );
+
+ FT_FREE( bitmaps );
+ }
+ }
+
+ /* restore the `flip_sign` property */
+ internal_params.flip_sign = flip_sign;
+
+ return error;
+ }
+
+
+ /**************************************************************************
+ *
+ * interface functions
+ *
+ */
+
+ static FT_Error
+ sdf_raster_new( FT_Memory memory,
+ SDF_PRaster* araster )
+ {
+ FT_Error error;
+ SDF_PRaster raster = NULL;
+
+
+ if ( !FT_NEW( raster ) )
+ raster->memory = memory;
+
+ *araster = raster;
+
+ return error;
+ }
+
+
+ static void
+ sdf_raster_reset( FT_Raster raster,
+ unsigned char* pool_base,
+ unsigned long pool_size )
+ {
+ FT_UNUSED( raster );
+ FT_UNUSED( pool_base );
+ FT_UNUSED( pool_size );
+ }
+
+
+ static FT_Error
+ sdf_raster_set_mode( FT_Raster raster,
+ unsigned long mode,
+ void* args )
+ {
+ FT_UNUSED( raster );
+ FT_UNUSED( mode );
+ FT_UNUSED( args );
+
+ return FT_Err_Ok;
+ }
+
+
+ static FT_Error
+ sdf_raster_render( FT_Raster raster,
+ const FT_Raster_Params* params )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_TRaster* sdf_raster = (SDF_TRaster*)raster;
+ FT_Outline* outline = NULL;
+ const SDF_Raster_Params* sdf_params = (const SDF_Raster_Params*)params;
+
+ FT_Memory memory = NULL;
+ SDF_Shape* shape = NULL;
+ SDF_Params internal_params;
+
+
+ /* check for valid arguments */
+ if ( !sdf_raster || !sdf_params )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ outline = (FT_Outline*)sdf_params->root.source;
+
+ /* check whether outline is valid */
+ if ( !outline )
+ {
+ error = FT_THROW( Invalid_Outline );
+ goto Exit;
+ }
+
+ /* if the outline is empty, return */
+ if ( outline->n_points <= 0 || outline->n_contours <= 0 )
+ goto Exit;
+
+ /* check whether the outline has valid fields */
+ if ( !outline->contours || !outline->points )
+ {
+ error = FT_THROW( Invalid_Outline );
+ goto Exit;
+ }
+
+ /* check whether spread is set properly */
+ if ( sdf_params->spread > MAX_SPREAD ||
+ sdf_params->spread < MIN_SPREAD )
+ {
+ FT_TRACE0(( "sdf_raster_render:"
+ " The `spread' field of `SDF_Raster_Params' is invalid,\n" ));
+ FT_TRACE0(( " "
+ " the value of this field must be within [%d, %d].\n",
+ MIN_SPREAD, MAX_SPREAD ));
+ FT_TRACE0(( " "
+ " Also, you must pass `SDF_Raster_Params' instead of\n" ));
+ FT_TRACE0(( " "
+ " the default `FT_Raster_Params' while calling\n" ));
+ FT_TRACE0(( " "
+ " this function and set the fields properly.\n" ));
+
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ memory = sdf_raster->memory;
+ if ( !memory )
+ {
+ FT_TRACE0(( "sdf_raster_render:"
+ " Raster not setup properly,\n" ));
+ FT_TRACE0(( " "
+ " unable to find memory handle.\n" ));
+
+ error = FT_THROW( Invalid_Handle );
+ goto Exit;
+ }
+
+ /* set up the parameters */
+ internal_params.orientation = FT_Outline_Get_Orientation( outline );
+ internal_params.flip_sign = sdf_params->flip_sign;
+ internal_params.flip_y = sdf_params->flip_y;
+ internal_params.overload_sign = 0;
+
+ FT_CALL( sdf_shape_new( memory, &shape ) );
+
+ FT_CALL( sdf_outline_decompose( outline, shape ) );
+
+ if ( sdf_params->overlaps )
+ FT_CALL( sdf_generate_with_overlaps( internal_params,
+ shape, sdf_params->spread,
+ sdf_params->root.target ) );
+ else
+ FT_CALL( sdf_generate_subdivision( internal_params,
+ shape, sdf_params->spread,
+ sdf_params->root.target ) );
+
+ if ( shape )
+ sdf_shape_done( &shape );
+
+ Exit:
+ return error;
+ }
+
+
+ static void
+ sdf_raster_done( FT_Raster raster )
+ {
+ FT_Memory memory = (FT_Memory)((SDF_TRaster*)raster)->memory;
+
+
+ FT_FREE( raster );
+ }
+
+
+ FT_DEFINE_RASTER_FUNCS(
+ ft_sdf_raster,
+
+ FT_GLYPH_FORMAT_OUTLINE,
+
+ (FT_Raster_New_Func) sdf_raster_new, /* raster_new */
+ (FT_Raster_Reset_Func) sdf_raster_reset, /* raster_reset */
+ (FT_Raster_Set_Mode_Func)sdf_raster_set_mode, /* raster_set_mode */
+ (FT_Raster_Render_Func) sdf_raster_render, /* raster_render */
+ (FT_Raster_Done_Func) sdf_raster_done /* raster_done */
+ )
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdf.h b/src/3rdparty/freetype/src/sdf/ftsdf.h
new file mode 100644
index 0000000000..5f6b3f52aa
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdf.h
@@ -0,0 +1,97 @@
+/****************************************************************************
+ *
+ * ftsdf.h
+ *
+ * Signed Distance Field support (specification).
+ *
+ * Copyright (C) 2020-2022 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.
+ *
+ */
+
+
+#ifndef FTSDF_H_
+#define FTSDF_H_
+
+#include <ft2build.h>
+#include FT_CONFIG_CONFIG_H
+#include <freetype/ftimage.h>
+
+/* common properties and function */
+#include "ftsdfcommon.h"
+
+FT_BEGIN_HEADER
+
+ /**************************************************************************
+ *
+ * @struct:
+ * SDF_Raster_Params
+ *
+ * @description:
+ * This struct must be passed to the raster render function
+ * @FT_Raster_RenderFunc instead of @FT_Raster_Params because the
+ * rasterizer requires some additional information to render properly.
+ *
+ * @fields:
+ * root ::
+ * The native raster parameters structure.
+ *
+ * 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 maked 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 are valid for both the 'sdf' and 'bsdf' renderers; the
+ * exception is `overlaps`, which gets ignored by the 'bsdf' renderer.
+ *
+ */
+ typedef struct SDF_Raster_Params_
+ {
+ FT_Raster_Params root;
+ FT_UInt spread;
+ FT_Bool flip_sign;
+ FT_Bool flip_y;
+ FT_Bool overlaps;
+
+ } SDF_Raster_Params;
+
+
+ /* rasterizer to convert outline to SDF */
+ FT_EXPORT_VAR( const FT_Raster_Funcs ) ft_sdf_raster;
+
+ /* rasterizer to convert bitmap to SDF */
+ FT_EXPORT_VAR( const FT_Raster_Funcs ) ft_bitmap_sdf_raster;
+
+FT_END_HEADER
+
+#endif /* FTSDF_H_ */
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdfcommon.c b/src/3rdparty/freetype/src/sdf/ftsdfcommon.c
new file mode 100644
index 0000000000..072a36ea6c
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdfcommon.c
@@ -0,0 +1,147 @@
+/****************************************************************************
+ *
+ * ftsdfcommon.c
+ *
+ * Auxiliary data for Signed Distance Field support (body).
+ *
+ * Copyright (C) 2020-2022 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 "ftsdf.h"
+#include "ftsdfcommon.h"
+
+
+ /**************************************************************************
+ *
+ * common functions
+ *
+ */
+
+ /*
+ * Original algorithm:
+ *
+ * https://github.com/chmike/fpsqrt
+ *
+ * Use this to compute the square root of a 16.16 fixed point number.
+ */
+ FT_LOCAL_DEF( FT_16D16 )
+ square_root( FT_16D16 val )
+ {
+ FT_ULong t, q, b, r;
+
+
+ r = (FT_ULong)val;
+ b = 0x40000000L;
+ q = 0;
+
+ while ( b > 0x40L )
+ {
+ t = q + b;
+
+ if ( r >= t )
+ {
+ r -= t;
+ q = t + b;
+ }
+
+ r <<= 1;
+ b >>= 1;
+ }
+
+ q >>= 8;
+
+ return (FT_16D16)q;
+ }
+
+
+ /**************************************************************************
+ *
+ * format and sign manipulating functions
+ *
+ */
+
+ /*
+ * Convert 16.16 fixed point values to the desired output format.
+ * In this case we reduce 16.16 fixed point values to normalized
+ * 8-bit values.
+ *
+ * The `max_value` in the parameter is the maximum value in the
+ * distance field map and is equal to the spread. We normalize
+ * the distances using this value instead of computing the maximum
+ * value for the entire bitmap.
+ *
+ * You can use this function to map the 16.16 signed values to any
+ * format required. Do note that the output buffer is 8-bit, so only
+ * use an 8-bit format for `FT_SDFFormat`, or increase the buffer size in
+ * `ftsdfrend.c`.
+ */
+ FT_LOCAL_DEF( FT_SDFFormat )
+ map_fixed_to_sdf( FT_16D16 dist,
+ FT_16D16 max_value )
+ {
+ FT_SDFFormat out;
+ FT_16D16 udist;
+
+
+ /* normalize the distance values */
+ dist = FT_DivFix( dist, max_value );
+
+ udist = dist < 0 ? -dist : dist;
+
+ /* Reduce the distance values to 8 bits. */
+ /* */
+ /* Since +1/-1 in 16.16 takes the 16th bit, we right-shift */
+ /* the number by 9 to make it fit into the 7-bit range. */
+ /* */
+ /* One bit is reserved for the sign. */
+ udist >>= 9;
+
+ /* Since `char` can only store a maximum positive value */
+ /* of 127 we need to make sure it does not wrap around and */
+ /* give a negative value. */
+ if ( dist > 0 && udist > 127 )
+ udist = 127;
+ if ( dist < 0 && udist > 128 )
+ udist = 128;
+
+ /* Output the data; negative values are from [0, 127] and positive */
+ /* from [128, 255]. One important thing is that negative values */
+ /* are inverted here, that means [0, 128] maps to [-128, 0] linearly. */
+ /* More on that in `freetype.h` near the documentation of */
+ /* `FT_RENDER_MODE_SDF`. */
+ out = dist < 0 ? 128 - (FT_SDFFormat)udist
+ : (FT_SDFFormat)udist + 128;
+
+ return out;
+ }
+
+
+ /*
+ * Invert the signed distance packed into the corresponding format.
+ * So if the values are negative they will become positive in the
+ * chosen format.
+ *
+ * [Note]: This function should only be used after converting the
+ * 16.16 signed distance values to `FT_SDFFormat`. If that
+ * conversion has not been done, then simply invert the sign
+ * and use the above function to pack the values.
+ */
+ FT_LOCAL_DEF( FT_SDFFormat )
+ invert_sign( FT_SDFFormat dist )
+ {
+ return 255 - dist;
+ }
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdfcommon.h b/src/3rdparty/freetype/src/sdf/ftsdfcommon.h
new file mode 100644
index 0000000000..af4490bbca
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdfcommon.h
@@ -0,0 +1,141 @@
+/****************************************************************************
+ *
+ * ftsdfcommon.h
+ *
+ * Auxiliary data for Signed Distance Field support (specification).
+ *
+ * Copyright (C) 2020-2022 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.
+ *
+ */
+
+
+ /****************************************************
+ *
+ * This file contains common functions and properties
+ * for both the 'sdf' and 'bsdf' renderers.
+ *
+ */
+
+#ifndef FTSDFCOMMON_H_
+#define FTSDFCOMMON_H_
+
+#include <ft2build.h>
+#include FT_CONFIG_CONFIG_H
+#include <freetype/internal/ftobjs.h>
+
+
+FT_BEGIN_HEADER
+
+
+ /**************************************************************************
+ *
+ * default values (cannot be set individually for each renderer)
+ *
+ */
+
+ /* default spread value */
+#define DEFAULT_SPREAD 8
+ /* minimum spread supported by the renderer */
+#define MIN_SPREAD 2
+ /* maximum spread supported by the renderer */
+#define MAX_SPREAD 32
+ /* pixel size in 26.6 */
+#define ONE_PIXEL ( 1 << 6 )
+
+
+ /**************************************************************************
+ *
+ * common definitions (cannot be set individually for each renderer)
+ *
+ */
+
+ /* If this macro is set to 1 the rasterizer uses squared distances for */
+ /* computation. It can greatly improve the performance but there is a */
+ /* chance of overflow and artifacts. You can safely use it up to a */
+ /* pixel size of 128. */
+#ifndef USE_SQUARED_DISTANCES
+#define USE_SQUARED_DISTANCES 0
+#endif
+
+
+ /**************************************************************************
+ *
+ * common macros
+ *
+ */
+
+ /* convert int to 26.6 fixed-point */
+#define FT_INT_26D6( x ) ( x * 64 )
+ /* convert int to 16.16 fixed-point */
+#define FT_INT_16D16( x ) ( x * 65536 )
+ /* convert 26.6 to 16.16 fixed-point */
+#define FT_26D6_16D16( x ) ( x * 1024 )
+
+
+ /* Convenience macro to call a function; it */
+ /* jumps to label `Exit` if an error occurs. */
+#define FT_CALL( x ) do \
+ { \
+ error = ( x ); \
+ if ( error != FT_Err_Ok ) \
+ goto Exit; \
+ } while ( 0 )
+
+
+ /*
+ * The macro `VECTOR_LENGTH_16D16` computes either squared distances or
+ * actual distances, depending on the value of `USE_SQUARED_DISTANCES`.
+ *
+ * By using squared distances the performance can be greatly improved but
+ * there is a risk of overflow.
+ */
+#if USE_SQUARED_DISTANCES
+#define VECTOR_LENGTH_16D16( v ) ( FT_MulFix( v.x, v.x ) + \
+ FT_MulFix( v.y, v.y ) )
+#else
+#define VECTOR_LENGTH_16D16( v ) FT_Vector_Length( &v )
+#endif
+
+
+ /**************************************************************************
+ *
+ * common typedefs
+ *
+ */
+
+ typedef FT_Vector FT_26D6_Vec; /* with 26.6 fixed-point components */
+ typedef FT_Vector FT_16D16_Vec; /* with 16.16 fixed-point components */
+
+ typedef FT_Fixed FT_16D16; /* 16.16 fixed-point representation */
+ typedef FT_Fixed FT_26D6; /* 26.6 fixed-point representation */
+ typedef FT_Byte FT_SDFFormat; /* format to represent SDF data */
+
+ typedef FT_BBox FT_CBox; /* control box of a curve */
+
+
+ FT_LOCAL( FT_16D16 )
+ square_root( FT_16D16 val );
+
+ FT_LOCAL( FT_SDFFormat )
+ map_fixed_to_sdf( FT_16D16 dist,
+ FT_16D16 max_value );
+
+ FT_LOCAL( FT_SDFFormat )
+ invert_sign( FT_SDFFormat dist );
+
+
+FT_END_HEADER
+
+#endif /* FTSDFCOMMON_H_ */
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdferrs.h b/src/3rdparty/freetype/src/sdf/ftsdferrs.h
new file mode 100644
index 0000000000..b28867609a
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdferrs.h
@@ -0,0 +1,37 @@
+/****************************************************************************
+ *
+ * ftsdferrs.h
+ *
+ * Signed Distance Field error codes (specification only).
+ *
+ * Copyright (C) 2020-2022 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.
+ *
+ */
+
+
+#ifndef FTSDFERRS_H_
+#define FTSDFERRS_H_
+
+#include <freetype/ftmoderr.h>
+
+#undef FTERRORS_H_
+
+#undef FT_ERR_PREFIX
+#define FT_ERR_PREFIX Sdf_Err_
+#define FT_ERR_BASE FT_Mod_Err_Sdf
+
+#include <freetype/fterrors.h>
+
+#endif /* FTSDFERRS_H_ */
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdfrend.c b/src/3rdparty/freetype/src/sdf/ftsdfrend.c
new file mode 100644
index 0000000000..b0213a40d3
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdfrend.c
@@ -0,0 +1,604 @@
+/****************************************************************************
+ *
+ * ftsdfrend.c
+ *
+ * Signed Distance Field renderer interface (body).
+ *
+ * Copyright (C) 2020-2022 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/ftdebug.h>
+#include <freetype/internal/ftobjs.h>
+#include <freetype/internal/services/svprop.h>
+#include <freetype/ftoutln.h>
+#include <freetype/ftbitmap.h>
+#include "ftsdfrend.h"
+#include "ftsdf.h"
+
+#include "ftsdferrs.h"
+
+
+ /**************************************************************************
+ *
+ * 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 sdf
+
+
+ /**************************************************************************
+ *
+ * macros and default property values
+ *
+ */
+#define SDF_RENDERER( rend ) ( (SDF_Renderer)rend )
+
+
+ /**************************************************************************
+ *
+ * for setting properties
+ *
+ */
+
+ /* property setter function */
+ static FT_Error
+ sdf_property_set( FT_Module module,
+ const char* property_name,
+ const void* value,
+ FT_Bool value_is_string )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Renderer render = SDF_RENDERER( FT_RENDERER( module ) );
+
+ FT_UNUSED( value_is_string );
+
+
+ if ( ft_strcmp( property_name, "spread" ) == 0 )
+ {
+ FT_Int val = *(const FT_Int*)value;
+
+
+ if ( val > MAX_SPREAD || val < MIN_SPREAD )
+ {
+ FT_TRACE0(( "[sdf] sdf_property_set:"
+ " the `spread' property can have a value\n" ));
+ FT_TRACE0(( " "
+ " within range [%d, %d] (value provided: %d)\n",
+ MIN_SPREAD, MAX_SPREAD, val ));
+
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ render->spread = (FT_UInt)val;
+ FT_TRACE7(( "[sdf] sdf_property_set:"
+ " updated property `spread' to %d\n", val ));
+ }
+
+ else if ( ft_strcmp( property_name, "flip_sign" ) == 0 )
+ {
+ FT_Int val = *(const FT_Int*)value;
+
+
+ render->flip_sign = val ? 1 : 0;
+ FT_TRACE7(( "[sdf] sdf_property_set:"
+ " updated property `flip_sign' to %d\n", val ));
+ }
+
+ else if ( ft_strcmp( property_name, "flip_y" ) == 0 )
+ {
+ FT_Int val = *(const FT_Int*)value;
+
+
+ render->flip_y = val ? 1 : 0;
+ FT_TRACE7(( "[sdf] sdf_property_set:"
+ " updated property `flip_y' to %d\n", val ));
+ }
+
+ else if ( ft_strcmp( property_name, "overlaps" ) == 0 )
+ {
+ FT_Bool val = *(const FT_Bool*)value;
+
+
+ render->overlaps = val;
+ FT_TRACE7(( "[sdf] sdf_property_set:"
+ " updated property `overlaps' to %d\n", val ));
+ }
+
+ else
+ {
+ FT_TRACE0(( "[sdf] sdf_property_set:"
+ " missing property `%s'\n", property_name ));
+ error = FT_THROW( Missing_Property );
+ }
+
+ Exit:
+ return error;
+ }
+
+
+ /* property getter function */
+ static FT_Error
+ sdf_property_get( FT_Module module,
+ const char* property_name,
+ void* value )
+ {
+ FT_Error error = FT_Err_Ok;
+ SDF_Renderer render = SDF_RENDERER( FT_RENDERER( module ) );
+
+
+ if ( ft_strcmp( property_name, "spread" ) == 0 )
+ {
+ FT_UInt* val = (FT_UInt*)value;
+
+
+ *val = render->spread;
+ }
+
+ else if ( ft_strcmp( property_name, "flip_sign" ) == 0 )
+ {
+ FT_Int* val = (FT_Int*)value;
+
+
+ *val = render->flip_sign;
+ }
+
+ else if ( ft_strcmp( property_name, "flip_y" ) == 0 )
+ {
+ FT_Int* val = (FT_Int*)value;
+
+
+ *val = render->flip_y;
+ }
+
+ else if ( ft_strcmp( property_name, "overlaps" ) == 0 )
+ {
+ FT_Int* val = (FT_Int*)value;
+
+
+ *val = render->overlaps;
+ }
+
+ else
+ {
+ FT_TRACE0(( "[sdf] sdf_property_get:"
+ " missing property `%s'\n", property_name ));
+ error = FT_THROW( Missing_Property );
+ }
+
+ return error;
+ }
+
+
+ FT_DEFINE_SERVICE_PROPERTIESREC(
+ sdf_service_properties,
+
+ (FT_Properties_SetFunc)sdf_property_set, /* set_property */
+ (FT_Properties_GetFunc)sdf_property_get ) /* get_property */
+
+
+ FT_DEFINE_SERVICEDESCREC1(
+ sdf_services,
+
+ FT_SERVICE_ID_PROPERTIES, &sdf_service_properties )
+
+
+ static FT_Module_Interface
+ ft_sdf_requester( FT_Renderer render,
+ const char* module_interface )
+ {
+ FT_UNUSED( render );
+
+ return ft_service_list_lookup( sdf_services, module_interface );
+ }
+
+
+ /*************************************************************************/
+ /*************************************************************************/
+ /** **/
+ /** OUTLINE TO SDF CONVERTER **/
+ /** **/
+ /*************************************************************************/
+ /*************************************************************************/
+
+ /**************************************************************************
+ *
+ * interface functions
+ *
+ */
+
+ static FT_Error
+ ft_sdf_init( FT_Renderer render )
+ {
+ SDF_Renderer sdf_render = SDF_RENDERER( render );
+
+
+ sdf_render->spread = DEFAULT_SPREAD;
+ sdf_render->flip_sign = 0;
+ sdf_render->flip_y = 0;
+ sdf_render->overlaps = 0;
+
+ return FT_Err_Ok;
+ }
+
+
+ static void
+ ft_sdf_done( FT_Renderer render )
+ {
+ FT_UNUSED( render );
+ }
+
+
+ /* generate signed distance field from a glyph's slot image */
+ static FT_Error
+ ft_sdf_render( FT_Renderer module,
+ FT_GlyphSlot slot,
+ FT_Render_Mode mode,
+ const FT_Vector* origin )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Outline* outline = &slot->outline;
+ FT_Bitmap* bitmap = &slot->bitmap;
+ FT_Memory memory = NULL;
+ FT_Renderer render = NULL;
+
+ FT_Pos x_shift = 0;
+ FT_Pos y_shift = 0;
+
+ FT_Pos x_pad = 0;
+ FT_Pos y_pad = 0;
+
+ SDF_Raster_Params params;
+ SDF_Renderer sdf_module = SDF_RENDERER( module );
+
+
+ render = &sdf_module->root;
+ memory = render->root.memory;
+
+ /* check whether slot format is correct before rendering */
+ if ( slot->format != render->glyph_format )
+ {
+ error = FT_THROW( Invalid_Glyph_Format );
+ goto Exit;
+ }
+
+ /* check whether render mode is correct */
+ if ( mode != FT_RENDER_MODE_SDF )
+ {
+ error = FT_THROW( Cannot_Render_Glyph );
+ goto Exit;
+ }
+
+ /* deallocate the previously allocated bitmap */
+ if ( slot->internal->flags & FT_GLYPH_OWN_BITMAP )
+ {
+ FT_FREE( bitmap->buffer );
+ slot->internal->flags &= ~FT_GLYPH_OWN_BITMAP;
+ }
+
+ /* preset the bitmap using the glyph's outline; */
+ /* the sdf bitmap is similar to an anti-aliased bitmap */
+ /* with a slightly bigger size and different pixel mode */
+ if ( ft_glyphslot_preset_bitmap( slot, FT_RENDER_MODE_NORMAL, origin ) )
+ {
+ error = FT_THROW( Raster_Overflow );
+ goto Exit;
+ }
+
+ /* nothing to render */
+ if ( !bitmap->rows || !bitmap->pitch )
+ return FT_Err_Ok;
+
+ /* the padding will simply be equal to the `spread' */
+ x_pad = sdf_module->spread;
+ y_pad = sdf_module->spread;
+
+ /* apply the padding; will be in all the directions */
+ bitmap->rows += y_pad * 2;
+ bitmap->width += x_pad * 2;
+
+ /* ignore the pitch, pixel mode and set custom */
+ bitmap->pixel_mode = FT_PIXEL_MODE_GRAY;
+ bitmap->pitch = (int)( bitmap->width );
+ bitmap->num_grays = 255;
+
+ /* allocate new buffer */
+ if ( FT_ALLOC_MULT( bitmap->buffer, bitmap->rows, bitmap->pitch ) )
+ goto Exit;
+
+ slot->internal->flags |= FT_GLYPH_OWN_BITMAP;
+
+ slot->bitmap_top += y_pad;
+ slot->bitmap_left -= x_pad;
+
+ x_shift = 64 * -slot->bitmap_left;
+ y_shift = 64 * -slot->bitmap_top;
+ y_shift += 64 * (FT_Int)bitmap->rows;
+
+ if ( origin )
+ {
+ x_shift += origin->x;
+ y_shift += origin->y;
+ }
+
+ /* translate outline to render it into the bitmap */
+ if ( x_shift || y_shift )
+ FT_Outline_Translate( outline, x_shift, y_shift );
+
+ /* set up parameters */
+ params.root.target = bitmap;
+ params.root.source = outline;
+ params.root.flags = FT_RASTER_FLAG_SDF;
+ params.spread = sdf_module->spread;
+ params.flip_sign = sdf_module->flip_sign;
+ params.flip_y = sdf_module->flip_y;
+ params.overlaps = sdf_module->overlaps;
+
+ /* render the outline */
+ error = render->raster_render( render->raster,
+ (const FT_Raster_Params*)&params );
+
+ /* transform the outline back to the original state */
+ if ( x_shift || y_shift )
+ FT_Outline_Translate( outline, -x_shift, -y_shift );
+
+ Exit:
+ if ( !error )
+ {
+ /* the glyph is successfully rendered to a bitmap */
+ slot->format = FT_GLYPH_FORMAT_BITMAP;
+ }
+ else if ( slot->internal->flags & FT_GLYPH_OWN_BITMAP )
+ {
+ FT_FREE( bitmap->buffer );
+ slot->internal->flags &= ~FT_GLYPH_OWN_BITMAP;
+ }
+
+ return error;
+ }
+
+
+ /* transform the glyph using matrix and/or delta */
+ static FT_Error
+ ft_sdf_transform( FT_Renderer render,
+ FT_GlyphSlot slot,
+ const FT_Matrix* matrix,
+ const FT_Vector* delta )
+ {
+ FT_Error error = FT_Err_Ok;
+
+
+ if ( slot->format != render->glyph_format )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ if ( matrix )
+ FT_Outline_Transform( &slot->outline, matrix );
+
+ if ( delta )
+ FT_Outline_Translate( &slot->outline, delta->x, delta->y );
+
+ Exit:
+ return error;
+ }
+
+
+ /* return the control box of a glyph's outline */
+ static void
+ ft_sdf_get_cbox( FT_Renderer render,
+ FT_GlyphSlot slot,
+ FT_BBox* cbox )
+ {
+ FT_ZERO( cbox );
+
+ if ( slot->format == render->glyph_format )
+ FT_Outline_Get_CBox( &slot->outline, cbox );
+ }
+
+
+ /* set render specific modes or attributes */
+ static FT_Error
+ ft_sdf_set_mode( FT_Renderer render,
+ FT_ULong mode_tag,
+ FT_Pointer data )
+ {
+ /* pass it to the rasterizer */
+ return render->clazz->raster_class->raster_set_mode( render->raster,
+ mode_tag,
+ data );
+ }
+
+
+ FT_DEFINE_RENDERER(
+ ft_sdf_renderer_class,
+
+ FT_MODULE_RENDERER,
+ sizeof ( SDF_Renderer_Module ),
+
+ "sdf",
+ 0x10000L,
+ 0x20000L,
+
+ NULL,
+
+ (FT_Module_Constructor)ft_sdf_init,
+ (FT_Module_Destructor) ft_sdf_done,
+ (FT_Module_Requester) ft_sdf_requester,
+
+ FT_GLYPH_FORMAT_OUTLINE,
+
+ (FT_Renderer_RenderFunc) ft_sdf_render, /* render_glyph */
+ (FT_Renderer_TransformFunc)ft_sdf_transform, /* transform_glyph */
+ (FT_Renderer_GetCBoxFunc) ft_sdf_get_cbox, /* get_glyph_cbox */
+ (FT_Renderer_SetModeFunc) ft_sdf_set_mode, /* set_mode */
+
+ (FT_Raster_Funcs*)&ft_sdf_raster /* raster_class */
+ )
+
+
+ /*************************************************************************/
+ /*************************************************************************/
+ /** **/
+ /** BITMAP TO SDF CONVERTER **/
+ /** **/
+ /*************************************************************************/
+ /*************************************************************************/
+
+ /* generate signed distance field from glyph's bitmap */
+ static FT_Error
+ ft_bsdf_render( FT_Renderer module,
+ FT_GlyphSlot slot,
+ FT_Render_Mode mode,
+ const FT_Vector* origin )
+ {
+ FT_Error error = FT_Err_Ok;
+ FT_Memory memory = NULL;
+
+ FT_Bitmap* bitmap = &slot->bitmap;
+ FT_Renderer render = NULL;
+ FT_Bitmap target;
+
+ FT_Pos x_pad = 0;
+ FT_Pos y_pad = 0;
+
+ SDF_Raster_Params params;
+ SDF_Renderer sdf_module = SDF_RENDERER( module );
+
+
+ /* initialize the bitmap in case any error occurs */
+ FT_Bitmap_Init( &target );
+
+ render = &sdf_module->root;
+ memory = render->root.memory;
+
+ /* check whether slot format is correct before rendering */
+ if ( slot->format != render->glyph_format )
+ {
+ error = FT_THROW( Invalid_Glyph_Format );
+ goto Exit;
+ }
+
+ /* check whether render mode is correct */
+ if ( mode != FT_RENDER_MODE_SDF )
+ {
+ error = FT_THROW( Cannot_Render_Glyph );
+ goto Exit;
+ }
+
+ if ( origin )
+ {
+ FT_ERROR(( "ft_bsdf_render: can't translate the bitmap\n" ));
+
+ error = FT_THROW( Unimplemented_Feature );
+ goto Exit;
+ }
+
+ /* Do not generate SDF if the bitmap is not owned by the */
+ /* glyph: it might be that the source buffer is already freed. */
+ if ( !( slot->internal->flags & FT_GLYPH_OWN_BITMAP ) )
+ {
+ FT_ERROR(( "ft_bsdf_render: can't generate SDF from"
+ " unowned source bitmap\n" ));
+
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* nothing to render */
+ if ( !bitmap->rows || !bitmap->pitch )
+ return FT_Err_Ok;
+
+ FT_Bitmap_New( &target );
+
+ /* padding will simply be equal to `spread` */
+ x_pad = sdf_module->spread;
+ y_pad = sdf_module->spread;
+
+ /* apply padding, which extends to all directions */
+ target.rows = bitmap->rows + y_pad * 2;
+ target.width = bitmap->width + x_pad * 2;
+
+ /* set up the target bitmap */
+ target.pixel_mode = FT_PIXEL_MODE_GRAY;
+ target.pitch = (int)( target.width );
+ target.num_grays = 255;
+
+ if ( FT_ALLOC_MULT( target.buffer, target.rows, target.pitch ) )
+ goto Exit;
+
+ /* set up parameters */
+ params.root.target = &target;
+ params.root.source = bitmap;
+ params.root.flags = FT_RASTER_FLAG_SDF;
+ params.spread = sdf_module->spread;
+ params.flip_sign = sdf_module->flip_sign;
+ params.flip_y = sdf_module->flip_y;
+
+ error = render->raster_render( render->raster,
+ (const FT_Raster_Params*)&params );
+
+ Exit:
+ if ( !error )
+ {
+ /* the glyph is successfully converted to a SDF */
+ if ( slot->internal->flags & FT_GLYPH_OWN_BITMAP )
+ {
+ FT_FREE( bitmap->buffer );
+ slot->internal->flags &= ~FT_GLYPH_OWN_BITMAP;
+ }
+
+ slot->bitmap = target;
+ slot->bitmap_top += y_pad;
+ slot->bitmap_left -= x_pad;
+ slot->internal->flags |= FT_GLYPH_OWN_BITMAP;
+ }
+ else if ( target.buffer )
+ FT_FREE( target.buffer );
+
+ return error;
+ }
+
+
+ FT_DEFINE_RENDERER(
+ ft_bitmap_sdf_renderer_class,
+
+ FT_MODULE_RENDERER,
+ sizeof ( SDF_Renderer_Module ),
+
+ "bsdf",
+ 0x10000L,
+ 0x20000L,
+
+ NULL,
+
+ (FT_Module_Constructor)ft_sdf_init,
+ (FT_Module_Destructor) ft_sdf_done,
+ (FT_Module_Requester) ft_sdf_requester,
+
+ FT_GLYPH_FORMAT_BITMAP,
+
+ (FT_Renderer_RenderFunc) ft_bsdf_render, /* render_glyph */
+ (FT_Renderer_TransformFunc)ft_sdf_transform, /* transform_glyph */
+ (FT_Renderer_GetCBoxFunc) ft_sdf_get_cbox, /* get_glyph_cbox */
+ (FT_Renderer_SetModeFunc) ft_sdf_set_mode, /* set_mode */
+
+ (FT_Raster_Funcs*)&ft_bitmap_sdf_raster /* raster_class */
+ )
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/ftsdfrend.h b/src/3rdparty/freetype/src/sdf/ftsdfrend.h
new file mode 100644
index 0000000000..cdb9c5f02f
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/ftsdfrend.h
@@ -0,0 +1,118 @@
+/****************************************************************************
+ *
+ * ftsdfrend.h
+ *
+ * Signed Distance Field renderer interface (specification).
+ *
+ * Copyright (C) 2020-2022 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.
+ *
+ */
+
+
+#ifndef FTSDFREND_H_
+#define FTSDFREND_H_
+
+#include <freetype/ftrender.h>
+#include <freetype/ftmodapi.h>
+#include <freetype/internal/ftobjs.h>
+
+FT_BEGIN_HEADER
+
+
+ /**************************************************************************
+ *
+ * @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.
+ *
+ */
+ typedef struct SDF_Renderer_Module_
+ {
+ FT_RendererRec root;
+ FT_UInt spread;
+ FT_Bool flip_sign;
+ FT_Bool flip_y;
+ FT_Bool overlaps;
+
+ } SDF_Renderer_Module, *SDF_Renderer;
+
+
+ /**************************************************************************
+ *
+ * @renderer:
+ * ft_sdf_renderer_class
+ *
+ * @description:
+ * Renderer to convert @FT_Outline to signed distance fields.
+ *
+ */
+ FT_DECLARE_RENDERER( ft_sdf_renderer_class )
+
+
+ /**************************************************************************
+ *
+ * @renderer:
+ * ft_bitmap_sdf_renderer_class
+ *
+ * @description:
+ * This is not exactly a renderer; it is just a converter that
+ * transforms bitmaps to signed distance fields.
+ *
+ * @note:
+ * This is not a separate module, it is part of the 'sdf' module.
+ *
+ */
+ FT_DECLARE_RENDERER( ft_bitmap_sdf_renderer_class )
+
+
+FT_END_HEADER
+
+#endif /* FTSDFREND_H_ */
+
+
+/* END */
diff --git a/src/3rdparty/freetype/src/sdf/module.mk b/src/3rdparty/freetype/src/sdf/module.mk
new file mode 100644
index 0000000000..772bc48bf7
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/module.mk
@@ -0,0 +1,29 @@
+#
+# FreeType 2 Signed Distance Field module definition
+#
+
+
+# Copyright (C) 2020-2022 by
+# David Turner, Robert Wilhelm, and Werner Lemberg.
+#
+# 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.
+
+
+FTMODULE_H_COMMANDS += SDF_RENDERER
+FTMODULE_H_COMMANDS += BSDF_RENDERER
+
+define SDF_RENDERER
+$(OPEN_DRIVER) FT_Renderer_Class, ft_sdf_renderer_class $(CLOSE_DRIVER)
+$(ECHO_DRIVER)sdf $(ECHO_DRIVER_DESC)signed distance field renderer$(ECHO_DRIVER_DONE)
+endef
+
+define BSDF_RENDERER
+$(OPEN_DRIVER) FT_Renderer_Class, ft_bitmap_sdf_renderer_class $(CLOSE_DRIVER)
+$(ECHO_DRIVER)bsdf $(ECHO_DRIVER_DESC)bitmap to signed distance field converter$(ECHO_DRIVER_DONE)
+endef
+
+#EOF
diff --git a/src/3rdparty/freetype/src/sdf/rules.mk b/src/3rdparty/freetype/src/sdf/rules.mk
new file mode 100644
index 0000000000..5239d643ff
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/rules.mk
@@ -0,0 +1,78 @@
+#
+# FreeType 2 Signed Distance Field driver configuration rules
+#
+
+
+# Copyright (C) 2020-2022 by
+# David Turner, Robert Wilhelm, and Werner Lemberg.
+#
+# 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.
+
+
+# sdf driver directory
+#
+SDF_DIR := $(SRC_DIR)/sdf
+
+
+# compilation flags for the driver
+#
+SDF_COMPILE := $(CC) $(ANSIFLAGS) \
+ $I$(subst /,$(COMPILER_SEP),$(SDF_DIR)) \
+ $(INCLUDE_FLAGS) \
+ $(FT_CFLAGS)
+
+
+# sdf driver sources (i.e., C files)
+#
+SDF_DRV_SRC := $(SDF_DIR)/ftsdfrend.c \
+ $(SDF_DIR)/ftsdf.c \
+ $(SDF_DIR)/ftbsdf.c \
+ $(SDF_DIR)/ftsdfcommon.c
+
+
+# sdf driver headers
+#
+SDF_DRV_H := $(SDF_DIR)/ftsdfrend.h \
+ $(SDF_DIR)/ftsdf.h \
+ $(SDF_DIR)/ftsdferrs.h \
+ $(SDF_DIR)/ftsdfcommon.h
+
+
+# sdf driver object(s)
+#
+# SDF_DRV_OBJ_M is used during `multi' builds.
+# SDF_DRV_OBJ_S is used during `single' builds.
+#
+SDF_DRV_OBJ_M := $(SDF_DRV_SRC:$(SDF_DIR)/%.c=$(OBJ_DIR)/%.$O)
+SDF_DRV_OBJ_S := $(OBJ_DIR)/sdf.$O
+
+
+# sdf driver source file for single build
+#
+SDF_DRV_SRC_S := $(SDF_DIR)/sdf.c
+
+
+# sdf driver - single object
+#
+$(SDF_DRV_OBJ_S): $(SDF_DRV_SRC_S) $(SDF_DRV_SRC) \
+ $(FREETYPE_H) $(SDF_DRV_H)
+ $(SDF_COMPILE) $T$(subst /,$(COMPILER_SEP),$@ $(SDF_DRV_SRC_S))
+
+
+# sdf driver - multiple objects
+#
+$(OBJ_DIR)/%.$O: $(SDF_DIR)/%.c $(FREETYPE_H) $(SDF_DRV_H)
+ $(SDF_COMPILE) $T$(subst /,$(COMPILER_SEP),$@ $<)
+
+
+# update main driver list
+#
+DRV_OBJS_S += $(SDF_DRV_OBJ_S)
+DRV_OBJS_M += $(SDF_DRV_OBJ_M)
+
+
+# EOF
diff --git a/src/3rdparty/freetype/src/sdf/sdf.c b/src/3rdparty/freetype/src/sdf/sdf.c
new file mode 100644
index 0000000000..297ba9ab02
--- /dev/null
+++ b/src/3rdparty/freetype/src/sdf/sdf.c
@@ -0,0 +1,29 @@
+/****************************************************************************
+ *
+ * sdf.c
+ *
+ * FreeType Signed Distance Field renderer module component (body only).
+ *
+ * Copyright (C) 2020-2022 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.
+ *
+ */
+
+
+#define FT_MAKE_OPTION_SINGLE_OBJECT
+
+#include "ftsdfrend.c"
+#include "ftsdfcommon.c"
+#include "ftbsdf.c"
+#include "ftsdf.c"
+
+
+/* END */
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-07 11:15:59 +0000