[sdf] Implement deviation-based splitting for Bezier curves.

* src/sdf/ftsdf.c (split_sdf_cubic, split_sdf_shape): Add checks to figure
out the deviation of Bezier curves and stop splitting if the curve is flat
enough.

* src/sdf/ftsdfcommon.h (ONE_PIXEL): New macro.

2 files changed, 45 insertions, 9 deletions

diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index f5e5551e6..fa551ea6e 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -764,9 +764,9 @@
                 const FT_26D6_Vec*  to,
                 void*               user )
   {
-    SDF_Shape*    shape    = ( SDF_Shape* )user;
-    SDF_Edge*     edge     = NULL;
-    SDF_Contour*  contour  = NULL;
+    SDF_Shape*    shape   = ( SDF_Shape* )user;
+    SDF_Edge*     edge    = NULL;
+    SDF_Contour*  contour = NULL;
 
     FT_Error   error  = FT_Err_Ok;
     FT_Memory  memory = shape->memory;
@@ -1137,23 +1137,38 @@
                    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  )
+    if ( !memory || !out )
     {
       error = FT_THROW( Invalid_Argument );
       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 benefit by */
+    /* splitting it further, so we can just stop splitting.      */
+    /*                                                           */
+    /* Check the deviation of the Bezier curve and stop if it is */
+    /* smaller than the pre-defined `threshold` 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 );
 
     /* If max number of splits is done */
@@ -1250,13 +1265,32 @@
           /* 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;
+
+            /* Calculate the number of necessary bisections.  Each      */
+            /* bisection causes a four-fold reduction of the deviation, */
+            /* hence we bisect the Bezier curve until the deviation     */
+            /* becomes less than 1/8th of a pixel.  For more details    */
+            /* check file `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 )
 
 
   /**************************************************************************