[ft-devel] latest patch file for spline flattening

[Graham Asher]

Here's a new version of my spline flattening patch. (I would like to be 
able to push this to the git repository but am having authentication 
problems; Werner has been helping me, but no success so far, probably 
because of my ineptitude in these matters.).

The nub of the latest change is that I found that predicting the number 
of recursion levels is not reliable when splitting a cubic spline for 
flattening. A better way is to check the flatness inside the loop - 
using the fast heuristic of taking the maximum coordinate difference of 
a control point from the chord midpoint. This also makes the code 
simpler - and, surprisingly, faster, according to my benchmark; however, 
my benchmark is based on cartographic, not typographic, use, so will 
need confirmation.

The patch obviously still solves the bug involving s-shaped curves 
(control points on both sides of the chord).

Graham

diff --git "a/C:\\DOCUME~1\\Graham\\LOCALS~1\\Temp\\ftgrays_c8f5b9.c" 
"b/C:\\FreeType\\freetype2\\src\\smooth\\ftgrays.c"
index 0b94143..3a5e3cf 100644
--- "a/C:\\DOCUME~1\\Graham\\LOCALS~1\\Temp\\ftgrays_c8f5b9.c"
+++ "b/C:\\FreeType\\freetype2\\src\\smooth\\ftgrays.c"
@@ -90,6 +90,9 @@
 #undef  FT_COMPONENT
 #define FT_COMPONENT  trace_smooth
 
+/* The maximum distance of a curve from the chord, in 64ths of a pixel; */
+/* used when flattening curves. */
+#define FT_MAX_CURVE_DEVIATION 16
 
 #ifdef _STANDALONE_
 
@@ -354,8 +357,6 @@ typedef ptrdiff_t  FT_PtrDist;
 
     int  band_size;
     int  band_shoot;
-    int  conic_level;
-    int  cubic_level;
 
     ft_jmp_buf  jump_buffer;
 
@@ -888,31 +889,18 @@ typedef ptrdiff_t  FT_PtrDist;
     if ( dx < dy )
       dx = dy;
 
-    level = 1;
-    dx = dx / ras.conic_level;
-    while ( dx > 0 )
+    if ( dx <= FT_MAX_CURVE_DEVIATION )
     {
-      dx >>= 2;
-      level++;
+      gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) );
+      return;
     }
 
-    /* a shortcut to speed things up */
-    if ( level <= 1 )
+    level = 1;
+    dx /= FT_MAX_CURVE_DEVIATION;
+    while ( dx > 1 )
     {
-      /* we compute the mid-point directly in order to avoid */
-      /* calling gray_split_conic()                          */
-      TPos  to_x, to_y, mid_x, mid_y;
-
-
-      to_x  = UPSCALE( to->x );
-      to_y  = UPSCALE( to->y );
-      mid_x = ( ras.x + to_x + 2 * UPSCALE( control->x ) ) / 4;
-      mid_y = ( ras.y + to_y + 2 * UPSCALE( control->y ) ) / 4;
-
-      gray_render_line( RAS_VAR_ mid_x, mid_y );
-      gray_render_line( RAS_VAR_ to_x, to_y );
-
-      return;
+      dx >>= 2;
+      level++;
     }
 
     arc       = ras.bez_stack;
@@ -957,21 +945,9 @@ typedef ptrdiff_t  FT_PtrDist;
       }
 
     Draw:
-      {
-        TPos  to_x, to_y, mid_x, mid_y;
-
-
-        to_x  = arc[0].x;
-        to_y  = arc[0].y;
-        mid_x = ( ras.x + to_x + 2 * arc[1].x ) / 4;
-        mid_y = ( ras.y + to_y + 2 * arc[1].y ) / 4;
-
-        gray_render_line( RAS_VAR_ mid_x, mid_y );
-        gray_render_line( RAS_VAR_ to_x, to_y );
-
-        top--;
-        arc -= 2;
-      }
+      gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
+      top--;
+      arc -= 2;
     }
 
     return;
@@ -1011,56 +987,9 @@ typedef ptrdiff_t  FT_PtrDist;
                               const FT_Vector*  control2,
                               const FT_Vector*  to )
   {
-    int         top, level;
-    int*        levels;
     FT_Vector*  arc;
-    int         mid_x = ( DOWNSCALE( ras.x ) + to->x +
-                          3 * (control1->x + control2->x ) ) / 8;
-    int         mid_y = ( DOWNSCALE( ras.y ) + to->y +
-                          3 * (control1->y + control2->y ) ) / 8;
-    TPos        dx = DOWNSCALE( ras.x ) + to->x - ( mid_x << 1 );
-    TPos        dy = DOWNSCALE( ras.y ) + to->y - ( mid_y << 1 );
 
 
-    if ( dx < 0 )
-      dx = -dx;
-    if ( dy < 0 )
-      dy = -dy;
-    if ( dx < dy )
-      dx = dy;
-
-    level = 1;
-    dx /= ras.cubic_level;
-    while ( dx > 0 )
-    {
-      dx >>= 2;
-      level++;
-    }
-
-    if ( level <= 1 )
-    {
-      TPos  to_x, to_y;
-
-
-      to_x  = UPSCALE( to->x );
-      to_y  = UPSCALE( to->y );
-
-      /* Recalculation of midpoint is needed only if */
-      /* UPSCALE and DOWNSCALE have any effect.      */
-
-#if ( PIXEL_BITS != 6 )
-      mid_x = ( ras.x + to_x +
-                3 * UPSCALE( control1->x + control2->x ) ) / 8;
-      mid_y = ( ras.y + to_y +
-                3 * UPSCALE( control1->y + control2->y ) ) / 8;
-#endif
-
-      gray_render_line( RAS_VAR_ mid_x, mid_y );
-      gray_render_line( RAS_VAR_ to_x, to_y );
-
-      return;
-    }
-
     arc      = ras.bez_stack;
     arc[0].x = UPSCALE( to->x );
     arc[0].y = UPSCALE( to->y );
@@ -1071,56 +1000,66 @@ typedef ptrdiff_t  FT_PtrDist;
     arc[3].x = ras.x;
     arc[3].y = ras.y;
 
-    levels    = ras.lev_stack;
-    top       = 0;
-    levels[0] = level;
-
-    while ( top >= 0 )
+    for (;;)
     {
-      level = levels[top];
-      if ( level > 1 )
-      {
-        /* check that the arc crosses the current band */
-        TPos  min, max, y;
-
-
-        min = max = arc[0].y;
-        y = arc[1].y;
-        if ( y < min ) min = y;
-        if ( y > max ) max = y;
-        y = arc[2].y;
-        if ( y < min ) min = y;
-        if ( y > max ) max = y;
-        y = arc[3].y;
-        if ( y < min ) min = y;
-        if ( y > max ) max = y;
-        if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
-          goto Draw;
-        gray_split_cubic( arc );
-        arc += 3;
-        top ++;
-        levels[top] = levels[top - 1] = level - 1;
-        continue;
-      }
+    /* Check that the arc crosses the current band. */
+    TPos  min, max, y;
+
+
+    min = max = arc[0].y;
+    y = arc[1].y;
+    if ( y < min ) min = y;
+    if ( y > max ) max = y;
+    y = arc[2].y;
+    if ( y < min ) min = y;
+    if ( y > max ) max = y;
+    y = arc[3].y;
+    if ( y < min ) min = y;
+    if ( y > max ) max = y;
+    if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < 0 )
+      goto Draw;
+
+    /* Check flatness: find the furthest distance of a coordinate of a  */
+    /* control point from the midpoint of the line.                     */
+    {
+    int dx1, dy1, dx2, dy2, midx, midy;
+
+
+       midx = (arc[0].x + arc[3].x) / 2;
+       midy = (arc[0].y + arc[3].y) / 2;
+    dx1 = arc[1].x - midx;
+    if ( dx1 < 0 )
+      dx1 = -dx1;
+    dy1 = arc[1].y - midy;
+    if ( dy1 < 0 )
+      dy1 = -dy1;
+    dx2 = arc[2].x - midx;
+    if ( dx2 < 0 )
+      dx2 = -dx2;
+    dy2 = arc[2].y - midy;
+    if ( dy2 < 0 )
+      dy2 = -dy2;
+    if ( dx1 < dy1 )
+      dx1 = dy1;
+    if ( dx1 < dx2 )
+      dx1 = dx2;
+    if ( dx1 < dy2 )
+      dx1 = dy2;
+    if ( dx1 <= FT_MAX_CURVE_DEVIATION )
+      goto Draw;
+    }
+    
+    gray_split_cubic( arc );
+    arc += 3;
+    continue;
 
     Draw:
-      {
-        TPos  to_x, to_y;
-
-
-        to_x  = arc[0].x;
-        to_y  = arc[0].y;
-        mid_x = ( ras.x + to_x + 3 * ( arc[1].x + arc[2].x ) ) / 8;
-        mid_y = ( ras.y + to_y + 3 * ( arc[1].y + arc[2].y ) ) / 8;
+    gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
+    if (arc == ras.bez_stack)
+        return;
 
-        gray_render_line( RAS_VAR_ mid_x, mid_y );
-        gray_render_line( RAS_VAR_ to_x, to_y );
-        top --;
-        arc -= 3;
-      }
+    arc -= 3;
     }
-
-    return;
   }
 
 
@@ -1760,25 +1699,6 @@ typedef ptrdiff_t  FT_PtrDist;
     ras.count_ex = ras.max_ex - ras.min_ex;
     ras.count_ey = ras.max_ey - ras.min_ey;
 
-    /* simple heuristic used to speed up the bezier decomposition -- see */
-    /* the code in gray_render_conic() and gray_render_cubic() for more  */
-    /* details                                                           */
-    ras.conic_level = 32;
-    ras.cubic_level = 16;
-
-    {
-      int  level = 0;
-
-
-      if ( ras.count_ex > 24 || ras.count_ey > 24 )
-        level++;
-      if ( ras.count_ex > 120 || ras.count_ey > 120 )
-        level++;
-
-      ras.conic_level <<= level;
-      ras.cubic_level <<= level;
-    }
-
     /* set up vertical bands */
     num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
     if ( num_bands == 0 )