Chapter 16: 3D Collision Detection and Response

 Download CD Content

Introduction

Simply put, collision detection is the process of determining if two objects have collided by testing their bounds or a spatial overlap. The word objects can be used to mean many different things, such as statistical data or even ideas, but in 3D games we usually mean geometric objects. Collision detection is inherently a boolean operation, that is, for any given objects there exists either a collision or there does not—their collision is either true or false. Often, determining this is enough to handle the collision and then continue with other collision testing or game logic. However, simply determining collision detection may not provide enough information to handle the collision in a particular way, for example, when affecting object motion. In this case, we may need to compute object intersections as well. An intersection is the point or set of points at the location where one line, surface, or solid crosses another during a collision.

The process of collision detection can generate what we call collision events. An event is simply a point in time and space. Collision events would typically also have references to the two colliding objects and any other useful information based on how the collision should be handled.

The process of handling the collision is called collision response or reaction. What should happen or how the objects or surfaces involved in the collision event react is based on game design. Collision response can be as simple as removing the colliding objects, say, in the case of a weapon projectile hitting a target, or as complex as simulating the physical reaction that would result when two real objects collide.

In addition, for resolving contacts, a description of the contact area is often required. This is often called the penetration depth of the collision. The penetration depth of a pair of intersecting objects is the shortest vector over which one object needs to be translated to bring the pair in touching contact so that they are no longer interpenetrating. This is often the first step in creating a physical-looking collision response.

Collision detection has been studied and developed in many different disciplines far beyond games, including robotics, computer graphics, computer-aided design, and computational geometry. There are as many approaches and algorithms for collision detection as there are systems computing it. More specifically, there is no standard way to do general 3D collision detection. Some systems precompute collision detection in advance of the motion they are analyzing, such as in some factory robotic systems. Other systems can afford only inaccurate collision detection, possibly for object selection or high-level decision making, which can be implemented with approximation techniques.

Collisions in Games

Depending on the actual gameplay desired, 3D games can sometimes require the most demanding real-time collision detection systems. The constraints are confining and demanding. The collision detection must execute as quickly as possible and as accurately as possible given the game geometry, on consumer-level processing hardware and in relatively low-memory systems. Implementing collision-detection techniques within these constraints makes game-collision detection a challenging topic in game development.

Good collision detection and reaction is fundamental to a positive gaming experience. Collision detection is central to 3D games that simulate interactions of the physical world. Even in games that are not performing physical simulations, collision detection is important for all kinds of other gaming operations. For example, as was expressed in Chapter 15, “3D Render Using JOGL,” view frustum culling for render engines is at its core a collision-detection problem. One of the best ways game AI can assess the game world situation for decision making is by using data gathered from collision detections. Finally, player game control is often based on interaction through collision detection.

Collision detection can be done in many ways. There isn’t a single generic algorithm that works for all collision types. Depending on the objects being represented by the game, completely different-collision detection techniques may be used for different classes of objects. In addition, what the objects are doing at the stage where collision will be computed can affect which collision detection algorithm to use. For example, fast-moving objects often need collision detection algorithms that are significantly modified from their static and slower moving objects’ counterparts. Often they will use different geometry than the actual object being represented.

Usually game data is organized to make collision testing as efficient as possible. Only the bare minimum should be computed to prevent wasting any runtime cycles. There is no point in computing the intersection volume of a sphere and a cylinder if simply finding that an overlap exists will do. In addition, there are often different techniques for computing collision detection versus computing intersections of a set of objects, and it pays to know what needs to be computed in advance of the tests.

Basic Collision-Detection Processing

Collision detection requires special data structures and management, and objects often need to be processed together in groups to achieve maximum performance for general scenes. Also, at what point in the game execution collision detection is processed can have direct impact on the accuracy and response perceived by the player. Typically, it is the last thing done before the scene is set for the render frame. Using collision detection for game objects could be processed as described in the following stages as shown in Figure 16.1.

Figure 16.1: The Collision detection process.

For each game object:

1. Compute the object’s new movement based on user input, AI control, game events or physics.

