summaryrefslogtreecommitdiff
path: root/Build/source/libs/freetype2/freetype-src/src/sdf
diff options
context:
space:
mode:
authorAkira Kakuto <kakuto@fuk.kindai.ac.jp>2021-08-29 06:19:44 +0000
committerAkira Kakuto <kakuto@fuk.kindai.ac.jp>2021-08-29 06:19:44 +0000
commit0de5be92a3a0fe27e8521fc4de67e19b1057842e (patch)
treee93a390fe965486cca19498840cb8d7904252fec /Build/source/libs/freetype2/freetype-src/src/sdf
parent27ce96eea3f1190bd744448cfa149e8d767af95a (diff)
revert freetype to 2.10.4
git-svn-id: svn://tug.org/texlive/trunk@60360 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/libs/freetype2/freetype-src/src/sdf')
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftbsdf.c1349
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.c3878
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.h97
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.c147
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.h139
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdferrs.h37
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.c590
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.h118
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/module.mk29
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/rules.mk78
-rw-r--r--Build/source/libs/freetype2/freetype-src/src/sdf/sdf.c29
11 files changed, 0 insertions, 6491 deletions
diff --git a/Build/source/libs/freetype2/freetype-src/src/sdf/ftbsdf.c b/Build/source/libs/freetype2/freetype-src/src/sdf/ftbsdf.c
deleted file mode 100644
index db4a2dd11aa..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftbsdf.c
+++ /dev/null
@@ -1,1349 +0,0 @@
-/****************************************************************************
- *
- * ftbsdf.c
- *
- * Signed Distance Field support for bitmap fonts (body only).
- *
- * Copyright (C) 2020-2021 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;
-
-
- /**************************************************************************
- *
- * @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 `near` parameter. Can be squared or absolute
- * depending on the `USE_SQUARED_DISTANCES` macro defined in file
- * `ftsdfcommon.h`.
- *
- * near ::
- * 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 near;
- 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].near = compute_edge_distance( ed + index,
- i, j,
- worker->width,
- worker->rows );
- ed[index].dist = VECTOR_LENGTH_16D16( ed[index].near );
- }
- else
- {
- /* for non-edge pixels assign far away distances */
- ed[index].dist = 400 * ONE;
- ed[index].near.x = 200 * ONE;
- ed[index].near.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;
-
- pixel = 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->near;
-
- 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->near = 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; 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; 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 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;
- }
-
-#if USE_SQUARED_DISTANCES
- spread = FT_INT_16D16( worker->params.spread *
- worker->params.spread );
-#else
- spread = 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 > spread )
- dist = spread;
-
-#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,
- FT_Raster* araster )
- {
- FT_Error error = FT_Err_Ok;
- BSDF_TRaster* raster = NULL;
-
-
- *araster = 0;
- if ( !FT_ALLOC( raster, sizeof ( BSDF_TRaster ) ) )
- {
- raster->memory = memory;
- *araster = (FT_Raster)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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.c b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.c
deleted file mode 100644
index d3722b1dc17..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.c
+++ /dev/null
@@ -1,3878 +0,0 @@
-/****************************************************************************
- *
- * ftsdf.c
- *
- * Signed Distance Field support for outline fonts (body).
- *
- * Copyright (C) 2020-2021 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;
-
-
- /**************************************************************************
- *
- * @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_QALLOC( ptr, sizeof ( *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_QALLOC( ptr, sizeof ( *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_QALLOC( ptr, sizeof ( *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;
-
- 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 a 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;
- 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_Int 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_Int max_splits,
- SDF_Edge** out )
- {
- FT_Error error = FT_Err_Ok;
- FT_26D6_Vec cpos[7];
- SDF_Edge* left,* right;
-
-
- if ( !memory || !out )
- {
- error = FT_THROW( Invalid_Argument );
- goto Exit;
- }
-
- /* split the conic */
- cpos[0] = control_points[0];
- cpos[1] = control_points[1];
- cpos[2] = control_points[2];
- cpos[3] = control_points[3];
-
- 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];
-
-
- ctrls[0] = edge->start_pos;
- ctrls[1] = edge->control_a;
- ctrls[2] = edge->end_pos;
-
- error = split_sdf_conic( memory, ctrls, 32, &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 );
- 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 = fixed_spread * fixed_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;
-
-
- 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;
-
- /* square_root the values and fit in a 6.10 fixed-point */
- 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 if ( dists[index].distance > dist.distance )
- dists[index] = dist;
- else if ( FT_ABS( dists[index].distance - dist.distance )
- < CORNER_CHECK_EPSILON )
- dists[index] = resolve_corner( 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,
- FT_Raster* araster)
- {
- FT_Error error = FT_Err_Ok;
- SDF_TRaster* raster = NULL;
- FT_Int line = __LINE__;
-
- /* in non-debugging mode this is not used */
- FT_UNUSED( line );
-
-
- *araster = 0;
- if ( !FT_ALLOC( raster, sizeof ( SDF_TRaster ) ) )
- {
- raster->memory = memory;
- *araster = (FT_Raster)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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.h b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.h
deleted file mode 100644
index 187b418af3c..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdf.h
+++ /dev/null
@@ -1,97 +0,0 @@
-/****************************************************************************
- *
- * ftsdf.h
- *
- * Signed Distance Field support (specification).
- *
- * Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.c b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.c
deleted file mode 100644
index 91aa521bb31..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.c
+++ /dev/null
@@ -1,147 +0,0 @@
-/****************************************************************************
- *
- * ftsdfcommon.c
- *
- * Auxiliary data for Signed Distance Field support (body).
- *
- * Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.h b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.h
deleted file mode 100644
index 44f6bba53f8..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfcommon.h
+++ /dev/null
@@ -1,139 +0,0 @@
-/****************************************************************************
- *
- * ftsdfcommon.h
- *
- * Auxiliary data for Signed Distance Field support (specification).
- *
- * Copyright (C) 2020-2021 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
-
-
- /**************************************************************************
- *
- * 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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdferrs.h b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdferrs.h
deleted file mode 100644
index dbb113d5379..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdferrs.h
+++ /dev/null
@@ -1,37 +0,0 @@
-/****************************************************************************
- *
- * ftsdferrs.h
- *
- * Signed Distance Field error codes (specification only).
- *
- * Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.c b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.c
deleted file mode 100644
index 420ad496c74..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.c
+++ /dev/null
@@ -1,590 +0,0 @@
-/****************************************************************************
- *
- * ftsdfrend.c
- *
- * Signed Distance Field renderer interface (body).
- *
- * Copyright (C) 2020-2021 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;
- }
-
- if ( !bitmap->rows || !bitmap->pitch )
- goto Exit;
-
- /* 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 );
-
- 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;
- }
-
- if ( x_shift || y_shift )
- FT_Outline_Translate( outline, -x_shift, -y_shift );
-
- 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;
- }
-
- if ( !bitmap->rows || !bitmap->pitch )
- goto Exit;
-
- 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/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.h b/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.h
deleted file mode 100644
index bc88707ec24..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/ftsdfrend.h
+++ /dev/null
@@ -1,118 +0,0 @@
-/****************************************************************************
- *
- * ftsdfrend.h
- *
- * Signed Distance Field renderer interface (specification).
- *
- * Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/module.mk b/Build/source/libs/freetype2/freetype-src/src/sdf/module.mk
deleted file mode 100644
index 6be4b0c6d47..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/module.mk
+++ /dev/null
@@ -1,29 +0,0 @@
-#
-# FreeType 2 Signed Distance Field module definition
-#
-
-
-# Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/rules.mk b/Build/source/libs/freetype2/freetype-src/src/sdf/rules.mk
deleted file mode 100644
index 7e7e4fbe860..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/rules.mk
+++ /dev/null
@@ -1,78 +0,0 @@
-#
-# FreeType 2 Signed Distance Field driver configuration rules
-#
-
-
-# Copyright (C) 2020-2021 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/Build/source/libs/freetype2/freetype-src/src/sdf/sdf.c b/Build/source/libs/freetype2/freetype-src/src/sdf/sdf.c
deleted file mode 100644
index 1bc3fc385cc..00000000000
--- a/Build/source/libs/freetype2/freetype-src/src/sdf/sdf.c
+++ /dev/null
@@ -1,29 +0,0 @@
-/****************************************************************************
- *
- * sdf.c
- *
- * FreeType Signed Distance Field renderer module component (body only).
- *
- * Copyright (C) 2020-2021 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 */