Cylinder Cube Collision Detection

Home --> Programming Projects --> Block Engine --> Cylinder Cube Collision Detection

Collision Detection: The Right Way

In a block game with gravity, it makese sense to model the player as a cylinder when it comes to moving the player through the world. One reason is so that the player can stand on the edge of clifs and look slightly over. There are other reasons as well.

So we want code to detect a collision between a moving cylinder and a cube. The cylinder is parallel to the z-axis. The cube is also always axis-aligned. The clyinder should be moving in a straight line. We want our code to find the first time the cylinder intersects the cube. Also, we would like to know information about the time of intersection so that after the intersection the cylinder will move parallel to the cube.

That is the right way to do it.

Collision Correction: The Hippie Way

But in addition to the right way to do it, there is also the "hippie way". Cubes are 1 unit wide, so the player's cylinder radius is perhaps 0.3 or something like that. We can move the player's cylinder 0.1 units at a time IGNORING any collision. Then after each 0.1 length move we can see if the cylinder intersects a cube. If it does, then we can move the cylinder slightly so it no longer intersects a cube. However we do not backtrack when there is a collision: we move the cylinder in a possibly new direction. We translate the cylinder the shortest length possible so that it no longer intersects a cube. Call this method Collision Correction.

In this page we describe this "hippie method" of collision correction.

This hippie collision correction method is likely slower than traditional collision detection. However it is simple. In a game where we mainly intersect the player's cyllinder with cubes, it works well and is robust.

What About Changing The Velocity?

Another downside of the collision correction method is that when there is a collision, the collision correction code does NOT generate a velocity vector which we can use to continue to move the cylinder.

However Block Arena and Fractal Block World use the approach of not storing the player's velocity. Instead, we have the position P_0 of the player at the previous time step and the position P_1 of the player at the current time step. To calculate the position P_2 at the next time step, we just pretend the velocity is some multiple (by a fixed constant) of P_1 minus P_0. Then we take this velocity (and modify it because of drag and forces) and combine it with P_1 to get P_2'. Then we do collision correction as we attempt to move the player's cyllinder from P_1 to P_2'. After the collision correction we get the position P_2 of the player. This is sort of like Verlet integration.

With this approach for updating the player's position, momentum works automatically. If the player is moving fast horizontally and hits the ground, he will slide along the ground naturally (ignoring drag effects, which will slow him down). This is what should happen.

The Code

Here is the function CollisionCorrectCylinderCube to move a cylinder which intersects a cube in the smallest way possible so that the cylinder no longer intersects the cube. It uses two helper functions: ColCorHelper1 and ColCorHelper2. The class Vector is a class with floating-point members x,y, and z.

Certainly this code could be made much faster by not pushing onto a vector.

//This is C++ code.

//A "possible correction" is a pair (diff,trans),
//where diff is a float and trans is a Vector.
//Given a possible correction (diff,trans),
//if diff > 0.0 then if we translate the cylinder
//by trans then there will no longer be an intersection.
//If diff <= 0.0, then we can ignore the possible correction pair.

//Given the cylinder and the cube,
//we want to form the list of all possible corrections.
//
//If there are either no possible corrections
//(or every possible correction's diff values are negative)
//then no correction needs to be made.
//
//If there is at least one possible correction (diff,trans)
//where diff is positive, then considering the pair (diff,trans) with
//the least such positive diff, translating the cylinder
//by trans will make it no longer intersect the cylinder.

//To collision correct the cylinder from the cube,
//we have 3 possible corrections:
//1) (Pushing up): moving the cylinder up so the bottom of
//   the cylinder >= the max z value of the cube.
//2) (Pushing down): moving the cylinder down so the top of
//   the cylinder is <= the min z value of the cube.
//3) (Pushing laterally): moving the cylinder
//   laterally (changing the x and y coordinates without
//   changing the z coordinates).
//   Here, we break into 8 cases depending on
//   where the (x,y) position of the cender of the cylinder is
//   relative to the (x,y) coordinates of the 4 vertical edges
//   of the cube.

//This function takes a list of possible corrections
//and returns the possible correction from the list
//with the smallest diff value.
void ColCorHelper1(
    svector< pair > diffs,
    float & best_diff,
    Vector & best_trans)
{
    if( diffs.size() == 0 ) {
        best_diff = 0.0f;
        best_trans = Vector(0.0f, 0.0f, 0.0f);
        return;
    }

    best_diff = diffs[0].first;
    int best_index = 0;
    for(int i = 1; i < diffs.size(); ++i) {
        float diff = diffs[i].first;
        if( diff < best_diff ) {
            best_diff = diff;
            best_index = i;
        }
    }
    best_trans = diffs[best_index].second;
}

