... | ... | @@ -75,7 +75,7 @@ number of small segments if a curve has to be approximated. |
|
|
PSLG description into a distance function description but we lose all
|
|
|
segments not part of a polygon (the bounding polygon or any hole).
|
|
|
|
|
|
|
|
|
---
|
|
|
|
|
|
# The mesh data structure <a name="The-mesh-data-structure"></a>
|
|
|
|
... | ... | @@ -316,9 +316,7 @@ var panel = new PMeshPanel<>( |
|
|
panel.display("Delaunay triangulation");
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
---
|
|
|
|
|
|
# Preliminary algorithms <a name="Preliminary-algorithms"></a>
|
|
|
|
... | ... | @@ -433,6 +431,72 @@ The following illustrated the difference between the DT (left), the CDT (middle) |
|
|
|
|
|
![CDT](uploads/28bdb462fa809bee789aaca6e5566c4e/CDT.png)
|
|
|
|
|
|
---
|
|
|
|
|
|
# Mesh generation
|
|
|
|
|
|
## The edge length function
|
|
|
|
|
|
The goal of unstructured mesh generation is to produce high quality meshes containing as less elements as possible.
|
|
|
To control the size of the elements, the user has to define an edge length function.
|
|
|
More precisely,
|
|
|
|
|
|
h : D --> R^+
|
|
|
|
|
|
is the edge length function defined on the mesh domain D. In the following examples you will find different edge length functions.
|
|
|
|
|
|
## Rebay's algorithms
|
|
|
|
|
|
The eikmesh library offers the implementation of two algorithm introduced by Rebay in [Rebay, 1993](https://doi.org/10.1006/jcph.1993.1097). The first one, the so called
|
|
|
> Voronoi-Vertex point insertion method,
|
|
|
is a *Delaunay-refinement* technique, i.e. additional so called *Steiner vertices* are inserted at the circumcenter of some Delaunay triangle.
|
|
|
The second one, called
|
|
|
> Voronoi-Segment point insertion method,
|
|
|
is a *Frontal-Delaunay algorithm*.
|
|
|
Frontal-Delaunay algorithms are a hybridization of advancing-front and Delaunay-refinement techniques, in which a Delaunay triangulation is used to define the topology of a mesh while new Steiner vertices are inserted in a manner consistent with *advancing-front techniques*.
|
|
|
Both algorithms have a time complexity of O(n log(n)), where n is the number of vertices of the generated triangulation.
|
|
|
For both the user can control the element size by an edge length function h. Both algorithm expect a segment-bounded PSLG G as input and terminates if h is satisfied everywhere.
|
|
|
|
|
|
In our implementation we start by constructing the constrained Delaunay triangulation of the PSLG G. In the second step we insert additional Steiner vertices based on the rules described by Rebay.
|
|
|
|
|
|
### Voronoi-Vertex point insertion method
|
|
|
|
|
|
For the first algorithm, in each iteration k, the Steiner vertex v is the circumcenter of the triangle t_j in the current triangulation with the largest circumcenter radius. Note that if the triangulation is a Delaunay triangulation, v is in fact a vertex of the Voronoi diagram of the current vertex set. It might be the case that v lies outside of the segment-bound of G. If so, we ignore the vertex, i.e. it will not be inserted.
|
|
|
|
|
|
The following code generates a mesh using h(x) = 0.05:
|
|
|
|
|
|
```java
|
|
|
PSLG pslg = ...
|
|
|
double h0 = 0.05;
|
|
|
var vviMethod = new PVoronoiVertexInsertion<VPoint, Double, Double>(
|
|
|
pslg,
|
|
|
(x, y) -> new VPoint(x, y),
|
|
|
p -> h0);
|
|
|
var triangulation vviMethod.generate();
|
|
|
```
|
|
|
|
|
|
#### Result:
|
|
|
|
|
|
The gray code indicate the triangle quality.
|
|
|
|
|
|
![vvmethod](uploads/632fa085e4fabac73002ceb70f29d4a6/vvmethod.png)
|
|
|
|
|
|
|
|
|
### Voronoi-Segment point insertion
|
|
|
|
|
|
For the first algorithm, in each iteration k, the Steiner vertex v lies on the segment of the Voronoi diagram of the current triangulation. Additional each inserted vertex is an attempt to generate a new triangle t_j such that h is satisfied, which is not always possible. Like before, c might be outside of the segment-bound of G. If so, we ignore the vertex, i.e. it will not be inserted
|
|
|
|
|
|
For more information we refer to [Rebay, 1993](https://doi.org/10.1006/jcph.1993.1097).
|
|
|
|
|
|
The following code generates a mesh using h(x) = 0.05:
|
|
|
|
|
|
#### Result:
|
|
|
|
|
|
The gray code indicate the triangle quality.
|
|
|
|
|
|
![vimethod](uploads/c06634e022fe7b9dd2eeaf1936de87b6/vimethod.png)
|
|
|
|
|
|
---
|
|
|
|
|
|
# EikMesh <a name="EikMEsh"></a>
|
|
|
|
... | ... | |