\chapter{Parallel Collision Detection System Implementation}

	\hsp{1em}
        This chapter discusses the implementation of a collision
        detection system that uses the new algorithm proposed in the
        previous chapter.  In this chapter, the architectural approach
        and design used in the implementation will be described along with
        the components that constitute the collision detection system.

\section{Client-Server Architecture, Object-Oriented \\ Design, Modular Implementation}
	\hspace{1em}
        The structure of the collision detection system is a client-server
        architecture. The application serves as the client, and the
        collision detection system acts as the server. A client-server
        approach is used to separate logically and physically the
        application from the collision detection.

	Logical separation of the collision detection system and the
	application is achieved by using object-oriented design techniques
	to encapsulate the data and functionality of the collision
	detection system in a collection of reusable components. A
	feature of this design is that it allows the collision detection
	system to be used by client applications with varying degrees
	of integration.

	As part of the design of the collision detection system, parallel
	aspects of the underlying algorithm are implemented as separate
	processes. This feature requires the collision detection
	system to be separated physically from the client application
	and was made possible by the underlying object-oriented
	design. Additionally, the physical separation of the collision
	detection system from the application allows the collision
	detection system to take advantage of both shared-memory,
	multi-processor computers and a cluster of networked computers.

\section{Operating Environment}

	\hspace{1em}
	The collision detection system has been implemented for use on
	Unix operating systems using the C++ programming
	language. Interprocess communication between components of the
	collision detection system on a single computer is implemented
	with System V semaphores and shared memory. Berkeley sockets are
	used for communicating over a network connection.

\section{Integrating Collision Detection into an \\ Application}

	\hspace{1em}
        As part of the object-oriented design of the collision detection
        system, application developers may choose from three levels of
        integration. This choice is made by selecting certain components
        of the collision detection system to build into an application.

	When the highest level of integration is used, the entire
	collision detection system is run in a process owned by the client
	application. In this configuration, the client application has
	the highest degree of control over initializing data structures
	internal to the collision detection system. The drawback to fully
	integrating the collision detection system is that the client
	application cannot take advantage of the parallel features of
	the collision detection system.

	A lower level of integration removes the task of building linear
	octrees from a client-application-owned process and performs this
	task in processes owned by the collision detection system. The
	task of merging linear octrees is still performed by a client-
	application-owned process using components from the collision
	detection system. Components from the collision detection system
	that run in a client-application-owned process communicate with
	processes owned by the collision detection system using shared
	memory and semaphores.	When this configuration is used, an
	application can begin to take advantage of the parallel features
	of the collision detection system.

	By using the lowest level of integration, all tasks
	performed by the collision detection system are removed from
	client-application-owned processes. In this configuration, an
	application can take full advantage of the parallel features
	of the collision detection system as well as communicate
	asynchronously with the collision detection system. Asynchronous
	communication with the collision detection system allows a client
	application to submit a job to the collision detection system
	and continue processing. At a later time, the client application
	can query the collision detection system to see if a previously
	submitted job is complete.

        There are two reasons for running the collision detection
        system as part of a client-application-owned process:

	\begin{enumerate}
        \item The target platform is a single-processor computer.

		In the collision detection system, multiple processes
		are used to facilitate concurrent execution in parallel
		computing environments. If the client application is
		not run on a parallel computer, then no performance
		advantage will be gained by using the parallel features
		of the collision detection system.

        \item The number of objects the client application manages is small. 

		The parallel features of the collision detection system
		are designed to enable client applications to exceed the
		number of objects other collision detection systems can
		handle. When the number of objects is small, there is no
		benefit to using the parallel features of this collision
		detection system.
	\end{enumerate}

\section{Class Objects}

	\hspace{1em}
        The following subsections describe the core components of the collision
        detection system and their role in performing collision detection.

