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%20cccg04%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: freetype-devel-bounces+david.bevan=pb@nongnu.org [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] 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 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
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 david.be...@pb.com To: freetype-devel freetype-devel@nongnu.org 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%20cccg04%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: freetype-devel-bounces+david.bevan=pb@nongnu.org [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] 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
Re: [ft-devel] a satisfactory fix for the cubic spline bug
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. Well, Graham tries to make FreeType faster than the originally used (and working) algorithm. Since it apparently hasn't been, we can make use of the latest research. Thanks! I'm waiting for Graham's comments :-) Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] a satisfactory fix for the cubic spline bug
Correction: for we are restricted to a maximum coordinate size of sqrt(2^31) read we are restricted to a maximum coordinate size of the cube root of 2^31 - Original Message From: GRAHAM ASHER graham.as...@btinternet.com To: David Bevan david.be...@pb.com; freetype-devel freetype-devel@nongnu.org Sent: Tuesday, 31 August, 2010 12:18:45 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 david.be...@pb.com To: freetype-devel freetype-devel@nongnu.org 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%20cccg04%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: freetype-devel-bounces+david.bevan=pb@nongnu.org [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] 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) +
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:graham.as...@btinternet.com] 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 david.be...@pb.com To: freetype-devel freetype-devel@nongnu.org Sent: Tuesday, 31 August, 2010
Re: [ft-devel] a satisfactory fix for the cubic spline bug
If I was managing this project, I would certainly consider this an unacceptable approach / sequence of events. Usually, I'm quite conservative, and Graham has provided a lot of useful additions to the FreeType code. I trust him to fix that in due course. Better to keep the inefficiency than (a) break the functionality, and (b) end up with code that is not obviously correct. Uh, oh, you are extremely exaggerating. This is not helpful. Until the bug report we weren't aware of problems, and Graham's change is in since two months already, and the code is probably run by millions of people... It's easy to revert if no satisfying solution can be found. Thanks for offering help, though. Werner ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] a satisfactory fix for the cubic spline bug
David, some points on what I think is a rather severe disquisition on your part: (i) You over-react to my use of the word 'hack', which was light-hearted and self-deprecatory. Yes, my original fix was incorrect, and I have now found one that I am satisfied is correct. This is a normal process in software development. Unfortunately nobody understands FreeType fully any more. This is a bad situation, but somewhat mitigated by the number of eyes on the problem, and the number of users willing to test the code. A full suite of regression tests, isolating each module and algorithm, would be great. If you do end up with some time, please consider writing some. I did not check in the fix. I merely proposed it, hoping for comments and improvements. I am very busy and any help is welcome. (ii) The error in gray_render_cubic was gross. It didn't cause a slight inefficiency; it resulted in a very great number of unnecessary bisections. (iii) Although there are provably correct mathematical algorithms, converting them to provably correct computer programs is non-trivial - in fact, impossible outside small toy problems. Your statement Better to keep the inefficiency than (a) break the functionality, and (b) end up with code that is not obviously correct. is laudable, but substantive code that is obviously correct doesn't exist in this world. (iv) The phrase 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. is strange. Why the passive voice and the use of someone? It's still me, and my name appears on the e-mails. I have been working on and off with cubic splines since about 1986. No, my degree is not in mathematics, but I am not ignorant of these matters. (v) Congratulations on your degree. I hope you have time to use your mathematical knowledge to help with this problem. (vi) Out of interest, please give an example, with coordinates, of a cubic spline with both control points on the same side of the straight line from start to end, for which the midpoint of the curve, as defined by bisection, is not the point of maximum deviation. Best regards, Graham From: David Bevan david.be...@pb.com To: GRAHAM ASHER graham.as...@btinternet.com; freetype-devel freetype-devel@nongnu.org Sent: Tuesday, 31 August, 2010 14:01:43 Subject: 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-
Re: [ft-devel] a satisfactory fix for the cubic spline bug
And putting this equation into more standard quadratic form I get d_norm(v) = 0.072(v^2) + 0.229v + 0.449 which yields 0.75 as expected for v = 1, so it looks as though I have the right equation here. Graham From: GRAHAM ASHER graham.as...@btinternet.com To: David Bevan david.be...@pb.com Sent: Tuesday, 31 August, 2010 17:07:52 Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug Can you give the workings? The equation I think you mean is this one: 0.07200(v + 3.180556)v + 0.449000, so when I substitute 0.1 for v I get 0.07200(0.1 + 3.180556)0.1 + 0.449000 which gives 0.47262, and multiplying that by 50, the maximum deviation of a control point, gives 23.631, not your y value, so obviously I'm missing something; Thanks, Graham From: David Bevan david.be...@pb.com To: GRAHAM ASHER graham.as...@btinternet.com Sent: Tuesday, 31 August, 2010 16:20:08 Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug From:GRAHAM ASHER [mailto:graham.as...@btinternet.com] Sent: 31 August 2010 15:56 To: David Bevan Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug Midpoint as defined by bisection is the point you get when you split a cubic spline into two by the bisection method (as used by FreeType in gray_split_cubic). It is defined as the midpoint of the line between the two midpoints of the lines between the three midpoints of the lines between the four control points, taken in order. It is of course a point on the curve. So that’s the point t = 0.5 in the parametric equation — found using de Casteljau’s algorithm. Your example gives a midpoint of (31.25, 20.625). Applying the midpoint method again (hastily) to the left-hand curve seems to yield a y coordinate of 21.84375, so if my arithmetic is correct your example is a good one. Using the equation in Hain’s paper (p.4; with v=0.1), the maximum deviation tmax in my example is at 0.3503928884, which is the point (16.26529900, 23.37564709). David %^ Thanks, Graham From:David Bevan david.be...@pb.com To: GRAHAM ASHER graham.as...@btinternet.com Sent: Tuesday, 31 August, 2010 15:20:59 Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug From:GRAHAM ASHER [mailto:graham.as...@btinternet.com] Sent: 31 August 2010 15:01 To: David Bevan; freetype-devel Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug David, (vi) Out of interest, please give an example, with coordinates, of a cubic spline with both control points on the same side of the straight line from start to end, for which the midpoint of the curve, as defined by bisection, is not the point of maximum deviation. I expect that something like the following would be an example: P0: 0,0 P1: 0,50 P2: 50,5 P3, 100,0 But to be sure I’d need to know what you mean by “midpoint as defined by bisection”? Is it t = 0.5 in the parametric equation, the point perpendicular to the midpoint of the chord, or something else? David %^___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel
Re: [ft-devel] a satisfactory fix for the cubic spline bug
GA == GRAHAM ASHER graham.as...@btinternet.com writes: GA Some reasons this hasn't made very many waves; GA 1. My impression is that nearly all actual fonts are TrueType these GA days. TrueType does't use cubic splines. It uses quadratics only. Cubic fonts remain an important sector, especially for print and for display of work intended for print. That notwithstanding: GA 2. Font designers very rarely use 'exciting' cubic splines. Splines GA with control points on both sides of the line hardly ever occur in GA glyphs, and I would expect self-crossing curves never to occur. That, on the other hand, is very true. In fact, and IIRC, Adobe actively promotes those objective to font designers, to ensure that the fonts work well with their software, including both their desktop software and their PS/PDF engines. GA We must of course be correct for all curves, but we need optimise GA heavily only for the common case where p0, p1, p2 and p3 have GA r-coordinates (using Hain's notation) in that order, and GA s-coordinates with the same sign. Consequent to your second point, that is also true. -JimC -- James Cloos cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6 ___ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel