Graham, That's looking much closer to what I would have thought we needed; only splitting the curve when required. However, your "fast heuristic" can be very inaccurate.
Consider P0: 0,0 P1: 5,5 P2: 95,5 P3: 100,0 The max deviation is 3.75 (0.75 * 5 since Hain's v == 1), but your heuristic gives a value of 45 - twelve times too great. Btw, I think that dx1, dy1, ... need to be of type TPos, not int. On the issue of avoiding square roots, a little bit of algebra shows that it is possible to estimate r = sqrt(dx^2 + dy^2) with a simple linear combination of dx and dy. For example, if an overestimate is required, and dx >= dy, you can use r_upperbound = dx + (sqrt(2) - 1) * dy which overestimates by no more than 8.5%. For integer arithmetic, sqrt(2) - 1 can be (over)estimated by 107/256. For example, you could use this approximation to do something like this: dx1 = abs(control1->x - midx); dy1 = abs(control1->y - midy); if (dx1 >= dy1) dr1 = dx1 + (107 * dy1 + 255) >> 8; else dr1 = dy1 + (107 * dx1 + 255) >> 8; dx2 = abs(control2->x - midx); dy2 = abs(control2->y - midy); if (dx2 >= dy2) dr2 = dx2 + (107 * dy2 + 255) >> 8; else dr2 = dy2 + (107 * dx2 + 255) >> 8; /* deviation never exceeds 75% of control point dist */ if (dr1 >= dr2) dev_max = (3 * dr1 + 3) >> 2; else dev_max = (3 * dr2 + 3) >> 2; if (dev_max <= FT_MAX_CURVE_DEVIATION) ... Of course, this doesn't resolve the problem I mentioned above; for the example curve, this gives dev_max a value of 36 - still nine times too great. I hope to have something based a bit more closely on Hain's paper by the end of tomorrow. I may use something like the square-root avoiding estimate above to approximate his L value. 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: 6 September 2010 11:10 > To: freetype-devel > Subject: [ft-devel] latest patch file for spline flattening > > Here's a new version of my spline flattening patch. (I would like to be > able to push this to the git repository but am having authentication > problems; Werner has been helping me, but no success so far, probably > because of my ineptitude in these matters.). > > The nub of the latest change is that I found that predicting the number > of recursion levels is not reliable when splitting a cubic spline for > flattening. A better way is to check the flatness inside the loop - > using the fast heuristic of taking the maximum coordinate difference of > a control point from the chord midpoint. This also makes the code > simpler - and, surprisingly, faster, according to my benchmark; however, > my benchmark is based on cartographic, not typographic, use, so will > need confirmation. > > The patch obviously still solves the bug involving s-shaped curves > (control points on both sides of the chord). > > Graham _______________________________________________ Freetype-devel mailing list Freetype-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/freetype-devel