Jump to content
  • Advertisement
Sign in to follow this  
yahn

Line Segment Rectangle Collision

This topic is 3174 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've searched online enough to know this is not a trivial task. I don't need the rectangles to be able to rotate, so that makes it a little easier, I think. The only way I can think to do it is to check all four edges of the rectangle for a collision with the line (line line collision). That seems pretty inefficient and I'm sure there is a much better solution. Can anyone tell me how it is done? Thank you

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by yahn
I've searched online enough to know this is not a trivial task.

I don't need the rectangles to be able to rotate, so that makes it a little easier, I think.

The only way I can think to do it is to check all four edges of the rectangle for a collision with the line (line line collision). That seems pretty inefficient and I'm sure there is a much better solution.

Can anyone tell me how it is done?

Thank you
This has been covered a number of times in past threads. Here are some search terms you might try:
line AABB intersection
line OBB intersection
AABB raycast
OBB raycast
AABB slab
OBB slab
As you surmise, performing four segment-segment tests isn't the best way to do it (for at least a couple of reasons). A better solution is the slab-based clipping approach, which you should be able to find a description of using the above search terms.

Share this post


Link to post
Share on other sites
It seems there are two popular algorithms for this. I've read that the slab algorithm is the better of the two, but it seems all the algorithms I have found are nearly identical, so I don't know if this is the right one.

Basically, the algorithm is:

| |
| |
* P0 | |
\ | |
\tymin | |
--------*-----+++++++-----------
\ + +
\ + +
-----------*--+++++++-----------
tymax\ | |
\| |
txmin * |
|\ |
| \ |
| \ |
| \ |
| \|
| *txmax
| |\
| | *P1

(P0.x < P1.x && tymax.x < txmin.x) no intersection


Basically the algorithm is that in order for a line to intersect the rectangle, if the edges of the rectangle are extended, the line would have to intersect a line parallel to the x-axis first then a line parallel y-axis then a line parallel to the x-axis and then a line parallel to the y-axis (or the other way around). If the line does not intersect then it will cross both lines parallel to the y-axis and then both lines parallel to the x-axis (or the other way around).

Is this the right algorithm and do I understand it correctly?

Thank you

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!