A Hybrid Software and Hardware System for Collision Detection

Abstract

Collision detection is a fundamental problem in myriad applications, spanning a wide variety of fields. Although the core concept is relatively straightforward, significant complexities result from the demand for interactive or real-time performance for ever-increasing workloads.

In this thesis, a different approach is applied to the problem of collision detection. This approach consists of a hybrid software and hardware system that utilises the properties of both software and hardware to achieve an acceleration over the current state of the art. At its core, the system consists of a custom microarchitecture performing broad phase collision detection, with the narrow phase executing in software. The microarchitecture consists of a plurality of memories internal to the microarchitecture, which parallelise the input data. These data are then formed into pairs using a custom data access algorithm, before being processed using a parallel version of the all-pairs algorithm. Two equivalent microarchitectures are presented: the first is designed for microarchitecture platforms with highly constrained resources, while the second supports many more objects. Both designs are prototyped using a reconfigurable hardware platform known as a field-programmable gate array (FPGA).

Despite the major advantages that can be achieved using this system, a question remains over how to deal with limitations on the size of internal memories in microarchitecture platforms. These limitations would significantly curtail the number of objects that could be processed by the microarchitectures. To answer this question, spatial partitioning is proposed. This partitions the environment into cells of appropriate size for processing by the microarchitecture. After the software reads a potentially colliding set (PCS) from the microarchitecture, narrow phase processing of the objects begins and this processing is overlapped with the microarchitecture?s processing of the subsequent cell.

A framework for benchmarking collision detection algorithms is also presented. This framework is based on a physics engine, in order to accurately reflect scenarios found in many interactive applications, and includes a set of parameters that allow the creation of myriad practical benchmarks from a single generic benchmark. Collision detection algorithm developers can use the benchmark to rapidly determine which scenarios perform inefficiently with their algorithm. In addition, developers of applications utilising collision detection can recreate their scenarios using the benchmark to rapidly find the most efficient algorithm for those scenarios.