3D-Collisions basics

13 02 2009

One thing that is absolutely vital in most games is the actual event when two objects somehow collides.

Be it bullets that collides with it’s target, wheels touching the floor, a paperMario reaching the end of the map or just a FPS-player that tries to walk through a wall, we just need to see whether something is touching something else (especially if inappropriate :) ) Now, there are several ways to detect this and as usual it’s all about processor vs quality. The absolute best and accurate way to do this is to let every single face check with every other single face out there if it has intersected and then dispatch that a collision has occured. Now, this (we call it face <-> face collision) is extremely demanding and even top notch 3D accelerated AAA-titles barely uses it so let’s just put that aside for the mathgeeks and dreamers and let’s look at some realistic aternatives.

Let us start in the other end. How fast can we go??? Well, I say (you can bash me as much as you want to, I have not studied this at all) that he fastest kind of collisiontest you can have is to just make a static numbercheck.

if (mesh.y < 0) { mesh.y = 0}

Yes, we all fid it extremely obvious but sometimes people make things WAY to difficult for them. Still in this game I have used this collisiontype many times where some people would have tried a more demanding approach just for the sake of being dynamic. Just because of the processorpower it takes to detect collisions I have purposely chosen to create a rectangular arena, opposite to the arena I used in my last game. It doesnt have any walls at the moment but when it get walls I don’t have to create some difficult collisioncheck, just a static numbercheck will make the job!

What about the ground?? Well I could have added bumbs in a sandy arena but now I choose a flat one for several reasons.

1. As soon as something like the grenade goes Z < 0 it will bounce up again.

2. When it’s flat and no units will be able to jump/have physics, I can remove all bottom faces of the unit. You should see them, they are all stripped and seethrough from underneath.

3. Putting obstacles on the arena (extra walls, barrels etc) is as easy as Z=0

Now you probably already knew this stupid collisioncheck but I still want you all to remember this simple solution when creating your design for the game. Maybe your 3D pong should go with square walls instead of your freakishly new plasmastyle.

Now, lets start with some “real” collisiontesting then. After the static one, I might be brave enough to say that the next least perfomancedemanding collisioncheck is a single distancecheck. “How far from this object is that object?? Is it to close? then BOOOM!” -style.

In Papervision we got the math already done with it’s  function: DisplayObject3D.distanceTo(otherObj:DisplayObject3D) .  (no it’s not rocketsciencemath either but it’s nice we don’t have to dig out mr.Pythagoras more than needed)

If the distance is lesser than your set value, then you consider it to be a collision. Now, this method is very rarely used but if we enhance it just a liiiiittle bit you will have one of the most common collisiontests in games…

Sphere-collision

When I was a kid, (yes, I promise i have been) I just couldn’t understand how spherecollision could be faster to use than ermm.. other that we will bring up in a short while. Spheres are complicated and as soon as round shapes are involved it means using PI and Sinus and maybe derivata. No, not this time. If you just think of it for a second: distanceTo() is really a sphere. It doesn’t have any direction but checks the distance in EVERY direction building a kind of a “sphere” around the object where the distance is actually the radius of the sphere. Look at this image:

spherecollision

Here I have set a distanceTo limit on the Defender and a distanceTo limit on the grenade so in code it is just:

if (defender.distanceTo(grenade)- (defender.collisionSphereRadius+grenade.collisionSphereRadius) < 0)  { trace(“defender is FUBAR!!!”)}

It’s all about the distance between the objects but we added some kind of radius to each object simulating it’s size. In my game I have set this radius manually and actually do have a “showCollisionSphere” function on each unit and bullet so I can see that it is somewhat correct with the size of the mesh. Still in Papervision3D DisplayObject3D you already have tis kind of collisiondetection in the function: hitTestObject( obj:DisplayObject3D, multiplier:Number=1 ):Boolean

This function takes the furthest pixels away and creates a radius out of that. This could create a collisionsphere that might not be the best for the whole object and therefor there is also a multiplier parameter if you would like to increase or decrease the size of your “sphere”. It works great (I just wanted to create my own flexible collisioncheck but I recommend using the inbuilt one).

Box Collision

What if my object is very flat? It might even be a plane! Creating a collisionsphere around that would just be stupic as it would, in worst cases, trigger collisions way beyond the actual planes location. The other single method that is used just as much as sphere collisions is the box collision. You have probably done it a thousands times already keeping something within a boundary or similar tasks.. does this looks familiar?

if (obj.x > MAX_WIDTH){obj.x = MAX_WIDTH;}

else if (obj.x < MIN_WIDTH){obj.x = MIN_WIDTH;}

if (obj.y > MAX_HEIGHT){obj.y = MAX_HEIGHT;}

else if (obj.y < MIN_HEIGHT){obj.y = MIN_HEIGHT;}

this is actually the technique to use with box collisions. Just check wether a box is within another box.

In every DisplayObject3D that contains a geometryobject you can somewhat easily achieve this as the geometryobject contains a variable with the freakedout name: aabb

This is actually the bounding box we need ( yes it is short for AxisAlignedBoundingBox). It holds all the MAX and MIN values of your mesh in all 3 dimensions so it’s just a matter of creating a lot of “If”‘ rows and you will have your own box collisiontest. Box collision is not as fast as spherecollision but is a very good alternativ for meshes with different proportions.

This was just some simple theory. I will try to stitch this up in some real code in the game to show you later on. Now already I can tell you that if you want to optimize collisioncheck you really should think about WHICH objects really do need to be checked with each other?? Can I remove some of the collisionchecks without harm? All geometry will probably not need to be checked against each other and even some units doesnt have to be checked with some bullets (eg the unit that shot the grenade doesn’t need to be collisionchecked with the nade). I am fond of lists in different ways so I will probably create one now again where objects subscribes to the list where it needs to check with other objects in that particular list.

59

The just-released StreetFighter IV went back from polygon collision to use classical box-collision just to speed up and recreate the classical feel of the game.

Also one small notice is that there are several other types of collisionchecks but thse are by far the most common ones. They are also very easy to mix together and it’s not unusual that game uses BOX <-> SPHERE collisions and POLYGON <->BOX etc.   Hope I could at least enlighten someone with this basic theoretical text. Have a great time creating things I can play!

Advertisements