ref: e2ae96b9783e326e44772643559044a8cc19972a
parent: 6b9a8044be0da700970e1cf5c0a7d6f3e92345f3
author: Anuj Verma <anujv@iitbhilai.ac.in>
date: Thu Aug 20 17:19:32 EDT 2020
[sdf] Add '8-point sequential Euclidean distance mapping' algorithm. * src/sdf/ftbsdf.c (compare_neighbor, first_pass, second_pass, edt8): New functions.
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2020-08-20 Anuj Verma <anujv@iitbhilai.ac.in>
+ [sdf] Add '8-point sequential Euclidean distance mapping' algorithm.
+
+ * src/sdf/ftbsdf.c (compare_neighbor, first_pass, second_pass,
+ edt8): New functions.
+
+2020-08-20 Anuj Verma <anujv@iitbhilai.ac.in>
+
[sdf] Add function to copy source bitmap to distance map.
* src/sdf/ftbsdf.c (bsdf_init_distance_map): New function.
--- a/src/sdf/ftbsdf.c
+++ b/src/sdf/ftbsdf.c
@@ -303,7 +303,7 @@
* 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.
+ * 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
@@ -694,5 +694,254 @@
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;
+ }
/* END */