Adaptive grid generation for discretizing implicit complexes
Authors: 
Yiwen Ju, Xingyi Du, Qingnan Zhou, Nathan Carr, Tao JuAuthors Info & Claims
Article No.: 82, Pages 1 - 17
Abstract
We present a method for generating a simplicial (e.g., triangular or tetrahedral) grid to enable adaptive discretization of implicit shapes defined by a vector function. Such shapes, which we call implicit complexes, are generalizations of implicit surfaces and useful for representing non-smooth and non-manifold structures. While adaptive grid generation has been extensively studied for polygonizing implicit surfaces, few methods are designed for implicit complexes. Our method can generate adaptive grids for several implicit complexes, including arrangements of implicit surfaces, CSG shapes, material interfaces, and curve networks. Importantly, our method adapts the grid to the geometry of not only the implicit surfaces but also their lower-dimensional intersections. We demonstrate how our method enables efficient and detail-preserving discretization of non-trivial implicit shapes.
References
[1]
Eugene Allgower and Kurt Georg. 1980. Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations. SIAM Rev. 22, 1 (jan 1980), 28--85.
[2]
Eugene L. Allgower and Kurt Georg. 1989. Estimates for piecewise linear approximations of implicitly defined manifolds. Applied Mathematics Letters 2 (1989), 111--115. https://api.semanticscholar.org/CorpusID:123564143
[3]
Eugene L. Allgower and Phillip H. Schmidt. 1985. An Algorithm for Piecewise-Linear Approximation of an Implicitly Defined Manifold. SIAM J. Numer. Anal. 22, 2 (1985), 322--346. arXiv:https://doi.org/10.1137/0722020
[4]
Robert Anderson, Julian Andrej, Andrew Barker, Jamie Bramwell, Jean-Sylvain Camier, Jakub Cerveny, Veselin Dobrev, Yohann Dudouit, Aaron Fisher, Tzanio Kolev, et al. 2021. MFEM: A Modular Finite Element Methods Library. Computers & Mathematics with Applications 81 (2021), 42--74.
[5]
Douglas N. Arnold, Arup K. Mukherjee, and Luc Pouly. 2000. Locally Adapted Tetrahedral Meshes Using Bisection. SIAM J. Sci. Comput. 22 (2000), 431--448. https://api.semanticscholar.org/CorpusID:13167330
[6]
Sergei Azernikov and Anath Fischer. 2005. Anisotropic Meshing of Implicit Surfaces. In Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI '05). IEEE Computer Society, USA, 94--103.
[7]
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.
[8]
Eberhard Bänsch. 1991. Local mesh refinement in 2 and 3 dimensions. IMPACT Comput. Sci. Eng. 3 (1991), 181--191. https://api.semanticscholar.org/CorpusID:33479075
[9]
Guillem Belda Ferrín, Eloi Ruiz Gironès, and Francisco Javier Roca Navarro. 2022. Bisecting with Optimal Similarity Bound on 3D Unstructured Conformal Meshes. In Proceedings of the 2022 SIAM International Meshing Roundtable. Zenodo, USA, 86--87.
[10]
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.
[11]
Jürgen Bey. 1995. Tetrahedral grid refinement. Computing 55 (1995), 355--378. https://api.semanticscholar.org/CorpusID:20829446
[12]
Jules Bloomenthal. 1988. Polygonization of implicit surfaces. Comput. Aided Geom. Des. 5 (1988), 341--355. https://api.semanticscholar.org/CorpusID:16474404
[13]
Jean-Daniel Boissonnat, David Cohen-Steiner, and Gert Vegter. 2008. Isotopic implicit surface meshing. Discrete & Computational Geometry 39, 1--3 (2008), 138--157.
[14]
Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken. 2023. Tracing Isomanifolds in R d in Time Polynomial in d using Coxeter-Freudenthal-Kuhn Triangulations. SIAM J. Comput. 52, 2 (2023), 452--486. arXiv:https://doi.org/10.1137/21M1412918
[15]
Jean-Daniel Boissonnat and Mathijs Wintraecken. 2022. The Topological Correctness of PL Approximations of Isomanifolds. Found. Comput. Math. 22, 4 (aug 2022), 967--1012.
[16]
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.
[17]
Rita Borgo, Paolo Cignoni, and Roberto Scopigno. 2004. Simplicial-based Multiresolution Volume Datasets Management: An Overview. In Geometric Modeling for Scientific Visualization. Springer Verlag, Berlin, Heidelberg, 309--327. https://api.semanticscholar.org/CorpusID:54075053
[18]
Jan Brandts, Sergey Korotov, Michal Křížek, et al. 2020. Simplicial partitions with applications to the finite element method. Springer.
[19]
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.
[20]
Amit Chattopadhyay, Simon Plantinga, and Gert Vegter. 2012. Certified Meshing of Radial Basis Function Based Isosurfaces. Vis. Comput. 28, 5 (may 2012), 445--462.
[21]
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.
[22]
L. de Figueiredo, A. Paiva, T. Lewiner, and H. Lopes. 2006. Robust adaptive meshes for implicit surfaces. In 2012 25th SIBGRAPI Conference on Graphics, Patterns and Images. IEEE Computer Society, Los Alamitos, CA, USA, 205--212.
[23]
J Ruiz de Miras and Francisco R Feito. 2002. Direct and robust voxelization and polygonization of free-form CSG solids. In Proceedings. First International Symposium on 3D Data Processing Visualization and Transmission. 352--355.
[24]
Tamal Krishna Dey and Andrew G. Slatton. 2013. Localized Delaunay Refinement for Piecewise-Smooth Complexes. In Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (Rio de Janeiro, Brazil) (SoCG '13). Association for Computing Machinery, New York, NY, USA, 47--56.
[25]
Sény Diatta, Guillaume Moroz, and Marc Pouget. 2019. Reliable Computation of the Singularities of the Projection in R3 of a Generic Surface of R4. In MACIS 2019 - Mathematical Aspects of Computer and Information Sciences. Gebze-Istanbul, Turkey. https://inria.hal.science/hal-02406758
[26]
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.
[27]
Xingyi Du, Qingnan Zhou, Nathan A. Carr, and Tao Ju. 2022. Robust computation of implicit surface networks for piecewise linear functions. ACM Transactions on Graphics (TOG) 41 (2022), 1--16. https://api.semanticscholar.org/CorpusID:249917144
[28]
Tom Duff. 1992. Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry. ACM SIGGRAPH computer graphics 26, 2 (1992), 131--138.
[29]
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 Proceedings of the 15th Annual European Conference on Algorithms (Eilat, Israel) (ESA'07). Springer-Verlag, Berlin, Heidelberg, 633--644.
[30]
Herbert Edelsbrunner and John Harer. 2002. Jacobi sets of multiple Morse functions. Foundations of Computational Mathematics, Minneapolis (2002), 37--57.
[31]
Gerald Farin. 1986. Triangular bernstein-bézier patches. Computer Aided Geometric Design 3, 2 (1986), 83--127.
[32]
Michael S Floater. 2015. Generalized barycentric coordinates and applications. Acta Numerica 24 (2015), 161--214.
[33]
Flopine. 2020. ShATI - Clé. https://www.shadertoy.com/view/wssBDf.
[34]
Paul Louis George, H. Borouchaki, F. Alauzet, P. Laug, A. Loseille, D. Marcum, and L. Maréchal. 2017. Mesh Generation and Mesh Adaptivity: Theory and Techniques. John Wiley & Sons, Ltd, USA, 1--51. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/9781119176817.ecm2012
[35]
T. Gerstner. 2003. Top-down view-dependent terrain triangulation using the octagon metric. Technical Report. University of Bonn.
[36]
Thomas Gerstner and Renato Pajarola. 2000. Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proceedings of the Conference on Visualization '00 (Salt Lake City, Utah, USA) (VIS '00). IEEE Computer Society Press, Washington, DC, USA, 259--266.
[37]
Benjamin Gregorski, Mark Duchaineau, Peter Lindstrom, Valerio Pascucci, and Kenneth I. Joy. 2002. Interactive view-dependent rendering of large isosurfaces. In Proceedings of the Conference on Visualization '02 (Boston, Massachusetts) (VIS '02). IEEE Computer Society, USA, 475--484.
[38]
Roberto Grosso, Christoph Lürig, and Thomas Ertl. 1997. The multilevel finite element method for adaptive mesh optimization and visualization of volume data. In Proceedings of the 8th Conference on Visualization '97 (Phoenix, Arizona, USA) (VIS '97). IEEE Computer Society Press, Washington, DC, USA, 387--ff.
[39]
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.
[40]
Mark Hall and Joe Warren. 1990. Adaptive polygonalization of implicitly defined surfaces. IEEE Computer Graphics and Applications 10, 6 (1990), 33--42.
[41]
Younis Hijazi, Aaron Knoll, Mathias Schott, Andrew Kensler, and Charles Hansen. 2010. Csg operations of arbitrary primitives with interval arithmetic and real-time ray casting. In Dagstuhl Follow-Ups, Vol. 1. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[42]
Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational implicit point set surfaces. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1--13.
[43]
Kin Chuen Hui and Z.H. Jiang. 1999. Tetrahedra Based Adaptive Polygonization of Implicit Surface Patches. Computer Graphics Forum 18, 1 (1999), 57--68. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/1467-8659.00302
[44]
Zhongshi Jiang, Ziyi Zhang, Yixin Hu, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2021. Bijective and coarse high-order tetrahedral meshes. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1--16.
[45]
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.
[46]
Payam Khanteimouri and Marcel Campen. 2023. 3D Bézier Guarding: Boundary-Conforming Curved Tetrahedral Meshing. ACM Transactions on Graphics (TOG) 42, 6 (2023), 1--19.
[47]
Byungmoon Kim. 2010. Multi-phase fluid simulations using regional level sets. ACM Transactions on Graphics (TOG) 29, 6 (2010), 1--8.
[48]
Dae-Hyun Kim, Ulf Doring, and Beat Bruderlin. 2000. Polygonization of Non-manifolds With the Aid of Interval Operators. ACM Eurographics Workshop on Implicit Surfaces (2000), 145--151. https://api.semanticscholar.org/CorpusID:14381080
[49]
Maximilian Kohlbrenner, Singchun Lee, Marc Alexa, and Misha Kazhdan. 2023. Poisson Manifold Reconstruction --- Beyond Co-dimension One. Computer Graphics Forum 42 (08 2023).
[50]
Igor Kossaczký. 1994. A recursive approach to local mesh refinement in two and three dimensions. J. Comput. Appl. Math. 55 (1994), 275--288. https://api.semanticscholar.org/CorpusID:123381194
[51]
Xinghua Liang and Yongjie Jessica Zhang. 2014. An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range. Engineering with Computers 30 (2014), 211--222. https://api.semanticscholar.org/CorpusID:14861190
[52]
Anwei Liu and Barry Joe. 1995. Quality Local Refinement of Tetrahedral Meshes Based on Bisection. SIAM Journal on Scientific Computing 16, 6 (1995), 1269--1291. arXiv:https://doi.org/10.1137/0916074
[53]
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.
[54]
Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. 2006. Multiple Interacting Liquids. ACM Trans. Graph. 25, 3 (jul 2006), 812--819.
[55]
Joseph M. Maubach. 1995. Local Bisection Refinement for N-Simplicial Grids Generated by Reflection. SIAM Journal on Scientific Computing 16, 1 (1995), 210--227. arXiv:https://doi.org/10.1137/0916014
[56]
Nimrod Megiddo. 1984. Linear programming in linear time when the dimension is fixed. Journal of the ACM (JACM) 31, 1 (1984), 114--127.
[57]
Chohong Min. 2003. Simplicial isosurfacing in arbitrary dimension and codimension. J. Comput. Phys. 190, 1 (2003), 295--310.
[58]
William F Mitchell. 2016. 30 years of newest vertex bisection. In AIP Conference Proceedings, Vol. 1738. AIP Publishing.
[59]
Neil Molino, Robert Bridson, Joseph Teran, and Ronald Fedkiw. 2003. A Crystalline, Red Green Strategy for Meshing Highly Deformable Objects with Tetrahedra. 12th Int. Meshing Roundtable, 103--114.
[60]
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.
[61]
Gregory Nielson and R. Franke. 1997. Computing the separating surface for segmented data. 229--233.
[62]
Th Ottmann, Sven Schuierer, and Subbiah Soundaralakshmi. 1995. Enumerating extreme points in higher dimensions. In STACS 95, Ernst W. Mayr and Claude Puech (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 562--570.
[63]
Steve Oudot, Laurent Rineau, and Mariette Yvinec. 2010. Meshing volumes with curved boundaries. Engineering with Computers 26, 3 (2010), 265--279.
[64]
Valerio Pascucci. 2004. Isosurface computation made simple: hardware acceleration, adaptive refinement and tetrahedral stripping. In Proceedings of the Sixth Joint Eurographics - IEEE TCVG Conference on Visualization (Konstanz, Germany) (VISSYM'04). Eurographics Association, Goslar, DEU, 293--300.
[65]
Alexander Pasko, Valery Adzhiev, Alexei Sourin, and Vladimir Savchenko. 1995. Function representation in geometric modeling: concepts, implementation and applications. The visual computer 11 (1995), 429--446.
[66]
Carl S. Petersen. 1984. Adaptive contouring of three-dimensional surfaces. Computer Aided Geometric Design 1, 1 (1984), 61--74.
[67]
Carl S. Petersen, Bruce R. Piper, and Andrew J. Worsey. 1987. Adaptive contouring of a trivariate interpolant. Geometric Modeling: Algorithms and New Trends (1987), 385--395.
[68]
Simon Plantinga and Gert Vegter. 2006. Isotopic meshing of implicit surfaces. The Visual Computer 23 (2006), 45--58. https://api.semanticscholar.org/CorpusID:751474
[69]
Angel Plaza and Maria-Cecilia Rivara. 2003. Mesh Refinement Based on the 8-Tetrahedra Longest- Edge Partition. In Proceedings of the 12th International Meshing Roundtable. 67--78.
[70]
Sundaresan Raman and Rephael Wenger. 2008. Quality Isosurface Mesh Generation Using an Extended Marching Cubes Lookup Table. Computer Graphics Forum 27, 3 (2008), 791--798. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2008.01209.x
[71]
Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977).
[72]
María Cecilia Rivara. 1991. Local modification of meshes for adaptive and/or multigrid finite-element methods. J. Comput. Appl. Math. 36 (1991), 79--89. https://api.semanticscholar.org/CorpusID:120011902
[73]
RI Saye. 2015. An algorithm to mesh interconnected surfaces via the Voronoi interface. Engineering with Computers 31, 1 (2015), 123--139.
[74]
Scott Schaefer and Joe Warren. 2004. Dual marching cubes: Primal contouring of dual grids. In 12th Pacific Conference on Computer Graphics and Applications, 2004. PG 2004. Proceedings. IEEE, 70--76.
[75]
Michael F. W. Schmidt. 1993. Cutting cubesvisualizing implicit surfaces by adaptive polygonization. The Visual Computer 10 (1993), 101--115. https://api.semanticscholar.org/CorpusID:35201048
[76]
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.
[77]
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.
[78]
Barton T. Stander and John C. Hart. 1997. Guaranteeing the topology of an implicit surface polygonization for interactive modeling. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., USA, 279--286.
[79]
Robert F. Tobler, Thomas Galla, and Werner Purgathofer. 1995. ACSGM - An adaptive CSG meshing algorithm. Technical Report TR-186-2-95-13. Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria. https://www.cg.tuwien.ac.at/research/publications/1995/Tobler-1995-AAC/ human contact: [email protected].
[80]
Gokul Varadhan, Shankar Krishnan, TVN Sriram, and Dinesh Manocha. 2004. Topology preserving surface extraction using adaptive subdivision. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 235--244.
[81]
Chris Weigle and David C. Banks. 1996. Complex-valued contour meshing. In Proceedings of the 7th Conference on Visualization '96 (San Francisco, California, USA) (VIS '96). IEEE Computer Society Press, Washington, DC, USA, 173--ff.
[82]
Kenneth Weiss and Leila De Floriani. 2009. Supercubes: A high-level primitive for diamond hierarchies. IEEE Transactions on Visualization and Computer Graphics 15, 6 (2009), 1603--1610.
[83]
Kenneth Weiss and Leila De Floriani. 2011. Simplex and Diamond Hierarchies: Models and Applications. Computer Graphics Forum 30, 8 (2011), 2127--2155. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2011.01853.x
[84]
Hassler Whitney. 1957. Geometric Integration Theory. Princeton University Press.
[85]
Shangyou Zhang. 1995. Successive subdivisions of tetrahedra and multigrid methods on tetrahedral meshes. Houston J. Math 21, 3 (1995), 541--556.
[86]
Yongjie Zhang, Chandrajit Bajaj, and Bong-Soo Sohn. 2005. 3D finite element meshing from imaging data. Computer Methods in Applied Mechanics and Engineering 194, 48 (2005), 5083--5106. Unstructured Mesh Generation.
[87]
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.
[88]
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.
[89]
Tong Zhao, Pierre Alliez, Tamy Boubekeur, Laurent Busé, and Jean-Marc Thiery. 2021. Progressive Discrete Domains for Implicit Surface Reconstruction. Computer Graphics Forum 40, 5 (2021), 143--156. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14363
[90]
Yong Zhou, Baoquan Chen, and Arie Kaufman. 1997. Multiresolution tetrahedral framework for visualizing regular volume data. In Proceedings of the 8th Conference on Visualization '97 (Phoenix, Arizona, USA) (VIS '97). IEEE Computer Society Press, Washington, DC, USA, 135--ff.
Index Terms
- Adaptive grid generation for discretizing implicit complexes
Recommendations
Trimming implicit surfaces
Algorithms for trimming implicit surfaces yielding surface sheets and stripes are presented. These two-dimensional manifolds with boundaries result from set-theoretic operations on an implicit surface and a solid or another implicit surface. The ...
Modelling with implicit surfaces that interpolate
SIGGRAPH '05: ACM SIGGRAPH 2005 CoursesWe introduce new techniques for modelling with interpolating implicit surfaces. This form of implicit surface was first used for problems of surface reconstruction and shape transformation, but the emphasis of our work is on model creation. These ...
Adaptive polygonization of implicit surfaces
We present an algorithm for polygonizing closed implicit surfaces, which produces meshes adapted to the local curvature of the surface. Our method is similar to, but not based on, Marching Triangles, in that we start from a point on the surface and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2024
Published in TOG Volume 43, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 492Total Downloads
- Downloads (Last 12 months)492
- Downloads (Last 6 weeks)59
Reflects downloads up to 14 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in