Collision meshes

It's a fairly common idea, that one should have seperate meshes for collision detection and for rendering. The rendering one is high-poly, while the collision one is low-poly. I've been thinking about ways to generate decent collision meshes algorithmically; doubtless there is material already out there, I've not got around to reading it yet.

Generating a collision mesh for a non-convex object is specifically the thing I'm wondering about. How could I generate a mesh for, say, a four-legged table? Or a car that the player can sit inside? I suspect many people just generate the convex hull, but that'd make my table seem like a box.

It'd probably be helpful to define some metrics. Given a collision mesh and a rendering mesh, and assuming that each is closed, we can find the volume that each encloses. If we 'subtract' the volume enclosed by the rendering mesh from the volume enclosed by the collision mesh, and sum the resulting pieces, we get a metric for the difference in volume between the two meshes. Furthermore, if we actually consider the pieces enclosed by the rendering mesh but not by the collision mesh as 'negative space,' our metric is signed - a positive metric means that the collision mesh is generally enclosing the rendering mesh, and a negative metric means that the rendering mesh is enclosing the collision mesh.

So we can consider that metric, and we can consider the number of polygons in the collision mesh. Essentially, we want to minimize both, but the fewer polygons you have the harder it becomes to match the meshes, so it's a tradeoff.