Sign in to follow this  
makingroulette

ray and triangle collision in 3d

Recommended Posts

I was learning how to do find if a ray intersected a triangle in 3d space. I had got to the stage where i had calculated the intersection point of the ray and the plane that contains the triangle. In order to determine if the ray had intersected the plane in area of triangle I learned about barycentric coordinate space and i didn;t get the purpose of it, because i can up with the following way of determining if the intersection point was inside area of triangle 1. computed the area of the triangle in question 2. computed separatley the area of the three subtriangles using the intersection point in the middle of the triangle 3. added up the area of the three subtriangles of the main triangle. 4. compared area of triangle with totalled area of subtriangles. if they are equal then the point of intersection must be inside the triangle. if they are not equal, i.e. the totalled area of subtriangles is greater than the area of the whole triangle, then the point of intersection lies outside of area of triangle Can anyone tell me if there is a flaw with this method, or is it just lacking in efficienty compared to the routes of calculating barycentiric coordinates. I have tried my method and it seems to work perfectlythe only problem is imprecision with floating point comparison. Thanks for reading i appreciate your feedback

Share this post


Link to post
Share on other sites
Quote:
Original post by makingroulette
Can anyone tell me if there is a flaw with this method, or is it just lacking in efficienty compared to the routes of calculating barycentiric coordinates.

it works, but other methods are more accurate, and way faster.

Share this post


Link to post
Share on other sites
As eelco said, there are better and more efficient methods. What method you need depends on the demands of your application.

Most naive methods will occasionally allow rays to 'fall through the cracks' between triangles. If this is not a problem for you, you could take the relatively simple approach of testing that the intersection point is in front of the three 'edge planes' of the triangle. The code is simple and might look something like this:

for (int i = 0; i < 3; ++i)
{
if ((p - v[i]).Dot(normal.Cross(v[(i + 1) % 3] - v[i])) < 0.0f)
return false;
}

You may have to change the < to a >, or reverse the cross product terms.

If you need more robust intersection, you should look into tetrahedral volumes or Plucker coordinates. Rather than finding the intersection point and testing it for containment in the triangle, these methods determine whether the ray passes on the 'inside' or 'outside' of the triangle edges. If the ray is found to pass inside all three edges, the intersection point can then be reconstructed from the volume/Plucker results.

In order for this test to be fully robust, you need to perform the ray/edge test once for each mesh edge, rather than once for each triangle edge. This means that 'inside' will be >= 0 for triangle A, but <= 0 for its neighbor B that shares that edge. Your data structure would need to maintain this information in some form.

Finally, if this is for raytracing, there are articles devoted to various optimizations, or perhaps altogether faster methods that I'm not aware of. I know it's been discussed on this forum, but I'm not sure where those threads are.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk

Finally, if this is for raytracing, there are articles devoted to various optimizations, or perhaps altogether faster methods that I'm not aware of. I know it's been discussed on this forum, but I'm not sure where those threads are.


Flipcode has some articles on this for raytracing you might want to check them out.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
In order for this test to be fully robust, you need to perform the ray/edge test once for each mesh edge, rather than once for each triangle edge. [...] Your data structure would need to maintain this information in some form.

Small addendum: It's not strictly necessary to have a data structure that deals with this. The important thing is that you perform _exactly_ the same calculation for the edge BC in triangles ABC and BCD. This means that you must order the vertices so that the edge whether given as BC or CB would always be used as, say, BC in the calculations. That way, the result is guaranteed to be the same from one triangle to the next.

Share this post


Link to post
Share on other sites
Quote:
This means that you must order the vertices so that the edge whether given as BC or CB would always be used as, say, BC in the calculations.

If I understand what Christer is saying, given vertices v[] and edge indices i and j, you consider the edge to be ordered v[min(i, j)], v[max(i, j)]. When i > j you would flip the sign of the predicate before testing it - no extra data structures required.

Another possible purpose of the data structure I mentioned, though, is efficiency. The predicate results can be cached per edge, avoiding the duplicate calculations inherent in the above method. Whether the increased memory cost is worth the gains in efficiency would of course depend on the application.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this