DCEL mesh structure

Basic concept

EBGeometry uses a doubly-connected edge list (DCEL) structure for storing surface meshes. The DCEL structures consist of the following objects:

  • Planar polygons (facets).

  • Half-edges.

  • Vertices.

As shown in Fig. 1, the half-edge is the most important data structure. Half-edges circulate the inside of the facet, with pointer-access to the previous and next half-edge. A half-edge also stores a reference to it’s starting vertex, as well as a reference to it’s pair-edge. From the DCEL structure we can easily obtain all edges or vertices belonging to a single facet, and also “jump” to a neighboring facet by fetching the pair edge.

_images/DCEL.png

Fig. 1 DCEL mesh structure. Each half-edge stores references to previous/next half-edges, the pair edge, and the starting vertex. Vertices store a coordinate as well as a reference to one of the outgoing half-edges.

In EBGeometry the half-edge data structure is implemented in it’s own namespace EBGeometry::Dcel. This is a comparatively standard implementation of the DCEL structure, supplemented by functions that permit signed distance computations to various features on such a mesh.

Important

A signed distance field requires a watertight and orientable surface mesh. If the surface mesh consists of holes or flipped facets, the signed distance function does not exist.

Signed distance

When computing the signed distance function, the closest point on the surface mesh can be one of the vertices, (half-) edges, or faces, see Fig. 2.

_images/PolygonProjection.png

Fig. 2 Possible closest-feature cases after projecting a point \(\mathbf{x}\) to the plane of a polygon face.

It is therefore necessary to distinguish between three cases:

  1. Facet/Polygon face.

    When computing the distance from a point \(\mathbf{x}\) to the polygon face we first determine if the projection of \(\mathbf{x}\) to the face’s plane lies inside or outside the face. This is more involved than one might think, and it is done by first computing the two-dimensional projection of the polygon face, ignoring one of the coordinates. Next, we determine, using 2D algorithms, if the projected point lies inside the embedded 2D representation of the polygon face. Various algorithms for this are available, such as computing the winding number, the crossing number, or the subtended angle between the projected point and the 2D polygon.

    Note

    EBGeometry uses the crossing number algorithm by default.

    If the point projects to the inside of the face, the signed distance is just \(d = \mathbf{n}_f\cdot\left(\mathbf{x} - \mathbf{x}_f\right)\) where \(\mathbf{n}_f\) is the face normal and \(\mathbf{x}_f\) is a point on the face plane (e.g., a vertex). If the point projects to outside the polygon face, the closest feature is either an edge or a vertex.

  2. Edge.

    When computing the signed distance to an edge, the edge is parametrized as \(\mathbf{e}(t) = \mathbf{x}_0 + \left(\mathbf{x}_1 - \mathbf{x}_0\right)t\), where \(\mathbf{x}_0\) and \(\mathbf{x}_1\) are the starting and ending vertex coordinates. The point \(\mathbf{x}\) is projected to this line, and if the projection yields \(t^\prime \in [0,1]\) then the edge is the closest point. In that case the signed distance is the projected distance and the sign is given by the sign of \(\mathbf{n}_e\cdot\left(\mathbf{x} - \mathbf{x}_0\right)\) where \(\mathbf{n}_e\) is the pseudonormal vector of the edge. Otherwise, the closest point is one of the vertices.

  3. Vertex.

    If the closest point is a vertex then the signed distance is simply \(\mathbf{n}_v\cdot\left(\mathbf{x}-\mathbf{x}_v\right)\) where \(\mathbf{n}_v\) is the vertex pseudonormal and \(\mathbf{x}_v\) is the vertex position.

Normal vectors

The normal vectors for edges \(\mathbf{n}_e\) and vertices \(\mathbf{n}_v\) are, unlike the facet normal, not uniquely defined. For both edges and vertices we use the pseudonormals from [1]:

\[\mathbf{n}_{e} = \frac{1}{2}\left(\mathbf{n}_{f} + \mathbf{n}_{f^\prime}\right).\]

where \(f\) and \(f^\prime\) are the two faces connecting the edge. The vertex pseudonormal are given by

\[\mathbf{n}_{v} = \frac{\sum_i\alpha_i\mathbf{n}_{f_i}}{\left|\sum_i\alpha_i\right|},\]

where the sum runs over all faces which share \(v\) as a vertex, and where \(\alpha_i\) is the subtended angle of the face \(f_i\), see Fig. 3.

_images/Pseudonormal.png

Fig. 3 Edge and vertex pseudonormals.