Sign in to follow this  
yahn

Line Segment Rectangle Collision

Recommended Posts

yahn    108
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
jyk    2094
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
yahn    108
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this