How to check triangle-triangle intersection?

OpenGL OpenGL: Advanced Coding
1

Hello, I have a problem about the triangle-triangle intersection of two triangle mesh. I have 2 triangle mesh, each contain 4092 vertices. I want to find out all of the intersection point of these 2 mesh. I have used the sample program of “A fast triangle-triangle intersection detection”. And then used another float pointer to store all of the point. But is seems that the function returns huge amount of point to me so it is very slow and then have memory error message. I used 2 for loop to compare all the point. "for (i=0; i<4092; i++) {for (k=0; k<4092; k++)…}}. It is very very slow. Can anyone please suggest what should I do or suggest a better algorithm to me. Thanks a lot.

2

It’s always good to get from high level tests to low level tests. Use bounding box test. Afterwards use the boxes of an octree to test on collision etc.
Or do you want something like CSG? Your posting sounds a bit like that. There are better !rendering! technuiqes to perform CSG. Some interresting things are @ nvidia.com.

3

The fastest and most exact way that I have found to do it is to use the concept of a signed volume via the Jacobian. This will minimize floating point errors.

Test each side of the first triangle against the second, and vice versa.

  1. Using one endpoint of the side and the whole other triangle, construct a tetrahedron. Compute its Jacobian. do the same for the other end point. If they have opposite signs, then the two point lie on opposite sides of the triangle and it is acutally possible that this line intersects the triangle.

  2. If we pass the first test, compute the volumes of the tetrahedra formed by two points on the triangle and the two endpoints of the line. If they all have the same sign, then the line intersects the triangle.

  3. Use a conventional test to determine the pierce point now that we are already sure that there is one.

The reasoning here is that finding the pierce point from the get-go will not always give good results, and will screw up on most degeneracies (i.e. triangles that share a side or point). This method is very exact way of determining whether the triangles intersect or not, and then we cn catch the errors in finding the pierce points.

For more info see, for example, http://www.nas.nasa.gov/~aftosmis/publications/aiaa99-0776.ps.gz

Chris Hennes