2

Currently I am looking for an efficient algorithm to compute the intersection of two triangle meshes. I have searched over the internet, but haven't found valuable materials. The book Real-Time Collision Detection is a helpful book but is too complex for my task. I also found the post:Triangle to triangle collision detection in 3D. However I hope to find a detailed description about the algorithm.

Regards Jogging

Community
  • 1
  • 1
Jogging Song
  • 573
  • 6
  • 28

1 Answers1

4

Well it depends on meshes size, testing each triangle in each mesh against the other is only valid in small meshes since it has n^2 complexity.

To work around that most algorithms use Spatial portioning first to subdivide the space into smaller ones and then tackles each one separately.

For spatial portioning most algorithms use OcTrees or BSPTrees however if you don't need to complicate things you can just subdivide the space into n boxes then check triangle triangle intersection in each box

Ahmed Matar
  • 241
  • 1
  • 6
  • Thanks. My plan is to build one octree using the points from two triangle meshes. If the leaf node contains points from both meshes, I will try to detect the possible intersection between the points. La – Jogging Song Feb 14 '14 at 02:03
  • Thanks. My plan is to build one octree using the points from two triangle meshes. If the leaf node contains points from both meshes, I will try to detect the possible intersection between the points. It depends on how to build the octree. I think the octree is controlled by two parameters: tree depth and minimum cell size. For the extreme case, each leaf node will contain only one point, and no intersection occurs. Is this plausible? – Jogging Song Feb 14 '14 at 02:14
  • it sure is, but i think the tree should be built on faces not vertices as it could be one big triangle that each of its vertices in a different cell, it has to be calculated against all cells intersected with the triangle, Sorry for the late reply – Ahmed Matar Feb 16 '14 at 10:17
  • What's the difference between tree built on faces and tree built on vertices? If one leaf node contains points from both meshes, I will check triangle-triangle intersection between all triangles of points in the leaf node from one mesh and all triangles of points in the same leaf node from another mesh. – Jogging Song Feb 17 '14 at 01:25
  • 1
    It is possible for two triangles to be intersected although no cell contains vertices of both, http://s28.postimg.org/n3z6i0yf1/Untitled.jpg in this image the red and blue triangles are intersected an using vertices no cell contains more than one vertex – Ahmed Matar Feb 17 '14 at 09:40
  • Thanks, Ahmed. The image is illustrative of the problem. Maybe I can modify the parameter VoxelSize to avoid the problem. This strategy can't solve the problem. I try to detect the intersection of two meshes. If I keep one triangle in one voxel, the edge of another triangle may intersect with the boundaries of the box. Is there a good way to build one tree on the faces of one mesh? – Jogging Song Feb 20 '14 at 01:53
  • you can split the space uniformly into n*n*n cells, then assign each triangle to all cells it is intersected with http://s23.postimg.org/xdjx3catn/Untitled.jpg at this example the blue triangle will be assigned to cells (2,3,4,8) then it will be checked with every cell it is assigned to – Ahmed Matar Feb 20 '14 at 13:29
  • If I use one uniform grid to partition the space, it is a new method and not a tree method. Checking whether triangles intersect with cells is time consuming. – Jogging Song Feb 20 '14 at 15:23
  • I wrote it before, in c++ and on a mesh with 300000 face it takes almost 2 seconds, if that is not sufficient enough for you, you can use OCtrees or BSBTrees and do the same to triangles located in more than one triangle. – Ahmed Matar Feb 20 '14 at 15:39