Intersecting meshes

If the polyhedron are convex, then you can use a CSG algorithm that performs half-space clipping in order to determine the intersection. Otherwise, there exists a Computational Geometry Algorithms Library, and one of the features is 3D boolean operations of Nef polyhedra. However, I don't know how much trouble it would be to convert your polyhedron into the Nef representation. If worse come to worst you're looking at a brute force clipping problem.

You can create a Hierarchical Bounding Volume (HBV) from each of those meshes and test for their intersection. A HBV is a tree structure formed by bounding volumes. Each node's BV contains within itself its successors' BV. So, in intersection testing, child nodes are tested only if their parents' BVs collide.

Thanks a lot! So if I get you right it wouldnt be possible to use stencil buffers or something in this way...

You're welcome. Personally, I've not heard of this method. You indeed can use stencil buffers to highlight intersections between primitives if that's what you're looking for, but how would you want to use stencil buffers to create a mesh out of the colliding objects considering that doing so needs access to the shared vertices?

Another issue that suddenly occurred to me, is how accurate you want this intersection tests to be? From your original post, I assume you're only interested in finding the colliding triangles and forming a mesh out of them. If you want to be more accurate, you may need to break up the colliding triangles into two or more triangles, on their line of intersection. This would be more complicated.

/EDIT: how accurate?

[Edited by - Ashkan on February 19, 2007 4:58:31 AM]

Ok thanks it should be as accurate as possible. Seems like a much more complicated algorithm as I thought :)