Capsule-Capsule Collision in Games

I have had to solve the problem of capsule on capsule collision solution and have found little if any good code or solutions on the 'net.  So here is my solution with code samples.  Also most game physics books discuss the math but not the overall view of how to sequence collision and physics in a game.  I highly recommend the book, Real-Time Collision Detection, by Christer Ericson.  A lot of the code here is derived and adapted from this book.

But first, lots of background about game collision.

Collision
In computer games (like TDL from Sandswept Studios, which I am writing) you need to have the Players and Non-Player Characters (Personas) move around the scene. As they move they should never be allowed to interpenetrate other objects like walls, the ground, and other personas.

You achieve this in two phases:

• First by making a list of all physics objects in the whole world that might interact.  This is the coarse phase, and results in each object having a list of all the other objects to check.
• Second is by moving each physics object with non-zero velocity while holding everything else still, and seeing if it collides with any of the objects it was paired with in the Coarse Phase. If it collides you move that distance, then adjust the velocity by the collision normal vector. This is called Movement Clipping.

Movement should not be confused with hit detection such as punches, baseball bat swings, and rifle shots.  These are solved with a very different strategy that involves triangle meshes and such.

There are several 3D shapes that are useful for movement clipping. A sphere is very simple to solve and is good for roundish objects like rocks, grenades, and such. Boxes can be good for walls and come in two flavors, Axis Aligned Bounding Boxes (AABB), and Object Bounding Boxes (OBB).  An AABB is a box aligned with the X,Y,Z axis and is very fast to solve.  OBB is a box but aligned along the natural axis of the object and moves and rotates with the object. OBB is pretty fast to solve too and is good for walls, and about any boxy objects.

Personas are best represented as Capsules.  A capsule is two spheres with a cylinder between them.  I have heard them called pills or suppositories too. The upper and lower ends are actually half-spheres.

A Capsule.

The reason capsules are so good to use is that they give a very realistic feel to collisions with walls and other Personas.  Also they are reasonably easy to program and compute. One very nice feature is they will slide up stair step due to the lower half sphere without any special programming for stairs.

Capsule represents a player. Lower curve navigates stairs.

Coarse Pass 
So, how do we solve the Coarse Pass?  What you do is every physics object has a AABB.  For each physics object you compare it against every other physics object to see if their AABBs overlap.  There are several complications.  Firstly the objects can be moving so you want to expand the AABB in the direction of motion so it fits the start and end locations of the object.  Not to hard to implement.  The second problem is a bit more complex.  In a large scene (TDL is infinite) there can be a huge number of physics objects.  Comparing all of them to each other is an Order Squared or O2 problem.  For example, 5,000 parts will require almost 25,000,000 comparisons!

So what you have to do is break the problem down so you are only comparing against parts that are reasonably close.  This can be done by grouping parts in some natural way, like all the parts in a given room, and put an AABB around them all and if your physics object does not intersect the big AABB, then ignore all the parts inside.  Often this ends up being a hierarchy of AABBs.

Nested AABBs

In TDL we do an OctTree.  We divided space up into cubes, then each cube is divided in to 8 sub-cubes for about 8 levels deep.  We only check a given physics objects others in it's parent cube, its cube, and all the sub cubes below it.

SubCube division.
From http://software.intel.com/en-us/articles/extending-stl-for-games/

On other major speed up for the Coarse Pass is to only have moving objects do checking against all other objects moving or not. (This particular strategy sped our Coarse Pass up by 32x!)

The result of the Coarse pass is that each Physics Object now has a list of all other potential other objects that might collide with it when it does is move.

Some improvements are to keep two lists, moving and not moving parts. Or keep three lists, moving, not moving but movable, and permanently immovable parts. (like walls)

The Fine Pass
So now we want to take all the parts that are moving and move them, but clip their movement by anything they collide with.  A object will have a certain movement it does in the current game time interval. For example a player moving at 3 meters per second will move 0.18 meters in 1/60th of a second.

What we want to do is check if any of the potential other objects get hit in that 0.18 meters and if so which are the closest. We then take those closest objects and subtract any component of our velocity that is perpendicular to the impact surface normal.

There are two approaches for finding the collision distance.  The first and best is to do a direct linear math solution as to how far you can move before hitting the other object.  This is best because is arrives at an exact distance in one pass of equations.

