\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 \cite{gilbert_distance,lin91fast,collision_free},
        computational geometry, and physical simulation
        \cite{eppstein-raising,ma99parallel,overset_grids}.

        This chapter is organized as follows: the collision
        detection problem is presented in context by describing how
        it applies to three-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
        explained.

\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
        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, 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.
	This flow control is illustrated in Figure~\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, as shown in Figure~\ref{fig:animation}.

	\begin{figure}[h]
	\epsfxsize=5in
	\centerline{\epsffile{chap02/interactive_graphics_flow.eps}}
	\caption{
		{\em Control flow of an interactive 3D graphics application.}
	}
	\label{fig:flow_control}
	\end{figure}

	\begin{figure}
	\epsfxsize=5in
	\centerline{\epsffile{chap02/animated_sphere.eps}}
	\caption{
		{\em
		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 position
	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 elapsed time is accounted
	for in the simulation. As a result, it is possible for important
	events to be overlooked.

	For example, consider the simulation under the conditions shown in
	Figure~\ref{fig:sphere_miss_floor}.  At 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.

	\begin{figure}
	\epsfxsize=4in
	\centerline{\epsffile{chap02/sphere_miss_floor.eps}}
	\caption{{\em
		Ball ``jumping through" floor as a result of too long of
		a time interval.}
	}
	\label{fig:sphere_miss_floor} \end{figure}

        A common solution to correct the problem of objects ``jumping
        through" other objects is to increase the sample rate of the
        simulation timeline 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.

	One might consider expanding the simulation's 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 between each ball and 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 ${\cal 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 between 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
        using the center of the sphere. Detecting a collision between
        spheres runs in constant time.

	This is not the case for general polyhedra. As show in
	\cite{lin91fast}, testing the intersection between two convex
	polyhedra can be done in ${\cal O}(n)$ time in the worst
	case where $n$ is the combined number of vertices of two
	polyhedra. Convex polyhedra are a special case of general
	polyhedra and are easier to test for intersection. For this
	reason, general polyhedra are often decomposed into convex
	entities. As a result of the running time of testing polyhedra
	for intersection, the number of polyhedra that can be tested
	for collision in a given period of time is much smaller than the
	number of spheres that could be tested in that period of time. As
	shown in Figure~\ref{fig:complex}, complex objects may collide in
	many different ways making testing for collision a more complex
	and time consuming process than testing spheres for collision.

	\begin{figure}
	\epsfxsize=4in
	\centerline{\epsffile{chap02/complex_objects.ps}}
	\caption{{\em
		Examples of complex objects colliding \cite{lin96collision}.}
		}
	\label{fig:complex} 
	\end{figure}

        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
        algorithm from one problem domain to another. Consequently,
        the breadth of highly specialized collision detection algorithms
        is great.

        Although collision detection algorithms are specialized, many
        processes, concepts, and structures they employ are common
        throughout collision detection research. This is particularly
        true for algorithms that use similar data structures and geometric
        principles as a basis for their design and for hybrid algorithms
        that use multiple existing algorithms in conjunction with one
        another.

	Many surveys and comparative overviews of
	collision detection algorithms are available in
	\cite{held95evaluation,nez-collision,zachmann01optimizing}.
	These sources discuss application domains, useful geometric
	principals, and solving strategies for collision detection
	problems are available. 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{The Collision Detection Pipeline}

	\hspace*{1em}
	General solutions to collision detection problems in interactive
	3D graphics applications are multifaceted. For example,
	detecting collisions between many objects and detecting collision
	between two complex objects are separate problems with separate
	solutions. These two problems are commonly referred to as the
	all-pairs problem and the exact-object problem. Another facet
	of the collision detection problem is concerned with exactly
	how the geometric features of two objects intersect. Geometric
	features, or simply features, refer to a region or part of
	an object comprised of one or more polygons. This problem
	is commonly called the exact-feature problem. Software that
	implements a general solution to collision detection typically
	uses a collection of algorithms to address each facet.

	Despite the disparate nature of each sub-problem, the algorithms
	for solving facets of the collision detection problem have
	well-defined relationships. These relationships have been studied
	in \cite{zachmann01optimizing}. In this article, the relationship
	among aspects of collision detection algorithms is described as a
	pipeline of successive filters. Filters correspond to algorithms
	that address aspects of the collision detection problem, and
	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 and is successively
	refined at each stage.

	The relationship among various aspects of the collision
	detection problem has also been described as a multi-phase
	\cite{ganovelli-buckettree,hubbard96approximating,Vemuri:1998:FCD}
	and a multi-stage \cite{Hudson:1997:VCA} 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
	among 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}

	\hspace*{1em}
	Stated formally, the all-pairs problem is to determine all pairs
	of $n$ 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 ${\cal O}( n^2
	)$ time. To solve the all-pairs problem efficiently, a strategy
	must be devised that can quickly differentiate between those
	objects that might collide from those that definitely will not.

	Many algorithms have been developed to address the all-pairs
	problem. A common feature among them is their use of bounding
	volumes. The bounding volume of an object is another  
	object that completely encloses the original object. Bounding
	volumes are designed to have a simple representation compared to the
	object they bind. Common choices for bounding volumes include
	cubes, boxes, and spheres. Algorithms that solve the all-pairs
	problem using bounding volumes instead of the original objects for
	collision detection are more efficient 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 \cite{Samet:1984:QRH}.
        The basic idea behind sweep and prune is to sweep a plane across
        a volume of space, testing pairs of objects for collisions that are
        simultaneously intersecting the plane. Pairs of 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. This is demonstrated in 
	Figure~\ref{fig:axis_interval}.  Determining overlapping
        intervals is a two-step process:

	\begin{enumerate}
        \item Sort the list of intervals in ascending order using the
        	minima of the intervals.
        \item Traverse the list in ascending order, testing 
		intervals against 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.
	\end{enumerate}

	\begin{figure}
	\epsfxsize=4in
	\centerline{\epsffile{chap02/interval.eps}}
	\caption{{\em
		Example of Dimension Reduction: Objects are projected onto the
		$x$-axis. Overlapping intervals along the axis indicate
		possible colliding objects. }}
	\label{fig:axis_interval} 
	\end{figure}


        Sweep and prune is also called dimension reduction 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 \cite{cohen95icollide}.  In I-Collide,
	the sweep and prune algorithm projects objects onto three
	coordinate axes.  Pairs of objects are considered for further
	collision tests only when their intervals overlap in all three
	dimensions. 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 ${\cal O}( n \ log \ n )$ and testing for overlap runs
	in ${\cal O}( n^2 )$ in the worse case. However, as cited in
	\cite{cohen95icollide}, when objects maintain temporal and
	geometric coherence, performance of this algorithm is improved.

	\begin{quote}
        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 \cite{cohen95icollide}.
	\end{quote}

        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 next 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 approximately
        sorted order. This reduces the problem of sorting the lists of
        intervals to that of resorting partially sorted lists from the
        previous time step. In the I-Collide collision detection library,
        the lists are resorted by first updating the endpoints of the
        intervals and then using an insertion sort.  When coherence is
        maintained, resorting the list using an insertion sort runs on
        average in ${\cal O}( n )$ time.

	An additional cost incurred by this algorithm is in maintaining a
	data structure that stores the overlap status of objects. Again,
	if coherence is maintained, updating the overlap status of
	an object runs in ${\cal O}( n )$ time. Total running time of
	this algorithm is ${\cal O}( n + s )$~\cite{cohen95icollide}
	where $n$ is the number of objects and $s$ is the number of
	overlapping intervals.

\subsection{Octree Data Structures and Algorithms}

	\hspace*{1em}
	Octree data structures belong to a class of structures that
	represent a volume space as a hierarchy of discrete units.
	Octree 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. 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, as shown in Figure~\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
	\centerline{\epsffile{chap02/octree_diagram.eps}}
	\caption{{\em
		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. A good description
        of pointer-based octree can be found in \cite{octree_isosurface}.


	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 indicate 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. These relationships between octants
        and data are shown in Figures~\ref{fig:octree_with_data}
        and \ref{fig:octree_with_spheres}.

	\begin{figure}[h]
	\epsfxsize=4in
	\centerline{\epsffile{chap02/octree_with_data.eps}}
	\caption{{\em
		Octree data structure storing the location of the sphere
		in the nodes of the tree.
		Note: not all octants that intersect the sphere are
		represented in the diagram.}
	 } 
	\label{fig:octree_with_data} 
	\end{figure}

	\begin{figure}
	\epsfxsize=4in
	\centerline{\epsffile{chap02/octree_with_spheres.ps}}
	\caption{{\em
		On the left is an octree drawn with all octants that
		intersect a sphere. On the right only the octants binding
		the sphere are drawn.}
	 } 
	\label{fig:octree_with_spheres} 
	\end{figure}

	A typical strategy for inserting data into an octree is to perform
	a recursive traversal beginning with the root of the octree and
	searching 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 ${\cal
	O}( log \ n )$ time with $n$ being the depth of the tree as a
	result of a divide and conquer approach to navigating the octree.

\newpage
        Octree data structures have been used in several collision
        detection algorithms 
	\cite{ganovelli-buckettree,EVL-1997-116,scg97*373,Vemuri:1998:FCD},
	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 among 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 algorithms that use octrees are \cite{scg97*373}
	and \cite{Vemuri:1998:FCD}. In both examples, an octree
	is constructed so that it contains paths to only 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 occupies to be calculated as a function of the
	center of the object. The algorithm in \cite{Vemuri:1998:FCD}
	uses coherence when moving an object from one octant to another
	and is able to maintain the octree in ${\cal O}( n )$ time. To
	move objects between octants, the algorithm in \cite{scg97*373}
	builds additional search trees to manage collision events. This
	operation takes ${\cal O}(n \ log \ n )$ time.

	In \cite{ganovelli-buckettree}, a collision detection algorithm
	based on an octree uses coherence to achieve ${\cal O}(
	n )$ when moving objects between octants. However, unlike
	\cite{Vemuri:1998:FCD}, \cite{ganovelli-buckettree} uses an
	auxiliary data structure to determine when an object is moving
	between octants. In \cite{ganovelli-buckettree}, three lists
	are used to store the $x$, $y$, and $z$ endpoints 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) \cite{bb15099}. Constructive
	Solid Geometry is concerned with performing high-level, logical
	operations between objects to construct new objects.  This is
	illustrated in Figure~\ref{fig:CSG}. The motivation for this type
	of representation is to facilitate an interactive mode for solid
	modeling~\cite{threeDgames}.  An example of a logical operation
	between two objects is to Boolean OR their volumes together to
	produce a new object.

	\begin{figure}
	\epsfxsize=2in
	\centerline{\epsffile{chap02/csg.ps}}
	\caption{{\em
		Boolean operations between solids in CSG modeling:
		(a) union, (b) subtraction, and (c) intersection
		\cite{threeDgames}.} } 
	\label{fig:CSG} 
	\end{figure}

        Octree 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 the object and
        the octants in a high resolution octree. A high resolution octree
        has exceedingly high number of leaf octants. The resulting
        octree is a hierarchical voxelization of the object's volume that
        captures the details of the shape of the 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. These include
        BSP/k-d tree \cite{held95evaluation} and k-dop trees
        \cite{klosowski98efficient}, which 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 in order to decide which features to test for collision. 
	Of those methods, the most widely used are Bounding Volume Hierarchy
	(BVH) algorithms.

	A BVH is a set of bounding volumes that recursively encloses 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. This is shown in Figure~\ref{fig:bounding_vol}.

\newpage
	\begin{figure}[h]
	\epsfxsize=4in
	\centerline{\epsffile{chap02/oriented_bounding_box.ps}}
	\caption{{\em
		Example of a Bounding Volume Hierarchy: bounding boxes
		recursively bound polygons \cite{gottschalk96obbtree}.} }
	\label{fig:bounding_vol}
	\end{figure}

	BVHs are designed to isolate quickly geometric features that are
	participating in collisions. This is done 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. 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. The
	differences among BVH implementations lie in the type of volumes
	used, how intersections between volumes are tested, and the
	algorithms used to build volume hierarchies for objects.

	An example of an algorithm that uses a BVH in a parallel collision
	detection algorithm is presented in \cite{kitamura-parallel}.
	In \cite{kitamura-parallel}, an octree BVH is built around the
	faces of two objects that may be colliding. When the octrees
	of two objects are compared with one another and voxels from
	the objects are found to overlap, the faces within the voxels
	are distributed to another processor where exact-feature tests
	are performed.

	Another example of a algorithm that uses a BVH in a
	parallel collision detection algorithm is presented in
	\cite{hybrid_bvh}. In \cite{hybrid_bvh} a bounding volume
	hierarchy is constructed from bounding boxes and bounding spheres
	to obtain tight fits around the features of an object. Internal
	to the bounding volumes, balanced binary trees are used to
	store polygons enclosed by the bounding volume. This algorithm
	implements parallelism by spawning threads to perform searches
	between the branches of the BVH.

        Other examples of BVH implementations include Oriented Bounding
        Box trees (OBB) \cite{gottschalk96obbtree}, Axis-Aligned
        Bounding Box trees \cite{barequet96boxtree}, Brep-Index
        trees \cite{jr91brepindex}, Binary Space Partitioning trees
        \cite{bentley, samet_rectangles}, Sphere Trees
        \cite{hubbard96approximating}, and octrees \cite{Samet:1984:QRH}.

\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 \cite{nez-collision} and \cite{threeDgames}.
