Line intersection in 2D - first collision
Author
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.
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
.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
Check out flipcode.com for some tutorials on collision.
You could probably do a text search on their website for some
articles.
You could probably do a text search on their website for some
articles.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
