Ray-Plane Intersection and Ray-Triangle Intersection
Author
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
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.
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.
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! :)
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.
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 :)
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.
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 - 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 - 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement