[freetype2] anuj-distance-field ce146c4 17/95: [sdf] The module can now generate SDF for outline with only lines.

[Anuj Verma]

branch: anuj-distance-field
commit ce146c4e6fcfe73304dabab5b8b879b66c71a3c9
Author: Anuj Verma <anujv@iitbhilai.ac.in>
Commit: Anuj Verma <anujv@iitbhilai.ac.in>

    [sdf] The module can now generate  SDF for outline with only lines.
---
 [GSoC]ChangeLog     | 18 +++++++++++
 src/sdf/ftsdf.c     | 86 +++++++++++++++++++++++++++++++++++++++++++----------
 src/sdf/ftsdfrend.c | 10 +++----
 3 files changed, 93 insertions(+), 21 deletions(-)

diff --git a/[GSoC]ChangeLog b/[GSoC]ChangeLog
index 64c5493..e094cec 100644
--- a/[GSoC]ChangeLog
+++ b/[GSoC]ChangeLog
@@ -1,5 +1,23 @@
 2020-06-27  Anuj Verma  <anujv@iitbhilai.ac.in>
 
+       [sdf] The module can now generate signed distance
+       fields for outline with only lines.
+
+       * src/sdf/ftsdf.c (get_min_distance_line): Calculation
+         mistake.
+
+       * src/sdf/ftsdf.c (square_root): Added function to calculate
+         square root of a 16.16 fixed point integer.
+
+       * src/sdf/ftsdf.c (sdf_generate): Assign values to the output
+         bitmap, currently the output is 6.10 fixed point which can
+         contain values from [-32, 32]. Also fixed a bug which was
+         causing upside down images.
+
+       * src/sdf/ftsdfrend.c (ft_sdf_render): Fixed alignment issues.
+
+2020-06-27  Anuj Verma  <anujv@iitbhilai.ac.in>
+
        [sdf] Added function to find shortest distance from
        a point to a line.
 
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 6a25775..912b543 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -599,6 +599,38 @@
 
 #endif
 
+  /**************************************************************************
+   *
+   * math functions
+   *
+   */
+
+  /* Original Algorithm: https://github.com/chmike/fpsqrt */
+  static FT_Fixed
+  square_root( FT_Fixed  val )
+  {
+    FT_ULong t, q, b, r;
+
+
+    r = val;
+    b = 0x40000000;
+    q = 0;
+    while( b > 0x40 )
+    {
+      t = q + b;
+      if( r >= t )
+      {
+        r -= t;
+        q = t + b;
+      }
+      r <<= 1;
+      b >>= 1;
+    }
+    q >>= 8;
+
+    return q;
+  }
+
   /*************************************************************************/
   /*************************************************************************/
   /**                                                                     **/
@@ -721,10 +753,8 @@
     nearest_point.y = FT_MulFix( FT_26D6_16D16(line_segment.y),
                                  factor );
 
-    nearest_point.x = FT_26D6_16D16( a.x ) + nearest_point.x -
-                      FT_26D6_16D16( p.x );
-    nearest_point.y = FT_26D6_16D16( a.y ) + nearest_point.y -
-                      FT_26D6_16D16( p.y );
+    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 );
@@ -831,14 +861,16 @@
       FT_CALL( sdf_edge_get_min_distance( 
                (SDF_Edge*)edge_list.head->data,
                point, &current_dist ) );
-    
+
       /* [TODO]: *IMPORTANT* Add corner checking function. */
-      if ( current_dist.squared_distance < min_dist.squared_distance )
+      if ( current_dist.squared_distance >= 0 && 
+           current_dist.squared_distance < min_dist.squared_distance )
         min_dist = current_dist;
     
       edge_list.head = edge_list.head->next;
     }
 
+    *out = min_dist;
   Exit:
     return error;
   }
@@ -868,11 +900,14 @@
                 FT_UInt           spread,
                 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_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' int 16.16 fixed    */
+
+    FT_Short*  buffer;
 
     if ( !shape || !bitmap )
     {
@@ -888,6 +923,9 @@
 
     width = bitmap->width;
     rows = bitmap->rows;
+    buffer = (FT_Short*)bitmap->buffer;
+
+    sp_sq = FT_INT_16D16( spread * spread );
 
     if ( width == 0 || rows == 0 )
     {
@@ -911,7 +949,8 @@
                                     FT_INT_26D6( y ) };
         SDF_Signed_Distance  min_dist = max_sdf;
         FT_ListRec           contour_list;
-
+        FT_UInt              index;
+        FT_Short             value;
 
         /* This `grid_point' is at the corner, but we */
         /* use the center of the pixel.               */
@@ -920,6 +959,8 @@
 
         contour_list = shape->contours;
 
+        index = ( rows - y - 1 ) * width + x;
+
         /* iterate through all the contours manually */
         while ( contour_list.head ) {
           SDF_Signed_Distance  current_dist = max_sdf;
@@ -929,12 +970,27 @@
                    (SDF_Contour*)contour_list.head->data,
                    grid_point, &current_dist ) );
 
-          if ( current_dist.squared_distance <
-               min_dist.squared_distance )
+          if ( current_dist.squared_distance < min_dist.squared_distance )
             min_dist = current_dist;
 
           contour_list.head = contour_list.head->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.squared_distance > sp_sq )
+          min_dist.squared_distance = sp_sq;
+
+        /* square_root the values and fit in a 6.10 fixed point */
+        min_dist.squared_distance = square_root( min_dist.squared_distance );
+
+        min_dist.squared_distance /= 64; /* convert from 16.16 to 22.10 */
+        value = min_dist.squared_distance & 0x0000FFFF; /* truncate to 6.10 */
+        value *= min_dist.sign;
+
+        buffer[index] = value;
       }
     }
 
@@ -1063,8 +1119,6 @@
     FT_CALL( sdf_generate( shape, sdf_params->spread, 
                            sdf_params->root.target ) );
 
-    sdf_shape_dump( shape );
-
   Exit:
     if ( shape )
       sdf_shape_done( memory, &shape );
diff --git a/src/sdf/ftsdfrend.c b/src/sdf/ftsdfrend.c
index 148efeb..5df5d22 100644
--- a/src/sdf/ftsdfrend.c
+++ b/src/sdf/ftsdfrend.c
@@ -112,8 +112,8 @@
     FT_SERVICE_ID_PROPERTIES, &sdf_service_properties )
 
   static FT_Module_Interface
-  ft_sdf_requester ( FT_Renderer  render,
-                     const char*  module_interface )
+  ft_sdf_requester( FT_Renderer  render,
+                    const char*  module_interface )
   {
     FT_UNUSED( render );
 
@@ -127,7 +127,7 @@
    */
 
   static FT_Error
-  ft_sdf_init ( FT_Renderer  render )
+  ft_sdf_init( FT_Renderer  render )
   {
     SDF_Renderer  sdf_render = SDF_RENDERER( render );
 
@@ -138,7 +138,7 @@
   }
 
   static FT_Error
-  ft_sdf_done ( FT_Renderer  render )
+  ft_sdf_done( FT_Renderer  render )
   {
     FT_UNUSED( render );
 
@@ -225,7 +225,7 @@
 
     slot->internal->flags |= FT_GLYPH_OWN_BITMAP;
 
-    x_shift  = 64 * -( slot->bitmap_left + x_pad );
+    x_shift  = 64 * -( slot->bitmap_left - x_pad );
     y_shift  = 64 * -( slot->bitmap_top + y_pad );
     y_shift += 64 * (FT_Int)bitmap->rows;