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: address@hidden
[mailto:address@hidden 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