[freetype2] anuj-distance-field 13fc345 53/95: [sdf] Optimize the coarse grid optimization.

[Anuj Verma]

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

    [sdf] Optimize the coarse grid optimization.
    
    * src/sdf/ftsdf.c (sdf_generate_coarse_grid): Merge
      the relevant edge finding loop and shortest dist-
      ance search loop. We can find the relevant edges
      of a coarse grid and immediately use them to find
      the shortest distance of the points in the coarse
      grid. This drastically reduce memory usage and
      performance.
      Also, do the sign assignment of the edges which was
      missing.
---
 [GSoC]ChangeLog | 14 ++++++++++
 src/sdf/ftsdf.c | 87 ++++++++++++++++++++++++++++-----------------------------
 2 files changed, 56 insertions(+), 45 deletions(-)

diff --git a/[GSoC]ChangeLog b/[GSoC]ChangeLog
index ae1fee1..cc9de59 100644
--- a/[GSoC]ChangeLog
+++ b/[GSoC]ChangeLog
@@ -1,3 +1,17 @@
+2020-07-12  Anuj Verma  <anujv@iitbhilai.ac.in>
+
+       [sdf] Optimize the coarse grid optimization.
+
+       * src/sdf/ftsdf.c (sdf_generate_coarse_grid): Merge
+         the relevant edge finding loop and shortest dist-
+         ance search loop. We can find the relevant edges
+         of a coarse grid and immediately use them to find
+         the shortest distance of the points in the coarse
+         grid. This drastically reduce memory usage and 
+         performance.
+         Also, do the sign assignment of the edges which was
+         missing.
+
 2020-07-11  Anuj Verma  <anujv@iitbhilai.ac.in>
 
        * src/sdf/ftsdf.c (*): Fixed warnings.
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index ab3aa08..458e745 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -2754,14 +2754,11 @@
     FT_UInt       c_width, c_rows; /* coarse grid dimensions              */
     FT_16D16      sp_sq;           /* max value to check                  */
     FT_16D16      cg_sq;           /* max value to check for coarse grid  */
-    FT_16D16      cg_max;
+    FT_16D16      cg_diagon;
 
     SDF_Contour*  contours;        /* list of all contours */
     FT_Short*     buffer;          /* the bitmap buffer    */
 
-    /* coarse grid to hold the list of edges */
-    SDF_Edge*     coarse_grid[ CG_DIMEN * CG_DIMEN ];
-
     if ( !shape || !bitmap )
     {
       error = FT_THROW( Invalid_Argument );
@@ -2794,19 +2791,20 @@
     c_width = width / CG_DIMEN + ( width % CG_DIMEN == 0 ? 0 : 1 );
     c_rows = rows / CG_DIMEN + ( rows % CG_DIMEN == 0 ? 0 : 1 );
 
-    cg_max = c_width > c_rows ? c_width : c_rows;
+    cg_diagon = FT_INT_16D16( c_width * c_width ) +
+                FT_INT_16D16( c_rows * c_rows );
 
     /* `cg_sq' is the max value for which we add an edge */
     /* to the coarse grid list.                          */
     if ( USE_SQUARED_DISTANCES )
     {
       sp_sq = FT_INT_16D16( spread * spread );
-      cg_sq = sp_sq + FT_INT_16D16( cg_max * cg_max ) / 4;
+      cg_sq = sp_sq + cg_diagon;
     }
     else
     {
       sp_sq = FT_INT_16D16( spread );
-      cg_sq = sp_sq + FT_INT_16D16( cg_max / 2 );
+      cg_sq = sp_sq + square_root( cg_diagon );
     }
 
     /* if the coarse grid is too small then simply */
@@ -2826,10 +2824,15 @@
         FT_Int        cindex  = j * CG_DIMEN + i;
         SDF_Contour*  cont    = contours;
         SDF_Edge*     edge;
+        SDF_Edge*     relevant_list;
         FT_26D6_Vec   cpoint;
+        FT_BBox       sample_region;
+        FT_Int        x, y;
+
+        SDF_Signed_Distance  min_cg_dist = max_sdf;
 
 
-        coarse_grid[cindex] = NULL;
+        relevant_list = NULL;
 
         /* we check from the center of the coarse grid */
         cpoint.x = FT_INT_26D6( i * c_width ) + FT_INT_26D6( c_width / 2 );
@@ -2855,32 +2858,25 @@
               FT_CALL( sdf_edge_new( memory, &temp ) );
               ft_memcpy( temp, edge, sizeof( *edge ) );
               
-              temp->next = coarse_grid[cindex];
-              coarse_grid[cindex] = temp;
+              temp->next = relevant_list;
+              relevant_list = temp;
             }
 
