Re: [ft-devel] tentative fix for cubic spline bug

[Graham Asher]

Here's a better fix that also works (below). I now check whether the 
control points are actually on different sides of the straight line from 
start to end. The only weak point is possible integer overflow here: 
suggestions, please:

   side0 = (x6 - x0) * (control1->y - y0) - (y6 - y0) * (control1->x - 
x0) <= 0;
   side1 = (x6 - x0) * (control2->y - y0) - (y6 - y0) * (control2->x - 
x0) <= 0;

In this code, side0 and side1 are set to 0 or 1 according to whether the 
control points are on the left or the right of the straight line.

But I am starting to wonder if a simpler approach might be better. 
Rather than calculating the number of iterations of the curve splitting 
loop in advance, perhaps it might be more efficient, and certainly 
simpler to code correctly, to iterate until neither of the two control 
points is further than 16 units from the start or end. That would, it is 
true, produce far too many iterations for very flat curves.

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;

   /*
   If the control points are on different sides of the curve,
   split the cubic into two, creating 7 points,
   then find the midpoints of the first and second curves.
   Splitting guarantees that the two curves' control points
   are both on the same side of the straight line from start to end.
   Find how far the midpoints are from the straight lines joining
   the start and end of the two curves. If they are close enough
   we can draw them as straight lines.
   */
   int x0, x1, x2, x3, x4, x5, x6, midx0, midx1;
   int y0, y1, y2, y3, y4, y5, y6, midy0, midy1;
   int dx0, dx1, dy0, dy1;
   int side0, side1;
   int mid_x, mid_y;
      
   x0 = DOWNSCALE(ras.x);
   x6 = to->x;
   y0 = DOWNSCALE(ras.y);
   y6 = to->y;

   side0 = (x6 - x0) * (control1->y - y0) - (y6 - y0) * (control1->x - 
x0) <= 0;
   side1 = (x6 - x0) * (control2->y - y0) - (y6 - y0) * (control2->x - 
x0) <= 0;

   if (side0 == side1)
       {
       mid_x = (x0 + x6 + 3 * (control1->x + control2->x)) / 8;
       mid_y = (y0 + y6 + 3 * (control1->y + control2->y)) / 8;
       dx0 = x0 + x6 - (mid_x << 1); if (dx0 < 0) dx0 = -dx0;
       dy0 = y0 + y6 - (mid_y << 1); if (dy0 < 0) dy0 = -dy0;
       if (dx0 < dy0)
           dx0 = dy0;
       }
   else
       {
       x1 = (x0 + control1->x) / 2;
       x3 = (control1->x + control2->x) / 2;
       x5 = (control2->x + x6) / 2;
       x2 = (x1 + x3) / 2;
       x4 = (x3 + x5) / 2;
       mid_x = x3 = (x2 + x4) / 2;   
       midx0 = (x0 + x3 + 3 * (x1 + x2)) / 8;
       midx1 = (x3 + x6 + 3 * (x4 + x5)) / 8;
       dx0 = x0 + x3 - (midx0 << 1); if (dx0 < 0) dx0 = -dx0;
       dx1 = x3 + x6 - (midx1 << 1); if (dx1 < 0) dx1 = -dx1;

       y1 = (y0 + control1->y) / 2;
       y3 = (control1->y + control2->y) / 2;
       y5 = (control2->y + y6) / 2;
       y2 = (y1 + y3) / 2;
       y4 = (y3 + y5) / 2;
       mid_y = y3 = (y2 + y4) / 2;   
       midy0 = (y0 + y3 + 3 * (y1 + y2)) / 8;
       midy1 = (y3 + y6 + 3 * (y4 + y5)) / 8;
       dy0 = y0 + y3 - (midy0 << 1); if (dy0 < 0) dy0 = -dy0;
       dy1 = y3 + y6 - (midy1 << 1); if (dy1 < 0) dy1 = -dy1;

       if (dx0 < dx1)
           dx0 = dx1;
       if (dx0 < dy0)
           dx0 = dy0;
       if (dx0 < dy1)
           dx0 = dy1;
       }

   level = 1;
   dx0 /= ras.cubic_level;
   while ( dx0 > 0 )
   {
     dx0 >>= 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

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