So I'm starting to make a simple physics engine for my Game Engine. I switched from ODE to build my own because ODE collision detection system checked collisions by current position which allowed fast objects to pass right through some objects. I'm just wondering if collision detection with slow and fast objects is possible. You might be wondering what I mean... Heres an example

Sphere A is at (0,0,5) and the radius is 1
Sphere B is at (0,0,-10) and the radius is 2

Sphere B will move 20 units in the Z direction
so Sphere B' = (0,0,+10)
we'll assume that Sphere A didn't move at all.

Using current collision detection between spheres, Sphere A and Sphere B ARE NOT COLLIDING. However, we know for a fact that for Sphere B to move 20 units in Z it must go through Sphere A. (Which shouldn't happen)

Is there a good way of going about this? And I'm also wanting this to be high performance, so if there are just too many calculations to do to get perfect collision detection is there a way to collide a fast object with a slow object?

What about this? http://en.wikipedia.org/wiki/Sweep_and_prune

If you're interested in knowing how the time of impact of two bounding sphere is computed...
We have two spheres S1 and S2 with centers C1 and C2, radiuses R1 and R2 and velocities V1 and V2 at time t0. We want to know if they will collide and if they do, when.
When they collide, the distance separating the centers of the two spheres is equal to the sum of their radiuses:

length( C1 - C2 ) = R1 + R2 (1)

which implies

( length( C1 - C2 ) )² = ( R1 + R2 )² (2)

The squared length of a vector is equal to its dot product with itself. So

( length( C1 - C2 ) )² = dot( C1 - C2, C1 - C2 ) (3)


(3) in (2) yields:

dot( C1 - C2, C1 - C2 ) = ( R1 + R2 )² (4)

Our spheres being in motion, the position of their centers regarding time, can be described by:
C1 = C10 + V1 * t (4) C10: location of the center of sphere1 at time t0
C2 = C20 + V2 * t (5) C20: location of the center of sphere2 at time t0

C1 - C2 = C10 + t*V1 - C20 - t*V2 = ( C10 - C20 ) + t*( V1 - V2 ) (6)

Let's define
dC = C1 - C2
dV = ( V1 - V2 )

(6) is then rewritten:

C1 - C2 = dC + t* dV (7)

(7) in (4) =>
dot( dC + t* dV, dC + t* dV ) = ( R1 + R2 )² (8)

The dot product is distributive with respect to vector addition (substraction). That means:

dot( C , E + F )
= dot( C, E ) + dot( C, F )

Hence
dot( dC + t* dV, dC + t* dV )
= dot( dC, dC ) + 2t*dot( dC, dV ) + t²*dot( dV, dV )
( dot distributes addition and is commutative )

So (8) becomes:
dot( dC, dC ) + 2t*dot( dC, dV ) + t²*dot( dV, dV ) - ( R1 + R2 )² = 0

This is a second degree equation in t.

At² + Bt + C = 0 with
A = dot( dV, dV )
B = 2dot( dC, dV )
C = dot( dC, dC ) - ( R1 + R2 )²

Solutions:
delta = B² - 4AC

if delta < 0, the two spheres won't collide.
else
t1 = ( -B - sqrt( delta ) ) / 2A
t2 = ( -B + sqrt( delta ) ) / 2A

t cannot be negative, so the solution is the least positive root between t1 and t2.

[Edited by - johnstanp on August 26, 2010 10:26:24 AM]

New to the forums but I'll try to help if i can. You don't really say anything about wanting to know the exact time of collision but if you just want a really rough and quick algorithm for just determining whether or not the collision took place you could turn the sphere into another shape like a a cylinder. You could have the radius of the top of the cylinder be the same as the radius of the sphere and the height of the cylinder be the distance traveled between frames. then run a collision test to see if that cylinder collided with sphere B.

You might run into problems if you are doing things like bullet vs bullet collision or any 2 fast moving objects. If you need something more precise you could even use this algorithm as a check to see if further collision calculations need to be done.

From your post it seemed like you wanted something simple and fast so I hope this helped!

Quote:Original post by deathbychipmunk
You don't really say anything about wanting to know the exact time of collision but if you just want a really rough and quick algorithm for just determining whether or not the collision took place you could turn the sphere into another shape like a a cylinder.

You'd want to use a capsule for this, not a cylinder. (A capsule will correctly represent the shape swept out by the sphere as it moves, and capsules are quite a bit easier to work with than cylinders as far as collision detection is concerned.)