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

[David Bevan]

Yes, I had FT_MAX_CURVE_DEVIATION set to 16 for my tests.

David %^>


> -----Original Message-----
> From: Graham Asher [mailto:address@hidden
> Sent: 12 September 2010 10:06
> To: David Bevan
> Cc: 'freetype-devel'
> Subject: Re: [ft-devel] latest patch file for spline flattening
> 
>   David,
> 
> I've tested your code with CartoType, my map rendering library, and it
> produces a small speedup there too. (The smallness of the speedup is to
> do with the fact that CartoType's curves are nearly always
> approximations to arcs of circles, which don't behave too badly with my
> previous optimisation; I can see why your code works better with font
> glyphs.)
> 
> Therefore, combined with the fact that it significantly speeds up font
> rendering, and solves the bug that prompted this latest burst of work, I
> recommend that it goes into FreeType.
> 
> Werner, can you give a ruling on whether assignments in conditionals are
> allowed in FreeType code?
> 
> David, what value are you using for FT_MAX_CURVE_DEVIATION? I assume 16,
> which is a good conservative value.
> 
> The full patch also requires getting rid of the now-unneeded cubic-level
> and conic-level variables, and making minor changes to the conic
> splitting routine. However, we could perhaps make the change to cubic
> splitting independent of any changes to conic splitting, because the
> latter doesn't suffer from the original bug ('if it ain't broke don't
> fix it').
> 
> Best regards,
> 
> Graham
> 
> 
> 
> On 08/09/2010 08:50, David Bevan wrote:
> > 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;
> >      }
> >    }
> >
> >
> >
> >
> >
>