\subsection{The Octree class}

	\hspace{1em}
        The {\bf Octree} class is used to encapsulate an octree data structure
        and its associated algorithms. Important issues this class
        addresses are the storage of an octree data structure in shared memory 
        and octree search algorithms.

	\subsubsection{Shared-Memory Octree Data Structure}
	\hspace{1em}
        On multi-processor, shared-memory computers, the parallel
        implementation of the collision detection system uses several
        processes to concurrently build linear octrees. Because the octree
        data structure is used as a static reference frame for positioning
        objects within a volume of space, it is not necessary for each
        processor to share the same octree data structure in memory.
        Searching identical octrees for the same object always produces
        identical results. However, because the size of an octree grows
        exponentially with its depth, it is advantageous for all processes
        on the same machine to share a single octree data structure in
        memory. The {\bf Octree} class addresses this issue by storing its
        internal octree data structure in shared memory.

	The main technical issue of sharing an octree between multiple
	processes is how to represent the octree data structure in
	shared memory. As described in Chapter 2, octree data structures
	are typically implemented as pointer-based trees. However,
	a pointer-based tree does not lend itself to being stored in
	shared memory because dynamically allocated nodes are used to
	construct the tree and are referenced using pointers. Typically,
	the memory sharing facilities that come with Unix operating
	systems are designed to map a small number of memory regions
	into address spaces of multiple processes, not to share many
	small blocks of dynamically allocated memory.

	To overcome this limitation, the octree data structure is
	constructed from an array of octants that is stored in a single
	region of shared memory. An array-based octree can be conveniently
	shared among many processes.

	In an array-based octree, the hierarchical relationship between
	octants is established by storing array indices with each octant.
	Array indices are used by octants to locate the position of their
	parent and child octants in the array. In array-based octrees,
	array indices are analogous to pointers in pointer-based
	trees. An example of an array-based octree is depicted in Figure
	\ref{fig:array_based_octree}. The {\bf NamedVector} class,
	which is described in section 4.5.4, is used to store an array
	of octants in shared memory.

	\begin{figure} 
	\epsfxsize=6in
	\centerline{\epsffile{chap04/array_based_octree.eps}}
	\caption{ {\em
		Portions from an array-based octree demonstrating
		how to traverse from parent to child octant using
		the array indices stored in each array cell. }
	}
	\label{fig:array_based_octree} 
	\end{figure}


	\subsubsection{Octant class}
	\hspace{1em}
	The {\bf Octant} class implements the node data structure
	used in an octree data structure. An instance of this class
	corresponds to an octant in an octree. Internally, this class
	stores a {\bf Cube} class to represent the volume of an octant
	and array indices that identify the location of parent and child
	octants in an array-based octree.

	\subsubsection{Octree::iterator class}
	\hspace{1em}
	To traverse an array-based octree, indices stored with octants
	are used to navigate the array to parent and child octants
	according to the structure of the octree. The {\bf Octree::iterator}
	class simplifies the process of traversing an array-based octree
	by encapsulating the mechanics of inspecting and storing array
	indices. This class is based on a container-iterator design
	pattern and is designed to work like the iterator class in the
	C++ Standard Template Library. Readers unfamiliar with iterators
	can think of them as intelligent pointers used for navigating
	data containers. In this case, the container is an array, and the
	data are {\bf Octant} class instances. Because the natural structure
	of an octree is not a linear array, the iterator class is used
	to abstract client code from the array storage container and
	make it appear more like an octree. The {\bf Octree::iterator} class
	simplifies writing octree algorithms.

	\subsubsection{Octree::ResolveObject()}
	\hspace{1em}
	The {\bf Octree::ResolveObject()} function implements a
	recursive search of the octree that finds the octants which
	bind an object. This function is used to build the linear
	octree representation of an object. The parameters of the {\bf
	Octree::ResolveObject()} function are a {\bf Cube} class, a
	maximum search depth, and a list of {\bf OctalCode} classes. The
	{\bf Octree::ResolveObject()} function searches the octree data
	structure stored in the {\bf Octree} class instance for octants
	that intersect a cube. The resulting octal codes are stored in the
	{\bf OctalCode} list parameter. These octal codes are the linear
	octree representation of the {\bf Cube}. The {\bf OctalCode}
	list parameter is a value-result argument and is used to pass
	the linear octree out of this function.

