Slovak republik

e-mail: medvid@virgo.dam.fmph.uniba.sk

**This page created :
Jaroslav Placek (translation) &
Juraj Sofranko
(HTML) **

e-mail : 4Placek@st.fmph.uniba.sk;
4Sofranko@st.fmph.uniba.sk

Marshall Bern and David Eppstein, Mesh Generation and Optimal Triangulation, In: Computing in Euclidean Geometry, pp. 23-90, World Scientific 1992.

Jan Frykestig, Advancing Front Mesh Generation Techniques with Application to the Finite Element Method, Chalmers University of Technology, Göteborg, 1994.

Gabriela Bobáková, The Basic Data Structures of Computational Geometry and their Application in Language C and Pascal, Comenius University, Faculty of Mathematics and Physics, Bratislava, 1995. (in Slovak)

Many problems in engineering practice can only be solved on computers by the use of some numerical method, and in the engineering community the finite element method (FEM) is mostly used. Finite element methods have proved indispensable for physical simulation. These methods typically assume that the simulated domain - for example, the air around a wing - is divided into many small "elements", trinagles or quadrilaterals in two dimensions and tetrahedra or hexahedra in three ones. The complex of elements is the mesh. The purpose of the mesh is to provide the framework for the numerical solution of the engineering problem at hand. The decomposition of the domain into a mesh of elements is called mesh generation, and this, at first glance, seemingly simple problem is in fact so complex that it has limited the widespread use of the FEM.

A tringulation is a partition of a geometric input, typically the region defined by a point set or a polytop, into simplices that meet only shared faces. So in two dimensions, a triangulation consists of triangles that intersect only at shared edges and vertices. An optimal triangulation is one that is best according to some criterion that measures the size, shape, or number of simplices.

We discuss algorithms
for the optimization of triangulations on a fixed set of vertices
and briefly survey heuristic algorithms used in some practical
mesh generators.

Most numerical methods - there are exceptions - assume that the domain of interest is divided into a mesh of small, simple elements. There are two major types of meshes: structured and unstructured. This paper studies only unstructured meshes, but here we briefly sketch the larger context.

A** structured mesh**

Structured meshes offer certain advantages over unstructured. They are simpler, and also more convenient for use in the simpler finite difference methods. They require less computer memory, as their coordinates can be calculated, rather than explicitly stored. Finally, structured meshes offer more direct control over the sizes and shapes of elements.

The big disadvantage of a structured mesh is its lack of flexibility in fitting a domain with a complicated shape. A number of techniques have been developed to find appropriate coordinate transformations: conformal mapping, algebraic methods, and numerical methods that themselves solve differential equations. Even armed with these techniques, it may be impossible to find a transformation that fits a complicated domain acceptably well. Faced with this problem, some practitioners cut out a region of the grid, without any transformation, to give a "stair-case approximation" to the domain. But then the computed solution will be quite inaccurate near the boundary of the domain, an area that is often of special interest. Other practitioners break up the domain into simpler regions, perhaps overlapping, each of which can be more nearly matched by a deformed grid. This method and its associated numerical analysis make up "domain decomposition", a large area of study in its own right.

A finite element mesh
must use elements of appropriate size and shape, and these quantities
may vary over domain. Multiple requirements lead to many interesting
and difficult triangulation problems. These computational problems
and practical use of simulated annealing for solving this define
the subject of this paper.

The requirements for mesh
are similar to requirements of triangulation of geometric input.
For that reason except of finding correct mesh is replaced by
finding the triangulation.** D-unit **is convex hull of d+1
points in Euclidian space *R*^{d}, d2, which is not
included in any halfspace with dimension less than d.

**Defínition 1.
***Let M = {p_{i}
| i=1, 2, ..., n_{p}} be a set of n_{p} points,
n_{p}>d, from Euclidian space E^{d}, d2, with
convex hull
K. Then d-dimensional triangulation T = {t_{i
}| i=1, 2, ... n_{t}} is a set of
n_{t} d-units, which fulfills folowing propertiesi: *

*All the vertexes of each unit are from set M.**Unit interiors are by two disjunct.**Unification t*=1, ..., n_{i}, iconvex hull K._{t }gives the*Every d-1 dimensional entity is either on the border C, or inside C and then it is common exactly for two d-units.*

Triangulation in three dimensions is called tetrahedralization (or sometimes tetrahedrization). A tetrahedralization is a partition of the input domain, point set or polyhedron, into a collection of tetrahedra, that meet only at shared faces (vertices, edges, or triangles). Tetrahedralization turns out to be significantly more complicated than triangulation. As in two dimensions, n represents the number of vertices of the input domain, and we distinguish several different types of domains.

