# Collision Detection

This is a simple question which probably requires a complex answer, but here goes:
What is an easy, yet efficient way to implement collision detection for a 3d game using different sized (and shaped) objects?

Since you said easy and efficient but not accurate , try bounding spheres.

Calculate the radius of a sphere that would enclose each of your objects. Then if the distance between the centers of two objects is greater than the sum of their radii, they have collided.

– Zeno

yah i’m familiar with that idea. my problem is the strategy of my checking. everytime i move the player, do i check it against all objects? this is taxing, is there a better way to do this?

Of course collision detection has nothing to do with OpenGL, but anyway . How you optimize collision detection is largely dependent on how your game engine (assuming it is a game engine) is organized. There is no one way. But that being said, there are some generalities that most methods have in common. Most game engines partition space in one fashion or another. Then in order to optimize collision detection, you just test one object against the other objects in the same partition. Also, collision detection of objects against a static world can be further optimized by using a pre-calculated collision map.

[This message has been edited by DFrey (edited 03-01-2001).]

nothing to do with OpenGL… sorry. But there are just so many smart people here!
yah i’ve been thinking about partitioning the space of my map and its objects (which are static in the sense that they aren’t mobile). Any suggested structures?

Almost every space-partitioning scheme uses trees. Octrees, BSP trees, etc. The reason for this is that each time you do a check against a tree node, you eliminate a big chunk of your world in one fell swoop.

For example, an octree would start with a root node that is a box surrounding your world. You then split this box in half in each of it’s three dimensions, creating 8 child boxes (each a node in the tree). You continue this process until you have your space divided as finely as you wish. Usually you divide more where there is more detail, so maybe your criteria would be a minimum number of polygons instead of minimum extents.

You can then insert your dynamic objects into this static world tree each frame, and you only have to check for collisions between objects in the same node (or occasionally adjacent nodes). This will cut out a huge number of possible comparisons.

Good luck.

– Zeno

Zeno, very nice idea. I hadn’t thought of that kind of tree (octree) but I think that’s the one I’ll start with. Thanx!

also just a little warning , a good + acurate collision detection + response is the hardest thing to do bar none in a game engine.so dont expect to solve it quickly

Zed is right. This is a difficult subject with tough implementation issues.

I have been reading / thinking / programming collision detection for the past several months (very part time) and am just getting code working where I can quickly detect and accurately respond to collisions down to the triangle level quickly.

Proud to say I can now detect overlap of 2 700 poly objects about 600 times per second on my PIII-450 . It’s possible to do it both correctly and quickly, but don’t expect to be able to do it in one night.

Make sure you read everything you can about it before starting and pick a method to fit your needs, else you’ll end up redoing it a bunch of times.

– Zeno

I’m making a collision myself and I’m wondering, do any of your collision detection method calculate the time of collision? Can you calculate the exact time of a collision inside a time range (i.e. the time between refreshes)? I know a lot of ppl don’t take time into their equations and it results in objects flying clear through walls if they go fast enough.

My engine eliminates this by considering the vector of the object and if it will collide with any other object. It’s a triangle-triangle collision detection system, but I’ve multiplexed some hacks on top of it to optimize the speed. I’ve got it running fast enough for my intended scale (nothing like 2x700tri @ 600/sec more like 2x500tri @ 30/sec). Problem is, I don’t think I can efficiently handle calculating rotation which the final program will heavily rely on.

So what I want to know is, does any1 know of a fast and realatively accurate way to calculate collisions between rotating objects, and not just IF the overlap, but WHEN they first contact.

For those of you who are mathematicians (you’ll find out what I mean if seriously persue this), I’ve got a method for calculating the collision, but the equations involved will bring a 1GHz P4 to a stand still, so some kind of hack is neccessary. I’ve got an idea, but I need to finish other parts of my engine b4 I try it. I’d still like to hear what you all come up with.

iCOLLIDE is fairly helpful.

check out unc’s site for a lot of good pointers/papers…

laterz,
-akbar A.

Instead of taking time into acount you can check the bounding box/sphere of the viewer angainst the object bounding /box/sphere. The bounding box/sphere must take into acount where the viewer currently is and where it wants to be. This will roughly give an indication of a collision of the player going at any speed. My first (and only) collision detection routine didn’t use this method, it was only a point to triangle detection and so aabb or what ever were not needed, simple vectors sufficed. (a vector was set up from the players position to where he wants to be and this was checked against all triangles.) This shows that time doesn’t have to be taken into acount (well actualy this method is using time) but have col. det. based on a function of time is useful.

