3D collision detection

3D libraries are conceived as just drawing primitives, and nothing more. That's why graphics programmers are asked to reinvent the wheel several times.

One of those wheels is the "world space" partitioning. In particular, the collision detection of meshes.

I don't know how serious engines handle it on a per-pixel/vertex basis, but I think they just do miracles. I implemented something simpler for my PLT by using cheap bounding spheres.

The improved geometries loader "keeps in mind" the minimum and maximum coordinates for each axis, while it constructs the vertex arrays; at the end of the loading process, it uses those coordinates to find the middle point of the mesh and the farthest vertex from it: they are the bounding sphere center and radius, respectively.

Checking if a mesh collides with another is straightforward:

• transform the bounding centers from model to world space, and compute the distance (let's call this value "D") between them
• sum up the two bounding radius (let's call it "S")
• if D > S meshes don't collide
  

It's kind of a cheat, but it works.
Of course, using complex meshes will reveal its nature: it's far from being accurate. But it so fast!

I think there's a couple of possible optimizations.

The first one is, well, "CAD driven": I could simply cut down every model into many "groups", and give everyone its own bounding sphere. The drawback is, obviously, that the designer is asked to think meshes as a collection of separate tranches, and everything works better if each partition fills out its "space". Moreover, this solution makes LOD design slightly more complex.

The second one is more challenging: compute the partitions on fly, during geometry loading, by using a stochastic approach: areas denser of polygons are more likely to be relevant for the mesh, and should be enclosed by their own bounding sphere.