“Robust computation of implicit surface networks for piecewise linear functions” by Du, Zhou, Carr and Ju

Implicit surface networks, such as arrangements of implicit surfaces and materials interfaces, are used for modeling piecewise smooth or partitioned shapes. However, accurate and numerically robust algorithms for discretizing either structure on a grid are still lacking. We present a unified approach for computing both types of surface networks for piecewise linear functions defined on a tetrahedral grid. Both algorithms are guaranteed to produce a correct combinatorial structure for any number of functions. Our main contribution is an exact and efficient method for partitioning a tetrahedron using the level sets of linear functions defined by barycentric interpolation. To further improve performance, we designed look-up tables to speed up processing of tetrahedra involving few functions and introduced an efficient algorithm for identifying nested 3D regions.

1. Pankaj K Agarwal and Micha Sharir. 2000. Arrangements and their applications. In Handbook of computational geometry. Elsevier, 49–119.Google Scholar
2. Lionel Alberti, Bernard Mourrain, and Julien Wintz. 2008. Topology and arrangement computation of semi-algebraic planar curves. Computer Aided Geometric Design 25, 8 (2008), 631–651.Google ScholarDigital Library
3. Marco Attene. 2020. Indirect predicates for geometric constructions. Computer-Aided Design 126 (2020), 102856.Google ScholarCross Ref
4. Brigham Bagley, Shankar Sastry, and Ross Whitaker. 2016. A Marching-tetrahedra Algorithm for Feature-preserving Meshing of Piecewise-smooth Implicit Surfaces. Procedia Engineering 163 (12 2016), 162–174.Google Scholar
5. C. L. Bajaj and T. Dey. 1990. Polygon Nesting and Robustness. Inf. Process. Lett. 35, 1 (jun 1990), 23–32.Google Scholar
6. Eric Berberich, Pavel Emeliyanenko, Alexander Kobel, and Michael Sagraloff. 2012. Arrangement computation for planar algebraic curves. In Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation. 88–98.Google ScholarDigital Library
7. Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269–1278.Google Scholar
8. Martin Bertram, Gerd Reis, Rolf Hendrik van Lengen, Sascha Köhn, and Hans Hagen. 2005. Non-manifold mesh extraction from time-varying segmented volumes used for modeling a human heart.. In EuroVis. Citeseer, 199–206.Google Scholar
9. Jules Bloomenthal and Keith Ferguson. 1995. Polygonization of non-manifold implicit surfaces. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. 309–316.Google ScholarDigital Library
10. Dobrina Boltcheva, Mariette Yvinec, and Jean-Daniel Boissonnat. 2009. Feature Preserving Delaunay Mesh Generation from 3D Multi-Material Images. In Proceedings of the Symposium on Geometry Processing (Berlin, Germany) (SGP ’09). 1455–1464.Google ScholarDigital Library
11. Kathleen Sue Bonnell, Mark A Duchaineau, Daniel R Schikore, Bernd Hamann, and Kenneth I Joy. 2003. Material interface reconstruction. IEEE Transactions on Visualization and Computer Graphics 9, 4 (2003), 500–511.Google ScholarDigital Library
12. Jonathan R Bronson, Shankar P Sastry, Joshua A Levine, and Ross T Whitaker. 2014. Adaptive and unstructured mesh cleaving. Procedia engineering 82 (2014), 266–278.Google Scholar
13. Michael Burns, Janek Klawe, Szymon Rusinkiewicz, Adam Finkelstein, and Doug DeCarlo. 2005. Line drawings from volume data. ACM Transactions on Graphics (TOG) 24, 3 (2005), 512–518.Google ScholarDigital Library
14. Marcel Campen and Leif Kobbelt. 2010. Exact and robust (self-) intersections for polygonal meshes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 397–406.Google Scholar
15. Bernard Chazelle and Herbert Edelsbrunner. 1992. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM (JACM) 39, 1 (1992), 1–54.Google ScholarDigital Library
16. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and robust mesh arrangements using floating-point arithmetic. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.Google ScholarDigital Library
17. Bruno Rodrigues De Araújo, Daniel S Lopes, Pauline Jepp, Joaquim A Jorge, and Brian Wyvill. 2015. A survey on implicit surface polygonization. ACM Computing Surveys (CSUR) 47, 4 (2015), 1–39.Google ScholarDigital Library
18. Tamal K Dey, Firdaus Janoos, and Joshua A Levine. 2012. Meshing interfaces of multilabel data with Delaunay refinement. Engineering with Computers 28, 1 (2012), 71–82.Google ScholarDigital Library
19. Lorenzo Diazzi and Marco Attene. 2021. Convex polyhedral meshing for robust solid modeling. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–16.Google ScholarDigital Library
20. Scott Dillard, John Bingert, Dan Thoma, and Bernd Hamann. 2007. Construction of Simplified Boundary Surfaces from Serial-sectioned Metal Micrographs. Visualization and Computer Graphics, IEEE Transactions on 13 (12 2007), 1528–1535.Google Scholar
21. Akio Doi and Akio Koide. 1991. An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells. IEICE Transactions on Information and Systems 74 (1991), 214–224.Google Scholar
22. Tao Du, Jeevana Priya Inala, Yewen Pu, Andrew Spielberg, Adriana Schulz, Daniela Rus, Armando Solar-Lezama, and Wojciech Matusik. 2018. Inversecsg: Automatic conversion of 3d models to csg trees. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–16.Google ScholarDigital Library
23. Xingyi Du, Qingnan Zhou, Nathan Carr, and Tao Ju. 2021. Boundary-Sampled Halfspaces: A New Representation for Constructive Solid Modeling. ACM Trans. Graph. 40, 4 (2021).Google ScholarDigital Library
24. Laurent Dupont, Michael Hemmer, Sylvain Petitjean, and Elmar Schömer. 2007. Complete, exact and efficient implementation for computing the adjacency graph of an arrangement of quadrics. In European Symposium on Algorithms. Springer, 633–644.Google ScholarCross Ref
25. Herbert Edelsbrunner and John Harer. 2002. Jacobi sets of multiple Morse functions. Foundations of Computational Mathematics, Minneapolis (2002), 37–57.Google Scholar
26. Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. 1996. The CGAL kernel: A basis for geometric computation. In Workshop on Applied Computational Geometry. Springer, 191–202.Google ScholarCross Ref
27. Andreas Fabri and Sylvain Pion. 2009. CGAL: The computational geometry algorithms library. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. 538–539.Google ScholarDigital Library
28. Powei Feng, Tao Ju, and Joe Warren. 2010. Piecewise Tri-linear Contouring for MultiMaterial Volumes. Lecture notes in computer science 6130, 43–56.Google Scholar
29. Google. 2017. Abseil: C++ Libraries from Google. https://abseil.io/.Google Scholar
30. Jiateng Guo, Xulei Wang, Jiangmei Wang, Xinwei Dai, Lixin Wu, Chaoling Li, Fengdan Li, Shanjun Liu, and Mark Walter Jessell. 2021. Three-dimensional geological modeling and spatial analysis from geotechnical borehole data using an implicit surface and marching tetrahedra algorithm. Engineering Geology 284 (2021), 106047.Google ScholarCross Ref
31. Hans-Christian Hege, Martin Seebass, Detlev Stalling, and Malte Zöckler. 1997. A generalized marching cubes algorithm based on non-binary classifications. (1997).Google Scholar
32. Michael Hemmer, Ophir Setter, and Dan Halperin. 2010. Constructing the exact Voronoi diagram of arbitrary lines in space. Ph.D. Dissertation. INRIA.Google Scholar
33. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
34. Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren. 2002. Dual contouring of hermite data. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 339–346.Google ScholarDigital Library
35. Byungmoon Kim. 2010. Multi-phase fluid simulations using regional level sets. ACM Transactions on Graphics (TOG) 29, 6 (2010), 1–8.Google ScholarDigital Library
36. Dae Hyun Kim, Ulf Doering, and Beat Bruderlin. 2000. Polygonization of non-manifolds with the aid of interval operators. In Proc. Implicit Surfaces. 145–151.Google Scholar
37. Bruno Lévy. 2016. Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK). Computer-Aided Design 72 (2016), 3–12.Google ScholarDigital Library
38. Bruno Lévy and Alain Filbois. 2015. Geogram: a library for geometric algorithms. (2015).Google Scholar
39. Jyh-Ming Lien, Vikram Sharma, Gert Vegter, and Chee Yap. 2014. Isotopic arrangement of simple curves: An exact numerical approach based on subdivision. In International Congress on Mathematical Software. Springer, 277–282.Google ScholarCross Ref
40. Patric Ljung and Anders Ynnerman. 2003. Extraction of intersection curves from iso-surfaces on co-located 3d grids. In The Annual SIGRAD Conference. Special Theme-Real-Time Simulations. Conference Proceedings from SIGRAD2003. Citeseer, 23–28.Google Scholar
41. William E. Lorensen and Harvey E. Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm.. In SIGGRAPH, Maureen C. Stone (Ed.). ACM, 163–169.Google Scholar
42. Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. 2006. Multiple Interacting Liquids. ACM Trans. Graph. 25, 3 (jul 2006), 812–819.Google ScholarDigital Library
43. Miriah Meyer, Ross Whitaker, Robert M. Kirby, Christian Ledergerber, Hanspeter Pfister, and Senior Member. 2008. Particle-based sampling and meshing of surfaces in multimaterial volumes. IEEE Transactions on Visualization and Computer Graphics (2008), 1539–1546.Google ScholarDigital Library
44. Bernard Mourrain, Jean-Pierre Técourt, and Monique Teillaud. 2005. On the computation of an arrangement of quadrics in 3d. Computational Geometry 30, 2 (2005), 145–164.Google ScholarDigital Library
45. Julius Nehring-Wirxel, Philip Trettner, and Leif Kobbelt. 2021. Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs. Computer-Aided Design 135 (2021), 103015.Google ScholarCross Ref
46. Gregory Nielson and R. Franke. 1997. Computing the separating surface for segmented data. 229–233.Google Scholar
47. J Pons, E Ségonne, Jean-Daniel Boissonnat, Laurent Rineau, Mariette Yvinec, and Renaud Keriven. 2007. High-Quality Consistent Meshing of Multi-Label Datasets. Information processing in medical imaging : proceedings of the … conference 20, 198–210.Google Scholar
48. Bernhard Reitinger, Alexander Bornik, and Reinhard Beichel. 2005. Constructing smooth non-manifold meshes of multi-labeled volumetric datasets. (2005).Google Scholar
49. Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977).Google Scholar
50. RI Saye. 2015. An algorithm to mesh interconnected surfaces via the Voronoi interface. Engineering with Computers 31, 1 (2015), 123–139.Google ScholarDigital Library
51. Robert I Saye and James A Sethian. 2012. Analysis and applications of the Voronoi implicit interface method. J. Comput. Phys. 231, 18 (2012), 6051–6085.Google ScholarDigital Library
52. Elmar Schömer and Nicola Wolpert. 2006. An exact and efficient approach for computing a cell in an arrangement of quadrics. Computational Geometry 33, 1–2 (2006), 65–97.Google ScholarCross Ref
53. M Haitham Shammaa, Yutaka Ohtake, and Hiromasa Suzuki. 2010. Segmentation of multi-material CT data of mechanical parts for extracting boundary surfaces. Computer-Aided Design 42, 2 (2010), 118–128.Google ScholarDigital Library
54. M Haitham Shammaa, Hiromasa Suzuki, and Yutaka Ohtake. 2008. Extraction of isosurfaces from multi-material CT volumetric data of mechanical parts. In Proceedings of the 2008 ACM symposium on solid and physical modeling. 213–220.Google ScholarDigital Library
55. Jonathan Richard Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (1997), 305–363.Google ScholarCross Ref
56. Kokichi Sugihara, Masao Iri, et al. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4 (1989), 380–393.Google ScholarDigital Library
57. Jean-Philippe Thirion and Alexis Gourdon. 1996. The 3D marching lines algorithm. Graphical Models and Image Processing 58, 6 (1996), 503–509.Google ScholarDigital Library
58. VP Voloshin, S Beaufils, and NN Medvedev. 2002. Void space analysis of the structure of liquids. Journal of molecular liquids 96 (2002), 101–112.Google ScholarCross Ref
59. Peihui Wang, Na Yuan, Yuewen Ma, Shiqing Xin, Ying He, Shuangmin Chen, Jian Xu, and Wenping Wang. 2020. Robust Computation of 3D Apollonius Diagrams. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 43–55.Google Scholar
60. Hans-Martin Will. 1999. Computation of additively weighted Voronoi cells for applications in molecular biology. Ph. D. Dissertation. ETH Zurich.Google Scholar
61. Ziji Wu and John M Sullivan Jr. 2003. Multiple material marching cubes algorithm. Internat. J. Numer. Methods Engrg. 58, 2 (2003), 189–207.Google ScholarCross Ref
62. Shuntaro Yamazaki, Kiwamu Kase, and Katsushi Ikeuchi. 2002. Non-manifold implicit surfaces based on discontinuous implicitization and polygonization. In Geometric Modeling and Processing. Theory and Applications. GMP 2002. Proceedings. IEEE, 138–146.Google ScholarCross Ref
63. Yongjie Zhang, Thomas Hughes, and Chandrajit Bajaj. 2007. Automatic 3D Mesh Generation for a Domain with Multiple Materials. Proceedings of the 16th International Meshing Roundtable, 367–386.Google Scholar
64. Yongjie Zhang, Thomas JR Hughes, and Chandrajit L Bajaj. 2008. Automatic 3d mesh generation for a domain with multiple materials. In Proceedings of the 16th international meshing roundtable. Springer, 367–386.Google Scholar
65. Yongjie Jessica Zhang and Jin Qian. 2012. Resolving topology ambiguity for multiple-material domains. Computer Methods in Applied Mechanics and Engineering 247 (2012), 166–178.Google ScholarCross Ref
66. Wen Zheng, Jun-Hai Yong, and Jean-Claude Paul. 2009. Simulation of bubbles. Graphical Models 71, 6 (2009), 229–239.Google ScholarDigital Library
67. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–15.Google ScholarDigital Library