Re: Game levels

[Steve Baker <sjbaker1@airmail.net>]

Bakemono wrote:
> 
> How is collision detection usually done with 3D levels?

Well, there is a bag of cheap tricks and there is complete analytical
correctness.

Which you do depends *critically* on what you are colliding with and
how much CPU time you can dedicate to it.

If you have 300 3D creatures fighting each other on the screen, it's unlikely
that you'll be able to do correct collision detection between them.  Something
cheesey like testing the bounding sphere around each character with others
nearby is likely to be all that you can afford.

On the other hand, if you are considering something like the player aiming
a laser weapon at another character through a sniper sight, you had better
test the collision of that laser bolt with every single polygon along the
way to pretty high precision or the results will suck and upset your users
no end!

Testing a polygon against another polygon is a very costly and difficult
thing to get right.  If you can simplify either the collider or the
collidee down to a simple shape (or a small collection of simple shapes)
then everything gets a heck of a lot easier.

Another key thing is early rejection of things that stand no chance whatever
of being collided with.  Organize your scene as a hierarchy of objects with
bounding spheres around each.  You can test whether two spheres collide
just by comparing the sum of their radii to the distance between their
centers.  With care, you can even avoid the square root.

In my Tux game, I treated Tux as two spheres - one for his head and one
for his body.  Comparing those spheres against the bounding spheres of
the scenery object quickly reduces the collision problem to a small number
of scenery polygons...then I do sphere-polygon tests to narrow things down
to an even smaller list of polygons that intersect Tux's spheres.  I could
then go further and test every one of Tux's polygons against the small set
that intersect his spheres...but the game didn't need that much precision
so I didn't bother.

----------------------------- Steve Baker -------------------------------
Mail : <sjbaker1@airmail.net>   WorkMail: <sjbaker@link.com>
URLs : http://www.sjbaker.org
       http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net
       http://prettypoly.sf.net http://freeglut.sf.net
       http://toobular.sf.net   http://lodestone.sf.net