Jump to content
  • Advertisement
Sign in to follow this  
gretty

Collision Between Rotated Rectangles: Detects collision when there isn't any

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello

I am using and expanding a function that detects whether two 2d rotated rectangles collide. The function is from here.

My Problem: The function incorrectly detects a collision between the following rectangles.


Rect1 = centreX=0, centreY=0, width=8, height=4 angle=0
Rect1 = centreX=16, centreY=0, width=8, height=4 angle=0
[/quote]

Am I wrong or should those rectangles not collide? How should I edit the function so that it detects pixel perfect collisions between rotated rectangles? I have a feeling I need to edit the last 2 lines but I'm not sure.


/*
Detect collisions between rotated rectangles:

Problem: The function RotRectsCollision() seems to say the following 2 rectangles
collide when I pretty sure they shouldn't right? How can I edit the code to perform
pixel perfect collisions?

Rect1 = centreX=0, centreY=0, width=8, height=4
Rect1 = centreX=16, centreY=0, width=8, height=4
*/
#include <iostream>
#include <math.h>
using namespace std;
struct _Vector2D {
float x, y;
};
struct _RotRect {
_Vector2D C;
_Vector2D S;
float ang;
};
inline void AddVectors2D(_Vector2D * v1, _Vector2D * v2);
inline void SubVectors2D(_Vector2D * v1, _Vector2D * v2);
inline void RotateVector2DClockwise(_Vector2D * v, float ang);
int RotRectsCollision(_RotRect * rr1, _RotRect * rr2);
int main()
{
_Vector2D r1C = {0,0};
_Vector2D r1S = {8,4};
_RotRect r1 = {r1C, r1S, 0};
_Vector2D r2C = {16,0};
_Vector2D r2S = {8,4};
_RotRect r2 = {r2C, r2S, 0};

cout << "Collide: " << RotRectsCollision(&r1, &r2) << endl; // Always returns 1 but shouldn't this NOT collide?
cout << "Collide: " << RotRectsCollision(&r2, &r1) << endl;

system("PAUSE");
return 0;
}
// Function Implementation //
inline void AddVectors2D(_Vector2D * v1, _Vector2D * v2)
{ v1->x += v2->x; v1->y += v2->y; }
inline void SubVectors2D(_Vector2D * v1, _Vector2D * v2)
{ v1->x -= v2->x; v1->y -= v2->y; }
inline void RotateVector2DClockwise(_Vector2D * v, float ang)
{
float t,
cosa = cos(ang),
sina = sin(ang);
t = v->x; v->x = t*cosa + v->y*sina; v->y = -t*sina + v->y*cosa;
}
// Rotated Rectangles Collision Detection, Oren Becker, 2001
int RotRectsCollision(_RotRect * rr1, _RotRect * rr2)
{
_Vector2D A, B, // vertices of the rotated rr2
C, // center of rr2
BL, TR; // vertices of rr2 (bottom-left, top-right)
float ang = rr1->ang - rr2->ang, // orientation of rotated rr1
cosa = cos(ang), // precalculated trigonometic -
sina = sin(ang); // - values for repeated use
float t, x, a; // temporary variables for various uses
float dx; // deltaX for linear equations
float ext1, ext2; // min/max vertical values
// move rr2 to make rr1 cannonic
C = rr2->C;
SubVectors2D(&C, &rr1->C);
// rotate rr2 clockwise by rr2->ang to make rr2 axis-aligned
RotateVector2DClockwise(&C, rr2->ang);
// calculate vertices of (moved and axis-aligned := 'ma') rr2
BL = TR = C;
SubVectors2D(&BL, &rr2->S);
AddVectors2D(&TR, &rr2->S);
// calculate vertices of (rotated := 'r') rr1
A.x = -rr1->S.y*sina; B.x = A.x; t = rr1->S.x*cosa; A.x += t; B.x -= t;
A.y = rr1->S.y*cosa; B.y = A.y; t = rr1->S.x*sina; A.y += t; B.y -= t;
t = sina*cosa;
// verify that A is vertical min/max, B is horizontal min/max
if (t < 0)
{
t = A.x; A.x = B.x; B.x = t;
t = A.y; A.y = B.y; B.y = t;
}
// verify that B is horizontal minimum (leftest-vertex)
if (sina < 0) { B.x = -B.x; B.y = -B.y; }
// if rr2(ma) isn't in the horizontal range of
// colliding with rr1(r), collision is impossible
if (B.x > TR.x || B.x > -BL.x) return 0;
// if rr1(r) is axis-aligned, vertical min/max are easy to get
if (t == 0) {ext1 = A.y; ext2 = -ext1; }
// else, find vertical min/max in the range [BL.x, TR.x]
else
{
x = BL.x-A.x; a = TR.x-A.x;
ext1 = A.y;
// if the first vertical min/max isn't in (BL.x, TR.x), then
// find the vertical min/max on BL.x or on TR.x
if (a*x > 0)
{
dx = A.x;
if (x < 0) { dx -= B.x; ext1 -= B.y; x = a; }
else { dx += B.x; ext1 += B.y; }
ext1 *= x; ext1 /= dx; ext1 += A.y;
}

x = BL.x+A.x; a = TR.x+A.x;
ext2 = -A.y;
// if the second vertical min/max isn't in (BL.x, TR.x), then
// find the local vertical min/max on BL.x or on TR.x
if (a*x > 0)
{
dx = -A.x;
if (x < 0) { dx -= B.x; ext2 -= B.y; x = a; }
else { dx += B.x; ext2 += B.y; }
ext2 *= x; ext2 /= dx; ext2 -= A.y;
}
}
// check whether rr2(ma) is in the vertical range of colliding with rr1(r)
// (for the horizontal range of rr2)
return !((ext1 < BL.y && ext2 < BL.y) ||
(ext1 > TR.y && ext2 > TR.y));
}

Share this post


Link to post
Share on other sites
Advertisement
I quickly looked at your code and it seems that you're using the width and height as half-width and half-height when computing BL and TR. So, your rectangles are actually 16 units wide and 8 units high. So they are touching but not overlapping.

I don't know if it's really your problem, but you should try to step through your code with the debugger to verify that the values being calculated are good.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!