Precise generalized contact point and normal determination for rigid body simulation

ABSTRACT

Modeling contact for rigid body simulation requires accurate determination of time of contact, contact points, and contact normals. Existing collision detection methods for rigid body simulation can be grouped into one of three categories: convexity-based discrete methods, a posteriori discrete methods, and continuous methods. Our proposed method combines the advantages of all three types: operating on arbitrary geometric representations, running in asymptotic linear time in the number of polyhedral features, having a parameterizable precision (a variation is guaranteed to miss no collisions), and avoiding simplex/simplex tests that are difficult to implement robustly. The algorithm is demonstrated on a pathological example involving both polyhedra and polygon soups.

REFERENCES

• 1: S. Cameron. Enhancing GJK: Computing minimum and penetration distances between convex polyhedra. In Proc. of the IEEE Intl. Conf. on Robotics and Automation, Albuquerque, NM, USA, April 1997.
• 2: J Canny, Collision detection vkr moving polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.200-209, March 1986 [doi>10.1109/TPAMI.1986.4767773]
• 3: N. Chakraborty, S. Berard, S. Akella, and J. Trinkle. An implicit time-stepping method for multibody systems with intermittent contact. In Proc. of Robotics: Science and Systems, 2007.
• 4: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 5: E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J. of Robotics and Automation, 4(2):193--203, April 1988.
• 6: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 8: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.289-298, June 1988
• 9: S. Redon, A. Kheddar, and S. Coquillart. Fast continuous collision detection between rigid bodies. In Proc. of Eurographics (Computer Graphics Forum), 2002.
• 10: J. M. Singh and P. Narayanan. Real-time ray tracing of implicit surfaces on the gpu. Technical Report IIIT/TR/2007/72, Intl. Inst. of Information Technology, July 2007.
• 11: K. Yamane and Y. Nakamura. Stable penalty-based model of frictional contacts. In Proc. of the IEEE Intl. Conf. on Robotics and Automation (ICRA), Orlando, FL, USA, May 2006.
• 12: Xinyu Zhang , Minkyoung Lee , Young J. Kim, Interactive continuous collision detection for non-convex polyhedra, The Visual Computer: International Journal of Computer Graphics, v.22 n.9, p.749-760, September 2006 [doi>10.1007/s00371-006-0060-0]