Wednesday, 26 September 2007

Java Fixed Point Maths

One of the first things I wrote when I started J2ME was a set of fixed point maths routines. I've seen quite a few others over the years, for Java and other languages, and they all seemed to follow the same pattern: sin and cos tables, plus a few methods for basic operations (multiply and divide, usually). The one I offer here, which in various guises and languages has served me well since forever, is a little more advanced (not much, but enough for most mobile games and applications).

The sin and cos (and by extension tan) routines are still table based, but instead of providing the table in-line with the code, it's generated using recursive synthesis at runtime. The advantage here is that the class can be quickly tailored for less or more fixed point precision, depending on the use (16.16 for general usage, 12.20 for audio work, etc.). There's also a fast atan, which was most useful for the physics and AI in Jet Set Racing (seen here, and Opposite Lock, seen here), plus a few other bits and bobs.

Most of the algorithms I devised myself, unless otherwise noted in the comments. The precision is pretty good (I have a test suite for it somewhere) but don't go taking my word for it, find out for yourself!


Sergey said...

It would be nice If you clarify the license. The preferable licenses are Public Domain and BSD considering the size of the code.

Otherwise the code can only be used as reference which probably was not your intention :)

Carl Woffenden said...

Hi! My intention with anything on my blog, unless specifically stated, is that it's all under a permissive licence with attribution. That's all a little vague, I realise, so let's say that it's BSD.


Cyber Axe said...
This comment has been removed by the author.
Carl Woffenden said...

Hi! It's in there, it's the two parameter atan call.

Cyber Axe said...

Thanks, I'd figured that was the case (hence why I deleted my comment after asking),

I've been unable to get the correct angle since converting from doubles to fixed point using that atan function and I'm pretty confident that's where the problem lies as everything else seems to work fine from testing.

Carl Woffenden said...

Send me a quick example of where it's going wrong and I'll take a look. One thing that may be happening is overflow in the fixed point calculations (for example, in 16:16 fixed point 256 * 128 will overflow).

Cyber Axe said...

final Viewport viewport = player.getViewport();

final int playerX = player.getX();
final int playerY = player.getY();

// Calculate the Direction to fire in.
final int fDirectionX = Fixed.intToFixed(player.getPlayerMovement().pointerX() - (playerX - viewport.getCamX()));
final int fDirectionY = Fixed.intToFixed(player.getPlayerMovement().pointerY() - (playerY - viewport.getCamY()));

final int fAngle = Fixed.atan(fDirectionX, fDirectionY);

fAngle is then used to fire a bullet in that direction, but I'm only getting a small cone left and right regardless, it's very possibly an overflow issue as you suggest.

Also tried it with fDirection variables being non fixed point numbers.


Carl Woffenden said...

What are typical values for fDirectionX and fDirectionY?

Cyber Axe said...

typically in the range of -512 to 512 before fixed point converstion

Cyber Axe said...

Doesn't seem to matter how big or small the fDirectionX and fDirectionY variables are, the results are the same.

Seems to be something to do with the following code:

n = n + (1 << (ATAN_SHIFT - 1)) >> ATAN_SHIFT;

as when I comment that out, the bullets fire at more or less the angle they should be with the exception of a cone at the top and bottom.

Carl Woffenden said...

I took a look at atan (and the other trig functions) and I didn''t see anything wrong. For example, given an angle of 22.5 degrees, so 16 in the brads used here, I can do:


Which gives me 27146 fixed (0.414 as a float). I then try:


That gives me 16 as expected. Next, for a length of 100 and an angle of 22.5 degrees, I used this:

System.out.println(atan(div(mul(sin(16), intToFixed(100)), mul(cos(16), intToFixed(100)))));

The result is 16 (or 22.5 degrees).

Try with a few more values and it should be (reasonably) correct. The only thing I can think of is that you have some regular integer multiplies and divides in there, instead of the fixed point mul() and div()?

Cyber Axe said...

Sorry for the delay in replying,

I don't use any non Fixed operations on them (octupally checked)

Been playing around with it again recently and I've determined that the problem is my attempt to use the result of Fixed.atan directly as data for a Fixed.sin or Fixed.cos to use for my vector.

my vector class works fine if I manually feed a ++i for example to plot circular motion

I've tried converting the result with the following

Fixed.atan(x, y) * 256 / 360 (both Fixed and Non Fixed to test)

All I'm doing is taking the result of Fixed.atan and then putting it into the Fixed.cos and Fixed.sin (though obviously I'm missing something)

This type of math is relatively new to me still as you can probably tell.

How fAngle is used:

// Distance Travelled
int fLength = Fixed.intToFixed(2);

// Source Cartesian Co-ords
int fX = Fixed.intToFixed(50); // Source X to plot New X
int fY = Fixed.intToFixed(50); // Source Y to plot New Y

int fSin = Fixed.sin(fAngle);
int fCos = Fixed.cos(fAngle);

// New X and Y Co-ordinates
int nX = Fixed.FixedtoInt(Fixed.mul(fX + fLength, fSin) + Fixed.HALF); // Fixed.Half is equal to half of Fixed.ONE, using it to round
int nY = Fixed.FixedtoInt(Fixed.mul(fY + fLength, fCos) + Fixed.HALF); // Fixed.Half is equal to half of Fixed.ONE, using it to round

Sorry for being such a bother!

Cyber Axe said...

... just tried the tan(16) it returned 0 (should have done that earlier)

and i got -63 for atan(27146)

So i must have accidentally changed something, I will go compare with original code


Cyber Axe said...

I managed to fix it, apparently I changed something in the sine table generation and that messed up the atan.

And apparently I did some stupid hack to the division function in my early days to get around the fact that I couldn't get it working with non Fixed points (I have no idea what the hell I was thinking at the time) which is what messed up the tan

but still worked with most division formula some how which is why I didn't notice it till I compared with original source

Sorry for being such an Idiot!