Title | ||
---|---|---|
An Interior Point Optimization Solver for Real Time Inter-frame Collision Detection: Exploring Resource-Accuracy-Platform Tradeoffs |
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 11× speedup over the GPGPU implementation. With object resolutions greater than 242 vertices, our GPGPU implementation outperforms our FPGA implementations. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/FPL.2010.31 | Field Programmable Logic and Applications |
Keywords | Field | DocType |
computer graphic equipment,coprocessors,field programmable gate arrays,fixed point arithmetic,floating point arithmetic,linear programming,logic design,parallel architectures,real-time systems,FPGA,GPGPU,affine interior-point algorithm,interior point optimization solver,object resolution,real time inter-frame collision detection,resource-accuracy-platform tradeoffs,single precision floating point,CUDA,Collision detection,FPGA,GPGPU,Linear Programming | Single-precision floating-point format,Algorithm design,Collision detection,Fixed-point arithmetic,Computer science,CUDA,Floating point,Parallel computing,Real-time computing,Inter frame,General-purpose computing on graphics processing units | Conference |
ISSN | ISBN | Citations |
1946-1488 | 978-1-4244-7842-2 | 4 |
PageRank | References | Authors |
0.63 | 14 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Brian Leung | 1 | 4 | 0.63 |
Chih-Hung Wu | 2 | 9 | 1.13 |
Seda Öǧrenci Memik | 3 | 488 | 42.57 |
Sanjay Mehrotra | 4 | 521 | 77.18 |