Skip to main content
gamedev.net
🔒 Locked

Fixed point math in c#?

Started by x4000 Mar 2, 2009 at 10:03 PM 7 replies 9k views
Original Post
x4000
x4000
Hi there, I was wondering if anyone here knows of any good resources for fixed point math in c#? I've seen things like this (http://2ddev.72dpiarmy.com/viewtopic.php?id=156), and a number of discussions about whether decimal is really fixed point or actually floating point, but I haven't seen a solid library for things like calculating cosine and sine. My needs are simple -- I need the basic operators, plus cosine, sine, arctan, PI... I think that's about it. Maybe sqrt. I'm programming a 2D RTS game, which I have largely working, but the unit movement when using floating-point math (doubles) has small inaccuracies across multiple machines, leading to desyncs. I was aware from this as a possible issue from the outset, and so have limited my use of non-integer position math as much as possible, but for smooth diagonal movement at varying speeds I'm calculating the angle between points in radians, then getting the x and y components of movement with sin and cos. That's the main issue. I'm also doing some calculations for line segment intersections, line-circle intersections, circle-rect intersections, etc, that also probably need to move from floating-point to fixed-point to avoid cross-machine issues. If there's something open source in Java or VB or another comparable language, I could probably convert the code for my uses. The main priority for me is accuracy, although I'd like as little speed loss over present performance as possible. This whole fixed point math thing is very new to me, and I'm surprised by how little practical information on it there is on google -- most stuff seems to be either theory or dense C++ header files. Anything you could do to point me in the right direction is much appreciated; if I can get this working, I plan to open-source the math functions I put together so that there will be a resource for other C# programmers out there.
phresnel
phresnel
Have a look at this thread, and also this article by Tom Forsyth. Maybe it helps you.

If not, I personally would use many lookup tables for sine/cosine/square root in a real time setting (you can generate them using floating point math). Those functions can be too slow for you if not hardware accelerated.

edit: Because I was snoopy myself, this should answer your question whether it is a float or not:
Quote:
MSDN
A decimal number is a floating-point value that consists of a sign, a numeric value where each digit in the value ranges from 0 to 9, and a scaling factor that indicates the position of a floating decimal point that separates the integral and fractional parts of the numeric value.
Bob Janova
Bob Janova
What do you actually need the trig functions and square roots for? Any implementation of them in fixed point is going to be slow, so try to use as few as possible. (Vector normalisation and finding distances require a square root, although you can do a lot of tests against the square of both sides.)

Quote:
or smooth diagonal movement at varying speeds I'm calculating the angle between points in radians, then getting the x and y components of movement with sin and cos. That's the main issue

Why are you doing it this way? Given points p1 and p2 and a unit speed s, you have a direction vector of norm(p2-p1), and a speed of s norm(p2-p1). That involves a square root (in the norm) but no trig functions.
x4000
x4000
Quote:
Original post by Bob Janova
What do you actually need the trig functions and square roots for? Any implementation of them in fixed point is going to be slow, so try to use as few as possible.


I'm definitely using as few as I can. Here's the current list of what I need and why:
-Atan2 to find the angle between two points.
-cos/sin to find the x/y components of the angle/distance combinations.
-sqrt for finding the distance between two points and as part of a line/circle intersection test.

That's actually it, it turns out -- less than I was thinking.

Quote:
Original post by Bob Janova Given points p1 and p2 and a unit speed s, you have a direction vector of norm(p2-p1), and a speed of s norm(p2-p1). That involves a square root (in the norm) but no trig functions.


Hmm, I'm not using vectors (don't really have a reason to so far), just point math. Can you elaborate on the norm(p1-p2) approach? The main reason I'm using my current approach is that I need both the angle and the actual location to move to. The angle determines the angle that the sprite is drawn at, the location determines where it goes. So using my current approach, I get both as a byproduct of the same operation chain.

