Siggraph 2010 mug

Being a reviewer for the last Siggraph 2010 has been a pleasure. If you work in the Academia being a reviewer is a normal part of your daily activities, since although you are not paid, the payment is implicitly included in your Academia salary besides giving you a plus in your CV for further scientific evaluations.

However, if you are working in the industry, it has a different meaning. You don't get paid either, it is not really worthy for your work since in your CV does not mean much for recruiters, your wife is upset for loosing time in something without any payment. From my point of view, it is done by the pleasure of reading and reviewing highly technical works. It gives you some sort of self-confidence.

I don't thing my boss cares if I am a SIGGRAPH reviewer or not, unlike the boss of  normal academia researchers. But, still, you get a free and pretty mug as shown in the picture.

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. 

VRIPHYS : Virtual Reality Interactions and Physical Simulations : http://www.vriphys.org

 You might be surprised that the website of the VRIPHYS workshop has disappeared. At the moment, this link:  http://www.vriphys.org does not work any more.

The main reason of this is because it has been decided to change to a different host provider for the website. Hence, the previous Italian provider (aruba) does not host the vriphys website and has therefore removed the information.

Vriphys will be now hosted and managed by INRIA, France. Find the latest 2010 vriphys (the 7th) workshop in this link.

As a partner event of Eurographics, you can find the papers and scientific committees of the previous workshops in the Eurographics Digital Library. HERE

Note that papers of the years 2004 and 2005 are not available in the Eurographics website since, although partnership with EG was obtained in 2005, it was until 2006 that they started to store the papers and related information.

In any case, if you need the vriphys papers or other information related to 2004 and 2005,  feel free to contact me.

Convex decomposition

I have recently wrap the extraordinary convex decomposition library of John Ratcliff. I did it with the 2007 version. I have added some functions (from John's as well) to find the best fitting capsules, spheres and oriented boxes of convex hulls.

The 2007 version has some bugs that I am currently fixing but it works fine. If you want a more robust version you can get that one of 2004 which is the one that the guys from Bullet have wrapped. I wrapped it as well and it works just perfect. The disadvantage is that it does not include best fitting features and that the splitting plane of concave objects is not always the best. Besides, it is implemented using floats instead of doubles.

John did a great job. At the beginning I tried to implement the convex decomposition myself, but I had some troubles trying to find the best fitting plane. It worked in some cases but in others it failed terrible. So, I decided to wrap John's convex library. It is a bit slower (since it computes the decomposition in a "brute force manner" but it is worthy to wait 30 seconds for decomposing a concave object of 700 triangles into a set of convex hulls.

I will use this together with my GJK implementation :)

Click here for the link of John's convex decomposition library. If you use it, feel free to donate something to John's son association.

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 !

THE SHORTEST COLLISION DETECTION SUMMARY EVER

I. INTRODUCTION

Collision detection between virtual objects is one of the bottlenecks in real-time applications.

Unfortunately, after more than 20 years of research, there is not a generic method that can be used in all applications.

The main reason of this is that the objects involved in the collision detection process become more and more complex. Hence, we have passed from using only rigid bodies to use more complex objects such as volumetric deformable bodies, cloths, fluids, etc.

Refer to [1][2][3] as a good starting point. Although most of the available techniques used to detect collision between rigid bodies need to be modified for deformable objects, most of these techniques share a basic approach. This approach divides the collision detection process into 3 steps:

1. Broadphase
2. Middle phase
3. Narrow phase

Next, I will briefly describe this steps. Note that we only consider static collision detection.


II. THE BROADPHASE.

In this stage, bodies are encapsulated in simpler volumes (spheres, boxes) for fast intersections.

This way, non intersecting pairs of complex objects are rapidly culled out from the collision process.

These simpler objects may be spheres, axis aligned bounding boxes (AABB), oriented bounding boxes (OBB) just to mention the most typical ones. They add little extra memory to the simulation but highly increase the performance of our collision detection process.

There is not a best choice between these bounding volumes, and some tests should be done to pick the best for a particular situation.

Decomposing the space into uniform grids and checking the interference between the cells and the simpler volume can additionally be added to this stage to speed up the collision process.


III. THE MIDDLE PHASE

The broadphase identifies the pair of bodies that should be tested for possible collision detection. Instead of directly test the primitives of the bodies (triangles, points) we may add an additional stage that can accelerate the collision detection process.

This additional stage is the middle phase. The main idea is to construct a bounding volume hierarchy of the object: the simpler volume used in the broadphase is subdivided into inner sub-volumes and each sub-volume into inner sub-volumes and so on, until we reach the primitives of the body.

Once the pair of objects are identified in the broadphase, the middle phase uses the bounding volume hierarchy to identify “regions” of the bodies for additional collision detection queries.

