🔒 Locked

Line intersection in 2D - first collision

Started by Tom Oct 4, 2000 at 7:16 PM 2 replies 550+ views

Original Post

Oct 4, 2000 at 7:16 PM

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.

Premandrake

Oct 4, 2000 at 10:44 PM

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

Tom

Oct 5, 2000 at 11:00 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.