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

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.