**Simple polyhedron.**A simple polyhedron is topologically equivalent to a sphere; it does not meet itself in a handle, or touch itself at a point or an edge. The boundary of such a polyhedron forms a connected planar graph. In triangulations without*Steiner points*, each tetrahedron's vertices must be vertices of the polyhedron.**Nonsimple polyhedron.**A nonsimple polyhedron may be multiply connected, topologically equivalent to a torus or a higher-genus surface. It may also have holes, meaning that its boundary is not connected.**Point set.**As in two dimensions, a triangulation of a point set fills the convex hull. If Steiner points are allowed, then the boundary of the triangulation may be a larger convex polytope.

In this section, we concentrate on existance and construction of tetrahedralizations, without concern for optimality. Existence and construction are already interesting, since many two-dimensional triangulation properties break down in three dimensions.

The first surprise is
that different triangulations of the very same input may contain
different numbers of tetrahedra. For example, choose *n*
points *v _{i}=(i,i^{2},i^{3}) *on
the

*Edelsbrunner, Preparata*,
and *West* in **Tetrahedrizing point sets in three dimensions
**show how to construct a linear-complexity tetrahedralization
of point sets. After tetrahedralizing the convex hull with only
linear complexity as above, interior points are added one at a
time. When a point is added, the tetrahedron containing it is
replaced by four smaller tetrahedra.

When we try to extend these results to nonconvex polyhedra, we meet a second surprise: not all polyhedra are tetrahedralizable. Consider a triangular prism, and twist one triangle relative to the other so that each rectangular face of the prism folds into two triangles with a reflex edge between them (Figure 1). Any set of four vertices must include a pair that face each other across such a reflex edge. So the polyhedron contains no tetrahedron, and tetrahedralization is impossible.

This polyhedron, known
as * Schönhardt's polyhedron *can be tetrahedralized
if we add one Steiner point. This leads to the question of how
many Steiner points may be required for tetrahedralization.

** Chazelle's polyhedron**
can be viewed as a cube, from which numerous thin wedges have
been removed. Wedges parallel to the

Figure 2 Chazelle's polyhedron

In this section, we consider three-dimensional optimal triangulation without Steiner points. Since Steiner points are required simply to tetrahedralize nonconvex polyhedra, this section treats only point sets (and as a special case, convex polyhedra). Even here very little is known, and this section has more open problems than results. Since a single input has tetrahedralizations of different complexity, a natural optimization question asks for a minimum-complexity tetrahedralization of a point set.

