Where to start on encapsulating a 3D mesh in a Bounding Volume Hierarchy

I am working on a rather rudimentary rigid body physics simulator for my studies. I require very fine-grain collision detection. That is, I require the XYZ point of colliding polygons of the meshes. I cannot just encapsulate the meshes in rough bounding volumes and base my collision responses on them.

So, for meshes with a high number of polygons I obvio开发者_开发技巧usly need a BVH (or something equivalent). Where I need help is an algorithm I can run in a pre-processing step which generates a BVH from the mesh. My background is games and all of the resources I have found thus far wrap entire meshes in convex polyhedra, and do not go as far as testing the meshes themselves. This is because games can get away with rough physics such as this.

I am currently reading through Ericson's Real Time Collision Detection which is quite helpful, but I am wondering if anyone knows of any books/papers which specifically deal with this problem.

I also was planning on generating AABB's from the polygons. Each frame while traversing the BVH I would transform the AABB by the rigid body's transformation matrix, creating an OABB. Then I would test the OABB's for intersection. I have not implemented this yet and is all theorycraft at the moment. If anyone has any experience doing this, any tips or more efficient algorithms would be greatly appreciated!

One benefactor to performance is using linear programming techniques for optimality and point reduction. One such solver is the GJK or Gilbert, Johnson Keerthi solver.

There are other simplice solvers out there, but really when it comes to optimization of NP complete problems, it is still a valid research topic and open for discussion.

You could implement triangle caching, which is a very simple technique. In essence, you save the pair of leaf-nodes from two BVHs that collides. The next time you check for collision between these two BVHs, begin by testing the saved two leaf-nodes immediately. If frame-to-frame coherency is high, which is usually the case with games, then chances are that you will detect a collision without ever testing the two BVHs!

UNHC gamma has published several papers that mention/describe triangle cachning. For instance, see this paper (I think its very readable!).