Continuous angular collision detection

I'm pretty sure Havok does not do this (AFAIK it always assumes that bodies have no angular velocity during collision detection and constant linear velocity).

There isn't a closed form solution to do this. The trick is called "conservative advancement". It's basically a numerical root finding solution.

Imagine you know at an instant in time that the bodies are not in contact. You can use something like GJK to find the minimum distance between the two bodies. Then, assuming constant velocity and angular velocity and the bounding sphere (centered around the center of mass, which might not be the centroid of the shape), you can calculate an upper bound on the velocity of any point on one body.

vmax (scalar) = linear velocity + bounding sphere radius * abs(angular velocity).

If both bodies are rotating, you can do:

vmax = linear velocity + bounding sphere radius of body 1 * abs(angular velocity of body 1) + bounding sphere radius of body 2 * abs(angular velocity of body 2).

Then, knowing the maximum speed that the two bodies can approach each other, and the minimum separating distance between them, you can get:

time to advance = minimum distance / vmax

You then do simulation time += time to advance. Then use the new simulation time to integrate the motion of either body forward to a new time, and repeat.

Given infinite precision arithmetic, this will always converge to exactly the time of the first collision between either body. If you're using floats it's possible that the time to advance will be below machine epsilon and you'll infinite loop, so it's something to watch out for. Fairly unlikely in normal situations, though.

There are ways to improve the estimate so you can make time to advance larger, but that's the basic idea. I believe this is explained in Chapter 2 of Mirtich's PhD thesis.

Havok does *indeed* consider the angular velocity during a convex sweep!

For CCD considering angular velocity you can use conservative advancement (CA) or bisection.

Here are some links on conservative advancement (best read in the order I posted the links):
http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf
http://www.kuffner.org/james/software/dynamics/mirtich/index.html

Gino v.d. Bergen's publications:
http://www.dtecta.com/papers/jgt04raycast.pdf

And all his GDC presentations which can be downloaded here:
http://www.dtecta.com/interesting/

FAST and CATCH
http://graphics.ewha.ac.kr/FAST/
http://graphics.ewha.ac.kr/CATCH/

You might also google Stephan Redon.


For bisection I recommend looking at Box2D and how Erin Catto computes the TOI. There is no publication on this, but the source is pretty clear and I am sure you will get answers on his forum. Of course this is 2D, but porting to 3D is a great excersise! If I needed to implement CCD this is the route I would take.

As a side note:
All mentioned CCD methods require a stable distance algorithm. So you have to become an expert on GJK as well. I assume you are familar with this, but here are some references (just in case):

Gino v.d. Bergen (as above)
Bullet
Box2D
https://mollyrocket.com/forums/viewtopic.php?t=245 (read forum as well!)
Christer Ericson's excellent book "Real-Time Collision Detection"

Regarding the video I like to point out that I just found examples where Casey's observations will fail and report false positives (I might post this on the Mollyrocket forum). For a boolean query this is not important if you use it for visibility queries. For CCD this is a nightmare.



HTH,
-Dirk

Quote:

Original post by DonDickieD Havok does *indeed* consider the angular velocity during a convex sweep!

Convex sweep? You mean linear casting? Linear casting in Havok assumes no rotation during the cast. You can tell just by looking at functions for linear casting. Like hkpWorld::linearCast. It takes a collidable (shape + transform) and a linear cast input. There isn't anywhere to specify an angular velocity.

Quote:

For bisection I recommend looking at Box2D and how Erin Catto computes the TOI. There is no publication on this, but the source is pretty clear and I am sure you will get answers on his forum. Of course this is 2D, but porting to 3D is a great excersise! If I needed to implement CCD this is the route I would take.

But the bisection method can potentially miss collisions, right? Conservative advancement will always converge to a root if there is one, which is not something bisection can claim necessarily.

It's probably good enough for government work, but it's not as robust a solution.

Linear cast is something different then a convex cast. At least for my understanding. But you are right a linear cast doesn't consider angular velocity. Anyway the continuous simulation in Havok does consider angular velocity. I am not sure whether there is a separate API call to do this.

You are right about bisection and CA. Anyway, CA can iterate forever and prooves numerically problematic from my experience. Of course you can use CA. I think Bullet uses it for example. Personally I would not use it though.


Cheers,
-Dirk

Quote:

Original post by DonDickieD Linear cast is something different then a convex cast. At least for my understanding. But you are right a linear cast doesn't consider angular velocity. Anyway the continuous simulation in Havok does consider angular velocity. I am not sure whether there is a separate API call to do this.

Hmm... I know Havok does some weird stuff with collisions, like only doing CD for one point in the manifold per frame. So I thought it was doing a strictly linear CCD. But after a bit of digging I think you're right and it's doing some angular checks for CCD.

Quote:

You are right about bisection and CA. Anyway, CA can iterate forever and prooves numerically problematic from my experience. Of course you can use CA. I think Bullet uses it for example. Personally I would not use it though.

Under what circumstances were you finding it giving bad results? The one I can think of involves finding safe delta time = min distance / max velocity being so small that because of machine epsilon current simulation time + safe delta time = current simulation time. Then you're hosed. Are there any other issues you're aware of? I haven't gotten this far but CA is going to be very important for the engine I'm working on right now at home. So it's good to know the limitations.

Quote:

Original post by DonDickieD Anyway the continuous simulation in Havok does consider angular velocity. I am not sure whether there is a separate API call to do this. You are right about bisection and CA. Anyway, CA can iterate forever and proves numerically problematic from my experience. Of course you can use CA. I think Bullet uses it for example. Personally I would not use it though.

Havok uses likely CA or a similar iterative method for angular time-of-impact calculation. Looking at Erin's implementation it seems Box2D conservative advancement is very similar to Bullet's continuous collision detection, but in 2D.

Bullet uses an upper number of iterations during the linear and angular convex cast, but typically it reaches the angular time of impact with less then 4 iterations, and I've never seen it reaching the upper cap in practice.

Do you have some reproduction case of those problems in your experience, Dirk?
Cheers,
Erwin

[Edited by - erwincoumans on December 21, 2009 8:43:36 PM]

Thanks for pointing this out, Erwin!

Cheers,
-Dirk

CA can takes hundreds of iterations in some cases (distance is small and angular velocity is large). The worst case for CA would be something like a hockey puck that is lying flat on the ice, but spinning very fast about the vertical axis.

CA is basically one-sided root finding. This is an awful restriction on a root finder. It is better to bracket the root on both sides. Then you will have many root finding tools you can use.

Quote:

Original post by nire CA can takes hundreds of iterations in some cases (distance is small and angular velocity is large). The worst case for CA would be something like a hockey puck that is lying flat on the ice, but spinning very fast about the vertical axis. CA is basically one-sided root finding. This is an awful restriction on a root finder. It is better to bracket the root on both sides. Then you will have many root finding tools you can use.

Box2D seems to mix the secant rule with bisection

// Use a mix of the secant rule and bisection.      float32 x;      if (rootIterCount & 1)      {         // Secant rule to improve convergence.         x = x1 + (target - f1) * (x2 - x1) / (f2 - f1);      }      else      {        // Bisection to guarantee progress.        x = 0.5f * (x1 + x2);      }

The idea to combine the secant method with bisection method with the goes back to Dekker, see http://en.wikipedia.org/wiki/Brent's_method

Bullet only uses the secant method to find the root, with an upper cap of 64 iterations, but we could interleave it with bisection. Previously we implemented an algebraic method, based on Stephane Redon's work, but we found the root finding to be too sensitive to numerical issues. Interval arithmetic might be another option to find the roots reliably.

In practice, a mix between continuous collision detection and discrete collision detection can be a good compromise:
In the case of that hockey puck, you would embed a sphere inside the puck and perform continuous collision detection with a linear cast on the embedded sphere. Discrete collision detection can give you penetration depth to resolve penetrations due to ignoring angular effects.

Cheers,
Erwin

[Edited by - erwincoumans on December 22, 2009 12:35:58 PM]