My first collision algorithm

Introduction

When I started 3D programming I soon realized that a lot of things I gave for granted on all the games I played, weren’t so. For example in a 3D world there are only textures and triangles to be drawn. Collisions and a lot of things alike have to be created on your own. That means that if you want the camera not to pass through a wall you have to create an internal geometric representation of the wall and manage the logic yourself.
I want to point out that there are many approaches for handling collisions. I am only showing my approach, I think that everything should be from simple to complex. I have seen so many people trying to enter to the 3D programming world but most of them back out because a lot of tutorials demand previous background of so many areas of knowledge that people get usually overwhelmed.
About the math used in this article, I studied it at school when I was about 12 years old, so I guess you don’t need to have a solid background to understand this and won’t be rocket science.
I say again this algorithm its only my approach I think there are far more better on the web but this one its pretty simple and it puts you on the right way.

Some before diving into the code.

First of all I assume I am handling 2D collisions. I am on a 3D environment but the floor is a flat surface. It’s like looking at a maze from above, the walls can be considered line segments and the camera can be considered a point. If I plot those line segments into a coordinate axis I can make use of analytic geometry to perform some collision calculations. So if say I don’t want my camera to get near a wall (in this case a wall is a line segment) no more than 1 unit; Then every time I move my camera I check the distance to all those line segments and if one distance is less than 1 unit then there is a collision and the camera won’t move to that direction. Of course, the new position has to be checked before moving the camera.

This image give you an overview of my method:

This has a drawback. You have to create your line segments on your own. That means that if you have a room then you have to create 4 line segments. That does bring another complication because you don’t get to know the coordinates of the points. Been this demo only for educational purposes I have created in the scene a code that displays on the left top side of the screen the current position of the camera. You go into one corner write down the coordinates the go to the other corner of the wall and write down to other coordinate. In this way you have the 2 points needed to create a line segment. I know you have to work a lot to create all the collisions for a simple scene but this goes in order to gain in understanding. Later on if you want to simplify you can make dummy points on the 3D object and interpret them on the code later

Steps to determine a collision

The main objective of this demonstration is finding out the distance between a point (camera) and a line segment (wall). Here are the steps to find it out.

1. A line segment is defined by 2 points and is contained in a linear function of the type:
Y = MX + N where M is the pendent of the equation and N is where it intersects the Y axis. The first step is finding out that equation. M can be found using the 2 points of the line segment and its equation is M = (Y1 – Y2)/(X1 - X2); to avoid division by zero I add a very small number if (X1 - X2) leads to zero;

2.       Later you try to find out the equation of the linear function perpendicular to that equation. For that you know that the pendent of that equation is M2 = - 1/M1

 

3.       Then you Equals the 2 functions trying to find the intersection point

M1X + N1 = M2X + N2

X = (N2 – N1)/ (M1 – M2)

Y it’s found replacing X in any of the two equations

4.       When you find the intersection  point there are 3 choices

a.       Intersection point is contained in the line segment

 b.      Intersection point is not contained on the line segment and is near of one extreme of the line segment

c.       Intersection point is not contained on the line segment and is near of the other extreme of the line segment

This is the main reason why I calculate the distance between the intersection point and the 2 extremes, and then the real distance is the less of the 3. The distance is calculated by the Euclidian method, Try this link if you don’t know it, is very simple

Working with the code

In this demo I used a small engine developed by myself to simplify other stuff such as texture loading, drawing and others. Here is a brief look at the classes it contains.

House.cs

This class contains the methods to draw the house seen on the demo. Here is the code where I create all the collisions:

public void CreateCollisions()

{

 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(18.9f, -14.1f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(-24.4f, 13.2f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(-20.2f, -0.1f), new Vector2F(-4.8f, -0.1f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(-0.5f, 0.7f), new Vector2F(-0.5f, -8.7f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(-24.4f, 14.4f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(19.4f, -14.4f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(-17.5f, 0.5f), new Vector2F(-17.5f, 11), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(13.4f, -0.15f), new Vector2F(18.74f, -0.15f), 0.5f);

 Collision.AddCollisionSegment(new Vector2F(-0.43f, -9.1f), new Vector2F(12.4f, -9.1f), 0.5f);

 //Collision.GhostMode = true;  

}

 Note the third parameter is the distance in which a collision will be valid, I mean if the distance of the camera to that line segment is less than that parameter a collision event will be triggered.

Camera.cs

This class handles camera movements. If you take a look at the code you will see how collision is managed:

if (pressedButton == 1) // forward button is pressed

{

if (!Collision.CheckCollision(new Vector3(eyex - (float)i * forwardSpeed,                             eyez - (float)k * forwardSpeed, 0)))

    {

       eyex -= (float)i * forwardSpeed;

       eyez -= (float)k * forwardSpeed;

    }  

}

Note that current X and Z position will only be updated if there is not a camera collision. Also note that the floor is located on the XZ plane.

Collision.cs

This is the class that handles collisions; note the code that checks for a collision

public static bool CheckCollision(Vector3 camaraPos)

{

    if (!ghostMode) //if collisions are not disabled

    {

       foreach (var item in colitionSegments)

       {

           if (item.segment.DistToSegment(camaraPos) < item.ColitionDistance)

           {

              return true;

            }

       }              

     }

     return false;

 }

Segment struct:

This struct holds all the calculations explained at the bottom of this article. First it finds the segment linear equation on the constructor and it has the method to calculate the distance between a point and a line segment.

public float DistToSegment(Vector3 other)

{

    //calculate the two linear functions

    float n2 = other.Y - m2 * other.X;   //y = m2x + n   m2 = -1/m1

    //calculate the intersection point(i.p.)

    Vector3 intersectionPoint = new Vector3();

    intersectionPoint.X = (n2 - n1) / (m1 - m2);

    intersectionPoint.Y = m1 * intersectionPoint.X + n1;

    float d = Vector3.DistPointToPoint(intersectionPoint, other);

   

    float dist1 = Point3D.DistPointToPoint(other, first);

    float dist2 = Point3D.DistPointToPoint(other, second);

//if the i.p. is contained in the rect segment return d else

//the minimun value between dist1 and dist2

if ((intersectionPoint.X < first.X && intersectionPoint.X > second.X) ||

    (intersectionPoint.X > first.X && intersectionPoint.X < second.X))

            {

                return d;

            }

            else

                return Math.Min(dist1, dist2);  

}

Controller.cs

This is the controller class; the most important part relative to this tutorial is the draw method:

public void DrawScene()

{   

   house.Draw();

   sky.Draw(); 

   //DebugMode.WriteCamaraPos(200, 200);

   Collision.DrawColissions();

}

The function WriteCamaraPos outputs to the screen the current coordinates of the camera; this is how I find out the coordinates of both extremes of a wall to define it as a line segment.

The other commented function draws all the lines representing collisions on the scene. This is how I see if everything is going ok. Sometimes if you want to see them, you have to comment the code that draws the house into the screen in order to see them.

Final conclusions

You will find out that all collisions for the house on the demo have not been implemented, only a few. If you want to learn how I did it, give it a shot and try to complete the collisions on the scene. This approach will place you on the right track if you want to learn this side of 3D programming. I think this articles proves that implementing your own collisions in a game doesnt always to have to be difficult. Also it proves that if you really want to learn 3D programming you have to make a lot of thing by yourself rather than rellying on a complex engine. In this way you will be your own god and you will go as far as your mind takes you.

this is the repo link for the source code
https://github.com/vtserej/3d-collision-opengl/