RE: [ft-devel] latest patch file for spline flattening

[David Bevan]

I'll do that. I wonder how much of the cost of FT_Load_Glyph is actually spent 
in gray_render_cubic and how much impact reducing the number of line segments 
has on later phases of the rendering process.

I'm also trying to see if I can come up with a heuristic that is both fast 
(i.e. simple linear combinations of positions) and accurate (i.e. always 
correct and any overestimate is reasonably bounded). Then we may be able to 
avoid the complexities of Hain's approach.

We so seem to be converging towards something that meets all the requirements.

I probably won't achieve much today, but hope to spend most of tomorrow on this.

David %^>


> -----Original Message-----
> From: Graham Asher [mailto:address@hidden
> Sent: 6 September 2010 12:36
> To: David Bevan
> Cc: freetype-devel
> Subject: Re: [ft-devel] latest patch file for spline flattening
> 
> David,
> 
> in fact I coded up and tested a different version using an accurate
> calculation of the control point deviation, but it was slower than the
> version I am proposing. I'll try your version; and I would be grateful
> if you could also do some benchmarking, because obviously we are not
> trying to minimise the number of straight line segments the curve is
> dissected into, but the overall speed. My aims, and my benchmarking, are
> rather biased, because my main use of cubic splines is for
> approximations to arcs of circles, used as parts of path envelopes when
> drawing maps.
> 
> Graham
> 
> 
> David Bevan wrote:
> > 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
> >>
> >
> >
> >
>