2D collision detection

[gabor]

Hi!

Finally I'm back to coding gfx routines. Since I've already created a base for managing sprites in dx9, now I'm looking further. Next stop is collision detection that will be followed by managing animations...

First I'd like to read some ideas about how to implement optimal 2D collision detection? For me optimal means fast and resource saving.
I made some research so I'd like to share what I learnt so far:
The most time consuming part is the pixel-exact matching of sprites to get a more precise detection than simply matching bounding rectangles. This also means that every simple and quick methods should be used to dramatically cut down the number of necessary pixel-exact matchings.
In my mind a 3 level matching has evolved:
1. Use quadtrees to split the 2D world into smaller rectangles. Sprites in the same rectangle (quad) are candidates for further matchings.
2. Use boundary rectangles to get a rough approximation of sprites thus let us quickly decide whether a candidate (marked by step 1) is a real candidate.
3. Use masks and some kind of masking operations to complere the pixel-exact collision detection.
I must admit step 3 is the point I get lost...
And there is the never sataisfying doubt: is my concept optimal? isn't there any other approaches that could be more efficient?

What do you think?

Greets,
Gábor

[Tedd]

I think rectangles are probably cheap enough that you can skip the quadtree -- unless you expect to be checking many more rectangles than there are partitions.
So, every object/sprite has a bounding rectangle - checking for intersection is trivial.
Then... checking for mask intersection could be expensive (AND the two masks, and non-nulls are intersections), but maybe you could quarter the sprite and only check overlapping quarters (can be found in the rectangle check.)

Alternatively, you could quad-tree the sprites themselves (down to 2x2) and then simply check for rectangle intersections; that should be fairly optimal in the number of intersection checks. Whether it's better/faster depends if you can find an efficient method for checking the mask intersection (hardware bitblt is a possibility).