\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 implemented components that constitute the collision detection system. \section{Implementation Architecture} \section{Client-Server Architecture, Object-Oriented Design, Modular Implementation} The structure of the collision detection system is a client-server architecture. The application serves as the client and the collision detection system as the server. A client-server approach is used to logically and physically separate the application from the collision detection. Logical separation of the collision detection system from 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 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 physically separated 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 as well as a cluster of networked computers. \section{Operating Environment} The collision detection system has been implemented for use on Unix operating systems using the C++ language. Interprocess communication between components of the collision detection system on a single computer is implemented with SysV semaphores and shared-memory. Berkley sockets are used for communicating over a network connection. \section{Integrating Collision Detection into an Application} As part of the object-oriented design of the collision detection system, application developers may choose from three levels of integration. Application developers make this choice by selecting which 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 into a client application 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 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 with the collision detection system asynchronously. 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 there no need to invoke the parallel features of the collision detection system as no performance will be gained. \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 parallel features of this collision detection system. \end{enumerate} \section{Class Objects} The following sections describe the core components of the collision detection system and their role in performing collision detection. \subsection{Octree class} The 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} On multi-processor, shared-memory computers, the parallel implementation of the collision detection system uses several processes to build linear octrees concurrently. Because the octree data structure is used as a static reference frame for positioning objects in 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 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 the dynamically allocated octant nodes used to construct the tree 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 is convenient for sharing 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. The NamedVector class is used to store an array of octants in shared memory. Octant class: The 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 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} 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 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 Octant class instances. Because the natural structure of an octree isn't 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 Octree::iterator class simplifies writing octree algorithms. (insert figure of pointer-based octree and equivalent array octree) \subsubsection{Octree::ResolveObject()} The Octree::ResolveObject() function implements the search algorithm described in Chapter 3 for finding octants in an octree that bind an object. This function is used to build the linear octree representation of an object. The parameters of the Octree::ResolveObject() function are a Cube class, a maximum search depth, and a list of OctalCode classes. Octree::ResolveObject() function searches the octree data structure stored in an Octree class instance for octants that intersect a cube. The resulting octal codes are stored in the OctalCode list parameter. These octal codes are the linear octree representation of the Cube. The OctalCode list parameter is a value-result argument and is used to pass the linear octree out of this function. The complete class diagram of the Octree class is as follows (ref figure): (insert class diagram of the octree) \subsection{OctreeMaster class} The OctreeMaster class is the intermediate interface between client applications and processes that perform octree searches. The primary responsibilities of the 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. The class diagram for the OctreeMaster is (ref figure): (insert class diagram of OctreeMaster) Asynchronous Communication with Client Application: One of the features implemented by the 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 executing while the job is completed. Clients can then that verify the job has been completed through the 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} Object data are transfered to and from an OctreeMaster class instance using shared memory. In most cases, the NamedVector class is used for this purpose. To transfer data to an instance of an OctreeMaster class, a process constructs a NamedVector class that attaches to the shared-memory of a NamedVector class owned by an OctreeMaster class. The process and the OctreeMaster can read and write the same region of shared memory using their respective instances of a NamedVector class. Reading and writing operations are synchronized using a NamedSemaphore class. \subsection{OctreeClient class} The OctreeClient class (ref class diagram) is the interface used by client applications to communicate with the collision detection system. The 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. OctreeClient::ResolveObjects(): The ResolveObjects() function is used to transmit objects to the collision detection system and signal the OctreeMaster to begin octree searches. This function returns immediately. OctreeClient::Finished(): The Finished() function is used to determine if a job submitted using the ResolveObjects() function has been completed. OctreeClient::Wait(): The Wait() function is used to wait for a job that was submitted using the 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. Internally, this class uses NamedVector and NamedSemaphore classes to transport data and communicate with the collision detection system. (insert class diagram of OctreeClient) \subsection{NamedVector class} The 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 NamedVector class is designed to simulate the C++ Standard Template Library vector class except, internal data is stored in a shared memory region. When a NamedVector class is constructed, the class internally manages creating or attaching to a shared memory region. Upon construction, if the shared memory region the class instance should use exists, then the memory is attached to it otherwise, the memory is allocated. The NamedVector class uses a mnemonic to identify the shared- memory region to associate with. (insert class diagram of NamedVector) \subsection{NamedSemaphore class} Throughout the collision detection system, processes and shared memory must be synchronized. To facilitate these operations, the NamedSemaphore (ref class diagram) class is used. This class is implemented as part of the class library of the collision detection system. The NamedSemaphore class encapsulates operations on SysV semaphores. Like the NamedVector class, upon initialization, the NamedSemaphore class uses a mnemonic to determine which semaphore to identify with. (insert class diagram for NamedSemaphore) \section{Service Components} To implement the previously described classes as components running in separate processes, simple harness programs are used to instantiate classes and initialize communication facilities. The resulting programs function as service components in the collision detection system. The collision detection system consists of four services excluding the the client application: octree\_master, octree\_slave, octree\_netclient, and octree\_netserver. \subsection{octree\_master service} The octree\_master service is the harness for the OctreeMaster class. This service interfaces with an instance of the OctreeClient class to forward data and signals to an instance of the OctreeMaster class. The octree\_master service then drives the OctreeMaster class by invoking its functions to communicate with the octree\_slave service. \subsection{octree\_slave service} The octree\_slave service is the harness for the Octree class. The octree\_slave service receives signals and data from an instance of the OctreeMaster class and in turn drives the Octree class to perform octree searches. The OctreeMaster class is capable of interfacing with multiple octree\_slave service processes. Multiple octree\_slave service processes running on the same computer are used to achieve parallelism on a multi-processor computer. The interaction between a client application, octree\_master, and octree\_slave is shown in (ref figure). (insert interaction diagram of client, octree\_master, octree\_slave) \subsection{Class-service relationships} Now that the major components of the collision detection system have been introduced, the relationships between the classes and services can be described in their entirety (ref fig). (insert class-service relationship diagram) Because the roles of the service components and the classes they communicate with are isolated from one another, client applications have the option of choosing which level of integration they prefer to have with the collision detection system (ref fig). (insert 3 figures of client application integrating with collision detection system) \subsection{octree\_netclient and octree\_netserver services} The octree\_netclient and 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 octree\_slaves and client applications. They operate by intercepting data and signals from client applications and octree\_slaves and forward information across network connections. The octree\_netclient service implements the communication interface that the octree\_slave service component uses to communicate with an instance of the OctreeMaster class. This allows the octree\_netclient to receive signals and data from an OctreeMaster class. When an OctreeMaster initiates a search, an octree\_netclient service receives the request and sends it across a network connection to a corresponding octree\_netserver. When an octree\_netserver service receives a request from an octree\_netclient service, the octree\_netserver simulates the behavior of a client application and submits the search request to an octree\_master service running on the same computer. The process is reversed to send results back to the octree\_master service that originally requested the octree searches to be performed. (insert block diagram of collision detection system with netclients/servers) (insert interaction diagram of collision detection system with netclients/servers) \subsection{Bandwidth Utilization} Both the octree\_netclient and 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 octree\_netclient/octree\_netserver can be installed allowing data transportation to be distributed over the interfaces. Using octree\_netclients and octree\_netservers 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. (insert diagrams of collision detection configurations)