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

[David Bevan]

> -----Original Message-----
> From: GRAHAM ASHER [mailto:address@hidden
> Sent: 8 September 2010 11:49
> To: David Bevan
> Cc: FreeType
> Subject: Re: [ft-devel] latest patch file for spline flattening
> 
> That's great - but can you refresh my memory on where the constants 236
> and 97
> (236/256 = 0.92..., 97/256 = 0.379...) in this expression come from, so
> that I
> can eventually write a comment on it?
> 
>        L = (  236 * FT_MAX(labs(dx), labs(dy))
>             +  97 * FT_MIN(labs(dx), labs(dy))) >> 8;


Sorry, I should have explained that.

Obviously, for the correct behaviour of the code, we need L to be an 
underestimate of the chord length.


In a previous email, I mentioned that, if dx >= dy, then r = sqrt(dx^2 + dy^2) 
can be overestimated with least maximum error by

  r_upperbound = dx + (sqrt(2) - 1) * dy

where sqrt(2) - 1 can be (over)estimated by 107/256 - giving an error of no 
more than 8.4%.


Similarly, some elementary calculus shows that r can be underestimated with 
least maximum error by

  r_lowerbound = sqrt(2+sqrt(2))/2 * dx + sqrt(2-sqrt(2))/2 * dy

236/256 and 97/256 are (under)estimates of the two algebraic numbers - giving 
an error of no more than 8.1%.


> It might also be better to calculate the absolute values and max and min
> just
> once but it probably makes little difference; I don't know. Like this (you
> did
> something like this in an earlier version, didn't you?)
> 
> if (dx < 0)
>   dx = -dx;
> if (dy < 0)
>   dy = -dy;
> if (dx > dy)
>   L = (236 * dx + 97 * dy) >> 8;
> else
>   L = (236 * dy + 97 * dx) >> 8;


That won't work; dx and dy are used later and need their signs, so you can't 
change what they mean. If you want to avoid calculating the absolute values 
twice, you'll need to store the results in new variables.


David %^>