\subsection{OctreeMaster Class}
	\hspace{1em}
        The {\bf OctreeMaster} class is the intermediate interface
        between client applications and processes that perform octree
        searches.  The primary responsibilities of the {\bf OctreeMaster}
        class include assigning objects to slaves, signaling slaves to
        begin octree searches, and merging search results. Moreover,
        this class acts as the interface to processes that build linear
        octree representations of objects.

	\subsubsection{Asynchronous Communication with Client Application}
	\hspace{1em}
	One of the features implemented by the {\bf OctreeMaster}
	class is an asynchronous communication method for client
	applications. Using this feature, client applications are able
	to submit jobs to the collision detection system and continue
	running while the job is being processed. Clients can then verify
	that the job has been completed through the {\bf OctreeMaster}
	class. Alternatively, the client application can wait for the job
	to complete. While waiting, execution of the client application
	is suspended.

	\subsubsection{Object transfer and storage}
	\hspace{1em}
	Object data are transfered to and from an {\bf OctreeMaster}
	class instance using shared memory. In most cases, the {\bf
	NamedVector} class is used for this purpose. To transfer data to
	an instance of an {\bf OctreeMaster} class, a process constructs
	a {\bf NamedVector} class that attaches to the shared memory of a
	{\bf NamedVector} class owned by an {\bf OctreeMaster} class. The
	process and the {\bf OctreeMaster} can read and write the same
	region of shared memory using their respective instances of a
	{\bf NamedVector} class.  Reading and writing operations are
	synchronized using a {\bf NamedSemaphore} class.

\subsection{OctreeClient Class}
	\hspace{1em}
        The {\bf OctreeClient} class is the interface used by client
        applications to communicate with the collision detection system.
        The {\bf OctreeClient} class provides an interface for clients
        to send and receive signals and data with the collision detection
        system.

        This class provides three functions to communicate with the
        collision detection system.

	\begin{itemize}
        \item {\bf OctreeClient::ResolveObjects():} The {\bf
        ResolveObjects()} function is used to transmit objects to the
        collision detection system and signal the {\bf OctreeMaster}
        to begin octree searches. This function returns immediately.

        \item {\bf OctreeClient::Finished():} The {\bf Finished()}
        function is used to determine if a job submitted using the {\bf
        ResolveObjects()} function has been completed.

        \item {\bf OctreeClient::Wait():} The {\bf Wait()} function
        is used to wait for a job that was submitted using the {\bf
        ResolveObjects()} function. This function blocks the process
        that invokes it until the requested job has been completed and
        data is ready to be delivered to the client application.

	\end{itemize}

	Internally, this class uses {\bf NamedVector} and {\bf
	NamedSemaphore} classes to transport data and communicate with
	the collision detection system.

\subsection{NamedVector Class}
	\hspace{1em}
	The {\bf NamedVector} class is a template class data structure
	designed to facilitate sharing memory between processes. This
	class is implemented as part of the class library for the
	collision detection system. The interface of the {\bf NamedVector}
	class is designed to simulate the C++ Standard Template Library
	vector class. Data is stored internally in a shared-memory
	region. When a {\bf NamedVector} class is constructed, the class
	creates or attaches itself to a shared memory region. Upon
	construction, if the shared memory region the class instance
	should use exists, then the class instance attaches to the memory,
	otherwise the memory is allocated. The {\bf NamedVector} class
	uses a mnemonic to identify the shared-memory region with which
	to associate.

\subsection{NamedSemaphore Class}
	\hspace{1em}
	Throughout the collision detection system, processes and shared
	memory must be synchronized. To facilitate synchronization
	operations, the {\bf NamedSemaphore} class is implemented
	as part of the class library of the collision detection
	system. The {\bf NamedSemaphore} class encapsulates operations
	on System V semaphores.  Like the {\bf NamedVector} class, upon
	initialization, the {\bf NamedSemaphore} class uses a mnemonic
	to determine with which semaphore to identify.

\section{Service Components}
	\hspace{1em}
	To implement the previously described classes as components
	running in separate processes, harness programs are
	used to instantiate classes and initialize communication
	facilities. The resulting programs function as service components
	in the collision detection system.

