“Immersion of self-intersecting solids and surfaces” by Li and Barbic
Conference:
Type:
Entry Number: 45
Title:
- Immersion of self-intersecting solids and surfaces
Session/Category Title: An Immersion in Computational Geometry
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Self-intersecting, or nearly self-intersecting, meshes are commonly found in 2D and 3D computer graphics practice. Self-intersections occur, for example, in the process of artist manual work, as a by-product of procedural methods for mesh generation, or due to modeling errors introduced by scanning equipment. If the space bounded by such inputs is meshed naively, the resulting mesh joins (“glues”) self-overlapping parts, precluding efficient further modeling and animation of the underlying geometry. Similarly, near self-intersections force the simulation algorithm to employ an unnecessarily detailed mesh to separate the nearly self-intersecting regions. Our work addresses both of these challenges, by giving an algorithm to generate an “un-glued” simulation mesh, of arbitrary user-chosen resolution, that properly accounts for self-intersections and near self-intersections. In order to achieve this result, we study the mathematical concept of immersion, and give a deterministic and constructive algorithm to determine if the input self-intersecting triangle mesh is the boundary of an immersion. For near self-intersections, we give a robust algorithm to properly duplicate mesh elements and correctly embed the underlying geometry into the mesh element copies. Both the self-intersections and near self-intersections are combined into one algorithm that permits successful meshing at arbitrary resolution. Applications of our work include volumetric shape editing, physically based simulation and animation, and volumetric weight and geodesic distance computation on self-intersecting inputs.
References:
1. Marco Attene. 2010. A lightweight approach to repairing digitized polygon meshes. The Visual Computer 26, 11 (2010), 1393–1406. Google ScholarDigital Library
2. Marco Attene. 2014. Direct repair of self-intersecting meshes. Graphical Models 76, 6 (2014), 658–668. Google ScholarDigital Library
3. J. Bærentzen and H. Aanæs. 2005. Signed Distance Computation using the Angle Weighted Pseudo-normal. IEEE Trans. on Visualization and Computer Graphics 11, 3 (2005), 243–253. Google ScholarDigital Library
4. David Baraff, Andrew Witkin, and Michael Kass. 2003. Untangling cloth. In ACM Transactions on Graphics (TOG), Vol. 22. 862–870. Google ScholarDigital Library
5. Jernej Barbič, Yijing Li, Bohan Wang, and Danyong Zhao. 2018. Vega FEM Library 4.0. (2018). http://www.jernejbarbic.com/vega.Google Scholar
6. Marcel Campen and Leif Kobbelt. 2010. Exact and Robust (Self-) Intersections for Polygonal Meshes. In Computer Graphics Forum, Vol. 29. 397–406.Google ScholarCross Ref
7. CGAL. 2018. Computational Geometry Algorithms Library. (2018). http://www.cgal.orgGoogle Scholar
8. Keenan Crane. 2017. 3D Model Repository. (2017). http://www.cs.cmu.edu/~kmcrane/Projects/ModelRepositoryGoogle Scholar
9. David Eppstein and Elena Mumford. 2009. Self-overlapping curves revisited. In Proc. of ACM-SIAM Symp. on Discrete Algorithms. 160–169. Google ScholarDigital Library
10. Jeff Erickson. 2009. Computational Topology; Cell Complexes. In Course Notes, University of Illinois at Urbana-Champaign. http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/cell-complexes.pdfGoogle Scholar
11. Dennis Frisch. 2010. Extending Immersions into the Sphere. arXiv preprint arXiv.1012.4923 (2010).Google Scholar
12. B. Heidelberger, M. Teschner, R. Keiser, M. Müller, and M. H. Gross. 2004. Consistent penetration depth estimation for deformable collision response. In VMV’04. 339–346.Google Scholar
13. F. Hétroy, S. Rey, C. Andújar, P. Brunet, and A. Vinacua. 2011. Mesh repair with user-friendly topology control. Computer-Aided Design 43, 1 (2011), 101–113. Google ScholarDigital Library
14. Zhe Huang, Hongbo Fu, and Rynson WH Lau. 2014. Data-driven segmentation and labeling of freehand sketches. ACM Trans. on Graphics (TOG) 33, 6 (2014), 175. Google ScholarDigital Library
15. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-time Deformation. ACM Trans. Graph. 30, 4 (2011), 78:1–78:8. Google ScholarDigital Library
16. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013a. Robust inside-outside segmentation using generalized winding numbers. ACM Transactions on Graphics (TOG) 32, 4 (2013), 33. Google ScholarDigital Library
17. A Jacobson, D Panozzo, C Schüller, O Diamanti, Q Zhou, N Pietroni, et al. 2013b. libigl: A simple C++ geometry processing library. (2013).Google Scholar
18. Weishi Li. 2011. Detecting Ambiguities in 3D Polygons with Self-Intersecting Projections. In Computer-Aided Design and Computer Graphics CAD/Graphics. 11–16. Google ScholarDigital Library
19. Yijing Li, Hongyi Xu, and Jernej Barbič. 2016. Enriching Triangle Mesh Animations With Physically Based Simulation. IEEE Trans. on Visualization and Computer Graphics (2016).Google Scholar
20. 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), 247. Google ScholarDigital Library
21. N. Molino, Z. Bao, and R. Fedkiw. 2004. A virtual node algorithm for changing mesh topology during simulation. In Proc. of ACM SIGGRAPH 2004. 385–392. Google ScholarDigital Library
22. Neil Molino, Robert Bridson, and Ronald Fedkiw. 2003a. Tetrahedral mesh generation for deformable bodies. In Symposium on Computer Animation (SCA).Google Scholar
23. Neil Molino, Robert Bridson, Joseph Teran, and Ron Fedkiw. 2003b. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In 12th Int. Meshing Roundtable. 103–114.Google Scholar
24. Uddipan Mukherjee. 2014. Self-overlapping curves: Analysis and applications. Computer-Aided Design 46 (2014), 227–232. Google ScholarDigital Library
25. Uddipan Mukherjee and M Gopi. 2012. Tweening boundary curves of non-simple immersions of a disk. In Proc. of Indian Conference on Computer Vision, Graphics and Image Processing. ACM, 36. Google ScholarDigital Library
26. U. Mukherjee, M. Gopi, and J. Rossignac. 2011. Immersion and embedding of self-crossing loops. In Proc. of the Eurographics Symposium on Sketch-Based Interfaces and Modeling. 31–38. Google ScholarDigital Library
27. Matthieu Nesme, Paul G. Kry, Lenka Jeřábková, and François Faure. 2009. Preserving Topology and Elasticity for Embedded Deformable Models. ACM Trans. on Graphics (SIGGRAPH 2009) 28, 3 (2009), 52:1–52:9. Google ScholarDigital Library
28. G. Noris, D. Sỳkora, A. Shamir, S. Coros, B. Whited, M. Simmons, A. Hornung, M. Gross, and R. Sumner. 2012. Smart scribbles for sketch segmentation. In Computer Graphics Forum, Vol. 31. 2516–2527. Google ScholarDigital Library
29. L. Sacht, A. Jacobson, D. Panozzo, C. Schüller, and O. Sorkine-Hornung. 2013. Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces. In Computer Graphics Forum, Vol. 32. 147–156. Google ScholarDigital Library
30. Peter W Shor and Christopher J Van Wyk. 1989. Detecting and decomposing self-overlapping curves. In Proc. of ACM Symp. on Computational geometry. 44–50. Google ScholarDigital Library
31. E. Sifakis. 2007. Algorithmic Aspects of the Simulation and Control of Computer Generated Human Anatomy Models. Ph.D. Dissertation. Stanford University.Google Scholar
32. Eftychios Sifakis, Kevin Der, and Ronald Fedkiw. 2007. Arbitrary Cutting of Deformable Tetrahedralized Objects. In Symp. on Computer Animation (SCA). 73–80. Google ScholarDigital Library
33. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symp. on Geometry processing, Vol. 4. 109–116. Google ScholarDigital Library
34. Ivan Sutherland and Gary Hodgman. 1974. Reentrant Polygon Clipping. Commun. ACM 17 (1974), 32–42. Google ScholarDigital Library
35. J. Teran, E. Sifakis, S. Blemker, V. Ng-Thow-Hing, C. Lau, and R. Fedkiw. 2005. Creating and simulating skeletal muscle from the visible human data set. IEEE Trans. on Visualization and Computer Graphics 11, 3 (2005), 317–328. Google ScholarDigital Library
36. Y. Wang, C. Jiang, C. Schroeder, and J. Teran. 2014. An adaptive virtual node algorithm with robust mesh cutting. In Symposium on Computer Animation (SCA). 77–85. Google ScholarDigital Library
37. Ofir Weber and Denis Zorin. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics (TOG) 33, 4 (2014), 75. Google ScholarDigital Library
38. Chris Wojtan, Nils Thürey, Markus Gross, and Greg Turk. 2009. Deforming meshes that split and merge. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 76. Google ScholarDigital Library
39. Chris Wojtan and Greg Turk. 2008. Fast viscoelastic behavior with thin features. ACM Trans. on Graphics (TOG) 27, 3 (2008), 47. Google ScholarDigital Library
40. K. Xu, K. Chen, H. Fu, W. Sun, and S. Hu. 2013. Sketch2Scene: sketch-based co-retrieval and co-placement of 3D models. ACM Trans. on Graphics (TOG) 32, 4 (2013), 123. Google ScholarDigital Library
41. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 39. Google ScholarDigital Library
