- Forum
- General C++ Programming
- Line intersection with a triangle.
Line intersection with a triangle.
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.
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
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 : )
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
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
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.