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

[GRAHAM ASHER]

Correction: for "we are restricted to a maximum coordinate 
size of sqrt(2^31)" read "we are restricted to a maximum coordinate 
size of the cube root of 2^31"


----- Original Message ----
From: GRAHAM ASHER <address@hidden>
To: David Bevan <address@hidden>; freetype-devel <address@hidden>
Sent: Tuesday, 31 August, 2010 12:18:45
Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug

David,

Thank you very much for the citations, which are very interesting, but I don't 
think anybody is proposing reinventing anything - least of all me. The problem 
here is not whether there are known rigorous methods of determining the 
flatness 

of a curve. We are looking for a very fast heuristic that reduces the number of 
bisections of a cubic spline to the minimum in most cases, and behaves 
reasonably in other cases; in that it never reduces the number of bisections 
below the minimum, or produces far too many.

Any system that always results in at least as many bisections as the minimum 
number required to flatten the curve to satisfy our definition of flatness, and 
does not enter an infinite loop, will give correct output.We know how to do the 
job correctly; the problem is doing it fast.

After looking at the papers you cite for a short while my impression is that 
they cannot easily be used without floating-point arithmetic, which is not used 
in FreeType (and that policy certainly won't be relaxed for a while, I am 
sure). 

Fixed-point is never a satisfactory substitute where multiplication and 
squaring 

of coordinates is used, because it can easily lead to overflows of the need for 
elaborate work-arounds for overflows. Methods relying on the cubic spline 
formula will inevitably require cubes of coordinates. FreeType works in 64ths 
of 

pixels, so in signed 32-bit arithmetic we are restricted to a maximum 
coordinate 

size of sqrt(2^31) = 1290 64ths, or 20 pixels, which makes it impossible. The 
method described in the first paper you cite requires as a starting point the 
distance of the control points from the straight line, which needs squares and 
square roots, posing more problems for integer overflow and speed.

If you can code up a better fix than mine, using one of the algorithms you 
cite, 

I will be very happy to withdraw my suggestion in favour of yours. I think an 
insuperable difficulty will be the possibility of overflow and the speed of the 
code. I hope to be proved wrong!

Best regards,

Graham




----- Original Message ----
From: David Bevan <address@hidden>
To: freetype-devel <address@hidden>
Sent: Tuesday, 31 August, 2010 9:14:36
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug


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


_______________________________________________
Freetype-devel mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/freetype-devel


_______________________________________________
Freetype-devel mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/freetype-devel