Re: [ft-devel] Re: possible inefficiency in gray_render_cubic

[Graham Asher]

Werner,

here's what I think is a better version of the start of the function. 
I've combined a few declarations and initialisations; probably against 
your house style, so please adjust as appropriate if you don't like it.

Important changes: (i) dx is now divided by ras.cubic_level; (ii) mid_x 
and mid_y are recalculated only if necessary.

Graham


 static int
 gray_render_cubic( RAS_ARG_ FT_Vector*  control1,
                             FT_Vector*  control2,
                             FT_Vector*  to )
 {
   int         top, level;
   int*        levels;
   FT_Vector*  arc;
   int error = 0;
   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 >>= 3;
     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

     error = gray_render_line( RAS_VAR_ mid_x, mid_y );
     if (!error)
       error = gray_render_line( RAS_VAR_ to_x, to_y );
     return error;
   }




Werner LEMBERG wrote:
> > Calculate the midpoint and compare it with start and end: [...]
> >     
>
> For me, this looks good.  Thanks for working on this.
>
>   
> > I am sceptical about the need to calculate both da and db.  Perhaps
> > db only will suffice.  I hope that David or Werner can comment.
> >     
>
> This is something Ken can probably check: He has a large database for
> Ghostscript to compare rendering results, and artifacts introduced by
> the simplified shorthand calculation would easily show up, I think.
>
> Below is a patch according to your data (hopefully, I've understood
> you correctly).  Please check and test.
>
>
>     Werner
>
>
> ======================================================================
>
>
> --- ftgrays.c.orig      2009-07-31 18:45:19.000000000 +0200
> +++ ftgrays.c   2010-06-08 09:56:23.000000000 +0200
> @@ -1007,45 +1007,40 @@
>                                const FT_Vector*  control2,
>                                const FT_Vector*  to )
>    {
> -    TPos        dx, dy, da, db;
> +    TPos        dx, dy;
> +    TPos        mid_x, mid_y;
>      int         top, level;
>      int*        levels;
>      FT_Vector*  arc;
>  
>  
> -    dx = DOWNSCALE( ras.x ) + to->x - ( control1->x << 1 );
> -    if ( dx < 0 )
> -      dx = -dx;
> -    dy = DOWNSCALE( ras.y ) + to->y - ( control1->y << 1 );
> -    if ( dy < 0 )
> -      dy = -dy;
> -    if ( dx < dy )
> -      dx = dy;
> -    da = dx;
> +    /* Calculate midpoint and compare it with start and end. */
> +    mid_x = ( DOWNSCALE( ras.x ) + to->x +
> +              3 * ( control1->x + control2->x ) ) / 8;
> +    mid_y = ( DOWNSCALE( ras.y ) + to->y +
> +              3 * ( control1->y + control2->y ) ) / 8;
>  
> -    dx = DOWNSCALE( ras.x ) + to->x - 3 * ( control1->x + control2->x );
> +    dx = DOWNSCALE( ras.x ) + to->x - ( mid_x << 1 );
>      if ( dx < 0 )
>        dx = -dx;
> -    dy = DOWNSCALE( ras.y ) + to->y - 3 * ( control1->x + control2->y );
> +    dy = DOWNSCALE( ras.y ) + to->y - ( mid_y << 1 );
>      if ( dy < 0 )
>        dy = -dy;
>      if ( dx < dy )
>        dx = dy;
> -    db = dx;
>  
> +    /* Check whether an approximation with straight lines is sufficient. */
>      level = 1;
> -    da    = da / ras.cubic_level;
> -    db    = db / ras.conic_level;
> -    while ( da > 0 || db > 0 )
> +    dx    = dx / ras.conic_level;
> +    while ( dx > 0 )
>      {
> -      da >>= 2;
> -      db >>= 3;
> +      dx >>= 3;
>        level++;
>      }
>  
>      if ( level <= 1 )
>      {
> -      TPos   to_x, to_y, mid_x, mid_y;
> +      TPos   to_x, to_y;
>  
>  
>        to_x  = UPSCALE( to->x );
> @@ -1104,7 +1099,7 @@
>  
>      Draw:
>        {
> -        TPos  to_x, to_y, mid_x, mid_y;
> +        TPos  to_x, to_y;
>  
>  
>          to_x  = arc[0].x;
>
>