\newpage
        The collision detection system consists of four services
        excluding the the client application: {\bf octree\_master},
        {\bf octree\_slave}, {\bf octree\_netclient}, and {\bf
        octree\_netserver}.

	\subsection{Octree\_master Service}
	\hspace{1em} The {\bf octree\_master} service is the harness
	for the {\bf OctreeMaster} class. This service interfaces with
	an instance of the {\bf OctreeClient} class to forward data
	and signals to an instance of the {\bf OctreeMaster} class. The
	{\bf octree\_master} service then drives the {\bf OctreeMaster}
	class by invoking its functions to communicate with the {\bf
	octree\_slave} service.

	\subsection{Octree\_slave Service}
	\hspace{1em}
        The {\bf octree\_slave} service is the harness for the {\bf
        Octree} class. The {\bf octree\_slave} service receives signals
        and data from an instance of the {\bf OctreeMaster} class
        and, in turn, drives the {\bf Octree} class to perform octree
        searches. The {\bf OctreeMaster} class is capable of interfacing
        with multiple {\bf octree\_slave} service processes. Multiple
        {\bf octree\_slave} service processes running on the same computer
        are used to achieve parallelism on a multi-processor computer.

	\subsection{Class-service Relationships}
	\hspace{1em}
	The relationship between the {\bf OctreeClient} class,
	{\bf octree\_master} service, {\bf OctreeMaster} class,
	{\bf octree\_slave}, and {\bf Octree} class is depicted in
	Figure~\ref{fig:instance_diagram}.
	\begin{figure} 
	\epsfxsize=6in
	\centerline{\epsffile{chap04/component_diagram.eps}}
	\caption{{\em Instance diagram of the collision detection system. }}
	\label{fig:instance_diagram}
	\end{figure}
	Because the roles of the service components and the classes
	with which they communicate are isolated from one another,
	application developers have the option of choosing the level
	in which the collision detection system is integrated into the
	client application. As show in Figure \ref{fig:instance_diagram},
	the {\bf OctreeClient} class, {\bf OctreeMaster} class,
	and {\bf Octree} class all expose an interface called {\bf
	ResolveObject()}. Functionally, the {\bf ResolveObject()}
	interface works approximately the same between all three classes
	that implement it. This allows the client application to be
	attached to the collision detection system using any one of
	the three {\bf ResolveObject()} interfaces.  By choosing the
	{\bf ResolveObject()} interface to attach to, the application
	developer chooses the level in which the collision detection
	system is integrated into the client application.

	\subsection{Octree\_netclient and Octree\_netserver Services}
	\hspace{1em}
	The {\bf octree\_netclient} and {\bf octree\_netserver}
	services are the glue that enables the collision detection
	system to distribute the task of building linear octrees over
	a network of computers. These services mimic the behavior of
	{\bf octree\_slave} and client applications. They operate by
	intercepting data and signals from client applications and {\bf
	octree\_slave} services and forward information across network
	connections.

        The {\bf octree\_netclient} service implements the communication
        interface that the {\bf octree\_slave} service component uses to
        communicate with an instance of the {\bf OctreeMaster} class. This
        allows the {\bf octree\_netclient} to receive signals and data
        from an {\bf OctreeMaster} class.  When an {\bf OctreeMaster}
        initiates a search, an {\bf octree\_netclient} service receives
        the request and sends it across a network connection to a
        corresponding {\bf octree\_netserver}.

	When an {\bf octree\_netserver} service receives a request from
	an {\bf octree\_netclient} service, the {\bf octree\_netserver}
	simulates the behavior of a client application and submits the
	search request to an {\bf octree\_master} service running on
	the same computer. The process is reversed to send results back
	to the {\bf octree\_master} service that originally requested
	the octree searches to be performed. The configuration of a
	collision detection system for parallel processing is shown in
	Figure~\ref{fig:NetworkConf}.

	\begin{figure} [h]
	\epsfxsize=6in
	\centerline{\epsffile{chap04/networkconf.eps}}
	\caption{ 
		{\em Collision detection system utilizing network
		connections for distribution.}
	}
	\label{fig:NetworkConf}
	\end{figure}

	\subsection{Bandwidth Utilization}
	\hspace{1em}
        Both the {\bf octree\_netclient} and {\bf octree\_netserver}
        services have the ability to bind themselves to a specific
        network connection. This feature gives the collision detection
        system the ability to take full advantage of all available
        network bandwidth for moving data to and from networked
        computers. This feature is particularly useful when computers
        are multi-homed on a network. For each network interface, a
        corresponding {\bf octree\_netclient}/{\bf octree\_netserver}
        can be installed, allowing data transportation to be distributed
        over the interfaces.

	Using {\bf octree\_netclient} and {\bf octree\_netserver}
	services in combination with the collision detection system
	services allows for a variety of configurations to be constructed
	that take full advantage of all available resources.

	Examples of how the collision detection can be configured
	for maximum utilization of resources are shown in
	Figure~\ref{fig:SampleConf}.

	\vspace{0.3in}
	\begin{figure} [h]
	\epsfxsize=6in
	\centerline{\epsffile{chap04/sampleconf.eps}}
	\caption{{\em
		Sample configurations of the collision detection system
		using both shared-memory and networked computers.}
	}
	\label{fig:SampleConf}
	\end{figure}

