“Efficient geometrically exact continuous collision detection” by Brochu, Edwards and Bridson

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.

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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
4. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472–2493. Google ScholarDigital Library
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. Google ScholarDigital Library
6. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
7. Dekker, T. J. 1971. A floating-point technique for extending the available precision. Numerische Mathematik 18, 224–242. 10.1007/BF01397083.Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
11. Guigue, P., and Devillers, O. 2003. Fast ray-triangle intersection test using orientation predicates. Journal of Graphics Tools 8, 1, addendum.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
15. O’Regan, D., Je Cho, Y., and Chen, Y.-Q. 2006. Topological Degree Theory and Applications. Chapman and Hall/CRC.Google Scholar
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.Google ScholarCross Ref
17. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177–89.Google Scholar
18. Ramsey, S. D., Potter, K., and Hansen, C. 2004. Ray bilinear patch intersections. Journal of Graphics Tools 9, 3, 41–47.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
21. Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In IEEE CADCG, 1–11.Google Scholar
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.Google Scholar
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. Google ScholarDigital Library
24. Villard, J., and Borouchaki, H. 2005. Adaptive meshing for cloth animation. Eng. with Comput. 20 (August), 333–341. Google ScholarDigital Library
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. Google ScholarDigital Library
26. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. In ACM Trans. Graphics (Proc. SIGGRAPH), 47. Google ScholarDigital Library
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.Google Scholar
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. Google ScholarDigital Library