[ft-devel] more thoughts on cubic spline flattening

[GRAHAM ASHER]

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