Introduction

One of the most intriguing problems when creating a BSP-tree based 3D-engine is collision detection. It is not as hard to solve as to do it fast. In the vast majority of FPS games most of the processor time is consumed when doing collision detection. Consider an object that is moving through the world. It has to be checked against the geometry and all other objects in the world to see that it does not pass through or get too close to any of them. For one avatar or object this can be done with a slow algorithm at an acceptable frame rate. The problem gets quite more complex when several objects and avatars have to be handled each frame. The rendering of the world to the screen has to be done only once each frame, whilst collision detection might need to be done hundreds of times each frame, depending on the number of objects currently moving in the world. So it is of utter most importance that the algorithm used is very fast.

There are several decisions that are needed to make before starting to design an algorithm to handle collisions. The objects must be encapsulated in one or more simple geometric shapes, since it is not be possible to check every single polygon in an object for collisions against everything and still have an acceptable frame rate. I chose to encapsulate each object in an ellipsoid, with one collision radius in the xz-plane and one collision radius in the y-axis. If several shapes are chosen there is a need of making them interact with each other, which is quite a complex problem. Below is an example of how to encapsulate a human:

Figure 1: A human encapsulated in an ellipsoid

Then you need to decide what should happen when an object collides with something. One variant is that if a collision is detected the move is prohibited and the object will stay in the original position, this will give a very bad behavior such as bouncing against the walls. In the figure below two moves of equal length are shown, the move to position a will be prohibited and the object will remain in the same position, but the move to position b will take place. This means that you can get closer to walls if you move along them, while a move straight towards a wall will be prohibited much earlier. Hence objects will bounce against the walls.

Figure 2: Prohibited and allowed move

In the figure above the move to position a will not be allowed, but the move to b is allowed. Another drawback with this idea is that the walls will behave as if they have “glue” on them, since the objects will get stuck to them when trying to move along them. A better way to do it is to let the objects slide against walls and other objects. This will be a less efficient way, but will give a much smoother result. This is the way I chose to do it.

Movement of an object can be divided in to three parts[1]:

1. Future Position Calculation
2. Collision Detection
3. Collision Handling

For each frame an object that moves in the world has to pass each of these steps.

Future Position Calculation

The easiest part is calculating which position the object will end up in given the original location, speed, acceleration, direction, current friction coefficient and time passed during that frame. We chose to use meters and seconds as units in our calculation, further more that we chose to discard the mass of objects and assume that all objects has a mass of 1. To simplify things we assume that the gravity always is applied downwards and that a user only can apply force in the xz-plane. In our solution the following steps are taken to calculate an objects future position:

1. Deduct the speed reduction caused by friction. The friction coefficient (0.0-1.0) is subtracted from the acceleration in the xz-plane. Since the mass is assumed to be 1, no more calculations need to be done at this point.
   
   Formula:
     Acceleration(x,z) -= Friction
   
   
2. Add the force input from the user to the acceleration vector in x- and z-direction. Multiplying the force added by the user with the frame time and then adding the resulting vector in x- and z-direction to the acceleration vector calculate this. We consider the mass to be 1, so that the force applied is in the unit Newton/kg.
   
   Formula:
     Acceleration(x,z) += Force * Normalize (Direction(x,z))
   
   
3. Set gravity to the acceleration in y-direction. The traditional gravity can be used (9.82) but in games this will be quite boring, since the falls will be too fast, so it’s quite common to use lower gravity.
   
   Formula:
     Acceleration(y) = -Gravity
   
   
4. Add the acceleration to the movement vector, this is done by adding the acceleration in x and z-direction multiplied with the frame time. It’s a good idea to limit the movement speed in x- and z-direction so that the objects will reach a maximum speed at sometime, otherwise a constant input of force will lead to an infinitely accelerating object.
   
   Formula:
     Movement = Movement + Acceleration * FrameTime
   
   
5. Now the position modifier for this frame has to be calculated. Multiply the movement vector by the frame time and the resulting vector is the distance the object travels this frame.
   
   Formula:
     Distance=Movement * FrameTime
   
   
6. The desired new position can now be calculated. Add the distance traveled to the current position and the result is the position the object will end up in this frame if it passes all collision checks.
   
   Formula:
     NewPosition = Position + Distance

Now it is time to check if the desired position is a valid position.

Collision Detection and Collision Handling

This is one of the trickiest parts in a BSP-tree engine. There are several aspects to consider when designing this step in a physics engine. First of all the efficiency is of great importance, since this is the part that hogs most of the processor time. Secondly the accuracy of the detection is of great concern, it is hard to get good accuracy without having to reduce the efficiency of the algorithm. So there is a trade-off between correctness and efficiency. Collision handling is not as difficult though but it is of great concern, since this is what will give the right "feeling", a poor and jumpy collision handling will lower the overall appearance of any game.

This is where BSP-trees show their strength. Most engines do not use the BSP-tree to speed up the drawing, such as portal engines, but still almost all of them have built a BSP-tree out of the geometry. This is because of the great advantage when calculating the collision detection, namely that it is very cheap to position the user in the BSP-tree. When that is done, the only polygons needed to be checked; are the polygons in the leaves the object passed through that frame.

One of the other strengths of the BSP-tree is that each leaf contains a convex set of polygons in the original design of BSP-trees. This means that the polygons can be tried for collision in any order. If the sets are not convex, as in our BSP-tree, the polygons have to be checked against in order of facing. We use a term called facing value to describe the value that tells how a polygon is directed compared to an object; this is calculated by taking the dot product of the normalized movement vector for the object and the normal for the polygon, which will return a value between –1 and 1. Where –1 means that the polygon is facing straight towards the movement direction of the object and 1 means that it is facing in the same direction as the object is moving.

The order of testing is; first test the polygon that has the lowest facing value, and then the polygons are checked in order up to the polygon with the highest facing value. Below is a set of figures that show why the polygons must be taken in that order.

Figure 3: Object move

In the figure above the facing value is lower for polygon 1, since the dot product between the objects movement vector and polygon 1's normal is less than the same value for polygon 2. So if we were to check collisions versus polygon 2 first, the result would look as follows.

Figure 4: Incorrect collision

In the figure above the object avoided collision with polygon 2. The end position has been corrected so that the object does not collide with polygon 2. The feeling of the result would be that the object passed through polygon 1. If the check for collision was made versus polygon 1 first the result would have looked like this:

Figure 5: Correct collision

In Figure 5 the movement has been corrected more accurately, since the object avoided collision with polygon 1 first. The end position has been corrected so that the object does not collide with polygon 1. When the BSP-tree contains only convex set of polygons there is no need to sort the polygons in the same node, but still the nodes have to be traversed in the same order as they were passed through.

In order to make a fast collision detection algorithm, a cheap test that can discard a large number of polygons from further testing is needed. This is done by calculating so called side values. The side value is a value for the distance between the objects center and the plane that the polygon is in; see the figure for better description.

Figure 6: Side value

In Figure 6 the length of the dotted line is the so-called side value. The further away the object is from the polygon, the greater the side value is. When the side values are calculated, it can be decided whether an object could have passed through the polygon. To calculate a side value the objects position is put into the plane equation of the polygon, but the distance value in the plane equation is subtracted instead of added. In this way we will have a value that is the distance between the object and the plane. By calculating the side value for the start position and the end position we can easily decide whether the object passed the plane or not.

There is one problem though; since we chose to represent objects with a bounding ellipsoid the collision radius of the object in the polygon's normal's direction has to be calculated. To do this, the x- and z-component of the polygons normal is multiplied with the xz-collision radius of the object and the y– component of the polygons normal is multiplied with the y-collision radius of the object. The length of the resulting vector is the collision radius for the object versus that polygon. Following is a figure and a formula to better describe the collision radius.

