[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [ft-devel] latest patch file for spline flattening
From: |
David Bevan |
Subject: |
RE: [ft-devel] latest patch file for spline flattening |
Date: |
Mon, 6 Sep 2010 07:04:14 -0400 |
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
- [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/06
- RE: [ft-devel] latest patch file for spline flattening,
David Bevan <=
- Re: [ft-devel] latest patch file for spline flattening, Graham Asher, 2010/09/06
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/06
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/07
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/07
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Re: [ft-devel] latest patch file for spline flattening, GRAHAM ASHER, 2010/09/07
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/07
- Message not available
- Message not available
- RE: [ft-devel] latest patch file for spline flattening, David Bevan, 2010/09/08