#162152 - thesean - Tue Aug 26, 2008 11:46 pm
So I've read several tutorials and just about every other type of information I can find for fixed point, but I still have some trouble visualizing some concepts with using it in my program.
Most information out there describes what fixed point is, why using it can be beneficial, and how to perform operations like multiplying, dividing, etc etc. What I'm still wondering is how to actually make use of fixed point.
My situation is that I have a game that uses float data types to control various aspects such as the player's global position, his velocity, things like that.
For screen position, I take the global position mod screen_width, so for x it would be something like: screen_pos.x = player_pos.x % 256
What I'm having trouble with is how I would do this using fixed point. Do I just do the same operations basically, but multiply everything by a scale factor? For example, when the user presses the "jump" key, I give the player a y velocity of -7.5, this effectively moves the player 7.5 units up on the next update (that is if there are no other forces such as gravity). If I change this to fixed point, would I just try something like: player_velocity.y = -75 << 16;
and then multiply that number by another fixed point number to get it to screen coordinates?
I hope this makes sense, what I'm getting at is that I believe I understand the concept behind and how to implement fixed point into my code, but I don't quite understand how to apply it for my needs.
Any help greatly appreciated!
#162158 - DiscoStew - Wed Aug 27, 2008 1:56 am
A fixed-point value acts like a lower-precision float value, imo. However, there is more to using it than floats from the user perspective.
With fixed-point, you need to know what format you are using, and what format the values represent. A format like 1:19:12 is widely used. If you don't know what these numbers represent, then you better hit the books again.
When converting to fixed-point from float, you left-shift the value by however many decimal bits you plan to use. To convert back, you right-shift by that many.
(float) << 12 = fixed-point with 12 decimal bits (:12)
(:12) >> 12 = float value
**Make sure to cast the fixed-point value to float prior to shifting to retain the decimal.**
Addition and subtraction require that the format for each side of the operator be the same in order for the result to be correct, in that it's format is the same as the 2 values used.
(1:19:12) + (1:19:12) = (1:19:12)
Multiplication and division require that you know the formats being used to know what the resulting format should be. They don't have to be the same format, but we won't get into that. When multiplying 2 values of the same format, the result ends up as such...
(:12) * (:12) = (:24)
The reason behind this is because unlike multiplying 2 numbers by a base value of 1 (1 * 1 = 1), you are multiplying by the base decimal value representing 1, where in the case of 12 decimal bits would be 4096, and what is multiplying that base value result in?
4096 * 4096 = 16777216 != 4096
So where did this number come from? It's the 24 bit decimal value representation of 1 in :24 fixed point (1 << 24).
How do you correct this? It's simple. You can correct this by shifting the resulting value by the number of decimal bits the other 2 values use.
(4096 * 4096) >> 12 = 4096
(x * y) >> 12 = z
For division, you in a sense go the other direction. Let's use this last line as an example, and using fundamental knowledge of algebra to break down the line, and turn it into a division function.
(x * y) >> 12 = z
z = (x * y) >> 12
(z << 12) = (x * y)
(z << 12) / y = x
--or--
(z << 12) / x = y
That is just for those kinds of operators. For other things, like 'mod', you need to understand what your fixed-point value's " decimal equivalent to 1" value is, like for :12, which is 4096.
Hope that helps. I'm terrible at explaining things.
_________________
DS - It's all about DiscoStew
#162176 - Cearn - Wed Aug 27, 2008 10:15 am
First and foremost, fixed-point numbers are still normal integers; they're just used in a special way. Contrary to what certain notations would have you believe, there's no separate sign-bit; it's just plain ol' twos-complement ints.
Working in fixed point is close to working conversion factors in the metric system. The 'normal' integer form corresponds to the standard unit (say, metre (m)), with a fixed-point value would be a smaller unit, like millimetre (mm). The conversion in this case would be a scaling of 1000. Just like you can't really add a quantity in cm to one in mm, you need to convert one so that both use the same units before you can add them. Similar conversion problems exist for multiplication and division.
The screen position is in metres, but for measurements in the game-world you'd use the position would use centimetres or millimetres for greater above-decimal accuracy. You do all the calculations in those units and then convert to the screen-units when the time is right.
Note that all the variables that would benefit from fixed-point actually do have units attached, but they're usually ignored because it's assumed you know what's what instinctively. Errors when dealing with fixed-point often comes from this issue. That and using unsigned integers, rather than signed ones.
| thesean wrote: |
What I'm having trouble with is how I would do this using fixed point. Do I just do the same operations basically, but multiply everything by a scale factor? For example, when the user presses the "jump" key, I give the player a y velocity of -7.5, this effectively moves the player 7.5 units up on the next update (that is if there are no other forces such as gravity). If I change this to fixed point, would I just try something like: player_velocity.y = -75 << 16;
and then multiply that number by another fixed point number to get it to screen coordinates? |
That's basically correct, but because the scaling factors use hexadecimal, scaling the decimal values won't work. 7.5 = 7+½, which would convert to (7+½)*16 = 0x78, not 75. or you can use some macros to do the float-fixed conversions. nds/arm9/math.h already has a few of these for 20:12 fixed-point values.
#162182 - sgeos - Wed Aug 27, 2008 4:33 pm
| Cearn wrote: |
| or you can use some macros to do the float-fixed conversions. nds/arm9/math.h already has a few of these for 20:12 fixed-point values. |
You could use macros like these for general float->fixed->int conversions:
| Code: |
// v = value
// f = fractional bits
#define FLOAT2FIXED(v,f) ((int)((v)*(1<<(f))))
#define FIXED2INT(v,f) ((v)>>(f)) |
I was not in a position to test those macros, so they are probably broken.
-Brendan
#162221 - thesean - Thu Aug 28, 2008 5:40 am
Wow thanks for all the help everyone!
So I think the MAJOR thing that I was missing (and probably the source of all my confusion) was that it's okay to declare float types in the program, but not do math on them. What I should do is if I have a float that I want to perform some math on, convert it to fixed point, do the math, then convert it back?
Or maybe I should just convert it to fixed and do the math, and then scale that value instead of converting it back to float?
Thanks for the macros Brendan, I may try them but I'm more inclined to use the ones in math.h, I've checked those ones out before too.
#162222 - TwentySeven - Thu Aug 28, 2008 5:53 am
Anything you do with floats will be emulated, and therefore slow. This includes reading it from a variable and converting it to an int.
So typically, if I have something that needs floating point, I prototype it out using floats, and then convert it carefully into fixed point, after its working - it's an optimization and treated as one :)
#162224 - thesean - Thu Aug 28, 2008 7:42 am
| TwentySeven wrote: |
| Anything you do with floats will be emulated, and therefore slow. This includes reading it from a variable and converting it to an int. |
I know the DS has no FPU and thus all operations on floats are emulated, but are you sure that even reading them is emulated as well? If that's true, then I'm afraid I have to say I'm confused again... then that means it is always bad to use floating point types at all?
#162227 - DiscoStew - Thu Aug 28, 2008 8:26 am
| thesean wrote: |
| TwentySeven wrote: | | Anything you do with floats will be emulated, and therefore slow. This includes reading it from a variable and converting it to an int. |
I know the DS has no FPU and thus all operations on floats are emulated, but are you sure that even reading them is emulated as well? If that's true, then I'm afraid I have to say I'm confused again... then that means it is always bad to use floating point types at all? |
This is just my guess, but floats are structured differently from your average type like int and short, and therefore require interpretation for conversion from that type to another. Because of no FPU, that interpretation is emulated.
_________________
DS - It's all about DiscoStew
#162241 - Miked0801 - Thu Aug 28, 2008 4:54 pm
As long as you place your decimal numbers within a Fixed declaration, the compiler will handle the conversion for you without the nasty lib overhead.
#162245 - sgeos - Thu Aug 28, 2008 5:10 pm
FWIW, my macros are probably broken. I didn't test them so I probably botched something somewhere with all the ().
| Miked0801 wrote: |
| As long as you place your decimal numbers within a Fixed declaration, the compiler will handle the conversion for you without the nasty lib overhead. |
By this, I assume you mean something like this will avoid lib overhead:
| Code: |
| FIXED pi = FLOAT2FIXED(3.14159, 12); |
While this will not:
| Code: |
float rawUserValue;
FIXED userValue;
// ...
rawUserValue = getUserValue();
userValue = FLOAT2FIXED(rawUserValue,8); |
-Brendan
#162274 - sgeos - Fri Aug 29, 2008 7:27 am
These are the macros you want:
| Code: |
// v = value
// f = fractional bits
#define FLOAT2FIXED(v,f) ((int)((v)*(1<<(f))))
#define FIXED2FLOAT(v,f) ((float)(v)/(1<<(f)))
#define FIXED2INT(v,f) ((v)>>(f)) |
This is the output of my testing program.
It may give you some insight into how fixed point numbers work.
If you look at the hex, notice how the 3 shifts to the left when the fractional component is a multiple of 4:
| Code: |
--- Diagnostic Information ---
sizeof( 0x7FFFFFFF ) * 8 == 32 == 0x00000020
FLOAT2FIXED( 0x7FFFFFFF, 0) == 2147483647 == 0x7FFFFFFF
--- Fixed Point Pi ---
FLOAT2FIXED( 3.14159, 0) == 3 == 0x00000003
FLOAT2FIXED( 3.14159, 8) == 804 == 0x00000324
FLOAT2FIXED( 3.14159,12) == 12867 == 0x00003243
FLOAT2FIXED( 3.14159,21) == 6588391 == 0x006487E7
--- Fixed To Int (Should be 3) ---
FIXED2INT(0x00000003, 0) == 3 == 0x00000003
FIXED2INT(0x00000324, 8) == 3 == 0x00000003
FIXED2INT(0x00003243,12) == 3 == 0x00000003
FIXED2INT(0x006487E7,21) == 3 == 0x00000003
--- Fixed To Float (Should be close to Pi) ---
FIXED2FLOAT(0x00000003, 0) == 3.00000000
FIXED2FLOAT(0x00000324, 8) == 3.14062500
FIXED2FLOAT(0x00003243,12) == 3.14135742
FIXED2FLOAT(0x006487E7,21) == 3.14158964 |
Here is the source, if you care to play around with it:
| Code: |
#include <stdio.h>
#define MES(m) printf("\n--- %s ---\n", #m)
#define PRINT_VALUE_INT(v) printf("%s\t== %10d\t== 0x%08X\n", \
(#v), ((int)v), ((int)v))
#define PRINT_VALUE_FLOAT(v) printf("%s\t== %10.8f\n", (#v), ((float)v))
// v = value
// f = fractional bits
#define FLOAT2FIXED(v,f) ((int)((v)*(1<<(f))))
#define FIXED2FLOAT(v,f) ((float)(v)/(1<<(f)))
#define FIXED2INT(v,f) ((v)>>(f))
int main(void)
{
MES( Diagnostic Information );
PRINT_VALUE_INT( sizeof( 0x7FFFFFFF ) * 8 );
PRINT_VALUE_INT( FLOAT2FIXED( 0x7FFFFFFF, 0) );
MES( Fixed Point Pi );
PRINT_VALUE_INT( FLOAT2FIXED( 3.14159, 0) );
PRINT_VALUE_INT( FLOAT2FIXED( 3.14159, 8) );
PRINT_VALUE_INT( FLOAT2FIXED( 3.14159,12) );
PRINT_VALUE_INT( FLOAT2FIXED( 3.14159,21) );
MES( Fixed To Int (Should be 3) );
PRINT_VALUE_INT( FIXED2INT(0x00000003, 0) );
PRINT_VALUE_INT( FIXED2INT(0x00000324, 8) );
PRINT_VALUE_INT( FIXED2INT(0x00003243,12) );
PRINT_VALUE_INT( FIXED2INT(0x006487E7,21) );
MES( Fixed To Float (Should be close to Pi) );
PRINT_VALUE_FLOAT( FIXED2FLOAT(0x00000003, 0) );
PRINT_VALUE_FLOAT( FIXED2FLOAT(0x00000324, 8) );
PRINT_VALUE_FLOAT( FIXED2FLOAT(0x00003243,12) );
PRINT_VALUE_FLOAT( FIXED2FLOAT(0x006487E7,21) );
return 0;
} |
-Brendan
#162303 - thesean - Sat Aug 30, 2008 7:37 pm
Thanks a lot for that code, that's very helpful. I think I'll use some of that to make a small fixed class, I'll post it up when I finish it.
Thanks again everyone.