An interior point optimization solver for real time inter-frame collision detection: Exploring resource-accuracy-platform tradeoffs

Brian Leung*, Chih Hung Wu, Seda Ogrenci Memik, Sanjay Mehrotra

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We present and compare implementations of an affine interior-point algorithm for real-time collision detection on a GPGPU and an FPGA. This particular interior-point algorithm is distinguished from other collision detection methods by its ability to perform detection between pairs of objects undergoing fast rotational and translational movement. This enables inter-frame collision detection, i.e. collision that might occur during the transition from one frame to another. In our design for the FPGA, we implemented the algorithm both in single-precision floating point and 32-bit fixed point and analyzed the trade-off between resource usage, data accuracy/precision, and system efficiency. Then, we compare them to a floating point implementation on a GPGPU using CUDA. With an object resolution of 45 vertices (45 vertices representing each polyhedral object), our FPGA implementation processes 1562 frames/sec for floating point and 1350 frames/second for fixed point and offers an 11x speedup over the GPGPU implementation. With object resolutions greater than 242 vertices, our GPGPU implementation outperforms our FPGA implementations.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 International Conference on Field Programmable Logic and Applications, FPL 2010
Pages113-118
Number of pages6
DOIs
StatePublished - 2010
Event20th International Conference on Field Programmable Logic and Applications, FPL 2010 - Milano, Italy
Duration: Aug 31 2010Sep 2 2010

Publication series

NameProceedings - 2010 International Conference on Field Programmable Logic and Applications, FPL 2010

Other

Other20th International Conference on Field Programmable Logic and Applications, FPL 2010
Country/TerritoryItaly
CityMilano
Period8/31/109/2/10

Keywords

  • CUDA
  • Collision detection
  • FPGA
  • GPGPU
  • Linear Programming

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'An interior point optimization solver for real time inter-frame collision detection: Exploring resource-accuracy-platform tradeoffs'. Together they form a unique fingerprint.

Cite this