The other not-so-good approach is to do successive approximations.  This is where you first test the farthest move distance (in our example 0.18 meters) and see if it overlaps the other object.  If it does you cut the distance in half and try again.  On success you add half again, and on fail subtract half again.  The more times you do this the closer you get to the correct distance. 8 iterations get you withing 2 to the -8th power or 1/256 of the total distance within the correct answer.  One approach is to make longer absolute distance do more iterations, and short distances do less.  This can be done with a single tolerance number.  Why would you ever use successive approximations?  Because there are some geometric solutions that get into very complex and ugly math, yet the 'does it overlap' math is very simple. A good example of this is unaligned capsules.

Rounding Errors
One other important issue with solving move distance to hit objects.  Once you have hit the object and adjusted you velocity to be parallel to the hit surface, you bay be just a very tiny bit inside the surface, and you velocity may not be exactly parallel.  On computer the actual math is in binary and there are rounding errors. For example 1 divided by 3 is not 1/3, it is 0.333333333 and the number is not infinite.  So you need to have a small number that is the limit of how close 'equal' is.  In TDL is is called PHYSICS_EPSILON and is 0.0001 meters.

You then have macros (inline functions) such as isEqual, isZero, that are like this...

    inline bool isEqual(float a, float b) { return abs(a - b) <= PHYSICS_EPSILON; }

You also need the same methods for your 3D vector classes.

Now when you check for the collision distance you check whether the velocity is away or parallel (nearly parallel!) to the surface.  If it is it is not a hit.

One other note: Testing for dot products to be small requires a test against PHYSICS_EPSILON squared since a dot product is in essence a multiply.  This can bite you if you are comparing normals for parallel and also comparing velocity values for near zero.  Your dot products can be very small and not appear to be not near zero when they are.

Back to Fine Pass
For the fine pass we now find how far we can move, move there, adjust our velocity by any impacts, subtract how far we moved from the total (the 0.18 meters) and keep doing that until we have moved the full distance, or our velocity hits zero.

Oh, one question you might have, where did our velocity come from in the first place?  Every tick of the game you add gravity to the velocity, and add some velocity according to the controls such as in TDL, the W key makes you move forward.

Capsules
Ok, enough back story. The real intent of this posting is to discuss solutions for capsules and give code examples.

A capsule is defined one of two ways, either points A and B which are the centers of the two spheres, and a radius, or a single point A and a direction and distance given by a vector, and a radius.

There are several solutions you need and methods.  They are surfaceNormal, intersects, and collisionDistance.

But to implement those you need some utility methods.  One is segmentSegmentDistance which is given segment AB and segment CD find the least distance between the segments and the two points on the segments that are closest.  In the case of a capsule if this distance is less than the sum of the two radii then they are intersecting.  If the distance is more than the sum of the radii plus the speed of motion, then they wont collide at all.

A very similar method as ptSegmentNearest which finds the distance between a point P and a line segment AB and wht the point on the segment is.

Surface Normal
The surface normal is fairly simple.Given a point P presumed to be on the surface use ptSegmentNearest to find the point Q on the capusles AB segment and subtract Q from P to get a vector and then normalize the vector.  It will be the surface normal.  Watch out for the degenerate case where P is on the segment AB!

Intersects
If you are solving the distance to impact by successive approximations you need to have a fast way to tell if two Capsules intersect.  The best is to use segmentSegmentDistance.  If it is less than the sum of the radii then they intersect.  Watch out for the PHYSCIS_EPSILON issues here.  It is really

  if(isZero(dist - R1 - R2)) ...
Collision Distance
Now for the hard part!
If we have a moving capsule and it might collide with another capsule, well, do they and how far?

Turns out there are two cases for this.

