“Air meshes for robust collision handling” by Müller-Fischer, Chentanez, Kim and Macklin

We propose a new method for both collision detection and collision response geared towards handling complex deformable objects in close contact. Our method does not miss collision events between time steps and solves the challenging problem of untangling automatically and robustly. It is conceptually simple and straight forward to parallelize due to the regularity of the algorithm.The main idea is to tessellate the air between objects once before the simulation and by considering one unilateral constraint per element that prevents its inversion during the simulation. If large relative rotations and translations are present in the simulation, an additional dynamic mesh optimization step is needed to prevent mesh locking. This step is fast in 2D and allows the simulation of arbitrary scenes. Because mesh optimization is expensive in 3D, however, the method is best suited for the subclass of 3D scenarios in which relative motions are limited. This subclass contains two important problems, namely the simulation of multi-layered clothing and tissue on animated characters.

1. Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2000. Deformable free space tilings for kinetic collision detection. In International Journal of Robotics Research, 83–96.Google Scholar
2. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4 (July), 82:1–82:10. Google ScholarDigital Library
3. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22, 3 (July), 862–870. Google ScholarDigital Library
4. Barbič, J., and James, D. L. 2010. Subspace self-collision culling. ACM Trans. Graph. 29, 4 (July), 81:1–81:9. Google ScholarDigital Library
5. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (July), 594–603. Google ScholarDigital Library
6. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. 31, 4 (July), 96:1–96:7. Google ScholarDigital Library
7. Civit-Flores, O., and Susn, A. 2014. Robust treatment of degenerate elements in interactive corotational fem simulations. Computer Graphics Forum 33, 6, 298–309.Google ScholarDigital Library
8. Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proceedings of the 2008 symposium on Interactive 3D graphics and games, ACM, New York, NY, USA, I3D ’08, 61–69. Google ScholarDigital Library
9. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’08, 155–162. Google ScholarDigital Library
10. Freitag, L. A., and Ollivier-Gooch, C. 1997. Tetrahedral mesh improvement using swapping and smoothing. International Journal for Numerical Methods in Engineering 40, 21, 3979–4002.Google ScholarCross Ref
11. Govindaraju, N. K., Redon, S., Lin, M. C., and Manocha, D. 2003. Cullide: Interactive collision detection between complex models in large environments using graphics hardware. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, HWWS ’03, 25–32. Google ScholarDigital Library
12. Govindaraju, N. K., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M. C., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24, 3 (July), 991–999. Google ScholarDigital Library
13. Grimm, J., and Grimm, W. 1812. Town musicians of bremen. In Grimm’s Fairy Tales, vol. KHM 27.Google Scholar
14. Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. In Proceedings of Computer Graphics, Visualization and Computer Vision, 145–152.Google Scholar
15. Hutter, M., and Fuhrmann, A. 2007. Optimized continuous collision detection for deformable triangle meshes. Journal of WSCG 15, 1-3, 25–32.Google Scholar
16. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. Proc. of the ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 131–140. Google ScholarDigital Library
17. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
18. Klingner, B. M., and Shewchuk, J. R. 2007. Agressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable, 3–23.Google Scholar
19. Levin, D. I. W., Litven, J., Jones, G. L., Sueda, S., and Pai, D. K. 2011. Eulerian solid simulation with contact. In ACM SIGGRAPH 2011 Papers, ACM, New York, NY, USA, SIGGRAPH ’11, 36:1–36:10. Google ScholarDigital Library
20. Macklin, M., Müller, M., Chentanez, N., and Kim, T.-Y. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4 (July), 153:1–153:12. Google ScholarDigital Library
21. Mezger, J., Kimmerle, S., and Etzmus, O. 2003. Hierarchical techniques in collision detection for cloth animation. Journal of WSCG 11, 1–3.Google Scholar
22. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface 2004, Canadian Human-Computer Communications Society, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, GI ’04, 239–246. Google ScholarDigital Library
23. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. In ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, SIGGRAPH ’05, 471–478. Google ScholarDigital Library
24. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2 (Apr.), 109–118. Google ScholarDigital Library
25. Pagano, S., and Alart, P. 2008. Self-contact and fictitious domain using a difference convex approach. International Journal for Numerical Methods in Engineering 75, 1 (July), 29–42.Google ScholarCross Ref
26. Prez-Urbiola, R. E., and Rudomin, G. I. 1999. Multi-layer implicit garment models. In Shape Modeling International Proceedings, 66–71. Google ScholarDigital Library
27. Schvartzman, S. C., Gascón, J., and Otaduy, M. A. 2009. Bounded normal trees for reduced deformations of triangulated surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’09, 75–82. Google ScholarDigital Library
28. Schvartzman, S. C., Pérez, L. G., and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH) 29, 3. Google ScholarDigital Library
29. Selle, A., Su, J., Irving, G., and Fedkiw, R. 2008. Robust high-resolution cloth using parallelism, history-based collisions and accurate friction. IEEE Transactions on Visualization and Computer Graphics, (TVCG) 15, 2, 339–350. Google ScholarDigital Library
30. Shewchuk, J. R. 2002. Two discrete optimization algorithms for the topological improvement of tetrahedral meshes. Manuscript.Google Scholar
31. Si, H. 2015. Tetgen, a delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. 41, 2 (Feb.), 11:1–11:36. Google ScholarDigital Library
32. Sifakis, E., Marino, S., and Teran, J. 2008. Globally coupled collision handling using volume preserving impulses. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’08, 147–153. Google ScholarDigital Library
33. Stomakhin, A., Howes, R., Schroeder, C., and Teran, J. M. 2012. Energetically consistent invertible elasticity. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’12, 25–32. Google ScholarDigital Library
34. Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2008. Interactive continuous collision detection between deformable models using connectivity-based culling. In SPM ’08: Proceedings of the 2008 ACM symposium on Solid and physical modeling, ACM, New York, NY, USA, 25–36. Google ScholarDigital Library
35. Tang, M., Manocha, D., and Tong, R. 2010. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, I3D ’10, 7–13. Google ScholarDigital Library
36. Tang, M., Manocha, D., Yoon, S.-E., Du, P., Heo, J.-P., and Tong, R.-F. 2011. Volccd: Fast continuous collision culling between deforming volume meshes. ACM Trans. Graph. 30, 5 (Oct.), 111:1–111:15. Google ScholarDigital Library
37. Tang, M., Tong, R., Wang, Z., and Manocha, D. 2014. Fast and exact continuous collision detection with bernstein sign classification. ACM Trans. Graph. 33 (November), 186:1–186:8. Google ScholarDigital Library
38. Teschner, M., Heidelberger, B., Mueller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. 47–54.Google Scholar
39. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., and Raghupathi, R. 2005. Collision detection for deformable objects. Computer Graphics Forum 24, 1, 61–81.Google ScholarCross Ref
40. Volino, P., and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. In ACM SIGGRAPH 2006 Papers, SIGGRAPH ’06, 1154–1159. Google ScholarDigital Library
41. Wang, B., Faure, F., and Pai, D. K. 2012. Adaptive image-based intersection volume. ACM Trans. Graph. 31, 4 (July), 97:1–97:9. Google ScholarDigital Library
42. Wang, H. 2014. Defending continuous collision detection against errors. ACM Trans. Graph. 33, 4 (July), 122:1–122:10. Google ScholarDigital Library
43. Wicke, M., Lanker, H., and Gross, M. 2006. Untangling cloth with boundaries. In Proceedings of VMV, 349–356.Google Scholar
44. Wicke, M., Ritchie, D., Klingner, B. M., Burke, S., Shewchuk, J. R., and O’Brien, J. F. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. 29, 4 (July), 49:1–49:11. Google ScholarDigital Library
45. Wong, S.-K., and Cheng, Y.-C. 2014. Gpu-based radial view-based culling for continuous self-collision detection of deformable surfaces. The Visual Computer, 1–15.Google Scholar
46. Wong, W. S.-K., Baciu, G., and Hu, J. 2004. Multi-layered deformable surfaces for virtual clothing. In Proceedings of the ACM symposium on Virtual reality software and technology, ACM, New York, NY, USA, VRST ’04, 24–31. Google ScholarDigital Library
47. Wong, S.-K., Liu, C.-M., Baciu, G., and Yeh, C.-C. 2010. Robust continuous collision detection for deformable objects. In Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology, ACM, New York, NY, USA, VRST ’10, 55–62. Google ScholarDigital Library
48. Wong, S.-K., Lin, W.-C., Hung, C.-H., Huang, Y.-J., and Lii, S.-Y. 2013. Radial view based culling for continuous self-collision detection of skeletal models. ACM Trans. Graph. 32, 4 (July), 114:1–114:10. Google ScholarDigital Library
49. Wong, S.-K., Lin, W.-C., Wang, Y.-S., Hung, C.-H., and Huang, Y.-J. 2014. Dynamic radial view based culling for continuous self-collision detection. In Proceedings of the 18th Meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, I3D ’14, 39–46. Google ScholarDigital Library
50. Yoon, S.-E., Kim, Y. J., Harada, T., Kim, Y. J., and Yoon, S.-E. 2010. Recent advances in real-time collision and proximity computations for games and simulations. In ACM SIGGRAPH ASIA 2010 Courses, ACM, New York, NY, USA, SA ’10, 22:1–22:110. Google ScholarDigital Library
51. Zhang, X., and Kim, Y. 2012. Simple culling methods for continuous collision detection of deforming triangles. IEEE Transactions on Visualization and Computer Graphics 18, 7, 1146–1155. Google ScholarDigital Library
52. Zheng, C., and James, D. L. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Trans. Graph. 31, 4 (July), 98:1–98:12. Google ScholarDigital Library