testing collision between line and triangle
Author
Is there a formula for testing whether a line and triangle intersect? In laman's terms?
[edit] A 3d line represented by 2 3d points and a 3d triangle represented by 3 3d points.
Quote:Original post by devroniousThere are several :)
Is there a formula for testing whether a line and triangle intersect?
Quote:In laman's terms?It depends on what you mean by layman's terms. The algorithms of interest necessarily will involve some geometry and linear algebra, and references that discuss a particular implementation will require some knowledge of a programming language (most likely C or C++). Some references are more clear and immediately accessible than others though, if that's what you mean.
Anyway, Google is your friend here. Good search terms might be 'ray triangle intersection', 'line triangle intersection', 'raytrace', 'raytrace triangle', and so on.
The only caveat here is that not all ray-tri algos are equally robust or equally suited for all situations. So if you want more specific advice, you'll have to provide more information.
Yup, what jyk said [smile].
The companion site from the Real-time Rendering book has a handy chart of links to (a few, but not all) different types of intersection test, including ray-triangle.
http://www.realtimerendering.com/int/
As jyk says, the different algorithms have different criteria, usually depending on what they were developed for. Some will just give you a yes/no answer rather than the point of intersection, some favour storing extra data such as face normals with the triangles, etc.
Most people do usually ignore robustness issues, but later learn not to after trying to debug why their game character falls through 'numerical' cracks between triangles in the ground of their game world 'occasionally'. [wink]
The companion site from the Real-time Rendering book has a handy chart of links to (a few, but not all) different types of intersection test, including ray-triangle.
http://www.realtimerendering.com/int/
As jyk says, the different algorithms have different criteria, usually depending on what they were developed for. Some will just give you a yes/no answer rather than the point of intersection, some favour storing extra data such as face normals with the triangles, etc.
Most people do usually ignore robustness issues, but later learn not to after trying to debug why their game character falls through 'numerical' cracks between triangles in the ground of their game world 'occasionally'. [wink]
The one I use:
1-Find if the line intersects the triangle plane, in case of a segment, it may, it may not, an infinite ray does intersect unless it is paralell to the plane, retrieve the intersection point.
2-Determine if the point lies inside the triangle either using baricentric coordinates, or calculating the area of the 3 triangles descrived by the point and each of the triangle's edges, if all the areas have the same sign, the point is inside the triangle and you have an intersection.
1-Find if the line intersects the triangle plane, in case of a segment, it may, it may not, an infinite ray does intersect unless it is paralell to the plane, retrieve the intersection point.
2-Determine if the point lies inside the triangle either using baricentric coordinates, or calculating the area of the 3 triangles descrived by the point and each of the triangle's edges, if all the areas have the same sign, the point is inside the triangle and you have an intersection.
So we have a line given by 2 3D points:
CVector3D Start;
CVector3D End;
And we also have a triangle given by:
CVector3D Triangle[3];
We want to find the intersection of these 2 objects. We'll begin by representing the line in it's parametric form:
Line(t) = Start + Dir*t, where Dir = End - Start;
This is the equation of our beautiful line. If you plug a value for t between [0.0f,1.0f] it will spit out a point that lies on the line.
If you plug in a t that is greater than 1.0f you'll end up with a point that is on "the right of End".
And finally if you plug in a t that is smaller than 0.0f than you'll end up with a point that is on the left of Start.
I made a picture(you got to admit it's beautiful :) )
Now let's look at the triangle. This triangle lies on an infinite plane. A plane can be represented in many ways, we'll just represent it by it's equation like this:
Plane(P) = P.N + D, where "." means P DOT N. N is a unit length vector that represents the normal of the plane, and D is the distance from the origin to the plane. Imagine it like this. You are at the Origin O(0,0,0) if you start running(really hard :) ) from this point along the normal of the plane about D units then you'll know for sure you arrived exactly on the plane. D is a signed value that means if the origin O(0,0,0) is behind the plane D<0 and if the origin O(0,0,0) is in front of the plane then D>0.
Another picture to illustrate that:
Now if you feel really sparky you'll say: Hmm... If I have the plane equation(the normal and D) then I could find a point on the Plane like this:
O(0,0,0) + N*(-D) = N*(-D).
Think of Plane and Line as functions: the Line takes 1 parameter: a float t. The function Plane takes also 1 parameter: a Point P. If the point lies on the plane then Plane(P)=0, if it is behind the plane then Plane(P)<0 and if it is in front of the plane the Plane(P)>0
Now let's deal intersections. We know that our point will be both on the line and both on the plane. This means if we plug the t associated to the intersection point in the Line equation we'll get 0 and if we plug the intersection in the Plane equation we'll also get 0. Now hold down a minute. Wouldn't be great if we had to plug t on both of the equations? Of course it would. To ahieve this we'll also write the point P from the Plane equation in it's parametric form using the informations from our line. We get:
P.N + D = 0 => (Start + Dir*t).N + D = 0;
Now all we have to do is to solve for t.
(Start + Dir*t).N + D = 0 =>
Start.N + Dir.N*t + D = 0
Dir.N*t = -Start.N - D
t = (-Start.N - D)/Dir.N
Carefull here if Dot(Dir, N) ( Dir.N that is) equals 0.0f with tolerance then the line is parallel to the plane so no intersection.
IntersectionPoint = Start + Dir * t
and that's it.... well that isn't it. We just found if an infinite line intersects an infinite plane. We need line(segment) to triangle intersection.
If t is between [0,1] then we know for certain that our Intersection point lies on the line, if not then it is not on our line so we don't have an intersection.
If (t>0.0f && t<1.0f) then read on else return false;
Now: we have a valid line to triangle intersection if our point(that at this stage we know it lies on the line and also on the plane) is inside the triangle. There are various ways to test if a point is inside a triangle, you could consider every edge as part of a plane pointing inside or outside the triangle. If the point is on the right side of all "edge-planes" then we know for certain that the point lies inside the triangle and we return success :). I'm not that good at drawing this but hopefully the source code attached will clear things up for you.
Hope this clears things up :)
[Edited by - Deliverance on October 22, 2006 2:09:38 PM]
CVector3D Start;
CVector3D End;
And we also have a triangle given by:
CVector3D Triangle[3];
We want to find the intersection of these 2 objects. We'll begin by representing the line in it's parametric form:
Line(t) = Start + Dir*t, where Dir = End - Start;
This is the equation of our beautiful line. If you plug a value for t between [0.0f,1.0f] it will spit out a point that lies on the line.
If you plug in a t that is greater than 1.0f you'll end up with a point that is on "the right of End".
And finally if you plug in a t that is smaller than 0.0f than you'll end up with a point that is on the left of Start.
I made a picture(you got to admit it's beautiful :) )
Now let's look at the triangle. This triangle lies on an infinite plane. A plane can be represented in many ways, we'll just represent it by it's equation like this:
Plane(P) = P.N + D, where "." means P DOT N. N is a unit length vector that represents the normal of the plane, and D is the distance from the origin to the plane. Imagine it like this. You are at the Origin O(0,0,0) if you start running(really hard :) ) from this point along the normal of the plane about D units then you'll know for sure you arrived exactly on the plane. D is a signed value that means if the origin O(0,0,0) is behind the plane D<0 and if the origin O(0,0,0) is in front of the plane then D>0.
Another picture to illustrate that:
Now if you feel really sparky you'll say: Hmm... If I have the plane equation(the normal and D) then I could find a point on the Plane like this:
O(0,0,0) + N*(-D) = N*(-D).
Think of Plane and Line as functions: the Line takes 1 parameter: a float t. The function Plane takes also 1 parameter: a Point P. If the point lies on the plane then Plane(P)=0, if it is behind the plane then Plane(P)<0 and if it is in front of the plane the Plane(P)>0
Now let's deal intersections. We know that our point will be both on the line and both on the plane. This means if we plug the t associated to the intersection point in the Line equation we'll get 0 and if we plug the intersection in the Plane equation we'll also get 0. Now hold down a minute. Wouldn't be great if we had to plug t on both of the equations? Of course it would. To ahieve this we'll also write the point P from the Plane equation in it's parametric form using the informations from our line. We get:
P.N + D = 0 => (Start + Dir*t).N + D = 0;
Now all we have to do is to solve for t.
(Start + Dir*t).N + D = 0 =>
Start.N + Dir.N*t + D = 0
Dir.N*t = -Start.N - D
t = (-Start.N - D)/Dir.N
Carefull here if Dot(Dir, N) ( Dir.N that is) equals 0.0f with tolerance then the line is parallel to the plane so no intersection.
IntersectionPoint = Start + Dir * t
and that's it.... well that isn't it. We just found if an infinite line intersects an infinite plane. We need line(segment) to triangle intersection.
If t is between [0,1] then we know for certain that our Intersection point lies on the line, if not then it is not on our line so we don't have an intersection.
If (t>0.0f && t<1.0f) then read on else return false;
Now: we have a valid line to triangle intersection if our point(that at this stage we know it lies on the line and also on the plane) is inside the triangle. There are various ways to test if a point is inside a triangle, you could consider every edge as part of a plane pointing inside or outside the triangle. If the point is on the right side of all "edge-planes" then we know for certain that the point lies inside the triangle and we return success :). I'm not that good at drawing this but hopefully the source code attached will clear things up for you.
#include <math.h>const float EPSILON = 0.01f;struct tPlane{ CVector3D Normal; float D;};bool LinePlaneIntersection(const tPlane &Plane, const CVector3D &StartLine, const CVector3D &EndLine, float &t){ CVector3D LineDir = EndLine - StartLine; float Denominator = Dot(LineDir, Plane.Normal); if (fabs(Denominator) <= EPSILON) // Parallel to the plane { return false; } float Numerator = Dot(StartLine, Plane.Normal) + Plane.D; t = - Numerator / Denominator; if (t < 0.0f || t > 1.0f) // The intersection point is not on the line { return false; } return true;}bool LineIntersectPolygon(const CVector3D *Vertices, const int NumVertices, const CVector3D &StartLine, const CVector3D &EndLine, float &t){ tPlane Plane; Plane.Normal = Normal(Vertices); Plane.D = - Dot(Plane.Normal, Vertices[0]); float tt; if (!LinePlaneIntersection(Plane, StartLine, EndLine, tt)) return false; CVector3D Intersection = StartLine + (EndLine - StartLine) * tt; int Vertex; for (Vertex = 0; Vertex < NumVertices; Vertex ++) { tPlane EdgePlane; int NextVertex = (Vertex + 1) % NumVertices; CVector3D EdgeVector = Vertices[NextVertex] - Vertices[Vertex]; EdgePlane.Normal = Cross(EdgeVector, Plane.Normal); EdgePlane.Normal.Normalize(); EdgePlane.D = - Dot(EdgePlane.Normal, Vertices[Vertex]); if (Dot(EdgePlane.Normal, Intersection) + EdgePlane.D < 0.0f) return false; } t = tt; return true;}Hope this clears things up :)
[Edited by - Deliverance on October 22, 2006 2:09:38 PM]
Author
thanks guys,
Deliverance, You're awesome! Thanks for the lamans terms. It will take me a week or two of application to understand. That's what I was looking for. I tried googling but came up with ray plane algorithms and wasn't sure how to know if it fell within polygon.
I had actually thought about transforming the line points to the normal of the triangle plane and then checking for intersection that way but it seemed a bit further of a road.
I'll digest this for a while. Thanks again and a big ahhhh!
-Devin
Deliverance, You're awesome! Thanks for the lamans terms. It will take me a week or two of application to understand. That's what I was looking for. I tried googling but came up with ray plane algorithms and wasn't sure how to know if it fell within polygon.
I had actually thought about transforming the line points to the normal of the triangle plane and then checking for intersection that way but it seemed a bit further of a road.
I'll digest this for a while. Thanks again and a big ahhhh!
-Devin
Author
Deliverance,
Two questions. fabs is a function that returns the absolute of the float? ALso what is EPSILON?
Thanks,
Devin
Two questions. fabs is a function that returns the absolute of the float? ALso what is EPSILON?
Thanks,
Devin
Devronious,
Two answers.
1.0 fabs is a function that will return the absolute value of a float. You could write the function yourself but it's easier to access it from the math library. just include this into you're code
#include <math.h>
2.0 EPSILON is a constant with a very small value that is used to compare numbers to 0 with tolerance, basically is used to make a "fuzzy" compare.
you should define it somewhere into you're app like this
const float EPSILON = 0.01f;
I made a little correction to the second image.
:)
Two answers.
1.0 fabs is a function that will return the absolute value of a float. You could write the function yourself but it's easier to access it from the math library. just include this into you're code
#include <math.h>
2.0 EPSILON is a constant with a very small value that is used to compare numbers to 0 with tolerance, basically is used to make a "fuzzy" compare.
you should define it somewhere into you're app like this
const float EPSILON = 0.01f;
I made a little correction to the second image.
:)
Author
Great that explains it. I'm implementing it into a collision test and will examine with debugger to better understand formulas.
-Devin
-Devin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
