Collision Detection algorithm between two arbitrarily shaped sprites

[Zcool31]

I don't want to make a new thread, but I have a relevant question. I am not using directX or opengl, but I do have 2D sprites in 2D space. However the sprites might have arbitrary shapes (circle, square, random blob, wheel with hollow center, etc). I do have masks for the sprites (i can tell which pixels the sprite occupies, and which it doesn't).
Using all this, how can I "quickly" calculate the properties of a collision between two such arbitrarily shaped sprites? By quickly, I mean without brute force, checking each pixel one by one.

[MattEvans]

Brute force isn't too bad.. you don't have to check every pair of pixels between the two sprites, you only have to check each pixel space to see if it's occupied twice, and that's not very costly ( it's no more costly than looping all of the pixels in the screen, and the calculation can be performed for all objects at the same time ). This is what a z-buffered application (e.g. OpenGL or DirectX) does to determine occlusion, so it's not really 'inneficient'.

There are some optimizations you can make though.. for any candidate pair of objects, calculate the 2d minimum bounding rectangles of the two sprites, and you will only possibly get a collision within the intersection of these two rectangles. Obviously, if the intersection is empty, you can return false straightaway, otherwise, check the pixels in the intersection.

Heuristically, for two 'convex' sprites, you're more likely to get a collision towards the (actual) centroid of the sprite so check the pixels in the intersection rectangle from the 'outside' in.. and finish the algorithm early if a collision is detected.

You can also group up pixel states into pre-defined groups of 8/16/32/etc pixels, and then it just takes just a bitwise 'and' to check a whole group of pixels at a time. 16 is good because it's square - effectively you can test two 4x4 squares of pixels in one cycle, rather than just testing 1 pair of pixels. Massaging your data into the correct form for that may well take more than you could gain, but, if you have one small moving object and lots of big stationary objects (like most games), then you only have to calculate the grouped states for the stationary objects once.

Beyond that, you can also use spacial partitioning schemes to cull out pairs that have no possibility of colliding. For e.g. start off by assuming that PIXELS are massive, and keep halving the size of a pixel in the areas where collisions occur with bigger pixels, until pixels are normal size. Keep removing candidate pairs at the depth where 'larger than normal' pixels don't register a collision. Essentially, in image terms*, scale the image down so that you have less pixels to check at each iteration, and scale up to normal again at the areas where you need more detail. This is essentially what a 'quadtree' does. http://en.wikipedia.org/wiki/Quadtree.

*obviously, you don't really work with an image to implement it.. but it's useful to visualize it that way.

There are also several other partitioning schemes you could use... Dimension reduction (checking for 'x' collisions and then checking for 'y' collisions) is good in 2D.. Uniform grid partitioning isn't gonna be any benefit, because you already have a uniform grid =)..

These optimizations are probably unecessary and will get in the way of whatever else it is you are doing though. Personally, I would use the first optimization I mentioned, only checking in the intersection rectangle (and perhaps also dimension reduction) for now, and consider the other methods if it ever proves a problem, they aren't particularly difficult to integrate at a later stage in development.