Jump to content
  • Advertisement
Sign in to follow this  
iSphere

[SDL] How to do collision detection by pixel and with circles?

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

Hey guys is there any easy way to do the following below? I really don't know that much of math yet so I was wondering if you could help me. 1) How can I detect collisions between a circle and a circle? 2) How can I detect collisions between a circle and a quad? 3) How can I get collision detection right down to the pixel? Thank you in advance, iSphere aka 'your pet dog I....I mean your gamedevian...yay!'

Share this post


Link to post
Share on other sites
Advertisement
Well, this is not my field of expertice, but since nobody else has replied I'll throw in some stuff.

First, you probably never ever want to do per-pixel collision detection. It gives you really accurate results, but it's a thusand times slower than a bounding box check. Usually this tradeoff is way to expensive, but it's up to you.

Same goes in 3D; you almost never collision-check each polygon. Instead you wrap the entire object in a couple of big boxes and check them instead.

Secondly, this topic has been covered extensively elsewhere. Here's some links:

gamedev.net/community/forums/ (good)
SDL_Collide.h (!!! looks homebrew but it might work)
gamedev.net/reference/articles/ (decent)
/bitmask/ (if you really really want it)
?page=tutorials/gfxsdl/tut6 (excellent!)

By the way, intersecting circles is the easiest and fastest.
Tutorial: just add radius A to radius B, and check if this is smaller than the distance between their centers.

Share this post


Link to post
Share on other sites
Quote:
Original post by iSphere
Hey guys is there any easy way to do the following below?
I really don't know that much of math yet so I was wondering if you could help me.

1) How can I detect collisions between a circle and a circle?
2) How can I detect collisions between a circle and a quad?
3) How can I get collision detection right down to the pixel?


Well, 'easy' is a relative term. I consider the following solutions fairly easy, but you may or may not. [smile] Since you said you aren't too savvy with the math behind it, I highly recommend doing some review. Solving these problems is generally highschool calibre math, although it may not feel like it.


(1) Circle->Circle

As NQ said, this is just a matter of summing the distance between the two circles' centres and comparing it to their radii. Here's a snippet:


bool circleToCircle(Circle *A, Circle *B)
{
float deltaX = B->x - A->x;
float deltaY = B->y - A->y;
float distance = sqrt( deltaX*deltaX + deltaY*deltaY ); // Standard Pythagorean Theorem
// They hit if their distance is less than this -- the smallest distance they can have from eachother /wo touching
float sumRadii = B->radius + A->radius;
if(distance < sumRadii)
return true;
else
return false;
}






(2) Circle->Quad

A quad, as far as I understand what you're after, we'll define as a 4-sided polygon. Given this, it's probably just as easy to extend this to check any n-sided polygon. Supplied that you wish to detect *intersections* of the circle and the edges of the quad, the idea is to consider each line segment of the quad separately and check each against the circle. If you want to also detect the case where the circle is completely contained within the quad, then you'll need to look into another method. Since you're likely using this for a game of somesort, you shouldn't need to worry about this unless the circle makes a really large movement during a one-frame interval and ends up inside the quad.

We can define each line of the quad (or polygon) in the infamous
y = mx + b
form, where 'm' is slope and 'b' is the y-intercept. To treat these as line segments, we can do a bounding-box check at the end to make sure the intersection point is on the line segment.

A circle is defined by
(x-u)^2 + (y-v)^2 = r^2
, with 'u,v' being the x and y offsets from the origin, and 'r' being the radius. As long as you're familiar with quadratic equations, you should be fine.

Note that I'm mostly fabricating these data structures as I go, but I can define them at the bottom if it helps.


