dcsimg
A Flash Developer Resource Site

Results 1 to 4 of 4

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

  1. #1
    Junior Member
    Join Date
    Jan 2010
    Posts
    2

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

    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

  2. #2
    Junior Member
    Join Date
    Dec 2009
    Posts
    15
    Quote Originally Posted by phibbe@gmx.de View Post
    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.

  3. #3
    Junior Member
    Join Date
    Jan 2010
    Posts
    2

    Find the equivalent intersection point of multi lines in 3D space

    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
    Attached Images Attached Images
    Last edited by phibbe@gmx.de; 01-15-2010 at 03:55 PM.

  4. #4
    Junior Member
    Join Date
    Dec 2009
    Posts
    15
    Quote Originally Posted by phibbe@gmx.de View Post
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center