Unstructured Grids.
Delaunay Method.
V. Selmin
Multidisciplinary Computation and Numerical Simulation
Advancing Front Method
• Elements, i.e. triangles and tetrahedra, and points are generated simultaneously.
• Enables the generation of elements of variable size and stretching.
• Differs from the approach followed in tetrahedral generators which are based upon
Delaunay concepts which generally connect grid points which have already been
distributed in space.
• The generation problem consists of subdividing an arbitrarily complex domain into
a consistent assembly of elements.
• The consistency of the generated mesh is guaranteed if the generated elements
cover the entire domain and the intersection between elements occurs only on
common points, sides or triangular faces in the three dimensional case.
• The process start by discretising each boundary curve.
Nodes are placed on the boundary curve components and then contiguous nodes are
joined with straight line segments.
• In later stages of the generation process, these segments will become sides of some
triangles.
• The length of these segments must be consistent with the desired local distribution
of mesh size.
• This operation is repeated for each boundary curve in turn.
Advancing Front Method
Advancing Front Method
• Next stage consists of generating triangular planar faces.
For each two dimensional region or surface to be dicretised, all the edges produced
when discretising its boundary curves are assembled into the so-called initial front.
• The relative orientation of the curve components with respect to the surface must be
taken into account in order to give the correct orientation to the sides in the initial
front. The front is a dynamic data structure which changes continuously during the
generation process.
• At any given time, the front contains the set of all the sides which are currently
available to form a triangular face.
• A side is selected from the front and a tringular element is generated.
This may involve creating a new node or simply connecting to an existing one.
• After the triangle has been generated, the front is updated and the generation proceed
until the front is empty.
• The size and shape of the generated triangles must be consistent with the local
desired size and shape of the final mesh.
Advancing Front Method
Delaunay Method
In the classical front advancing method, the nodes coordinates are built at the same time as the elements from
the knowledge of the size of the elements that belong to the front and the spacing distribution.
In the Delaunay method, a triangulation of the domain from the knowledge of the boundary discretisation is first
performed.
Recursively, nodes are added in order to satisfy the imposed spacing distribution and new triangulation is performed
in order to taking into account the insertion of new nodes.
Delauney Method
Delaunay Method
Dato un insieme di punti
{P}, per ogni punto si
definisce la sua regione
di Voronoi (ovvero la
regione di piano più
vicina al punto Pi che ad
ogni altro punto)
Delaunay Method
Delaunay Method
I punti che hanno in
comune un lato della
propria regione di
Voronoi vengono
connessi, ottenendo
la triangolazione di
Delaunay.
Delaunay Method
Delaunay Method
La triangolazione di Delaunay
gode della proprietà del cerchio
circoscritto. I vertici delle
regioni di Voronoi sono i
circocentri delle circonferenze
che passano per i vertici di ogni
triangolo. Nessun punto, ad
eccezione di quelli che formano
i triangoli, può cadere
all’interno di una circonferenza.
Delaunay Method
Su questo criterio si basa
l’algoritmo di Bowyer-Watson
Bowyer-Watson Algorithm
1. Si definisce il guscio
convesso (poligono) che
contiene l’insieme dei punti
{P} che deve essere
connesso.
2. Si inserisce un nuovo punto
Pi all’interno del guscio.
3. Si definisce la base B(Pi),
ovvero si cercano i triangoli
che contengono il punto Pi al
loro interno.
Delaunay Method
Bowyer-Watson Algorithm
4. Si definisce la cavità
C(Pi), ovvero a partire
dalla base B(Pi), si
cercano tutti i triangoli
che contengono
all’interno del loro
cerchio circoscritto il
punto Pi.
Delaunay Method
Bowyer-Watson Algorithm
4. I lati interni
della cavità
sono cancellati
e il punto Pi è
connesso con i
punti
appartenenti al
contorno della
cavità.
5. Gli step 2-5 sono
ripetuti per ogni
punto
dell’insieme {P}.
Delaunay Method
Basis Generation
Per trovare il triangolo
contenente il punto Pi,
viene applicato il test
del semispazio.
Per mezzo di questo test, si può
valutare a quale dei due
semispazi, individuati dai punti
A e B, appartenga il punto C.
Applicando questa
logica ai lati dei
triangoli si giunge a
quello contenente
il punto Pi.
Delaunay Method
Cavity Generation
Sia K il triangolo di cui deve
essere valutato l’inserimento
nella cavità rispetto al punto
Pi.
Sia rK il raggio del cerchio
circoscritto al triangolo K. Si
definisce la misura di Delaunay
a(Pi,K):
d (O, K )
a ( Pi, K ) 
rK
E’ necessario che sia verificato a(Pi,K) < 1,
affinchè K sia aggiunto alla cavità.
Delaunay Method
Examples
Connessione di un
insiemi di punti
Delaunay Method
Boundary Recovery
Sia dato un insieme di
punti che definisce il
contorno di un certo
dominio.
La costruzione di Delaunay
non garantisce che i lati e le
facce del contorno siano
contenute all’interno della
triangolazione
Alla fine della fase di connessione è
necessario eseguire un controllo sulla
triangolazione, modificando
localmente gli elementi in modo
da renderli conformi con il
contorno del dominio
Delaunay Method
Boundary Recovery
Caso 2D: in una triangolazione bidimensionale
possono mancare dei lati di contorno. Il recupero
viene fatto attraverso l’inserzione di nuovi punti
sul contorno del dominio, lungo la direzione del
lato mancante.
Delaunay Method
Boundary Recovery
Caso 3D: in una triangolazione tridimensionale possono
mancare lati e facce del contorno. Il recupero viene fatto
attraverso:
1. Lo swapping dei triangoli sulle superfici connesse.
2. Lo swapping degli spigoli dei tetraedri.
3. L’inserzione di nuovi punti in posizioni opportune.
Delaunay Method
Boundary Recovery
Swapping dei triangoli su una superficie connessa. E’ possibile
che nella connettività della triangolazione superficiale esistano dei
triangoli che non coincidono con alcuna faccia dei tetraedri. Il
recupero degli elementi può essere effettuato cambiando semplicemente
la connettività dei nodi dei triangoli.
Se questa modalità di
recupero non è sufficiente, è
necessario ricorrere alle
modalità (2) e (3).
Delaunay Method
Boundary Recovery
Recupero dei lati e delle
facce di contorno attraverso
la swapping degli spigoli e
l’inserzione di nuovi punti.
Lo swapping può essere
utilizzato per
•recuperare un lato, passando
da una configurazione a due
tetraedri ad una con tre,
•recuperare una faccia,
passando da una
configurazione a tre tetraedri ad
una con due.
Delaunay Method
Boundary Recovery
Ci sono tuttavia alcune configurazioni a cui non è possibile applicare lo
swapping.
Si ricorre all’inserzione di nuovi
punti, che sono posizionati sul lato o
sulla faccia da recuperare.
Delaunay Method
Examples
Delaunay Method
Examples
Delaunay Method
Characteristic Dimension Parameters
The geometrical characteristics of an element can be defined in terms of the following mesh parameters.
If n is the number of dimensions, the parameters used are a set of n orthogonal directions α i and n
associated element sizes  i .
The transformation T may be defined as the result of superposing n scaling operations with factor 1 /  i
in each α i direction:
n
T
1
i 1  i
Metric matrix
Delaunay Method
α i α Ti
→ M  TT T
Characteristic Dimension Parameters
The effect of the transformation T
n
T
1
i 1  i
α i α Ti
in two dimensions is illustrated for the case of constant mesh size throughout the domain.
Delaunay Method
Anisotropic Triangulation
La costruzione di una
triangolazione
anisotropa è un
campo di interesse
relativamente recente.
Sono utilizzate per la risoluzione
di problemi in cui la soluzione
varia molto rapidamente e/o ha
direzioni di sviluppo
preferenziali.
Necessità di estendere
l’algoritmo di
Bowyer-Watson al
caso anisotropo
Necessità di fornire
informazioni riguardanti la
spaziatura dei punti nelle
diverse direzioni (metrica)
Delaunay Method
Anisotropic Triangulation
Interpretazione geometrica della metrica. Ad ogni punto
Pi del dominio è associato una metrica (o tensore metrico)
 aPi bPi 

M ( Pi )  
 bPi cPi 
che è una matrice simmetrica, definita positiva.
La lunghezza del segmento P1P2 vale
1
t
dM ( P1, P 2)   P1P 2  M ( P1  t P1P 2)  P1P 2dt
0
Delaunay Method
Anisotropic Triangulation
Effettuando una decomposizione spettrale di M, si ottiene M = Pt L P in cui
 l 0 
L  

 0 l
presenta sulla diagonale gli autovalori li associati ad M.
Effettuando una rotazione q, in modo che gli
assi cartesiani coincidana con gli assi
principali d’inerzia, la metrica definisce in
ogni punto un cerchio unitario di equazione
e12 e22
1
 2  1 con li  2
2
h1
h2
hi
dove hi rappresenta la lunghezza unitaria
lungo gli assi principali
Delaunay Method
Indirect Approach
Delaunay Method

The surface geometry can be defined by means of
polynomial parametric patches.

In this case the “indirect approach” to surface mesh
generation can be used

It consists in generating the mesh in the parametric
domain of the patch and mapping it onto the surface
in R3.
Indirect Approach
3D surface geometric definition
M3 is defined by analysing
the surface curvature
M3
M2 is deduced by M3
M2
Mesh of the parametric domain
Mesh of the 3D surface
Delaunay Method
The parametric mesh is
constructed in such a way
that lenght edges are created
in accordance with M2
The parametric mesh is
mapped onto the surface
obtaining final mesh
Indirect Approach
The meshing process of the parametric domain W includes
the following two steps:
1. generation of the boundary mesh, triangulation of the
points which divide the boundary in segments of unit
length
2. generation of the final unit mesh, applying an insertion
point strategy to the mesh of its boundary
The points computed to generate the mesh are inserted
using an algorithm based on the generalized Delaunay
triangulation.
Delaunay Method
Saturation Method
Inizialization: the domain mesh is the boundary mesh
DO UNTIL (all the edges are unitary)
FOR each internal edge
1. Compute points to subdivide edge in unit
length segments
2. Ensure that new points are not too close
to any already existing point
3. Insert points in the mesh
END
END
Delaunay Method
Saturation Method
Delaunay Method
Advancing Front Technique
Let the front be the interface between a “satisfactory” element
and an “unsatisfactory” one with respect to a quality measure.
Inizialization: the domain mesh is the boundary mesh.
DO UNTIL (all elements are satisfactory)
1. For all the segments of the front define points
in such a way that they are at unit distance
from the segment endpoints
2. Ensure that the new points are not too close to
each other and to any already existing point
3. Insert the points in the mesh
END
Delaunay Method
Advancing Front Technique
Delaunay Method
Optimisation
The following optimization tools can be used to improve the
quality of the mesh:
1. diagonal swapping (DS): the
swapping is based on the point
connectivity and the element
shape quality.
2. edge collapsing (EC): if the
edge has length lower than a
value e, it’s replaced with one
point
Delaunay Method
Optimisation
3. Node movement (NM): the
“spring analogy” has been
used to move the mesh.
The resulting mesh is the
solution of the equilibrium
system for each vertex i.
The optimization process is guided by the variation of two
quantities:
1. edge length quality
2. element shape quality.
Delaunay Method
Quality
The edge length quality Qe of AB
with respect to a Riemannian
structure can be defined as
 LM ( AB) if LM ( AB)  1

Qe   1
 L ( AB) if LM ( AB)  1
 M
With this measure we have Qe  1
and a unit edge has Qe  1
Let K=(P1 P2 P3) be a triangle in a
Riemannian space. The triangle shape
quality can be defined as
Q( K )  max Qi ( K )
1i3
where Qi(K) is the triangle quality in the
Euclidean space characterized by
metric M(Pi) at vertex Pi of K, defined
as
max
Qi ( K )  a
1 j  k 3
t
Pj Pk M i Pj Pk 

1 j  k 3
t
Pj Pk M i Pj Pk
Det ( M i )  Det ( P1P2 , P1P3 )
With this measure we have Q  1 and an
“optimal” element has Q  1
Delaunay Method
Test-Cases: Klein Bottle
This mesh is obtained using advancing front technique.
Delaunay Method
Test-Cases: Dini’s surface
This mesh is obtained using advancing front technique.
Delaunay Method
Test-Cases: Hilly surface
This mesh is obtained using advancing front technique.
Delaunay Method