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 on other sites
jyk    2094
Quote:
 Original post by yahnI'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 intersectionline OBB intersectionAABB raycastOBB raycastAABB slabOBB 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 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