Hi all, there is something i realy need right now, i searched on google but found nothing usefull, so i hope you can help me.
I need to find out if a line in 3D is inside of a Triangle or not, preferable in c#, but in other language would be fine too. And i don't need theory, don't have time for that i need a complete solution. Thanks in advance.
Your question seems oddly specific. Like something one might find on a homework assignment or a test... Why do you need to do this? What have you tried so far? What part are you having trouble with? Answer those questions and maybe we can help you.
This site isn't about handing out fish. It's about teaching people how to fish. :)
- Eck
First, you need to find the plane the triangle lies in. Next find the point of collision between the line and the plane. Then you find the barycentric coordinates of that point relative to the triangle. If all three values of the barycentric coordinates are in the range [0,1], then the point is inside the triangle meaning line intersects the triangle.
Your question seems oddly specific. Like something one might find on a homework assignment or a test... Why do you need to do this? What have you tried so far? What part are you having trouble with? Answer those questions and maybe we can help you.
This site isn't about handing out fish. It's about teaching people how to fish.
- Eck
Right now it is like when you are a fisherman and you meet a starwing painter and he asks you for food and you are like: "Listen here dude, i wont give you any fish but ill teach you how to fish.". In short, im working on something totaly out of my league and i need some quick fix for it, i can't afford to learn to understand how it works.
First, you need to find the plane the triangle lies in. Next find the point of collision between the line and the plane. Then you find the barycentric coordinates of that point relative to the triangle. If all three values of the barycentric coordinates are in the range [0,1], then the point is inside the triangle meaning line intersects the triangle.
That "line and the plane" part looks way to complicated for me.
What level of education do you have?
The math tends to look scary if you haven't seen it before. It isn't really that bad.
Line/plane intersection is a basic formula taught in high school algebra. I'm not sure what age that is in your country, around here that is age 16 or so mathematics. We also learned about taking barycentric coordinates in middle-school trigonometry by about age 14, although I didn't learn it under that name.
By the time you get to college studies, this is one of the early topics they review during linear algebra, which is the study of manipulating lines and coordinates in space. Linear algebra is often a second or third year college course. Linear algebra is really the basis of 3D simulations, so unless you either self-educate on the subject or reach that level of college math in school, it will likely remain beyond you until you do reach that level.
What level of education do you have?
The math tends to look scary if you haven't seen it before. It isn't really that bad.
Line/plane intersection is a basic formula taught in high school algebra. I'm not sure what age that is in your country, around here that is age 16 or so mathematics. We also learned about taking barycentric coordinates in middle-school trigonometry by about age 14, although I didn't learn it under that name.
By the time you get to college studies, this is one of the early topics they review during linear algebra, which is the study of manipulating lines and coordinates in space. Linear algebra is often a second or third year college course. Linear algebra is really the basis of 3D simulations, so unless you either self-educate on the subject or reach that level of college math in school, it will likely remain beyond you until you do reach that level.
Yes i had that in school and i even have done line vs triangles collusions long time ago, but i have successfully forgot all of it and now doing something very different. I guess i was hopping to get a done function that i could just copy paste, this may sound kind of selfish but i don't realy have any choice here, got like two days to finish this program, therefor no time to do it right.
Try finding solutions to the three steps. I could give you some psuedo code right here, but you will learn more if you figure this out yourself.
Intersection of a plane and line
barycentric coordinates of point in triangle
For that last step, you might not actually need to calculate the barycentric coordinates. You may find another method of determining if a point lies inside a triangle you prefer, although barycentric coordinates will be useful if you want to find information such as the texture coordinate of where the line intersections the triangle.
If you are still stuck after working over it a little, then come back with specific questions on what you don't understand. I suggest pulling out a piece of paper and drawing diagrams of the problem.
Yes i had that in school and i even have done line vs triangles collusions long time ago, but i have successfully forgot all of it and now doing something very different. I guess i was hopping to get a done function that i could just copy paste, this may sound kind of selfish but i don't realy have any choice here, got like two days to finish this program, therefor no time to do it right.
Assuming then that you aren't in school, there are quite a few linear algebra libraries that can handle it. Or if you're just stuck on the problem for your job, a codeplex project might be more useful.
After searching some more i found this function, but for it dosn't seem to work, maybe anyone who is better in math can tell what is wrong with it?
bool TestSegmTri(Vector3 rs,Vector3 re,Vector3 v1,Vector3 v2,Vector3 v3)
{
if(Mathf.Sign(v3.z*(re.x*v1.y-v1.x*re.y)+v3.y*(v1.z*re.x-re.z*v1.x)+v3.x*(v1.y*re.z-re.y*v1.z))<=0) return false;
if(Mathf.Sign(v2.z*(re.x*v1.y-v1.x*re.y)+v2.y*(v1.z*re.x-re.z*v1.x)+v2.x*(v1.y*re.z-re.y*v1.z))<=0) return false;
if(Mathf.Sign(v3.z*(re.x*v2.y-v2.x*re.y)+v3.y*(v2.z*re.x-re.z*v2.x)+v3.x*(v2.y*re.z-re.y*v2.z))<=0) return false;
return true;
}
Source: ...
The page seems clear enough. That is one function that serves as a part of the algorithm to detect the existence of the intersection.
You need the rest of the function from the web site for it to work.
Math-wise, in that segment they are using the sign of the dot product of planar intersections to see if is on the inside slabs representing the boundaries of the triangle. It has some drawbacks, notably the inability to see exactly where it happens.
I'd stick with the Moller-Trumbore algorithm presented on that site; it is a fairly common algorithm. Or just go with the already implemented C# version on the CodePlex link given earlier.
