Re: [ft-devel] more thoughts on cubic spline flattening

[Graham Asher]

Here's a patch for review. As you know I have also started the process 
of registering as a contributor, so I might be able to commit directly 
if you like.

Graham


Werner LEMBERG wrote:
> > Some brief comments inline.
> >
> > More feedback from my investigations later.  [...]
> >     
>
> BTW, thanks a lot to both of you for working on this!  Is there
> something which I shall already commit to the repository?
>
>
>     Werner
>
>   

281daa355bf9a3f335dc75773188d68075e4af98
 src/smooth/ftgrays.c |  164 ++++++++++++++++----------------------------------
 1 files changed, 51 insertions(+), 113 deletions(-)

diff --git a/src/smooth/ftgrays.c b/src/smooth/ftgrays.c
index 0b94143..7c6afb0 100644
--- a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ -90,6 +90,8 @@
 #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 +356,6 @@ typedef ptrdiff_t  FT_PtrDist;
 
     int  band_size;
     int  band_shoot;
-    int  conic_level;
-    int  cubic_level;
 
     ft_jmp_buf  jump_buffer;
 
@@ -878,7 +878,6 @@ typedef ptrdiff_t  FT_PtrDist;
     int*        levels;
     FT_Vector*  arc;
 
-
     dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
     if ( dx < 0 )
       dx = -dx;
@@ -888,31 +887,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 +943,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;
@@ -1014,51 +988,45 @@ typedef ptrdiff_t  FT_PtrDist;
     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 )
+       
+    /*
+       Estimate the furthest distance of a coordinate of a control point from 
the
+       midpoint of the chord.
+       */
+       TPos dx1, dy1, dx2, dy2;
+       int midx = ( DOWNSCALE( ras.x ) + to->x ) / 2;
+       int midy = ( DOWNSCALE( ras.y ) + to->y ) / 2;
+       dx1 = control1->x - midx;
+    if ( dx1 < 0 )
+      dx1 = -dx1;
+       dy1 = control1->y - midy;
+    if ( dy1 < 0 )
+      dy1 = -dy1;
+       dx2 = control2->x - midx;
+    if ( dx2 < 0 )
+      dx2 = -dx2;
+       dy2 = control2->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 )
     {
-      dx >>= 2;
-      level++;
+      gray_render_line( RAS_VAR_ to->x, to->y );
+      return;
     }
 
-    if ( level <= 1 )
+    level = 1;
+    dx1 /= FT_MAX_CURVE_DEVIATION;
+    while ( dx1 > 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;
+      dx1 >>= 2;
+      level++;
     }
 
     arc      = ras.bez_stack;
@@ -1104,20 +1072,9 @@ typedef ptrdiff_t  FT_PtrDist;
       }
 
     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_ mid_x, mid_y );
-        gray_render_line( RAS_VAR_ to_x, to_y );
-        top --;
-        arc -= 3;
-      }
+      gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );
+      top --;
+      arc -= 3;
     }
 
     return;
@@ -1760,25 +1717,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 )