\chapter{Linear Octree-based Parallel Collision Detection Algorithm}

\section{Introduction}
	\hspace{1em}
        As presented in Chapter 2, collision detection is a multi-faceted
        problem requiring individual solutions to subsets of the collision
        detection problem. Current collision detection algorithms
        use a collection of algorithms to solve subset problems. The
        relationships among subsets of collision detection algorithms
        and how they can be used in conjunction with one another is best
        described as a pipeline. By optimizing each algorithm used in
        a collision detection pipeline, fast solutions to the general
        collision detection problem can be devised.

	This chapter describes the data structures and algorithms
	explored in the development of a parallel collision detection
	algorithm designed to solve the all-pairs problem.  This chapter
	is organized into four sections. In Sections 3.2 and 3.3, two
	octree-based data structures considered for use in a parallel
	collision detection algorithm are described. In Section 3.4,
	a new parallel collision detection algorithm for solving the
	all-pairs problem is presented and an algorithmic analysis of
	the new algorithm is discussed.

\section{Distributed Octree Data Structure}
	\hspace{1em}
	In the process of designing a parallel collision detection
	algorithm, two strategies were explored, the first of which
	involved pursuing a distributed octree implementation that would
	facilitate parallel processing for collision detection.

	A distributed octree is an octree data structure in which
	the octants and the objects they contain, are assigned to
	separate processors. In this configuration, objects can be
	operated on concurrently by the processors that manage the
	octants within which the data are contained. See Figure \ref{
	fig:distributed_octree } for an example of a distributed octree
	data structure.

	\begin{figure}[h]
        \epsfxsize=5in
        \centerline{\epsffile{chap03/distributed_octree.eps}}
        \caption{{\em
		Distributed Octree: 4-level octree data structure
		distributed over 4 processors.}  } 
	\label{ fig:distributed_octree }
        \end{figure}

	A distributed octree data structure has several qualities that
	make it appropriate for implementing a parallel collision
	detection algorithm.  The five major qualities are:

	\begin{enumerate}
	\item 
		Decomposition of an octree hierarchy for distribution
		is easy to understand and implement as a modified
		pointer-based tree. As stated in the description of
		pointer-based octrees in Chapter 2, an octree node
		stores pointers to its child nodes. To facilitate the
		distribution of octant nodes to multiple processors,
		pointers used for referencing child octants are
		generalized, enabling them to reference a processor that
		manages octants.  From a distributed octree implementor's
		perspective, the generalized pointer can be viewed as
		addresses used for communicating with processors that
		manage octants.

	\item 

		Distributing an octree across a cluster of networked
		computers is conceptually the same as distributing
		an octree across the processors of a shared-memory,
		multi-processor computer. As a function of the structure
		of an octree, clearly defined boundaries between regions
		of space are created. As a result of the logical structure
		of an octree, octree data structures have clearly defined
		regions by which data are segregated. In an octree, these
		boundaries are defined by the volume of an octant, but
		in an octree data structure, the boundaries are defined
		by the tree nodes in which data are stored. This feature
		allows tree nodes to be separated physically without
		compromising the logical structure of the octree. To
		distribute an octree data structure over a cluster of
		networked computers, pointers to octants are allowed
		to be computer network addresses where child octants
		are located.

	\item 
		When an octree is distributed across a cluster of
		computers, the aggregate size of the octree data structure
		can exceed the largest octree that can be stored on
		a single computer. This allows for a larger octrees
		to be constructed. On a single computer, the maximum
		size of an octree data structure that can be stored
		is limited to the amount of available random access
		memory.  By distributing octants to several computers,
		the memory from each computer contributes to the total
		space available for storing the data structure. It is
		important to note that although an octree data structure
		can be stored on disk, accessing the data structure is
		prohibitively slow as a result disk access speeds.

	\item 
		Distribution of data processing is a function of storing
		data in octants. As objects are placed in octants that
		bind their position and volume, they are accordingly
		distributed among the processors that manage octants.

	\item 
		The complexity of distributing an octree across multiple
		processors does not grow as a function of the number
		of processors over which it is distributed. As a result
		of the structure of an octree, once a program has been
		written to handle a single distributed octant, the same
		program should scale to any number of distributed octants.
	\end{enumerate}

	In our first attempt to develop a parallel collision detection
	algorithm, a distributed octree was used to partition and manage
	objects among multiple processors and memories. Each processor
	would then perform collision detection between objects 
	stored locally. However, after studying distributed octree
	implementations, we determined that distributed octrees are
	unsuitable for use in a parallel collision detection algorithm
	because they require load balancing to remain efficient, and,
	in some cases, must duplicate an object on multiple processors
	in order to build a tight-fitting bounding volume for the object.

   \subsection{The Load Balancing Problem}
	\hspace{1em}
	When objects become concentrated in small regions of space, their
	representations become concentrated in the octants of the octree
	representing that space. In the case of distributed octrees,
	processors managing octants where concentrations of objects
	exist have a disproportionately high workload. As a result of an
	unevenly distributed workload, performance of the distributed
	octree gained through parallelism is decreased. To solve this
	problem, load balancing can be used to redistribute work among
	the processors. Redistribution of workload is accomplished using
	three operations: dynamic octant splitting, octant migration,
	and octant consolidation.

	Dynamic octant splitting is the process of subdividing octants at
	runtime to create additional levels in an octree. Dynamic octant
	splitting is performed by subdividing the volume of an octant
	into eight new child octants and then inserting objects contained in
	the original octant into the newly created children. The goal of
	dynamic octant splitting is to create additional subdivisions of a
	volume to further segregate objects. If dynamically splitting an
	octant fails to adequately partition a concentration of objects,
	the procedure is repeated until the objects are sufficiently
	segregated. Octants containing high concentrations of objects
	are candidates for dynamic octant splitting.

	Octant migration is the process of moving octants from one
	processor to another. To move an octant between processors,
	the definition of an octant and the data the octant contains
	are reassigned to another processor. After an octant has
	been reassigned, all pointers that reference the octant are
	updated to reflect the change of management. Depending on the
	architecture of the parallel computer for which a distributed
	octree is implemented, octant migration can involve as little as
	reassigning octant pointers, as is the case for a multi-processor,
	shared-memory computer, or as much as transporting octant
	definitions and data across a network connection when an octree
	is implemented for a networked cluster of computers.

	Combined, dynamic octant splitting and octant migration can
	be used to distribute data and processing evenly throughout a
	distributed octree. However, as a result of these operations,
	the structure of a distributed octree becomes fragmented over
	processors and memory. Fragmentation reduces the performance
	of octree operations and consumes excessive amounts of memory
	as branches of the octree become unused and the paths through
	the octree span an excessive number of processors. To repair
	a fragmented octree, octant consolidation is used to remove
	unnecessary octants and decrease the number of processors spanned
	by paths through the octree. Octant consolidation is the opposite
	operation of dynamic octant splitting. Octants are consolidated
	based on the number of objects contained in a branch of an
	octree. If the children of an octant, combined, contain a small
	number of objects, the objects are moved into the parent and the
	children are deleted. This process reduces the amount of memory
	consumed by the data structure, decreases the number of levels
	in the octree, and decreases the separation distance between
	the root and leaves of the octree on a parallel computer.

        An example of a distributed octree is described in
        \cite{freitag99adaptive}. Although not designed specifically for
        collision detection, the distributed octree implementation
        discussed in this article can also be used for parallel
        collision detection. A distributed octree is used for storing
        and manipulating scientific data sets for visualization. By
        distributing a data set across multiple processors, operations
        on data can be performed in parallel. Due to the large amounts
        of data, a distributed octree is well suited for this type
        of application.

   \subsection{The Object-Octant Membership Problem} 
	\hspace{1em}
	Object-octant membership is a term that will be used to
	describe which octants an object intersects. The other factor
	which makes distributed octrees unsuitable for use in a parallel
	collision detection algorithm is the manner in which object-octant
	membership must be managed. The fundamental purpose of using an
	octree is to segregate objects based on their position. Octrees
	do this by creating a spatial relationship between objects based
	on which octants objects occupy. A spatial relationship exists
	between two objects that occupy a common octant. Several methods
	have been developed to determine the object-octant membership
	of an object. In this discussion, a search method will be used
	to illustrate problems with distributed octrees.

	As discussed in Chapter 2, a typical strategy for inserting
	data into an octree is to recursively search for octants that
	intersect the object. Depending on how an algorithm terminates
	recursive descents into the tree, upon completion of an insertion
	operation, a reference to the object will have been stored with
	octree data structure nodes that correspond to the location and
	volume of the object. Octree nodes that store references to an
	object define the object-octant membership of the object.

	As seen in Figure \ref{fig:sphere_in_persp_octree} and Figure
	\ref{fig:sphere_in_dist_octree}, when the volume of an object
	straddles octants managed by different processors, the object must
	be stored by each processor that manage octants that intersect
	the object.

	\begin{figure}[h]
        \epsfxsize=5in
        \centerline{\epsffile{chap03/sphere_straddle_2view.ps}}
        \caption{ 
		{\em A perspective and orthogonal view of a sphere
		located in the center of an 3-level octree.}
	 }
	\label{fig:sphere_in_persp_octree} \end{figure}

