[SDL] Pixel perfect collision detection

Arne Claus priest at seraphim.info
Tue Jun 28 00:23:54 PDT 2005


> How would I do pixel perfect collision detection?

As already said numerous times inside this thread - in most cases -  
don't.
But - however - I did some thoughts on that, too, also I never  
implemented the following Idea:

Basically you can use 2color-masks (1 and 0) for your objects.
The first thing you do is checking wether those two mask overlap  
(bounding box intersection).
If they do, blit one inside another using AND (I guess you will have  
to write that yourself - don't know if SDL provides this). Now check  
your newly created Mask if any Pixel is !=0. If there is -> collision.

A z-Pyramid like aproach might speed this up - you can create mipmap  
like "level of detail masks", meaning you put together blocks of 4  
pixels in each step until you end up with a required number of pixels  
width/height in your image (e.g. 8x8 or sth. similar that's fast  
enough with brute force). Now you test the smallest map first as  
described above.
On collision go one level deeper but only at the area where the  
intersection took place(!). If you still have collision at the lowest  
mask-level -> collision. otherwise - stop where you are.
That could speed up things a bit (common hierarchical grid method),  
although I'm not totally sure about this - depends on the number of  
operations you do.

However - this method has some downsizes, like speed and the fact,  
that you can't so easily calculate an accurate penetration depth, but  
If you have to use it, the above approach might(!) be faster than  
brute force testing.

The best way doing collision detection (IMHO) is using polygons /  
circles and some kind of hierarchy, like uniform/hierarchical grid or  
kd-Trees. There are numerous papers on the web about this. The most  
are 3D, but can be easily derived for 2D-cases (most use 2D examples).

Arne
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20050628/41d0ad5f/attachment-0008.htm>


More information about the SDL mailing list