Collision Detection Algorithm, version 2.1

 

Developed for project Largo by

Torbjørn Vik

Ståle Furset

Rolv Seehuus

 

[ Changes ]

We decided that we wanted a general line-face intersection algorithm, and not just stick to lines who follow the coordinates’ axis. This lead to some major changes on level 4 of the algorithm, but the result now gives the actual intersectionpoint, not just a booleanvalue.

 

[ Changes 2 ]

The algorithm is slightly extended to work properly with huge amounts of snakesegments to test against. See section "Snok extension" for further description.

Torbjørn Vik 26.05.00

 

[ Problem ]

This algorithm is supposed to detect collisions within a virtual 3-dimensional world. As for now, we aim for collisiondetection between the camera (the player) and the world around him. To give the camera a certain size in space, we define it by a boundingbox. A boundingbox is a cube, built up of two coordinates: (xmin, ymin, zmin) and (xmax, ymax, zmax). These coordinates will change as the camera moves around in the world, possibly hitting some of the walls. The world is defined by an array of objects. Each object is built up of two arrays, one array with vertices (x,y,z-coordinates), and one array with triangles. The triangles are built up of three indexes into the verticearray.

 

[ Solution ]

The algorithm will work on several different levels of complexity. We define the levels roughly as following:

Level 1: Test if the camera’s boundingbox intersects with any of the objects’ boundingboxes.

Level 2: Test if the camera’s boundingbox intersects with any of the boundingboxes of the object’s triangles.

Level 3: Test if any of the lines in the camera’s boundingbox intersects with a polygon’s boundingbox.

Level 4: Test if a line in the camera’s boundingbox intersects with a triangle.

The total algorithm is built up of all these levels. If a test on level 1 indicates a collision, we’ll have to run further tests to verify that an actual collision has occured. Same goes for level 2 and 3. Only if a test on level 4 returns true, we can be absolutely sure of an actual collision. It is fully possible that all tests on level 1, 2 and 3 return true, but when we run the final test on level 4, it turns out there was no collision at all. The three first levels in the algorithm is just a method of avoiding the heavy calculations that will be performed on level 4.

 

[ Algorithm, level 1 ]

If any of the camera’s boundingboxcoordinates is inside the boundingbox of an object, this test will return true. The test will also have to be done in the opposite direction, or else an object that is totally inside the camera’s boundingbox will not be detected as a crash.

 

[ Algorithm, level 2 ]

This test will be performed in a similar way as the test on level 1. The difference is that the test must be performed against the boundingbox of a triangle. This boundingbox has to be calculated for each frame, as precalculation will consume too much memory.

 

[ Algorithm, level 3 ]

The lines of a boundingbox will always be parallell with one of the axis of the worldcoordinatesystem. This line’s boundingbox is to be tested against the boundingbox of a triangle , to dump even more level 4 tests.

 

[ Algorithm, level 4 ]

The inputs to this level of testing, will be a line defined by two vertices (V0 and V1) , and a triangle defined by three vertices (T0, T1, T2). By calculating and using the vectors of the triangle, we may set up the equation for an infinite plane. If we then extend our line to an infinite length, there will always be an intersection point with the plane, as long as the line isn’t entirely paralell with the triangle.

The formula for the line, defined by a factor t (t represents a scalingfactor of the original line).

X(t) = V0.X + (V1.X – V0.X)*t

Y(t) = V0.Y + (V1.Y – V0.Y)*t

Z(t) = V0.Z + (V1.Z – V0.Z)*t

A plane may be defined by two vectors. To find the correct equation, the two vectors is used to calculate the planes normalvector (N). By using one of the three vertices in the original triangle, we define a general vector that exist in the plane.

 

The plane is then defined by all values of x,y,z that solves the following equation:

 

The dotproduct of the plane’s normalvector and any vector that exist in the plane, should be zero, as the dotproduct of two vectors always produce zero if the angle between them is 90°.

This gives us the following equations:

 

We have four equations and four unknowns: X, Y, Z and t. These equations may be used to calculate t, which in turn gives the actual position of intersection.

 

Study the rendered picture. There’s a green triangle, a triangle defined by the three vertices T0, T1 and T2. Besides the triangle is a dot that represents the previously calculated intersectionpoint. This intersectionpoint does always exist in the same plane as the triangle, but not necessarily within the triangle. The next step is to decide whether the point is inside or outside the triangle.

 

This three dimensional problem may be reduced to a two dimensional problem, simply by projecting both the triangle and the point to one of the coordinate system’s planes (XY, XZ or YZ). In the rendered picture (positive Y-axis up), the green triangle’s Y-coordinate has been set to zero, and the result is the gray triangle that lies in the XZ-plane. (If the triangle already lies in one of the planes, this plane has to be used, else the projection onto the two other planes would give a straight line.)

 

The figur on the left illustrates the projection of the triangle, represented by the three vectors a, b and c. Any point along the vector c, may be represented as a weighted sum of vector a and b.

 

...where k is a number in the range [0, 1]. The vector d is the vector from T0 to I, where I is our intersection point. The vector d can also be written as a weigthed sum of a and b.

 

This two values, r and t, contains the solution. They may be calculated by using the following equations (for XZ-plane projection):

 

To confirm the state of the intersection point, r and t has to be evaluated;

-         if r and/or t is < 0, I is outside

-         if r + t > 1, then I is outside

-         if r + t < 1, then I is inside.

 

These three statements are achieved from the calculations just performed. Voila.

 

[ Snok Extension ]

 

During the game, accurate collision detection between the player and the other snakes is required. As the snakes grow and reach great length, these calculations will occupy a unacceptable portion of the cpu using the original algorithm described. Geometry describing the snakes does not consist of random handmade polygons such as the level itself, but will always be built up of sylindrical segments. This fact make room for spesific optimization techniques applying to collision detection between a boundingbox and another snake's body.

 

In the original algorithm, one of the first tests is whether the boundingbox (the camera) and the boundingbox of an object intersects. This test is more or less useless when it comes to snake-snake intersection, as a boundingbox fencing an entire snake would not be suitable for eliminating any significant sections of geometry. Consider the figure on the right; a boundingbox fencing this model will result in the blue lines, covering a much larger portion of space than the actual geometry. When running collision detection test, a test on polygon-to-polygon level would be triggered as soon as the snake's head enters the boundingbox of another snake. This means all the faces in the snake's body will be tested. This is not desirable.

 

The new approach is to create a boundingbox for each segment of the snake, thus eliminating 16 faces in each boundingbox vs. boundingbox-test (each segment consist of 16 faces). The figure on the right, illustrates how this could be achieved. When the player's boundingbox intersects with one of these boundingboxes, a test against these 16 spesific faces are triggered. These calulations should be performed using the formulas derived on level 4 of the original algorithm.

 

Torbjørn Vik, 26.05.2000