research-article

Open access

Shortest Path to Boundary for Self-Intersecting Meshes

Authors:

Cem YukselAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 42, Issue 4

Article No.: 146, Pages 1 - 15

https://doi.org/10.1145/3592136

Published: 26 July 2023 Publication History

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.

Supplementary Material

ZIP File (papers_373-supplemental.zip)

supplemental material.

Download
699.26 MB

MP4 File (papers_373_VOD.mp4)

presentation

Download
173.87 MB

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In Proceedings of the sixth annual symposium on Computational geometry. 360--369.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[30]

Yijing Li and Jernej Barbič. 2018. Immersion of self-intersecting solids and surfaces. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1--14.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[39]

Joseph SB Mitchell, David M Mount, and Christos H Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (1987), 647--668.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[56]

Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).

Cited By

Qian FZou YXu MZhang XZhang CXu CChen H(2024)A Comprehensive Understanding of the Impact of Data Augmentation on the Transferability of 3D Adversarial ExamplesACM Transactions on Knowledge Discovery from Data10.1145/3673232Online publication date: 15-Jun-2024
https://dl.acm.org/doi/10.1145/3673232
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Liu JHu WYang ZChen JWang GChen XCai YGao HZhao H(2024)Rip-NeRF: Anti-aliasing Radiance Fields with Ripmap-Encoded Platonic SolidsACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657402(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657402
Show More Cited By

Index Terms

Shortest Path to Boundary for Self-Intersecting Meshes
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Collision detection
      2. Physical simulation

Recommendations

A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Shortest paths in simple polygons with polygon-meet constraints

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the ...
Complexity of some inverse shortest path lengths problems

The input to an inverse shortest path lengths problem (ISPL) consists of a graph G with arc weights, and a collection of source-sink pairs with prescribed distances that do not necessarily conform to the shortest path lengths in G. The goal is to modify ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 42, Issue 4

August 2023

1912 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3609020

Issue’s Table of Contents

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2023

Published in TOG Volume 42, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
497
Total Downloads

Downloads (Last 12 months)442
Downloads (Last 6 weeks)40

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qian FZou YXu MZhang XZhang CXu CChen H(2024)A Comprehensive Understanding of the Impact of Data Augmentation on the Transferability of 3D Adversarial ExamplesACM Transactions on Knowledge Discovery from Data10.1145/3673232Online publication date: 15-Jun-2024
https://dl.acm.org/doi/10.1145/3673232
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Liu JHu WYang ZChen JWang GChen XCai YGao HZhao H(2024)Rip-NeRF: Anti-aliasing Radiance Fields with Ripmap-Encoded Platonic SolidsACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657402(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657402
Cui JXu GLiu JFeng SWang JPeng HFu SZheng ZZheng XLiu S(2024)ID-SR: Privacy-Preserving Social Recommendation Based on Infinite Divisibility for Trustworthy AIACM Transactions on Knowledge Discovery from Data10.1145/363941218:7(1-25)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3639412
Dayanandan KLall B(2024)Enabling Multi-modal Conversational Interface for Clinical ImagingExtended Abstracts of the 2024 CHI Conference on Human Factors in Computing Systems10.1145/3613905.3650805(1-13)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3613905.3650805

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents