Archived

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

Blue*Omega

Collision between rectangles

Recommended Posts

Just getting different opinions... What''s do you think is the fastest way to detect if two rectangles are ovelapping? I already have a method (which I won''t post her for fear of being laughed off the message board) but would like to see what else you guys have got. Just so you all know, i''m using the standard RECT class: typedef struct { int top, left, bottom, right; } RECT Thanx! ^_^ ----------------------------- Vash the Stampede "Love & Peace!"

Share this post


Link to post
Share on other sites
2d, but I guess it doesn''t really matter. It might be nice to know a couple of 3d methods. But yes, if you look at the RECT struct it only has top/right-bottom/left. In order to be 3d you would need a front/back as well.

-----------------------------

Vash the Stampede

"Love & Peace!"

Share this post


Link to post
Share on other sites
I think you just have to "project" the y and x direction intervals to the one ray and check their intersection. ..if both directions have an intersection the the collide. Nothing faster doesn''t exist or at least I think so.

Dave007
dave007@volny.cz

Share this post


Link to post
Share on other sites
I guess if you pretend each rectangle has two diagonals from corner to corner and test for intersection. This won''t work if one of the rectangles is also rotated.

hmm...

so say rectangle one is ((1,1) - (100,100));

so, the equation of the diagonal is y = MX + B

M is the slope, or Y2- Y1
------
X2 -X1

in this case, would be 1.
B is 1 (the offset from zero)
so the equation is Y = X + 1

rectangle two is (100,100) - (1,1)

in this case, Y = -X + 101

To test intersection, the equation is:

X + 1 = -X + 101

which simplifies to:

X = -X + 100
2X = 100
X = 50

Doublechecking:

Y = (50) + 1 = 51
Y = -(50) + 101 = 51

So yes, they do intersect, and they intersect exactly halfway through (X = 50).

Dunno how well any of this translates to computer programming, but just a idea I had

BTW you would need two diagonals for each rectangle, and you would have to perform two tests.

Share this post


Link to post
Share on other sites
Are you counting when one rectangle is completely inside another?

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
rectangle collision detection is female dog to say the least. if yoru rects can rotate, you have a major problem to contend with since most tutorials dont deal with that aspect. my algo handles it quite well though may not be optimal.

first off you will use two version of the bound box, rotated and unrotated. (this was done in an overhead shooter similar to subspace but withoutt he shooting part and ships could collide and not get destroyed so it was kinda like bumber ships)

this algo assumes:
1. that the unrotated version will match an unrotated sprite which makes sense.
2. that points are in 2d space, you could though adapt for 3d space (quite easily actually) once you understand the algo and the concpet behind it.

definations:
sprite1 is the sprite checking for collide
sprire2 is the sprite being checked with (i did it in a class fucntion)
all sprites store their own angle varible which represenst the anbgle at which they are rotated (obviously)
this technique makes more sense if you understand what is being done, which is basically converting coordinate space like in 3d camera transformations.

rotbox1: rotated bound box for sprite1
rotbox2: rotated bound box for sprite2
nonbox1: non rotated bound box for sprite1
nonbox2: non rotated bound box for sprite2
the algo:

1. find the non rotated version of the bounding box of sprite1
2. rotate the rotbox2 with the negeative angle that sprite1 is rotated (converts sprite2box into sprite1 coordinate space)
3. if any of the rotbox2 points are in the nonbox1, you got collision. (simple point in rect check)
4. now the reverse, get nonbox2.
5. rotate rotbox1 using the reverse angle of sprite2
6. if any or rotbox1 points are in nonbox2 then you got collision (simple point in rect check)


this works in the following cases:
1. both sprites are rotated
2. only one sprite is rotated
3. one sprite is totally inside the other sprite
4. actually all cases

i WILL NOT post code regarding this. the algorithm is pretty easy to code and should pose very little resistence. i will however clarify the algo if you need me to, since some of my expliaination may be fuzzy.



Edited by - a person on December 9, 2001 11:57:46 PM

Share this post


Link to post
Share on other sites
The way I do it is check to see if any vertex of one rectangle is inside the other one. Not too robust, but has worked great for me so far If your rectangles are rotating, then its not so easy of course

Share this post


Link to post
Share on other sites
Okay, this is just spun out of thought, but it seems the simplest approach to me (for rotated rects, as was mentioned previously, the passed-in rects can either be the bounding box before rotation (based on the situation, close enough might work) or a new bounding box that is computed based on rotated-box coordinates.

//(assume: typedef struct RECT {int right; int left; int top; int bottom; };

bool Collision2D(RECT box1, RECT box2)
{

bool horizontal = true;
bool vertical = true;

if (box1.right > box2.left) horizontal = !horizontal;
if (box1.left < box2.right) horizontal = !horizontal;
if (box1.bottom > box2.top) vertical = !vertical;
if (box1.top < box2.bottom) vertical = !vertical;

if (horizontal && vertical) return true;

return false;

} // end Collision2D

This will work for overlapping rectangles as well as rectangles that are one inside the other. Not bad for the first thing that came to mind, I guess.

"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt

Share this post


Link to post
Share on other sites
i think you misread my post void*. the alogorithm i posted is for bounding boxes that ARE rotated. so the bound box stays exactly the same except its rotated. in other words you odnt need to make sure you bound boxes are aligned on any axis. yoru technique will not work with rotated rects at all. my system does not use the close enough and should work philosophy. its the exact bound box for a rotated sprite assuming the original bounding box was good. please next time read and understand the post and algorithm before assuming its as simple as you make it.

btw a clarification. you never need to generate a new bound box EVER. simply ensure you have an unrotated and rotated version of the bound box. (ie actually rotate the points of the bound box to match the angle of rotation of the sprite).

is this even making any sense at all? i will repeat again since it is a very important thing baout the algo. it is designed to take abitrary rectangles rotated to ANY angle and detect if there is a collision between them.

Share this post


Link to post
Share on other sites
quote:
Original post by a person
this works in the following cases:
1. both sprites are rotated
2. only one sprite is rotated
3. one sprite is totally inside the other sprite
4. actually all cases



To be accurate, these aren't all the cases.
The the rectangles can be positioned perpendicularly to form the shape of a plus sign (+ ). Here they do collide, but no vertex of one rectangle is inside the other rectangle.

It's true, though, that for most animations this case needn't be handled at all.

Besides, none of the original post and the replies before yours even mentioned rotation. You were the first one to bring it up. Did you honestly misread the question or did you just want to show-off?

Don't worry, I have the same problem.
I wrote a RotRect-RotRect collision detection routine too and I'm looking for a good place to post it. Only that mine really handles all cases, and it's even fast (this sentence can be used for you as a proof that I have your problem too).

Just try not to sound so conceited:
quote:

..my system does not use the close enough and should work philosophy...



Well, I showed you your routine is just close enough and should work. Is that always bad?

quote:

please next time read and understand the post and algorithm before assuming its as simple as you make it



Or should it be you that needs to read the original post better?


Regards,
Oren.

p. s: Blue*Omega, implement an idea like the one suggested by void*'s code. It's just fine.

Edited by - SkatMan on December 11, 2001 7:27:04 AM

Share this post


Link to post
Share on other sites
Thanks for the defense, SkatMan...

a person: I was not trying to post source relating to your algorithm, I was trying to respond to the initial post. (Seemed more relevant). The reason I mentioned rotated-rectangle cases was because you had brought up that scenario, and I was trying to describe two (of several) choices for extending my source for those rotated-rectangle cases.

True, it doesn''t cover all bases, but the original post asked for the fastest way to detect if two rectangles are overlapping, not the most thorough way. Perhaps I should have made myself clearer about that, but I was hoping it would be evident that my code would be different from the other source/algo''s that were posted, seeing as how the original poster stated he was "just getting different opinions".

But I digress, I''m not trying to start a petty argument here, I''m just trying to explain myself a little further.

Blue*Omega: Assuming that the rectangles will not eventually rotate, my code should work fine... if you plan on rotating your sprites then you should go with something akin to a person''s or SkatMan''s algorithm.

"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt

Share this post


Link to post
Share on other sites
heh i completely forgot about that one (where would overlap and cross with all vertices outside the rects), since it never occers in my app (mainly because i try to detect the collision before such a case like that happens os it never occered). thanks for pointing that one out i guess when i said not close enough type, was about the rects are always tight around the sprite (since whan you rotate the sprite the bound box void starts to increase in size if you keep the bound box axis aligned)

he mentioned collision between rects, which I assumed they could be rotated since rectangles are not always axis aligned. maybe he dont have rects that are not axis aligned, then he could ignore my post and use what void* posted. i was not ryting to show, but show insight on another approach to the problem (he did ask for different opions )

i guess i misread what you where saying, sorry about that void* (well i knew the codey oyu psted was not for the algo, but it seemed you were saying my algo would take axis aligned rects and bound the rotated sprite which it does not)

i agree though, an argugment would be silly, i as well merely clarifing what i posted.

i probally should have examined my algo more beofre posting, since it was written a while ago for a now defunct multiplayer space combat game. lets just say other projects always happen to get in the way of other projects. i really shoudl learn to stick to one project instead of expeirmenting so much and creating many unfinshed apps that for the most part are useless

Share this post


Link to post
Share on other sites