Vriphys 09

Oh, ahh, I always do it at the last minute... but I do it right. I finished reviewing some papers for this conference.

VRIPHYS 09

It is a conference for professionals, researchers, students interested in virtual reality interactions and physics simulations. I think it is a great forum where people can meet in a friendly manner.

It is not the huge show of Siggraph, not even EG or SCA. It is more focused in real-time and interactions and it has the support of Eurgraphics. I hope this year it will have excellent papers as previous years.

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 !

PS3 compilation hints

Templates are not transparent all the time when compiling with PS3. I have been compiling a set of hints from my short experience. I will put a list of them shortly.

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