Depending on the efficiency of cos/sin versus sqrt, it might make more sense to use your approach (which I don't quite follow as yet), and then calculate the angle separately. Unless there's some way to determine the angle between two points as a byproduct of part of your calculation? If I could do that, I'd have no need for any trig functions, just sqrt. I already have the fixed point math working otherwise, so that would be all I'd need in general, apparently.

Thanks for your thoughts!

Bob Janova
Bob Janova
I think to get an angle you will always need to use an arc-tangent (or another inverse trig function). You only need to do it once though (for a straight line).

Norm is simply a vector function which normalises a vector, i.e. sets its length to 1. Here is one of mine:
public Vector3 Normalise(){ double f = w/Mag; return new Vector3(x*f,y*f,z*f); }
It requires a square root to calculate the magnitude (you know Pythagoras I assume :D).

So what you do is, take the difference in position between the two points, and normalise that, giving you a vector which points along the line (from point 1 to 2, if you did p2-p1) and is of length 1. (I.e., for points [0,0] and [2,1], (p2-p1) is [2,1] and the direction vector is [2,1]÷√5, or [0.894, 0.447]). You can then use this for movement simply by multiplying by the speed – e.g. for a unit of speed 10, the movement each step would be [8.94, 4.47].

To find the angle, you still need to do atan2(1, 2). For graphical purposes you can use a lookup table I guess. But you only need to do it once per direction change.
x4000
x4000
Quote:
Original post by phresnel
Have a look at this thread, and also this article by Tom Forsyth. Maybe it helps you.

If not, I personally would use many lookup tables for sine/cosine/square root in a real time setting (you can generate them using floating point math). Those functions can be too slow for you if not hardware accelerated.


Hey, thanks for the response. Good to have it cleared up about the decimal data type. Very interesting links you posted, took me a while to go all through them. I think that for sin/cos I will almost certainly start using lookup tables. My need for precision is fairly limited, so the lookup table doesn't even have to be too terribly large.

Thinking about Sqrt, though, I don't think that approach would work because of the vast number of possible ranges I need to calculate this for -- between 1 and about 64000^2 (integers only, but still). So that doesn't seem like that part would work. I found some interesting algorithms such as this one: http://www.mathpath.org/Algor/squareroot/algor.square.root.htm

To quote from them:

Quote:

Square roots by Divide-and-Average
This method dating back to the Babylonians (1700 B.C.) is known as the Babylonian Algorithm.
If A > 0 is a guess of the square root of the positive number Q, then a better approximation to √Q is given by
B = (A + Q/A)/2.
Now you use B as an approximation and compute C = (B + Q/B)/2, and so on to get as close as you want to the value of √Q. We have shown elsewhere why the Babylonian Algorithm works.

Example:
Let us find the square root of 5. Let A = 2.
Then B = (2 + 5/2)/2 = 2.25
C = (B + Q/B)/2 = (2.25 + 5/2.25)/2 = (2.25 + 2.22)/2 = 2.235
Notice that this value is getting closer with each iteration to the actual value 2.2360679..


So if I want the Sqrt of a number, I'd start my guess A as being that number / 2, perhaps? Then with a few iterations -- 3 maybe, I'm not sure, would have to try it out -- I'd arrive at a reasonably-correct result. It wouldn't be a super-precise result, but I don't know that I'd need it to be. But, at least with this approach I'd know that it would provide consistent results on any machine. The question would be if it could still run 40,000+ Sqrts per second, as I seem to currently be able to...
x4000
x4000
Quote:
Original post by Bob Janova
I think to get an angle you will always need to use an arc-tangent (or another inverse trig function). You only need to do it once though (for a straight line).

Norm is simply a vector function which normalises a vector, i.e. sets its length to 1. Here is one of mine:
public Vector3 Normalise(){ double f = w/Mag; return new Vector3(x*f,y*f,z*f); }
It requires a square root to calculate the magnitude (you know Pythagoras I assume :D).

So what you do is, take the difference in position between the two points, and normalise that, giving you a vector which points along the line (from point 1 to 2, if you did p2-p1) and is of length 1. (I.e., for points [0,0] and [2,1], (p2-p1) is [2,1] and the direction vector is [2,1]÷√5, or [0.894, 0.447]). You can then use this for movement simply by multiplying by the speed – e.g. for a unit of speed 10, the movement each step would be [8.94, 4.47].

To find the angle, you still need to do atan2(1, 2). For graphical purposes you can use a lookup table I guess. But you only need to do it once per direction change.


I think this approach makes sense, but I'm not sure if I'm feeling that it's that much more efficient than my current way. I'm still not sure where the divisor w comes from (and no I don't know Pythagoras, but I love his theorem :D). Part of my issues is that this is an integer coordinate space, so I can't actually track partial movements without rounding.

Having it continually recalculate the amount to move, based on the slightly-changing angles between the two points, does a LOT for self correct in this sort of situation, where otherwise you get all sorts of drift problems over long distances (which these are). I think your way might be slightly more efficient than what I'm doing now, but I'm not sure it's enough so to warrant taking out the inherent self-correction I already have.... I'm still noodling on all this, though, so I might change my mind in the end, you never know.
Bob Janova
Bob Janova
Oh, my mistake for not checking ... that w is a scale factor I apply in a lazy 3D projection, it should be a 1 for a simple (x,y,z) vector.

Quote:
Part of my issues is that this is an integer coordinate space, so I can't actually track partial movements without rounding.

Track it in 1/100th of a pixel (or 1/1000, or 1/256, or whatever is suitable). In general the smallest unit in a fixed-point world should be small enough that rounding doesn't matter in any real situation.
x4000
x4000
Ok, thanks for all the help to everyone in this thread. Some very useful information here, and that helped lead me to my ultimate solution, most of which is based on the MathFP liberal source software java code by Dr. Onno Hommes. Here's a link to my full solution, in case anyone else wants it:
http://stackoverflow.com/questions/605124/fixed-point-math-in-c/616015#616015

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.