Fixed Point Implementation

Here's the place to get help and discuss features. The focus is on the C++ version, but generic questions are welcome.
kavaler
Posts: 67
Joined: Wed Jan 02, 2008 3:19 am

Fixed Point Implementation

Postby kavaler » Wed Mar 12, 2008 12:19 am

I'm starting this thread to move discussions of the fixed point implementation away from the patch thread. I did some more analysis and found that the main culprit in overflow is warm starting (disabled/enabled by the checkbox in the testbed). I don't know what warm starting is, I'm guessing it has to do with the initial conditions for some iterative solver. It seems to be important to keeping stacks of things together.

The other interesting thing is that the testbed overflows about 20 times before the first line of main is executed. I'm guessing these overflows are in object constructors that call multiply, but finding those is tough.

BTW, the code I'm using to track where overflow is occuring is in Fixed.h (works in LInux, I doubt it would work in Windows):

#if 0
// more acurate, using long long
inline Fixed Fixed::operator *(const Fixed a) const { return Fixed(RAW, (int)\
( ((long long)g * (long long)a.g ) >> BP)); }

#elif 1
#include <execinfo.h>
#include <signal.h>
#include <exception>

inline Fixed Fixed::operator *(const Fixed a) const {
long long x = ((long long)g * (long long)a.g );
if(x > 0x7fffffffffffLL || x < -0x7fffffffffffLL) {
printf("overflow");
void *array[2];
int nSize = backtrace(array, 2);
char **symbols = backtrace_symbols(array, nSize);
for(int i=0; i<nSize; i++) {
printf(" %s", symbols[i]);
}
printf("\n");
}
return Fixed(RAW, (int)(x>>BP));
}
#else

nimodo
Posts: 75
Joined: Sat Feb 09, 2008 4:00 pm

Re: Fixed Point Implementation

Postby nimodo » Thu Mar 13, 2008 8:43 am

I tried the TARGET_FLOAT32_IS_FIXED on windows 32bit, here some questions/remarks
warmstart and positioncorrection is off
- it seems, that it is not 100% working (overflow?)- see attached gif capture -, but anyway, thx for the good start
- ..\common\Fixed.h(420) : warning C4244: 'argument' : conversion from '__int64' to 'int', possible loss of data --- can this compiler warning be ignored ?
- why is the graphics working ? i'm still using the same freeglut library and render.cpp as for floating point
- is it correct to convert from FIXED to FLOAT with the following macro ?
#define FIXED2FLOAT(x) ((float)(x) / (float)(1 << 16))

- thx nimodo
Attachments
b2dtb.gif
Animated Testbed/Varying Friction gif
b2dtb.gif (116.15 KiB) Viewed 13919 times

kavaler
Posts: 67
Joined: Wed Jan 02, 2008 3:19 am

Re: Fixed Point Implementation

Postby kavaler » Thu Mar 13, 2008 6:16 pm

nimodo wrote:I tried the TARGET_FLOAT32_IS_FIXED on windows 32bit, here some questions/remarks
warmstart and positioncorrection is off


I do not have a windows machine. Does it work with warmstart and positioncorrection turned on? The is a an issue in the testbed where the frequencyHz is not set correctly because of typing issues. To fix this change line 309 of Main.cpp to:

float settingsHz = 60.0;
GLUI_Spinner* hertzSpinner =
glui->add_spinner("Hertz", GLUI_SPINNER_FLOAT, &settingsHz);
settings.hz = settingsHz;


nimodo wrote:- it seems, that it is not 100% working (overflow?)- see attached gif capture -, but anyway, thx for the good start


If this is the testbed demo then it works perfectly on my machine (linux/gnu). I don't know what is going on for you, it might be something about your compiler? Did you try the gnu compiler?

nimodo wrote:- ..\common\Fixed.h(420) : warning C4244: 'argument' : conversion from '__int64' to 'int', possible loss of data --- can this compiler warning be ignored ?


If you are getting lots of these I would say that they can be ignored. If you are getting just one then maybe it means something. I did find a problem with the initialization of angularvelocitysquared in b2Settings.h.

