Space-efficient FPGA-accelerated collision detection for virtual prototyping

ABSTRACT

We present a space-efficient, FPGA-optimized architecture to detect collisions among virtual objects. The design consists of two main modules, one for traversing a hierarchical acceleration data structure, and one for intersecting triangles. This paper focuses on the former.The design is based on a novel algorithm for testing discretely oriented polytopes for overlap in 3D space. In addition, we derive a new overlap test algorithm that can be implemented using fixed-point arithmetic without producing false negatives and with bounded error.SystemC simulation results on different levels of abstraction show that real-time collision detection of complex objects at rates required by force-feedback and physically-based simulations can be obtained. In addition, synthesis results show that the design can still be fitted into a six-million gates FPGA. Furthermore, we compare our FPGA-based design with a fully parallelized ASIC-targeted architecture and a software implementation.

REFERENCES

• 1: Ageia. White paper, May 2005.
• 2: G. Baciu, W. S.-K. Wong, and H. Sun. RECODE: an image-based collision detection algorithm. The Journal of Visualization and Computer Animation, 10(4):181--192, October - December 1999. ISSN 1049-8907.
• 3: J. Eckstein and E. Schömer. Dynamic collision detection in virtual reality applications. In WSCG'99, pages 71--78, Plzen, Czech Republic, Feb. 1999. University of West Bohemia.
• 4: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 5: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 6: A. Gress and G. Zachmann. Object-space interference detection on programmable graphics hardware. In M. L. Lucian and M. Neamtu, editors, SIAM Conf. on Geometric Design and Computing, pages 311--328, Seattle, Washington, Nov.13--17 2003. Nashboro Press.
• 7: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717 ]
• 8: D. Knott and D. K. Pai. CInDeR: Collision and interference detection in real-time using graphics hardware. In Proc. of Graphics Interface, Halifax, Nova Scotia, Canada, June11--13 2003.
• 9: K. Myszkowski, O. G. Okunev, and T. L. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9):497--512, 1995. ISSN 0178-2789.
• 10: Andreas Raabe , Blazej Bartyzel , Joachim K. Anlauf , Gabriel Zachmann, Hardware Accelerated Collision Detection - An Architecture and Simulation Results, Proceedings of the conference on Design, Automation and Test in Europe, p.130-135, March 07-11, 2005 [doi>10.1109/DATE.2005.167]
• 11: G. J. A. van den Bergen. Collision Detection in Interactive 3D Computer Animation. PhD dissertation, Eindhoven University of Technology, 1999.
• 12: G. Zachmann, Rapid Collision Detection by Dynamically Aligned DOP-Trees, Proceedings of the Virtual Reality Annual International Symposium, p.90, March 14-18, 1998
• 13: G. Zachmann and G. Knittel. An architecture for hierarchical collision detection. In Journal of WSCG '2003, pages 149--156, University of West Bohemia, Plzen, Czech Republic, Feb.3--7 2003.
• 14: G. Zachmann and G. Knittel. High-performance collision detection hardware. Technical Report CG-2003-3, University Bonn, Informatik II, Bonn, Germany, Aug. 2003.