[freetype2] 1100-sdf-improvements b3d917d2f 2/3: [sdf] Impliment deviation based splitting for bezier curves.

[Werner Lemberg]

branch: 1100-sdf-improvements
commit b3d917d2f8b1c2daefae0644fcc6320fac5220a3
Author: Anuj Verma <anuj@womp.xyz>
Commit: Anuj Verma <anuj@womp.xyz>

    [sdf] Impliment deviation based splitting for bezier curves.
    
    * src/sdf/ftsdf.c (split_sdf_cubic, split_sdf_shape): Added checks
      to figure out the deviation of bezier curves and stop splitting
      if the curve is flat enough.
    
    * src/sdf/ftsdfcommon.h (ONE_PIXEL): Added macro for unit pixel size
      in 26.6 fixed point representation.
---
 src/sdf/ftsdf.c       | 42 +++++++++++++++++++++++++++++++++++++-----
 src/sdf/ftsdfcommon.h |  2 ++
 2 files changed, 39 insertions(+), 5 deletions(-)

diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index f5e5551e6..e6ab61fe6 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -1137,9 +1137,10 @@
                    FT_Int        max_splits,
                    SDF_Edge**    out )
   {
-    FT_Error     error = FT_Err_Ok;
-    FT_26D6_Vec  cpos[7];
-    SDF_Edge*    left,*  right;
+    FT_Error       error = FT_Err_Ok;
+    FT_26D6_Vec    cpos[7];
+    SDF_Edge*      left,*  right;
+    const FT_26D6  threshold = ONE_PIXEL / 4;
 
 
     if ( !memory || !out  )
@@ -1148,11 +1149,24 @@
       goto Exit;
     }
 
-    /* split the conic */
+    /* split the cubic */
     cpos[0] = control_points[0];
     cpos[1] = control_points[1];
     cpos[2] = control_points[2];
     cpos[3] = control_points[3];
+    
+    /* If the segment is flat enough, we won't get any benifit by */
+    /* splitting it further, so we can just stop splitting. Here, */
+    /* we check the deviation of the bezier and stop if it is     */
+    /* lower than a pre-defined `threhold` value.                 */
+    if ( FT_ABS( 2 * cpos[0].x - 3 * cpos[1].x + cpos[3].x ) < threshold &&
+              FT_ABS( 2 * cpos[0].y - 3 * cpos[1].y + cpos[3].y ) < threshold 
&&
+         FT_ABS( cpos[0].x - 3 * cpos[2].x + 2 * cpos[3].x ) < threshold &&
+              FT_ABS( cpos[0].y - 3 * cpos[2].y + 2 * cpos[3].y ) < threshold )
+    {
+      split_cubic( cpos );
+      goto Append;
+    }
 
     split_cubic( cpos );
 
@@ -1250,13 +1264,31 @@
           /* Subdivide the curve and add it to the list. */
           {
             FT_26D6_Vec  ctrls[3];
+            FT_26D6      dx, dy;
+            FT_UInt      num_splits;
 
 
             ctrls[0] = edge->start_pos;
             ctrls[1] = edge->control_a;
             ctrls[2] = edge->end_pos;
 
-            error = split_sdf_conic( memory, ctrls, 32, &new_edges );
+                   dx = FT_ABS( ctrls[2].x + ctrls[0].x - 2 * ctrls[1].x );
+                   dy = FT_ABS( ctrls[2].y + ctrls[0].y - 2 * ctrls[1].y );
+            if ( dx < dy )
+                     dx = dy;
+
+                   /* Here we calculate the number of necessary bisections. 
Each */
+                   /* bisection reduces the deviation by exactly 4-fold, hence 
  */
+                   /* we bisect the bezier until the deviation becomes less 
than */
+                   /* 1/8th of a pixel. For more details check `ftgrays.c`.    
  */
+                   num_splits = 1;
+                   while ( dx > ONE_PIXEL / 8 )
+                   {
+                     dx >>= 2;
+                     num_splits <<= 1;
+                   }
+       
+            error = split_sdf_conic( memory, ctrls, num_splits, &new_edges );
           }
           break;
 
diff --git a/src/sdf/ftsdfcommon.h b/src/sdf/ftsdfcommon.h
index c8ea38034..af4490bbc 100644
--- a/src/sdf/ftsdfcommon.h
+++ b/src/sdf/ftsdfcommon.h
@@ -48,6 +48,8 @@ FT_BEGIN_HEADER
 #define MIN_SPREAD      2
   /* maximum spread supported by the renderer */
 #define MAX_SPREAD      32
+  /* pixel size in 26.6 */
+#define ONE_PIXEL       ( 1 << 6 )
 
 
   /**************************************************************************