nimodo wrote:- why is the graphics working ? i'm still using the same freeglut library and render.cpp as for floating point


The floating point stuff in box2d is defined as float32, which when using the fixed point implementation is defined as "Fixed". C++ will automatically convert from and to various types. So if you define float x = y, where y is type Fixed, the conversion from Fixed to float is done implicitly.

nimodo wrote:- is it correct to convert from FIXED to FLOAT with the following macro ?
#define FIXED2FLOAT(x) ((float)(x) / (float)(1 << 16))


See above. You can do the conversion by just using float(x).

Mollusk
Posts: 8
Joined: Thu Mar 13, 2008 11:56 pm

Re: Fixed Point Implementation

Postby Mollusk » Fri Mar 14, 2008 12:07 am

Hi !

Great work on the Fixed point version ! I'm currently doing a quick app on PocketPC, and it runs decently with the floating point version, but obviously I have major slowdowns when too many things enter the screen, so I'll have to move on to the fixed point version of Box2D...

The main issue I have is that I get a completely inappropriate behaviour, even with a simple scene : 1 ground box, 1 box falling on it. When it hits the ground, it starts moving left very slowing and turns right by a very little angle... Looks like an overflow (or something like that) problem, not sure why though (I'm using the version from the SVN). I don't have this when using floats.

Is there anything I'm supposed to change/adjust in my code ? The world area has limits of like -4 to +6, I kept it small (and I then convert the position to fit the PocketPC screen).

I'll post a video of this later on today, I don't have access to my code from this PC.

Thanks for the hard work !
Mollusk

kavaler
Posts: 67
Joined: Wed Jan 02, 2008 3:19 am

Re: Fixed Point Implementation

Postby kavaler » Fri Mar 14, 2008 1:54 am

I have a new patch for the fixed point implementation that uses a different approach to solving overflow issues. What I am doing now is representing forces in a different scale than other variables. Then I reorder some of the multiplications by the scaling factor to prevent overflows. Basically I set the scale factor to 128.0, which is similar to the size of dt, so that SCALE*dt is approximately 1.0. For the floating point implementation all of the scale factors are set to 1.0, so they should optimize out of any reasonable compiler not effecting the mathematical or computational results

Using this approach, I patched the b2ContactSolver, mouse joint and revolute joints so far. The results look very good in that I don't see any overflows for testbed cases that just use those features like car, biped, pyramid, and a bunch of others. Also warm starting works well and doesn't overflow for these joints. If this approach is acceptable, then I will try to modify the rest of the joint types in the same way.

One drawback of this approach that must be decided is how to handle external referencesto force. Currently I assume that such references are in unscaled (nominal) units. This causes problems in, for example, the testbed where the car example uses a max force on the mouse of 70,000, which already is too big to represent in Fixed. Same goes for the reaction forces. The exception to this rule are the cpp->tangent and cpp->normal forces that are scaled values. Since these might be used by external programs some care must be taken to clean up this interface.

I also patched the Makefiles so that they should now make properly, and they also make all of the .h dependencies (useful when playing with box2d internals), and fixed the Hz settings in the testbed to work with Fixed.
Attachments
box2d_fixed_r131.patch.zip
(4.7 KiB) Downloaded 479 times

Mollusk
Posts: 8
Joined: Thu Mar 13, 2008 11:56 pm

Re: Fixed Point Implementation

Postby Mollusk » Fri Mar 14, 2008 6:33 am

Thanks, I'll see how to apply the patch and give you feedback :) I haven't checked out box2D code yet, but having played a lot with fixed point math in the past I have thought about it. I'm not sure how much can be done by patching versus doing a real fork :/ (the problem with a fork being that you kind of lose potential updates, or they'll require much more work).

Anyways, I hope we can get fixed point in Box2D, it would be awesome for all portable systems !

nimodo
Posts: 75
Joined: Sat Feb 09, 2008 4:00 pm

Re: Fixed Point Implementation

Postby nimodo » Fri Mar 14, 2008 7:10 am