I looked to the XCOLLIDE engines at first, but they don’t take into account rotation which I absolutely have to have.

Regular triangle-triangle collision detection isn’t my main concern, it’s how well the collision detection method can calculate rotation too, that’s what’s going to ultimately make or break the cd method I use.

I’m currectly using bound box collision and face normal optimizations to cut down on the number of faces that make it down to triangle-triangle cd level, but once there even calculating a collision between just 2 triangle while taking into accoutn rotation can stop everything cold.

On top of just regular tri-tri cd, the cd method must also account for rotation in time too, that’s where it gets hard. When you account for rotation, you start using trigonometry and calculus. You ultimately end up using Netwon’s method which has to be recursively resolved to an accurate answer, that’s what kills performance. And even if you don’t resolve if far, the equation itself is so taxing you can’t call it even once per qualifying triangle and you actually have to call it at least 15 times, 60 for good results.

I’ve got ideas on hacks around this but I’m hoping there’s a better way than hacking, and a quicker way than calculus.

You need to translate your meshes into some
common space. There’s some trig in there to
set up the matrices involved, but it’s so
little (per object) that it’s in the noise.
Translating into the common space is somewhat
more calculation intensive, but not at all
impossible on current hardware, even for a
hundred objects per frame. You only want to
do this translation if the bounding spheres
intersect.

Once there, you know that each triangle has
swept through some volume during your physics
step. Run intersection between each such
volume in the source and the destination
(which can be further optimized with recursive
bounding sphere structures for your meshes).

Once you know which volume(s) collided, figure
out which one collided the earliest using
simple linear algebra (no Newtonian root
solved needed) and that’s where your point of
contact was. I assume you can pre-compute
the inertial/rotational effect each triangle
colliding will have on your mesh to make the
final effect simple to arrive at.

I appreciate the help but I don’t think you all realize what kinds of collision are possible when rotation is involved.

bgl:
I know what you’re talking about but linear algebra alone won’t account for sinusoidal value changes. The actual point of contact changes with rotations.

In the above example 2 objects’ bound [boxes / spheres] can pass almost directly through each other and never collide. In that same example the roation of one of the object could be just slighty off causing the them to swing into each other just b4 their bound volumes stop intersecting.

Simple math can’t resolve collisions between object with changing sinusoidal values. Linear algebra is simple incapable of resolving sinusoidal collision, it’s a conceptual flaw, you have to use [trig / calculus]. The only way to get around this is with hacked numbers or some slick method.

I don’t expect an immediate answer, it will take some time for serious thought to solve this problem. Judging by the fact that I’ve yet to see game engine (and I’ve seen a lot) with the capability to resolve the time rotational collisions.

Sumectavae -

Maybe I misunderstood your question, but why worry at all about the motion paths of your objects like this? After each time step, they will be in a certain position…just check them in this new position for overlap.

I watched your animation, and my code would (and does) handle situations like that just fine.

The only problem that can occur is if an objects velocity times the change in time between frames is greater than the other object’s width. Then they could pass through eachother. There are lots of ways to make sure this doesn’t happen, though…

– Zeno

That’s my primary concern.

I’ll be employing some many other features along with the collision engine that I’ll only get maybe 30 updates/sec. In that time a bullet could pass straight through a wall, or even more frustrating, a person. I could stretch the bounding shapes ove the time period, but that creates conceptual problems in resolve the actual point of contact, so fast moving objects will be adversely affected.

I absolutely can’t sacrifice calculating the exact time of collision for linear movements, but I’m willing to for rotation. I only need the method to be accurate out to 3 (preferably 5) decimal places in calculating the time of collision.

In the end it will be worth it.

On a more general note, when you come to do the tri-tri intersection tests, it might be possible to use a low-poly version of your models in order to get a speed/accuracy tradeoff.

Iain

In our game, we know the maximum acceleration of each object and use this to determine which objects that are capable of colliding during the current frame. These objects are then simulated in small steps to see if they do. Using bounding spheres/boxes we then go down to a finer level of checking if this is the case. Objects are handled in pairs and inserted in a priority queue.

Thus for lazer shots, that are of constant velocity, we can instantly determine which static objects it won’t have a chance to collide with. Works quite well so far, but we are going to make improvements on it.
(Like using multiple queues for different parts of the world…)

I’m working the gfx-engine, so I don’t know all the innards of the collision checking, but could look it up for you. The algorithm was described somewhere on the net though.

Does your method account for rotation? That’s what will ultimately make or break the engine I use.