Fast 3D Line Segment (float , no thickness) Intersection Detection.

[phibbe@gmx.de]

In my current project I have tons of linear 3D line segments and I want to check its intersections. In the 2D world the line sweep algorithm would solve exactly this problem. Anyone know a solution for the 3D world ? Algorithms ? Collision packages ?

Thank you
Peter

[Freshmaker]

Anyone know a solution for the 3D world ?

Eberly has a segment-segment distance paper on his documentation page. The general approach described is applicable to a number of problems. The point-triangle paper on the same site describes a similar algorithm, for instance.

A second approach with which I am familiar is described in the book Real Time Collision Detection, and references a paper called "On Fast Computation of Distance Between Line Segments", of which I can not find a freely available version. This approach involves finding the closest point between the two lines that the segments sit on, clamping the found point to a segment, and repeating the process for the found point.

I am unaware of the performance differences of the two approaches, but since more information on the first approach given is immediately available, I would suggest attempting it. If you want to try the second approach or want a general resource on the topic of collision detection, Real Time Collision Detection is an excellent book worth buying. Dave Eberly also has a book on the topic, but I do not own it and cannot comment on it.

[phibbe@gmx.de]

Thanx for you answer !

I think I have described the problem imprecisely. The problem is not the function for the intersection of the lines the problem is the quantity of the comparisons to find the knots. Please look at the attached pic.

Thank you

[Freshmaker]

I think I have described the problem imprecisely. The problem is not the function for the intersection of the lines the problem is the quantity of the comparisons to find the knots.

Ahh I see. My mistake.

As for reducing the total number of comparisons made, some sort of broad phase culling scheme could be implemented. If you have already considered this and ruled it out due to the nature of the problem, then I don't really have any other insights to offer.

Otherwise, various spatial partitioning schemes, and possibly sweep and prune, may be worth investigating. I know that, for instance, KD-trees are often associated with good behavior with respect to shooting rays, and so may be a good starting point.