Collision

There are several techniques to detect collisions between objects. The simplest method is to see if each object intersects any of the other objects in the scene. This gets very expensive quickly, so most programmers use acceleration structures to simplify the search — anything to exclude candidate objects from a search. A popular method is sweep and prune. I'm not using it here.

The KD Tree is the intersection accelerator of choice in raytracing for its quick traversal, but it is not necessarily preferred for collision detection. It has a very expensive generation step and any moving objects will force a rebuild. So, I wouldn't necessarily recommend using one for collision detection, but I had one lying around and wanted to see how it would fair.

The scene below is fairly complex. The ground is made of a 10x10 mesh grid, and the total scene has 274 faces. Collision detection is done at the triangle level, so there are over 500 objects to check per ball each time step. I'm using a very simpler Euler integrator, and I do detection by extending a ray from the ball center towards its predicted position in the next time step. By intersecting this ray with the scenegraph held in the KD Tree, I can determine if it hits any object in the scene. By the magic of heirarchies, I can reduce the 500 checks necessary per ball to around 10.

The best part is that the search time is O(nLog(n)) with scene complexity, so adding more triangles is not going to slow the detection very much. Of course, this is assuming that the tree was constructed using a good algorithm, like a surface area heuristic or whatnot. If you look at the KD Tree in this simulation, you may notice that I'm building it using a simple median algorithm (I'm so lazy), so the traversal performance here should be on par with an octree.

Related

Octree created 07 Oct 07

Heirarchical triangle storage using an Octree.