yahn 108 Report post Posted November 8, 2009 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 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted November 8, 2009 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 youThis 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 slabAs 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. 0 Share this post Link to post Share on other sites
Haladria 132 Report post Posted November 8, 2009 Here's a good collection of different collision tests (yours included): http://www.realtimerendering.com/intersections.html 0 Share this post Link to post Share on other sites
yahn 108 Report post Posted November 9, 2009 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 intersectionBasically 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 0 Share this post Link to post Share on other sites