Box2D Forums

The fixed point implement should have a minor impact on the floating point code. It should not effect the mathematics of the physics at all (that is, you should get exactly the same values, with and without the patch, when the code is compiled using floating point).

The biggest difference is that FLT_EPSILON and FLT_MAX.., which are defined in a standard library, must be changed to FLOAT32_EPSILON, etc. and then #define to equal FLT_EPSILON, ... In addition, in order to reduce the number of ifdefs in the main code the floating point routines like sqrtf, tanf, etc. have been "renamed" using inline functions. Probably 1/2 of the patch deals with these sort of issues. As long as one uses these new definitions/functions instead of the old ones, keeping the float in line with the fixed should be easy.

There are seven places in the code (cpp files) where ifdefs are used do something different between fixed and floating point (mostly using different constants or computing something in a way that retains resolution or prevent overflow). There are two header files that have a total of 6 ifdefs related to fixed point. So that makes a total of 13 places in the codebase that are "fixed point special cases." My guess is that to improve the performance further only a few more will need to be added.

Otherwise, all of the fixed point stuff is included in one file (Fixed.h) and the DS stuff is included in both Fixed.h and a second file (jtypes.h), both of which are not needed for the floating point codebase.

Overall I would say this, if you accept to change some of the constants and functions then the impact of supporting both floating point and fixed point in the same codebase will be minimal. Assuming you use a reasonable optimizing compiler (i.e. a compiler that can handle inline functions), the run time performance of the floating point should not suffer at all because of the fixed point implementation.

I have improved the fixed point implementation so that all of the testbed examples run reasonably well. In Biped all the balls stay in the box and the guy remains stable (joints do not explode). The pyramid comes to a rest in about 15 seconds now, the car remains on the ground when you drag it, the bridge/chain stay stable when you use the mouse to pull them apart, etc. I also cleaned up some of the extra checking done for the fixed point stuff that seemed to not do anything (although perhaps that was a mistake). The result is that there are only 5 ifdefs in the cpp code:

1. Overflow in computation of force in mouse joint code. This code is very strange because the forces computed are usually very large (100K), but then they are limited to be small later (1K). The larger force has a factor of inv_dt that scales it to be very large. In the Fixed code the multiplication by inv_dt is eliminated and then the force is scaled and then inv_dt is reintroduced.
2. Overflow in contact solver related to TOI computation of lambda. Lambda scales with the inverse of dt, and in the TOI code dt can be infinitely small (substep size). In the fixed point code lambda is computed without scaling by inv_dt, and then limited so that when finally converted to a force it does not overflow. This is very similar to (1) above.
3. In b2Island the computations of max angular and linear velocity both first compute the square of the velocity and then apply the limitation (for performance reasons). In the Fixed code the squaring is eliminated. BTW, the computation of Length in the fixed code uses a method that does not underflow or overflow, so Length is safe. On the other hand just computing sqrt(x*x + y*y) is not safe since it can both under and over flow. I did not track down instances where Length could be used instead of sqrt(x*x + y*y) although I believe that there are some.
4. In b2Distance a threshold associated with detecting collisions is set to 100.0*EPSILON. Because the Fixed code uses a bigger EPSILON, the 100.0 value must be reduced (5.0 seems to work well).
5. In the code that computes three point intersections, the value of "n" is only used for it's sign, but because n is the product of other values it has a large dynamic range. In the Fixed code "n" is limited to only three values -1.0, 0.0, and 1.0.

Attached is the latest patch against SVN rev 127.

kavaler: These are some great observations. You really dug into it.

Going from 1.4.3 to 2.0.0 I changed all the constraints to work with forces rather than impulses to support a variable time step. I did see the forces become very large when solving TOI events. They were so large that I had skip storing them for subsequent warm starting.

Another approach I can take is to store impulses instead of forces but to scale them at the beginning of each time step by (dt_new / dt_old). Perhaps this will give the best of both worlds: support for variable time steps and more reasonable constraint values. Would this make a difference for your work? If so, I'll add it to the TODO list. I'll do this right away if this can reduce the number of ifdefs.

Does your fixed point library automatically check for under/overflow? This would seem to be the best method for catching these troublesome case.

I cannot say what the best way is to implement the physics since these last couple of months has been my first programming foray into physics since college. However, anything you can do to eliminate instances of (1/x) where x can be very small is a good idea, for both fixed and floating point implementations (especially fixed point). The scale that the fixed point implementation uses is +-15.16 (32767.999... is the max value, 1/65536.0 is the minimum value). Keeping values in this range would help the fixed point stuff a lot.

I have not implemented a version of Fixed that automatically checks for overflow, but that might be a good idea since most problems are manifest by overflow. Checking for underflow is almost impossible since things will always underflow and 99.999% of the time that is normal. The main time when underflow is bad is when you take 1/x, and the codebase has many asserts for these cases already. Other troublesome cases are comparisons, especially comparing differences. That sort of problem is very difficult to find at the level that the Fixed class is implemented.

IMHO 5 ifdefs for fixed point exceptions in a codebase this big and mathematically intense is BETTER than you can expect. That means that there are most likely lots of other lurking exceptions that I have not discovered since the coverage in the testbed and my own code is pretty limited. I could live with 5 ifdefs, but perhaps we will find that as people use the code for more applications this number will grow requiring some more holistic rewrite.

BTW you could try out this approximate method for vector length when using fixed point because platforms with slow float computations usually have slow sqrt computation, too.
http://www.soe.ucsc.edu/~pang/160/f98/G ... ist_fast.c

Also it might be a good idea to check for overflow/underflow only in debug mode...or when some special symbol is defined.

I did more testing of the Fixed point implementation by adding a check for overflow in the multiply routine and indeed there are many places that are overflowing. You can see them in the Pulley Joint for example. Many of these overflows do not effect overall performance, but that is more coincidence than good practice. If we want a good fixed point implementation some rethinking of the way the physics is computed and stored is needed. The fixes I've included so far work for me, but that is pretty limited audience.

kavaler: I applied your patch in SVN. Please test it out and post any further patches.

I think folder 'latex' isn't related to box2d engine...probably included by mistake ?

Are this fixed point patches start development of v2.1 ? I want to know when code on SVN become unstable due to development process, so I won't mess my local copy.

Erin: You said somewhere that there will be bugfixes to 2.0. So maybe you should focus on them and any non-bugfix things put in v2.1, because for example this fixed point modifications can mess up current code.

in my opinion fixed piont patch when not tested in 100% should be distributed separately only for those who wants it. when you finish it it could be applied in SVN

max: I agree that we shouldn't mess up the 2.0 code with non-bug fixes. I think this patch is okay because everything is turned off for floating point code. Right now I consider this an experiment to see how well fixed point code can integrate. If it becomes troublesome I will nuke the changes.

The latex folder is there for generating a PDF doxygen document. It shouldn't hurt anything.

I'm not starting 2.1 yet. I want to take a break and just fix bugs for a couple weeks.

Here's a patch for discussion (I'm not sure if it makes other things worse) regarding the stacking behaviour I mentioned in another thread a while back. It was a build thread see last post
http://www.box2d.org/forum/viewtopic.php?f=7&t=455

The patch ignores fixed point and modifies the VaryingRestitution sample to better illustrate the problem the patch tries to address.