[gameprogrammer] Re: About 2D collision detection

Thanks!
You got me a few tips I didn't think of!

I wonder, yet, whether polygon intersection can be considered cpu intensive ...


Alan Wolfe wrote:

Unless you are making something which requires scientific precision, you are way over thinking this.
*****SUPER IMPORTANT CONCEPT TO ANY NEWBIE GAME PROGRAMMERS ON THE LIST:*****
Remember, as a game programmer, you are not trying to model your game after reality, you are trying to make it look as though you are.
This is an important distinction :P
For a game, you don't need to make perfect collision detection and if you do it will probably use up all your CPU and leave nothing left for something else, you just want it to appear good enough that nobody ever questions your collisions.
You would be FAR better using bounding box collision detection (ie the rectangle idea you were using before). However, when you use bounding boxes, in general the box is going to contain a lot of empty space (perhaps thats why you switched methods even?), to get around this, you shrink the box down a little bit to reduce empty space within the box. This makes it so some REAL collisions don't get counted as collisions, but it saves more false collisions than it reduces real collisions so you net a better collision detection scheme.
If you are hell bent on making a perfect collision detection method though, what I suggest is using bounding box collision as a pre-filter before you do your perfect collision detection.
IE what you do is check to see which bounding boxes overlap, and when you figure out which ones do, then do the perfect but more cpu intensive tests between those to see which are in fact overlapping.
Theres many more collision detection otpomizations and prefilters you can do but this should be good enough for now (:
The game programming gems series has alot of good articles on this subject too FYI!
On 10/26/06, *Facundo Dominguez - Inco* <fdomin@xxxxxxxxxxx <mailto:fdomin@xxxxxxxxxxx>> wrote:

    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





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


Other related posts: