An accurate, robust, and easy-to-implement method for integration over arbitrary polyhedra: Application to embedded interface methods
Introduction
Consider the integration of a polynomial function over the domain
Evaluation of (1) is of great practical relevance when is an arbitrary shaped polygon or polyhedron, since such integrations arise frequently in computational modeling and simulations in a variety of fields. Some notable applications include polygonal and polyhedral finite element methods [1], [2], [3], [4], [5], [6], embedded interface methods [7], [8], [9], [10], [11], [12], [13], [14], [15], level set based methods [16], [17], [18], [19], electronic structure calculations [20], [21], aerospace applications [22], [23], [24], computational geometry [25], [26], [27] etc. The general characteristic of many of these applications is that the integrand is not explicitly available, but is constructed during the solution process. As reviewed in the following text, most of the available methods to handle such integrations are either very complicated to implement or they are not accurate enough. Our objective is to devise an efficient and generalized, but easy-to-implement method to accurately approximate the above integral. The present work is motivated by our interest in developing an efficient embedded interface method (EIM) to handle complex fluid-structure interaction (FSI) and multiphase flow problems [13], [18], [28], [29], [30], [31]. In EIM, evaluation of stiffness matrices over the elements that are cut by the interface requires computation of such integrals over arbitrary polyhedral shaped volume cells (weak form integration) as shown in Fig. 1. Accuracy of the weak form integration over these volume cells largely influences the overall solution accuracy. Moreover, in transient FSI and multiphase flow problems, since the interface changes its position and shape with time, the geometrical cutting operations and construction of integration method for the volume cells are performed at each time step. Hence, an accurate and efficient method to evaluate equation (1) over arbitrary polyhedra is an essential prerequisite to develop efficient EIMs.
Since the integration over polyhedra is important across a wide variety of fields, it is impossible to review all the available works. Hence we make note only of the methods that are related to the finite element literature.
Three important class of integration methods that are used in FEM are
- 1.
Tessellation
- 2.
Moment fitting methods
- 3.
Methods based on the divergence theorem
In most works, the integration over a polyhedron is accomplished by the tessellation procedure, which involves a volume decomposition process [5], [7], [11], [13], [15], [32]. First, the given polyhedron is decomposed into a number of tetrahedra. Then, the polynomial is integrated over each of these tetrahedra, and summed up to get the integral value over the polyhedron. Though tessellation yields accurate value of integrals, the associated volume decomposition procedure is complicated to implement, especially when one aims at robust methods for complex problems.
Other methods, which do not involve volume decomposition process, either solve the moment fitting equations or use the divergence theorem.
In moment fitting methods, to obtain a quadrature rule of order n, all the monomials are integrated over the polyhedra. Then, a quadrature rule is fit to integrate these monomials exactly [33], [34], [35], [36], [37], [38]. The method used to integrate ϕ decides the applicability of such procedures. For example, in [36], Lasserre's method is used to integrate ϕ which limits the applicability of such a procedure to convex volumes. By using the divergence theorem to accomplish the integration of ϕ, the method is extended to deal with both convex and concave volumes in [37]. The drawbacks of this class of methods are the difficulty to obtain the location of quadrature points in three dimensional problems, and it is slightly less accurate when compared to tessellation when used for EIMs [37].
Various researchers have used the divergence theorem to perform integration over arbitrary polygons and polyhedra. The divergence theorem is used to simplify the domain integral into integration along the boundaries of the domain that can be easily evaluated. However, almost all the available methods of this kind either assume that the integrand of interest is predefined [6], [25], [26], [27], [39], [40], or rely on symbolic computations to integrate generalized functions [1], [41]. There are severe arguments against using these methods in a general finite element framework, since
- •
the integrand is not explicitly available in FEM (but can be computed at any point within the domain of interest)
- •
the FE framework targets large scale problems, and coupling such efficiently tuned codes (usually written in C++) with symbolic computation packages significantly slows down the execution speed.
In recent works [42], [43], aimed at efficient integration in boundary element methods, the researchers eliminate the symbolic computation by using radial basis function or Gauss quadrature. A similar procedure for 2D polygons is described also in [44]. However, [42], [44] deal only with polygons, and in [43] the method is used for integration over simple volumes only. These references do not address the integration over complex volumes, and more importantly the efficiency of these methods is not reported.
In summary, each of the aforementioned methods has its own shortcomings: the volume decomposition process involved in tessellation is highly complicated to implement and usually lacks robustness, moment fitting methods are less accurate for some special polyhedra, and the existing methods based on the divergence theorem cannot be used in a general FEM framework. In this article, we propose an accurate, robust, efficient and easy-to-implement method for numerical integration of polynomials that are not explicitly pre-specified, over arbitrarily complex shaped polyhedra. Our method involves the application of the divergence theorem to convert the volume integral to surface integrals over the facets of the polyhedra. We eliminate the need for symbolic computation by using one-dimensional Gauss quadrature rule, as in [43], [44]. We implemented this method in BACI, the FEM multiphysics solver developed in our institute, to integrate the weak form of the Navier–Stokes equations over the cut elements arising in EIM as the first example application class.
In this paper, we do not focus on the derivation of weak form in EIMs. It is assumed that the weak form is already available and the integration method is described in detail. The present method is explained for polygons in Section 2. In Section 3, the integration procedure over 3D polyhedra is described. A method to split the arbitrary facets of polyhedra into triangular and quadrilateral cells, which greatly enhances the performance of the present method when compared to [43], [44], is explained in Section 4. More emphasis is placed on the implementation aspects in the above sections. In Section 5, numerical examples that demonstrate the robustness, accuracy and computational efficiency of the present method are described.
Section snippets
Integration over polygons
Though the main objective of this work is the integration of polynomials over complex 3D polyhedra, for brevity, the method is first explained for 2D polygons. As already stated, the present method makes use of the divergence theorem to convert the domain integral into boundary integral.
Let be the region in bounded by the closed surface . Let denote the outward normal of on then the divergence theorem states that for any vector field F defined on
Since our
Integration over polyhedra
In this section, the present method is explained for performing integration over arbitrary polyhedra. The polyhedra are defined by their facets, the same way as the polygons are built by their edges. Application of the divergence theorem converts the domain integral into integrals evaluated over the facets where denotes the ith facet of the polyhedra, and is the total number of facets.
The procedure is very similar to the one described for polygons. All operations
Facet splitting
As explained above, when a facet of a polyhedron has more than 4 vertices, mapping the main Gauss points over these facets is not straightforward. Such facets can be triangulated, the mapping can be done over each of the resulting Tri. (In this section, the abbreviations Tri and Quad are used for triangular cell and quadrilateral cell respectively.) However, as will be shown in the following text, triangulation will result in a large number of main Gauss points, which may deteriorate the
Numerical examples
As stated in the introduction, one motivation and example application of the present work is to integrate the weak form of the Navier–Stokes equations over the cut elements in EIM. We consider this to be an appropriate example application since the fluid flow simulations are very sensitive to the accuracy of the weak form integration. To demonstrate the robustness, accuracy and efficiency of the proposed method for such applications, we present results of some EIM simulations in which the
Conclusion
We proposed a method based on the divergence theorem to integrate polynomials over arbitrary polyhedra. We implemented this method in our generalized finite element framework to integrate the weak form of the Navier–Stokes equations in EIMs. The present method is robust as it is capable of constructing accurate quadrature schemes for arbitrarily complex shaped polyhedra. Also, a simple fluid flow example demonstrated that the present method is more accurate than its alternatives, namely
Acknowledgements
We thank Ulrich Küttler for developing the geometrical cut libraries. The financial support from ATCoMe (238548) project through seventh framework programme is gratefully acknowledged. We also acknowledge the support through the International Graduate School of Science and Engineering (IGSSE) of the Technische Universität München, Germany, under project 6.02.
References (54)
- et al.
Flexible simulation of deformable models using discontinuous Galerkin FEM
Graph. Models
(2009) - et al.
The generalized finite element method
Comput. Methods Appl. Mech. Eng.
(2001) - et al.
Hierarchical X-FEM for n-phase flow ()
Comput. Methods Appl. Mech. Eng.
(2009) - et al.
Geometric integration over irregular domains with application to level-set methods
J. Comput. Phys.
(2007) - et al.
An efficient fluid–solid coupling algorithm for single-phase flows
J. Comput. Phys.
(2009) - et al.
An extended residual-based variational multiscale method for two-phase flow including surface tension
Comput. Methods Appl. Mech. Eng.
(2011) - et al.
A second-order sharp numerical method for solving the linear elasticity equations on irregular domains and adaptive grids – application to shape optimization
J. Comput. Phys.
(2013) Inertia of any polyhedron
Icarus
(1996)- et al.
Boundary integration over linear polyhedra
Comput. Aided Des.
(1990) - et al.
An extended finite element method/Lagrange multiplier based approach for fluid-structure interaction
Comput. Methods Appl. Mech. Eng.
(2008)
Generalized Gaussian quadrature rules for discontinuities and crack singularities in the extended finite element method
Comput. Methods Appl. Mech. Eng.
Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in Enriched Partition of Unity Methods
Comput. Methods Appl. Mech. Eng.
Integration of polynomials over linear polyhedra in Euclidean three-dimensional space
Comput. Methods Appl. Mech. Eng.
The radial integration method for evaluation of domain integrals with boundary-only discretization
Eng. Anal. Bound. Elem.
Effect of numerical integration on meshless methods
Comput. Methods Appl. Mech. Eng.
A Cartesian grid method for solving the two-dimensional streamfunction-vorticity equations in irregular regions
J. Comput. Phys.
A Cartesian grid method for modeling multiple moving objects in 2D incompressible viscous flow
J. Comput. Phys.
A new face-oriented stabilized XFEM approach for 2D and 3D incompressible Navier–Stokes equations
Comput. Methods Appl. Mech. Eng.
Integration within polygonal finite elements
J. Aerosp. Eng.
Confirming polygonal finite elements
Int. J. Numer. Methods Eng.
A three-dimensional finite element method with arbitrary polyhedral elements
Int. J. Numer. Methods Eng.
A finite element method on convex polyhedra
Comput. Graph. Forum
Polytope finite elements
Int. J. Numer. Methods Eng.
Extended finite element method for three-dimensional crack modelling
Int. J. Numer. Methods Eng.
On the elimination of quadrature subcells for discontinuous functions in the eXtended Finite-Element Method
Int. J. Numer. Methods Eng.
Fluid-structure interaction approaches on fixed grids based on two different domain decomposition ideas
Int. J. Comput. Fluid Dyn.
hp-Generalized FEM and crack surface representation for non-planar 3-D cracks
Int. J. Numer. Methods Eng.
Cited by (63)
Robust numerical integration of embedded solids described in boundary representation
2024, Computer Methods in Applied Mechanics and EngineeringTetraFreeQ: Tetrahedra-free quadrature on polyhedral elements
2023, Applied Numerical MathematicsAdaptive quadrature/cubature rule: Application to polytopes
2023, Computer Methods in Applied Mechanics and EngineeringA fast, high-order scheme for evaluating volume potentials on complex 2D geometries via area-to-line integral conversion and domain mappings
2023, Journal of Computational PhysicsCitation Excerpt :To address the challenges of multi-dimensional quadrature over potentially arbitrary regions, a variety of works have converted a volumetric integral of interest with a smooth integrand to integration along domain boundaries (potentially after some degree of domain-decomposition), after which numerical quadrature rules are used for various resulting one-dimensional integrals. Much of this work is focused on cubature for polyhedra, where we note contributions for this purpose [43,44] based on theorems of vector calculus. One approach [45] treats volumes bounded by rational parametric curves using Green's theorem, while others [46,47] produce volume quadratures over implicitly-defined surfaces and volumes by a recursive dimensional-reductional algorithm and ultimately result in one-dimensional integrals that can be treated with Gaussian quadrature.
Octree-based integration scheme with merged sub-cells for the finite cell method: Application to non-linear problems in 3D
2022, Computer Methods in Applied Mechanics and EngineeringUnfitted finite element method for fully coupled poroelasticity with stabilization
2022, Computer Methods in Applied Mechanics and Engineering