Archived

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

Tom

Line intersection in 2D - first collision

Recommended Posts

Hi there. What would you consider the best (fastest) method for determining the first line segment with which a ray collides when fired into a field of line segments? This is probably very similar to determining the first polygon intersection in a portal engine, and I''m not against using a similar approach. Problem is, I need to know what the approach is. I''m working with in two dimenions right now. (I''ll move to 3D later, once I get the basic stuff down.) Think of firing a gun into a field of walls---I need to know which wall gets hit first. I''ve got the formulas for ray-line intersection. Personal assistance is greatly appreciated, as are links to articles that discuss this problem. Thanks for your help.

Share this post


Link to post
Share on other sites
Well, I don''t think that this question can be answered with a definitive best algorithm, but I can give you my opinion .

The main thing you want to do with any intersection routine is make sure that you are testing as few objects as possible. Generally you do this with subdivision schemes, such as octrees, quadtrees, binary trees or whatever method you think is most efficient for your specific domain. In your 2d case with line segments a good scheme would be bsp actually, if you don''t need movement. This is another point, generally you can sacrifice generality for speed, so it really depends on what you want to do.

After you have culled all the useless lines you can decide whether to just brute force it, ie. find all intersection points and keep the closest one. Or, you can try and further optimize the situation, but if you only have 15 lines left, sometimes it is a tradeoff between algorthmic complexity and speed.

Sorry I can''t give any truly specific advice, but this is one of those things where testing and trying really win the day.

PreManDrake

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Check out flipcode.com for some tutorials on collision.
You could probably do a text search on their website for some
articles.

Share this post


Link to post
Share on other sites
PreManDrake: Your response was what I needed to know. A brute-force method seems to be the best option, as long as my sectors are relatively small (and ideally convex). Now, a couple of questions:

I''d like to test each segment beforehand to see if a collision is even possible. Will dot product work for this?

Okay, nevermind. That was the only question.

Share this post


Link to post
Share on other sites