Graham, I finally had a brief chance to look at the code yesterday, and hope to be able to spend most of the rest of today on it too. (So far I have only looked at the pre-2.4.0 code.) gray_render_cubic is a (non-recursive implementation of) a recursive algorithm for splitting the curve into 2^n line segments. This is "forward differencing" rather than "recursive subdivision" (which determine whether each subdivision is required independently).
At the moment I don't understand the basis for the calculation of n, though I presume that it is some standard heuristic. You point 7 below rather brings that into doubt though! This was probably state-of-the-art when it was first implemented, but is probably quite inefficient in the number of line segments created. I've added further comments inline below, and some queries at the end. > -----Original Message----- > From: freetype-devel-bounces+david.bevan=pb....@nongnu.org > [mailto:freetype-devel-bounces+david.bevan=pb....@nongnu.org] On Behalf Of > GRAHAM ASHER > Sent: 3 September 2010 09:14 > To: FreeType > Subject: [ft-devel] more thoughts on cubic spline flattening > > 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%20ccc > g04%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). This isn't quite the whole story. The curve may extend outside the infinite strip perpendicular to the chord P0P3 as seen in Hain's Figure 2. Indeed it may do so even if the curve never deviates from the chord in the s-direction by more than the maximum acceptable deviation value (because both control points are very close to the line which extends the chord). This is the reason for Hain's section 3.2 on the longitudinal deviation. However, there's a simple approach for handling this: if P0 or P3 is (more than the maximum acceptable deviation value) outside the strip, subdivide. Hain mentions this at the end of his section 1. > 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.) Perhaps I've missed something, but my reading of Hain's paper is that the evaluation of square roots is never actually needed. > 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. This looks like a variant of what Hain describes on pp1-2. > 5. Therefore a usable fast heuristic is the maximum coordinate distance > from the > middle of the chord, multiplied by 0.75. I don't think that will work. A control point can be sqrt(2) x max(dx,dy) from the chord (if dx=dy), so we need to factor that into the calculation. An example: P0: 0,0 P1: 0,99 P2: 1,100 P3: 100,100 v = 1 so the max deviation = 0.75 * 99 / sqrt(2) ~= 52.50 But max(dx,dy) = 50, so the heuristic would give 0.75 * 50 = 37.5. You would need to use a factor at least 0.75 * sqrt(2) ~= 1.06, rather than 0.75. For this example it would give an estimate of ~53.03. For sensible estimates, it is necessary to work in Hain's r-s coordinate system. > 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. Some queries: A. Perhaps it's obvious to someone familiar with the FreeType code, but (to save me time trying to work it out), in the units being used in gray_render_cubic, what is the maximum acceptable deviation value that should be used as a cut-off for stopping subdivision? Perhaps the answer could briefly explain the use of DOWNSCALE and UPSCALE. B. Would it be possible to have a copy of the font that was the catalyst for the changes in 2.4.0, along with details of the character / resolution / point-size which shows the problem. C. Similarly, would it be possible to have a copy of the font that showed up the bug in the changed code (with similar details). Thanks. David %^> ________________________________ David Bevan Development Manager Pitney Bowes Emtex Software Tel: +44 (0)1923 279300 david.be...@pb.com ________________________________ > Comments please. > > Thanks in advance, > > Graham > > _______________________________________________ > Freetype-devel mailing list > Freetype-devel@nongnu.org > http://lists.nongnu.org/mailman/listinfo/freetype-devel _______________________________________________ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel