Jump to content
  • Advertisement
Sign in to follow this  
gusso

simple collision detection and response for spheres and rectangles

This topic is 3623 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

I'd like to know what are the steps involved in a simplistic collision detection and response for spheres against rectangles and vice versa. The response I'm looking for is probably the inverse of the velocity vector based on the collision plane as well as some force taken away based on the surface the circle hit to begin with. The detection I'm not so sure about this, leaving the time issue behind a simple circle-rect or even point-rect intersection test with some offsetting doesn't seem to work at all because I can't make up which plane the collision occurred at, any ideas? Ideally I'd like to handle simple physics, I already have a basic rigid-body setup I'm working on the collision part now... Thanks.

Share this post


Link to post
Share on other sites
Advertisement
If you're not looking for the most performance critical code, I'd try an ad-hoc breakdown like the following: (There might be an analytic continuous collision contact point detection solution for 2D circle-rectangle if you need to be super-exact)

1) Broad-phase exclusion: Check if the circle center point lies outside a rectangle that is defined by the original rectange, but in which all sides are extruded out the distance of the circle radius r. If so, the circle and rectangle can't intersect. Return NoIntersection.

2) Broad-phase inclusion: Check if the circle center point lies inside the original rectangle. If so, there's an intersection, and a bad one to say so, since even the circle centerpoint has penetrated the rectangle! Could try either one of these approaches:
a) Use e.g. the bisection method to iteratively backtrack in time to find an easier intersection, so that the contact point and normal can be more precisely determined. Return Intersection.
b) Just be lazy and do something like projecting the circle center point outwards onto an rectangle edge along the line defined by the rectangle center and the circle center. This projection would be the contact point, and the rectangle edge normal the contact normal. Return Intersection.

3) Test the individual rectangle edges with an algorithm that computes the nearest point of a line segment to a point. Run that for the line segments and the circle center point, and return Intersection if one of those return true, and NoIntersection if all the edge tests show negative. The contact normal is the edge normal, and the closest point the contact point. (Note that this contact point is not exactly true, but is an approximation.)

For a speedup, you can cull the number of edge segments to test by checking
which one or two of the four line segments of the rectangle "face" the sphere, i.e. if the circle center lies on the positive half-space of the edge normal.

Also, google shows plenty of hits for "circle rectangle intersection".

For the collision response phase, a typical breakdown of velocities into linear and angular parts works fine.

Share this post


Link to post
Share on other sites
simplest is to find the point on the rectangle boundary the closest to the sphere centre. If that point is in the sphere, then you have a collision.

Furthermore, the collision plane to reflect the relative velocity would have its normal going through that closest point, to the centre of the sphere.



struct RigidBody
{
Vector m_position; // position of object
Vector m_velocity; // velocity of object
float m_inverseMass; // inverse of mass. 0.0f if object is static
}

struct Rectangle: public RigidBody
{
Vector m_halfSize; // half size of rectangle.
};

struct Sphere: public RigidBody
{
float m_radius;
};


Vector closestPointToRectangle(const Vector& p, const Rectangle& r)
{
// relative position of p from the point 'p'
Vector d = (p - r.m_position);

// rectangle half-size
Vector h = r. m_halfSize;

// special case when the sphere centre is inside the rectangle
if(fabs(d.x) < h.x && fabs(d.y) < h.y)
{
// use left or right side of the rectangle boundary
// as it is the closest
if((h.x - fabs(d.x)) < (h.y - fabs(d.y)))
{
d.y = 0.0f;
d.x = h.x * sign(d.x);
}
// use top or bottom side of the rectangle boundary
// as it is the closest
else
{
d.x = 0.0f;
d.y = h.y * sign(d.y);
}
}
else
{
// clamp to rectangle boundary
if(fabs(d.x) > h.x) d.x = h.x * sign(d.x);
if(fabs(d.y) > h.y) d.y = h.y * sign(d.y);
}

// the closest point on rectangle from p
Vector c = r.m_position + d;
return c;
}

bool applyReponse(RigidBody& a, RigidBody& b, const Vector& mtd)
{
// inverse masses (for static objects, inversemass = 0).
float ima = a.m_inverseMass;
float imb = b.m_inverseMass;
float im = ima + imb;
if(im < 0.000001f) im = 1.0f;

// separate the objects so they just touch each other
const float relaxation = 0.8f; // relaxation coefficient, arbitrary value in range [0, 1].
a.m_position += mtd * (ima / im) * relaxation;
b.m_position -= mtd * (imb / im) * relaxation;

// collision plane normal. It's the mtd vector, but normalised.
Vector n = mtd;
n.normalise();

// impact velocity along normal of collision 'n'
Vector v = (a.m_velocity - b.m_velocity);
float vn = v.dotProduct(n);

// objects already separating, no reflection
if (vn > 0.0f) return true;

const float cor = 0.7f; // coefficient of restitution. Arbitrary value, in range [0, 1].

// relative collision impulse
float j = -(1.0f + cor) * vn / (im);

// apply collision impulse to the two objects
a.m_velocity += n * (j * ima);
b.m_velocity -= n * (j * imb);

return true;
}

bool collide(Sphere& s, Rectangle& r)
{
Vector c = closestPointToRectangle(s.m_position, r);

// relative position of point from sphere centre
Vector d = (s.m_position - c);

// check if point inside sphere
float dist2 = d.dotProduct(d);
if(dist2 >= s.m_radius*s.m_radius)
return false;

// minimum translation vector (vector of minimum intersection
// that we can use to push the objects apart so they stop intersecting).
float dist = sqrt(dist2);
if(dist < 0.0000001f) return false;

vector mtd = d * (s.m_radius - dist) / dist;

applyReponse(s, r, mtd);
return true;
}



[Edited by - oliii on January 9, 2009 4:22:54 PM]

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!