RE: [ft-devel] a satisfactory fix for the cubic spline bug

[David Bevan]

Rather than piecemeal reinventing of the wheel, I would have thought that FT 
should implement a mathematically rigorous flattener. The following might be a 
good place to start:

http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf

Or:

http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

Naively, I had assumed that this sort of issue would have been resolved 
properly back in the pre-history of FT, since it is obviously of critical 
importance for correct output.

Since it apparently hasn't been, we can make use of the latest research.

David %^>


> -----Original Message-----
> From: address@hidden
> [mailto:address@hidden On Behalf Of
> Graham Asher
> Sent: 30 August 2010 10:59
> To: freetype-devel
> Subject: [ft-devel] a satisfactory fix for the cubic spline bug
> 
> I thought about this overnight and realised that we can slightly modify
> the existing heuristic to get a much simpler fix. Instead of trying to
> find points on the curve or trying to measure the distance from a point
> to a straight line, we adapt the earlier idea, used in existing FreeType
> code, of finding the maximum coordinate difference (that is, whichever
> is greater of dx and dy):
> 
> * existing method: use max coordinate difference between middle of
> spline, found by bisection, and middle of straight line
> 
> * new method: use max coordinate difference between either of the two
> control points and the middle of the straight line
> 
> This yields the following code (start of gray_render_cubic), which
> works, fixes the bug, and is probably faster, because it is certainly
> simpler. I don't think I'll go any further than this.
> 
>   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;
> 
>     if (dx1 <= ras.cubic_level)
>         return gray_render_line( RAS_VAR_ to->x, to->y );
> 
>     level = 1;
>     dx1 /= ras.cubic_level;
>     while ( dx1 > 0 )
>     {
>       dx1 >>= 2;
>       level++;
>     }
> 
> 
> Graham
> 
> 
> _______________________________________________
> Freetype-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/freetype-devel