Date of Award

Spring 1-1-2013

Document Type


Degree Name

Master of Science (MS)


Computer Science

First Advisor

Willem Schre¨uder

Second Advisor

Ken Anderson

Third Advisor

Roger King


Collision detection is a popular topic in computer graphics. Any physics-based application (e.g. surgical simulations, robotics, video games, computer animations, etc.) necessitates some degree of collision detection and handling. Many techniques exist for performing collision detection. Until recently, the majority of them rely on CPU-based approaches. The increasing accessibilty of general purpose GPU (GPGPU) programming has marshalled in new possibilities for computing collision detection in virtual environments. However, GPGPU programming is certainly not a silver bullet. There are a variety of challenges to recognize and overcome, in particular, as it relates to collision detection. This thesis will explore existing methods for performing collision detection and present a novel GPU-based approach to a common technique - hierarchical grid spatial partitioning.