... | @@ -132,20 +132,25 @@ The advantage of this approach is that those arrays can be sorted with respect t |
... | @@ -132,20 +132,25 @@ The advantage of this approach is that those arrays can be sorted with respect t |
|
Consequently, elements geometrically close can be sorted in such a way that they are close in memory which
|
|
Consequently, elements geometrically close can be sorted in such a way that they are close in memory which
|
|
improves the performance of algorithms iterating over geometrically local elements.
|
|
improves the performance of algorithms iterating over geometrically local elements.
|
|
|
|
|
|
### Generic data types
|
|
### Properties
|
|
We use a generic implementation such that the user can define types which can be associated with, and accessed via, a specific mesh element.
|
|
Each mesh element (vertex, half-edge, face) can have different user-defined properties. Each property has to have a unique `String name`. Properties are managed by the mesh, i.e. defining, inserting and accessing properties can be done via the mesh object by the following methods:
|
|
Therefore the ``PMesh<P,CE,CF>`` defines three generic types:
|
|
- `setData(V vertex, String name, CV value)`, where `CV` is a generic type
|
|
|
|
- `setData(E edge, String name, CE value)`, where `CE` is a generic type
|
|
|
|
- `setData(F edge, String name, CF value)`, where `CF` is a generic type
|
|
|
|
- `CV` getData(V vertex, String name, Class<CV>)`, where 'CV' is a generic type
|
|
|
|
- `CE` getData(E edge, String name, Class<CE>)`, where 'CE' is a generic type
|
|
|
|
- `CF` getData(F face, String name, Class<CF>)`, where 'CF' is a generic type
|
|
|
|
|
|
- ``P`` is the type of objects which can be associated with a ``PVertex``. ``P`` has to be a point (``P extends IPoint``)
|
|
****Remark****: The user is responsible for the correctness of the types that is inserting the objects / primitives of the same type for one key / name and using the correct `Class<>`. The following code, for example, would cause an `Exception`:
|
|
- ``CE`` is the type of objects which can be associated with a ``PHalfEdge`` and
|
|
|
|
- ``CF`` is the type of objects which can be associated with a ``PFace`.
|
|
```java
|
|
|
|
mesh.setData(vertex, "velocity", 3.0);
|
|
|
|
mesh.getData(vertex, "velocity", Boolean.class);
|
|
|
|
```
|
|
|
|
|
|
In Java there is nothing like ``typedef`` thus the programmer has always to fully specify the data type which might lead to long lines of code like:
|
|
In Java there is nothing like ``typedef`` thus the programmer has always to fully specify the data type which might lead to long lines of code like:
|
|
```java
|
|
```java
|
|
IMesh<VPoint,Double,Double,
|
|
IMesh<PVertex, PHalfEdge, PFace> mesh = ...
|
|
PVertex<VPoint,Double,Double>,
|
|
|
|
PHalfEdge<VPoint,Double,Double>,
|
|
|
|
PFace<VPoint,Double,Double>> mesh = ...
|
|
|
|
```
|
|
```
|
|
However, we wanted to make it possible that the user can integrate his own ``XMesh`` implementation and at the same time, it should be easy to use the meshing library.
|
|
However, we wanted to make it possible that the user can integrate his own ``XMesh`` implementation and at the same time, it should be easy to use the meshing library.
|
|
Therefore, we introduce some classes which predefine some types like ``PMesh``. We also encourage the user to use the local-variable type inference introduced in Java 10
|
|
Therefore, we introduce some classes which predefine some types like ``PMesh``. We also encourage the user to use the local-variable type inference introduced in Java 10
|
... | @@ -153,7 +158,7 @@ by replacing long type definitions by the ``var` keyword if possible. |
... | @@ -153,7 +158,7 @@ by replacing long type definitions by the ``var` keyword if possible. |
|
The code above and below are semantically the same.
|
|
The code above and below are semantically the same.
|
|
|
|
|
|
```java
|
|
```java
|
|
PMesh<VPoint,Double,Double> mesh = ...
|
|
PMesh mesh = ...
|
|
```
|
|
```
|
|
|
|
|
|
### Implicit assumptions
|
|
### Implicit assumptions
|
... | @@ -172,17 +177,15 @@ Furthermore, we save ``Double`` objects on its half-edges and faces. |
... | @@ -172,17 +177,15 @@ Furthermore, we save ``Double`` objects on its half-edges and faces. |
|
|
|
|
|
****Remark****: The order of points matter, i.e. they have to form a ****simple counter-clockwise (CCW) oriented polygon****.
|
|
****Remark****: The order of points matter, i.e. they have to form a ****simple counter-clockwise (CCW) oriented polygon****.
|
|
|
|
|
|
Some operations offered by ``IMesh`` require the construction of new points ``P``, therefore it requires a ``IPointConstructor``, here defined by the lambda expression ``(x,y) -> new VPoint(x,y)``:
|
|
|
|
|
|
|
|
```java
|
|
```java
|
|
var mesh = new PMesh<>((x,y) -> new VPoint(x,y));
|
|
var mesh = new PMesh();
|
|
mesh.toFace(new VPoint(0,0),new VPoint(1,0),new VPoint(1,1),new VPoint(0,1));
|
|
mesh.toFace(new VPoint(0,0),new VPoint(1,0),new VPoint(1,1),new VPoint(0,1));
|
|
```
|
|
```
|
|
|
|
|
|
To use the array-based implementation instead, we only have to exchange ``PMesh`` by ``AMesh``:
|
|
To use the array-based implementation instead, we only have to exchange ``PMesh`` by ``AMesh``:
|
|
|
|
|
|
```java
|
|
```java
|
|
var mesh = new AMesh<>((x,y) -> new VPoint(x,y));
|
|
var mesh = new AMesh<>();
|
|
mesh.toFace(new VPoint(0,0),new VPoint(1,0),new VPoint(1,1),new VPoint(0,1));
|
|
mesh.toFace(new VPoint(0,0),new VPoint(1,0),new VPoint(1,1),new VPoint(0,1));
|
|
```
|
|
```
|
|
|
|
|
... | @@ -259,7 +262,7 @@ As already mentioned each mesh element (vertex, half-edge, face) can carry some |
... | @@ -259,7 +262,7 @@ As already mentioned each mesh element (vertex, half-edge, face) can carry some |
|
In the following we save on each face its area.
|
|
In the following we save on each face its area.
|
|
|
|
|
|
```java
|
|
```java
|
|
for(PFace<VPoint, Double, Double> face : mesh.getFaces()) {
|
|
for(PFace face : mesh.getFaces()) {
|
|
mesh.setData(face, mesh.toTriangle(face).getArea());
|
|
mesh.setData(face, mesh.toTriangle(face).getArea());
|
|
}
|
|
}
|
|
```
|
|
```
|
... | @@ -286,8 +289,6 @@ Average triangle area = 0.04939003214493538 |
... | @@ -286,8 +289,6 @@ Average triangle area = 0.04939003214493538 |
|
Area triangulated = 97.10080319694295 %
|
|
Area triangulated = 97.10080319694295 %
|
|
```
|
|
```
|
|
|
|
|
|
We can also exchange ``VPoint`` by any point container extending ``IPoint``.
|
|
|
|
|
|
|
|
### Visualization
|
|
### Visualization
|
|
During the development of the EikMesh library we created some useful utility classes to accelerate the development process.
|
|
During the development of the EikMesh library we created some useful utility classes to accelerate the development process.
|
|
Visualizing the mesh helped us to understand and improve certain algorithms and to write documents like this.
|
|
Visualizing the mesh helped us to understand and improve certain algorithms and to write documents like this.
|
... | @@ -310,7 +311,7 @@ TexGraphGenerator.toTikz( |
... | @@ -310,7 +311,7 @@ TexGraphGenerator.toTikz( |
|
Furthermore, we can display the same mesh on a Java ``Swing`` canvas:
|
|
Furthermore, we can display the same mesh on a Java ``Swing`` canvas:
|
|
|
|
|
|
```java
|
|
```java
|
|
var panel = new PMeshPanel<>(
|
|
var panel = new PMeshPanel(
|
|
dt.getMesh(),
|
|
dt.getMesh(),
|
|
500,
|
|
500,
|
|
500,
|
|
500,
|
... | @@ -382,7 +383,7 @@ List<VPoint> points = randomPoints |
... | @@ -382,7 +383,7 @@ List<VPoint> points = randomPoints |
|
.collect(Collectors.toList());
|
|
.collect(Collectors.toList());
|
|
|
|
|
|
// (2) compute the Delaunay triangulation
|
|
// (2) compute the Delaunay triangulation
|
|
var dT = new PDelaunayTriangulator<VPoint, Double, Double>(points,(x,y) -> new VPoint(x,y));
|
|
var dT = new PDelaunayTriangulator(points);
|
|
var triangulation = dT.generate();
|
|
var triangulation = dT.generate();
|
|
```
|
|
```
|
|
|
|
|
... | @@ -424,9 +425,8 @@ The following code generates the CDT of the PSLG. If we replace ``conforming = f |
... | @@ -424,9 +425,8 @@ The following code generates the CDT of the PSLG. If we replace ``conforming = f |
|
final InputStream inputStream = ...
|
|
final InputStream inputStream = ...
|
|
boolean conforming = false;
|
|
boolean conforming = false;
|
|
PSLG pslg = PolyGenerator.toPSLGtoVShapes(inputStream);
|
|
PSLG pslg = PolyGenerator.toPSLGtoVShapes(inputStream);
|
|
var cdt = new PContrainedDelaunayTriangulator<VPoint, Double, Double>(
|
|
var cdt = new PContrainedDelaunayTriangulator(
|
|
pslg,
|
|
pslg,
|
|
(x,y) -> new VPoint(x,y),
|
|
|
|
conforming);
|
|
conforming);
|
|
var triangulation = cdt.generate();
|
|
var triangulation = cdt.generate();
|
|
```
|
|
```
|
... | @@ -471,9 +471,8 @@ The following code generates a mesh using h(x) = 0.05: |
... | @@ -471,9 +471,8 @@ The following code generates a mesh using h(x) = 0.05: |
|
```java
|
|
```java
|
|
PSLG pslg = ...
|
|
PSLG pslg = ...
|
|
double h0 = 0.05;
|
|
double h0 = 0.05;
|
|
var vviMethod = new PVoronoiVertexInsertion<VPoint, Double, Double>(
|
|
var vviMethod = new PVoronoiVertexInsertion(
|
|
pslg,
|
|
pslg,
|
|
(x, y) -> new VPoint(x, y),
|
|
|
|
p -> h0);
|
|
p -> h0);
|
|
var triangulation vviMethod.generate();
|
|
var triangulation vviMethod.generate();
|
|
```
|
|
```
|
... | @@ -496,9 +495,8 @@ The following code generates a mesh using h(x) = 0.05: |
... | @@ -496,9 +495,8 @@ The following code generates a mesh using h(x) = 0.05: |
|
```java
|
|
```java
|
|
PSLG pslg = ...
|
|
PSLG pslg = ...
|
|
double h0 = 0.05;
|
|
double h0 = 0.05;
|
|
var vviMethod = new PVoronoiSegmentInsertion<VPoint, Double, Double>(
|
|
var vviMethod = new PVoronoiSegmentInsertion(
|
|
pslg,
|
|
pslg,
|
|
(x, y) -> new VPoint(x, y),
|
|
|
|
p -> h0);
|
|
p -> h0);
|
|
var triangulation vviMethod.generate();
|
|
var triangulation vviMethod.generate();
|
|
```
|
|
```
|
... | @@ -526,11 +524,10 @@ The following code generates a mesh using h(x) = 0.05 and a minimal allowed thet |
... | @@ -526,11 +524,10 @@ The following code generates a mesh using h(x) = 0.05 and a minimal allowed thet |
|
PSLG pslg = ...
|
|
PSLG pslg = ...
|
|
double h0 = 0.02;
|
|
double h0 = 0.02;
|
|
double theta = 20.0;
|
|
double theta = 20.0;
|
|
var ruppert = new PRuppertsTriangulator<VPoint, Double, Double>(
|
|
var ruppert = new PRuppertsTriangulator(
|
|
pslg,
|
|
pslg,
|
|
p -> h0,
|
|
p -> h0,
|
|
theta,
|
|
theta);
|
|
(x, y) -> new VPoint(x, y));
|
|
|
|
var triangulation = ruppert.generate();
|
|
var triangulation = ruppert.generate();
|
|
```
|
|
```
|
|
|
|
|
... | @@ -592,7 +589,7 @@ IDistanceFunction d_comb = IDistanceFunction.createDisc(0.5, 0.5, 0.5); |
... | @@ -592,7 +589,7 @@ IDistanceFunction d_comb = IDistanceFunction.createDisc(0.5, 0.5, 0.5); |
|
IDistanceFunction d_rec = IDistanceFunction.create(rect);
|
|
IDistanceFunction d_rec = IDistanceFunction.create(rect);
|
|
IDistanceFunction d = IDistanceFunction.substract(d_comb, d_rec);
|
|
IDistanceFunction d = IDistanceFunction.substract(d_comb, d_rec);
|
|
double edgeLength = 0.03;
|
|
double edgeLength = 0.03;
|
|
var meshImprover = new PEikMeshGen<EikMeshPoint, Double, Double>(
|
|
var meshImprover = new PEikMesh(
|
|
d,
|
|
d,
|
|
p -> edgeLength + 0.5 * Math.abs(d.apply(p)),
|
|
p -> edgeLength + 0.5 * Math.abs(d.apply(p)),
|
|
edgeLength,
|
|
edgeLength,
|
... | @@ -645,13 +642,12 @@ IDistanceFunction d = IDistanceFunction.substract(d_b,d_union); |
... | @@ -645,13 +642,12 @@ IDistanceFunction d = IDistanceFunction.substract(d_b,d_union); |
|
// h_min
|
|
// h_min
|
|
double edgeLength = 0.03;
|
|
double edgeLength = 0.03;
|
|
|
|
|
|
var meshImprover = new PEikMeshGen<EikMeshPoint, Double, Double>(
|
|
var meshImprover = new PEikMesh(
|
|
d,
|
|
d,
|
|
p -> edgeLength + 0.5 * Math.abs(d.apply(p)),
|
|
p -> edgeLength + 0.5 * Math.abs(d.apply(p)),
|
|
edgeLength,
|
|
edgeLength,
|
|
GeometryUtils.boundRelative(boundary.getPath()),
|
|
GeometryUtils.boundRelative(boundary.getPath()),
|
|
Arrays.asList(rect),
|
|
Arrays.asList(rect));
|
|
(x, y) -> new EikMeshPoint(x, y, false));
|
|
|
|
|
|
|
|
// generate the mesh
|
|
// generate the mesh
|
|
var triangulation = meshImprover.generate();
|
|
var triangulation = meshImprover.generate();
|
... | @@ -681,7 +677,7 @@ The following code uses a Delaunay triangulation of 1000 random points as the in |
... | @@ -681,7 +677,7 @@ The following code uses a Delaunay triangulation of 1000 random points as the in |
|
|
|
|
|
```java
|
|
```java
|
|
var dt = ... // the Delaunay triangulation
|
|
var dt = ... // the Delaunay triangulation
|
|
var eikMesh = new PEikMeshGen<>(p -> 1.0 + Math.abs(bound.distance(p)),dt.getTriangulation());
|
|
var eikMesh = new PEikMesh(p -> 1.0 + Math.abs(bound.distance(p)),dt.getTriangulation());
|
|
var triangulation = eikMesh.generate();
|
|
var triangulation = eikMesh.generate();
|
|
```
|
|
```
|
|
|
|
|
... | @@ -709,15 +705,13 @@ VPolygon segmentBound = pslg.getSegmentBound(); |
... | @@ -709,15 +705,13 @@ VPolygon segmentBound = pslg.getSegmentBound(); |
|
IDistanceFunction d = IDistanceFunction.create(segmentBound, holes);
|
|
IDistanceFunction d = IDistanceFunction.create(segmentBound, holes);
|
|
|
|
|
|
// (3) use EikMesh to construct the mesh
|
|
// (3) use EikMesh to construct the mesh
|
|
IPointConstructor<EikMeshPoint> pointConstructor = (x, y) -> new EikMeshPoint(x, y);
|
|
|
|
double h0 = 5.0;
|
|
double h0 = 5.0;
|
|
var meshImprover = new PEikMeshGen<EikMeshPoint, Double, Double>(
|
|
var meshImprover = new PEikMesh(
|
|
d,
|
|
d,
|
|
p -> h0 + 0.3 * Math.abs(d.apply(p)),
|
|
p -> h0 + 0.3 * Math.abs(d.apply(p)),
|
|
h0,
|
|
h0,
|
|
new VRectangle(segmentBound.getBounds2D()),
|
|
new VRectangle(segmentBound.getBounds2D()),
|
|
pslg.getHoles(),
|
|
pslg.getHoles()
|
|
pointConstructor
|
|
|
|
);
|
|
);
|
|
meshImprover.generate();
|
|
meshImprover.generate();
|
|
````
|
|
````
|
... | | ... | |