Pixel-based collision detection

Apprentice
Posts: 17
Joined: 2006.10
Post: #1
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 http://skwirl.ca/SpaceRat/, it may give you an idea of where I'm coming from.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #2
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:
[SOURCECODE]
o--------o
| |
| o--+------o
| |XX| |
o-----+--o |
| |
o---------o
[/SOURCECODE]
: 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
Quote this message in a reply
Apprentice
Posts: 17
Joined: 2006.10
Post: #3
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
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #4
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.
Quote this message in a reply
Apprentice
Posts: 17
Joined: 2006.10
Post: #5
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.
Quote this message in a reply
Member
Posts: 39
Joined: 2002.04
Post: #6
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.

Notes:
* 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 ...
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #7
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.
Quote this message in a reply
Hog
Member
Posts: 151
Joined: 2002.09
Post: #8
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] >----------<
>--------------<
>------------<
>----------->x<---<
>---------->xxx<----<
>------>xxx<-------<
>-----------<
>-------<[/SOURCECODE]

and if there is an intersection test columnwise.
Quote this message in a reply
Member
Posts: 39
Joined: 2002.04
Post: #9
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:


[SOURCECODE]
s1 = start line1
e1 = end line1
s2 = start line2
e2 = end line2

if
// part of s1-e1 inside s2-e2
((s1 >= s2 and s1 <= e2) or
(e1 >= s2 and e1 <= e2))
or
// part of s2-e2 inside s1-e1
((s2 >= s1 and s2 <= e1) or
(e2 >= s1 and e2 <= e1))
[/SOURCECODE]
Quote this message in a reply
Member
Posts: 39
Joined: 2002.04
Post: #10
Quote:Originally posted by Fenris
Hokan (or is it HÂkan? Smile ), ...


Actualy HÂkan but hokan is kind of the ascii version Wink
Quote this message in a reply
Feanor
Unregistered
 
Post: #11
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
Quote this message in a reply
Apprentice
Posts: 17
Joined: 2006.10
Post: #12
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.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 2,260 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 21,621 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 4,322 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 14,744 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 4,514 Sep 6, 2009 02:46 PM
Last Post: johncmurphy