Sign in to follow this  
dave

Ray-Plane Intersection and Ray-Triangle Intersection

Recommended Posts

dave    2187
Hi, i've been scouring google for good clear descriptions on ray-picking. I have done it before bu i was using D3DXIntersect() and the like. This time i am not using meshes, but i am using small enough amount of triangles to brute-force it. Can anyone give me any pointers to tutorials on this simple algebra. ace

Share this post


Link to post
Share on other sites
jyk    2094
Your basic ray-tri test has two steps: finding the point of intersection, if any, between the ray and the triangle plane, and determining if the point of intersection is inside the triangle.

For the first step, google 'ray plane intersection'. This part's pretty easy - just plug the ray equation O+tD into the plane equation P.N = d and solve for t. You can bail if the ray is nearly parallel to or directed away from the plane, or if the ray starts behind the plane and you're culling intersections from the back.

For the second step, google 'point in triangle' or 'point in polygon'. There are various solutions you'll run across. If you see the 'sum of angles' method, skip it. Other methods include cross product comparison, barycentric coordinates, and side planes.

The above method has some flaws that may arise when raytracing against a triangle mesh; due to floating-point error, intersections that occur very close to a triangle edge may not be detected. This can cause rays to pass between triangles where an intersection should occur.

There are more robust algorithms which address this problem. These algorithms involve a little more math than the above, but it's not too bad. If you just want to get something working though, and aren't too worried about robustness, the basic algorithm outlined above will work and is fairly easy to implement.

Share this post


Link to post
Share on other sites
Quote:
Original post by The_Nerd
Why skip the "sum of angles"? It has always worked fine for me...


Because the angle test is (a) nonrobust and (b) slow. It's particularly nonrobust because it involves trig functions, which become very inaccurate at (near) multiples of 90 degrees. This means there's a lot of errors in the floating-point calculations that are part of the test; enough errors that you cannot really compensate for them and get a robust test. The angle test is also incredibly slow because of just the trig functions.

There's a ton of methods that are much faster and also much more robust. Of those, tests based on halfspace testing are generally the best.

Basically, odds are the angle test hasn't always worked fine for you, you just haven't noticed how bad it is! :)

Share this post


Link to post
Share on other sites
oliii    2196
the moller-trumbore test is very good, and very fast (but that's not your priority).

http://www.realtimerendering.com/int/
http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/

another solution. the point-in-triangle half plane algorithm works like this.


bool PointInTriangle(Vector P, Vector* V)
{
Vector N = (V[1] - V[0]) ^ (V[2] - V[1]); // cross product
for(int j = 2, i = 0; i < 3; j = i; i ++)
{
Vector E(V[i] - V[j]); // edge direction
Vector H(P - V[j]); // edge start towards point
Vector F(E ^ N); // cross product. Normal of edge's half plane
float d(H * F); // dot product. sign of point from edge's half plane

if (d < 0.0f) // point on negative half-plane (outside)
{
return false;
}
}
return true;
}




the ray test can be made quite similar.

Basically, it's like looking at the triangle from the point of view, and towards ray direction. The triangle shape will be flattened, and you'll see the point projecting inside or outside the triangle.

For that, it's like replacing N by the ray direction (it is -RayDirection actually). So you also save the normal calculation from the point in triangle test :)



bool PointInTriangle(Vector P, Vector D, Vector* V)
{
for(int j = 2, i = 0; i < 3; j = i; i ++)
{
Vector E(V[i] - V[j]); // edge direction
Vector H(P - V[j]); // edge start towards point
Vector F(E ^ D); // cross product. Normal of edge's half plane
float d(H * F); // dot product. sign of point from edge's half plane

// since D = -N from the Point in triangle function,
// we need to test for POSITIVE half planes.
if (d > 0.0f) // point on positive half-plane (outside)
{
return false;
}
}
return true;
}



you'll also need to check if the plane is before or after. But you can do that after when calculating the point of collision with the triangle plane.

Anyway, the Muller test is good, and it returns the barycentric coordinates of the intersection point as well. So even better.

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