Archived

This topic is now archived and is closed to further replies.

CobraMantis

Line Seg & Rect Collisions

Recommended Posts

Mmmk...I''ve got a nice start for my collision detection system thus far, but now I''ve run into a wall. Collisions between two bounding boxes are working, but I now need to be able to test for collisions between a rectangle and a line segment. Anyone have a simple solution for this?

Share this post


Link to post
Share on other sites
First convert the line segment into a full line in the form of y = mx + b, with a defined "leftmost x" and "rightmost x" which form the endpoints of the segment. For each edge of the rectangle, test the intersection of the infinite line with the infinite edge. For example, if your box starts at (0,0) and goes to (5, 5), and your line segment is y = 2x - 4 beginning at -1 and ending at 7, test against the bottom edge of the box y = 0. When y = 0, your line equation becomes 0 = 2x - 4; solving for x we get x = 4/2 = 2. Now look at x=2; it is within the valid range for the line segment (i.e. it is > -1 and < 7) and it is also valid for the edge of the box (i.e. > 0 and < 5). Since the point is valid, return true.

However, if the point were to miss, simply test all of the other edges in a similar manner. If you ever find a valid hit you can instantly return true; otherwise, if you have tested all edges but no points are valid, return false.

Share this post


Link to post
Share on other sites
I see. I figured I would most likely have to do tests with each edge of the box, though I thought this may be rather expensive if there were a large number of collisions to test for. Ah well, I''ll try it out and see what happens. Many thanks, ApochPiQ =)

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
just make a bounding box around the line segment...



Doesn't always work. It is possible for the bounding box of a line to hit the rectangle while the line misses it by far:

___
|../|
|./.|
|/.----
|--|..|
....|__|

a bit crude but should get the point across. [edit: grr... ascii art is tough with variable pitch fonts...)

Although, yes, a bounding box might speed things up for a huge number of collisions, but I doubt it. Especially if you use SIMD to do a couple of line-vs-edge tests at a time.

[edited by - ApochPiQ on July 5, 2003 1:45:01 AM]

Share this post


Link to post
Share on other sites