\newpage
	\begin{figure}
        \epsfxsize=4in
        \centerline{\epsffile{chap03/distributed_octree_diagram_sphere.eps}}
        \caption{
		{\em A distributed octree data structure storing the sphere
		from Figure~\ref{fig:sphere_in_persp_octree}.}
	 }
	\label{fig:sphere_in_dist_octree}
	\end{figure}

	Storing objects on multiple processors is problematic for
	distributed octrees because maintaining the state of an object
	requires coordinating the processors which store the object.

        Although the difficulties surrounding distributed octrees can be
        overcome, the cost of load balancing in terms of performance
        outweigh the benefits of using it for parallel collision
        detection. For this reason, distributed octrees are not suitable
        for use in a parallel collision detection algorithm.

\section{Linear Octree}

	\hspace{1em}
	The second data structure we considered for use in a parallel
	collision detection algorithm was a linear octree. A linear
	octree is not a tree-like data structure. It is an encoding
	scheme derived from the structure of an octree. Codes generated
	using a linear octree encoding scheme uniquely identify voxels
	positioned within an octree. These codes are used for describing
	three-dimensional objects volumetrically based on the voxels an
	object intersects. The set of codes that describe the volume of
	an object are called a linear octree. A linear octree is stored
	in a list data structure.

\newpage
	The basic unit of a linear octree is an octal code, also called
	octnode code. An octal code is a sequence of numbers that, when
	read from left to right, describe a path from the root of an octree
	to an octant. The numbers used in the sequence of an octal code
	correspond to the indices of octants. The position of a number
	in the sequence of an octal code corresponds to a level in the
	octree. For example, the octal code \verb+{3, 1, 4}+ refers
	to an octant located on the third level of an octree and can
	be found by recursively descending into octant 3, followed by
	octant 1, and finally octant 4.

	The sequence of numbers in an octal code can be stored
	conveniently in an unsigned integer by using the digit positions
	to store the octal code sequence. For example, the sequence
	\verb+{3, 1, 4}+ can be represented by the integer \verb+{314}+.

	Several variations of the linear encoding scheme have been
	developed. \cite{Samet:1984:QRH} provides a comprehensive overview
	of these variations as well as a description of their origins.
	\cite{setop_linear} also provides a thorough description of
	linear encoding schemes as well as discusses set operations
	between linear octrees. \cite{ray_octree} briefly describes
	a linear encoding scheme and then describes how to use linear
	octrees for ray tracing.

	Linear octrees have several qualities that make them useful
	for parallel computing environments. The most useful quality
	is that a linear octree preserves the hierarchical nature of
	the data it represents, while avoiding the need to retain a
	pointer-based tree. Furthermore, the data representation of
	a linear octree is convenient for transportation by means of
	interprocess communications.

	Another useful quality of linear octrees is a unique property
	that octal codes exhibit. By sorting in ascending order a list
	of octal codes represented as integers, the resulting sequence
	is the pre-order traversal of an octree \cite{Samet:1984:QRH}.
	As show in Figure \ref{fig:pre_order}, by visiting octants from
	a list of octal codes that has been sorted in ascending order,
	nodes in the tree are visited in order on lower to higher numbered
	branches and from top to bottom. This property of octal codes
	is useful because it provides a method for merging disparate
	linear octrees into a single octree. Given a set of octal codes,
	a pre-order traversal of an octree that only contains octants
	that intersect objects can be found by simply sorting the list
	of octants. This property is the cornerstone of the new algorithm
	presented in the next section.

	\begin{figure}
        \epsfxsize=5in
        \centerline{\epsffile{chap03/pre_order_traversal.eps}}
        \caption{{\em
		Octal codes sorted in ascending order and the order
		octree nodes are visited.}
	}
	\label{fig:pre_order}
	\end{figure}


