Mesh collisions

This is usually where physics gets messy. It's all fun and games until someone suggests that maybe all objects are not perfectly convex, such as... the game level? There is convex decomposition, yes, but I'm not totally convinced that's a silver bullet. Convex decomposition is awfully complicated, and requires heavy preprocessing. It's definitely a good idea in many cases, but there will always be raw triangles.

Convex decomposition or not, you need some sort of mid-phase, finding which triangles/primitives collide with a specific object. A lot of work has been put into this, and I think most people today agree that a quantized, binary AABB tree is the ideal solution.

What's interesting here is how people usually query these AABB trees. The output from the broad phase is a list of pairs with overlapping bounding volumes. These pairs are then processed one by one, and in the case of a triangle mesh, the mid-phase is engaged to find the relevant triangles/primitives. After that, the near phase finds the actual contacts.

What I would like to suggest is to query the whole dynamic scene against the AABB tree all at once. That is, instead of colliding the AABB tree with a single object (single AABB) multiple times, you collide it with another AABB tree, representing all moving objects. This is especially relevant if combined with a Dynamic Bounding Volume Tree broad phase, as suggested by Erwin Coumans. In this case, all moving objects are already in a dynamic AABB tree of their own. Objects tend to appear in clusters, so objects close together also tend to collide with the same triangles. Doing the mid-phase this way saves you from drilling down the compressed AABB tree multiple times, which gives an instant performance gain. The tree/tree traversal is a bit of a mind job at first, but the Bullet DBVT implementation is a really good reference.

As usual, I'm really lazy and not doing my side-by-side comparisons, but it might show up later.

Movie time

It was a long time since I posted a movie, so I thought I'd record a little snippet of what I'm working on at the moment - mesh collisions. Without the fancy SSAO renderer it runs in 60 FPS. Stay tunes for details!

STL

I really like the idea of using standardized versions of simple data structures. Small snippets of code rewritten over and over again by thousands of people. I bet there are a handfull of programmers world-wide at this moment implementing a dynamic array or a hash table. As much as I like the idea, I hate the only standard out there - STL.

There are several problems:

1) The interface is horribly over-engineered and just plain sucks. Even the simplest of simple operations turns out as three or for lines of code. Really long ones. Say I want to remove an element from a vector. Instead of just offering a dead simple myVector.erase(element) I have to bother with iterators and find functions (of course defined in another include file), ending up with this:

std::vector::iterator it = find(myVector.begin(), myVector.end(), element);

if (it != vec.end())

vec.erase(it);

This does only remove the first occurance of "element", which is understandable. If you want to remove all of them you need to use a whole different method... Another option is to iterate through the vector myself and remove the desired elements, basically implementing the erase algorithm on the spot, which completely takes away the benefit of using a standardized vector in the first place. Just as a bonus, you need to take special care of what happens to the iterator as you erase the element it's pointing at. Sigh.

2) It is not minimal, nor consequent. There are heaps of ways to do everything, and none of them seems more commonly used than any other, and the naming of operations vary between classes. Removing elements is a good example, which can be done with member functions pop_back, erase or remove (available on lists but not vectors). There are also the global algorithms remove and remove_if, which actually does not really remove anything but merely scrambles elements around a bit for easier removal later. Confusing aye?

3) Because of its severe complexity it is not consistent across platforms. Hence, porting your code to another platform involves small tweaks. There are projects like stlport that makes life easier, but it kind of takes away the purpose of a standard if there is actually only one implementation that is portable.

4) Debugging STL code makes you suicidal. You know exactly what I mean.

5) It claims to be designed for performance, but only considers academic-style algorithmic complexity and not real-world performance which is often based more on memory allocations, locking and memory access patterns. Some implementations use pool allocators to speed things up, but it's still allocations. I personally use my own data structures which includes an initial template-specified storage as part of the container and only allocate memory if it grows beyond that initial size. I suppose STL could be configured to do similar things by a template wizard, but I wouldn't want to be the guy maintaining that mess.