The University of Dublin | Trinity College -- Ollscoil Átha Cliath | Coláiste na Tríonóide
Trinity's Access to Research Archive
Home :: Log In :: Submit :: Alerts ::

School of Computer Science and Statistics >
Computer Science >
Computer Science (Theses and Dissertations) >

Please use this identifier to cite or link to this item:

Title: A Hybrid Software and Hardware System for Collision Detection
Author: Woulfe, Muiris
Advisor: Manzke, Michael
Author's Homepage:
Keywords: Collision detection
Broad phase
Spatial partitioning
Field-programmable gate array (FPGA)
Computer graphics
Issue Date: 2010
Publisher: University of Dublin, Trinity College
Citation: Muiris Woulfe, A Hybrid Software and Hardware System for Collision Detection, University of Dublin, Trinity College, 2010
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.
Description: PUBLISHED
Appears in Collections:Computer Science (Theses and Dissertations)

Files in This Item:

File Description SizeFormat
A Hybrid Software and Hardware System for Collision Detection.pdfPublished63.24 MBAdobe PDFView/Open

This item is protected by original copyright

Please note: There is a known bug in some browsers that causes an error when a user tries to view large pdf file within the browser window. If you receive the message "The file is damaged and could not be repaired", please try one of the solutions linked below based on the browser you are using.

Items in TARA are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback