Archived

This topic is now archived and is closed to further replies.

maikgerth

faster 3d-Line-Line intersection

Recommended Posts

Hi! is there a faster 3D -line- line intersection-test (to find the point when they hit each other) ... probably using the cross product (yes i feel stupid about that question) at the moment im just using the common equation --> (with 3 formulas ... the first one is used whose divisor is not 0) it works but i got the feeling it slows me down thanks -)

Share this post


Link to post
Share on other sites
Well the book Real Time Rendering (which is a very good book) derives this as a fast 3D Line-Line Intersection Test, where lines are in the form of r(t) = O + T*D where O is the point of origin, D is the direction, and T is a scalar defining how far along the line you are.

    
s = det | O2 - O1 |
| D2 | / ||D1 X D2||^2
| D1 X D2 |

t = det | O2 - O1 |
| D1 | / ||D1 X D2||^2
| D1 X D2 |


This looks ugly , so let me explain. This is just saying that the scalar, S, for the first point (which defines the length along the line that we are) is the determinate of the 3x3 matrix which is formed by the x, y, and z componets of the vector formed by O2 - O1 as the first row, the direction vector of the second line as the second row (D2), and the cross product of D1 and D2. This is all divided by the squared magnitude of the cross product of D1 and D2. The same this holds for T, except that D1 is substitude in for D2 on the second row of the matrix.

Also, if ||D1 X D2||^2 equals zero, then the lines are parallel so there is no point of intersection. If the lines are skew, then the S and T parameters represent the points of closest approach.

If the lines are to be treated as line segments, with lines L1 and L2, and the direction vectors D1 and D2 are normalized, then you need to check whether 0 <= s <= 1 and if not then the intersection is rejected. Otherwise, t is computed and tested against the interval 0 to L2, if it is outside, then the line segments do not intersect; otherwise they do.

Note: This all comes from the book Real-Time Rendering by Tomas Moller and Eric Haines, which is the best book that I have ever read. If you want to know more about some fast intersection test and many other things related to real time rendering then I would highly suggest that you check out this book.


Share this post


Link to post
Share on other sites