Figure 7: Collision radius

In the figure above the dotted line represents the effective collision radius of the object towards the polygon. Observe that the line is perpendicular to the polygon.

CollisionRadius(Object, Polygon) = Sqrt((Object.xzColl * Polygon.Normal.x)2 +
                                        (Object.yColl * Polygon.Normal.y)2 + (Object.xzColl *
                                        Polygon.Normal.z)2)

Now we can decide whether the object actually passed through the plane. Following is the algorithm to perform this test, together with a helper function to calculate the collision radius for an object in a given direction:

► CALCULATE-COLLISIONRADIUS
* Indata:
*   Object – The object to get the collision radius for.
*   Direction – The direction to calculate the collision radius in.
* Outdata:
*   The collision radius of the object in the given direction.
* Effect:
*   Calculates the objects collision radius in the given direction.

CALCULATE-COLLISIONRADIUS (Object, Direction)
1 return Sqrt((Object.xzColl * Direction.x)2 +
              (Object.yColl * Direction.y)2 +
              (Object.xzColl * Direction.z)2)

► PRE-CHECK-COLLISION
* Indata:
*   Object – The object to check collision for
*   Polygon – The polygon to check the object towards
* Outdata:
*   Whether the object passed through the plane defined by the polygon
* Effect:
*   Checks if the object passed trough the plane defined by the polygon.

PRE-CHECK-COLLISION (Object, Polygon)
  // Calculate the effective collision radius of the object towards
  // this polygon.
1 CollisionRadius = CALCULATE-COLLISIONRADIUS (Object, Polygon.Normal)
 
  // Calculate distance between the plane and the objects start
  // position.
2 StartSide = Object.StartPosition.x * Polygon.Normal.x +
              Object.StartPosition.y * Polygon.Normal.y +
              Object.StartPosition.z * Polygon.Normal.z -
              Polygon.Distance
 
  // Calculate distance between the plane and the objects end
  // position.
3 EndSide = Object.EndPosition.x * Polygon.Normal.x +
            Object.EndPosition.y * Polygon.Normal.y +
            Object.EndPosition.z * Polygon.Normal.z -
            Polygon.Distance
 
  // If the two points is on different sides of the plane, multiplying
  // the two values will give a negative result, indicating that the
  // object passed through the plane.
4 if ((StartSide – CollisionRadius) * (EndSide – CollisionRadius) < 0)
5     return true
6 else
7    return false

PRE-CHECK-COLLISION determines whether an object passed through the plane defined by a polygon, but it does not consider the boundaries of the polygon. We need further testing for the polygons that passed this test, namely a test that determines if the object passes within the boundaries of the polygon. This test is quite expensive so the more polygons that are discarded in the earlier stage the better. First we have to check if the polygon is inside the cylinder created by the object’s move. See the following figure.

Figure 8: Testing if a object passes through a polygon

In the figure above the object moves from the start location to the end location. Both locations are on different sides of both polygons. But the cylinder (the gray area in the figure) created by the move of the object only passes through polygon 1.

In order to perform this test, we need to calculate perpendicular planes for the polygon. They can be calculated once and for all when a polygon is created to save time. Perpendicular planes are planes with a normal perpendicular to the normal of the polygon and facing inwards. There are three perpendicular planes for a triangle, one for each edge. We have illustrated how it looks in the figure below.

Figure 9: Perpendicular planes for a triangle

Each perpendicular plane is calculated by the cross product of the direction vector of the edge it is aligned on and the normal of the polygon, and normalizing the resulting vector. If the result gives an outward facing normal, it is inverted. The distance of the perpendicular planes is calculated by the dot product between the normal of the perpendicular plane and one of the vertices on the edge the plane is aligned on. For example the perpendicular plane between p1 and p2 in the figure is calculated as follows.

1. PerPlane.Normal = Normalize (Direction (p1, p2) x Polygon.Normal)
2. if(Perplane.Normal * p3 < 0) invert(PerPlane.Normal)
3. PerPlane.Distance = PerPlane.Normal*p2

