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.