If the capsules are aligned, in other words their AB lines are parallel or anti-parallel then the solution is much easier. (Anti-parallel means line AB is exactly the opposite direction from the other capsule's AB).

To tell if they are parallel just take the dot product of the two ABs.  If it 1.0 or -1.0 then they are parallel so you do the easy direct linear math solution.  Careful, once again don't just do abs(AB.dot(other->AB)) == 1.0.  You must use isZero(abs(AB.dot(other->AB)) - 1.0) to account for PHYSICS_EPSILON.

Parallel Capsules

* note: in some graphics code PHYSICS_EPSILON is just called EPSILON.

If they are not parallel then you have to solve by successive approximations.

Direct Linear Solution
Parallel capsules can be solved by adding the two AB segment together into one longer segment (watch out for the anti-parallel case!) and adding the radii resulting in a bigger capsule.  Then solve a ray from the A point of this to hit the combined capsule.  The distance will be correct.

-- Picture here ---

To solve the ray, first solve for an infinite cylinder and if it misses then there is no collision.  If it hits, find the point along the cylinder center line nearest the hit point.  If it is between A and B then you hit the body of the capsule.  If not then solve each of the spheres. and see which is closest.  There are some odd cases where your ray origin is inside the capsule, oops, the capsules were already intersecting.

You also have to see if the surface normal at the hit point is at right angles to your velocity.  This means it is a grazing hit (a miss) or you are just on the surface and are moving parallel to the surface, also a miss.  In fact any solution with the ray origin inside the capsule is a miss. These near misses are critical to good collision behavior.

Combine two capsules and then collide as a vector to get distance to collision.

Successive Approximation
If the capsules are not parallel you have to do a successive approximation.  Above I explained that you can tell whether two capsules are intersecting by simply finding the distance between the two AB segments. So you call the intersects method to decide how to iterate.  One great optimization is that much of the math for distance doe not depend on the resulting distance, only on the dot or cross product between the two AB segments.  You can take advantage of this to speed the iterations up.

Successive Approximation. Shown with parallel capsules but in our case they would not be parallel. Shows just 3 iteration, you would do more like 10.

Terrain Collision
One exception in all this collision is terrain.
Since TLD is an infinite world, and based on a OctTree, the terrain is not a normal object in the scene.  It changes altitude as a single sheet of triangles, penetrates between OctTree cubes and is generally misbehaved So I treat terrain as a special case in the collision code as a check before checking object collision in the Fine Pass.  I also do not collide physics objects with the terrain as such, I instead take a lowest point in the physics object and just collide that with the start and end points on the ground for the move interval. This makes the assumption that you are moving less than a terrain square tile interval.  Since my terrain is 1 meter squares this assumes you are doing somewhat less than 60 meters per second, which is very fast. So rather than check each triangle along the path of the move, I just check the start and end points.  In practice this works well.  Then I use the surface normal of the ground to adjust velocity.  Inelegant, but efficient.

Movement vectors with convex and concave terrain.  Vectors are exaggerated long. 

Code
Some words about collision code.  Each game physics engine has its own vector type, some float or double scalar type, and its own convention for variable names.  When making a game it is a good idea to use an existing physics engine.  We tried Bullet Physics.  In the end I ended up doing a custom physics engine for TDL for several reasons.

• We have an infinite world and physics engines are usually geared toward a 'level' in a game which is limited in space.
• We have all the data structures in place such as an OctTree, terrain definitions, all the objects in the scene, all because we are generating the whole world on-the-fly as you move through it. (Go play Minecraft)  Using and existing engine tends to result in duplicate data for everything.  We have to use memory very efficiently.
• We are very efficient with CPU use.  Every cycle counts.

There are only two reasons you should write your own physics engine...

• The above three reasons of you have a very unique game world.
• Because it is downright fun and you like algorithms, math, and lots of debugging.

So, the following code examples are built on the bullet physics base types such as btVector3 and btScalar (set to double precision) so I don't have to rewrite all the vector math and Quaternions, and Matrices.

---- Code examples coming soon. -----

Oh, BTW, X is to the right of the screen, Y is Up, Z is out of the screen toward the viewer, but collision is in world coordinates, not screen coordinate, so you can think of it as X is East, Y is Up, Z is South.

Profiling
I can't emphasize enough how important it is to do code profiling. I use cRunWatch from raven.  It is very simple.  I was doing lots of work on getting the Fine Pass collision to be fast, and as soon as I profiled TDL, I saw that my Coarse Pass was taking 80% of the total execution time.  I easily then made it much faster and it now gets 32 FPS in debug mode, and > 200 FPS in release mode.

Debugging
Debugging physics is very difficult because everything is happening in a fraction of a second and if you set a break point the timing is all off and the keyboard is no longer game movement input.  The best thing to do is put if statements specifically as breakpoints.  In TDL it looks like this...

volatile int foo = 0;

if(!IsServer && m_isPlayer && m_velocity.getX() > 0.0 and other->m_isAABB)
{
     foo = 1;
}Then you can get to the right place in the game, like running into a wall and set the breakpoint on foo = 1 and then continue and when you start to move forward the breakpoint is triggered.  So get creative on breakpoints in this style.

Another great class I designed is a PeriodicLog.  What it does is every n milliseconds it enables logging for one frame.  Then you can have a log entry for example that prints the solution distance every frame but instead of getting swamped with log lines, you just get one or two per second.

Also at a higher level it helps to be able to turn on wireframe representations of all collision objects and they change color when impacting or moving etc.  This does not help much with low level collision code debugging, but is great for in game whole scene setup issues.

TF