[gameprogrammer] About 2D collision detection

Hi:
I'm new to video game programming and not so new to programming.
I am facing now the collision detection problem on a 2D game made with SDL. I found a rather sofisticated solution for this, so I want to share it and know if it can be considered widely useful and if there is currently some similar implementation over there.

My first try was using simple bounding shapes such us rectangles and circles. Then it became obvious that I need something more precise.

The first natural alternative was to use pixel perfect (PP) collision detection, but then I realized I had lots of images which rotate. That matters because then I might need to have calculated the mask of each image for each possible orientation. There were other things that prevents me from using PP. For example, it is quite unnatural to check swept collisions with PP, and it is more tedious to get a normal vector which explains the contact.

Then, I remembered that Clanlib use polygons for detection of collisions. Polygons overcomes the limitations above comented of PP. And I also remembered that the outline polygons of an image can be automatically calculated, and can be tuned to any desired precision around the image. It seems that intersection of convex polygons can be test in O(log(m+n)) time being m and n the amount of vertexes of each polygon, that's good pay of for its benefits, I think.

The solution I'm making now is:
1-Derive automatically the polygonal outline of an image.
2-Round a little the outline to eliminate superfluous edges and vertexes.
3-Break automatically the polygonal outline into convex components (this was not trivial).
4-Calculate the minimum enclosing disk of each component.
5-Now, when you check for intersection of images check first the disks for intersection, whenever they overlap, test intersection of the polygons within the disks.

¿What do you think?

Regards.


---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html


Other related posts: