More Web Proxy on the site http://driver.im/

research-article

Geometric Reconstruction of Implicitly Defined Surfaces and Domains with Topological Guarantees

Authors:

Christian Engwer,

Andreas NüßingAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 2

Article No.: 14, Pages 1 - 20

https://doi.org/10.1145/3104989

Published: 16 August 2017 Publication History

Abstract

Implicitly described domains are a well-established tool in the simulation of time-dependent problems, for example, using level-set methods. To solve partial differential equations on such domains, a range of numerical methods was developed, for example, the Immersed Boundary method, the Unfitted Finite Element or Unfitted Discontinuous Galerkin methods, and the eXtended or Generalised Finite Element methods, just to name a few. Many of these methods involve integration over cut-cells or their boundaries, as they are described by sub-domains of the original level-set mesh.

We present a new algorithm to geometrically evaluate the integrals over domains described by a first-order, conforming level-set function. The integration is based on a polyhedral reconstruction of the implicit geometry, following the concepts of the marching cubes algorithm. The algorithm preserves various topological properties of the implicit geometry in its polyhedral reconstruction, making it suitable for Finite Element computations. Numerical experiments show second-order accuracy of the integration.

An implementation of the algorithm is available as free software, which allows for an easy incorporation into other projects. The software is in productive use within the DUNE framework (Bastian et al. 2008a).

References

[1]

O. Aberth. 1973. Iteration methods for finding all zeros of a polynomial simultaneously. Math. Comp. 27, 122 (1973), 339--344.

[2]

. W. Barrett and C. M. Elliott. 1987. Fitted and unfitted finite-element methods for elliptic equations with smooth interfaces. IMA J. Numer. Anal. 7, 3 (1987), 283--300.

[3]

P. Bastian, M. Blatt, A. Dedner, C. Engwer, R. Klöfkorn, R. Kornhuber, M. Ohlberger, and O. Sander. 2008a. A generic grid interface for parallel and adaptive scientific computing. Part II: Implementation and tests in DUNE. Computing 82, 2--3 (7 2008), 121--138.

Digital Library

[4]

P. Bastian, M. Blatt, A. Dedner, C. Engwer, R. Klöfkorn, M. Ohlberger, and O. Sander. 2008b. A generic grid interface for parallel and adaptive scientific computing. Part I: Abstract framework. Computing 82, 2 (July 2008), 103--119.

Digital Library

[5]

P. Bastian and C. Engwer. 2009. An unfitted finite element method using discontinuous Galerkin. Int. J. Numer. Methods Eng. 79, 12 (2009), 1557--1576.

[6]

E. Burman, S. Claus, P. Hansbo, M. G. Larson, and A. Massing. 2015. CutFEM: Discretizing geometry and partial differential equations. Int. J. Numer. Methods Eng. 104, 7 (2015), 472--501.

[7]

E. V. Chernyaev. 1995. Marching Cubes 33: Construction of Topologically Correct Isosurfaces. Technical Report. CERN, Geneva. http://cds.cern.ch/record/292771.

[8]

J. Dolbow, N. Moes, and T. Belytschko. 2001. An extended finite element method for modeling crack growth with frictional contact. Comput. Methods Appl. Mech. Eng. 190, 51--52 (2001), 6825--6846.

[9]

T. Elvins. 1992. A survey of algorithms for volume visualization. ACM Siggraph Comput. Graph. 26, 3 (1992), 194--201.

Digital Library

[10]

C. Engwer and F. Heimann. 2012. DUNE-UDG: A cut-cell framework for unfitted discontinuous Galerkin methods. In Advances in DUNE, Andreas Dedner, Bernd Flemisch, and Robert Klöfkorn (Eds.). Springer, 89--100.

[11]

C. Engwer and A. Nüßing. 2017a. TPMC examples and tests. ZENODO. (2017).

[12]

C. Engwer and A. Nüßing. 2017b. TPMC library. ZENODO. (2017).

[13]

G. J. Fix. 1982. Phase Field Methods for Free Boundary Problems. Technical Report. Department of Mathematical Sciences, Carnegie Mellon University.

[14]

H. Freudenthal. 1942. Simplizialzerlegungen von beschränkter Flachheit. Ann. Math. 43 (1942), 580--582.

[15]

A. Gueziec and R. Hummel. 1995. Exploiting triangulated surface extraction using tetrahedral decomposition. IEEE Trans. Vis. Comput. Graph. 1, 4 (1995), 328--342.

Digital Library

[16]

C. Lehrenfeld and A. Reusken. 2012. Nitsche-XFEM with streamline diffusion stabilization for a two-phase mass transport problem. SIAM J. Sci. Comput. 34, 5 (2012), A2740--A2759.

Digital Library

[17]

T. Lewiner, H. Lopes, A. W. Vieira, and G. Tavares. 2003. Efficient implementation of marching cubes’ cases with topological guarantees. J. Graph. Tools 8, 2 (2003), 1--15.

[18]

W. Lorensen and H. Cline. 1987. Marching cubes: A high resolution 3d surface construction algorithm. Comput. Graph. 21, 4 (1987), 163--169.

Digital Library

[19]

C. Min and F. Gibou. 2007. Geometric integration over irregular domains with application to level-set methods. J. Comput. Phys. 226, 2 (2007), 1432--1443.

Digital Library

[20]

B. Müller, F. Kummer, and M. Oberlack. 2013. Highly accurate surface and volume integration on implicit domains by means of moment-fitting. Int. J. Numer. Methods Eng. 96, 8 (2013), 512--528.

[21]

S. Osher and J. A. Sethian. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 1 (1988), 12--49.

Digital Library

[22]

C. S. Peskin. 1977. Numerical analysis of blood flow in the heart. J. Comput. Phys. 25, 3 (November 1977), 220--252.

[23]

T. Strouboulis, K. Copps, and I. Babuška. 2001. The generalized finite element method. Comput. Methods Appl. Mech. Eng. 190, 32--33 (2001), 4081--4193.

[24]

Y. Sudhakar and W. A. Wall. 2013. Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in enriched partition of unity methods. Comput. Methods Appl. Mech. Eng. 258 (2013), 39--54.

Cited By

Erdbrügger THöltershinken MRadecke JBuschermöhle YWallois FPursiainen SGross JLencer REngwer CWolters C(2024)CutFEM‐based MEG forward modeling improves source separability and sensitivity to quasi‐radial sources: A somatosensory group studyHuman Brain Mapping10.1002/hbm.2681045:11Online publication date: 14-Aug-2024
https://doi.org/10.1002/hbm.26810
Erdbrügger TWesthoff AHöltershinken MRadecke JBuschermöhle YBuyx AWallois FPursiainen SGross JLencer REngwer CWolters C(2023)CutFEM forward modeling for EEG source analysisFrontiers in Human Neuroscience10.3389/fnhum.2023.121675817Online publication date: 22-Aug-2023
https://doi.org/10.3389/fnhum.2023.1216758
Birke GEngwer CMay SStreitbürger F(2023)Domain of Dependence Stabilization for the Acoustic Wave Equation on 2D Cut-Cell MeshesFinite Volumes for Complex Applications X—Volume 2, Hyperbolic and Related Problems10.1007/978-3-031-40860-1_6(53-61)Online publication date: 13-Oct-2023
https://doi.org/10.1007/978-3-031-40860-1_6
Show More Cited By

Index Terms

Geometric Reconstruction of Implicitly Defined Surfaces and Domains with Topological Guarantees

Recommendations

Using High-Order Transport Theorems for Implicitly Defined Moving Curves to Perform Quadrature on Planar Domains

The numerical integration over a planar domain that is cut by an implicitly defined boundary curve is an important problem that arises, for example, in unfitted finite element methods and in isogeometric analysis on trimmed computational domains. In this ...
Removing excess topology from isosurfaces

Many high-resolution surfaces are created through isosurface extraction from volumetric representations, obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical and topological errors. Reducing ...
Surfaces from contours

This paper is concerned with the problem of reconstructing the surfaces of three-dimensional objects, given a collection of planar contours representing cross-sections through the objects. This problem has important aplications in biomedical research and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 44, Issue 2

June 2018

242 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3132683

Editor:
Daniel Kressner
EPF Lausanne, Switzerland

Issue’s Table of Contents

Copyright © 2017 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 ACM 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: 16 August 2017

Accepted: 01 May 2017

Revised: 01 January 2017

Received: 01 January 2016

Published in TOMS Volume 44, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
253
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Erdbrügger THöltershinken MRadecke JBuschermöhle YWallois FPursiainen SGross JLencer REngwer CWolters C(2024)CutFEM‐based MEG forward modeling improves source separability and sensitivity to quasi‐radial sources: A somatosensory group studyHuman Brain Mapping10.1002/hbm.2681045:11Online publication date: 14-Aug-2024
https://doi.org/10.1002/hbm.26810
Erdbrügger TWesthoff AHöltershinken MRadecke JBuschermöhle YBuyx AWallois FPursiainen SGross JLencer REngwer CWolters C(2023)CutFEM forward modeling for EEG source analysisFrontiers in Human Neuroscience10.3389/fnhum.2023.121675817Online publication date: 22-Aug-2023
https://doi.org/10.3389/fnhum.2023.1216758
Birke GEngwer CMay SStreitbürger F(2023)Domain of Dependence Stabilization for the Acoustic Wave Equation on 2D Cut-Cell MeshesFinite Volumes for Complex Applications X—Volume 2, Hyperbolic and Related Problems10.1007/978-3-031-40860-1_6(53-61)Online publication date: 13-Oct-2023
https://doi.org/10.1007/978-3-031-40860-1_6
Birke GEngwer CMay SStreitbürger F(2023)DoD Stabilization of linear hyperbolic PDEs on general cut‐cell meshesPAMM10.1002/pamm.20220019823:1Online publication date: 31-May-2023
https://doi.org/10.1002/pamm.202200198
Zhang JZhong DWang L(2022)A Two-Step Surface Reconstruction Method Using Signed Marching CubesApplied Sciences10.3390/app1204179212:4(1792)Online publication date: 9-Feb-2022
https://doi.org/10.3390/app12041792
Streitbürger FBirke GEngwer CMay S(2022)DoD Stabilization for Higher-Order Advection in Two DimensionsSpectral and High Order Methods for Partial Differential Equations ICOSAHOM 2020+110.1007/978-3-031-20432-6_33(495-508)Online publication date: 29-Nov-2022
https://doi.org/10.1007/978-3-031-20432-6_33
Engwer CWesterheide S(2021)An Unfitted dG Scheme for Coupled Bulk-Surface PDEs on Complex GeometriesComputational Methods in Applied Mathematics10.1515/cmam-2020-005621:3(569-591)Online publication date: 1-Jun-2021
https://doi.org/10.1515/cmam-2020-0056
Schrader SWesthoff APiastra MMiinalainen TPursiainen SVorwerk JBrinck HWolters CEngwer C(2021)DUNEuro—A software toolbox for forward modeling in bioelectromagnetismPLOS ONE10.1371/journal.pone.025243116:6(e0252431)Online publication date: 4-Jun-2021
https://doi.org/10.1371/journal.pone.0252431
Makki KSalem DAmor B(2021)Toward the Assessment of Intrinsic Geometry of Implicit Brain MRI ManifoldsIEEE Access10.1109/ACCESS.2021.31136119(131054-131071)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3113611
Bastian PBlatt MDedner ADreier NEngwer CFritze RGräser CGrüninger CKempf DKlöfkorn ROhlberger MSander O(2021)The Dune framework: Basic concepts and recent developmentsComputers & Mathematics with Applications10.1016/j.camwa.2020.06.00781(75-112)Online publication date: Jan-2021
https://doi.org/10.1016/j.camwa.2020.06.007
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents