#### Archived

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

# Fastest 2D line-to-rect collision??

This topic is 5855 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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

##### 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.

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633317
• Total Posts
3011336
• ### Who's Online (See full list)

There are no registered users currently online

×