/**************************************************************************** * * ftsdf.c * * Signed Distance Field support for outline fonts (body). * * Copyright (C) 2020-2023 by * David Turner, Robert Wilhelm, and Werner Lemberg. * * Written by Anuj Verma. * * This file is part of the FreeType project, and may only be used, * modified, and distributed under the terms of the FreeType project * license, LICENSE.TXT. By continuing to use, modify, or distribute * this file you indicate that you have read the license and * understand and accept it fully. * */ #include <freetype/internal/ftobjs.h> #include <freetype/internal/ftdebug.h> #include <freetype/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 … /************************************************************************** * * 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 … #endif /* * The number of intervals a Bezier curve gets sampled and checked to find * the shortest distance. */ #define MAX_NEWTON_DIVISIONS … /* * 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 … /* * 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 … #if 0 /* * Coarse grid dimension. Will probably be removed in the future because * coarse grid optimization is the slowest algorithm. */ #define CG_DIMEN … #endif /************************************************************************** * * macros * */ #define MUL_26D6( a, b ) … #define VEC_26D6_DOT( p, q ) … /************************************************************************** * * 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. * */ SDF_PRaster; /************************************************************************** * * @Enum: * SDF_Edge_Type * * @Description: * Enumeration of all curve types present in fonts. * * @Fields: * SDF_EDGE_UNDEFINED :: * Undefined edge, simply used to initialize and detect errors. * * SDF_EDGE_LINE :: * Line segment with start and end point. * * SDF_EDGE_CONIC :: * A conic/quadratic Bezier curve with start, end, and one control * point. * * SDF_EDGE_CUBIC :: * A cubic Bezier curve with start, end, and two control points. * */ 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. * */ 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. * */ 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. * */ 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. * */ 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. * */ 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. * */ SDF_Params; /************************************************************************** * * constants, initializer, and destructor * */ static const FT_Vector zero_vector = …; static const SDF_Edge null_edge = …; static const SDF_Contour null_contour = …; static const SDF_Shape null_shape = …; static const SDF_Signed_Distance max_sdf = …; /* 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 ) { … } /* Free the allocated `edge` variable. */ static void sdf_edge_done( FT_Memory memory, SDF_Edge** 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 ) { … } /* Free the allocated `contour` variable. */ /* Also free the list of edges. */ static void sdf_contour_done( FT_Memory memory, SDF_Contour** 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 ) { … } /* Free the allocated `shape` variable. */ /* Also free the list of contours. */ static void sdf_shape_done( SDF_Shape** 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 ) { … } /* 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 ) { … } /* 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 ) { … } /* 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 ) { … } /* 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 ) { … } /************************************************************************** * * utility functions * */ /* Return the control box of an edge. The control box is a rectangle */ /* in which all the control points can fit tightly. */ static FT_CBox get_control_box( SDF_Edge edge ) { … } /* 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 ) { … } /* 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 ) { … } /* 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 ) { … } /* Split a conic Bezier curve into a number of lines */ /* and add them to `out'. */ /* */ /* This function uses recursion; we thus need */ /* parameter `max_splits' for stopping. */ static FT_Error split_sdf_conic( FT_Memory memory, FT_26D6_Vec* control_points, FT_UInt max_splits, SDF_Edge** out ) { … } /* Split a cubic Bezier curve into a number of lines */ /* and add them to `out`. */ /* */ /* This function uses recursion; we thus need */ /* parameter `max_splits' for stopping. */ static FT_Error split_sdf_cubic( FT_Memory memory, FT_26D6_Vec* control_points, FT_UInt max_splits, SDF_Edge** out ) { … } /* 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 ) { … } /************************************************************************** * * 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 ) { … } /************************************************************************** * * @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 ) { … } /************************************************************************** * * @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 = { 0, 0 }; /* 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 ) { … } #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 ) { … } /************************************************************************** * * @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 ) { … } /* `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, ¤t_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, ¤t_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 ) { … } /************************************************************************** * * @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 ) { … } /************************************************************************** * * @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 ) { … } /************************************************************************** * * interface functions * */ static FT_Error sdf_raster_new( void* memory_, /* FT_Memory */ FT_Raster* araster_ ) /* SDF_PRaster* */ { … } static void sdf_raster_reset( FT_Raster raster, unsigned char* pool_base, unsigned long pool_size ) { … } static FT_Error sdf_raster_set_mode( FT_Raster raster, unsigned long mode, void* args ) { … } static FT_Error sdf_raster_render( FT_Raster raster, const FT_Raster_Params* params ) { … } static void sdf_raster_done( FT_Raster 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 */
Codebase Browser
godot