• # Practical Collision Detection

General and Gameplay Programming

To appear in the Proceedings of the Computer Game Developer's Conference, 1997 [size="5"] Target Audience Programmers of realtime 3D applications who intend to implement sophisticated collision detection schemes. [size="5"] Abstract Most modern 3D games require some form of collision detection. This paper presents some basic brute force methods of collision detection between polyhedra, successively refining the techniques until we are left with a system that runs quickly. An implementation is examined in which a game engine handles 32 players and hundreds of objects in realtime. [size="5"] Modus Operandi Over the past year, we have been experimenting with methods of collision detection for use in games. The goal of this paper is to communicate the experience we have gained. Being an exposition of "practice and experience", this paper does not present any new work in that it does not plant a new condominium tract amid the burgeoning fields of computer science. We hope merely to provide observations and ideas that will be useful to others exploring this subject. All the ideas presented here (and many more) would be evident to anyone who sat down and experimented with collision detection for a time. Our main goal is to save you some of that time. This paper is constructed in a form that matches the evolution of our collision detection system over time. In the first section we begin slowly, taking small steps until a foundation is firmly established. We detail the history of our progress, highlighting key discoveries. Finally, we speed through some advanced concepts, and leave off with some jaded summaries of the current state of collision detection research. [size="5"] What Do You Want? We wanted to make a game with "good collision detection", but we didn't take much time to clarify to ourselves what precisely that meant. We knew that we wanted objects to have the shapes of arbitrary polyhedra, and we knew that we didn't want grossly inaccurate collision results: that is, we never wanted to see objects bounce off empty space, and neither did we want to see them interpenetrate. [size="5"] A First Try If two objects are sticking through each other, and they are both closed polyhedra, then at least one face of one object will be penetrating at least one face of the other object. If we can detect this case as soon as it occurs, then "fix" the situation by moving the objects slightly so that they no longer penetrate, then we should be done. Therefore we decided that the logic governing object motion would proceed in a loop like this:
while the game is running foreach entity in the world update(entity) update(entity): entity.old_position := entity.current_position modify entity.current_position based on entity.velocity and other factors if Colliding(entity) then entity.current_position := entity.old_position Colliding(current_entity) -> bool: foreach entity in the world if entity != current_entity then if Entities_Collide(current_entity, entity) then return true return false Entities_Collide(e1, e2) -> bool: foreach polygon p1 in e1 foreach polygon p2 in e2 if polygons_intersect(p1, p2) then return true return false
We have not defined _polygons_intersect_ here. Descriptions of how to determine the intersections of two polygons can be found in [O94]. It is easier and faster to determine intersections of convex polygons than nonconvex ones, so one may wish to compose one's models of convex polygons (there are many good reasons to do this, most of which have to do with graphics.) When objects collided, we chose to move them back to their starting positions, because if those were "safe" spots for the objects a moment ago, they will probably still be safe. One alternative is to search through space to find new positions for the objects, which is icky. But there are complications in the method that we chose: for example, when an object is moved back to its starting point, we must make sure that it is really still safe; if not (because an object has moved into that space in the meantime), we must move the offending object back to its own starting position. The worse that can happen is that we have to revert every object in the world to its starting point. For the most part, though, the pseudocode above illustrates an extremely basic, extremely simple, and extremely slow way of doing collision detection. Why is it so slow? If we have two objects, each of which is composed of 100 polygons, then when they collide, that loop body in Entities_Collide will be executed a lot -- 1002 times in most cases. Finding whether two polygons intersect is not the fastest operation known to man. On current-day computers, doing it 10,000 times is far from instantaneous. And doing it 10,000 times for each pair of objects that may collide, updating the world many times per second, becomes impossible. It's dreadfully slow, but it works (with a few exceptions, which we'll talk about later). And something that works is not a bad starting point. [size="5"] The First Filters One way to speed up a slow algorithm is to install "filters" which keep the slow part from getting run when it doesn't need to, or which can come up with an easy answer using inexpensive techniques. Immediately we put into place two simple filters that most experienced programmers would take as givens:
1. Segregation is Good We divide the world into a regular grid that partitions objects into smaller groups, with the goal of reducing the number of entity-entity comparisons the system needs to make. Every time we move an object, we compute which squares of the grid it overlaps. For our engine we chose a two-dimensional grid, although it is a true 3D world, because the game is played over a landscape and we do not expect many objects to be piled on top of each other.
2. Bounding Spheres Before doing the polyhedron-polyhedron check, we look at the distance between the centers of the two objects. If they are further than the sum of the two objects' radii, the objects cannot possibly interpenetrate. To speed this up slightly, we can check the distance squared versus the sum of the radii squared (this avoids a costly square root operation).
3. I Prefer Jersey Actually, we originally had a third filter that ran before the bounding sphere test, which looked at the Manhattan distance between the objects' centers. This was not really worth the bother (It almost never saved any execution time worth worrying about) so we deleted it.
[size="5"] Filling In the Gaps The code discussed so far tests for interpenetration, but that might not be adequate. I've never seen a realtime object simulator in which movement wasn't discrete; that is to say, motion occurs by teleporting objects from place to place. The illusion of smooth motion arises because the distances by which the objects "jump" are very small. But the faster an object is moving, the further it must jump during a fixed timestep. If an object jumps far enough during one update, it could "miss" another object, appearing to fly right through it (or part of one object could miss part of another, causing strange things to happen). Our quick fix for this was to create a "speedbox" around the object; the speedbox was a bounding box that enclosed the full volume of space through which the object might pass during one update. When testing for collisions we would use the speedbox's shape instead of the object's actual shape. This violated our original concern that collisions should be very accurate, but we waved our hands and said that since the object was moving so quickly, nobody would see what was going on anyway. See, games are cool because you can wimp out like that, any time you want. The most drastic (and only theoretically sound) alternative we know of is to represent shapes mathematically as functions of their initial space occupancies, their velocities, and time, and then solve huge sets of simultaneous equations to determine collision. We do not expect this approach to be computationally feasible any time this millennium. Divisiveness is Good. It's an ancient fact that, if two convex polyhedra do not intersect, one can always find a dividing plane between them [Rab95]. Exploiting this fact seemed like a good idea. We didn't want to limit our objects to convex polyhedra, or have to express them as being composed of such. But it is still true that, if objects are mostly convex, then you can usually find a dividing plane between them (illustrated in figures 5-7). So we wrote another filter called "plane divides entities", which would heuristically try to find a dividing plane between two objects. And we saw that it was good. By this point we had built up a stack of "easy"-to-compute filters that would happen before the final collision detection, which became known as the "hard case". But the hard case was, so to speak, still too hard. And though the filters were very helpful, there were cases when they just failed to apply. When two objects got very close to each other in ways that left no easily-found dividing plane between them, the game slowed down unacceptably. We knew about BSP trees, so we cracked open some references and began writing some new hard-case code. We will not attempt to explain BSP trees fully in this paper. Instead, we refer the reader to [Chin95], [FV90], and [Wade95], and provide a brief explanation for the sake of context. BSP trees consist of a hierarchy of planes, where each plane divides a region of space into two halfspaces. We can use them to describe a solid object by adopting the convention that each separating plane of a leaf node describes a portion of the object's surface, where one of the plane's halfspaces represents the inside of the object, and the other represents space that is outside. Binary tree organizations of n nodes can often allow search operations to complete in O(log(n)) time, and the collision detection we are trying to perform is fundamentally a search. Intuitively, if we use BSP trees well when testing two objects for intersection, we should be able to handle a "hard case" collision test in something like O(log(n)2) time, where n is a typical number of polygons contained by an entity. We can employ BSP trees to speed up collision detection by using their spatial-partitioning properties to reject polygons early. If we are detecting a collision between two entities A and B, and if we know that A lies entirely on one side of some plane P that cuts through B, then we need only test A against the parts of B that are on the same side of the plane as A. (In a sense, this is a more sophisticated version of the Plane Divides Entities test, where the dividing plane eliminates only part of an object, rather than the whole thing.) BSP trees provide us with a myriad of such planes. So if we recurse down the BSP tree of B, finding whether A's bounding sphere intersects each separating plane (a very cheap operation in itself), we can ignore many polygons of B that have no chance of colliding with A. For each polygon of B that passes this filter, we will call a procedure that compares it with every polygon in A. Some sample C++ source code to do this is presented below:
struct Polyhedron { List *faces; // All polygons contained in this object Point center; // Center of the object float radius; // Radius of its bounding sphere BSP_Node *bsp_tree; // BSP tree representing this object }; enum flag_value { TOUCHES_POS_HALFSPACE = 0x1, TOUCHES_NEG_HALFSPACE = 0x2, SLICED = 0x3 // Touches both halfspaces }; struct BSP_Node { float a, b, c, d; // Coefficients of plane equation (ax + by + cz + d = 0) List *polygons; // Polygons that are coplanar with said plane BSP_Node *positive, *negative; // Contents of each halfspace }; bool object_hits_world(BSP_Node *node, Polyhedron *solid) { if (node == NULL) return false; int status = classify(node, solid->center, solid->radius); if (status == SLICED) { if (test_solid_against_polygons(node->polygons, solid)) return true; } if (status & TOUCHES_NEG_HALFSPACE) { if (object_hits_world(node->negative, solid)) return true; } if (status & TOUCHES_POS_HALFSPACE) { if (object_hits_world(node->positive, solid)) return true; } return false; } int classify(BSP_Node *node, Point center, float radius) { float distance = (center.x * node->a) + (center.y * node->b) + (center.z * node->c) + node->d; int status = 0; if (distance - radius <= 0.0) status |= TOUCHES_NEG_HALFSPACE; if (distance + radius >= 0.0) status |= TOUCHES_POS_HALFSPACE; return status; } bool test_solid_against_polygons(List *polygons, Polyhedron *solid) { Polygon *face1, *face2; Foreach(polygons, face1, { Foreach(solid->faces, face2, { if (polygons_intersect(face1, face2)) return true; }); }); return false; }
longest_radius := 0.0 foreach vertex in the object vertex_distance := distance from vertex to object's origin if vertex_distance > longest_radius then longest_radius := vertex_distance
Here is a listing of collision tests, the number of times during the sample run that they were effective (came up with a definitive answer about the status of a collision), the percent of all cases for which they were effective, and the average amount of time taken for one test (timings taken from a Pentium 166 running Linux, program compiled with gcc -ggdb -O3 -m486).  Collison Test # of definitive answers Average Running Time bounding spheres 3800 tiny bounding box safety 1911 26.13us plane divides entities 93 231.94us BSP hard case 842 450.98us

Report Article

## User Feedback

You need to be a member in order to leave a review