Dimitrios Christopoulos - Collision detection tutorial

The source code upon which this tutorial is based, is from an older contest entry of mine (at OGLchallenge.dhs.org). The theme was Collision Crazy and my entry (which by the way took the 1st place :)) was called Magic Room. It features collision detection, physically based modeling and effects.

A quite difficult subject and to be honest as far as I have seen until now, there is no easy general solution for it. For every application a slightly different way of finding and testing for collisions can be employed. Of course there are brute force algorithms which are very general but expensive and would work for every kind of objects.

We are going to investigate algorithms which are very fast, easy to understand and to some extend quite flexible. Furthermore importance must be given on what to do once a collision is detected and how to move the objects, in accordance to the laws of physics. So we have a lot stuff to cover. Lets review first what we are going to learn (click on headers to continue).

1) Collision Detection

Moving Sphere Plane

Moving Sphere Cylinder

Moving Sphere Moving Sphere

2) Physically Based Modeling

Collision response

Moving under Gravity using Euler equations

3) Special Effects

Explosion Modeling using a Fin-Tree billboard method.

Sounds using the windows multimedia library (windows only ;()

4) Explaining the code

The code is divided into 5 files.

image.cpp, image.h: code from tutorial 6 to load bitmaps

MagicRoom.cpp: main code of the demo

Tmatrix33.cpp, TMatrix33.h: Classes to handle rotations

TRay.cpp, TRay.h: Classes to handle ray operations

TVector.cpp, TVector.h: Classes to handle vector operations

A lots of handy code. The Vector, Ray and Matrix classes are very useful, a nice library to have. I used them until now for personal projects.

For the collision detection we are going to use algorithms which are mostly used in ray tracing.

Lets first define a ray.

A ray using vector representation is represented using a vector which denotes the start and a vector (usually normalized) which is the direction in which the ray goes. Essentially a ray starts from the start point and travels in the direction of the direction vector. So our ray equation is.

PointOnRay = Raystart + t*Raydirection

t is a float which takes values from [0, infinity).

With 0 we get the start point and substituting other values we get the corresponding points along the ray.

PointOnRay, Raystart, Raydirection, are 3D Vectors with values (x,y,z). Now we can use this ray representation and calculate the intersections with plane or cylinders.

A plane is represented using its Vector representation as

Xn dot X = d

Xn, X are vectors and d is a floating point value.

Xn is its normal

X is a point on its surface

d is a float representing the distance of the plane along the normal, from the center of the coordinate system.

Essentially a plane represents a half space. So all that we need to define a plane is a 3D point and a normal from that point which is perpendicular to that plane. These two vectors form a plane, ie. if we take for the 3D point the vector (0,0,0) and for the normal (0,1,0) we essentially define a plane across x,z axes. Therefore defining a point and a normal is enough to compute the Vector representation of a plane.

Using the vector equation of the plane the normal is substituted as Xn and the 3D point from which the normal originates is substituted as X. The only value that is missing is d which can easily be computed using a dot product (from the vector equation).

(Note: This Vector representation is equivalent to the widely known parametric form of the plane Ax + By + Cz + D=0 just take the three x,y,z values of the normal as A,B,C and set D=-d).

The two equations we have until know are

PointOnRay = Raystart + t * Raydirection

Xn dot X = d

If a ray intersects the plane at some point then there must be some point on the ray which satisfies the plane equation as follows

Xn dot PointOnRay = d

or

(Xn dot Raystart) + t* (Xn dot Raydirection) = d

solving for t

t = (d Xn dot Raystart) / (Xn dot Raydirection)

or by replacing d

t= (Xn dot PointOnRay Xn dot Raystart) / (Xn dot Raydirection)

or by summing it up

t= (Xn dot (PointOnRay Raystart)) / (Xn dot Raydirection)

t represents the distance from the start until the intersection point along the direction of the ray. Therefore substituting t into the ray equation we can get the collision point. There are a few special cases though.

If Xn dot Raydirection = 0 then these two vectors are perpendicular (ray runs parallel to plane) and there will be no collision. If t is negative the collision takes place behind the starting point of the ray along the opposite direction and again there is no intersection. In the code now the function

int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal) {

double DotProduct = direction.dot(plane._Normal); //Dot product between plane normal and ray direction

double l2;

//Determine if ray paralle to plane

if ((DotProduct < ZERO) && (DotProduct > -ZERO)) return 0;

l2=(plane._Normal.dot(plane._Position-position)) / DotProduct; //Find distance to collision point

if (l2 < -ZERO) //Test if collision behind start

return 0;

pNormal = plane._Normal;

lamda=l2;

return 1;

}

It calculates and returns the intersection. Returns 1 if there is an intersection otherwise 0. The parameters are the plane, the start and direction of the vector, a double (lamda) where the collision distance is stored if there was any, and the returned normal at the collision point.

Computing the intersection between an infinite cylinder and a ray is much more complicated that is why I won't explain it here. There are way too many math involved too be useful and my goal is primarily to give you tools how to do it without getting into much detail (this is not a geometry class). If anyone is interested in the theory behind the intersection code, please look at the

Graphic Gems II Book (pp 35, intersection of a with a cylinder). A cylinder is represented as a ray, using a start and direction (here it represents the axis) vector and a radius (radius around the axis of the cylinder). The relevant function is

int TestIntersionCylinder(const Cylinder& cylinder, const TVector& position, const TVector& direction, double& lamda, TVector& pNormal, TVector& newposition)

Returns 1 if an intersection was found and 0 otherwise.

The parameters are the cylinder structure (look at the code explanation further down), the start, direction vectors of the ray. The values returned through the parameters are the distance, the normal at the intersection point and the intersection point itself.

A sphere is represented using its center and its radius. Determining if two spheres collide is easy. Just by finding the distance between the two centers (dist method of the TVector class) we can determine if they intersect, if the distance is less than the sum of their two radius.

The problem lies in determining if 2 MOVING spheres collide. Bellow is an example where 2 sphere move during a time step from on point to another. Their paths cross in-between but this is not enough to prove that an intersection occurred (they could pass at a different time) nor can be the collision point be determined.