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

Graham/Werner,

Perhaps I have misunderstood something. If so, I apologize.

I hadn't been following this closely until I noticed an email saying that the curve flattening algorithm failed under some circumstances. That seemed very shocking to me. I would have presumed that the flattening algorithm would be defined in a mathematically rigorous manner and hence would be known to always work (bar any 'typos' in the code).

Checking through the ft-devel archive suggests that the beginning of this issue was the message of 7th June, which starts, "I have discovered a possible inefficiency in gray_render_cubic in ftsmooth.c. Removing it (by means of what I admit is a hack based on a limited understanding of the code) gives a vast speedup with no apparent loss of quality."

For something as critical as the curve flattening, I wouldn't consider a "hack" of any sort appropriate. I haven't followed the message trail in detail but my understanding is that some version of this hack was accepted into the source and was subsequently shown to be incorrect. Fixes are now being proposed to the hack, and this is being done by someone who states that they are somewhat ignorant of the mathematics of cubic splines.

If I was managing this project, I would certainly consider this an unacceptable approach / sequence of events. Better to keep the inefficiency than (a) break the functionality, and (b) end up with code that is not obviously correct.

I didn't respond to the following query earlier:

"If there are any good mathematicians out there (better than me at this, which sets quite a low bar), please confirm that no point on a cubic spline curve with both control points on the same side of the straight line from start to end can be further from the line than the curve's midpoint as defined by bisection of the curve."

A simple continuity/smoothness argument shows that the maximum deviation of a cubic spline is not always at the curve's midpoint: If with the control points on either side, the maximal deviation can be elsewhere, and a smooth movement of the control points leads to a smooth change in the curve then the position of the maximal deviation moves smoothly too (and hence is in fact hardly ever actually at the mid-point).

I don't have time to investigate this in detail for a while, but might be able to do so sometime next week.

David %^>

P.S. I have a degree in mathematics from Oxford University.

> -----Original Message-----

> From: GRAHAM ASHER [mailto:address@hidden

> Sent: 31 August 2010 12:19

> To: David Bevan; freetype-devel

> 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%20ccc

> g04%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

From:	David Bevan
Subject:	RE: [ft-devel] a satisfactory fix for the cubic spline bug
Date:	Tue, 31 Aug 2010 09:01:43 -0400