Re: [ft-devel] latest patch file for spline flattening

[GRAHAM ASHER]

That's great - but can you refresh my memory on where the constants 236 and 97 
(236/256 = 0.92..., 97/256 = 0.379...) in this expression come from, so that I 
can eventually write a comment on it?

       L = (  236 * FT_MAX(labs(dx), labs(dy)) 
            +  97 * FT_MIN(labs(dx), labs(dy))) >> 8;

It might also be better to calculate the absolute values and max and min just 
once but it probably makes little difference; I don't know. Like this (you did 
something like this in an earlier version, didn't you?)

if (dx < 0)
  dx = -dx;
if (dy < 0)
  dy = -dy;
if (dx > dy)
  L = (236 * dx + 97 * dy) >> 8;
else
  L = (236 * dy + 97 * dx) >> 8;

Another finicky point; to get this into FreeType I'll have to remove 
assignments 
inside conditionals.

Graham




----- Original Message ----
From: David Bevan <address@hidden>
To: Graham Asher <address@hidden>; freetype-devel 
<address@hidden>
Sent: Wednesday, 8 September, 2010 8:50:51
Subject: RE: [ft-devel] latest patch file for spline flattening


Graham,

Here's a final revision.

It produces exactly the same results as the previous one but the code is a bit 
faster (and also easier to understand - the previous code was trying to be a 
bit 
too clever).

David %^>


  static void
  gray_render_cubic( RAS_ARG_ const FT_Vector*  control1,
                              const FT_Vector*  control2,
                              const FT_Vector*  to )
  {
    FT_Vector*  arc;


    arc      = ras.bez_stack;
    arc[0].x = UPSCALE( to->x );
    arc[0].y = UPSCALE( to->y );
    arc[1].x = UPSCALE( control2->x );
    arc[1].y = UPSCALE( control2->y );
    arc[2].x = UPSCALE( control1->x );
    arc[2].y = UPSCALE( control1->y );
    arc[3].x = ras.x;
    arc[3].y = ras.y;

    for (;;)
    {
    /* 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;

    /* Decide whether to split or draw */
    /* See Hain's paper at http://tinyurl.com/HainBez for more info */
    {
       TPos  dx, dy, L, dx1, dy1, dx2, dy2, s, s_limit;


       /* dx and dy are x- and y- components of the P0-P3 chord vector */
       dx = arc[3].x - arc[0].x;
       dy = arc[3].y - arc[0].y; 

       /* L is an (under)estimate of the Euclidean distance P0-P3 */
       L = (  236 * FT_MAX(labs(dx), labs(dy)) 
            +  97 * FT_MIN(labs(dx), labs(dy))) >> 8;

       /* avoid possible arithmetic overflow below by splitting */
       if (L > 32767)
          goto Split;

       /* s is L * the perpendicular distance from P1 to the line P0-P3 */
       s = labs(  dy * (dx1 = arc[1].x - arc[0].x) 
                - dx * (dy1 = arc[1].y - arc[0].y));

       /* max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1) */
       if (s > (s_limit = L * (TPos)(FT_MAX_CURVE_DEVIATION / 0.75)))
          goto Split;

       /* s is L * the perpendicular distance from P2 to the line P0-P3 */
       s = labs(  dy * (dx2 = arc[2].x - arc[0].x) 
                - dx * (dy2 = arc[2].y - arc[0].y));

       /* max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1) */
       if (s > s_limit)
          goto Split;

       /* if P1 or P2 is outside P0-P3, split */
       if (   dy * dy1 + dx * dx1 < 0
           || dy * dy2 + dx * dx2 < 0
           || dy * (arc[3].y - arc[1].y) + dx * (arc[3].x - arc[1].x) < 0
           || dy * (arc[3].y - arc[2].y) + dx * (arc[3].x - arc[2].x) < 0
          )
          goto Split;

       /* no reason to split */
       goto Draw;
    }
    
    Split:
    
    gray_split_cubic( arc );
    arc += 3;
    continue;

    Draw:

    gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );

    if (arc == ras.bez_stack)
      return;

    arc -= 3;
    }
  }