kavaler wrote:I have a new patch...

Thanx for the answers
Regarding your first answers
- regarding warmstarting - below is capture, what happens on my win32 (desktop) version
(i applied your recent patch)
-positioncorrection has so far no (visual) effect in the varying friction example
-about the Hz problem: i do not use glui, only freeglut/glutes due compatibility to windows mobile platform
- i'm actually using the Microsoft Visual C++ 2005 compiler, maybe i'll try the gcc.
(probably mollusk used the gcc, it seems he has the same problems ?)
- regarding int64 compiler warnings: yes, i have a lot of, i think you are right, that should not be the problem
- thx for the float conversion hint ! it works.

i'll continue trying with compiler options
regards - nimodo
Attachments
box2d_demo_warmstart.gif
TestBed/Varying friction with warmstarting
box2d_demo_warmstart.gif (48.49 KiB) Viewed 13747 times

kavaler
Posts: 67
Joined: Wed Jan 02, 2008 3:19 am

Re: Fixed Point Implementation

Postby kavaler » Sat Mar 15, 2008 1:05 am

I have yet another patch. This one fixes almost all of the overflow problems in all the joint types and in the contact solver. I did something slightly different than previously which should have no effect on the floating point code. You can check out the gear, pulley, web and other demos to see how stable they are now.

You can change the scaling used by the package by changing the macros B2FORCE_SCALE and related macros. There is a different version in the contact solver that scales things slightly differently. You might have to adjust these values if you exceed the general parameters of the testbed.

A few notes about things that still have issues:
1. Forces are currently represented externally with limits of +-32767. The mouse joint is sometimes called with a bigger value than this. I changed the testbed code to limit to 16000.0 (just to make sure things don't overflow) in the Fixed code. The getreactionforce calls will probably return overflowed values too.
2. The pyramid does not change to blue unless you up the number of iterations and/or decrease the frame rate. I am looking into what is going on there but it might be difficult to fix this problem.
3. The edit shape demo doesn't work quite right because the mass of the square is too large and overflow occurs when the mouse joint moves the square. Fixing the scaling to deal with large masses is possible.
4. The performance of things like stacking and the pyramid are different in the fixed versus the floating code, but both seem to do reasonable things. Setting the various flags will change their behavior sometimed to something better, sometimes to something worse.

Regarding the two gif's in previous messages that show some very bad behavior, this doesn't happen in the testbed on my system regardless of the various settings (warm start, position correction or TOI). I use an Intel/Linux box with gcc 4.1.2. Perhaps you could post the code so that I could see what it does on my machine.
Attachments
box2d_fixed_r131_2.patch.zip
(6.62 KiB) Downloaded 488 times

Mollusk
Posts: 8
Joined: Thu Mar 13, 2008 11:56 pm

Re: Fixed Point Implementation

Postby Mollusk » Sat Mar 15, 2008 1:30 am

With the latest patch vs latest SVN version, I get a compilation error :

Code: Select all

b2Island.o:b2Island.cpp:(.text+0x99c): undefined reference to `b2ContactSolver::SolvePositionConstraints(Fixed)'
b2Island.o:b2Island.cpp:(.text+0x1420): undefined reference to `b2ContactSolver::SolvePositionConstraints(Fixed)'


Not sure why, but apparently I only have the float version of that function. Was this patch supposed to be applied on the latest SVN version or on another one ?

edit : added #include "../Common/b2Settings.h" and it seems to take it well now...

kavaler
Posts: 67
Joined: Wed Jan 02, 2008 3:19 am

Re: Fixed Point Implementation

Postby kavaler » Sat Mar 15, 2008 2:47 am

The last patch was against rev 131 in SVN. You don't seem to be linking in b2ContactSolver.o? The method seems to be defined correctly:

bool b2ContactSolver::SolvePositionConstraints(float32 baumgarte)

Perhaps the version of b2ContactSolver.o that you linking with did not have TARGET_FLOAT32_IS_FIXED #defined.


Return to “General Discussion”



Who is online

Users browsing this forum: Google [Bot] and 1 guest