[gameprogrammer] Re: About 2D collision detection

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

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

Also are you getting the outline EVERY frame?  if so, processing the image
to get the outline and then round it off a bit adds to the CPU used per
frame for collision detection.

If you are doing it every frame, what you might think about doing is only
re-getting the outline only when an object rotates but if alot of things are
constantly rotating then this method doesn't help much.

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.

You could do a time trial and see how your method compares to straight up
hit boxes and see how much faster one is than the other (:

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

On 10/27/06, Facundo Dominguez - Inco <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>> 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: