I just created a simple golf game using the techniques that I will describe in this tutorial. I had originally used simple axis aligned bounding boxes to my ground mesh to calculate and resolve collisions (Figure 1 below), but in this tutorial, I will show you a much more accurate way by taking it a step further, without costing lots of CPU or memory. A diagram showing in simple terms what I will be doing is shown here:
The example provided is using collision detection of a height-field terrain, against a ball, but you can use the theory for many aspects of collision detection. Also note that in my example x is the length of the field, y is the height of the field with y going up and direction of gravity, whilst z is the width of the terrain/pitch.
The problem with general axis aligned bounding boxes was that the golf ball would always rest on each polygon at the height of the maximum y value as shown in figure 1 (where y, not z was the direction of gravity in this case, x and z are the length and width of the field). What we really want (shown in Figure 2) is to have the golf ball rest on the polygon, AND check when it goes past or hits that part of the polygon, not just when its gone past the lowest or highest y value. This does not mean the bottom y of the ball touches the polygon or the bottom/max x, but the actual point of the ball that should be touching the polygon.
Figure 1
Figure 2
In my example, I use a 2x2 grid array of squares/quadrilaterals(actually 2x2x2 because had two triangles for each grid but you can think of it as 2x2 of squares) First we need to know what grid the ball is currently above or inside (where would the shadow fall if the sun directly above ball). To do this, we want to multiply the ball/object's coordinates, by the scalar size of your grid (IE how many units along x/z axis is each grid cell, note that this is not the size, as the y values should be variable). You then use this to select which polygon you know the ball is above and going to hit if it was to hit something in that timeslice/frame.
Once you have the polygon that is in question we need to find out if there is an intersection or hit. First, you need to find out its normal (shown in figure 3). This will be used towards creating a transformation matrix (I'll step you through it, don't let that put you off) which will transform the polygon so that it is facing directly upwards, and transform the ball so that it is still in the same position relative to the polygon. For those who dint know how, the normal can be determined by the cross product of two rays that form a triangle on the polygon (IE two sides of the polygon that meet at a corner such as Vector 1 and Vector 2 in Figure 3). This is best with triangles as they have to form a flat plane, whereas quadrilaterals may or may not form a flat face (not all points lie on a plane). Once you have the normal, you need to calculate the cross product of one of the sides with the normal. This will give you completely orthogonal axis that will form our new X,Y, and Z coordinate system, as shown as the resultant Vector in figure 3. I call them x', y', and z' respectively (the dash, not the capitalization). You can think of this as setting up a local coordinate system, rather than a world coordinate system.
Figure 3
For the next bit it is probably easist if you create some sort of matrix class. I created one with 3 vectors called xcomponent; ycomponent; zcomponent; and my constructor for the class takes three vectors, Vector3F x, Vector3F y, Vector3F z, which are assigned to the three componenets. Now just simply plug in the ray that is part of the polygon as the x or z vectors that form the matrix, whilst using the normal that was found earlier as the y component. The missing component (x or z) should be assigned the axis determined by the cross product of the side of the polygon with the normal for a complete orhthogonal set. Note that you could just use two sides of the polygon that meet at a corner, but this would probably distort the ball/polygon so they are no longer the same shape in a sense (if you were to draw them using the new coordinates), which could result in incorrect collision detection if you didnt take this into account.
Once you have those three components for the matrix, you then just need to multiply the vertices of the polygon and the ball position by this matrix to get the new coordinates of the polygon vertices and the ball. I perform my multiplication like this:
Vector3F result;
result.x = vec.x * xcomponent.x + vec.y * xcomponent.y + vec.z * xcomponent.z;
result.y = vec.x * ycomponent.x + vec.y * ycomponent.y + vec.z * ycomponent.z;
result.z = vec.x * zcomponent.x + vec.y * zcomponent.y + vec.z * zcomponent.z;
return result;
where result is the new coordinates of a vertex, and vec is the coordinate of the vertex put into the transformation.
Basically what we have done is now set the polygon to be flat to an axis plane, and set the ball to the correct position relative to the polygon. Now you can simply test if the ball's y position value minus its radius is less than or equal to the y value of any of the vertices on the polygon. If there is then you have detected a collision! If not then there is no collision.
To resolve the collision, I recommend simply putting the ball's position equal to the polygon's y value plus the ball's radius. Then to get back to the regular world coordinates you simply take the trasformation matrix from earlier and invert it. You then multiply the new coordinates you created for the ball and multiply them by that inverted matrix.
Inverting a matrix is really boring/tedious so ill just give you the code. I've tested it, it works. The code is based on http://www.dr-lex.be/random/matrix_inv.html where I took the maths and adapted it to my situation. I kept all his variable names for simplicity.
float a11 = this->xcomponent.x;
float a12 = this->xcomponent.y;
float a13 = this->xcomponent.z;
float a21 = this->ycomponent.x;
float a22 = this->ycomponent.y;
float a23 = this->ycomponent.z;
float a31 = this->zcomponent.x;
float a32 = this->zcomponent.y;
float a33 = this->zcomponent.z;
float determinant = a11 * (a33 * a22 - a32 * a23) - a21 * (a33 * a12 - a32 * a13) + a31 * (a23 * a12 - a22 * a13);
xcomponent.x = a33 * a22 - a32 * a23;
xcomponent.y = -(a33 * a12 - a32 * a13);
xcomponent.z = a23 * a12 - a22 * a13;
ycomponent.x = -(a33 * a21 - a31 * a23);
ycomponent.y = a33 * a11 - a31 * a13;
ycomponent.z = -(a23 * a11 - a21 * a13);
zcomponent.x = a32 * a21 - a31 * a22;
zcomponent.y = -(a32 * a11 - a31 * a12);
zcomponent.z = a22 * a11 - a21 * a12;
//multiply by 1 over determinant
determinant = 1.0 / determinant;
xcomponent.x *= determinant;
xcomponent.y *= determinant;
xcomponent.z *= determinant;
ycomponent.x *= determinant;
ycomponent.y *= determinant;
ycomponent.z *= determinant;
zcomponent.x *= determinant;
zcomponent.y *= determinant;
zcomponent.z *= determinant;
Now that you have the inverted matrix. Multiply the ball coordinates by that to get the correct coordinates for the world. From this point you now have a ball resting on the plane of the polygon. I took this a step further and calculated the angle of reflection at this point by taking the balls current velocity and the normal of the polygons face (original normal in world coordinates, not the normal when the polygon was converted to be aligned to the axis. That would give a straight up normal which would be incorrect unless you performed this step before converting back to world coordinates.) Here is a function that will do this for you.
static Vector3F calculateReflectionVector(Vector3F incidence, Vector3F normal)
{
float value = dotProduct(normal, incidence);
value *= 2;
Vector3F newVector = normal;
newVector.multiplyByScalar(value);
Vector3F reflection = incidence - newVector;
return reflection;
}
You now just set the balls velocity to the reflection vector provided so that it will bounce off the polygon, not just stick to it like a magnet, unless you want it to act like a magnet of course...
Special Thanks To:
www.uploadscreenshot.com for making my life so much easier, allowing me to quickly and easily post pictures/diagrams up for my blogs. Much easier than using the in house image manager that blogger provides.
APPENDAGES
if you want to see the Vector3F class that i use in this tutorial its here:
#ifndef VECTOR3F_H
#define VECTOR3F_H
#include
#include
class Vector3F
{
public: //public attributes
float x, y, z;
public: //public methods
Vector3F(float, float, float);
//Vector3F(const Vector3F &vec);
Vector3F();
/*IMPORTANT - These operater overloader functions are copied from
* OpenGl Game Programming by Kevin Hawkins and Dave Astle, published 2001.
* but additional messages have been added by me, such as the mouswheel one and adjusted mouse movement.
*/
const Vector3F operator +(const Vector3F &vec) // addition
{
return Vector3F(x+vec.x, y+vec.y, z+vec.z);
}
const Vector3F operator -(const Vector3F &vec) //subtraction
{
return Vector3F(x-vec.x, y-vec.y, z-vec.z);
}
//end of copied functions
void setMagnitude(Vector3F);
void setMagnitude(float);
void multiplyByScalar(float);
void outputCoordinates(std::string);
void outputCoordinates();
float calculateMagnitude();
};
#endif
----------------------------------
And the CPP file of the Vector3F class
#include "Vector3F.h"
#include "VectorMaths.h"
#include
#include
#include
#include
Vector3F::Vector3F(float xx, float yy, float zz)
{
Vector3F::x = xx;
Vector3F::y = yy;
Vector3F::z = zz;
}
Vector3F::Vector3F()
{
Vector3F::x = 0;
Vector3F::y = 1; //just to give it a magnitude.
Vector3F::z = 0;
}
float Vector3F::calculateMagnitude()
{
float mag = sqrt( pow(this->x,2) + pow(this->y,2) + pow(this->z,2) );
if(mag == 0)
{
mag = 0; //--------------------------------------this shouldnt happen.
}
return mag;
}
void Vector3F::setMagnitude(Vector3F magnitudeVector)
{
Vector3F::setMagnitude(magnitudeVector.calculateMagnitude());
}
void Vector3F::setMagnitude(float magnitudeAmount)
{
float xx = this->x;
float yy = this->x;
float zz = this->x;
if(magnitudeAmount > 1.0)
{
std::cout << "this is annoying" << std::endl;
}
float magnitude = this->calculateMagnitude();
if(magnitude == 0)
{
std::cout << "SYSTEM ERROR ORIGINAL VECTOR MAGNITUDE IS 0 SO CANT SET AS A MAG" << std::endl;
//temp code
Vector3F::x = 0;
Vector3F::y = 1;
Vector3F::z = 0;
}
//convert to unit vector
Vector3F::x = Vector3F::x / magnitude;
Vector3F::y = Vector3F::y / magnitude;
Vector3F::z = Vector3F::z / magnitude;
//make it aas large as desired
float scalar = magnitudeAmount;
Vector3F::x = Vector3F::x * scalar;
Vector3F::y = Vector3F::y * scalar;
Vector3F::z = Vector3F::z * scalar;
float magnitude2 = Vector3F::calculateMagnitude();
float diff = magnitude2 - magnitudeAmount;
if(diff < -0.5 || diff > 0.5)
{
std::cout << "this is annoying" << std::endl;
}
}
void Vector3F::multiplyByScalar(float scalar)
{
Vector3F::x = Vector3F::x * scalar;
Vector3F::y = Vector3F::y * scalar;
Vector3F::z = Vector3F::z * scalar;
}
void Vector3F::outputCoordinates()
{
std::cout << Vector3F::x << " , " << Vector3F::y << " , " << Vector3F::z << std::endl;
}
void Vector3F::outputCoordinates(std::string s)
{
std::cout << "" << s << Vector3F::x << " , " << Vector3F::y << " , " << Vector3F::z << std::endl;
}