bool circleToPolygon(Circle *A, Polygon *B)
{
float u = A->x, v = A->y;
float r = A->radius;

for(int i=0; i < B->sides.length; i++)
{
Point o = B->sides.first;
Point p = B->sides.second;

// Normal 'y = mx + b' form (NOT a vertical line)
if(o.x != p.x)
{
float m = (p.y - o.y) / (p.x - o.x); // slope = rise / run
float b = o.y - m * o.x; // y-coordinate at x=0 of line


/* So, with our circle and line formulae, we get:
*
* y = mx + b
* (x-u)^2 + (y-v)^2 = r^2
*
* So, we sub 'mx+b' into the circle equation for 'y': (and move r^2 over)
*
* (x-u)^2 + (mx+b-v)^2 - r^2 = 0
*
* Then we expand everything until we get a quadratic form:
*
* x^2 - 2xu + u^2 + (mx)^2 + 2mxb - 2mxv + b^2 - 2bv + v^2 - r^2 = 0
*
* And group terms by 'x':
*
* x^2(m^2) + x(-2u + 2mb - 2mv) + (u^2 + b^2 - 2bv + v^2 - r^2) = 0
*
* And plug it into the quadratic equation, given:
*
* A = m^2
* B = -2u + 2mb - 2mv
* C = u^2 + b^2 - 2bv + v^2 - r^2
*
* X = (-B + sqrt(B^2 - 4AC)) / 2A and
* X = (-B - sqrt(B^2 - 4AC)) / 2A
*
* We need to check to make sure the discriminent (B^2 - 4AC is > 0, too)
*
* If the discriminent is valid, then we really only need to check one
* of the above equations, since we just need *A* point where the line
* and circle intersect.
*
* After we have X, then it's just a matter of plugging that into the 'y=mx+b'
* equation to solve for Y.
*
* Finally, we check the X/Y to make sure it's actually on this line segment.
*
* Oh, right. The code. :)
*/


float A = m * m;
float B = -2*u + 2*m*b - 2*m*v;
float C = u*u + b*b - 2*b*v + v*v - r*r;

float discrim = B*B - 4*A*C;
if(discrim < 0) // Complex number intersection
return false;

float x = (-B + sqrt(discrim)) / (2*A);
float y = m*x + b;

// Finally, the bounding-box check to see if the point is on the line
// segment.
if( ((x >= o.x && x <= p.x) || (x >= p.x && x <= o.x)) &&
((y >= o.y && y <= p.y) || (y >= p.y && y <= o.y)) )
{
return true;
}
// Otherwise, move on to the next line..
}
// If the line is vertical, it's a special case (otherwise slope is undefined, remember?)
else
{
/* A vertical line is much easier to compute; simply the form: "x = c".
* We do the same quadratic jazz as above, but subbing in 'c' for 'x', and
* instead solving for Y. We end up with the following values for A,B, and C
* for our quadratic equation:
*
* A = 1;
* B = -2u;
* C = v^2 + c^2 - 2cu + u^2 - r^2
*
*/

float A = 1;
float B = -2*u;
float C = v*v + c*c - 2*c*u + u*u - r*r;

float discrim = B*B - 4*A*C;
if(discrim < 0)
return false;

float y = (-B + sqrt(discrim)) / (2*A);
float x = c; // The x-coordinate MUST be 'c', since our vertical line only exists there

// Finally, the bounding-box check to see if the point is on the line
// segment.
if( ((x >= o.x && x <= p.x) || (x >= p.x && x <= o.x)) &&
((y >= o.y && y <= p.y) || (y >= p.y && y <= o.y)) )
{
return true;
}
// Otherwise, move on to the next line..
}
}

// No collisions. Dang.
return false;
}





For optimization purposes, it would be worth doing a bounding box check comparing the polygon to the circle to avoid unneeded checks. (ie. comparing boxes that approximate the circle and the quad/polygon)


(3) Pixel->???

I'm not sure what you wanted to check pixels against, but the idea is generally
simpler than the above item. The algorithm is typically to iterate over every
(non-transparent) pixel in the sprite, and compare it as a point in the world
against whatever shape you want. Or, in the case of pixel->pixel collisions between
two bitmaps, checking if the same point on both bitmaps is non-transparent.


As promised, here are the data structures I conjured:


struct Circle
{
float x, y, radius;
}

struct Point
{
float x, y;
}

struct LineSegment
{
Point first, second;
}

struct Polygon
{
LineSegment *lines;
}





Phew. Hopefully this was of some help -- I had forgotten how long the line->polygon check was (with explanations) until I finished writing it out. [grin]

Note that I haven't tested this code myself, but as long as you understand the equations and concepts you should be able to rederive the code yourself. Good luck!

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!