Posts Tagged ‘continuous collision detection’

h1

CCD stuff

October 21, 2008

Aaah, the many ways of doing continuous collision.  After looking at conservative advancement in Box2D, I realized it just wasn’t what I needed.  I wanted a process that could finish in one iteration.  So I started looking at sweep tests, and my first was circle-circle sweeps.

Basically circle-circle sweeps are a quadratic equation, where A is the relative velocity squared, B is two times the relative velocity dotted with their relative position, and C is their relative position squared minus the sum of their radii squared.  BLARGH!  So, here’s the math:

v is a vector describing their relative velocity
p is a vector describing their relative position

A=v^2
B=2*v*p,
C=p^2-radii^2

Then you just crunch that with the good ol’ quadratic formula and the smallest of your two roots is the time of impact.  The larger root would be the time they separate after passing through eachother, but who the fuck needs that?  Not me.  Here’s a picture.  Joooocy peeectoooor.  Yaaaaah.

Aaaaw yeeeaaaah.  It’s an exact answer too, no dicking around with approximations.

Polygons might be trickier though.  I CAN get an exact answer using extended separating axis, (where each axis’ interval is extended by the velocity component dotted with said axis,) but it is only a result given linear velocity.  When you have screw motion, it becomes approximate, because a lot can change between now and projected time of impact when they rotate.  You may wind up hitting totally wrong, or worse, missing just as badly.  So, I may need conservative advancement for this one, or else I’ll have to dig for papers on Google about more advanced methods my feeble brain can barely comprehend.

More on this later.  For now, I will headbang.  To Dream Theater.

Advertisements
h1

continuous collision detection

October 18, 2008

Do you people think it’s about time?  HUH?  Well, I do.  So, several things are planned for addition soon.  This will involve a lot of lists:

  • 0 degrees of freedom constraint: pivot constraints (the anchor point on each object are forced to share a common point in global space.)  Basically a bar constraint, but with a length of zero.  This is needed because a length of zero creates a singularity in bar constraints.
  • 2 degrees of freedom constraint: groove constraints (probably.)
  • Continuous Collision Detection by means of sweep test + a time of impact advancement method.

In the future, I will probably add force fields, but not just yet, all we have is the global gravity constant for now.  My current collision algorithm is completely discrete, and is as follows:

  1. Update positions by delta time.
  2. Cache AABBs and world transforms.
  3. Check for intersections.
  4. Generate collision contacts and update arbiters.
  5. Do response.

Continuous collision detection is trickier:

  1. Cache swept AABBs and swept world transforms using the Minkowski Sum method or gift wrap method.  With the Minkowski Sum you could do an iterative deformation for orientation movement, but only if you wanted to handle potentially concave hulls.
  2. Check for sweep intersections.
  3. For each sweep intersection calculate the time of impact of the two hulls.  The best method in my opinion is a convex cast, but there are more accurate ways out there.  The time of impact should have a slight slop to it.
  4. Then take each of those and update positions by time of impact and accumulate lost time as delta time minus time of impact, and update the rest by delta time plus time lost in any previous TOI (time of impact) collisions.
  5. Cache world transforms.
  6. Check for intersections.
  7. Generate collision contacts and update arbiters.
  8. Do response.

As you can clearly see, the only complex part is updating of the position based on advanced timing.  After that, it’s just like the discrete method, as none of the actual collision handling is different.  We’re just making sure there is no tunneling, that is, nothing can pass through anything else.  This is a huge undertaking.  As such, this is a big milestone.  I’ll keep people in the loop about progress as much as I feel like it.

Peace  🙂