[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%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
RE: [ft-devel] more thoughts on cubic spline flattening
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
Re: [ft-devel] Re: render error after ftgrays: Speed up rendering of small cubic splines.
It seems that this mail didn't came through... Oops! It's there already http://lists.gnu.org/archive/html/freetype-devel/2010-08/msg00031.html Sorry for the duplicate. Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] more thoughts on cubic spline flattening
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). Here it is: http://lists.gnu.org/archive/html/freetype-devel/2010-08/msg00031.html Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] more thoughts on cubic spline flattening
David, you are of course correct that my point 5 is wrong. That is just carelessness on my part. Some clarifications: You point out that p0 and p3 can have coordinates outside the range 0...1 in Hain's r/s system. I deliberately ignore that, and I should have explained why in more explicit terms. The aim of FreeType is to rasterize the outline of a closed curve, and for this purpose I believe that, just as we can ignore deviations from the curve of greater than a certain tolerance, we can ignore spikes with maximum width less than that tolerance. P0 and P3 coordinates of this type create such spikes. But if we a heuristic based on the maximum distance of control point coordinates from the middle of the chord, the problem doesn't arise anyway. It arises only if we use Hain's algorithm fully. You said my reading of Hain's paper is that the evaluation of square roots is never actually needed. To get the deviations of the control points we need to either (i) rotate the points into the r/s coordinate system, and the simplest way of creating a rotation transform requires square roots (convert chord vector to unit vector by dividing by vector length obtained by Pythagoras, then sine and cosine needed for transform are x and y coords of vector); or (ii) use the standard method of finding the distance of a point from a line, which again needs Pythagoras to get the lengths of vectors. I hope I've missed some simpler way of doing it, in which case please tell me. In answer to your question A: the units are 64ths of a pixel, so 16 is a quarter pixel. That is for the normal case; FreeType can be configured to use different numbers of bits per pixel. The controlling macro is PIXEL_BITS in ftgrays.c In answer to question B: I don't know; perhaps Werner can answer. I don't follow everything on the FreeType list, and have long periods when I haven't time to look at anything. In answer to question C: yes, I posted the font and screen shots to the list a few days ago - and I see that Werner has just linked to it in his latest post. Graham David Bevan wrote: 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
RE: [ft-devel] more thoughts on cubic spline flattening
Some brief comments inline. More feedback from my investigations later. -Original Message- From: Graham Asher [mailto:graham.as...@btinternet.com] Sent: 3 September 2010 13:56 To: David Bevan Cc: FreeType Subject: Re: [ft-devel] more thoughts on cubic spline flattening David, you are of course correct that my point 5 is wrong. That is just carelessness on my part. Some clarifications: You point out that p0 and p3 can have coordinates outside the range 0...1 in Hain's r/s system. I deliberately ignore that, and I should have explained why in more explicit terms. The aim of FreeType is to rasterize the outline of a closed curve, and for this purpose I believe that, just as we can ignore deviations from the curve of greater than a certain tolerance, we can ignore spikes with maximum width less than that tolerance. P0 and P3 coordinates of this type create such spikes. That does not follow the recommended PostScript Language scan-conversion rules for path fills (PLRM3 7.5.1) - a shape is scan-converted by painting any pixel whose square region intersects the shape, however small the intersection is. Whether that rule should actually be applied to character shapes is another matter though (see the last paragraph of 7.5.1). But if we a heuristic based on the maximum distance of control point coordinates from the middle of the chord, the problem doesn't arise anyway. It arises only if we use Hain's algorithm fully. That's a very good point. You said my reading of Hain's paper is that the evaluation of square roots is never actually needed. To get the deviations of the control points we need to either (i) rotate the points into the r/s coordinate system, and the simplest way of creating a rotation transform requires square roots (convert chord vector to unit vector by dividing by vector length obtained by Pythagoras, then sine and cosine needed for transform are x and y coords of vector); or (ii) use the standard method of finding the distance of a point from a line, which again needs Pythagoras to get the lengths of vectors. I hope I've missed some simpler way of doing it, in which case please tell me. Hain explains how to do the calculations in section 3. The rotation is simply achieved by using the equation for s (where the denominator of L^2 can be ignored as Hain further explains). The last paragraph of section 3 then describes how to do the necessary comparison thereby avoiding a square root evaluation. The challenge will be ensuring that we can use the widest range of integer values without overflow. Squaring the P0-P3 distance seems unavoidable. Using unsigned 32-bit values (which we should be able to use for values which are always positive) allows us up to 65536 = 1023 pixels = 1.7 at 600dpi. However, there is one very simple heuristic solution to this: subdivide once automatically if the chord length is too great. In answer to your question A: the units are 64ths of a pixel, so 16 is a quarter pixel. That is for the normal case; FreeType can be configured to use different numbers of bits per pixel. The controlling macro is PIXEL_BITS in ftgrays.c Thanks for the answer; obviously your previous email gave a big hint! Regards, David %^ ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
RE: [ft-devel] more thoughts on cubic spline flattening
I've added some trace code to gray_render_cubic to report the average number of line segments created for a Bezier arc, and to calculate for each segment the (exact) deviation of the arc segment it replaces. I've still only tested this with the pre-2.4.0 code. Here are the results with my test data: For screen resolutions, an average of about 9 segments are generated per arc, with an average deviation of about 1.5 (x 1/64 pel) and a maximum deviation of about 11 (x 1/64 pel). For printer resolutions, an average of about 12 segments are generated per arc, with an average deviation of about 2.5 (x 1/64 pel) and a maximum deviation of about 20 (x 1/64 pel). In both cases, about 20% of the segments have a deviation less that 0.5 (x 1/64 pel). Assuming I have the time, next week I'll attempt to implement something based on Hain's paper. I will also do some profiling (timing) of the code, so we can compare performance. David %^ ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] more thoughts on cubic spline flattening
In answer to question B: I don't know; perhaps Werner can answer. I don't follow everything on the FreeType list, and have long periods when I haven't time to look at anything. If I understand David correctly, he wants you to present the details which have motivated you to work on the flattening algorithm. In other words, do you have a font or test case which triggers an excessive number of subdivisions with the old algorithm? Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] more thoughts on cubic spline flattening
Some brief comments inline. More feedback from my investigations later. [...] BTW, thanks a lot to both of you for working on this! Is there something which I shall already commit to the repository? Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
