EikMesh is a Java library for high quality meshes. In Vadere, EikMesh is used to generate the navigational floor field.

The EikMesh Java library is part of Vadere and was developed to generate high quality meshes for spatial discretization in the domain of pedestrian dynamics. We are especially interested in reducing the complexity of dynamic floor field computation which is one of our active research topics. Computing a floor field involves the solution of the eikonal equation which led us to the name EikMesh.

Despite its origin, the library can be used independently of Vadere. Aside from the EikMesh algorithm, the library contains multiple algorithms and data structures to generate, change and use unstructured 2D triangular meshes. It implements a generic version of the edge based half-edge data structure also called doubly connected edge list (DCEL). Objects of user defined data types can be easily stored at, and accessed via mesh elements, i.e. vertices, (half-)edges and faces / triangles. Given some mesh element, adjacent elements can be accessed in O(1) time. Each generated mesh is conforming. Holes are supported.

The aim was to provide a fast, light and user-friendly meshing tool with parametric input, generic data types and advanced visualization capabilities. The EikMesh library generates

  • Delaunay triangulations (DT),
  • constrained Delaunay triangulations (CDT),
  • conforming Delaunay triangulations (CCDT),
  • Voronoi diagrams, and
  • high-quality unstructured conforming triangular meshes.

The EikMesh algorithm

The EikMesh mesh generator is heavily based on DistMesh, a simple and effective mesh generator (in MATLAB) which was developed by Per-Olof Persson and Gilbert Strang. EikMesh inherits from DistMesh the specification of the geometry via signed distance functions and the concept of iterative smoothing by converging towards a force equilibrium. However, EikMesh completely avoids the computation of the Delaunay triangulation, generates a different and cache friendly initial triangulation and treats boundary elements more carefully. Additionally, EikMesh supports geometries defined by a segment bounded planar straight-line graphs (PSLG).

Documentation

Download

The source code is available at GitLab. A pre-compiled version can be download here. The eikmesh library is part of Vadere but can be used separately. Like Vadere, it is distributed under the LGPL license.

Examples

The following examples provide some insights of the capabilities of the EikMesh algorithm.

Code

VRectangle bound = new VRectangle(-0.1, -0.1, 2.2, 2.2);
IDistanceFunction d_r = IDistanceFunction.createRing(1, 1, 0.2, 1.0);
double h_min = 0.1;
PEikMesh meshImprover = new PEikMesh(d_r,h_min,bound);
meshImprover.generate();
PSLG pslg = ...
double h_min = 0.02;
PEikMesh meshImprover = new PEikMesh(pslg.getSegmentBound(), h_min, pslg.getHoles());
meshImprover.generate();
VRectangle bound = ...
VRectangle rect = new VRectangle(0.5, 0.5, 1, 1);
IDistanceFunction d_c = IDistanceFunction.createDisc(0.5, 0.5, 0.5);
IDistanceFunction d_r = IDistanceFunction.create(rect);
IDistanceFunction d = IDistanceFunction.substract(d_c, d_r);
double h_min = 0.03;
var meshImprover = new PEikMesh(
				d,
				p -> h_min + 0.5 * Math.abs(d.apply(p)),
				h_min,
				bound,
				Arrays.asList(rect));

VRectangle rect = new VRectangle(-0.5, -0.5, 1, 1);
VRectangle boundary = new VRectangle(-2,-0.7,4,1.4);

IDistanceFunction d1_c = IDistanceFunction.createDisc(-0.5, 0, 0.5);
IDistanceFunction d2_c = IDistanceFunction.createDisc(0.5, 0, 0.5);
IDistanceFunction d_r = IDistanceFunction.create(rect);
IDistanceFunction d_b = IDistanceFunction.create(boundary);
IDistanceFunction d_unionTmp = IDistanceFunction.union(d1_c, d_r)
IDistanceFunction d_union = IDistanceFunction.union(d_unionTmp, d2_c);
IDistanceFunction d = IDistanceFunction.substract(d_b,d_union);

double h_min = 0.03;
var meshImprover = new PEikMesh(
				d,
				p -> h_min + 0.5 * Math.abs(d.apply(p)),
				edgeLength,
GeometryUtils.boundRelative(boundary.getPath()),
				Arrays.asList(rect));

var triangulation = meshImprover.generate();

Videos

The three stages of EikMesh

The following video illustrates the 3 different stages of EikMesh. Colors code the memory location of mesh elements.

Adaptive edge length function

The following video shows an EikMesh run meshing a disc. If you watch carefully you can spot a fix point at the center of the disc.

Adaptive distance and edge length function

The next video shows the influence of changing the signed distance function as well as the edge length function. In the beginning the distance function defines a rectangle with a hole which is the union of a square and two circles. Then it changes to a square and finally to a circle while the edge length function changes to a constant.

Adaptive mesh for a disc

In the following the geometry is a disc. The edge length function is equal to h(p) = h_min + 0.3 * |p.x-c_x|, where c_x is the x-coordinate of the center of the disc and p.x is the x-coordinate of the point p.

Meshing a (segment bounded) planar straight-line graph

Next we show the mesh generation using EikMesh when the geometry is a PSLG containing sharp corners.

EikMesh for geometries in pedestrian simulation

In the following we demonstrate EikMesh using a real world geometry which is used in our simulation framework Vadere.

Smoothing a random Delaunay triangulation

The last video shows the robustness of EikMesh. The initial triangulation is a Delaunay triangulation of 1000 uniformly distributed points.