\chapter{Conclusions and Future Work}

	\hsp{1em}
	In this thesis we presented a new collision detection algorithm 
	that solves the all-pairs collision detection problem using
	parallel processing. The design of the algorithm is based on a
	linear octree and runs in parallel with a theoretical performance
	of ${\cal O}(( n\ log \ n)/k)$ runtime. The algorithm has been
	implemented as a collision detection system using object-oriented
	design techniques and a client-server architecture. The
	architecture of the collision detection system is designed to use
	the parallel capabilities of both shared-memory, multi-processor
	computers and clusters of networked computers. Additionally,
	the modularity of the collision detection system gives
	application developers the flexibility to choose the level
	at which the collision detection system is integrated into an
	application. Using the collision detection system, experimental
	results have been generated that demonstrate how the algorithm
	performs according to the calculated theoretical performance.

\section{Conclusions}

	\hsp{1em}
	Distributed octree data structures are well suited for collision
	detection when the data storage requirements of an application
	exceed the memory capacity of a single computer. In this case,
	a distributed octree data structure used in conjunction with
	a cluster of networked computers is an effective solution
	that will enable an application to meet the requirements of a
	memory-intensive application. However, distributed octree data
	structures are ill suited for implementing parallel collision
	detection algorithms that compete with the performance of existing
	collision detection algorithms. Issues of load balancing and
	object representation in the data structure prevent algorithms
	that use the distributed octree data structures from performing
	efficiently. Linear octrees are an efficient and robust method
	for representing objects in a collision detection algorithm.

\section{Future Work}

	\hsp{1em}
	Many aspects of the algorithm and collision detection system
	developed in this thesis are the result of an evolutionary process
	in which experimental designs were explored. Successful ideas
	and techniques from these experiments became part of the final
	algorithm and collision detection system. A prime example of
	an evolutionary change the collision detection system underwent
	is the transition from a distributed octree to a linear octree
	used in the parallel collision detection algorithm. In the same
	way that the algorithm and collision detection system evolved
	into the current implementation, it can continue to evolve with
	further development. The following list outlines areas where
	the algorithm and collision detection system can be improved.

	\begin{enumerate}
	\item 	Faster octree searches 

		In the collision detection system the algorithm used for
		finding the set of octants that enclose an object is a
		recursive search of an octree. The running time of the
		search is ${\cal O}(log \ n)$. An alternative algorithm could be
		used that directly calculates the octal code of the octant
		in which the center of an object resides. The search for
		octants that enclose the object can then be restricted
		to the octants adjacent to the octant containing the
		center of the object. The formula for calculating the
		octal code of a three-dimensional coordinate is well
		known and runs in ${\cal O}(1)$ time. A description of
		this formula can be found in \cite{Vemuri:1998:FCD}. As
		a result of restricting the search to a constant number
		of octants, the algorithm for performing an octree search
		will run in ${\cal O}(1)$ time.

		This search was not used because the original search
		algorithm developed for this project was designed for a
		distributed octree. At the stage of the project when the
		transition was made from using a distributed octree to
		a linear octree, the algorithm for performing an octree
		search was already well developed and debugged. This
		search works equally well for building linear octrees
		and inserting objects into a distributed octree. Another
		reason for not implementing the new algorithm when the
		transition was made was that it would not improve the
		algorithmic performance of the system as a whole. Because
		a linear octree is built for each object every time
		the collision detection system is invoked, the search
		routine that builds the linear octree becomes a constant
		factor in the collision detection algorithm. However,
		implementing this feature will improve the speed of the
		collision detection system.

	\item	Improved network performance

		When the collision detection system is run on a cluster of
		networked computers, performance is limited by the speed
		at which data can be transferred between computers. Two
		methods should be explored to reduce the amount of network
		traffic generated by the collision detection system  in
		order to increase the throughput of network operations:

		\begin{itemize}
		\item {\bf Data compression}
			By compressing data that is transferred
			across the network, the total number of bytes
			transferred is decreased. The choice of
			which compression scheme to use should be based
			on the total amount of time needed to compress,
			transfer, and decompress.

		\item {\bf UDP transport protocol} 
			Currently, the TCP protocol is used to move data
			across network connections reliably. In order to
			deliver data reliably, the TCP protocol incurs
			overhead which results in extra network traffic.
			Schemes have been developed to deliver data
			reliably using UDP, an unreliable protocol,
			and should be explored to determine if they
			are suitable for use in the collision detection
			system.
		\end{itemize}

	\item	Parallel Merge Operation

		In Step 6 of the collision detection algorithm, the octal
		codes generated by the slave processes are sent to the
		master process to be merged. When four or more processors
		are being used and the number of objects is large, this
		step can possibly benefit from a parallel merge operation.

		To perform the merge in parallel, the data between
		pairs of processors can be merged until only one
		pair of processors with data remains. At this point,
		the two remaining processors send their data to the
		master processor where the final merge is performed. To
		demonstrate how this algorithm works consider eight
		processors, each with a list of octal codes, and one
		master processor. In the first stage of merging, process
		1 sends its list to processor 2, processor 3 sends its
		list to processor 4, processor 5 sends to 6, and 7 sends
		to 8. Processors 2, 4, 6, and 8 then merge the lists they
		are storing. In the second stage of the merge operation,
		processor 2 sends its list to processor 4 and processor
		6 sends its list to processor 8. Processors 4 and 8 then
		merge their lists, and the results are sent to the master
		processor for the final merge. This algorithm can be
		expanded to additional levels as well as work with an
		uneven number of processors.

		This algorithm incurs a logarithmic increase in the
		amount of time spent performing communication operations
		as opposed to all slaves sending their data to the master
		processor in one step. However, the benefit of performing
		merges in parallel is that the actual time spent merging
		ordered lists on the master process will be decreased.

	\item	Exploit spatial and temporal coherence 

		The possibility of exploiting coherence to improve the
		algorithmic performance from ${\cal O}(n \ log \ n)$
		to ${\cal O}(n)$ may exist. As a result of coherence,
		if objects move a sufficiently small distance between
		invocations of the collision detection algorithm, the
		number of objects that change position in the octree
		between time steps will be small.  Therefore, octal codes
		in the linear octree and the sorted order of the octal
		codes will remain approximately constant between time
		steps. This situation can be exploited in step 3 of the
		algorithm when each slave sorts its list of octal codes.

		Because the collision detection algorithm partitions
		and distributes the list of objects to slave processes
		in the same order on each invocation of the algorithm,
		the list of objects a slave receives and the order of the
		octal codes the slave generates will remain approximately
		constant as a result of coherence. Therefore, if the slave
		process caches the order of the octal codes it generates
		between invocations, the slave will be able to construct
		a nearly sorted list of octal codes upon each
		invocation. The list of octal codes can then be sorted
		completely using an insertion sort which, when run on
		a nearly sorted list, runs in ${\cal O}(n)$ time on average.

		In the current implementation of the collision detection
		system, the algorithmic performance is bound to the
		runtime of the sort performed by the slave processes,
		which run in ${\cal O}(n \ log \ n)$ time.  If this
		modification to the algorithm does in fact work, then
		the performance of the collision detection algorithm
		will be improved to ${\cal O}( n/k )$.

	\end{enumerate}
