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