Efficient geometrically exact continuous collision detection

Abstract

Continuous collision detection (CCD) between deforming triangle mesh elements in 3D is a critical tool for many applications. The standard method involving a cubic polynomial solver is vulnerable to rounding error, requiring the use of ad hoc tolerances, and nevertheless is particularly fragile in (near-)planar cases. Even with per-simulation tuning, it may still cause problems by missing collisions or erroneously flagging non-collisions. We present a geometrically exact alternative guaranteed to produce the correct Boolean result (significant collision or not) as if calculated with exact arithmetic, even in degenerate scenarios. Our critical insight is that only the parity of the number of collisions is needed for robust simulation, and this parity can be calculated with simpler non-constructive predicates. In essence we analyze the roots of the nonlinear system of equations defining CCD through careful consideration of the boundary of the parameter domain. The use of new conservative culling and interval filters allows typical simulations to run as fast as with the non-robust version, but without need for tuning or worries about failure cases even in geometrically degenerate scenarios. We demonstrate the effectiveness of geometrically exact detection with a novel adaptive cloth simulation, the first to guarantee to remain intersection-free despite frequent curvature-driven remeshing.

References

1. Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A finite element method for animating large viscoplas-tic flow. ACM Trans. Graph. (Proc. SIGGRAPH) 26, 3.
2. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (Proc. SIGGRAPH) 21, 3, 594--603.
3. Brochu, T., and Bridson, R. 2009. Numerically robust continuous collision detection for dynamic explicit surfaces. Tech. Rep. TR-2009-03, University of British Columbia.
4. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472--2493.
5. Brönnimann, H., Burnikel, C., and Pion, S. 2001. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics 109, 25--47.
6. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
7. Dekker, T. J. 1971. A floating-point technique for extending the available precision. Numerische Mathematik 18, 224--242. 10.1007/BF01397083.
8. Ericson, C. 2004. Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
9. Etzmuss, O., Keckeisen, M., and Strasser, W. 2003. A fast finite element solution for cloth modelling. In Proc. 11th Pacific Conference on Computer Graphics and Applications, 244--251.
10. Goualard, F. 2010. Fast and correct SIMD algorithms for interval arithmetic. In Proceedings of PARA '08, Springer, Trondheim, Lecture Notes in Computer Science. 10 pages.
11. Guigue, P., and Devillers, O. 2003. Fast ray-triangle intersection test using orientation predicates. Journal of Graphics Tools 8, 1, addendum.
12. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. (Proc. SIGGRAPH) 27, 3, 1--4.
13. Lambov, B. 2006. Interval arithmetic using SSE-2. In Reliable Implementation of Real Number Algorithms: Theory and Practice, P. Hertling, C. M. Hoffmann, W. Luther, and N. Revol, Eds., vol. 5045 of Lecture Notes in Computer Science, 102--113.
14. Li, L., and Volkov, V. 2005. Cloth animation with adaptively refined meshes. In Proc. 28th Australasian Conference on Computer Science - Volume 38, Australian Computer Society, Inc., Darlinghurst, Australia, Australia, ACSC '05, 107--113.
15. O'Regan, D., Je Cho, Y., and Chen, Y.-Q. 2006. Topological Degree Theory and Applications. Chapman and Hall/CRC.
16. Priest, D. M. 1991. Algorithms for arbitrary precision floating point arithmetic. In Proceedings of the 10th Symposium on Computer Arithmetic, IEEE Computer Society Press, 132--145.
17. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177--89.
18. Ramsey, S. D., Potter, K., and Hansen, C. 2004. Ray bilinear patch intersections. Journal of Graphics Tools 9, 3, 41--47.
19. Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. ACM Trans. Graph. (Proc. SIGGRAPH) 27, 64:1--64:11.
20. Shewchuk, J. R. 1996. Robust adaptive floating-point geometric predicates. In Proceedings of the Twelfth Annual Symposium on Computational Geometry, Association for Computing Machinery, 141--150.
21. Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In IEEE CADCG, 1--11.
22. Tang, M., Kim, Y. J., and Manocha, D. 2010. Continuous collision detection for non-rigid contact computations using local advancement. Proc. Int'l. Conf. Robotics and Automation.
23. Tang, M., Manocha, D., and Tong, R. 2010. Fast continuous collision detection using deforming non-penetration filters. In Proc. ACM SIGGRAPH Symp. Interactive 3D Graphics and Games, 7--13.
24. Villard, J., and Borouchaki, H. 2005. Adaptive meshing for cloth animation. Eng. with Comput. 20 (August), 333--341.
25. Wicke, M., Ritchie, D., Klingner, B., Burke, S., Shewchuk, J., and O'Brien, J. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graphics (Proc. SIGGRAPH) 29, 3.
26. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. In ACM Trans. Graphics (Proc. SIGGRAPH), 47.
27. Yap, C. 2004. Robust geometric computation. In CRC Handbook of Computational and Discrete Geometry, J. E. Goodman and J. O'Rourke, Eds., 2 ed. CRC Press LLC, ch. 41.
28. Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007. Continuous collision detection for articulated models using Taylor models and temporal culling. ACM Trans. Graph. (Proc. SIGGRAPH) 26, 3, 15.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology