Cylinder Based Collision Detection

Welcome to my tutorial on cylinder-based collision detection and response. I will attempt to provide you with an alternative to the ever popular sphere-based collision detection that is abundant out there. Why a cylinder you may ask, because I handle my collision detection in two different ways. I use cylinder based collision detection (CD) for my horizontal collision and response and I handle up/down gravity as a separate entity. It is actually easier to break it up this way than to fight with a sphere rolling on the ground. I will try and prove this to you , but please note that I may not be the best tutorial writer in the world. If you every have a question, please feel free to email me at spiritking@lycos.com . On to the beginning.....

Setup and Definitions

I make my game world with the X-axis being left and right, Z-axis near and far, and Y-axis is Up and Down. If you use anything different , you will have to adjust accordingly.

The Player in the game world is represented by a single point (X,Y,Z) I like to call Position.The position is the place the player is standing in the world, meaning it is usually a point on the ground. First we will handle the Cylinder (XZ) collision and response and then we will handle the Gravity (Y) aspect.

The Cylinder has 3 variables that make it up. It's radius (R), beginning height (H1) and it's ending height (H2). The radius should encompase your player but not really exceed to far out from him. The H1 is always a little above the player position, how much determines the slope he can travel before he will collide with it. The H2 is always at the top of the player. To determine H1 use some good ole triangle math to determine the angle.

Using Tan (a)=H1/R you can find the max angle you player will walk up.

On to more setup

Now that we know what a cylinder is and what values we use to set it up, let's place it in our world.

Now we start with the players Original Position (oPos) and we move him by whatever velocity vector we want and come up with the New Pos (nPos). We need both of these for the CD routine and remember we move our player's XZ components only, the Y is separate, start thinking 2-D from the top down.

So we now have our oPos (X,Z) and our nPos (X,Z), also the R, H1, H2. Here's what we do with it.

Clipping the World

We take all the world geometry that is close by, that we could possible collide with, and we clip it all at the H1 and H2 mark.We discard anything not in this range, as it could not possible effect or CD.

Before

After

So now that we have clipped our world to only the things that matter, we still have one more step. Since everything thats in range of H1 and H2 will collide the same no matter where it hits the cylinder, we flatten all the clipped geometry to have y=0. Do you got that, we clip to fit in the range of the cylinder, then we flatten it. We are working in 2 dimensions now.

There is no side view, it's all flat.

What Now...

So far, there has not been any code, and there won't be yet. I'm saving that for the end. Here's what we do now that we have the following, oPos, nPos, R, H1, H2, All close by geometry clipped within the range of H1 and H2, you have all these right...right. Well, now you loop through all the clipped geometry checking each edge to the npos using a closestpointonline() function. If the distance is less than R, you have a collision, save the closestpointonline() result and distance. Continue loop through all the geometry checking for any points closer, if there is than that become your new saved point and distance.

Response

Now that we have the collision point (if we have one that is), what do we do...Simple,
we calculate a normal from the nPos to the collision point , normalize the normal and move the nPos , R units in the normal direction. Did you get all that? Good, if not we are getting to the code soon.

To code or not to code...

Here's the part we all been waiting for, the main event. The "I'm to darned lazy to code it myself" section.... But first , let me explain why you've not seen any code up until now. Through my sheer genius, I have reduced the whole process into 1 mere function... which would be kinda pointless to butcher it up and sprinkle it here and there throughout the tutorial. I t would just get in the way and be messy. Let me give you and overview of the function...One, it does not tell you what geometry should be sent to it, it will process anything you send to it, it is your job to setup a good partition of your world weather bsp,oct/quad or whatever. Send only the geometry that could possible be collided with, no more or less. It will work with more, but that is a waste of valuable CPU. Two it can fail if your player moves greater than Radius each frame.... I have left that check and solution out of this... you have to work for something...this will work fine though if your player does not move > than R each frame. I do have the solution , but it is mine...sorry, but here's a hint, there is a reason to send oPos into the function. This function accepts a triangle from your world , clips it to the H1 and H2, flattens it, and checks it against the nPos and send back the collision point. It's that darned amazing. So here it is....

// h1 is H1 ...duh
// h2 is H2 ...ditto
// r is radius....n/c
// pos is nPos
// opos is oPos
// vPoly[] has to be a triangle
// res is the returned collision
// function returns true if a collision else returns false
//
bool TriInRange(float h1, float h2, float r, D3DXVECTOR3 pos,D3DXVECTOR3 opos, D3DXVECTOR3 vPoly[], D3DXVECTOR3 *res)
{
    int inr,i;
    int lowwer,higher;

    int numverts;
    D3DXVECTOR3 verts[6];

    D3DXVECTOR3 closest,org,cpl,normal,oorg;
    float cdis,ndis,bignum;

//// org is nPos
    org=pos;
    org.y=0;

//// oorg is oPos
    oorg=opos;
    oorg.y=0;

    D3DXVECTOR3 hold;

    lowwer=0;
    higher=0;
    inr=0;
    numverts=0;

    if (vPoly[0].y<h2) lowwer=1;
    if (vPoly[1].y<h2) lowwer=1;
    if (vPoly[2].y<h2) lowwer=1;

    if (vPoly[0].y>h1) higher=1;
    if (vPoly[1].y>h1) higher=1;
    if (vPoly[2].y>h1) higher=1;

    if ((higher==1)&&(lowwer==1))
    {
        //======== AB Group ==========================
        if ((vPoly[0].y>h2)&&(vPoly[1].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[0].x+((h2-vPoly[0].y)*(vPoly[1].x-vPoly[0].x)/(vPoly[1].y-vPoly[0].y));
            hold.z=vPoly[0].z+((h2-vPoly[0].y)*(vPoly[1].z-vPoly[0].z)/(vPoly[1].y-vPoly[0].y));
            verts[numverts]=hold;
            numverts++;
        }//clip a top

        if ((vPoly[0].y<h1)&&(vPoly[1].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[0].x+((h1-vPoly[0].y)*(vPoly[1].x-vPoly[0].x)/(vPoly[1].y-vPoly[0].y));
            hold.z=vPoly[0].z+((h1-vPoly[0].y)*(vPoly[1].z-vPoly[0].z)/(vPoly[1].y-vPoly[0].y));
            verts[numverts]=hold;
            numverts++;
        }//clip a bot

        if ((vPoly[1].y>h2)&&(vPoly[0].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[1].x+((h2-vPoly[1].y)*(vPoly[0].x-vPoly[1].x)/(vPoly[0].y-vPoly[1].y));
            hold.z=vPoly[1].z+((h2-vPoly[1].y)*(vPoly[0].z-vPoly[1].z)/(vPoly[0].y-vPoly[1].y));
            verts[numverts]=hold;
            numverts++;
        }//clip b top

        if ((vPoly[1].y<h1)&&(vPoly[0].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[1].x+((h1-vPoly[1].y)*(vPoly[0].x-vPoly[1].x)/(vPoly[0].y-vPoly[1].y));
            hold.z=vPoly[1].z+((h1-vPoly[1].y)*(vPoly[0].z-vPoly[1].z)/(vPoly[0].y-vPoly[1].y));
            verts[numverts]=hold;
            numverts++;
        }//clip b bot
        //======== BC Group ==========================
        if ((vPoly[1].y>h2)&&(vPoly[2].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[1].x+((h2-vPoly[1].y)*(vPoly[2].x-vPoly[1].x)/(vPoly[2].y-vPoly[1].y));
            hold.z=vPoly[1].z+((h2-vPoly[1].y)*(vPoly[2].z-vPoly[1].z)/(vPoly[2].y-vPoly[1].y));
            verts[numverts]=hold;
            numverts++;
        }//clip b top

        if ((vPoly[1].y<h1)&&(vPoly[2].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[1].x+((h1-vPoly[1].y)*(vPoly[2].x-vPoly[1].x)/(vPoly[2].y-vPoly[1].y));
            hold.z=vPoly[1].z+((h1-vPoly[1].y)*(vPoly[2].z-vPoly[1].z)/(vPoly[2].y-vPoly[1].y));
            verts[numverts]=hold;
            numverts++;
        }//clip b bot

        if ((vPoly[2].y>h2)&&(vPoly[1].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[2].x+((h2-vPoly[2].y)*(vPoly[1].x-vPoly[2].x)/(vPoly[1].y-vPoly[2].y));
            hold.z=vPoly[2].z+((h2-vPoly[2].y)*(vPoly[1].z-vPoly[2].z)/(vPoly[1].y-vPoly[2].y));
            verts[numverts]=hold;
            numverts++;
        }//clip c top

        if ((vPoly[2].y<h1)&&(vPoly[1].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[2].x+((h1-vPoly[2].y)*(vPoly[1].x-vPoly[2].x)/(vPoly[1].y-vPoly[2].y));
            hold.z=vPoly[2].z+((h1-vPoly[2].y)*(vPoly[1].z-vPoly[2].z)/(vPoly[1].y-vPoly[2].y));
            verts[numverts]=hold;
            numverts++;
        }//clip c bot

        //======== CA Group ==========================
        if ((vPoly[2].y>h2)&&(vPoly[0].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[2].x+((h2-vPoly[2].y)*(vPoly[0].x-vPoly[2].x)/(vPoly[0].y-vPoly[2].y));
            hold.z=vPoly[2].z+((h2-vPoly[2].y)*(vPoly[0].z-vPoly[2].z)/(vPoly[0].y-vPoly[2].y));
            verts[numverts]=hold;
            numverts++;
        }//clip c top

        if ((vPoly[2].y<h1)&&(vPoly[0].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[2].x+((h1-vPoly[2].y)*(vPoly[0].x-vPoly[2].x)/(vPoly[0].y-vPoly[2].y));
            hold.z=vPoly[2].z+((h1-vPoly[2].y)*(vPoly[0].z-vPoly[2].z)/(vPoly[0].y-vPoly[2].y));
            verts[numverts]=hold;
            numverts++;
        }//clip c bot

        if ((vPoly[0].y>h2)&&(vPoly[2].y<h2)){
            hold.y=0;//h2;
            hold.x=vPoly[0].x+((h2-vPoly[0].y)*(vPoly[2].x-vPoly[0].x)/(vPoly[2].y-vPoly[0].y));
            hold.z=vPoly[0].z+((h2-vPoly[0].y)*(vPoly[2].z-vPoly[0].z)/(vPoly[2].y-vPoly[0].y));
            verts[numverts]=hold;
            numverts++;
        }//clip a top

        if ((vPoly[0].y<h1)&&(vPoly[2].y>h1)){
            hold.y=0;//h1;
            hold.x=vPoly[0].x+((h1-vPoly[0].y)*(vPoly[2].x-vPoly[0].x)/(vPoly[2].y-vPoly[0].y));
            hold.z=vPoly[0].z+((h1-vPoly[0].y)*(vPoly[2].z-vPoly[0].z)/(vPoly[2].y-vPoly[0].y));
            verts[numverts]=hold;
            numverts++;
        }//clip a bot

        //repeat first point
        verts[numverts]=verts[0];

        closest=verts[0];
        cdis=10000;
        D3DXVECTOR3 resnc;
//******************************************Find closest point on lines
        for (i=0;i<numverts;i++){
                cpl=ClosestPointOnLine(verts[i],verts[i+1],org);
                ndis=Distance(cpl,org);
                if (ndis<cdis){
                    cdis=ndis;
                    closest=cpl;
                }//closer

        }

        //check to see if it is less than radius
        if (cdis<r){
            *res=closest;
            return true;

        }else return false;
    }
    else return false;

}
//// end function

D3DXVECTOR3 ClosestPointOnLine(D3DXVECTOR3 vA, D3DXVECTOR3 vB, D3DXVECTOR3 vPoint)
{
    // Create the vector from end point vA to our point vPoint.
    D3DXVECTOR3 vVector1 = vPoint - vA;

    // Create a normalized direction vector from end point vA to end point vB
    D3DXVECTOR3 vVector2 = Normalize(vB - vA);

    // Use the distance formula to find the distance of the line segment (or magnitude)
    float d = Distance(vA, vB);

    // Using the dot product, we project the vVector1 onto the vector vVector2.
    // This essentially gives us the distance from our projected vector from vA.
    float t = Dot(vVector2, vVector1);

    // If our projected distance from vA, "t", is less than or equal to 0, it must
    // be closest to the end point vA. We want to return this end point.
    if (t <= 0)
        return vA;

    // If our projected distance from vA, "t", is greater than or equal to the magnitude
    // or distance of the line segment, it must be closest to the end point vB. So, return vB.
    if (t >= d)
        return vB;

    // Here we create a vector that is of length t and in the direction of vVector2
    D3DXVECTOR3 vVector3 = vVector2 * t;

    // To find the closest point on the line segment, we just add vVector3 to the original
    // end point vA.
    D3DXVECTOR3 vClosestPoint = vA + vVector3;

    // Return the closest point on the line segment
    return vClosestPoint;
}

It really is simple, now for the code within your program to use this and dela with collision reponse..... you will have to figure your own hooks out...

    D3DXVECTOR3 vTri2[3];
    float radius=4.0f;
    float oldPos=Player.pos;
    float newPos=Player.pos+Time_Elapsed*Player.velocity;

        for (ict=0;ict<Level->numobj;ict++){

                for(j=0; j<Level->obj[ict].numtri; j++ )
                {
                     //load the triangle to send to the function
                    vTri2[0] = Level->obj[ict].verts[Level->obj[ict].index[3*j+0]];
                    vTri2[1] = Level->obj[ict].verts[Level->obj[ict].index[3*j+1]];
                    vTri2[2] = Level->obj[ict].verts[Level->obj[ict].index[3*j+2]];


    if (TriInRange(player.pos.y+3,Player.pos.y+9,radius,newPos,oldPos,vTri2,&res))
                    {
                        bnorm=newPos-res;

                        bnorm.y=0;

                        bignum=sqrt((bnorm.x*bnorm.x)+(bnorm.z*bnorm.z));
                        bnorm.x/=bignum;
                        bnorm.z/=bignum;
                        newPos=res+radiusf*bnorm;

                    }//tri hit
                }//for j numtris

        }//loop obj
// only update XZ, Y is done by itself
   Player.pos.x=newPos.x;
    Player.pos.z=newPos.z;
Player.pos.y= GetYValueAtPosition(newPos.x,newPos.z,etc...);

What about Y

Ok, so for now all we have been effecting is the XZ axis of our player. I am only gonna describe the GetYValueAtPosition() function. Maybe my next revision will have code. it really is simple if you are thinking in 2-D, think that you are looking down from above. Loop all close triangles find the triangle that your player pos is in and find the Y value of that triangle at that position.... ok. Just a little code....

BOOL GetYValueAtPosition( const float& xp,const float& zp, D3DXVECTOR3& v0,D3DXVECTOR3& v1, D3DXVECTOR3& v2,float *ddd)
{

        float d,dh,yh;
        int ct=0;

        if (!IsPossible(xp,zp,v0,v1,v2))return FALSE;

        if (( (v0.x>=xp)&&(v1.x<xp) )||( (v0.x<xp)&&(v1.x>=xp) ))
        {
        d=v0.z+(xp-v0.x)*(v1.z-v0.z)/(v1.x-v0.x);
        if (d>zp){ ct++; dh=d;yh=v0.y+(xp-v0.x)*(v1.y-v0.y)/(v1.x-v0.x); }
        }
        if (( (v1.x>=xp)&&(v2.x<xp) )||( (v1.x<xp)&&(v2.x>=xp) ))
        {
        d=v1.z+(xp-v1.x)*(v2.z-v1.z)/(v2.x-v1.x);
        if (d>zp){ ct++; dh=d; yh=v1.y+(xp-v1.x)*(v2.y-v1.y)/(v2.x-v1.x);}
        }
        if (( (v2.x>=xp)&&(v0.x<xp) )||( (v2.x<xp)&&(v0.x>=xp) ))
        {
        d=v2.z+(xp-v2.x)*(v0.z-v2.z)/(v0.x-v2.x);
        if (d>zp){ ct++; dh=d; yh=v2.y+(xp-v2.x)*(v0.y-v2.y)/(v0.x-v2.x); }
        }

        if (ct==1) {


            float x[3],y[3],z[3];
            int hm=0;

            if ( ((v0.x>=xp)&&(v1.x<xp)) || ((v1.x>=xp)&&(v0.x<xp)) )
            {
                z[hm]=v0.z+(xp-v0.x)*(v1.z-v0.z)/(v1.x-v0.x);
                y[hm]=v0.y+(xp-v0.x)*(v1.y-v0.y)/(v1.x-v0.x);
                x[hm]=xp;
                hm++;

            }

            if ( ((v1.x>=xp)&&(v2.x<xp)) || ((v2.x>=xp)&&(v1.x<xp)) )
            {
                z[hm]=v1.z+(xp-v1.x)*(v2.z-v1.z)/(v2.x-v1.x);
                y[hm]=v1.y+(xp-v1.x)*(v2.y-v1.y)/(v2.x-v1.x);
                x[hm]=xp;
                hm++;

            }

            if ( ((v2.x>=xp)&&(v0.x<xp)) || ((v0.x>=xp)&&(v2.x<xp)) )
            {
                z[hm]=v2.z+(xp-v2.x)*(v0.z-v2.z)/(v0.x-v2.x);
                y[hm]=v2.y+(xp-v2.x)*(v0.y-v2.y)/(v0.x-v2.x);
                x[hm]=xp;
                hm++;

            }

            if (hm<2) return FALSE;
            *ddd = y[0] + (zp-z[0])*(y[1]-y[0])/(z[1]-z[0]);


            return TRUE;
        }

        return FALSE;


}

Send the triangles in and if the x and z value are in the triangle , it returns true and ddd returns the y value at that location. You have to decide which one is the right one if more than 1 triangle is over/under the player....

Last update: 9-8-04

Netflick