[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freetype2] GSoC-2020-anuj 5cee930 1/2: [sdf] Added the subdivision and
From: |
Anuj Verma |
Subject: |
[freetype2] GSoC-2020-anuj 5cee930 1/2: [sdf] Added the subdivision and bounding box optimization. |
Date: |
Wed, 19 Aug 2020 07:07:27 -0400 (EDT) |
branch: GSoC-2020-anuj
commit 5cee930937fada9236cb19c45e67b89b992091e8
Author: Anuj Verma <anujv@iitbhilai.ac.in>
Commit: Anuj Verma <anujv@iitbhilai.ac.in>
[sdf] Added the subdivision and bounding box optimization.
* src/sdf/ftsdf.c (sdf_generate_bounding_box): Added function to generate
SDF by
only checking grid point around the bounding box of any edge.
* src/sdf/ftsdf.c (sdf_generate_subdivision): Added function to generate
SDF by
splitting the shape into a number of line segments and then only checking
grid
points around the neighborhood of the lines.
---
src/sdf/ftsdf.c | 292 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 292 insertions(+)
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 6d2552d..b442cf9 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -2801,4 +2801,296 @@
#endif
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate_bounding_box
+ *
+ * @Description:
+ * This function does basically the same thing as the above
+ * `sdf_generate' but more efficiently.
+ * Instead of checking all the pixels against all the edges, we loop
+ * through all the edges and only check the pixels around the control
+ * box of the edge, the control box is increased by the spread in all
+ * all the directions. Anything outside the control box will naturally
+ * be more than the `spread' and shouldn't be computed.
+ * Lastly to determine the sign of unchecked pixels we do a single pass
+ * of all the rows starting with a '+' sign and flipping when we come
+ * across a '-' sign and continue.
+ * This also eliminate the chance 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 the actual parameters.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed inthe output bitmap.
+ *
+ * @Return
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * FT_Error ::
+ * 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_UInt width, rows, i, j;
+ FT_UInt sp_sq; /* max value to check */
+
+ SDF_Contour* contours; /* list of all contours */
+ FT_Short* buffer; /* the bitmap buffer */
+
+ /* This buffer has the same size in indices as the */
+ /* bitmap buffer. When we check a pixel position for */
+ /* shortest distance we keep it in this buffer. */
+ /* This way we check find out which pixel is set, */
+ /* and also determine the signs properly. */
+ SDF_Signed_Distance* dists = NULL;
+
+ 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;
+ }
+
+ contours = shape->contours;
+ width = bitmap->width;
+ rows = bitmap->rows;
+ buffer = (FT_Short*)bitmap->buffer;
+
+ if ( SDF_ALLOC( dists, width * rows * sizeof( *dists ) ) )
+ goto Exit;
+
+ FT_MEM_ZERO( dists, width * rows * sizeof(*dists) );
+
+ 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] sdf_generate:\n"
+ " Cannot render glyph with width/height == 0\n"
+ " (width, height provided [%d, %d])", width, rows ));
+ error = FT_THROW( Cannot_Render_Glyph );
+ goto Exit;
+ }
+
+ /* loop through all the contours */
+ while ( contours ) {
+ SDF_Edge* edges = contours->edges;
+
+
+ /* loop through all the edges */
+ while ( edges )
+ {
+ FT_CBox cbox;
+ FT_Int x, y;
+
+ /* get the control box and increase 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 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 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 = y * width + x;
+ else
+ index = ( rows - y - 1 ) * width + x;
+
+ /* check weather 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 */
+ /* will be 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 = j * width + i;
+
+ /* if the pixel is not set that means it's */
+ /* shortest distance is more than spread */
+ if ( dists[index].sign == 0 )
+ dists[index].distance = FT_INT_16D16( spread );
+ else
+ current_sign = dists[index].sign;
+
+ /* clamp the values */
+ if ( dists[index].distance > FT_INT_16D16( spread ) )
+ dists[index].distance = FT_INT_16D16( spread );
+
+ /* convert from 16.16 to 6.10 */
+ dists[index].distance /= 64;
+
+ if ( internal_params.flip_sign )
+ buffer[index] = (FT_Short)dists[index].distance * -current_sign;
+ else
+ buffer[index] = (FT_Short)dists[index].distance * current_sign;
+ }
+ }
+
+ Exit:
+ SDF_FREE( dists );
+ return error;
+ }
+
+ /**************************************************************************
+ *
+ * @Function:
+ * sdf_generate_subdivision
+ *
+ * @Description:
+ * This function subdivide the shape into a number of straight lines
+ * and then simply use the above `sdf_generate_bounding_box' to generate
+ * the SDF.
+ * Note: After calling this function the `shape' will no longer have the
+ * original edges, it will only contain lines.
+ *
+ * @Input:
+ * internal_params ::
+ * Internal parameters and properties required by the rasterizer.
+ * See `SDF_Params' for the actual parameters.
+ *
+ * shape ::
+ * A complete shape which is used to generate SDF.
+ *
+ * spread ::
+ * Maximum distances to be allowed inthe output bitmap.
+ *
+ * @Return
+ * bitmap ::
+ * The output bitmap which will contain the SDF information.
+ *
+ * FT_Error ::
+ * 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. */
+ /* */
+ /* This optimiztion mode take advantage of two facts: */
+ /* */
+ /* - Computing shortest distance froma point to a line segment */
+ /* is super fast. */
+ /* - We don't have to compute shortest distance for the entire */
+ /* 2D grid. */
+ /* */
+ /* This is how it works: */
+ /* */
+ /* - We split the outlines into a number of line segments. */
+ /* */
+ /* - For each line segment we only process the neighborhood of */
+ /* the line segment. */
+ /* */
+ /* - Now, only for the neighborhood grid points we compute the */
+ /* closest distance to the line. */
+ /* */
+ /* - This way we do not have to check all grid points against */
+ /* all the edges. Instead for each line's neighborhood we */
+ /* only compute shortest distance for that one line only. */
+ /* */
+ /* All in all, it reduces the number of grid point to edge 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;
+ }
+
/* END */
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [freetype2] GSoC-2020-anuj 5cee930 1/2: [sdf] Added the subdivision and bounding box optimization.,
Anuj Verma <=