If the object were a single a point we would only need to check it is on the positive side of each of the perpendicular planes, thus indicating that the object is within the polygon. But since the object has a collision radius we cannot just take the planes that are along the edges, we need to move them outwards a bit. So each of the perpendicular planes are moved a collision radius from the center of the polygon, calculated by deducting the collision radius from perpendicular plane’s distance value. This will still leave us one problem, illustrated in the following figure:

Figure 10: Moved perpendicular planes

Obviously the planes are encapsulating a too big area. The distance between p1 and the intersection of perpendicular plane 1 and 3 is too long. The same is true for each of the other corners. To correct this the objects position needs too be checked so that it inside three more perpendicular planes. Let us copy perpendicular plane 2 in the figure above and move it to p1. Then move it the collision radius of the object further away, and invert the normal of that plane. That corrects the problems. This is done for each the vertices opposing plane. The figure would look like this then:

Figure 11: The effective collision area of a triangle

The gray area in the figure above is the area in which an object will be considered as inside of the polygon. Even this area is not exactly correct, where as the corners will be a bit too far away, but the result is good enough. Using the exact area would be much too expensive since we would have to use an infinite number of planes in the corners of the area. Below is figure that illustrates the correct appearance of the area.

Figure 12: The correct collision area of a triangle

Now we can detect whether an object collides with a polygon or not. The algorithm for doing this can shortly be put down as this:

► GET-COLLIDING-POLYGON
* Indata:
*   Object – The object to check collisions for
*   PolygonSet – The polygons to check collisions versus
* Outdata:
*   The polygon that the object collides with.
* Effect:
*   Loops through all polygons in the polygon set and checks if the
*   object’s movement is obstructed by a polygon or not.

GET-COLLIDING-POLYGON (Object, PolygonSet)
1 for each polygon P in PolygonSet in order of increasing facing value
 
      // If the object passes through the plane defined by the polygon,
      // further testing is needed.
2     if (PRE-CHECK-COLLISION (Object, P))
 
          // Test each of the six perpendicular planes.
3         for each perpendicular plane Pl in P
 
              // The effective collision radius the object towards the plane is
              // the width of the object in the direction of the planes normal.
4             CollisionRadius = CALCULATE-COLLISIONRADIUS (Object, Pl.Normal)
 
              // Move the plane backwards the collision radius of the object.
5             Pl.Distance = Pl.Distance - CollisionRadius
 
              // Calculate distance between the plane and the objects
6             Side = Object.Position.x * Pl.Normal.x +
                     Object.Position.y * Pl.Normal.y +
                     Object.Position.z * Pl.Normal.z -
                     Pl.Distance
 
              // If the object is on the negative side of this plane, the object is
              // not within the polygon and we can skip further testing on this
              // polygon.
7             if ( Side < 0 )
8                 goto step 1

          // If we reach this point the object was within all perpendicular
          // planes and we can return this polygon as the polygon the object
          // collided with.
9         return P
 
   // We couldn’t find a polygon that the object collide with so we
   // return no polygon.
10 return NOPOLYGON

Complexity Analysis

Since this is a very frequently used function during run time it is of utter most importance that it is effective. As it is now it is not effective enough, the order of the function is dominated by the sorting of the polygons needed on line 1, using an effective sorting algorithm such as quick sort, the order will be O(n lg n), where n is the number of polygons in the incoming set. We need to be closer n. We will have to re-write this function later on.

Every frame GET-COLLIDING-POLYGON will be called until there is no colliding polygon left in every node the object passes through. Now that we can detect whether an object collides with a polygon or not, we need to handle objects colliding with objects. This is a much simpler task and it can be done with just a few calculations. First a direction vector between the centers of the two objects is calculated and normalized. Then the collision radius for both objects is calculated in that direction, in the same way as it was calculated in the polygon collision case. If the distance between the two object’s centers is less than the sum of the two collision radii the objects collide and collision handling needs to be done. Below is an algorithm to determine if two objects collide.

