[sdf] Add '8-point sequential Euclidean distance mapping' algorithm.

* src/sdf/ftbsdf.c (compare_neighbor, first_pass, second_pass,
edt8): New functions.

2 files changed, 257 insertions, 1 deletions

diff --git a/ChangeLog b/ChangeLog
index 48b028395..1503842bb 100644
--- 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.
diff --git a/src/sdf/ftbsdf.c b/src/sdf/ftbsdf.c
index da4d9f91e..aee998790 100644
--- 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
@@ -695,4 +695,253 @@
   }
 
 
+  /**************************************************************************
+   *
+   * @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 */