The book: Game Physics Pearls

I have written a chapter on this book about how to set-up soft bodies in games. Within the chapter you will find sample code on how to implement the most difficult features of the model. It has been tested in one prototype using the Alone in the Dark framework for PC.

Within the book there are other very interesting topics related to physics in games. All of them give incredible hints in how to optimize the algorithms for games.

So, it would be a good idea if you buy the book. You can get it from Amazon. 

Implementation of GJK

Wow, quite a lot without posting here... I will try to be better on this.

After some relaxing weeks implementing intersection tests for basic primitives (triangles, box, spheres, etc) I have decided to go further and implement a generic algorithm to detect collisions: I decided to implement the well known GJK algorithm (also known as Gilbert-Johnson-Keerthi algorithm).

Here, I will just describe my general thoughts and experience while implementing this (time of implementation, bibliography) but I will not give details on the theory, which might take lots and lots of lines.

Actually, the GJK algorithm is only a part of a whole collision detection architecture. It only gives you the distance between two convex objects but it is possible to adapt it to a clever architecture to provide you with contact points a penetration depths.

So, I did a fast "state-of-the-art" just to realize that it was not an easy task. Even worst, my dear boss was asking me for details on the time that it can be implemented and just looking all the maths, I was just scared !

Unless you have a good experience working with convex theory, Minkowski sums, affine transformations, you will do the implementation very fast or, if you are like me, not a real expert on this, it will take about "1 month" working 8 hrs a day to implemented the whole thing. I should say that you can get it much faster from Bullet or Solid libraries, but here in the company, due to license constraints, we have to implement everything from nothing.

I should accept that I had good inspiration from these books:

1. Collision Detection in Interactive 3D Environments, Gino Van der Vergen
2. Real-Time Collision Detection, Christer Ericson

In the first book, the one from Gino, there are a lot of maths (quite a lot, I would say), but you can get the Solid library where GJK is implemented. The book explains everything in the code, mainly the numerical problems, and provides you of a hybrid method to get penetration depths using GJK. I compiled the library and it runs very nice. It was a huge source of inspiration. However, there is no way it will make it for our PS3 compilation standards and many many problems arise while integrating SIMD operations.

The second book gives you a better introduction to the GJK problem but it will no go farther into the details. So, I think both books complement each other very well.

I also took some inspiration from Bullet. It computes distance to simplexes in a more direct way but still, it remains quite complex.

So, I implemented GJK + EPA as explained in Gino's book and so far it compiles perfectly in within our SIMD standards and PS3 compilation constraints.

The main idea is to add an extra convex radius to each convex shape (as Havok does) . Then

• GJK is used when inter-penetrations are small. Using EPA when penetration are larger is quite unstable. To use GJK we surround the objects with a little margin (the convex radius in Havok terms) When the inter-penetration is within this margin, we compute the closest distance between the original objects. The witness points of the distance are projected to the boundaries of the enlarged objects in order to return the penetration depth.
  

• If the original objects penetrate as well, we use EPA (Expanding Polytope Algorithm). EPA is fully explained in Gino's book. It is really worthy to take a look on it. Be sure on reading page 162 which is very helpful to get rid of many numerical errors. The general idea is to expand a 3D politope which is further used to extract the penetration depth. You can have a better idea if you have a look on Solid 3D.

To avoid jittering you should better allowed some little penetration and create a persistent manifold as Bullet does. The little penetration is easy to allow since we have already implemented a convex radius. At the beginning I "snobbed" the persistent manifold and only catched contact points (the deepest). But it turns out that this is very important and an optimal persistent manifold should be implemented. GJK retunrs always one contact point, so imagine for a capsule/box collision: it will give you a jittering due to only one contact at a time. You have to keep one contact point. The most clever, I have found, to do this, is to do it as bullet. Keeping the contact points that covers the maximum area of the manifold. Although, if you go further into Bullet's code, you will notice a risk for slippering.

Anyway, no more time to write, now..

take care !

Evaluating Physics Engines For Games - PAL -

