[gameprogrammer] Re: About 2D collision detection

> Well, I guess it depends on how much "rounding" you do on your outline.

I' ve seen quite tight polygons with 10-20 vertexes.

Also are you getting the outline EVERY frame? 

No, no. It is precomputed.

Or if you are just getting the outline when you load the images and then rotating the points on the polygon as the object rotates, thats not so bad.

And aditionally you don't need to rotate all the points. You can rotate just the ones you need for testing the intersection with another polygon.


But then again I once heard someone say "premature optomization is the root of all evil", so if your technique is fast enough for your purposes, that's all that matters :P

I may do such a thing just for curiosity. At the beggining I thought I was optimizing everything. But when I saw the different bottlenecks that arose in the game, I found I have a totally unbalanced missconception on what was expensive and what was not.


On 10/27/06, *Facundo Dominguez - Inco* <fdomin@xxxxxxxxxxx <mailto:fdomin@xxxxxxxxxxx>> wrote:

    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>
    > <mailto: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





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


Other related posts: