[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.

2 files changed, 39 insertions, 6 deletions

diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 784e24705..0f9dffecf 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,12 +1149,25 @@
       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 );
 
     /* If max number of splits is done */
@@ -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 44f6bba53..a64774507 100644
--- a/src/sdf/ftsdfcommon.h
+++ b/src/sdf/ftsdfcommon.h
@@ -48,7 +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 )
 
   /**************************************************************************
    *