ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2010, том 50, № 1, с. 44-59
УДК 519.63
BOUNDARY CONFORMING DELAUNAY MESH GENERATION © 2010 K. Gärtner, H. Si, J. Fuhrmann
(Berlin, Weierstrass Institute for Applied Analysis and Stochastics) e-mail: {si, fuhrmann, gaertner}@wias-berlin.de Received November 27, 2008; in final form July 7, 2009
A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay sim-plices such that all boundary simplices satisfy the generalized Gabriel property. It's dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains, however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by arccos 1/3 « 70.53°. In addition, well-shaped tetrahedra and appropriate mesh size can be obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical guarantee on the input angle (70.53°) is still too strong for many practical situations. We further discuss variants of the algorithm to relax the input angle restriction and to improve the mesh quality.
Key words: Delaunay mesh, Voronoi partitions, partitions of polyhedra.
К. Гартнер, Г. Си, Дж. Фурман. Построение сеток Делоне, согласованных с границами. Изучается разбиение многогранной области на симплексы Делоне такое, что все граничные симплексы удовлетворяют обобщенному условию Габриэля. Разбиение Вороного этой же области является двойственным разбиению Делоне, и оказывается предпочтительным при использовании методов конечного объема на ячейках Вороного. Для произвольных двумерных многоугольных областей можно строить оптимальные по размерности сетки с оптимальной вычислительной сложностью. Для произвольных трехмерных многогранных областей эта задача остается нерешенной. Основной результат данной статьи заключается в том, что существует эффективный алгоритм построения сеток Делоне, сообразных границе, внутри трехмерных многогранных областей, если минимальный входящий угол между смежными гранями изнутри области ограничен снизу величиной arccos 1/3 « 70.53°. К тому же, можно получить заданное распределение размера тетраэдров сетки притом, что мера искажения формы тетраэдров ограничена сверху. Новые результаты получены посредством анализа классического метода сгущения сеток Делоне. Заметим, что полученная теоретическая гарантия по входному углу (70.53°) все еще слишком жесткая для многих практических случаев. Обсуждаются варианты алгоритма построения сеток, позволяющие ослабить требования к углу и улучшить качество сетки. Библ. 29. Фиг. 12. Табл. 1.
Ключевые слова: сетки Делоне, разбиения Вороного, разбиение многогранников.
1. VORONOI FINITE VOLUMES
Physical problems governed by conservation laws are often treated by finite volume methods. The motivation behind the focus on boundary conforming Delaunay meshing is the Voronoi box based finite volume method for PDEs. It allows to carry important qualitative properties from the continuous to the discrete level. To give a short description of this method. We consider the convection-diffusion problem
ct - V-( D Vc - c v) = 0, (x, t)eQx[ 0, T], (1)
on a 2D or 3D domain Q with appropriate initial and boundary conditions. Here, c can be seen e.g. as a species concentration, D is a diffusion coefficient, and v is a velocity field or a potential gradient (V^). This setting includes solute transport in fluids and charge carrier transport in semiconductor devices. For Di-richlet boundary conditions and V ■ v = 0, c is bounded from below and above by its boundary and initial values. If the lower bound is nonnegative, c stays nonnegative. The Voronoi box based finite volume method
(see [1]), known also as "box method", "control volume method", allows to carry over this maximum principle to the discretized equations.
Given a partition of Q whose cells (called control volumes) are all Voronoi cells [2] (see Fig. 1 for examples) and a partition 0 = fi < ... < tn = T, for each space-time control volume K x (tn - 1, tn), we integrate (1), and apply the Gauss theorem to the integral of the flux divergence. After choosing a quadrature in time which yields an implicit scheme, and dividing by the time difference, with cn = c(tn, x) we arrive at
n n - 1
^- - c- - dx - J(DVcn - cnv) • nKds = 0. (2)
K ^ - ^ dK
Splitting the surface integral into contributions from the facets common with the neighboring control volumes L e N(K), applying quadrature rules, and introducing the flux function g(cK, cL, vKL) to approximate the scaled normal flux (—DVc + cv) • (xK — xL) through a common facet <jKL = dK n dL yields
n n - 1 ||
\KCCKr^h + Z P^lg(c- cL, Vkl) = 0. (3)
tn - tn-1 ^ xK- xL
' ' L e M(K) K L
Here, cK is the average value of cn in K, and = --; v • nds is the average normal flux of v through aK£.
Fk^I JaKL
Any consistent upwind 1D finite difference expression of the flux along xKxL defines a flux function g which leads to a stable and converging scheme. A preferable choice is the exponential fitting scheme [3, ..., 5] which can be derived from the analytical solution of a two-point boundary value problem arising from the projection of (1) onto xKxL (see [6]).
Per time step, this approach yields a linear system of equations cn + Ac" = Bcn -1 where B is a positive diagonal matrix, and the graph of A is connected, A has column sum zero, non-positive off-diagonal entries and nonnegative main diagonal entries. Therefore I + B-1A has the M-property (see [7]), immediately resulting in cn > 0, once cn -1 > 0. A convergence theory for finite volume methods which covers the Voronoi case is available in [8]. Discrete theory for the nonlinear case, including a proof of the local maximum principle for interior points can be found in [9]. A generalization of exponential fitting to the nonlinear case is available in [6]. Coupled equations, where v = Уф are handled in [10]—[12]. In particular, [10] contains a proof of the dissipativity of the scheme. Coupling to the pointwise divergence free Scott Vogelius finite element for the Navier—Stokes equation has performed in [13].
Fig. 2. A three-dimensional polyhedral domain (left) and its partition with all simplices (right).
A prerequisite for applying the Voronoi finite volume method for solving PDEs defined on an arbitrary domain Q is to generate a partition of Q which has certain desired properties. For example, one basic geometrical requirement is that all control volumes are Voronoi cells.
2. BOUNDARY CONFORMING DELAUNAY MESHES
3
Let Q с R be a physical domain for numerical simulation. The boundary of Q is denoted as dQ. An example of a polyhedral domain is shown in Fig. 2 (top). In this paper, we assume that dQ consists of polyhedral surface. It is necessary that Q contains internal boundaries which may separate itself into sub-domains so that the discontinuity between different materials can be modeled. Hence Q is in general not a topological manifold.
A partition of Q is a finite set 2Г of simple cells such that: (i) any two cells of 2Г are either disjoint or intersect at their common face, (ii) the union of 2Г equals to Q, and (iii) dQ is represented by the union of
a subset of 2Г. Each cell in 2Г may be any convex polytope. The simplest cell is called a simplex, e.g., edges,
3
triangles, and tetrahedral are simplices in R . Figure 2 (right) shows a partition of simplices.
Let S be a finite set of points in R . A simplex a in S is Delaunay (see [14]) if it has a circumscribed sphere Z such that no other point of S lies inside Z. Moreover, a is Gabriel (see [15]) if no other point of S lies inside the diametrical sphere of a, i.e., the smallest circumscribed sphere of a. A boundary conforming Delaunay mesh of a domain Q is partition of Q into a set 2Г of simplices with the following properties
(i) every simplex in Q is Delaunay, and
(ii) every simplex in dQ is Gabriel.
Property (i) ensures that the dual of^ is a Voronoi partition ofQ. However, such a partition may not satisfy the requirements of the Voronoi-box based finite volume scheme. A critical case is illustrated in Fig. 3 (left). A Voronoi cell from one sub-domain may cross an internal boundary if the simplex on dQ does not have the Gabriel property. If such case happens, equation (2) may not be evaluated correctly (since the diffusion coefficient D may be discontinuous at dQ). The property (ii) is included for avoiding such cases, see Fig. 3 (right).
The Meshing Problem. We consider the following problem: Given a three-dimensional domain Q, generate a boundary conforming Delaunay mesh 2Г of Q such that (1) the mesh size (e.g., the number of nodes, and elements) of 2Г is bounded, and (2) the mesh quality of 2Г is optimal.
The two extra requirements are generally needed by numerical methods for achieving high accuracy with low computational costs. Note that the term "mesh quality" depends on the given PDE system. One of the essential requirements on mesh quality is the element shape. A general shape measure is the aspect ratio X which is defined as the ratio between the largest and smallest diameter of the element. A smaller X implies a better shape. For a tetrahedron т, the minimum dihedral angle 0(x) between two faces of т is also a shape measure.
Fig. 3. Edge ab is in dQ. Left is a Delaunay mesh of Q whose dual is a Voronoi partion of Q. Since ab does not have the Gabriel property, the Voronoi cell Ki of one subregion intersects with ab. The mesh in the right is a boundary conforming Delaunay mesh of Q.
Fig. 4. A 3D piecewise linear system (PLS) %. Here x contains 2 cells (3-polytopes), 16 facets (2-polytopes), 37 segments
(1-polytopes),
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.