\section{A Parallel Linear Octree Collision Detection Algorithm}
	\hspace{1em}
	In this section, a new collision detection algorithm is proposed
	that uses a linear octree for solving the all-pairs collision
	detection problem. The algorithm has ${\cal O}((n \ log \ n)/k)$ 
	performance, where $n$ is the number of objects and $k$ is the
	number of processors.

        The strategy behind the proposed algorithm is to construct the
        linear octrees of $n$ objects in parallel using $k$ processors and
        then merge the resulting octrees into a single linear octree on a
        single processor. In the description of this algorithm, the
        following assumptions are made:

	\begin{enumerate}
        \item All objects are cubes.
	\item The parallel program consists of one master process
		and $k$ slave processes.
	\item Each slave process either shares a single octree, or all
		processes have an exact copy of the same octree.
	\item The number of objects is an even multiple of the number
		of processes.
	\end{enumerate}

	\subsection{Algorithm Outline}
	\hspace{1em}
	The following is an outline of the steps performed by the
	algorithm to generate a linear octree of a set of objects and
	test the objects for collision.  

	\begin{enumerate} \item The master process divides a list of $n$
		objects by $k$ processes and distributes a list of $n$/$k$
		objects to each process. The master process then waits
		for all slaves to complete processing before execution
		is resumed.

	\item Each slave waits to receive a list of objects from the
		master. When the list of objects is received, each
		slave builds a linear octree for each object.
		The resulting octal codes are paired with an index of
		corresponding objects from the main list of objects. All
		resulting octal-code/object-index pairs are stored in
		a single list.

	\item Each slave process sorts in ascending order its list of
	octal-code/object-index pairs by the integer representation of
	the octal codes.

	\item Each slave sends its list of octal-code/object-index pairs
	back to the master process. The slave process is complete.

	\item The master process receives $k$ list of
	octal-code/object-index pairs from the slave processes.

	\item The master process merges $k$ lists of
	octal-code/object-index pairs into a single list.

	\item The master process iterates in ascending order through
	the list of octal-code/object-index and finds all pairs of
	octal codes that share octants. The indices of objects that
	correspond to octant-codes that share octants are stored in
	a list.
	\end{enumerate}

\subsection{Algorithm Pseudo Code}
	\hspace{1em}
	The algorithm can be summarized in two pseudo code programs,
	one for the master process and one for the slave processes.

{\footnotesize
\begin{verbatim}
Master Process()
Begin
  integer k := number of slaves
  address slave[ 0 to k ] := locations of slave processes
  cube object_list[ 0 to n ] := list of n objects 
  Pair<octalcode,integer> slave_lists[0 to k][] := NIL
  Pair<octalcode,integer> master_list[] := NIL
  Pair<integer,integer> colliding_pair_list[] := NIL
  octalcode smallest_octalcode := NIL

// Step 1
  sublist_size := sizeof(object_list[]) / k
  index := 0
  For each x := from 0 to k
  {
    Send( slave[x], object_list[ index to (index + sublist_size) ] )
    index := index + sublist_size
  }

// Step 5
  num_octal_codes := NIL
  For each x := from 0 to k 
  {
    Wait(slave[x])
    Receive(slave[x], slave_list[x])
  }


// Step 6
  master_list[] := MergeSortedLists(slave_lists[])

// Step 7
  index := 0
  For( object1 := 0 ... sizeof(master_list[]) - 1 )
  {
    For( object2 := object1 ... sizeof(master_list) ) 
       if( CommonPath( master_list[object1], master_list[object2] ) == true ) 
       {
         colliding_pair[index] := object1,object2	
         index := index + 1
       }
       else 
         break from inner for-loop
  }
End

Slave Process()
Begin
  cube object_list[] := NIL
  octalcode linear_octree[] := NIL
  Pair<octalcode,integer> slave_list[] := NIL
  address master := address of master process

// Step 2
  Wait( master )
  Receive( master, object_list ) 

  For each x := object_list[]
  {
    linear_octree[] := SearchOctree(object_list[x]) 
    For each y := linear_octree[]
    {
      slave_list[] append pair(linear_octree[y],x)
    }
  }

// Step 3
  Sort( slave_list[] )
// Step 4
  Send( master, slave_list )
End

Subroutine Send( address, data ) 
{
  Send "data" to a process at "address"
}

Subroutine Wait( address )
{
  Wait for communications from the process at "address"
}

Subroutine Receive( address, data )
{
  Receive "data" from the process located at "address" 
}

array Subroutine MergeSortedLists( "list of sorted lists" )
{
  Merges a "list of sorted lists" into a single "list"
  return "list"
}

Boolean CommonPath( octalcode1, octalcode2 )
{
  Determines if the octal codes share an octant.
  Two octal codes share an octant if both codes define
  octants on the same path through the octree.

  Return true if two octants are shared, otherwise return
  false.
}

array SearchOctree( cube )
{
  Determine the object-octant membership of an object return
  the octal codes of the octants this object intersects.
}

Sort( octant[] )
{
	 Sorts a list of octants in ascending order
}
\end{verbatim}
}

\subsubsection{Bounding Cube Representations} 
	\hspace{1em}
	Like other algorithms for solving the all-pairs collision
	detection problem, this algorithm uses bounding representations
	of objects to gain performance. In this algorithm, bounding cubes
	are used. Bounding cubes are used for two reasons. First, testing
	for intersection between two cubes is efficient. This is important
	because the octree search algorithm makes extensive use of cube
	intersection tests. Second, cubes can be stored efficiently in
	memory. Storage efficiency is important because it reduces the
	overall memory requirements of the collision detection algorithm
	and can be quickly transported over a network connection.

\subsubsection{Octree Search}
	\hspace{1em}
	To build a linear octree for an object, the slave processes
	search an octree for a set of octants that. When combined, these
	octants form a cube that binds the bounding cube representation
	of the object.

\subsubsection{Octal Code Comparisons}
	\hspace{1em}
	The {\tt CommonPath} subroutine is used to determine if two objects
	are colliding by determining if they share octants. The {\tt CommonPath}
	subroutine is so named because octal codes that define similar
	paths through an octree have overlapping octants. The general
	algorithm for comparing two octal codes is a piecewise equivalence
	test between the sequences of numbers stored as octal codes. If
	any of the numbers between the sequences differ, then the octal
	codes identify disparate regions of space.  Otherwise, the octal
	codes identify overlapping regions of space, and the corresponding
	objects are considered for further collision testing.

	It is possible for two octal codes to define paths of different
	lengths. When this occurs, the octant indices are compared up
	to the maximum length of the shorter octal code. For example,
	consider the two octal codes \verb+{1, 2, 3, 4, 5}+ and \verb+{1,
	2, 6, 0, 0}+. In this case, because the second octal code defines
	a shorter path than the first octal code, only the first three
	numbers in the code would be compared.

\newpage
	In practice, the implementation of the general algorithm exploits
	the integer representation of octal codes. When two octal codes
	differ in length, the longer of the two is truncated using a
	modulus and a subtraction operation. The octal codes can then
	be tested for equivalence using an integer comparison. Using
	the previous example of octal codes in integer form, octal code
	12345 would be transformed to 12300 so that it can be compared
	to octal code 12600 using an integer comparison.

	\subsubsection{Pre-order Traversal of a Linear Octree}
	\hspace{1em}
	The feature of linear octrees that makes the proposed algorithm
	efficient is the property of octal codes that, when sorted
	in ascending order, result in a list that defines a pre-order
	traversal of an octree \cite{Samet:1984:QRH}. This feature is
	used to merge the linear octree representations of multiple
	objects into a single space by concatenating the linear octree
	representations of multiple objects and sorting the resulting
	list of octal codes.

	The sorted list of octal codes is used to determine all colliding
	pairs of objects using the {\tt CommonPath} function. This is done
	by testing each octal code for a common path with subsequent
	octal codes from the list until an octal code representing
	a non-overlapping region of space is tested. At this point,
	no additional octal codes need to be tested for a common path
	because the region of space represented by the octal code does
	not overlap any additional regions of space represented in the
	list of octal codes.

	To understand why this works, recall that within an octree
	each octant is a fully enclosed subdivision of a higher level
	octant. Therefore, only parent and child octants that lie on the
	same path along a branch of the octree overlap. Because octal
	codes represent paths along octree branches, octal codes that
	represent different paths indicate non-overlapping regions of
	space. As a result of sorting octal codes in ascending order,
	octal codes representing overlapping regions of space appear
	contiguously and in order within the list such that higher level
	octants intersecting lower level octants appear first. For
	example, in the sequence of octal codes \verb+{1200, 1210, 1214,
	1330, ...}+, {\tt 1200} identifies the parent of both {\tt 1210}
	and {\tt 1214} and overlaps both of their spaces. Octal code {\tt
	1210} is the parent of {\tt 1214} and overlaps its space. Octal
	code {\tt 1330} defines a region of space that doesn't overlap
	any of the previous spaces and indicates that the previous spaces
	do not overlap any other regions of space represented in the list
	of octal codes. This property allows the search for overlapping
	octants to be performed in the fewest number of steps. As a result
	of the ordering, once two octal codes identifying non-overlapping
	regions of space have been tested, no further comparisons with
	subsequent octal codes will reveal any additional overlapping
	regions of space.


\subsection{Analysis of the Algorithm}
	\hspace{1em}
	On the master processor, steps 1 and 5 of the algorithm run
	in linear time as a function of the data distributed to, and
	collected from, the slave processes. Because every object is
	passed to the search subroutine in step 2 to build the linear
	octree for each object, each search time becomes a constant
	factor. Therefore, searching for $n$ objects runs in linear time
	as a function of the number of objects. In Step 3, each slave
	sorts $n$ resultant octal codes which takes 
	${\cal O}((n \ log \ n))$ time in the
	worst case.  In step 6, merging $k$ lists of sorted octal codes is
	done in linear time.  Finally, step 7 runs in ${\cal O}(n^2)$ time in
	the worst case, but, if objects are not allowed to remain in an
	intersecting state, then the running time is ${\cal O}(n)$ on average
	as a result of the pre-order traversal ordering of the list.

	Based on the individual run times of each step, the runtime
	performance of this algorithm will be bound by the sort performed
	in Step 3 by each slave processor. Therefore, the expected
	runtime of this algorithm is ${\cal O}((n \ log \ n ) / k)$.
