# Deciding how to do collision detection

## Recommended Posts

PrestoChung    334
What do you all think of this implementation of an Octree?

Performance seems to be pretty good, in release mode I tried 2000 balls and the frame rate was still smooth. (And I was only counting needing to simulate on maybe a couple hundred objects).

The only issue I see is that here collisions will be missed if the objects are going too fast: collision only occurs if the objects overlap on a particular timestep.

I guess what I want to know is it feasible to calculate some kind of continuous collision detection in realtime? That is, collision independent of the time-step (my program uses a fixed 10ms timestep). Most cases 10ms should be fine, but depending on the size and relative speed of the object, misses could occur frequently (as in the case of say, a bullet-like projectile).

One of my ideas was to calculate the movement vector over the last frame (this was initially an idea I had in order to check in a portal system if an object had intersected a wall or passed through a portal), and use these vectors as a means of collision detection in the octree.

##### Share on other sites
xytor    136
Space partitioning schemes like octrees are just complicated trivial rejections. If you're having misses, the problem is with your collision algorithm. Work on that first, then implement optimization (if, after profiling, you even need it at all).

Anyway, using the movement vector for collision is great. You can, for example, do line segment-box collision with the line segment being derived from the movement vector. Then, just place a dummy box at next frame's position and check that too.
These two checks will eliminate misses due to speed (assuming you are using box collision. If not, replace the word box with whatever you're using).

The second problem is collision resolution. You're going to want to save the collision point from the line segment-box collision for your resolution. For example, if your object is supposed to bounce on collision, don't bounce it the full amount when detecting collision this way. Instead, calculate its bounce amount by taking into account how far away it is when the collision was detected (the distance between the collision point and the object).

[Edited by - xytor on November 15, 2010 11:05:30 AM]

##### Share on other sites
Burnt_Fyr    1665
The term your looking for, for continuous collision, is a swept test. Basically the aabb/obb/bs is swept from it's LKP(last known position), to it's current position, and the volume created is used as the collision shape. A BS for instance, would become a capsule. If your only missing collisions on VeryFastObjects, such as bullets, it's probably better to just use some type of ray casting.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account