//This generates a possible collision pair (pdiff,ptrans)
//for when the cylinder intersects an edge of the cube.
//More precisely, we let mover_plane_p be the center
//of the cylinder projected to the xy plane
//and we let solid_plane_p be the cube edge projected
//to the xy plane.
//Then we calculate how to translate mover_plane_p
//(by the translation vector ptrans) so that
//the resulting vector mover_plane_p + ptrans
//is at least mover_radius away from solid_plane_p.
//
//Just to reiterate, mover_plane_p and solid_plane_p
//should both be in the xy plane.
//If their dist apart is < mover_radius,
//then we set pdiff to be > 0.0 and 
//so a correction needs to be made.
void ColCorHelper2(
    const Vector & mover_plane_p, //Should be in xy plane.
    float mover_radius,           //The radius of the cylinder.
    const Vector & solid_plane_p, //Should be in xy plane.
    float & pdiff,    //Output: the distance required move out of collision.
    Vector & ptrans)  //Output: translation vector to move out of collision.
{
    ptrans = mover_plane_p - solid_plane_p;
    pdiff = mover_radius - Length(ptrans);
    Normalize(ptrans); //Could do faster.
    ptrans *= pdiff;
}

//Returns true iff there is a collision.
//If there is a collision, then trans
//determines which translation should be made
//to move the cylinder so that it no longer
//intersects the cube.
//Morever, this will be the smallest such
//translation that does the trick.
bool CollisionCorrectCylinderCube(
    const Vector & p,     //Bottom of cylinder
    float radius,         //Radius of cylinder.
    float height,         //Height of cylinder.
    const Vector & c_min, //Min position of cube.
    const Vector & c_max, //Max position of cube.
    Vector & trans)       //Output: translation to move cylinder.
{
    float cyl_min_z = p.z;
    float cyl_max_z = p.z + height;

    //The bottom of the cylinder projected
    //to the xy plane.
    Vector plane_p = Vector(p.x, p.y, 0.0f);

    //When the smallest diff is positive,
    //a correction will be made.

    svector< pair > diffs;

    //Pushing up.
    float diff1 = c_max.z - cyl_min_z;
    Vector trans1(0.0f, 0.0f, diff1);
    diffs.push_back( make_pair(diff1, trans1) );

    //Pushing down.
    float diff2 = cyl_max_z - c_min.z;
    Vector trans2(0.0f, 0.0f, -diff2);
    diffs.push_back( make_pair(diff2, trans2) );

    //Pushing laterally.
    //Breaking into 8 cases for the plane.
    float pdiff;
    Vector ptrans;
    if( p.x >= c_max.x ) {
        //Right.
        if( p.y >= c_max.y) {
            //Front right.
            //Pushing away from a vertal cube edge.
            ColCorHelper2(
                plane_p, radius,
                Vector(c_max.x, c_max.y, 0.0f),
                pdiff, ptrans);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else if( p.y <= c_min.y ) {
            //Back right.
            //Pushing away from a vertal cube edge.
            ColCorHelper2(
                plane_p, radius,
                Vector(c_max.x, c_min.y, 0.0f),
                pdiff, ptrans);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else {
            //Middle right.
            //Pushing away from a vertical cube face.
            pdiff = radius - (p.x - c_max.x);
            ptrans = Vector(pdiff, 0.0f, 0.0f);
            diffs.push_back( make_pair(pdiff, ptrans) );
        }
    } else if( p.x <= c_min.x ) {
        //Left.
        if( p.y >= c_max.y ) {
            //Front left.
            //Pushing away from a vertal cube edge.
            ColCorHelper2(
                plane_p, radius,
                Vector(c_min.x, c_max.y, 0.0f),
                pdiff, ptrans);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else if( p.y <= c_min.y ) {
            //Back left.
            //Pushing away from a vertal cube edge.
            ColCorHelper2(
                plane_p, radius,
                Vector(c_min.x, c_min.y, 0.0f),
                pdiff, ptrans);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else {
            //Middle left.
            //Pushing away from a vertical cube face.
            pdiff = radius - (c_min.x - p.x);
            ptrans = Vector(-pdiff, 0.0f, 0.0f);
            diffs.push_back( make_pair(pdiff, ptrans) );
        }
    } else {
        //Middle.
        if( p.y >= c_max.y ) {
            //Front middle.
            //Pushing away from a vertical cube face.
            pdiff = radius - (p.y - c_max.y);
            ptrans = Vector(0.0f, pdiff, 0.0f);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else if( p.y <= c_min.y ) {
            //Back middle.
            //Pushing away from a vertical cube face.
            pdiff = radius - (c_min.y - p.y);
            ptrans = Vector(0.0f, -pdiff, 0.0f);
            diffs.push_back( make_pair(pdiff, ptrans) );
        } else {
            //Middle middle.
            //Should not have to worry about!
        }
    }

    //Finding the possible correction
    //with the smallest diff value.
    float best_diff;
    Vector best_trans;
    ColCorHelper1(
        diffs, best_diff, best_trans);

    if( best_diff <= 0.0f ) {
        //No collision.
        return false;
    } else {
        trans = best_trans;
        return true;
    }
}