“Shortest Path to Boundary for Self-Intersecting Meshes” by Chen, Diaz and Yuksel
Conference:
Type(s):
Title:
- Shortest Path to Boundary for Self-Intersecting Meshes
Session/Category Title: Making Contact: Simulating and Detecting Collisions
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We introduce a method for efficiently computing the exact shortest path to the boundary of a mesh from a given internal point in the presence of self-intersections. We provide a formal definition of shortest boundary paths for self-intersecting objects and present a robust algorithm for computing the actual shortest boundary path. The resulting method offers an effective solution for collision and self-collision handling while simulating deformable volumetric objects, using fast simulation techniques that provide no guarantees on collision resolution. Our evaluation includes complex self-collision scenarios with a large number of active contacts, showing that our method can successfully handle them by introducing a relatively minor computational overhead.
References:
1. Jérémie Allard, François Faure, Hadrien Courtecuisse, Florent Falipou, Christian Duriez, and Paul G Kry. 2010. Volume contact constraints at arbitrary resolution. In ACM SIGGRAPH 2010 papers. 1–10.
2. Aytek Aman, Serkan Demirci, and Uğur Güdükbay. 2022. Compact tetrahedralization-based acceleration structures for ray tracing. Journal of Visualization (2022), 1–13.
3. Mukund Balasubramanian, Jonathan R Polimeni, and Eric L Schwartz. 2008. Exact geodesics and shortest paths on polyhedral surfaces. IEEE transactions on pattern analysis and machine intelligence 31, 6 (2008), 1006–1016.
4. David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques. 23–34.
5. Ted Belytschko and Mark O Neal. 1991. Contact-impact by the pinball algorithm with penalty and Lagrangian methods. Internat. J. Numer. Methods Engrg. 31, 3 (1991), 547–572.
6. Jan Bender, Matthias Müller, and Miles Macklin. 2015. Position-Based Simulation Methods in Computer Graphics.. In Eurographics (tutorials). 8.
7. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM transactions on graphics (TOG) 33, 4 (2014), 1–11.
8. Stephen Cameron. 1997. Enhancing GJK: Computing minimum and penetration distances between convex polyhedra. In Proceedings of international conference on robotics and automation, Vol. 4. IEEE, 3112–3117.
9. John Canny. 1986. Collision detection for moving polyhedra. IEEE Transactions on Pattern Analysis and Machine Intelligence 2 (1986), 200–209.
10. Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In Proceedings of the sixth annual symposium on Computational geometry. 360–369.
11. Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A Survey of Algorithms for Geodesic Paths and Distances. arXiv preprint arXiv:2007.10430 (2020).
12. Ounan Ding and Craig Schroeder. 2019. Penalty force for coupling materials with Coulomb friction. IEEE transactions on visualization and computer graphics 26, 7 (2019), 2443–2455.
13. Evan Drumwright. 2007. A fast and stable penalty method for rigid body simulation. IEEE transactions on visualization and computer graphics 14, 1 (2007), 231–240.
14. Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil Ureta, Timothy R Langlois, Chenfanfu Jiang, Denis Zorin, Danny M Kaufman, and Daniele Panozzo. 2021. Intersection-free rigid body dynamics. ACM Trans. Graph. 40, 4 (2021), 183–1.
15. Susan Fisher and Ming C Lin. 2001a. Deformed distance fields for simulation of non-penetrating flexible bodies. In Computer Animation and Simulation 2001. Springer, 99–111.
16. Susan Fisher and Ming C Lin. 2001b. Fast penetration depth estimation for elastic bodies using deformed distance fields. In Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180), Vol. 1. IEEE, 330–336.
17. Marie-Paule Gascuel. 1993. An implicit formulation for precise contact modeling between flexible solids. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques. 313–320.
18. James K Hahn. 1988. Realistic animation of rigid bodies. ACM Siggraph computer graphics 22, 4 (1988), 299–308.
19. Bruno Heidelberger, Matthias Teschner, Richard Keiser, Matthias Müller, and Markus H Gross. 2004. Consistent penetration depth estimation for deformable collision response.. In VMV, Vol. 4. 339–346.
20. Everton Hermann, François Faure, and Bruno Raffin. 2008. Ray-traced collision detection for deformable bodies. In GRAPP 2008-3rd International Conference on Computer Graphics Theory and Applications. INSTICC, 293–299.
21. Gentaro Hirota, Susan Fisher, and Ming Lin. 2000. Simulation of non-penetrating elastic bodies using distance fields. University of North Carolina at Chapel Hill Technical Report: TR00-018. Spring (2000).
22. I Huněk. 1993. On a penalty formulation for contact-impact problems. Computers & structures 48, 2 (1993), 193–203.
23. Changsoo Je, Min Tang, Youngeun Lee, Minkyoung Lee, and Young J Kim. 2012. Poly-Depth: Real-time penetration depth computation using iterative contact-space projection. ACM Transactions on Graphics (TOG) 31, 1 (2012), 1–14.
24. Ladislav Kavan. 2003. Rigid body collision response. Vectors 1000, 2 (2003).
25. Dan Koschier, Crispin Deul, Magnus Brand, and Jan Bender. 2017. An hp-adaptive discretization algorithm for signed distance field generation. IEEE transactions on visualization and computer graphics 23, 10 (2017), 2208–2221.
26. Ares Lagae and Philip Dutré. 2008. Accelerating ray tracing using constrained tetrahe-dralizations. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1303–1312.
27. Lei Lan, Danny M. Kaufman, Minchen Li, Chenfanfu Jiang, and Yin Yang. 2022a. Affine Body Dynamics: Fast, Stable and Intersection-Free Simulation of Stiff Materials. ACM Trans. Graph. 41, 4, Article 67 (jul 2022), 14 pages.
28. Lei Lan, Guanqun Ma, Yin Yang, Changxi Zheng, Minchen Li, and Chenfanfu Jiang. 2022b. Penetration-free projective dynamics on the GPU. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1–16.
29. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M Kaufman. 2020. Incremental potential contact: Intersection-and inversion-free, large-deformation dynamics. ACM transactions on graphics (2020).
30. Yijing Li and Jernej Barbič. 2018. Immersion of self-intersecting solids and surfaces. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–14.
31. Yong-Jin Liu. 2013. Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures. Computer-Aided Design 45, 3 (2013), 695–704.
32. Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Zach Corse. 2020. Local optimization for robust signed distance field collision. Proceedings of the ACM on Computer Graphics and Interactive Techniques 3, 1 (2020), 1–17.
33. Miles Macklin and Matthias Muller. 2021. A Constraint-based Formulation of Stable Neo-Hookean Materials. In Motion, Interaction and Games. 1–7.
34. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proceedings of the 9th International Conference on Motion in Games. 49–54.
35. Maxime Maria, Sébastien Horna, and Lilian Aveneau. 2017. Efficient ray traversal of constrained Delaunay tetrahedralization. In 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017), Vol. 1. 236–243.
36. Gerd Marmitt and Philipp Slusallek. 2006. Fast ray traversal of tetrahedral and hexahedral meshes for direct volume rendering. In Proceedings of the Eighth Joint Eurographics/IEEE VGTC conference on Visualization. 235–242.
37. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. In ACM SIGGRAPH 2011 papers. 1–12.
38. Brian Mirtich and John Canny. 1995. Impulse-based simulation of rigid bodies. In Proceedings of the 1995 symposium on Interactive 3D graphics. 181–ff.
39. Joseph SB Mitchell, David M Mount, and Christos H Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (1987), 647–668.
40. Nathan Mitchell, Mridul Aanjaneya, Rajsekhar Setaluri, and Eftychios Sifakis. 2015. Non-manifold level sets: A multivalued implicit surface representation with applications to self-collision processing. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–9.
41. Matthew Moore and Jane Wilhelms. 1988. Collision detection and response for computer animation. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques. 289–298.
42. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. Journal of Visual Communication and Image Representation 18, 2 (2007), 109–118.
43. Carol O’Sullivan and John Dingliana. 1999. Real-time collision detection and response using sphere-trees. (1999).
44. Steven Parker, Michael Parker, Yarden Livnat, Peter-Pike Sloan, Charles Hansen, and Peter Shirley. 2005. Interactive ray tracing for volume visualization. In ACM SIGGRAPH 2005 Courses. 15–es.
45. John C Platt and Alan H Barr. 1988. Constraints methods for flexible models. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques. 279–288.
46. Stéphane Redon and Ming C. Lin. 2006. A Fast Method for Local Penetration Depth Computation. Journal of Graphics Tools 11 (2006), 37–50.
47. Alper Şahıstan, Serkan Demirci, Nathan Morrical, Stefan Zellmann, Aytek Aman, Ingo Wald, and Uğur Güdükbay. 2021. Ray-traced shell traversal of tetrahedral meshes for direct volume visualization. In 2021 IEEE Visualization Conference (VIS). IEEE, 91–95.
48. Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG) 24, 3 (2005), 553–560.
49. Yun Teng, Miguel A Otaduy, and Theodore Kim. 2014. Simulating articulated subspace self-contact. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–9.
50. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques. 205–214.
51. Mickeal Verschoor and Andrei C Jalba. 2019. Efficient and accurate collision response for elastically deformable models. ACM Transactions on Graphics (TOG) 38, 2 (2019), 1–20.
52. Ingo Wald, Sven Woop, Carsten Benthin, Gregory S Johnson, and Manfred Ernst. 2014. Embree: a kernel framework for efficient CPU ray tracing. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–8.
53. Bin Wang, François Faure, and Dinesh K Pai. 2012. Adaptive image-based intersection volume. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–9.
54. Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection. ACM Transactions on Graphics (TOG) 40, 5 (2021), 1–16.
55. Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Transactions on Graphics (TOG) 28, 4 (2009), 1–8.
56. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).
Additional Images:
