Jump to content

  • Log In with Google      Sign In   
  • Create Account

Line vs Triangle collision in 3D


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 Rasly   Members   -  Reputation: 121

Like
0Likes
Like

Posted 23 August 2014 - 09:10 PM

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.

 

W91Ld.png



Sponsor:

#2 Eck   Crossbones+   -  Reputation: 3356

Like
0Likes
Like

Posted 23 August 2014 - 09:23 PM

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



#3 HappyCoder   Members   -  Reputation: 2887

Like
1Likes
Like

Posted 23 August 2014 - 09:41 PM

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.



#4 Rasly   Members   -  Reputation: 121

Like
1Likes
Like

Posted 23 August 2014 - 10:13 PM

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. smile.png

 

- 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.



#5 frob   Moderators   -  Reputation: 22792

Like
2Likes
Like

Posted 23 August 2014 - 11:17 PM

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.


Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#6 Rasly   Members   -  Reputation: 121

Like
0Likes
Like

Posted 24 August 2014 - 12:00 AM

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.



#7 HappyCoder   Members   -  Reputation: 2887

Like
0Likes
Like

Posted 24 August 2014 - 12:56 AM

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.

 

Plane with a triangle

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.



#8 frob   Moderators   -  Reputation: 22792

Like
1Likes
Like

Posted 24 August 2014 - 01:22 AM


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.


Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#9 Rasly   Members   -  Reputation: 121

Like
0Likes
Like

Posted 24 August 2014 - 05:32 PM

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: http://hugi.scene.org/online/hugi25/hugi%2025%20-%20coding%20corner%20graphics,%20sound%20&%20synchronization%20ken%20ray-triangle%20intersection%20tests%20for%20dummies.htm


Edited by Rasly, 24 August 2014 - 05:36 PM.


#10 frob   Moderators   -  Reputation: 22792

Like
2Likes
Like

Posted 24 August 2014 - 08:27 PM


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.


Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#11 Eck   Crossbones+   -  Reputation: 3356

Like
0Likes
Like

Posted 26 August 2014 - 08:46 AM


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.

 

Except that I offer to feed the fisherman and tell him I'll even give him the fish today AND teach him to fish if he can describe why he's in this position in the first place. But the painter storms off to start pestering other fisherman.

 


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.

 

I'm genuinely curious why you need this and only have 2 days to do it. It doesn't sound like you're in school, so perhaps it's a take-home interview assignment? If so, then you should really get to the solution on your own with guidance rather than just being handed a solution. If I didn't guess right, then please tell me why.

 

You do have a choice. Two days is PLENTY of time to teach you how to write this function and understand why it works. If you can take 5 minutes of that deadline and explain more details about your situation, I'll be more than happy to give you the fish and teach you how to fish. (provided I agree with the why)

 

- Eck



#12 Gaius Baltar   Members   -  Reputation: 275

Like
2Likes
Like

Posted 26 August 2014 - 03:42 PM

I'm just guessing right now, so this might be wrong:

 

First check if the line ever passes the triangle, if yes, take the point where the line passes the triangle and make three more triangles with each of the points of the original triangle and the point like so:

 

7zog0Lp.png

 

 

If the area of the three triangles is equal to the area of the larger triangle, you have yourself an intersection.

I actually had a quick glimpse at a youtube video talking about this kind of intersection, thought it might be worth sharing my two cents.

 

Edit: Here's the video: 


Edited by Gaius Baltar, 26 August 2014 - 04:17 PM.


#13 Rasly   Members   -  Reputation: 121

Like
1Likes
Like

Posted 26 August 2014 - 10:35 PM

I'm genuinely curious why you need this and only have 2 days to do it. It doesn't sound like you're in school, so perhaps it's a take-home interview assignment? If so, then you should really get to the solution on your own with guidance rather than just being handed a solution. If I didn't guess right, then please tell me why.

 

You do have a choice. Two days is PLENTY of time to teach you how to write this function and understand why it works. If you can take 5 minutes of that deadline and explain more details about your situation, I'll be more than happy to give you the fish and teach you how to fish. (provided I agree with the why)

 

- Eck

 

It were 5 days for the whole Test, not just for this function and i did set the time limit myself when i started it. Basically i was trying to write a small simulation in unity3d. Funny is that i found out later that unity3d framework already contains this function, not just for Ray's but for Line's as well ^^

 

I'm just guessing right now, so this might be wrong:

 

First check if the line ever passes the triangle, if yes, take the point where the line passes the triangle and make three more triangles with each of the points of the original triangle and the point like so ...

 

If the area of the three triangles is equal to the area of the larger triangle, you have yourself an intersection.

I actually had a quick glimpse at a youtube video talking about this kind of intersection, thought it might be worth sharing my two cents.

Thanks for that, i like when tutorials have some simply graphic's, i think i understand it better now.
 


Edited by Rasly, 26 August 2014 - 10:36 PM.


#14 Gaius Baltar   Members   -  Reputation: 275

Like
0Likes
Like

Posted 27 August 2014 - 09:06 AM

Thanks for that, i like when tutorials have some simply graphic's, i think i understand it better now.


You're welcome! The thing is, I've never actually done anything in 3d so this is completely theoretical... would be logical though.

 

Also I would be interested to know how one would find the position where the line and triangle pass each other, I could probably figure it out for 2d but it seems more complex for 3d.If anyone knows, would be great to note into my reference book.



#15 Eck   Crossbones+   -  Reputation: 3356

Like
1Likes
Like

Posted 28 August 2014 - 07:19 AM

Careful using this method with computers though since floating point numbers aren't perfect. There's likely to be some rounding error when calculating the sums of the triangles' areas.

 

Here's an article that explains how another algorithm works. 

 

http://geomalgorithms.com/a06-_intersect-2.html

 

I'd have shared it earlier, but it has a C++ solution at the end and I wanted to make sure you weren't "cheating". :)

 

- Eck






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS