please wait
- Forum
- General C++ Programming
- Line intersection with a triangle.
Line intersection with a triangle.
Nov 27, 2011 at 9:57am
Hi,
I am trying to make an algorithm that can determine the intersection point between a line formed by 2 points A(x1,y1,z1) and B(x2,y2,z2) and a triangle CDE. Can someone please tell me a method that only involves the line and the triangle's coords without any other complicated stuff.
I am trying to make an algorithm that can determine the intersection point between a line formed by 2 points A(x1,y1,z1) and B(x2,y2,z2) and a triangle CDE. Can someone please tell me a method that only involves the line and the triangle's coords without any other complicated stuff.
Nov 27, 2011 at 10:26am
I could tell you how (I think), but it involves a bunch of matrix magic, so if you don't like complicated stuff, I'm not sure if I should bother..
edit: Apparently, I don't have the code any more. Anyway, the idea was to find such matrix that the triangle was with coordinates (0, 0, 0) (1, 0, 0) and (0, 1, 0). It's really simple afterwards. But you do need some understanding of matrices.
edit: Apparently, I don't have the code any more. Anyway, the idea was to find such matrix that the triangle was with coordinates (0, 0, 0) (1, 0, 0) and (0, 1, 0). It's really simple afterwards. But you do need some understanding of matrices.
Last edited on Nov 27, 2011 at 11:03am
Nov 28, 2011 at 3:16pm
I do have an understanding of matrices so if you can explain me your method maybe I will be able to implement it. Thank you for your quick reply : )
Nov 28, 2011 at 4:41pm
I don't remember exactly. First you find a 4*4 matrix M such that
M*(0, 0, 0, 1) = (Cx, Cy, Cz, 1)
M*(1, 0, 0, 1) = (Dx, Dy, Dz, 1)
M*(0, 1, 0, 1) = (Ex, Ey, Ez, 1)
and maybe
M*(0, 0, 1, 0) = (ABx, ABy, ABz, 0),
I'm not sure about this and I think you could get by without it.
You should be able to build such matrix by simply filling its rows or columns with coordinates of point C and vectors CD, CE and AB.
You then find the inverse of this matrix M'
Then find points A' = M'*A and B' = M'*B. Find a scalar k such that A' + k*A'B' = (x, y, 0, 1) where x and y are any numbers. Now, if x > 0 and y > 0 and x+y < 1, it's an intersection.
The intersection point should be C+x*CD+y*CE.
M*(0, 0, 0, 1) = (Cx, Cy, Cz, 1)
M*(1, 0, 0, 1) = (Dx, Dy, Dz, 1)
M*(0, 1, 0, 1) = (Ex, Ey, Ez, 1)
and maybe
M*(0, 0, 1, 0) = (ABx, ABy, ABz, 0),
I'm not sure about this and I think you could get by without it.
You should be able to build such matrix by simply filling its rows or columns with coordinates of point C and vectors CD, CE and AB.
You then find the inverse of this matrix M'
Then find points A' = M'*A and B' = M'*B. Find a scalar k such that A' + k*A'B' = (x, y, 0, 1) where x and y are any numbers. Now, if x > 0 and y > 0 and x+y < 1, it's an intersection.
The intersection point should be C+x*CD+y*CE.
Last edited on Nov 28, 2011 at 4:43pm
Nov 28, 2011 at 7:26pm
I like the idea of mapping the triangle to (0,0,0), (1,0,0), (0,1,0). Here is how I would do it
1. Subtract one of the triangle vertices from all 3 triangle points, maybe C
C' = (0,0,0)
D' = D-C
E' = E-C
at this point there is a detectable degenerate case where the triangle is squashed to a line, handle this if you need to
2. Construct D'' = D'/|D'|^2, E'' = E'/|E'|^2, F'' = D''xE''/|D''xE''|^2, write these as rows in a matrix M. This is a change of basis from the triangle coords to the (1,0,0), (0,1,0) coords. The total transformation of an arbitrary point x is M*(x-C)
3. Apply this transformation to the points A and B, A' = M*(A-C), B' = M*(B-C)
there are now various cases
i. Another degenerate case - both A' and B' have very small sized z coordinates, => the line is in the same plane as the triangle - you decide how to handle
ii. Both A' and B' have z coordinates with the same sign - the line segment does not cross the plane => no crossing
iii. The line segment does cross the plane, need to find where
Let alpha = B'z/(A'z-B'z). The point the line segment crosses the plane is P = alpha*A' + (1-alpha)*B'
We then just look at the x and y coordinates of P and see if it is in the triangle (0,0), (1,0), (0,1), i.e. Px>0 and Py>0 and Py<1-Px
1. Subtract one of the triangle vertices from all 3 triangle points, maybe C
C' = (0,0,0)
D' = D-C
E' = E-C
at this point there is a detectable degenerate case where the triangle is squashed to a line, handle this if you need to
2. Construct D'' = D'/|D'|^2, E'' = E'/|E'|^2, F'' = D''xE''/|D''xE''|^2, write these as rows in a matrix M. This is a change of basis from the triangle coords to the (1,0,0), (0,1,0) coords. The total transformation of an arbitrary point x is M*(x-C)
3. Apply this transformation to the points A and B, A' = M*(A-C), B' = M*(B-C)
there are now various cases
i. Another degenerate case - both A' and B' have very small sized z coordinates, => the line is in the same plane as the triangle - you decide how to handle
ii. Both A' and B' have z coordinates with the same sign - the line segment does not cross the plane => no crossing
iii. The line segment does cross the plane, need to find where
Let alpha = B'z/(A'z-B'z). The point the line segment crosses the plane is P = alpha*A' + (1-alpha)*B'
We then just look at the x and y coordinates of P and see if it is in the triangle (0,0), (1,0), (0,1), i.e. Px>0 and Py>0 and Py<1-Px
Last edited on Nov 28, 2011 at 9:07pm
Nov 29, 2011 at 5:13pm
Thank you for your posts. I will try to implement them and see how they work.
Nov 29, 2011 at 7:03pm
Sorry, I made a mistake in mine
The matrix M is constructed by writing D', E' and D'xE' as columns. and then taking the inverse.
The rest is the same
The matrix M is constructed by writing D', E' and D'xE' as columns. and then taking the inverse.
The rest is the same
Topic archived. No new replies allowed.