As an example, in a bottom-up construction approach of the bounding volume hierarchy, we select a small set of primitives of the object ( say 2 or 3 triangles for example) and we enclose them within a bounding volume. This is a leaf node. We do the same for all the primitives of the object. We end up by enclosing all the primitives of the object with small bounding volumes.

Next, we select a set of these small bounding volumes (2 or more and normally neighbors of each other) and enclosed them within a larger bounding volume. We repeat this for all the small volumes. As a result, we will have a smaller set of larger (middle) bounding volumes. We repeat the process until we have only one bounding volume, which represents our root node. Each level of the hierarchy represents a tighter fit than its parent. The number of level of the hierarchy is usually known as the depth of the tree.

Note that these hierarchies are constructed in an offline process.

The middle phase starts by testing the root bounding volume of bodyA (rootBVA) with the children bounding volumes of the root bounding volume of bodyB (rootBVB). If an interference exists between rootBVA and only one of the children of rootBVB we will know that the collision does not happen with the other children of rootBVB. In the next iteration we will not include them in the intersection tests. We will only test the colliding children with the children of the rootBVB and so on.

Alternatively, there exists a top-bottom approach in which we start by using the simpler bounding volume of the object and subdivide this volume into inner subvolumes in a recursively manner until we reach the primitives of the object.

For rigid bodies, there is not a clear advantage between OBB, AABB or bounding spheres trees. Their efficiency, memory consumption and accuracy depend on the application and on the enclosing body.

The main difference comes out when they are applied to deformable bodies (volumetric, 2D cloths) since these hierarchies need to be updated at each time step to adapt to the new deformed shape of the body.

Van der Bergen compared AABB's and OBB's hierarchies for deformable objects and determined that AABB's are the best option [4]. He also showed that, although hierarchies can also be rebuilt, updating them is almost ten times faster than rebuilding them. Larson et al. [5] compared different methods for the hierarchy updating process based on bottom-up and top-down strategies. They found that these methods depend on the depth of the tree and proposed a method that uses both strategies.

There has not been a comparison between sphere hierarchies and AABB's hierarchies since sphere trees were for long time rejected for its poor tightness to the body. However, latest results have shown that sphere trees can be as tight as AABB's trees and then can be an excellent option for deformable bodies. Their only problem is that their construction is not as simple as AABB's trees but the update can be much faster (note: last sentence is only an empirical personal assumption).

Advance issues concern the update of the trees when the encapsulating body suffers a topology modification, i.e. when the object is broken or cut. If it is a partial fracture or rupture, the tree most probably will need a rebuilt, which is computationally costly. If the object is broken in hundreds of sub-bodies, then the tree hierarchy might result to be obsolete.

Additionally, as an advance issue, auto-collisions might occur, (e.g. cloth self-collisions) and this is a subject in which volume hierarchies haven't present an effective solution.

To handle these two last issues, alternative approaches can be used. Instead of using bounding trees, we can used an optimized spatial hashing for collision detection of deformable objects [6].


IV THE NARROW PHASE

The result of the middle phase is either no collision (i.e. no leaves of body A are colliding with any leaves of body B) or "leaves collision" (i.e. at least one bounding volume leaf of body A is overlapping at least one bounding volume leaf of body B).

We focus here in polygonal models.

The leaves of the bounding volume tree (the smaller boxes and spheres in the hierarchy) are associated to a small set of primitives of the object. Hence, a little sphere will point to 2 or 3 triangles. Associating triangles to little bounding volumes is not a simple task since some aliasing problems may arise (e.g. a triangle may be associated to different bounding volumes under different circumstances).

Therefore, the narrow phase consists on finding the intersection of the primitives (e.g. triangles) enclosed by the bounding volume leaves of body A and B. Finally, we need to find the separation normal and the penetration distance as the minimum information for the collision response. Additional information can be included such as the intersecting triangles or edges. This additional information can be useful to build the Id of the contact.

Alternatively, instead of finding the primitives associated to the each leaf bounding volume, we can use the little leaf bounding volume as a "coarse primitive" of the body and compute the separation normal and penetration distance. We lose accuracy by doing this, however, if the approximation of the object by the deepest level of the hierarchy is good enough (i.e. the leaves were extraordinary calculated) then we can have an acceptable response and we can earn lots of time computations and memory consumption is highly reduced.

Finding contact information for triangles or other primitives is not an easy task. Methods such as the Lin-Canny Closest Feature algorithm may not be well suited since it does not provide penetration information and the well known and complicated to implement GJK seems to be the best option to best measure interpenetration.


BIBLIOGRAPHY

[1] Collision Detection for Deformable Bodies, Teschner. M et al., Proc. of the Star Reports, EG 04, pp 119-140

