Sign in to follow this  
Moof

Per-pixel collision detection for 2D sprites

Recommended Posts

In my 2D game, I currently have collision detection working fine with bounding boxes. I am attempting to implement collision detection on a per-pixel level, and this is how it is working so far: 1. Check for bounding box collision. 2. Calculate the overlap of the bounding boxes. 3. Check every pixel in the overlap to see if two pixels with an alpha value greater than zero occupy the same location. This works fine, until I start rotating my sprites around. I can still calculate the overlapping region, but since my sprites are rotated I can't figure out how to calculate which pixels in my image (an OpenGL texture on a GL_QUAD) lie within the overlap box. Other solutions I have considered are: - Using multiple bounding boxes/circles for my sprites, rather than per-pixel. I will still need to do a bunch of mathy stuff when my sprites are rotated, but it should be possible to do. (Although checking for collision between a bounding circle and a bounding box might be a little tricky). - Using several collision points for my player sprite, and checking to see whether any of these collision points lie within the bounding box of another sprite each frame. Any suggestions are appreciated. Thanks.

Share this post


Link to post
Share on other sites
There are plenty of ways to do this, but I can't see a way to get much improvement, in the general case, over using the rasteriser to do the work for you. If you are using shaders, this is even easier:

On a separate render-target, simply draw the alpha channels of the two sprites - transformed as usual - onto an empty buffer using a logical-and operator. Then check the area of intersection for any non-empty pixels. Existence of such pixels signifies collision.

What API are you using? I imagine this method would be pretty snappy when implemented correctly under programmable 3D acceleration, but perhaps not so much for a CPU-based pixel renderer.

If this won't do, then you could always sample the sprites under your own rotation operator. It's fairly straight-forward to use a little matrix-mathematics and point-sample the result, but it may be a little heavy on the CPU for large sprites.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
There are plenty of ways to do this, but I can't see a way to get much improvement, in the general case, over using the rasteriser to do the work for you. If you are using shaders, this is even easier:

On a separate render-target, simply draw the alpha channels of the two sprites - transformed as usual - onto an empty buffer using a logical-and operator. Then check the area of intersection for any non-empty pixels. Existence of such pixels signifies collision.

What API are you using? I imagine this method would be pretty snappy when implemented correctly under programmable 3D acceleration, but perhaps not so much for a CPU-based pixel renderer.

If this won't do, then you could always sample the sprites under your own rotation operator. It's fairly straight-forward to use a little matrix-mathematics and point-sample the result, but it may be a little heavy on the CPU for large sprites.


Thanks for the help. I am using OpenGL, and my sprites are textured quads. I imagine it should be possible to render my two colliding sprites to a separate target and check for colliding pixels, although I imagine this may be a little tricky since I am basically dealing with textured polygons. I will take a look into it though, thanks!

Share this post


Link to post
Share on other sites
In your situation, I would approximate each sprite using circles. This could be manually done, or done algorithmically and then stored on file. Each sprite has a list of circles, each with a vector from the center of the sprite and a diameter.

Share this post


Link to post
Share on other sites
Quote:
Original post by shotgunnutter
In your situation, I would approximate each sprite using circles. This could be manually done, or done algorithmically and then stored on file. Each sprite has a list of circles, each with a vector from the center of the sprite and a diameter.


This would work well for most of my sprites, however I have a lot that are rectangular and do not rotate and so I am using bounding boxes for those. Calculating the collision between bounding boxes and bounding circles becomes a little tricky.

Share this post


Link to post
Share on other sites
Quote:
Original post by Moof
Quote:
Original post by shotgunnutter
In your situation, I would approximate each sprite using circles. This could be manually done, or done algorithmically and then stored on file. Each sprite has a list of circles, each with a vector from the center of the sprite and a diameter.


This would work well for most of my sprites, however I have a lot that are rectangular and do not rotate and so I am using bounding boxes for those. Calculating the collision between bounding boxes and bounding circles becomes a little tricky.


Hmm. I would do the entire thing with circles, despite the slight performance hit. Having one large circle that encompasses each of the smaller ones means all kinds of sprite, however rotated or scaled, can be tested against each other.

Here's another idea, however: How about having a collision map lower resolution than the resolution of the image, and scaling / rotating it? Each pixel in the collision map is set if one of the 4 / 9 / etc pixels it represents is set. If the objects are moving, the difference between the 64x64 image and the 16x16 collision map won't be very noticeable.

Share this post


Link to post
Share on other sites
Quote:
Original post by shotgunnutter

Here's another idea, however: How about having a collision map lower resolution than the resolution of the image, and scaling / rotating it? Each pixel in the collision map is set if one of the 4 / 9 / etc pixels it represents is set. If the objects are moving, the difference between the 64x64 image and the 16x16 collision map won't be very noticeable.



I could do that certainly, and it would be more efficient. However, I have to figure out how to do the per-pixel collision detection first and then I can modify my collision mask to have a lower resolution once i figure that out.

Share this post


Link to post
Share on other sites
Quote:
Original post by HappyCoder
What if you were to make an outline of the sprite and store the line segments. then you could do collision detection between the two outlines that are easy to rotate or scale.

Hmm, a good idea, but I am not entirely sure how to do collision detection between line segments.

One idea that comes to mind is to compare every line segment in one entity with every line segment in the other, and to check for intersections. If a line segment in one entity intersects with a line segment in the other, then that is a collision. I will probably try this out.

Share this post


Link to post
Share on other sites
Quote:
Original post by Moof
Quote:
Original post by HappyCoder
What if you were to make an outline of the sprite and store the line segments. then you could do collision detection between the two outlines that are easy to rotate or scale.

Hmm, a good idea, but I am not entirely sure how to do collision detection between line segments.