2. For collidable objects, check if the new movement violates any other game geometry via collision detection.

   1. If no collision occurs, then the motion is allowed. Do nothing.

   2. If collision occurs, determine the desired reaction, such as generating a game event (power up, explosion, and so on), correcting the movement based on collision information, or compute reaction motion.

3. Render scene.

4. Rinse and repeat.

Even with this general sequence, it’s possible that some game collision testing won’t quite fit in so well. For example, user input in the form of mouse clicks or other picking mechanisms, as well as instantaneous weapons such as a laser beam or even bullets, may need to have collision detection computed in the action routines. Because these types of actions are not implemented as objects moving through the world, they require immediate collision tests and collision events processing outside of step 2, where the general object-to-object collision detection is processed.

In a ideal game engine, collision detection would be precise, efficient, and very fast. These requirements mean that the collision-detection process will need to have fast access to the scene geometry. Unfortunately, modern games contain too much 3D data for per-frame brute-force methods to finish quickly enough. More elegant methods have been developed, because checking each polygon of an object against every other polygon in the scene takes too long. Even determining whether an object’s geometry only penetrates the world’s geometry would be too computationally expensive with this method.

A note about 2D collisions: when applicable, use 2D collision tests for 3D worlds. There are many cases where a cheaper 2D test can be used in place of a more expensive 3D algorithm. For example, finding the local ground triangle on which a character is located may be possible to do in 2D if the ground on which the character is standing holds its basic shape when projected flat. Many terrain collision systems use only a character’s x- and z-coordinates to quickly find the triangle they would be standing on from a table and then compute the y-coordinate (height) at the point on the triangle. This method is much cheaper than performing general 3D triangle tests, which would yield the same results.

Bounding Volumes

The most popular way of improving collision-detection performance is to approximate each object or a part of the object with a bounding volume, and then process the bounding volumes of collision (see Figure 16.2). This method is widely used for approximate collisions but also in place of accurate and exact collisions instead because it’s much more computationally efficient than computing exact collisions.

Figure 16.2: Example bounding volume types.

Whereas simpler bounding volume collision calculations are much quicker than processing the more complex visual scene geometry, the collision results are imprecise and may often require further refinement, depending on the need for accuracy. Using bounding volumes collision detection as a first step before processing the bounded geometry for the final, more accurate tests offers a good balance between final execution speed and collision accuracy.

In addition, it is possible to process individual object bounding volume pairs one at a time, followed by exact collision detection on passing candidates or while queuing the candidates for later bulk exact collision-detection processing. Unfortunately, this is terribly inefficient for the large scenes of today’s games.

Efficient and Accurate Collision Detection for Complex Scenes

As scene complexity increases, even scene geometry wrapped in bound volumes will become too expensive to test because in a general collision system, each collidable bounding object needs to be compared to every other one, making the final bounds-to-bounds test equal to the square of the number of collidable objects. For example, in a scene with 100 possible collidable bounding volumes, there would be 99 * 99 = 9801 collision tests! (99 because for any object it must test against the remaining 99, but not itself.) That is a lot of tests for 100 objects, and a typical game these days could contain more than a 1,000 collidable world objects or surfaces.

Bounding Volume Hierarchies

One technique for greatly reducing the n² object pair testing is to use a hierarchy of bounding volumes. A hierarchy of bounding volumes or spatial partition groups greatly improves performance, albeit with a tradeoff in memory use. Let’s look at an example.

We could represent a whole group of objects as one large sphere completely containing the group of objects and then check whether the large sphere intersects with any other objects’ bounds in the scene. If collision is detected, to increase the precision we can subdivide the big sphere into a set of smaller spheres and check each one of those for collision as well. (See Figures 16.3 and 16.4.) We can then continue to subdivide and check until we are satisfied with the approximation. This is the basic idea of a bounding volume hierarchy. If the hierarchies’ subdivisions and group bounds are properly built in advance of the collision testing, the bounding collision tests can be performed quickly and efficiently at runtime.

Figure 16.3: Simple bounding volume hierarchy.

Figure 16.4: Complex bounding volume hierarchy.

Collision object hierarchies and bounding volume collision detection really go hand-in-hand to complete an optimal collision system. The overall collision detection cost is decreased because the hierarchy makes finding potential collisions faster than large linear searches that would be used on a scene list. Also, in an elegant way, they allow us to trade accuracy for speed, depending on how we build and use the hierarchy.

Collision Engine Design

For large, complex scenes, collision detection can be implemented as a several-stage process and can be further developed into an engine of sorts that can be integrated with game logic and render engines as illustrated in Figure 16.5. Specifically, real-time collision detection can be split into at least three distinct steps:

Figure 16.5: Collision engine design.

Process Hierarchical Collision Detection: Called sweep and prune or collision culling, this step produces potential object collision pairs.

Compute Approximate and Exact Object-to-Object Collision Detection: Using bounding volumes, spatial partitioning, or object geometry collision tests to reject all noncolliding object pairs.

Perform Collision Response: Generate collision events for the game logic, or perform proper response based on object information or engine design.

To be able to get this engine up and running, we need classes for building collision hierarchies and spatial partitioning structures, collidable objects, techniques for representing different types of bounding volumes, and the algorithms for determining their collisions, as well as equivalent classes for processing exact collisions with scene object geometry or its proxies.

Object to Object versus Object to World

In addition to using bound hierarchies to speed up things, we can also divide our collision tests into two major categories, object-to-object collisions and object-to-world collisions. This is an artificial division because in reality there is no difference between these two types of collisions. However, in games, often the objects and resulting collision information needed for gameplay is very different. Typical object-to-object collisions require only a true-or-false-type detection for triggering game events, such as a weapon hit or picking up a powerup. Object-to-world collisions often require additional information about the collision, usually in the form of intersection, particularly for computing the desired collision response for player motions, such as navigation. There is no reason why collision detection techniques for either type can’t be used in either situation, but as we will see, it is advantageous to view these techniques from this perspective.

Static Objects versus Dynamic Objects

Another reason we denote collision tests as object-to-object or object-to-world is because quite often the game “world” is a static set of geometry, in which case these world objects’ bounds are unchanging. This means the world objects’ bounds will not need to be dynamically updated during the game, which can lead to many optimizations.

Any moving object can then be said to be dynamic, which means that the object’s bounds must also be moved along with the object. Because the bounds of moving objects will be changing by definition, dynamic objects in collision hierarchies require additional runtime hierarchical processing. Parent nodes in the hierarchy are meant to contain all of their children’s bounds, so any object below them in the hierarchy that is dynamically changing its bounds must bubble up the changes, that is, it must somehow notify its parent(s) that its bounds have changed and, therefore, they too must modify their bounds accordingly. This process can get complex and expensive at runtime, depending on many factors, such as the depth of the hierarchy, amount and frequency of the movement, and the cost of modifying or recalculating bounding volumes. Therefore, dynamic objects are often managed in their own structure, separate from the main scene bounding volume hierarchy.

Static versus Dynamic Collisions

In addition, moving objects may require a slightly different set of collision-detection algorithms than nonmoving world geometry. Updating a moving object and then testing its updated bounds for collisions against the rest of the scene is the typical process, as described earlier. However, static collision detection tests, which examine only the current object’s bounds with other objects’ current bounds, may fail, depending on the object’s velocity as relates to its size and other possible collision objects.

The reason is that because of the discrete nature of a 3D game (or any computer-based simulation), when the collision system executes it processes only a snapshot of the game’s collidable objects’ current states. It is possible that between the last game state and the current game state, fast-moving objects will pass right through each other and basic static collision tests will not detect the collision that would have happened between the last frame and the current. This situation is illustrated in Figure 16.6. In the first frame, the static collision test luckily detects the bounding sphere collision as it collides with the box. In the second frame, the displacement between frames is great enough that the static frame-to-frame collision detection fails to catch the bounding sphere passing through the box. To properly prevent this collision failure, either the object must not be allowed to move more than its width in one frame, multiple static collision detection tests must be run, or a more sophisticated dynamic collision test accounting for the volume the object traveled between the frames must be used.

Figure 16.6: Static collision success and failure.