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 Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel