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

[Graham Asher]

There is another error in flattening code, both for quadratic and cubic 
splines. The flattening criterion - the minimum 'heuristic distance' 
(approximation to the maximum deviation) is stored in 
TRaster.conic_level and TRaster.cubic_level. It is made larger for 
larger glyphs, which is clearly wrong:

   /* 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.max_ex > 24 || ras.max_ey > 24 )
       level++;
     if ( ras.max_ex > 120 || ras.max_ey > 120 )
       level++;

     ras.conic_level <<= level;
     ras.cubic_level <<= level;
   }

We can correct and simplify the code in two ways: (i) by defining a 
single constant flattening criterion:

/* The maximum distance of a curve from the chord, in 64ths of a pixel; 
used when flattening curves. */
#define FT_MAX_CURVE_DEVIATION__ 16

and of course deleting ras.conic_level and ras.cubic_level and the code 
quoted above;

and (ii) by drawing a straight line directly to the end of the curve 
when this deviation is not exceeded, instead of unnecessarily drawing a 
line to the midpoint, then to the end. If the midpoint is beyond the 
start and end of the chord, in r coordinates, it doesn't matter because 
the zero-width spike need not be drawn in any case.

Here's some code which works (and gives no apparent speed penalty, in 
fact a slight speed gain, but not enough to be significant, I think, 
because of benchmarking inaccuracies):

The start of gray_render_cubic becomes:

 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;

   /*
   Find the furthest distance of a coordinate of a control point from the
   midpoint of the line.
   */
   int 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;

   /*
   dx1 is the maximum distance of a control point coordinate
   from the middle of the chord, and the maximum deviation of the curve
   can never be greater than 3/4 of that, so multiply dx1 by 3/4.
   */
   dx1 *= 3;
   dx1 /= 4;

   if (dx1 <= FT_MAX_CURVE_DEVIATION)
       return gray_render_line( RAS_VAR_ to->x, to->y );       

   level = 1;
   dx1 /= FT_MAX_CURVE_DEVIATION;
   while ( dx1 > 0 )
   {
     dx1 >>= 2;
     level++;
   }

and the start of gray_render_conic becomes

 static int
 gray_render_conic( RAS_ARG_ FT_Vector*  control,
                             FT_Vector*  to )
 {
   TPos        dx, dy;
   int         top, level;
   int*        levels;
   FT_Vector*  arc;
   int error = 0;


   dx = DOWNSCALE( ras.x ) + to->x - ( control->x << 1 );
   if ( dx < 0 )
     dx = -dx;
   dy = DOWNSCALE( ras.y ) + to->y - ( control->y << 1 );
   if ( dy < 0 )
     dy = -dy;
   if ( dx < dy )
     dx = dy;

   if (dx <= FT_MAX_CURVE_DEVIATION)
       return gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( 
to->y ) );

   level = 1;
   dx = dx / FT_MAX_CURVE_DEVIATION;
   while ( dx > 1 )
   {
     dx >>= 2;
     level++;
   }

Graham


GRAHAM ASHER wrote:
> David Bevan's citation of two papers on spline flattening 
> (http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf
>  and 
> http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf)
>  stimulated some more thoughts on the problem. To recapitulate some existing 
> points, and ask some more questions, and point out another error in the current 
> FreeType logic (point 6):
>
> 1. The ideal flattening criterion is the maximum deviation (sideways distance) 
> of any point on the curve from the chord (straight line from p0 to p3; not the 
> line segment, but the whole infinite line).
>
> 2. Hain's paper shows that this can be approximated (yielding an estimate that 
> is never too small, and always quite close) by a quadratic equation based on the 
> ratio between the deviations of the two control points from the chord. If the 
> ratio (smaller deviation divided by larger) is v, the expression 0.072(v^2) + 
> 0.229v + 0.449, multiplied by the larger of the two deviations, gives this 
> approximation.
>
> 3. Calculating the expression in (2) is quite expensive because square root 
> operations are required to get the deviations of the two control points, and 
> some fixed-point arithmetic is needed to avoid or at least minimise overflow. (I 
> have coded this experimentally.)
>
> 4. There are a series of less accurate heuristics. The first relaxation is not 
> to evaluate the expression in (2), but to use the value 0.75, which is the 
> maximum value it can yield (v is always in the range 0...1, and v=1 yields 0.75; 
> smaller values of v give smaller results). However, this heuristic still 
> requires calculation of the deviations of the control points. A second 
> relaxation uses the maximum coordinate distance (max of dx and dy) of a control 
> point from the middle of the chord, which cannot be less than the actual 
> deviation.
>
> 5. Therefore a usable fast heuristic is the maximum coordinate distance from the 
> middle of the chord, multiplied by 0.75.
>
> 6. Unfortunately the current logic in FreeType has another error. It assumes 
> that the flattening criterion can be applied at the start, yielding the required 
> number of bisections. That is, a ratio is calculated between the heuristic 
> distance and a so-called 'cubic level'; and the number of bisections needed is 
> calculated as the ceiling of the base-4 logarithm of the heuristic distance; in 
> other words, there is an assumption that every bisection of a cubic spline 
> increases its flatness fourfold.
>
> 7. Here is the proof that the assumption in (6) is wrong. A cubic spline with 
> control points on different sides of the chord, symmetrically arranged, will be 
> bisected at the point where it crosses the chord. The two halves will have 
> exactly the same maximum deviation as the whole.
>
> This leads to the big question. Is it possible to determine the minimum number 
> of bisections needed at the start, using a formula that does not itself apply 
> the bisections - that is, something simpler than the exhaustive calculation? 
> (Perhaps flatness does increase fourfold if the control points are the same side 
> of the chord, so all we need do is add one iteration for an initial contrary 
> case.) I suspect that the answer is no, but I am sure David Bevan will want to 
> comment. If the answer is no, then I shall need to code up a fix that estimates 
> flatness efficiently on each iteration of the bisection loop.
>
> Comments please.
>
> Thanks in advance,
>
> Graham
>
> _______________________________________________
> Freetype-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/freetype-devel
>
>