Archived

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

Timbo_M45

Fastest 2D line-to-rect collision??

Recommended Posts

I''m looking for a collision detection formula for a line (representing the path of a bullet [note that the bullet cannot be seen, as it moves too fast]) or a laser-beam that eminates from the center of the screen, and ends at the edge of the screen (once the bullet is off-screen it no longer exists) in 2D, at any angle. I need to check if the line intersects with a rectangle, the rectanlge is never rotated (it could be represented by the RECT struct), but the line, or path of the bullet can be of any angle. I am looking for speed, as this may at times be done on a frame-by-frame basis, and the target machine dont get much faster then 400MHz. If anyone knows of such a formula or algorythm, or any references that deal with this type of algorythm (eg. a webpage?), I would be greatful if you could share your knowledge.

Share this post


Link to post
Share on other sites
assuming line equation Ax + By + C = 0 you can simply feed in the four edgepoints, calculate 4 times Ax + By + C and check if they are not equal in sign.. (that means, not all points lie on the same side of the line..)

you don''t need all four points, just the two extreme ones (right top and left bottom, or left top and right bottom) for example.. determining wich ones should be a simple min/max math, or so.. dunno..:D if it is integermath, you can optimize a lot with the signs and that with some bitmath, and then parallelize two tests together with mmx if you want (as you only need 2 tests that means you get it into the speed of Ax + By + C >=< something)

dunno if its the fastest way.. but.. who cares? :D (you do..)

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Another thing...if there are lots and lots of "target" rectangles...

construct a rectangle around the laser beam...use the origin as one corner...and where it meets the screen edge as the opposite corner...you can then check if the laser rectangle intersects any of the target rectangles...this would allow you to quickly get rid of any rectangles that lie outside of the laser target area...if the target rectangle intersects the laser rectangle then check if the target rectangles corners are all on one side of the laser line as per the above post.

Share this post


Link to post
Share on other sites