Physics engines are a high-tech aspect within a next-gen game. They are in charge of simulating all the physics as realistic as possible. Many times the accuracy of the physics is reduced to meet the real-time requirements of the game. Many companies prefer to buy the physics engine as a middleware and apply their effors in others parts of the game. Nowadays there well established companies offering this middleware, like for example Havok, Nvidia-AGEIA. There are of course new comers and open-source engines such as Pixelux, Bullet, ODE, Tokamak, etc.

The big question is: which physics engine is the best ?

The answer is straighforward: None of them is in overall the best and it is very case dependent. However, there is still a way to make some comparisons. So, I came across this paper:

Evaluation of Real Time Physics Simulation Systems,
A. Boeing, T. Braunl
Procc. Computer graphics and interactive techniques in Australasia and South East Asia, 2007

The work on the paper compares different physics engines: AGEIA-Nvidia, Bullet, JigLib (from my friend Danny Chapman), Newton Physics, ODE, Tokamak, True Axis. The authors implemented a physics abstraction layer (PAL) to carry out the comparison. You can even download PAL. I suppose that it has been an amazing work to wrap all the physics engine in only one application. Unfortunately, HAVOK is not compared nor PIXELUX.

The comparison was based on five tests:

1. Integrator performance (i.e. solution of ODE's)
   
2. Material properties (i.e. frictions, restitution)
   
3. Constraint stability
4. Collision detection
5. Stacking test

The authors had these results: AGEIA-Nvidia has the best integrator performance. True Axis gave the best results for restitutions followed by Bullet and AGEIA-Nvidia. Static friction was best simulated by Newton followed by AGEIA-Nvidia. With respecto to constraints, Tokamak provides the best results solving constraints in the least time, ODE provided the most accurate results but requires a lot of time to solve the constraints. In this aspect, among the worst you can find AGEIA-Nvidia. This is very surprising since I've been using AGEIA-Nvidia and it has been quite accurate when solving the constraints. Collision detection was best carried out by Tokamak and Bullet, however, it should be noted that other engines failed this test because the test was not properly adapted to the engine. For box stacking the author only provided a visual test claiming that all the engines pass the test with the best performance for Tokamak.

The main conclusion that the authors made is that Bullet engine provided the best results overall.

Although this result is the conclusion of a huge work, it should be taken with a lot of care, since many aspects were not included in the comparison and that the PAL system does not support correctly some engines (for example AGEIA-Nvidia for collision detection), Pixelux and Havok were not included in the comparison, support from the physics engine provider, other aspects such as fluid simulation, soft body simulation and some specific optimisations of the engines were not included. Which ones are optimised for PS3 or Xbox360 ? Results are evidently tested on a PC. Finally, some tests are not suitable in many cases, for instance the integrator performance may vary for each engine and for each object being simulated.

Still, PAL is a good starting tool to start testing physics engines.

Anyway, my favorites are AGEIA-Nvidia, Havok and Bullet and the one we are developping :)

Box2D -Part II-

As I told you previously Box2D has been used in some games. A good example is the Crayon Physics Deluxe that won the first prize in the Independent Game Festival.

I really like this game. It is very original and simple. When my baby will grow, I will probably get this game. Hopefully, it will be available in a little toy-set instead of using the screen and computer.

Check it out the website of the game by clicking here. You can also check the little video below:

Box2D -Part I-

Most of my previous research dealed with soft bodies, collision detection, real-time optimisation, biped robotics for virtual humans, but very recently I have started to investigate rigid body constraints (rigid body contacts, distance constraints, etc.) for real-time simulations.

I must confess that I am quite new in this. i.e. I have never implemented a contact ball constraint... now, this is about to change. Rigid body research is not new at all, there are more than 20 years that people has spent on that and now there are really good commercial software out there (e.g. Havok, Ageia, etc.) and also open source, like Bullet.

This is great, but still, if you want to implemented from nothing, you might need some documentation. Papers are the best choice, but if you have simple code available is just fantastic. So, I have found Box2D . It is an open source software where rigid body dynamics is implemented in 2D in a very friendly manner. It has been coded with an incredible videogame taste. It has already been used in some 2D videogames.

And the best thing for me is that it has the implementation of constraints in 2D. This implementation is actually 2D version of the constraints implemented in Bullet !

I have compiled some tests and surfed throughout the code and it is really good... so, as a first look, Box2D seems a very didactical starting point for rigid body simulation for games.