“Multi-material Mesh-based Surface Tracking With Implicit Topology Changes” by Heiss-Synak, Kalinov, Strugaru, Etemadi and Wojtan
Conference:
Type(s):
Title:
- Multi-material Mesh-based Surface Tracking With Implicit Topology Changes
Presenter(s)/Author(s):
Abstract:
We introduce a multi-material, non-manifold mesh-based surface tracking algorithm that converts self-intersections into topological changes. Our algorithm preserves surface features like mesh-based methods and robustly handles topological changes like level set methods. We demonstrate the effectiveness of the approach on complex soap film simulations with thousands of interacting bubbles.
References:
[1]
Adam W Bargteil, Tolga G Goktekin, James F O’Brien, and John A Strain. 2006. A Semi-Lagrangian Contouring Method for Fluid Simulation. ACM Trans. Graph. 25, 1 (2006).
[2]
Gavin Barill, Neil G. Dickson, Ryan Schmidt, David I. W. Levin, and Alec Jacobson. 2018. Fast Winding Numbers for Soups and Clouds. ACM Trans. Graph. 37, 4 (2018), 43:1–43:12.
[3]
Gilbert Louis Bernstein and Chris Wojtan. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.
[4]
Stephan Bischoff and Leif Kobbelt. 2005. Structure preserving CAD model repair. In Computer Graphics Forum, Vol. 24. Amsterdam: North Holland, 1982-, 527–536.
[5]
Wurigen Bo, Xingtao Liu, James Glimm, and Xiaolin Li. 2011. A Robust Front Tracking Method: Verification and Application to Simulation of the Primary Breakup of a Liquid Jet. SIAM J. Sci. Comput. 33, 4 (2011), 1505–1524.
[6]
Kenneth A Brakke. 1992. The surface evolver. Experimental mathematics 1, 2 (1992), 141–165.
[7]
Tyson Brochu and Robert Bridson. 2009. Robust Topological Operations for Dynamic Explicit Surfaces. SIAM J. Sci. Comput. 31, 4 (2009), 2472–2493.
[8]
Paul Burchard, Li-Tien Cheng, Barry Merriman, and Stanley Osher. 2001. Motion of curves in three spatial dimensions using a level set approach. J. Comput. Phys. 170, 2 (2001), 720–741.
[9]
Nuttapong Chentanez, Matthias M?ller, and Miles Macklin. 2016. GPU Accelerated Grid-Free Surface Tracking. Computers & Graphics 57, C (2016), 1–11.
[10]
Nuttapong Chentanez, Matthias M?ller, Miles Macklin, and Tae-Yong Kim. 2015. Fast Grid-Free Surface Tracking. ACM Trans. Graph. 34, 4 (2015), 148:1–148:11.
[11]
Fang Da, Christopher Batty, and Eitan Grinspun. 2014. Multimaterial Mesh-Based Surface Tracking. ACM Trans. Graph. 33, 4 (2014), 112:1–112:11.
[12]
Fang Da, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2015. Double bubbles sans toil and trouble: Discrete circulation-preserving vortex sheets for soap films and foams. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.
[13]
Lorenzo Diazzi and Marco Attene. 2021. Convex Polyhedral Meshing for Robust Solid Modeling. ACM Trans. Graph. 40, 6 (2021), 259:1–259:16.
[14]
Jian Du, Brian Fix, James Glimm, Xicheng Jia, Xiaolin Li, Yuanhua Li, and Lingling Wu. 2006. A simple package for front tracking. J. Comput. Phys. 213, 2 (2006), 613–628.
[15]
Herbert Edelsbrunner and Ernst Peter M?cke. 1990. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics (tog) 9, 1 (1990), 66–104.
[16]
Xianzhong Fang, Mathieu Desbrun, Hujun Bao, and Jin Huang. 2022. TopoCut: Fast and Robust Planar Cutting of Arbitrary Domains. ACM Trans. Graph. 41, 4 (2022), 1–15.
[17]
Steven W Gagniere, Yushan Han, Yizhou Chen, David AB Hyde, Alan Marquez-Razon, Joseph Teran, and Ronald Fedkiw. 2022. A Robust Grid-Based Meshing Algorithm for Embedding Self-Intersecting Surfaces. arXiv preprint arXiv:2201.06256 (2022).
[18]
James Glimm, John W. Grove, X. L. Li, and D. C. Tan. 2000. Robust Computational Algorithms for Dynamic Interface Tracking in Three Dimensions. SIAM Journal on Scientific Computing 21, 6 (Jan. 2000), 2240–2256.
[19]
Francis H Harlow. 1964. The particle-in-cell computing method for fluid dynamics. Methods Comput. Phys. 3 (1964), 319–343.
[20]
Andreas Hubeli and Markus Gross. 2000. Fairing of non-manifolds for visualization. In Proceedings Visualization 2000. VIS 2000 (Cat. No. 00CH37145). IEEE, 407–414.
[21]
Sadashige Ishida, Peter Synak, Fumiya Narita, Toshiya Hachisuka, and Chris Wojtan. 2020. A Model for Soap Film Dynamics with Evolving Thickness. ACM Trans. Graph. 39, 4, Article 31 (aug 2020), 11 pages.
[22]
Sadashige Ishida, Chris Wojtan, and Albert Chern. 2022. Hidden degrees of freedom in implicit vortex filaments. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–14.
[23]
Sadashige Ishida, Masafumi Yamamoto, Ryoichi Ando, and Toshiya Hachisuka. 2017. A hyperbolic geometric flow for evolving films and foams. ACM Transactions on Graphics (TOG) 36, 6 (2017), 1–11.
[24]
Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust Inside-Outside Segmentation Using Generalized Winding Numbers. ACM Trans. Graph. 32, 4 (2013), 33:1–33:12.
[25]
Xiangmin Jiao. 2007. Face offsetting: A unified approach for explicit moving interfaces. Journal of computational physics 220, 2 (2007), 612–625.
[26]
Byungmoon Kim. 2010. Multi-phase fluid simulations using regional level sets. ACM Transactions on Graphics (TOG) 29, 6 (2010), 1–8.
[27]
Byungmoon Kim, Yingjie Liu, Ignacio Llamas, Xiangmin Jiao, and Jarek Rossignac. 2007. Simulation of bubbles in foam with the volume control method. ACM Transactions on Graphics (TOG) 26, 3 (2007), 98–es.
[28]
Oliver Laric. 2012. Three D Scans. Retrieved 21 Januarry 2024 from https://threedscans.com
[29]
Xiaosheng Li, Xiaowei He, Xuehui Liu, Jian J. Zhang, Baoquan Liu, and Enhua Wu. 2016. Multiphase Interface Tracking with Fast Semi-Lagrangian Contouring. IEEE Transactions on Visualization and Computer Graphics 22, 8 (2016), 1973–1986.
[30]
Yijing Li and Jernej Barbi?. 2018. Immersion of Self-Intersecting Solids and Surfaces. ACM Trans. Graph. 37, 4 (2018), 45:1–45:14.
[31]
Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. 2006. Multiple interacting liquids. ACM Transactions on Graphics (TOG) 25, 3 (2006), 812–819.
[32]
Marek Krzysztof Misztal and Jakob Andreas B?rentzen. 2012. Topology-Adaptive Interface Tracking Using the Deformable Simplicial Complex. ACM Trans. Graph. 31, 3 (2012), 24:1–24:12.
[33]
Matthias M?ller. 2009. Fast and Robust Tracking of Fluid Surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (New Orleans, Louisiana) (SCA ’09). Association for Computing Machinery, New York, NY, USA, 237–245.
[34]
Ken Museth. 2013. VDB: High-resolution Sparse Volumes with Dynamic Topology. 32, 3 (2013), 27:1–27:22.
[35]
Stanley Osher and Ronald P Fedkiw. 2001. Level set methods: an overview and some recent results. Journal of Computational physics 169, 2 (2001), 463–502.
[36]
Darko Pavi?, Marcel Campen, and Leif Kobbelt. 2010. Hybrid booleans. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 75–87.
[37]
J-P Pons and J-D Boissonnat. 2007. A lagrangian approach to dynamic interfaces through kinetic triangulation of the ambient space. In Computer Graphics Forum, Vol. 26. Wiley Online Library, 227–239.
[38]
Bernhard Reitinger, Alexander Bornik, and Reinhard Beichel. 2005. Constructing Smooth Non-Manifold Meshes of Multi-Labeled Volumetric Datasets. The 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (2005).
[39]
Jarek Rossignac. 2001. 3D compression made simple: Edgebreaker with zipandwrap on a corner-table. In Proceedings International Conference on Shape Modeling and Applications. IEEE, 278–283.
[40]
Silvia Sell?n, Herng Yi Cheng, Yuming Ma, Mitchell Dembowski, and Alec Jacobson. 2019. Solid geometry processing on deconstructed domains. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 564–579.
[41]
James A Sethian. 1999. Fast marching methods. SIAM review 41, 2 (1999), 199–235.
[42]
Nicholas Sharp and Keenan Crane. 2020. A laplacian for nonmanifold triangle meshes. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 69–80.
[43]
D. She, R. Kaufman, H. Lim, J. Melvin, A. Hsu, and J. Glimm. 2016. Chapter 15 – Front-Tracking Methods. In Handbook of Numerical Analysis, R?mi Abgrall and Chi-Wang Shu (Eds.). Handbook of Numerical Methods for Hyperbolic Problems, Vol. 17. Elsevier, 383–402.
[44]
Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Workshop on applied computational geometry. Springer, 203–222.
[45]
Kenji Shimada and David C Gossard. 1995. Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing. In Proceedings of the third ACM symposium on Solid modeling and applications. 409–419.
[46]
Michael Tao, Christopher Batty, Eugene Fiume, and David I. W. Levin. 2019. Mandoline: Robust Cut-Cell Generation for Arbitrary Triangle Meshes. ACM Trans. Graph. 38, 6 (2019), 1–17.
[47]
Philip Trettner, Julius Nehring-Wirxel, and Leif Kobbelt. 2022. EMBER: Exact Mesh Booleans via Efficient & Robust Local Arrangements. ACM Trans. Graph. 41, 4 (2022), 1–15.
[48]
Marc Wagner, Ulf Labsik, and G?nther Greiner. 2003. Repairing non-manifold triangle meshes using simulated annealing. International Journal of Shape Modeling 9, 02 (2003), 137–153.
[49]
Charlie CL Wang. 2010. Approximate boolean operations on large polyhedral solids with partial mesh reconstruction. IEEE transactions on visualization and computer graphics 17, 6 (2010), 836–849.
[50]
Chris Wojtan, Nils Th?rey, Markus Gross, and Greg Turk. 2009. Deforming Meshes That Split and Merge. ACM Trans. Graph. 28, 3 (2009), 76:1–76:10.
[51]
Chris Wojtan, Nils Th?rey, Markus Gross, and Greg Turk. 2010. Physics-Inspired Topology Changes for Thin Fluid Features. ACM Trans. Graph. 29, 4 (2010), 50:1–50:8.
[52]
Meng Yang, Juntao Ye, Frank Ding, Yubo Zhang, and Dong-Ming Yan. 2019. A Semi-Explicit Surface Tracking Mechanism for Multi-Phase Immiscible Liquids. IEEE Transactions on Visualization and Computer Graphics 25, 10 (2019), 2873–2885.
[53]
Lexing Ying and Denis Zorin. 2001. Nonmanifold subdivision. In Proceedings Visualization, 2001. VIS’01. IEEE, 325–569.
[54]
Steven T Zalesak. 1979. Fully multidimensional flux-corrected transport algorithms for fluids. Journal of computational physics 31, 3 (1979), 335–362.
[55]
Wen Zheng, Jun-Hai Yong, and Jean-Claude Paul. 2009. Simulation of bubbles. Graphical Models 71, 6 (2009), 229–239.
[56]
Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. 35, 4 (2016), 39:1–39:15.