+            if ( dist.distance < min_cg_dist.distance )
+              min_cg_dist = dist;
+            else if ( FT_ABS( dist.distance - min_cg_dist.distance ) <
+                      CORNER_CHECK_EPSILON )
+              min_cg_dist = resolve_corner( min_cg_dist, dist );
+
             edge = edge->next;
           }
 
           cont = cont->next;
         }
-      }
-    }
-
-    /* Now that we have the list of edges relevant for the pixels */
-    /* inside a coarse grid, we only need to check those pixels   */
-    /* against the list of edges.                                 */
-
-    /* again loop through the coarse grid */
-    for ( j = 0; j < CG_DIMEN; j++ )
-    {
-      for ( i = 0; i < CG_DIMEN; i++ )
-      {
-        FT_BBox    sample_region;
-        FT_Int     x, y;
 
-
-        if ( !coarse_grid[j * CG_DIMEN + i] ) continue;
+        /* Now that we have the list of edges relevant for the pixels */
+        /* inside a coarse grid, we only need to check those pixels   */
+        /* against the list of edges.                                 */
 
         /* this gives the pixels inside the coarse grid */
         sample_region.xMin = i * c_width;
@@ -2888,7 +2884,6 @@
         sample_region.yMin = j * c_rows;
         sample_region.yMax = sample_region.yMin + c_rows;
 
-
         /* for all the pixes inside the coarse grid */
         for ( y = sample_region.yMin; y < sample_region.yMax; y++ )
         {
@@ -2896,12 +2891,20 @@
           {
             FT_26D6_Vec          current_pos;
             SDF_Signed_Distance  min_dist = max_sdf;
-            SDF_Edge*            edges = coarse_grid[j * CG_DIMEN + i];
+            SDF_Edge*            edges = relevant_list;
+            FT_Int               index = ( rows - y - 1 ) * width + x;
 
 
             if ( x < 0 || x >= width ) continue;
             if ( y < 0 || y >= rows )  continue;
 
+            /* If there is no relevant edge for the */
+            /* coarse grid then it's fare than the  */
+            /* `spread'. In that case simply assign */
+            /* `min_dist' = `min_cg_dist'.          */
+            if ( !relevant_list )
+              min_dist = min_cg_dist;
+
             /* we check from the center of a pixel */
             current_pos.x = FT_INT_26D6( x ) + FT_INT_26D6( 1 ) / 2;
             current_pos.y = FT_INT_26D6( y ) + FT_INT_26D6( 1 ) / 2;
@@ -2917,6 +2920,9 @@
 
               if ( dist.distance < min_dist.distance )
                 min_dist = dist;
+              else if ( FT_ABS( dist.distance - min_dist.distance ) <
+                        CORNER_CHECK_EPSILON )
+                min_dist = resolve_corner( min_dist, dist );
 
               edges = edges->next;
             }
@@ -2930,29 +2936,20 @@
 
             min_dist.distance /= 64;
 
-            buffer[( rows - y - 1 ) * width + x] = (FT_Short)min_dist.distance;
+            buffer[index] = (FT_Short)min_dist.distance * min_dist.sign;
 
           }
         }
-      }
-    }
-
-    /* release the allocated lists */
-    for ( i = 0; i < CG_DIMEN * CG_DIMEN; i++ )
-    {
-      SDF_Edge*  edge = coarse_grid[i];
-      SDF_Edge*  temp;
-
 
-      while ( edge )
-      {
-        temp = edge;
-        edge = edge->next;
+        /* release the allocated lists */
+        while ( relevant_list )
+        {
+          edge = relevant_list;
+          relevant_list = relevant_list->next;
 
-        sdf_edge_done( memory, &temp );
+          sdf_edge_done( memory, &edge );
+        }
       }
-
-      coarse_grid[i] = NULL;
     }
 
   Exit: