Elsevier

Journal of Computational Physics

Volume 273, 15 September 2014, Pages 393-415
Journal of Computational Physics

An accurate, robust, and easy-to-implement method for integration over arbitrary polyhedra: Application to embedded interface methods

https://doi.org/10.1016/j.jcp.2014.05.019Get rights and content

Abstract

We present an accurate method for the numerical integration of polynomials over arbitrary polyhedra. Using the divergence theorem, the method transforms the domain integral into integrals evaluated over the facets of the polyhedra. The necessity of performing symbolic computation during such transformation is eliminated by using one dimensional Gauss quadrature rule. The facet integrals are computed with the help of quadratures available for triangles and quadrilaterals. Numerical examples, in which the proposed method is used to integrate the weak form of the Navier–Stokes equations in an embedded interface method (EIM), are presented. The results show that our method is as accurate and generalized as the most widely used volume decomposition based methods. Moreover, since the method involves neither volume decomposition nor symbolic computations, it is much easier for computer implementation. Also, the present method is more efficient than other available integration methods based on the divergence theorem. Efficiency of the method is also compared with the volume decomposition based methods and moment fitting methods. To our knowledge, this is the first article that compares both accuracy and computational efficiency of methods relying on volume decomposition and those based on the divergence theorem.

Introduction

Consider the integration of a polynomial function F over the domain RRnIR=RFdR

Evaluation of (1) is of great practical relevance when R 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 F 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 ϕ={xiyjzk,i+j+kn} 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 R be the region in Rn bounded by the closed surface S. Let nˆ denote the outward normal of R on S then the divergence theorem states that for any vector field F defined on RRFdR=SFnˆdS

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 facetsRFdR=i=1NfFiG(x)nxdFi where Fi denotes the ith facet of the polyhedra, and Nf 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)

  • S.E. Mousavi et al.

    Generalized Gaussian quadrature rules for discontinuities and crack singularities in the extended finite element method

    Comput. Methods Appl. Mech. Eng.

    (2010)
  • Y. Sudhakar et al.

    Quadrature schemes for arbitrary convex/concave volumes and integration of weak form in Enriched Partition of Unity Methods

    Comput. Methods Appl. Mech. Eng.

    (2013)
  • H.T. Rathod et al.

    Integration of polynomials over linear polyhedra in Euclidean three-dimensional space

    Comput. Methods Appl. Mech. Eng.

    (1995)
  • X.W. Gao

    The radial integration method for evaluation of domain integrals with boundary-only discretization

    Eng. Anal. Bound. Elem.

    (2002)
  • I. Babuška et al.

    Effect of numerical integration on meshless methods

    Comput. Methods Appl. Mech. Eng.

    (2009)
  • D. Calhoun

    A Cartesian grid method for solving the two-dimensional streamfunction-vorticity equations in irregular regions

    J. Comput. Phys.

    (2002)
  • D. Russell et al.

    A Cartesian grid method for modeling multiple moving objects in 2D incompressible viscous flow

    J. Comput. Phys.

    (2003)
  • B. Schott et al.

    A new face-oriented stabilized XFEM approach for 2D and 3D incompressible Navier–Stokes equations

    Comput. Methods Appl. Mech. Eng.

    (2014)
  • G. Dasgupta

    Integration within polygonal finite elements

    J. Aerosp. Eng.

    (2003)
  • N. Sukumar et al.

    Confirming polygonal finite elements

    Int. J. Numer. Methods Eng.

    (2004)
  • M.M. Rashid et al.

    A three-dimensional finite element method with arbitrary polyhedral elements

    Int. J. Numer. Methods Eng.

    (2006)
  • M. Wicke et al.

    A finite element method on convex polyhedra

    Comput. Graph. Forum

    (2007)
  • P. Milbradt et al.

    Polytope finite elements

    Int. J. Numer. Methods Eng.

    (2008)
  • N. Sukumar et al.

    Extended finite element method for three-dimensional crack modelling

    Int. J. Numer. Methods Eng.

    (2000)
  • G. Ventura

    On the elimination of quadrature subcells for discontinuous functions in the eXtended Finite-Element Method

    Int. J. Numer. Methods Eng.

    (2006)
  • W.A. Wall et al.

    Fluid-structure interaction approaches on fixed grids based on two different domain decomposition ideas

    Int. J. Comput. Fluid Dyn.

    (2008)
  • J.P. Pereira et al.

    hp-Generalized FEM and crack surface representation for non-planar 3-D cracks

    Int. J. Numer. Methods Eng.

    (2009)
  • Cited by (63)

    • Robust numerical integration of embedded solids described in boundary representation

      2024, Computer Methods in Applied Mechanics and Engineering
    • Adaptive quadrature/cubature rule: Application to polytopes

      2023, Computer Methods in Applied Mechanics and Engineering
    • A 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 Physics
      Citation 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.

    • Unfitted finite element method for fully coupled poroelasticity with stabilization

      2022, Computer Methods in Applied Mechanics and Engineering
    View all citing articles on Scopus
    View full text