Jump to content
  • Advertisement
Sign in to follow this  
Moof

Per-pixel collision detection for 2D sprites

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

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
Advertisement
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
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.

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
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!