[Devel] Some thoughts about fttrigon.c

[eiked]

Quite a while ago I looked at fttrigon.c and --- in the course ---
read a bit about "cordic" math. Unfortunately I lost my notes, but
since the functions are now in use, I try to recall some issues:

1) Possible omission of initial left shift in "ft_trig_pseudo_rotate"
   and "ft_trig_pseudo_polarize"

Both, "ft_trig_pseudo_rotate" and "ft_trig_pseudo_polarize" do some
argument reduction. This makes it possible to omit the initial left
shift in these functions. To approximate angles between -90 and 90
degrees it's enough to use a discrete basis starting with atan(2^0)=
45 deg.

It's possible to push argument reduction one step further. This allows
one to choose a basis starting with atan(2^-1) which is advantageous
(see below). But then again, the needed additional code is probably not
worth it.

An immediate gain of choosing a basis atan(2^i), i=0, -1, ... (apart
from less code) is that the "cordic shrink factor" grows, i.e. the
vectors, whilst pseudo-rotating, are not being stretched as much. This
means we can preserve two additional bits in "ft_trig_prenorm".


2) Using optimal fixed point representations in interim calculations

After switching to a different basis (see above) it may be worthwhile
to choose an 8.24 format for the atan-table. This format can then be
used as an interim format (after argument reduction in "ft_trig_pseudo_
rotate" and before "result expansion" (?) in "ft_trig_pseudo_polarize")
for angles. This gives a higher precision and allows more iterations
(if wanted).


3) Rounding

Forgot most of the things regarding rounding. The current rounding of
theta in "ft_trig_pseudo_polarize" is not clear to me. Applying 1) and
2) allows some rounding though.


4) Desired precision

IIRC there were some precision issues involved regarding differing FT1
and FT2 output. This brings up the question: How much precision do we
actually need? Reading the TrueType spec I couldn't find any details. In
any case, it is thinkable of varying the number of iterations (making it
an additional argument to "ft_trig_pseudo_rotate" and "ft_trig_pseudo_
polarize"). E.g. using 17 iterations for FT_Cos, FT_Sin is enough. Things
are no getting better using a 16.16 format. In other situations you are
getting better result using more than the current 23 iterations.



Apart from 1) it's probably not worth taking any of the above into account.

Also, I assume, the fttrigon.c code is mainly meant as a platform-
independent implementation making it easy to compare different ports of
freetype; so again, tweaking (except for the embedded folks) might not be
worth it (having modern fpu's in mind).

It was fun reading the fttrigon.c code and doing so running into the
opportunity of getting to know some cordic things ... Thanks FreeType!


Eike.

PS: In case of interest, I can dig out some code to illustrate the above.

-- 
GMX - Die Kommunikationsplattform im Internet.
http://www.gmx.net