[SDL] How to do collision detection by pixel and with circles?
Author
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!'
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.
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.
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 + bA circle is defined by
(x-u)^2 + (y-v)^2 = r^2Note 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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
