Jump to content
  • Advertisement
Sign in to follow this  
zaneski13

Fast Moving Primitives Colision Detection

This topic is 3030 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
The solution to your problem is Continuous Collision Detection.
There is a big discussion about it here:
http://bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=4&t=20

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
For the case of two spheres you can also do a "GJK raycast" which will be really fast for that particular case.

For anything but spheres though the minkowski sum deforms under rotational movement and everything becomes a bit more complex.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!