Sign in to follow this  
johnl87

Fixed point and trig functions

Recommended Posts

johnl87    133
I want to write a software renderer for my cellphone and I've read up on fixed point math, but how would I apply this to a fixed point number such as 0.5? The sin of 5 and .5 is different so how does that work?

Share this post


Link to post
Share on other sites
SiCrane    11839
Fixed point trig functions work pretty much the same as manual calculation of non-fixed point trig functions. The traditional method is to first map the angle into the range -PI to PI or 0 to 2*PI (depending on the trig function) and then apply a Taylor/Maclaurin expansion. For example, the expansion of sin(x) around 0 is x - x3/3! + x5/5! - x7/7! + x9/9! .... Just apply the number of terms necessary for the precision of your number.

Share this post


Link to post
Share on other sites
johnl87    133
Ah, I see. I was actually thinking about the built in functions in the math libraries but now that I think about it that won't work at all. So if I want to go 90 degrees, that's 0.5*PI so using that number I should get close to 1 right?

I'm not sure if I have the calculation right. Would it be something like:
0.5PI = 1.57 so as a 32 bit fixed point number it would be (in 16.16 precision), 65536 + (57 << 15) and then I would plug that into the sin approx function?

Share this post


Link to post
Share on other sites
serg3d    100
Actually SiCrane has no clue what he is talking about. Trigs and all other functions (with exception of *low* degree polynomial) are implemented through lookup tables in fixed point libraries. You can download nokia Symbian OS 3d game example from forum.nokia.com It includes trigs and atrigs implementation through lookup tables. Idea is simple - precalculate table of 256 points for 0 - PI/2 quadrant. After that downshift your value to 0-1024 range, get quadrant and get value from table. IF you need more precision get more points.

Share this post


Link to post
Share on other sites
swiftcoder    18426
Quote:
Original post by serg3d
Actually SiCrane has no clue what he is talking about. Trigs and all other functions (with exception of *low* degree polynomial) are implemented through lookup tables in fixed point libraries. You can download nokia Symbian OS 3d game example from forum.nokia.com It includes trigs and atrigs implementation through lookup tables. Idea is simple - precalculate table of 256 points for 0 - PI/2 quadrant. After that downshift your value to 0-1024 range, get quadrant and get value from table. IF you need more precision get more points.


The lookup table is merely an optimisation - how do you think you fill out those tables to begin with?

Share this post


Link to post
Share on other sites
Trenki    345
Using a lookup table for fixed point stuff is the way to go. It will also be faster than using the taylor expansion. To compute this lookup table you can simply use the standard math functions and convert the result to a fixed point library.

I have already developed a software renderer which uses fixed point math. You might want to check it out. On my homepage you will also find a small fixed point math library which contains functions for sin() and cos() in fixed point 16.16 format.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Trenki
To compute this lookup table you can simply use the standard math functions and convert the result to a fixed point library.

Which is great if you're on a platform which supports floating point. For the situation the OP is talking about, you need the Taylor expansion.

Share this post


Link to post
Share on other sites
serg3d    100
Quote:
Original post by Sneftel
Quote:
Original post by Trenki
To compute this lookup table you can simply use the standard math functions and convert the result to a fixed point library.

Which is great if you're on a platform which supports floating point. For the situation the OP is talking about, you need the Taylor expansion.


Did you actually do any non-trivial fixed point coding? Fought register overflow and rounding error? Do you have any idea how to calculate Sum x^i/i! for 16 or even 10 bit fixed point with [0., 1.]->[0->2^10] representation ? To actually do it you have to simulate floating point, including sum, multiplication and division operations. Just trying to do it easy way with multiplication-downshift will get you into world of hurt. More easy would be just drop complete 256 element hard coded array into code.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by serg3d
Did you actually do any non-trivial fixed point coding? Fought register overflow and rounding error?
For years and years, so drop the attitude.
Quote:
Do you have any idea how to calculate Sum x^i/i! for 16 or even 10 bit fixed point with [0., 1.]->[0->2^10] representation ? To actually do it you have to simulate floating point, including sum, multiplication and division operations.
Er, I suppose you could do it that way, but much more simple and efficient (and probably more accurate) is simply to do it in simulated 32-bit fixed point, interleaving the multiplications and divisions to keep the appropriate range.

Share this post


Link to post
Share on other sites
Trenki    345
Quote:
Original post by Sneftel
Quote:
Original post by Trenki
To compute this lookup table you can simply use the standard math functions and convert the result to a fixed point library.

Which is great if you're on a platform which supports floating point. For the situation the OP is talking about, you need the Taylor expansion.


Sneftel, you are wrong on this one. You really don't want to use the taylor expansion. You can precompute the lookup table on whatever computer you want and use it everywhere. You can even precompute the lookup table on hardware which does not support floating point in hardware. It would still work as the standard C library is required to support the float and double types and also the functions like sin, cos etc. Take the GP2X for example. You can use floats from C/C++ but then they will be emulated since the GP2X does not have native hardware support for floating point, but you can still use them, so it would also be possible to compute the lookup table at runtime, but normally you would compute it offline and store it in some source file.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Trenki
You can even precompute the lookup table on hardware which does not support floating point in hardware. It would still work as the standard C library is required to support the float and double types and also the functions like sin, cos etc.
Wouldn't that be nice. The GP2X may support floating point, but many other embedded systems don't, standards be damned. You're right, though, that there'd be little reason to compute at runtime if all you wanted were sin and cos (especially since most runtimes already have those tables laying around somewhere). As it turns out, however, for certain situations you need a heck of a lot more transcendental functions than those, and the space needed for the lookup tables really starts to add up.

Share this post


Link to post
Share on other sites
Trenki    345
Are you saying that on Consoles, PDAs, and Cell Phones there don't exist standard conformant C/C++ compilers? This seems a bit odd because it's not neccessarily the hardware but the compiler which has to support floats. If the hardware doesn't support floats natively the compiler has to make sure the correct software floating point functions get called. And for Cell Phones which support Java I think floats are a requirement to as otherwise they wouldn't be Java compliant.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Trenki
Are you saying that on Consoles, PDAs, and Cell Phones there don't exist standard conformant C/C++ compilers? This seems a bit odd because it's not neccessarily the hardware but the compiler which has to support floats.

That is exactly what I'm saying. [grin] As you said, for architectures that don't support floating point, compilers delegate to the runtime library; if they didn't do so, they'd have to insert emulation code for each operation site, sharply increasing the code size. And for whatever reason, some runtimes don't provide these operations. I can't speak to the why. (I also know at least one architecture-specific compiler which just does not support float or double, full stop.)
Quote:
And for Cell Phones which support Java I think floats are a requirement to as otherwise they wouldn't be Java compliant.
J2ME != J2SE. clicky

Share this post


Link to post
Share on other sites
johnl87    133
Alright, I tried a test program to see if the libraries were emulated. When I use the wireless toolkit from Sun, I get

cannot find symbol symbol : variable Double

I'm working with a Razr v3t so I guess there's no support in my situation. I'll just figure out how much precision I need and go from there. Thanks for the help.

Share this post


Link to post
Share on other sites
Daerax    1207
I thought this thread was about fixed points of some iterated trigonometric function. lol.

Quote:
Original post by Sneftel
As it turns out, however, for certain situations you need a heck of a lot more transcendental functions than those, and the space needed for the lookup tables really starts to add up.


Its mean of you to just leave us hanging like that :p. You should give at least one example.

Share this post


Link to post
Share on other sites
Sneftel    1788
It was a pseudo-physics-y thing we were doing a while back, with these shapes somewhat resembling metaballs. I don't recall the details, but we had these ugly complicated expressions for the shapes which didn't play nicely with the standard fixed-point sin/cos functions. The solution was to use lookup tables with the actual values for the entire formulae, but that would have been way too many lookup tables (this was in the day of sharply restricted JAR sizes). The solution we took was to derive the Maclaurin series of the equations, storing only the coefficients, and generate the lookup tables at runtime as necessary (only a couple of the equations were needed for a given level). I'm certain there was a cleverer, simpler way to do it, but this gave us good results and kept the download size under the cap.

Share this post


Link to post
Share on other sites
Daerax    1207
Ah ok. That make sense, due to my limited experience I would never have been able to imagine a scenario like that. One o those retrospective foresight things i suppose. thanks for clearing.

Share this post


Link to post
Share on other sites
outRider    852
Quote:
Original post by johnl87
Alright, I tried a test program to see if the libraries were emulated. When I use the wireless toolkit from Sun, I get

cannot find symbol symbol : variable Double

I'm working with a Razr v3t so I guess there's no support in my situation. I'll just figure out how much precision I need and go from there. Thanks for the help.


Generate your table on another machine with your favourite capable language and stick it in the source as an array maybe.

Share this post


Link to post
Share on other sites
frob    44903
Quote:
Original post by outRider
Generate your table on another machine with your favourite capable language and stick it in the source as an array maybe.

"Maybe" is the key word.

There are situations when you have space at runtime and can generate the tables quickly and easily when starting the app, but you don't have any bits to spare on your distributable. This was the case on more than one cartridge I've seen.

Yet another option I've seen used when both storage and RAM are sparse is an MRU cache. The parameter is rounded to the nearest x. A quick cache search can often find a result, and if necessary the new value is computed and added to the cache. A little performance tuning can find good values of x and a cache size that gives good results.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this