iDevGames Forums
Pixel-based collision detection - Printable Version

+- iDevGames Forums (
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Pixel-based collision detection (/thread-7294.html)

Pixel-based collision detection - skwirl42 - Feb 19, 2003 11:06 AM

I'm looking at implementing pixel-based collision detection in a new game's engine, and I was wondering if there are any fast ways of doing this, beyond checking bounding boxes first.

Here are a few features of the proposed engine, which may or may not help someone with helping me Wink:

- 2D OpenGL based drawing
- non-tile based backgrounds
- different collision classes (weapon vs. ground collisions)

I was thinking maybe there would be some tricks like drawing sprite masks transparently in different colours, and seeing where they intersect, based on the resulting colour, then scan through the pixel buffer for collisions around sprites that can collide.

Perhaps also tricks using the auxiliary buffers in OpenGL, maybe draw the 2D sprites at different depths, then check the depth buffer... really, all I've ever done is rectangle-based collision detection...

If you want to see what I've done in the past, the only game I've ever programmed, with graphics, is available at, it may give you an idea of where I'm coming from.

Pixel-based collision detection - Fenris - Feb 19, 2003 11:44 AM

Really, pixel based collision is about the following steps:

: Do bounding box check
: If they intersect, make a note of where the intersection occurs like so:
| |
| o--+------o
| |XX| |
o-----+--o |
| |
: Then check every pixel (or every other pixel if you think that suffices) in both sprites inside your collision rect (the one marked by XX in the inadequate graphic above), and see if both alphas are full-on (255, 1, or whatever treshold you find suitable). If so, you've got a collision.

Usually, this type of intersection rect is very small, unless you are dealing with fast-moving sprites or very low framerate.

EDIT: Darn smileys! Smile

Pixel-based collision detection - skwirl42 - Feb 19, 2003 11:47 AM

It makes sense, and I pretty much had that in mind. I guess I can just check those pixels in the source images for alpha levels. Thank you for helping me realize I don't have to over-engineer THAT part of it. Smile

Pixel-based collision detection - Fenris - Feb 19, 2003 11:50 AM

Yeah, unless you don't want to subclass madly the different types of geometric collisions you can do. Smile You mentioned ground-object collisions, and those are pretty easy to do - just check if the object BB intersects the ground BB.

Pixel-based collision detection - skwirl42 - Feb 19, 2003 11:56 AM

The ground maybe be non-regular. I plan to have masks which identify the collidable parts of the ground, since the actual backgrounds will simply be straight artwork, no tiles. I want the game to be visually stunning, and I find using tiles tends to take away from that. It's a side-scroller, by the way. Smile I may be wrong though... I'll have to evaluate it once I have a better idea of what the full requirements are.

I'll have bounding boxes around those masks, or bounding lines, as the case may be, and use that as my primary means of detecting collision, then do pixel tests on the ground mask vs the object's mask.

Pixel-based collision detection - hokan - Feb 19, 2003 12:05 PM

I haven't really worked with this kind of stuff but the following seams reasonably efficient if you want to do a pixel based collision detection.

1) Determine if sprite bounding boxes overlap
2) if they do, create a 2D array W x H large (with 32 bit ints),
H = overlap box width / 32 (round up)
W = overlap box height / 32 (round up)
3) The basic idea is that "fill" for each sprite can be represented with 1 bit for each pixel (1 = filled, 0 = empty) in the sprite.
A collision has occurred in strip array[i][j] if:
sprite1_strip binary_and sprite2_strip != sprite1_strip binary_xor sprite2_strip
4) put "sprite1_strip binary_and sprite2_strip" into array[i][j] if you intend to do additional collision checks against its new contents - the array is otherwise redundant.

* you need to figure out which bits of sprite1 and sprite2 that ocupy array[i][j].
* you could work with a bit at a time (rather than 32) which might be simpler but also quite a bit slower
* if the sprites are large and collision detection is time consuming to compute you could always reduce the resolution of the sprites used i.e. only check every 2nd, 3rd, 4th pixel ... which reduces the work to 1/4, 1/9, 1/16 ...

Pixel-based collision detection - Fenris - Feb 19, 2003 12:12 PM

Hokan (or is it HÂkan? Smile ), that's a cool way, doing 32 pixels in one long. Cool stuff. Smile

In addition to Hokan's sprite resolution thingie, you could do a simple BSP map of your sprites - for instance, divide them into left/right half of the sprite, and keep on splitting the sprite into more interesting parts. But for most instances, doing intersection boxes will prove very efficient.

Pixel-based collision detection - Hog - Feb 19, 2003 01:52 PM

you could determine the starting point and the end point of each line in the sprites mask, and intersect those,
sort of like this:
[SOURCECODE] >----------<

and if there is an intersection test columnwise.

Pixel-based collision detection - hokan - Feb 19, 2003 05:38 PM

Quote:Originally posted by c_dev
you could determine the starting point and the end point of each line in the sprites mask, and intersect those,
sort of like this:
and if there is an intersection test columnwise.

This can get somewhat complicated if both sprites can have non-continiouse lines or putting it another way if each line can consist of several segments with start and end points, like this:

[SOURCECODE]>----< >-< >-------<[/SOURCECODE]

If the sprites on the other hand consist of continiouse lines I fail to see the need for a column intersection test, collision will occur if:

s1 = start line1
e1 = end line1
s2 = start line2
e2 = end line2

// part of s1-e1 inside s2-e2
((s1 >= s2 and s1 <= e2) or
(e1 >= s2 and e1 <= e2))
// part of s2-e2 inside s1-e1
((s2 >= s1 and s2 <= e1) or
(e2 >= s1 and e2 <= e1))

Pixel-based collision detection - hokan - Feb 19, 2003 05:41 PM

Quote:Originally posted by Fenris
Hokan (or is it HÂkan? Smile ), ...

Actualy HÂkan but hokan is kind of the ascii version Wink

Pixel-based collision detection - Feanor - Feb 20, 2003 06:28 PM

Here's almost no help, but is not the stencil buffer supposed to be very useful for this kind of thing? When you do a stencil test, you can tell if the last thing you drew was overlapping some other thing or things you have already drawn, or something to that effect. Someone who understands it, please elaborate. Blush

Pixel-based collision detection - skwirl42 - Feb 20, 2003 06:35 PM

I just looked it up to be sure, but the stencil buffer is to allow drawing or disallow drawing for particular pixels. You can use it to do things like mirrors. You draw into the stencil buffer where you want the mirror to be, and nowhere else, then draw your scene backwards, so to speak, and it only gets drawn where the mirror was drawn.

But, I've decided to go with SpriteWorld 3.0, when eventually it gets finished. It's 2D, it uses OpenGL, and has all the nifty-cool features I want. Plus, the license is very permissive.