“Continuous collision detection for articulated models using Taylor models and temporal culling” by Zhang, Redon, Lee and Kim

We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as collision witness features. We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated-body dynamics and character motion planning. Our algorithm can perform CCDs including self-collision detection for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.

1. Abdel-Malek, K., Blackmore, D., and Joy, K. 2002. Swept volumes: foundations, perspectives, and applications. International Journal of Shape Modeling.Google Scholar
2. Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2001. Deformable free space tiling for kinetic collision detection. In Workshop on Algorithmic Foundations of Robotics, 83–96.Google Scholar
3. Ageia. 2006. PhysX. http://www.ageia.com.Google Scholar
4. Baraff, D., and Witkin, A. 2001. Physically-based modeling. ACM SIGGRAPH Course Notes.Google Scholar
5. Barequet, G., and Har-Peled, S. 2001. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38, 91–109. Google ScholarDigital Library
6. Berz, B., and Hofstätter, G. 1998. Computation and application of Taylor polynomials with interval remainder bounds. Reliable Computing 4, 83.Google ScholarCross Ref
7. Bühler, K., Dyllong, E., and Luther, W. 2004. Reliable distance and intersection computation using finite precision geometry. Lecture Notes in Computer Science 2991, 160–190.Google ScholarCross Ref
8. Canny, J. F. 1986. Collision detection for moving polyhedra. IEEE Trans. PAMI 8, 200–209. Google ScholarDigital Library
9. Choi, Y.-K., Wang, W., Liu, Y., and Kim, M.-S. 2006. Continuous collision detection for elliptic disks. IEEE Transactions on Robotics 22, 2. Google ScholarDigital Library
10. Comba, J. L. D., and Stolfi, J. 1993. Affine arithmetic and its applications to computer graphics. In Proceedings of the VI Sibgrapi. Recife, Brazil.Google Scholar
11. Coumans, E. 2006. Bullet Physics library. http://www.continuousphysics.com.Google Scholar
12. Craig, J. J. 1989. Introduction to Robotics: Mechanics and Control. Prentice Hall. Google ScholarDigital Library
13. Ehmann, S., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics ‘2001) 20, 3, 500–510.Google Scholar
14. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. In SIGGRAPH 96 Conference Proceedings, Annual Conference Series, 171–180. Google ScholarDigital Library
15. Havok. 2006. Havok Physics. http://www.havok.com.Google Scholar
16. Hubbard, P. M. 1993. Space-time bounds for collision detection. Technical report cs-93-04, Dept. of Computer Science, Brown University, Feb. Google ScholarDigital Library
17. Kim, B., and Rossignac, J. 2003. Collision prediction for polyhedra under screw motions. In ACM Conference on Solid Modeling and Applications. Google ScholarDigital Library
18. Kim, D., Guibas, L., and Shin, S. 1998. Fast collision detection among multiple moving spheres. IEEE Trans. Vis. Comput. Graph. 4, 3, 230–242. Google ScholarDigital Library
19. Kirkpatrick, D., Snoeyink, J., and Speckmann, B. 2000. Kinetic collision detection for simple polygons. In Proc. of ACM Symposium on Computational Geometry, 322–330. Google ScholarDigital Library
20. Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 1999. Fast proximity queries with swept sphere volumes. Tech. Rep. TR99-018, Department of Computer Science, University of North Carolina.Google Scholar
21. Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
22. Lin, M. C. 1993. Efficient Collision Detection for Animation and Robotics. PhD thesis, University of California, Berkeley, CA. Google ScholarDigital Library
23. Mirtich, B. V. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. PhD thesis, University of California, Berkeley. Google ScholarDigital Library
24. Mirtich, B. 2000. Timewarp rigid body simulation. SIGGRAPH Conference Proceedings, 193–200. Google ScholarDigital Library
25. Moore, R. E. 1979. Methods and Applications of Interval Analysis. SIAM, Philadelphia. ISBN 0-89871-161-4. Google ScholarDigital Library
26. MPK-Team. 2006. Motion Planning Kit. http://ai.stanford.edu/~mitul/mpk/.Google Scholar
27. Neumaier, A. 1993. The wrapping effect, ellipsoid arithmetic, stability and confidence regions. Computing Supplementum 9, 175–190.Google ScholarCross Ref
28. Ortega, M., Redon, S., and Coquillart, S. 2006. A six degree-of-freedom god-object method for haptic display of rigid bodies. In IEEE International Conference on Virtual Reality. Google ScholarDigital Library
29. Redon, S., and Lin, M. C. 2005. Practical local planning in the contact space. In Proceedings of IEEE International Conference on Robotics and Automation, 4200–4205.Google Scholar
30. Redon, S., Kheddar, A., and Coquillart, S. 2000. An algebraic solution to the problem of collision detection for rigid polyhedral objects. Proc. of IEEE Conference on Robotics and Automation.Google Scholar
31. Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum).Google Scholar
32. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Interactive and continuous collision detection for avatars in virtual environments. In Proceedings of IEEE Virtual Reality. Google ScholarCross Ref
33. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Fast continuous collision detection for articulated models. In Proceedings of ACM Symposium on Solid Modeling and Applications. Google ScholarDigital Library
34. Schwarzer, F., Saha, M., and Latombe, J.-C. 2002. Exact collision checking of robot paths. In Workshop on Algorithmic Foundations of Robotics (WAFR).Google Scholar
35. Spong, M. W., Hutchinson, S., and Vidyasagar, M. 2005. Robot Modeling and Control. Wiley.Google Scholar
36. van den Bergen, G. 2004. Ray casting against general convex objects with application to continuous collision detection. Journal of Graphics Tools.Google Scholar
37. Zhang, X. Y., and Kim, Y. J. 2007. Motion interpolation and bounds calculations in CATCH. Tech. Rep. CSE-TR-2007-01, Ewha Womans University, Seoul, Korea.Google Scholar
38. Zhang, X. Y., Lee, M. K., and Kim, Y. J. 2006. Interactive continuous collision detection for rigid non-convex polyhedra. The Visual Computer (Proceedings of Pacific Graphics 2006) 22, 9–11. Google ScholarDigital Library