► OBJECTS-COLLIDE
* Indata:
*   Object1 – The object that moves.
*   Object2 – The object to check collision towards
* Outdata:
*   Whether the first object collide with the second object or not.
* Effect:
*   Checks if the two objects collide.

OBJECTS-COLLIDE (Object1, Object2)
 
  // Calculate the direction vector between the two objects
1 Direction = GET-DIRECTION (Object1.EndPosition, Object2.Position)
 
  // Calculate the both collision radius in that direction.
2 CR1 = CALCULATE-COLLISIONRADIUS(Object1, Direction)
3 CR2 = CALCULATE-COLLISIONRADIUS(Object2, Direction)
 
  // Calculate the distance between the two objects
4 Distance = GET-DISTANCE (Object1.EndPosition, Object2.Position)
5 if (Distance < CR1 + CR2)
6     return true
5 else
6     return false

OBJECTS-COLLIDE will be called once for every object in the nodes the moving object passes through.

When collision between an object and a polygon or an object and another object is detected, the end position of the moving object needs to be corrected. In the case of collision versus a polygon, the corrected end position that is calculated with the following formula:

EndPosition += Polygon.Normal*(CollRadius-EndSideValue)

The effect of this formula will be that objects "slide" against the walls as opposite to get stuck against walls which would be the case if the end position was set to the start position every time a collision was detected.

In the case of collision between two objects the end position for the moving object is corrected according to the following formula:

EndPosition += Direction * (CollRadius1 + (CollRadius2-Distance))

In the above formula, Direction is the direction between the moving object’s end position and the other object’s current position, CollRadius1 is the moving object’s collision radius in that direction, while CollRadius2 is the other object’s collision radius in the direction and Distance is the distance between the end position of the moving object and the other object’s current position.

When the position is corrected it might be that the object is moved so that it collides with a previously passed polygon or object. So each time a collision is detected the collision detection needs to be restarted from the beginning. This can become very expensive in complex environments, so it is recommended to put some upper limit for the number of iterations. When that number of iteration has passed and collisions are still detected the end position will be set to the object’s start position.

Since sorting the polygons by facing value every time a node is checked for collision would take much too long time, another solution is better. In every iteration: loop through all polygons and remember the one with the lowest facing value that was in the way for the moving object. If a collision was detected when all polygons in a leaf has been checked against, collision handling will be done towards that polygon. Then the loop will be restarted from the beginning. This will give that the collisions will be taken in order of facing as was mentioned earlier in this article. So our re-written GET-COLLIDING-POLYGON will look like this:

► GET-COLLIDING-POLYGON
* Indata:
*   Object – The object to check collisions for
*   PolygonSet – The polygons to check collisions versus
* Outdata:
*   The polygon that the object collides with.
* Effect:
*   Loops through all polygons in the polygon set and checks if the
*   object’s movement is obstructed by a polygon or not.

GET-COLLIDING-POLYGON (Object, PolygonSet)
1  LowestFacing = INFINITY
2  CollidingPolygon = NOPOLYGON
3  for each polygon P in PolygonSet
 
   // If the object passes through the plane defined by the polygon,
   // further testing is needed.
4  if (PRE-CHECK-COLLISION (Object, P))
 
       // Test each of the six perpendicular planes.
5      for each perpendicular plane Pl in P
 
           // The effective collision radius the object towards the plane is
           // the width of the object in the direction of the planes normal.
6          CollisionRadius = CALCULATE-COLLISIONRADIUS(Object, Pl.Normal)
 
           // Move the plane backwards the collision radius of the object.
7          Pl.Distance = Pl.Distance - CollisionRadius
 
           // Calculate distance between the plane and the objects
8          Side = Object.Position.x * Pl.Normal.x +
                  Object.Position.y * Pl.Normal.y +
                  Object.Position.z * Pl.Normal.z -
                  Pl.Distance
 
           // If the object is on the negative side of this plane, the object is
           // not within the polygon and we can skip further testing on this
           // polygon.
9          if ( Side < 0 )
10             goto step 1
 
       // If we reach this point the object was within all perpendicular
       // planes, so if this polygon has lower facing value than the lowest
       // facing value this far, we will remember this polygon.
11     FacingValue = P.Normal.x * Object.MovementDirection.x +
                     P.Normal.y * Object.MovementDirection.y +
                     P.Normal.z * Object.MovementDirection.z
12     if (FacingValue < LowestFacing)
13         CollidingPolygon = P
14         LowestFacing = FacingValue

   // Return the remembered polygon, might be no polygon if no colliding
   // polygon was found.
14 return CollidingPolygon

Complexity Analysis

Now we only loop through all polygons once, so the order of this algorithm is O(n), where n is the number of polygons in the incoming set.

In our solution we set a maximum of 5 iterations for the polygons, but of course this is very dependent of how complex the scene is, where a more complex scene could require more iterations. The following  is the collision loop that is done once every frame for every moving object.

► COLLISION-HANDLING
* Indata:
*   Object – The moving object
* Outdata:
*   None
* Effect:
*   Checks the objects movement versus every polygon and object in the
*   nodes the object passes through. When collision is detected, it
*   will be handled.

COLLISION-HANDLING (Object)
1  PolygonSet = {}
2  for each node N the object passes through
3      PolygonSet = PolygonSet U N.PolygonSet
4  Iterations = 0
5  while ( Iterations <= MAXITERATIONS)
6      Polygon = GET-COLLIDING-POLYGON (Object, N)
7      if (Polygon = NOPOLYGON)
8          goto step 14
9      CollisionRadius = CALCULATE-COLLISIONRADIUS(Object, Polygon.Normal)
10     EndSide = Object.EndPosition.x * Polygon.Normal.x +
                 Object.EndPosition.y * Polygon.Normal.y +
                 Object.EndPosition.z * Polygon.Normal.z -
                 Polygon.Distance
 
       // Move the end position of the object so that it will not collide.
11     Object.EndPosition = Object.EndPosition + Polygon.Normal * (CollisionRadius - EndSide)
12     Iterations = Iterations + 1

       // The only way to reach this step is if there were more collisions
       // than then maximum number of iterations. This move is considered
       // illegal so we set the end position to be the original position.
13 Object.EndPosition = Object.StartPosition
14 for each object O in the nodes the object passes through
15     if (OBJECTS-COLLIDE (Object, 0))
 
           // Calculate the direction vector between the two objects
16         Direction = GET-DIRECTION (Object1.EndPosition, Object2.Position)
 
           // Calculate the both collision radius in that direction.
17         CR1 = CALCULATE-COLLISIONRADIUS (Object1, Direction)
18         CR2 = CALCULATE-COLLISIONRADIUS (Object2, Direction)
 
           // Move the end position of the object so that it will not collide.
19         Object.EndPosition = Object.EndPosition + Direction *
                                (CollRadius1 + (CollRadius2-Distance))

Complexity Analysis

The collision loop is of order O(i n), where n is the number of polygons in the nodes the object passes through and i is the maximal number of iterations (which could vary).

There is at least one obvious optimization that is very easy to implement, that is to only calculate the collision radii once per polygon-object and object-object pair. But we chose to present this way, unoptimized, out of clarity reasons. Probably there are some more obvious things that can speed up the process, but we leave them to you.

Related Reading

• Nuydens, Tom. 3D Engine Column, Delphi3D
• Magarshak, Greg. Theory and Practice
• Lin, Ming C. Fast Collision Detection for Interactive games
• UNC Collide Research Group, Collision Detection
• Bikker, Jacco. Building a 3D Portal Engine

References

1. Magarshak, Greg. Theory and Practice