[cairo] Fwd: RE: [ft-devel] latest patch file for spline flattening
Behdad Esfahbod
behdad at behdad.org
Tue Sep 7 09:25:08 PDT 2010
Thought people may find the hypot() estimate useful here.
behdad
-------- Original Message --------
Subject: RE: [ft-devel] latest patch file for spline flattening
Date: Mon, 6 Sep 2010 07:04:14 -0400
From: David Bevan <david.bevan at pb.com>
To: Graham Asher <graham.asher at btinternet.com>
CC: freetype-devel <freetype-devel at nongnu.org>
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.com at nongnu.org
> [mailto:freetype-devel-bounces+david.bevan=pb.com at 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 at nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel
More information about the cairo
mailing list