\chapter{Implementation and Results} \hsp{1em} This chapter discusses the implementation of a collision detection system that uses the new algorithm proposed in the previous chapter. This chapter is organized into three sections. First, the basic layout of the design and architectural approach to the implementation is presented. Second, architectural details and processes internal to the implementation are described. Finally, results of testing the implementation are presented. \section{Implementation Architecture} \subsection{Client-Server Architecture, Object-Oriented Design, Modular Implementation} The structure of this collision detection system uses a client-server architecture. In this case, the client is the application and the server is the collision detection system. The client-server architecture is used to logically and physically separate the application from the collision detection. Logical separation of system components is facilitated using an object-oriented design. Object-oriented techniques are used to logically encapsulated data and data transformations used by components. The collision detection system is then constructed using the components. The object-oriented techniques where also used to create reusable code through generic programming. To create a true client-server architecture, the modularity of the design is exploited to create physical separation between components. Physical separation is done by running components in their as their own process. This design also allows parallel aspects of the collision detection algorithm to be implemented using concurrently executing processes. Additionally, modularity makes the system highly reconfigurable. \subsection{Operating Environment} This system has been implemented for Unix operating systems using the C++ language. To support communication between processes on a single computer, SysV semaphores and SysV shared-memory APIs are used. Additionally, to support communication over network connections, the Berkley sockets API is used. Computer architecture supported by the system include single processor, multi-processor shared-memory, and clusters of networked computers. \subsection{Application-Collision Detection System Integration} As part of the system's object-oriented design, application developers have the choice of running the collision detection system as part of an application or as a separate processes. Both configuration have advantages, but the choice to use one over the other should be made based on the needs of the application and the computer architecture it is intended to run on. There are two reasons to run the collision detection system in the same process as the client application. \begin{enumerate} \item The target platform is a single processor computer. In the collision detection system, multiple processes are used to reinforce the client-server architecture of the system as well as facilitate concurrent execution in multiprocessor environments. However, when the application and collision detection system are executing on the same processor, both processes would be competing for the same CPU time. Therefore, its more efficient to execute both as part of the same process and completely avoid process scheduling conflicts. \item The number of objects the application manages is small. The parallel features of this collision detection system are designed to allow applications to exceed current limitations of the number of objects collision detection systems can handle. When the number of objects is small there is no benefit to using parallel features of the collision detection system. \end{enumerate} Besides these two reasons, there are additional benefits to running the collision detection system in the application process. First, when run locally, applications have a higher degree of control over initialization of the collision detection system's internal data-structures then when run in separate processes; namely the octree and intermediate object storage. Direct control over these data-structures is when, for example, the depth of the octree needs to be changed while the application is running. When the collision detection system is running separately, control over its internal data-structures are highly limited. Another benefit of running the collision detection system in the application's process is that communication between the application and the collision detection system is faster than when they run separately. This is because interprocess communication to synchronize the collision detection system and the application is not needed. If parallel capabilities of the system are used, then the collision detection system must be run separate from the application. Internally, multiple processes are used to facilitate concurrent execution on shared-memory multiprocessor computers. This is used to perform multiple octree searches simultaneously. Communication between the application and server processes is done using a client API provided with the system. When running in this configuration, the application and collision detection system are logically and physically isolated from one another. Physical separation enables the the parallel execution environment to be configured independent of the application. \section{Object-oriented design} \subsection{Block-Diagram Layout} The following diagrams depict the two types of relationships an application can have to interface with the collision detection system. The first diagram shows the collision detection system integrated into the application directly (reference figure). The second show how the collision detection system can be run separately from the application (reference figure). The components show in the diagrams will be explained in the following sections. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert diagrams of application with collision detection system) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsection{Class Objects} The following sections describe the major that comprise the core functionality of the collision detection system. \subsubsection{Octree} The Octree class is used to encapsulate an octree data-structure and their associated algorithms. Important issues this class addresses are storage of octree data-structures in shared memory and octree search algorithms. \paragraph{Shared Memory Octree Data-structure} On multi-processor shared memory machines, the parallel implementation of the collision detection system uses multiple processors to perform concurrent octree searches. Because the octree data-structure is used as a static reference to position objects in 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 produce 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 surrounding shared-memory octrees is how to represent the data-structure in memory. As demonstrated in chapter 2, the octree data-structure is typically implemented as a pointer-based tree. However, this implementation does not lend itself to being stored in shared-memory because octant nodes are dynamically allocated and their hierarchical relationship is established using pointers. Memory sharing facilities are typically designed to share linear regions of one process with another. To overcome this limitation, the octree is stored in linear region of memory as an array of octants. This storage representation can conveniently be shared by mapping the address space of the octant array into process' address space when the Octree class is initialized. In this representation, the hierarchical relationship between octants is established by storing indices with each octact that identify the positions of their children in the octant array. Array indices are analogous to pointers in a pointer-based octree implementation. Traversing an array-based octree is nearly identical to traversing a pointer-based octree; instead of following pointers from parent to child octant, array indices indicate the next position in the array to move to. To simplify creating a shared memory region to store an array of octants, the NamedVector class is used, which is described later. \paragraph{Octant class} Internal to the octree data-structure, the Octant class implements the container used to represent octree octants. In addition to array indices of child octants, the Octant class also stores the array index of their parent octant, a Cube that bounds the space the octant encloses, an OctalCode class, and a flag indicating if the octant is a leaf in the tree. \paragraph{Octree::iterator} Because Octant classes represent parent-child relationships using array indices, traversal of the octree data-structure involves incrementing and decrementing an index into the array and accessing the Octant array of directly. To encapsulate the mechanics of this process and abstract client code from the linear storage of the octree, the Octree::iterator class is provided. The Octree::iterator class implements methods for traversing the octree data-structure using a set of convenience operators. This class is based on container-iterator design pattern and is designed to work functionally like iterators 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 octree's natural structure isn't a linear array, the iterator class is used to abstract client code from the array storage container making it appears more like a pointer based octree. This simplifies writing octree search algorithms. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert figure of tree based octree and equivalent array octree) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \paragraph{Octree::ResolveObject()} The most important function the Octree class exposes to clients is ResolveObject(). This function implements the search algorithm described in chapter 3 used for finding enclosing octants in an octree. As its parameters, ResolveObject() takes a Cube class, a maximum search depth, and a list of OctalCode classes. ResolveObject searches the octree for octants that tightly enclose the Cube and stores the results in the OctalCode list parameter. \paragraph{NamedVector class} To simplify sharing memory between processes, the NamedVector template class is implemented as part of the class library for this project. NamedVector implements an STL-like vector that uses shared memory storage internally. When the NamedVector is constructed, it determines if the shared memory region it is supposed to use already exists. If it does, it is attached to, otherwise it is created. To identify the region of memory to use, this class uses a mnemonic that names the region of memory to use. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert class diagram of NamedVector) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} Internal to the Octree class, the NamedVector is used to store a list of Octants and facilitates coordinating the construction of a shared octree data-structure. The class diagram of the Octree class is as follows (ref figure): (insert class diagram of the octree) \subsubsection{OctreeMaster} The OctreeMaster class is the intermediate interface between client applications and processes that perform octree searches. The primary responsibilities of OctreeMaster include assigning objects to slaves, signaling slaves to begin octree searches, and merging search results. In other words, this class acts as the interface to processes that perform octree searches. Processes that perform octree searches are implemented in the octree\_slave component and are introduced later. The class diagram for the OctreeMaster is (ref figure): \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert class diagram of OctreeMaster) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \paragraph{Asynchronous Communication with Client Application} One of the features of the OctreeMaster class is asynchronous communication methods for client applications. Using this feature, client application are able to submit jobs to the collision detection system and continue executing while the job is completed. Clients can then check back with the OctreeMaster to see if the job is complete. Optionally, the client application can wait for the job to complete. While waiting, execution of the client application is suspended. \paragraph{Object transfer and storage} Objects are transfered to and from the OctreeMaster using shared memory. In most cases, the NamedVector class is used for this purpose. Process that send data to class or receive objects from the OctreeMaster class open a NamedVector to read and write it as needed. To synchronize reading and writing operations, NamedSemaphores are used. \paragraph{NamedSemaphore class} Throughout the collision detection system, processes and access to shared resources needs to be to synchronized. To facilitate these operations, the NamedSemaphore (ref class diagram) class is implemented in the class library for the system. The NamedSemaphore class encapsulates SysV semaphore functions. Like the NamedVector class, upon initialization, NamedSemaphores use a mnemonic to determine to determine which semaphore to identify with. Process that open a NamedSemaphore with the same name are given access to the same semaphore. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert class diagram for NamedSemaphore) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} NamedSephores are used by OctreeMaster to facilitate pausing processes and implementing asynchronous communication with the client application. \subsubsection{OctreeClient} The OctreeClient class (ref class diagram) is the interface client applications use 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 perform all communication operations. OctreeClient::ResolveObjects(): The ResolveObjects function is used to pass 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 all octree searches have been completed. This function is called after ResolveObjects to determine if data is ready for retrieval from the collision detection system. OctreeClient::Wait(): The Wait function is used to wait for the collision detection system to finish all collision detection tasks. This function will block the calling process until the data is ready. Return from this function indicates that the collision detection system has completed all octree searched. Internally, this class uses NamedVectors and NamedSemaphores to transport data and communicate with the collision detection system. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert class diagram of OctreeClient) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsection{Service Components} To implement the previously described classes as components running in separate processes, simple harness programs are written to instantiate the class and initialize any additional communication facilities needed. The resultant component functions as a service in the collision detection system. The collision detection system is made up of four services excluding the the client application: octree\_master, octree\_slave, octree\_netclient, and octree\_netserver. The flow control the harness applications is a continuous event loop (ref event loop figure) \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert diagram of harness event loop) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsubsection{octree\_master} The octree\_master service is the harness for the OctreeMaster class. This service interfaces with the OctreeClient class to forward search requests and data to the OctreeMaster class. octree\_master then drives the OctreeMaster class by calling its functions to communicate with the octree\_slave component. \subsubsection{octree\_slave} The octree\_slave service is the harness for the Octree class. octree\_slave receives signals and data from 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 services. Multiple octree\_slave services running no the same machine are used to achieve parallelism on multi-processor computers. The interaction between a client application, octree\_master, and octree\_slave is show in (ref figure). \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert interaction diagram of client, octree\_master, octree\_slave) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsection{Class-service relationships} Now that the major components of the collision detection system have been introduced, the relationship between the classes and services can be described in its entirety (ref fig) \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert class-service relationship diagram) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} Because the roles of the service components and the the classes they communicate with are isolated from one another, client applications are given options on what level of integration they want to have with the collision detection system (ref fig). \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert 3 figures of client application integrating with collision detection system) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsubsection{octree\_netclient and octree\_netserver} The octree\_netclient and octree\_netserver services are the glue that enables the collision detection system to distribute over a network of computers. These services mimic the behavior of octree\_slaves and client applications. The purpose of these services is to intercept data and signals from client applications and octree\_slaves and forward them across network connections. The octree\_netclient mimics the behavior of octree\_slave services by implementing the interface the OctreeMaster communicate with. When an OctreeMaster submits a search request to an octree\_netclient, the request and associated data is sent across a network connection to a corresponding octree\_netserver. When an octree\_netserver receives a request from an octree\_netclient, the octree\_netserver mimics the behavior of a client application and submits the search request to the octree\_master service running on that machine. When a search is complete, the process is reversed and resultant data returned from the octree\_netserver back to the octree\_netclient that sent the request. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert block diagram of collision detection system with netclients/servers) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert interaction diagram of collision detection system with netclients/servers) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure} \subsubsection{Bandwidth Utilization} Both the octree\_netclient and octree\_netserver services have the ability to bind themselves to a specific network connection upon initialization. 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 the network. For each network interface, a corresponding octree\_netclient/netserver can be installed effectively allowing transport of data to be distributed over the interfaces. Using octree\_netclients and octree\_netservers in combination with the other services allows a variety of configurations to be constructed that take full advantage of all available resources. \begin{figure} \epsfxsize=4in \vspace{2in} %\centerline{\epsffile{figs/rconst.ps}} (insert diagrams of collision detection configurations) \caption{Run times ($r=20$, $n$ is varied)} \label{fig:fig2} \end{figure}