* *The
Delaunay triangulation (DT) in three dimensions contains each
tetrahedron with vertices from the input point set, whose circumsphere
contains no other input points on its surface or in its interior.
Assuming general position, in which no five points lie on a single
sphere, so this defines a triangulation. The complexity of the
DT may be as high as (n

We can use the *lifting*
transformation. We map an input point with Cartesian coordinates
(*x,y,z*) to the point (*x,y,z,x ^{2}+y^{2}+z^{2
}*). The image points all lie on a paraboloid in four
dimensions; the projection of the lower convex hull back onto
the

There are also direct
algorhims. *Bowyer *and *Watson* gave incremental algorithms
that are quite popular in practice. Watson's algorithm inserts
points in sorted order by one coordinate, testing all old circumspheres
that intersect the current sweep plane. Bowyer includes evidence
that his algorithm runs in time O(n^{4/3}) for a random
point set.

Use of DT in 3D does not
grant well-shaped tetrahedras. As it is shown at the picture,
tetrahedron vertex can move on the sphere surface, so we get tetrahedron
with too small volume. This type of tetrahedron must be removed
from tetrahedralization. We replace it with tetrahedron got by
inserting of the new point or by moving the inner point in tetrahedralization.

* Joe*
and *Rajan* generalized the flip algorithm for DT construction.
In three dimensions, flips involve sets of five points, forming
a tetrahedral bipyramid. Such a figure can be tetrahedralized
in two ways: either as a pair of tetrahedra separated by a face,
or as three tetrahedra surrounding an interior diagonal. Thus
flips trade two tetrahedra for three, or vice versa. Starting
from an arbitrary tetrahedralization, however, the flip algorithm
can get stuck in a local optimum and fail to produce the DT.

*Joe* showed that,
if we start with the DT of some point set, and add a single point
(dividing the tetrahedron containing it into four, or if the new
point is outside the convex hull, adding tetrahedra connecting
it to the triangles it can see), then flipping from the resulting
triangulation never gets stuck. All tetrahedra involved in flips
are neighbors of the new vertex, so in some sense this flipping
procedure becomes two- rather than three-dimensional. This result
gives another O(n^{2})-time algorithm for computing the
DT: add points one by one (say, in sorted order by *x*-coordinate)
and, after each addition, flip until the DT is reached. Rajan
described a similar procedure for incrementally adding points
and flipping tetrahedra to find the DT. His procedure flips tetrahedra
in the order corresponding to the changes in the convex hull of
the lifted points as the new point is moved vertically down onto
the paraboloid. Thus, Rajan's algorithm generalizes to higher-dimensional
DT construction.

Because the DT posseses
so many optimality properties in two dimensions, geometers long
suspected that it should optimize something in three dimensions.
Recently, *Rajan* discovered the first such result. (His
result actually holds in all dimensions.) The * min-containment
sphere *of a simplex

**Theorem. ***The Delaunay triangulation is the triangulation that minimizes
the maximum radius of a min-containment sphere.*

* Proof Sketch: *
Lift the points to the paraboloid (

Most of the techniques for generating and improving two-dimensional meshes can be generalized to three dimensions, such as Octrees, Laplacian smoothing, Polyhedron decomposition, Advancing front, though not without some difficulties. Overall, three-dimensional unstructured mesh generation is still in its early stages of development.

Laplacian smoothing (when
vertex *v* in the interior of the mesh is moved to the centroid
of the polygon formed by its neighbors) generalizes to three dimensions
but the improvement it offers may not be as significant as in
two dimensions.

There are local transformations that trade two tetrahedra for three, and three tetrahedra for two, as it was discussed above. These transformations give the analog of the flip procedure in two dimensions, and may be used to improve a triangulation according to some criterion, such as the Delaunay empty circumsphere condition. In three dimensions, however, the flip procedure may get stuck in a local optimum that is not a global optimum. It is already known, that for the Delaunay criterion, special starting triangulations always lead to a global optimum.

The characterizing feature of the advancing front method is that nodes and elements are created simultaneously starting from the boundary of the domain of interest. In three dimensions, the initial front is created from the triangular facets of the boundary surface meshes. A triangle on the front is selected, and a tetrahedron is formed by placing a new node in a position so that the size of the tetrahedron satisfies the desired mesh size. Alternatively, an existing node is used if this results in a bettershaped tetrahedron. Following the construction of the tetrahedron, the front is updated in that facets no longer on the front are deleted and new facets are added. This procedure is repeated until the front is empty.

* Algorithm of simulated
annealing* (ASA) is an algorithm for global optimization
of very complex functions. This heuristic algorithm issues from
process of annealing, crystallization of melt with very slow reducing
of temperature to the point of gelation. The physical system is
simulated by generation of random variety of atom configuration.
The variety is acceptable, if it caused reduction of energetic
level. Otherwise, the variety is accepted with particular expectation.

*G. Bobáková*
used the ASA-method for the solution of the minimum weight triangulation
problem. The desired algorithm for finding of the minimum weight
triangulation consits in flipping triangulation edges to reduce
the global sum of edge lengths. It can increase the global sum
during annealing process. This is the way to find the global minimum
of global sum. She achieved unusual results and tendered some
hypothesis:

**Process of annealing can move in space of all triangulations and through suitable quality measure function find out the optimal triangulation of necessary properties.**Studying of some annealing processes returned an information, that triangulation created by one triangulation algorithm can transform to triangulation created by another algorithm.**Every annealing process is useful to be next to minimum weight triangulation.**There was an experiment with classic triangulations, which were well-known as a minimal triangulation. The triangulation edges remitted after certain number of flips.

In this chapter I'll describe a method, which I used for generating the depth mesh

of point set in the space.
This method uses simulated annealing algorithm. Initial triangulation
is not randomized state but it is Delaunay triangulation created
by "divide and conquer" algorithm. As we have shown,
this classic triangulation in the space does not grant so much
optimizing properties as it is in the plane. Exactly simulated
annealing method would grant results which will approximate wanted
properties of the mesh. This method is namely robust algorithm
for searching global minimum of real function defined in the set
*R*^{n}.

The goal of the method
is to find optimal mesh, respectively mesh with properties mostly
approximating initial user requierements. The mesh with lowest
price with respect to **price function **will be understood
as optimal mesh**. **__Price function__ is weight sum of
several purpose functions. In described method I aimed at creation
of the mesh with lowest price, if price function evaluated tetrahedron
curvature, total sum of mesh edges lenght and number of tetrahedrons.
These criteria are important for threedimensional mesh creation.
It is important for FEM(Finite Element Methods) that mesh cannot
contain degenerated elements. Exactly disturbation criterion reveals
these elements in the mesh.

Especially in 3D, the measure aspect ratio

is the most often choice for disturbation measure of four-faced elements,

where *R* is a diameter
of circumsphere of tetrahedron and *r* is a diameter of the
smallest sphere embraced i