\chapter{Introduction to the collision detection problem} \hspace*{1em} For the purpose of this discussion, the collision detection problem will be limited to its applicability in 3D interactive graphics applications. However, the concepts, ideas and algorithms presented have been drawn from many areas of research concerned with collision detection including robotics, computational geometry, and physical simulation [citations] This chapter is organized as follows: the collision detection problem is presented in context by describing how it applies to 3-dimensional interactive graphics applications; a discussion of common types of collision detection algorithms is presented along with an explanation of a collision detection pipeline; and examples of popular collision detection algorithms and data structures are presented. \section{Collision Detection and Interactive Graphics} \hspace*{1em} The purpose of collision detection is to determine if, and in what manner, objects are colliding at a moment in time. To illustrate this purpose, one might simulate dropping a ball onto a flat level floor. In this simulation, collision detection is used to determine when the ball hits the floor. The obvious solution is to calculate the time of impact directly using the initial height of the ball and a gravitational constant. Unfortunately, this solution doesn't constitute collision detection, but rather collision prediction. By calculating the time of impact directly, the assumption is made that the path of the ball remains unimpeded for the duration of the simulation. However, if unpredictable changes in the simulation occur, the prediction may be incorrect. This is the case imposed by interactive 3D graphics on collision detection algorithms. In an interactive 3D graphics application, the flow of control runs in a continuous loop sampling time at discrete intervals \ref{fig:flow_control}. At the end of each interval of time, the state of the simulated objects is updated to reflect changes that occur during the interval. For example, an object moving along a path is translated to a new position according to its velocity vector. Interactive 3D graphics applications create the illusion of smooth, animated motion by redrawing the screen at the end of each interval of time \ref{fig:animation}. \begin{figure} \epsfxsize=4in \vspace{2in} \centerline{\epsffile{chap02/interactive_graphics_flow.eps}} \caption{Control flow of an interactive 3D graphics application} \label{fig:flow_control} \end{figure} \begin{figure} \epsfxsize=4in \vspace{2in} \centerline{\epsffile{chap02/animation.eps}} \caption{Position of object is updated as a function of time to create smooth animation} \label{fig:animation} \end{figure} Along with updating the state of simulated objects, collision detection is also performed to determine whether the new positions of an object causes it to interfere with the positions of other objects. It is important to note that collision response is an application dependent issue and is not addressed by collision detection algorithms. The mechanics of the simulation impose restrictions on collision detection algorithms. By sampling time at discrete intervals, only a fraction of the total time elapsed is accounted for in the simulation. As a result, it is possible for important events to be overlooked. Returning to the example simulation, one must consider what might happen under the conditions shown in figure (ref figure). \begin{figure} \epsfxsize=4in \vspace{2in} \centerline{\epsffile{chap02/sphere_miss_floor.eps}} \caption{Ball "jumping through" floor as a result of too long of a time interval} \label{fig:fig2} \end{figure} As shown in figure (ref figure), at the end of time interval $t( n )$, the ball is positioned just above the floor. Then, at $t( n + 1 )$, the ball's position is calculated to be just below the floor. If the floor is represented as a plane and collision detection is done using an intersection test, then the simulation would have incorrectly determined that no collision occurred. A common solution to correct the problem of objects "jumping through" other objects is to increase the sample rate of the simulation time line which will increase the probability of all collision being detected. Using this solution, one must determine the sample rate to be employed. If the rate is too high, application performance suffers. If the rate is too low, collisions might be missed. Returning to the example simulation, one might consider expanding its capabilities to allow multiple balls to collide with the floor and with each other. Under the previous conditions, intersection between the ball and the floor could be tested rapidly at the end of each interval of time. However, with the new conditions, collision must be detected between all pairs of balls, $(N choose 2)$, and each ball with the floor. The naive approach to solving this problem tests all pairs of balls and each ball with the floor for collision. This approach runs in $O( n^2 )$ time. The situation is further complicated when objects that are more complex than spheres are introduced into the simulation. Testing for collision between two spheres or a sphere and plane can be performed in a few operations. Due to the symmetry of a sphere, both tests reduce to a distance calculation with the center of the sphere. Detecting a collision between spheres runs in constant time. (insert sphere fig) This is not the case for general polyhedra. As show in [Incremental Distance Calc], testing the intersection between two convex polyhedra can be done in O(n) time in the worst case. Convex polyhedra are a special case of general polyhedra and are easier to test intersection. For this reason, general polyhedra are decomposed into convex entities. As a result of the running time to test the intersection of polyhedra, the number of polyhedra that can be tested for collision in a given period of time is much smaller than when spheres are used. Testing for collision between multiple moving objects and testing for collision between complex objects are some of the cases effective collision detection algorithms must address. The manner in which an algorithm handles these situations determines the problem domain for which an algorithm is suitable. Issues of object representation, resource utilization, and acceptable performance characteristics also constrain applicability of an algorithms from one problem domain to another. Consequently, the breadth of highly specialized collision detection algorithms is great. Although collision detection algorithm are specialized, many processes, concepts, and structures they employ are common throughout collision detection research. This is particularly true among algorithms that use similar data-structures and geometric principals as a basis for their design and hybrid algorithms that use multiple existing algorithms in conjunction with one another. Many surveys and comparative overviews of collision detection algorithms are available [3D collision detection: a survey, optimizing collision detection pipeline, collision detection for virtual reality fly-through, Collision Detection: Algorithms and Applications] that discuss application domains, useful geometric principals, and solving strategies for collision detection problems. Rather than exploring all aspects of collision detection algorithms, the remainder of this chapter will discuss the components of general collision detection solutions followed by examples of collision detection algorithms. \section{Collision Detection Pipeline} \hspace*{1em} General solutions to the problem of detecting collision between objects in interactive 3D graphics applications are multifaceted. Detecting collision between many objects and detecting collision between two complex objects are two facets of the general collision detection problem. Detecting collision between many objects is commonly called the all-pairs problem and can be generalized as follows: given n objects, determine all pairs of objects that are colliding. Detecting collision between two complex objects is commonly called the exact-body problem and can be generalized as follows: given two objects, determine which pairs of geometric features between the two objects are colliding. Geometric features, or simply features, refers to a region or part of an object comprised of one or more polygons. Another facet of the collision detection problem is determining exactly how two features of two objects are colliding. This problem is commonly called the exact-feature problem. Software that implements a general solution to the collision detection problem typically uses a collection of algorithms to address facets of the collision detection problem. Despite the disparate nature of each of the previously mentioned collision detection problems, the algorithms that solve these problems have well defined relationships. These relationships have been studied in the article [Optimizing the Collision Detection Pipeline]. In this article, the relationships between collision detection algorithms are described as pipelines of successive filters. Filters correspond to algorithms that address aspects of the collision detection problem while the pipeline describes the order in which filters are applied to data. Input to the pipeline is a set of objects and output is a pairwise description of collisions between objects. Internally, data flows from one filter to the next being successively refined at each stage. The relationship between various aspects of the collision detection problems has also been described as a multi-phase [Approximating Polyhedra with Spheres for Time-Critical Collision Detection, Separating Vector, Bucket Tree, Particle Flow] and multi-stage [V-Collide] process. In this description, the broad phase and the narrow phase are respectively analogous to the first stages and the last stages of pipeline filters. Although these descriptions of the relationships between facets of the collision detection problem express the same idea, the pipeline paradigm is preferable because it emphasizes the composition of solutions to the general collision detection problem. Because each pipeline filter has a well defined role, filters can be implemented as reusable components. Using the pipeline as a framework, specialized application-specific collision detection systems can then be assembled from filter components. Another quality of the pipeline paradigm is that it remains conceptually flexible, allowing for modification without breaking existing conventions. As new collision detection algorithms are developed, pipeline filters can be inserted or replaced as a natural and expected process. \section{Algorithms for Solving the All-Pairs Problem} As previously stated, the all-pairs problem is, given n objects, determine all pairs of objects that are colliding. Algorithms that solve the all-pairs problem are positioned at the beginning of the collision detection pipeline and are designed to reduce the number of exact-object tests performed in the latter stages of the pipeline. The naive solution to the all-pairs problem is to test "all pairs" of objects for collision. This solution is considered naive because it is a brute force approach and runs in $O( n^2 )$ time. To solve the all-pairs problem efficiently, a strategy must be devised that can quickly differentiate between those objects that can collide from those that definitely can not. Many algorithms have been developed to address the all-pairs problem. A common feature among them is their use of bounding volumes of objects. The bounding volume of an object is object that completely encloses the original object. Bounding volumes are designed to have a simple representation compared to the object they bound. Common choices for bounding volumes include cubes, boxes, and spheres. Algorithms that solve the all-pairs problem use bounding volumes in stead of the original objects for collision detection because testing for intersection between bounding volumes is, by design, much faster than testing for intersection using the actual objects. \subsection{Sweep-and-prune Algorithm} \hspace*{1em} One of the earliest algorithms developed to address the all-pairs problem is the sweep-and-prune algorithm [samet]. The basic idea behind sweep-and-prune is to sweep a plane across a volume of space, testing objects for collisions that intersect the plane simultaneously. Objects that are not simultaneously intersecting the plane cannot collide and are eliminated from further collision tests. In practice, implementations of sweep-and-prune operate by projecting all objects onto a coordinate axis which results in intervals along the axis line. Overlapping intervals indicate possible collisions between objects. Determining overlapping intervals is performed in a two-step process: Step 1: Sort the list of intervals in ascending order using the minima of the intervals. Step 2: Traverse the list in ascending order, testing intervals with the successive intervals to determine overlap. If the end-point of one interval is greater than or equal to the beginning-point of a subsequent interval, then the intervals overlap. This method is also called dimension reduction [I-Collide] because it reduces the number of dimensions in which objects are compared. A variation on sweep-and-prune is implemented in the I-Collide collision detection library [I-Collide: an interactive and exact collision detection system for large scale environments]. In I-Collide, the sweep-and- prune algorithm projects objects onto all three coordinate axes. Pairs of objects are only considered for further collision tests when their intervals overlap in all three sub-spaces. Costs associated with this algorithm include sorting three lists of intervals and testing for interval overlap on all three intervals. In the general case, sorting the lists runs in $O( n log n )$ and testing for overlap runs in $O( n^2 )$ in the worse case. However, as cited in [I-Collide], when objects maintain temporal and geometric coherence, performance of this algorithm is improved. "Temporal coherence is the property that application state does not change significantly between time steps or frames. The objects move only slightly from frame to frame. The slight movements of the objects translates into geometric coherence because their geometry, defined by the vertex coordinates, changes minimally between frames."[I-Collide]. Moreover, if the interval of time between object updates is small, objects can be expected to move relatively little between time steps. This makes the following position of an object predictably close to its previous position. The sweep and prune algorithm described in I-Collide takes advantage of coherence by keeping the three lists of intervals between time steps. As a result of coherence, if the sample rate is high, the lists of intervals will remain in an approximate sorted order. This reduces the problem of sorting the lists of intervals to resorting partially sorted lists from the previous time step. In the I-Collide collision detection library, the lists are resorted by updating the endpoints of the intervals and then resorting the lists using an insertion sort. When coherence is maintained, resorting the list can be performed with an insertion sort in $O( n )$ time on average. Additional costs associated with this algorithm include maintaining a data structure used for storing the overlap status of objects. Again, if coherence is maintained, this operation runs at $O( n )$ time. Total running time of this algorithm is $O( n + s )$ [I-Collide]. \subsection{Octree data structure and algorithms} \hspace*{1em} Octree data structures belong to a class of structures that represent a volume space as a hierarchy of discrete units. Octrees algorithms use a divide-and-conquer approach to navigating and searching a volume of space and have many uses in the fields of collision detection and interactive 3D graphics. As the name implies, an octree data structure is a tree structure in which each node has eight child nodes (ref fig). To represent a volume of space, the root node of an octree is associated with a cubic region within which the octree structure is contained. Below the root, each of the eight node children are associated with an even subdivision of the space enclosed by the root \ref{fig:octree_diagram}. The relationship between the root and its eight children can be recursively expanded to any number of levels, creating further subdivisions of the original cube associated with the root. When discussing octrees, several terms are used for describing their components. The term octant is used to describe a cube that is one of eight even subdivisions of a larger cube. In the octree data structure, as with other tree data structures, nodes that terminate a branch are called leaves. Octants that correspond to leaves in an octree are called voxels. A voxel describes the smallest unit of space that can be addressed in a discretized three dimensional volume. \begin{figure} \epsfxsize=4in \vspace{2in} \centerline{\epsffile{chap02/octree_diagram.eps}} \caption{ A three level octree and the corresponding tree data structure that represents it } \label{fig:octree_diagram} \end{figure} Octree data structures are commonly implemented as pointer-based tree data structures because pointer-based trees allow for a high degree of flexibility and simplicity in tree construction and traversal. As a feature of pointer-based trees, octants can be added and removed from the octree as needed. Internal to the octant data-structure, parent octants store pointers to child octants which are used for navigating the octree data structure. In addition to pointers for navigation, octants store a record of data or a pointer to data that is associated with the octant. Because of the manner in which octrees subdivide and index volumes of space, they are well suited to representing three dimensional data volumetrically. To represent data as a volume of space in an octree, the data is associated with an octant. The position and size of the octant implies the volume and location of the data. When data is stored in an octant that is not a leaf, it is implied that the data occupies all octants below the octant within which it is contained. A typical strategy for inserting data into an octree is to perform a recursive traversal beginning with the root of the octree and search for octants within which to store data. Beginning at the root, data is checked for intersection with each of the root's eight children. The traversal is continued within each child the data intersected. Depending on the needs of the algorithm, traversal of the octree can be terminated at a suitable time. Generally, most octree traversal algorithms run in $O( log n )$ [samet] time with n being the depth of the tree as a result of a divide and conquer approach to navigating the octree. Octree data structures have been used in several collision detection algorithms [cite samet, vemuri, sphere collisions], the most successful of which operate in a similar manner. After a pointer-based octree is constructed and populated with objects, objects are moved in and out of octants as they move through space. To test for collision, the octree structure is searched to determine which objects share octants. Only objects that share octants are considered for further collision tests. The differences between algorithms that use octrees are the way in which objects are moved between octants and how the octree data structure is searched. Two examples of collision detection algorithmis that use octree are [Fast Collision Detection among Multiple Moving Spheres] and [Fast Collision Detection Algorithms with Applications to Particle Flow]. In both examples, an octree is constructed so that it only contains paths to non-empty octants. This guarantees that every search path in the octree yields objects that need to be tested for collision. Also, both of these algorithms use an indexing scheme which allows the octants an object intersects to be calculated as a function of the center of the object. The difference is that [Fast Collision Detection Algorithms with Applications to Particle Flow] uses coherence to reduce the time needed to move an object from one octant to another to $O( n )$ time, while [Fast collision detection] does this by limiting the search for octants an object will move into to the neighbors of the octant the object is leaving. In [Fast Collision Detection among Multiple moving spheres], destination octants are found by traversing the octree from the root which takes $O( log n )$ time. In [BucketTree: deformable collision detection], a collision detection algorithm based on an octree uses coherence to achieve $O( n )$ when moving objects between octants. However, unlike [Fast Collision], [BucketTree] uses an auxiliary data structure to determine when an object is moving between octants. In [BucketTree], three lists are used to store the x, y, and z end-points of intervals defined by the axis aligned bounding boxes of the objects. After sorting the lists, the indices of the intervals that straddle the leaf octant boundaries are recorded. The recorded indices define the boundaries of buckets within the lists. By using an insertion sort, the order of the intervals in the buckets can be maintained in linear time as long as the positions or lengths of the intervals do not change significantly between sorts. This algorithm reduces the number of times that objects are checked for movement between octants by limiting its search to the objects that move between buckets. Besides being suitable for solving the all-pairs problem in collision detection algorithms, octrees have been successfully applied in other fields relating to computer graphics such as Constructive Solid Geometry (CSG). Constructive Solid Geometry is concerned with performing high-level, logical operations between objects to construct new objects. The motivation for this type of representation is to facilitate an interactive mode for solid modeling [3D Games, addison wesley]. An example of a logical operation between two objects is to Boolean OR their volumes together to produce a new object. (insert picture of CSG object operation) Octrees data structures are well suited for CSG applications because of the way in which volumetric regions are represented in octrees. In CSG applications, an octree is used to encode the volume of an object to a high degree of detail. This is done by finding the intersections between the surface of an object and the octants in high resolution octree. A high resolution octree has exceedingly small leaf octants. The resulting octree is a hierarchical voxelization of the object's volume captures the details of the shape of an object. Logical operations between objects are performed using their octree representations. For example, subtracting one object from another is done by combining the octree data structures of two objects and deleting the common leaf octants. In addition to octrees, other hierarchical and space indexing data structures exist [cite BSP/k-d trees, sphere octree, k-dop tree, grids] and have been used extensively in collision detection algorithms. \section{Exact-Object Algorithms} \hspace*{1em} In interactive 3D graphic applications it is important to present users with a visual display of believable objects. One way to accomplish this is by representing objects with detailed models. Typically, these models are constructed using polygons positioned in 3D space. Polygons positioned in 3D space are preferable because they are convenient for constructing continuous surfaces that simulate the features and contours of real-world objects. Unfortunately, detecting collisions between these types of models is substantially more difficult than between simple objects. In interactive 3D graphic applications, algorithms that perform exact-object collision detection are designed to address the complexities of testing for collision between objects constructed from polygonal surfaces. In much the same way that algorithms for solving the all-pairs problem prune the number of objects passed to exact-object collision detection algorithms, exact-object algorithms prune the number of features between two objects passed to exact-feature collision detection algorithms. Many methods have been developed for analyzing the geometry of two objects that decide which features to test for collision. Of those methods, the most widely used are Bounding Volume Hierarchy algorithms. \paragraph{Bounding Volume Hierarchy} \hspace*{1em} A bounding volume hierarchy (BVH) is a set of bounding volumes that recursively enclose the geometric features of an object. The resulting volumes form a hierarchy of enclosed spaces where levels of the hierarchy represent the resolution of enclosure around a geometric feature. Moreover, bounding volumes at lower levels of the hierarchy have tighter fits around their corresponding geometric features \ref{fig:bounding_vol}. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} \caption{ caption goes here } \label{fig:bounding_vol} \end{figure} BVHs are designed to quickly isolate geometric features that are participating in collisions. This is done by using an object's BVH as a guide to search for geometric features using a divide and conquer strategy. BVHs are typically implemented as tree data-structures. Tree nodes are used to store the volume bounding a geometric feature and the relationship between parent and child nodes is such that the bounding volume of the parent encloses the bounding volume of the child (ref figure). An octree data structure can be used as a BVH. Algorithms that use BVHs to the find colliding features between two objects follow the same fundamental steps. Beginning at the root of each BVH tree, bounding volumes are tested for intersection with each other. When intersections are detected, the corresponding branches in each tree are descended. \begin{figure} \epsfxsize=4in \vspace{2in} \centerline{\epsffile{chap02/oriented_bounding_box.ps}} \caption{Example of a Bounding Volume Hierarchy: bounding boxes recursively bound polygons [cite OBBTree] } \label{fig:} \end{figure} The differences between BVH implementations are in the type of bounding volume used, how intersections between bounding volumes are tested, and the algorithms used to build BVHs for objects. Examples of BVH implementations include Oriented Bounding Box trees (OBB)[OBB-tree: a hierarchical data structure for rapid interference detection], Axis Aligned Bounding Box trees (AABB), Constructive Solid Geometry trees (CSG) [...], Brep-Index trees [BREP-INDEX: A Multidimensional Space Partitioning Tree], Binary Space Partitioning trees [Multidimensional Binary Search Trees used for associative searching, Representing Small rectangles for interference testing, samet] , Sphere Trees [time critical collision detection], and Octrees [garinatti, samet]. \section{Exact-Feature Testing} \hspace*{1em} The final stage of the collision detection pipeline concludes with an exact-feature test. Exact-feature tests are used to determine if the geometric features from two objects are in fact intersecting. Algorithms for these tests are based on mathematical solutions to geometry problems. When objects are constructed from polyhedral surfaces, this problem reduces to detecting if the edge of one surface pierces the face of another. For a discussion of efficient techniques used to solve this problem, refer to [Collision Detection Survey] and [3D Games].