[2] 3D Collision Detection: A Survey, Jimenez P. et al, Computer And Graphics, 2001 pp 269-285

[3] Real-Time Collision Detection, C Ericson, Elsevier 2005

[4] Efficient Collision Detection Of Complex Deformable Models Using AABB trees, Van den Bergen, G. J Graph Tools, 2,4 (1997)

[5] Collision Detection for continuously deforming bodies, Larsson T. et al, EG Short Presentations 2001, pp. 325-333

[6] Optimized Spatial Hashing for Collision Detection of Deformable Objects, M. Teschner et al. Proc. VMV 2003

Time Critical Collision Detection

One of the bottlenecks to obtain real-time physical based simulations is the collision detection process and much research has been done on this. In the past, I proposed a method to fit the collision process to any given budget of time. See the paper here. This method works for rigid and deformable bodies.

The idea is to interrupt the collision process when our budget of time has expired and use the available information to compute the collision response (it this happened). The computed response is an approximation of the real one: Yes, we trade time for accuracy, but in general the results are quite satisfactory.


The method is based on sphere representations of the object. Each of these representations goes from a coarse representation (a) to a high quality representation (d). If we have little time, we compute the collision detection process using (a) or (b) representations as in the figure above. If we have lots of time, we use more detailed representations (c) or (d). The coarser the representation the less accurate is the response (or even the detection).

The complexity of the problem comes to compute good responses even with little information.

The question is: do you prefer high accurate responses even if your application goes slow or do you prefer to keep your simulation rates and obtaining some non-accurate responses ??

Well, here at Atari we have decided to go for high accurate responses... so, that means that I will have to find other ways to keep good simulation rates... good challenge !

So, if anybody have some good ideas, please let me know.

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 :)

Optimized Spatial Hashing for Collision Detection: Implementation

A couple of weeks ago, I implemented a method to detect collisions between any kind of body -rigid or deformable-. The method is based on the following paper:

M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M. Gross, "Optimized Spatial Hashing for Collision Detection of Deformable Objects," Proc. Vision, Modeling, Visualization VMV'03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.

Click here to get the paper.

Short conclusion and review after the implementation:

The collision detection method is based on an optimised spatial hashing of the object. I have implemented it for rigid bodies and soft bodies (2D and 3D) so you can use it for both. The method assumes that you can provide the surface vertices of the object and that you can also provide a collision primitive representation of the object. The collision primitives in case of soft bodies can be the surface tetrahedrons, for fluids you can inflate the particles, for cloths you can give a thickness to the triangles or even bounding spheres for triangles.

The method follows two main steps:

STEP 1:
Discretization and hashing of the surface vertices of the object. Each vertex is discretized with respect to a cell (an axis aligned box). The coordinates of the vertex (x,y,z) are divided by the given cell size and rounded down to the next integer. As in the paper the discretized vertex is: (i,j,k) where i = x/l, j = y/l and k = z/l. Then, a hash function maps the discretized vertex to a 1D index h. I used the following code:

inline unsigned int hash(int xi, int yi, int zi) {

unsigned int h = (xi * 73856093)^(yi * 19349663)^(zi * 83492791) ; //same as in paper
return h % sizeOfHashTable} //sizeOfHashTable=big value
}

STEP 2:
Discretization and hashing of the collision primitives as in step 1. For example, for each surface tetrahedron of the object, I compute the AABB and discretize the minimum and maximum values as we did for the vertices. Hash values are computed for all cells affected by the AABB of the tetrahedron. This is a tricky part and I can explain a bit further if you want. Then, all the vertices found at the according hash table index are tested for intersection. The intersection test can be: vertices inside sphere, tetrahedron or box, or if continuous collision detection, you can use segments versus sphere, tetrahedron or box.

The rest of the paper determines an optimal size of the hash table and optimal hash function.

CONCLUSION:
Good stuff: The method handles collision detection for deformable objects (cloths and volumetric objects) and rigid bodies. The method handles self-collisions since it hashes all collision primitives and all vertices of all objects in the same table.

Bad stuff: It is not edge sensitive which means that it does not detect collision with edges. Object penetration happens when edges are not detected. The method detects if vertices are inside the object but not edges. Authors of the paper claim that this is not a problem.. well, not really, if the objects uses a low resolution with big triangles (like the case of triangles in videogames) the penetrations are really evident and things are very unrealistic.
Besides, it is difficult to compute a proper collision response. If a vertex is inside the object, which is the direction of the repulsion normal ? To solve this, I use previous vertex positions to compute segments and handle this problem.

I am not quite sure about the optimization at the end of section 4.2. It is not clear explained so I am not sure if I got it right (well, it works fine, so I think it is correct). But, is there a big signifcance for this optimization for small hash tables ?

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.