Be warned. You may need to know some knowledge about vector math to completely understand everything. Sufficient knowledge of OOP in programming or scripting languages such as, respectively, C++ or Perl is required. You will see why in just a few paragraphs within the writeup.

Part I: Checking for a collision

The basic way of getting the ball rolling is using a

for loop to iterate through every

plane. Inside the loop the shortest distance from the

plane to the player's position should be calculated using

physics formulas such as the dot product of two

vectors to get the closest distance from a

plane (x

_{1}x

_{2} + y

_{1}y

_{2} + z

_{1}z

_{2}), and the

cross product of two

vectors (V

_{c}=(y

_{1}z

_{2}-z

_{1}y

_{2}, z

_{1}y

_{2}-x

_{1}z

_{2}, x

_{1}y

_{2}-y

_{1}x

_{2})), which is the result of the

normal vector of a

plane that contains two different

vectors ((x

_{1}, y

_{1}, z

_{1}) and (x

_{2}, y

_{2}, z

_{2}) in respect to the previous

cross product expression).

A normal vector is a vector that is perpendicular from the given plane. It can be used for other things such as lighting (shading, etc.) in programming 3D games, but for this, it is just to use in a dot product to check the shortest distance to a plane. To help understand what a normal vector is, a diagram is shown:

^
^ /
Normal Vector__-->__|/__
<---/ |¬ /--->
/______/ (Infinite plane)
/
/
v

**NOTE:** In order for the

collision to work, the

normal vector of a plane should be

*facing* the player. The player should never be able to

collide with a

plane from behind.

According to the theorems of Geometry, "The shortest line connecting a skew point to a plane is always perpendicular to the plane." This is the reason for using the normal as a parameter of the dot product.

If the distance is close enough, the points of a polygon should be checked. In order for this to be done, the specific point on the plane that the player will collide at is required. This is done by rescaling the velocity vector by how far away the person is from the shortest distance from the plane. Add the player's position to that vector, and that altogether is the vector of the point on collision from the origin.

Then the points of the polygon are subtracted by the point on collision so an angle can be obtained, like so:

Let p_{1} = vertex of polygon,
p_{2} = another vertex of polygon,
p_{c} = point on collision,
a = angle between vectors.
. <-- p_{1} ----------.
| |
| |
| . <-- p_{c} |
| |
| |
. <-- p_{2} __________.
v_{1} = p_{1}-p_{c}
v_{2} = p_{2}-p_{c}
.------------------.
|\ v_{1} |
| \ |
| a. <-- p_{c} |
| / |
|/ v_{2} |
.__________________.

Angle a is obtained by dividing the

dot product of the

vectors by the product of the

magnitude, or length, of the

vectors (√(x

² + y

² + z

²)):

v_{1} . v_{2}
cos a = -------------
||v_{1}||•||v_{2}||

Solving for a, the equation is:

v_{1} . v_{2}
a = cos^{-1} -------------
||v_{1}||•||v_{2}||

The reason for getting the

angle at the vertex of two of these vectors is simple. This is done with every possible

angle made with the

polygon, like so:

.---------.
|\ /|
| \ / |
| \a_{2} / |
| \ / |
| a_{1} . a_{3} |
| / \ |
| /a_{4} \ |
| / \ |
|/ \|
._________.

The

sum of all of these

angles should be 2π

radians when the point is within the polygon. If the

sum does not add up to

2π, whether it is more than or less than the value, then the

point is not within the

plane. The value should not be checked specifically for 2π. It's best to have the

code check in between a certain

margin of error. This will be explained in

**The player's response to collision detection**.

Part II: The player's response to collision detection

Just to stay on track, here is a small refresher on how the collision detection would be written in pseudocode and where the response to it should be placed:

for(*loop from plane 0 to plane x, where x is the maximum number of planes*)
{
if(*the player is close enough to the plane for collision to occur*)
{
if(*the point of collision on the plane is within a polygon*)
{
**...
Collision response code would go here.
...**
}
}
}

The main thing done is: the player is "bounced back" to a certain distance from the plane. This is done by calculating the

normal vector of the plane, if not calculated already and stored in a variable. This diagram will show how to bounce the player back:

Let:
O = player,
____ = polygon to be collided with,
---- = the sufficient distance from the polygon,
d = Distance from the ___ to the ---,
p = player's distance from the ___.
V_{p} = (x,y,z) position of the player's location.
Frame A:
____________________
--------------------
O (Player is safe.)
Frame B:
____________________
O p < d (Player has crossed the boundary.)*
--------------------
Frame C:
____________________
V_{p} = V_{p} + Plane's normal with length: (d-p)**
-------~~O~~------------ (Player is 'bounced' back to this exact distance)

* Make sure this stage of collision is never displayed, or the collision won't

look smooth at all!

** Don't know how to manipulate the distance of a

vector? Here's how. There are easier ways, but it will be done this way to help the reader understand what's going on.

Let:
(x_{n}, y_{n}, z_{n}) = the XYZ value of the normal vector,
m = magnitude of the vector (√(x_{n}² + y_{n}² + z_{n}²)).
First, turn the normal vector into a unit vector, if not already:
x_{n} = x_{n} / m,
y_{n} = y_{n} / m,
z_{n} = z_{n} / m.
This makes the magnitude of the vector a length of one.
After this is done, the vector is then multiplied by (d-p).
x_{n} = x_{n} * (d-p),
y_{n} = y_{n} * (d-p),
z_{n} = z_{n} * (d-p).

This makes the vector have a magnitude of (d-p). The XYZ values are added to the XYZ values of the player's position after this.

Part III: Extra tips!

**Difference Between a Slide and a Slanted Floor**: If the normal of a vector of a plane is a slanted floor (y_{n} is > 0.0, but less than a steep wall), assume that (x_{n}, y_{n}, z_{n}) is (0, 1, 0), otherwise the player will look like he is sliding down a sliding board when walking down a ramp.
**What Goes Up Must Come Down**: If the player is jumping in the air up toward a ceiling (where y_{n} is equal to or close to -1.0), then the y value of the player's current velocity should become the opposite of itself so the feeling is like the person just bumped his head and fell back down at the same speed he came up.
**Give Less Margin of Collision to Floors**: It is best to make the point-in-polygon tolerance have more margin for the walls than the floors/ceilings. The walls are best to make realistic. The floors and ceilings with a high margin seem weird, because it is possible to stand beyond the polygon, which is like levitating about a foot away from a cliff.

This

tutorial should be able to help anyone who is ambitious to create a decent

first-person shooter. This

collision detection can be applied to other things, such as

rockets,

bullets, other players, and

AI. There are other ways to apply collision detection, but this method seemed the easiest and most fit for a first person shooter.

Happy coding!