This way for example:
http://physics.hardwire.cz/index.php?action=show&sortby=order&parent_id=45

Share this post


Link to post
Share on other sites
Quote:
Original post by Hardwire
Quote:
Original post by Moof
Quote:
Original post by HappyCoder
What if you were to make an outline of the sprite and store the line segments. then you could do collision detection between the two outlines that are easy to rotate or scale.

Hmm, a good idea, but I am not entirely sure how to do collision detection between line segments.


This way for example:
http://physics.hardwire.cz/index.php?action=show&sortby=order&parent_id=45


Great, thanks for the links.

Share this post


Link to post
Share on other sites
I am planning to solve this in my game by using one of the objects'
local coordinate system for the coordinate system. Object A would be the center of the world, axis aligned. Then every pixel from object B would be rotated into A's space before testing. The pixels to be tested would be calculated before-hand, to minimize the number of sine/cosine/multiply operations.

And I was also thinking about using "vector" collision detection instead of "raster" collision detection. Every sprite would have a collision map for the image it currently displays, and the collision map would be approximated using line segments. This was already mentioned in this thread.

Share this post


Link to post
Share on other sites
I'm actually dealing with the same situation right now. My bitmaps are changing from frame to frame, so a polygon (vector) based solution would involve a good amount of overhead recomputing the boundary shape. Ideally, I would like to just use the bitmap.

Here is the approach I am going to take:
A bitmap is just a bunch of squares, so we can treat each pixel in a rotated bitmap as an oriented bounding box(OBB). Testing for intersection between two bitmaps becomes testing if any OBB from one image intersects one from the other.

By itself, this is a pretty slow way of doing things. But there are plenty of ways to give it a boost. I plan on doing it by having a series of smaller and smaller bitmaps, where each pixel is set if any of the pixels it represents is set. They are basically mip maps. Each of these pixels also corresponds to a new OBB that contains all of it's interior OBBs. To test two bitmaps, you test their OBBs down the heirarchy.

I'm sure there are a lot of other ways to speed it up, but I think this will be a good start for what I need.

Share this post


Link to post
Share on other sites
Quote:
Original post by Moof
Quote:
Original post by shotgunnutter
In your situation, I would approximate each sprite using circles. This could be manually done, or done algorithmically and then stored on file. Each sprite has a list of circles, each with a vector from the center of the sprite and a diameter.


This would work well for most of my sprites, however I have a lot that are rectangular and do not rotate and so I am using bounding boxes for those. Calculating the collision between bounding boxes and bounding circles becomes a little tricky.


I don't think detecting collisions between bounding boxes and circles has to be much trickier than checking collisions between two circles. For a method that isn't perfectly accurate you could inflate the size of the box by the radius of the circle and then check if the x,y of the circle is contained in the inflated box. This will be accurate for the walls, but the corners will return false positives. However, if that test returns a hit you could do a more precise collision detection by testing a wide version of the box, a tall version of the box, and then testing the corners of the box. The code below should explain the algorithm better than I can with words.

Sorry if the syntax is off, I have been using quite a few languages lately I tend to confuse syntax sometimes. It should be close to c++ syntax.


bool ballRectHitTest(Rect rect, Circle ball){
//Assuming you have a rect class with a pixel hittest method
//and a circle class with a pixel hittest method both with a signature of
//Contains(x,y) --> boolean

//Step 1: Make sure a collision is possible
//This test is accurate for everything except the corners
if (new Rect(rect.x - ball.radius, rect.y - ball.radius, rect.w + ball.radius, rect.h + ball.radius).Contains(ball.x, ball.y) ){
//Test the tall rectangle for a hit and return true on success
Rect rect1 = new Rect(rect.x, rect.y - ball.radius, rect.w, rect.h + ball.radius);
if rect1.Contains(ball.x, ball.y) { return true; }

//Test the wide rectangle for a hit and return true on success
Rect rect2 = new Rect(rect.x - ball.radius, rect.y, rect.w + ball.radius, rect.h);
if rect2.Contains(ball.x,ball.y) {return true; }

//Now test each of the four corners for a hit
Circle circ1 = new Circle(rect.x, rect.y, ball.radius)
if circ1.Contains(ball.x, ball.y) {return true;}

Circle circ2 = new Circle(rect.x+rect.w, rect.y, ball.radius)
if circ2.Contains(ball.x, ball.y) {return true;}

Circle circ3 = new Circle(rect.x, rect.y+rect.h, ball.radius)
if circ3.Contains(ball.x, ball.y) {return true;}

Circle circ4 = new Circle(rect.x+rect.w, rect.y+rect.h, ball.radius)
if circ4.Contains(ball.x, ball.y) {return true;}
}
//If the function runs to the end there was no collision
return false;
}





I personally like the idea of using hit shapes rather than pixel level hit testing.

Share this post


Link to post
Share on other sites
In "Weird Worlds: Return to Infinite Space", I used a rasterizing per-pixel collision detection for collisions between spaceship sprites with good results. The system first transforms one ship to the other's local coordinates, then checks for overlapping pixels using a method similar to what you'd use to draw rotated/scaled sprites in a software renderer.

This test is of course only done if a bounding circle test detects two ships close enough to potentially collide, but the performance is good even in the worst case situations (two ships parked close enough for their bounding circles to overlap)... After all, this check is computationally the equivalent of rendering a rotated sprite, which you can do on hardware a hundred times slower than a common PC.

Pixel-level test is also useful in detecting hits by fast projectiles or laser beams etc. In that case, the collision system "draws" a line through the sprite (with Bresenham or similar) and triggers hit effects at the location where the line hits an opaque pixel. Beam weapons sweeping across a spaceship hull look really cool :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this