Content

This document has the following sections:

Data Structure

Data Structure

The winged-edge data structure was proposed by Bruce G. Baumgart in 1975. It features nodes, edges, and faces, along with a dense pointer structure between incident primitives. With those links, a fast accessing of neighboring primitives is possible, although there is some overhead in space and time necessary (memory space and processing time, and sometimes programming time...).

The WEM libray uses this data structure for surface representation, and the modules for mesh processing avail themselves from the speed of accessing neighboring primitives.

WEMPrimitive

All the three primitives, the WEMNode, the WEMEdge, and the WEMFace are derived from WEMPrimitive. This base class provides basic functionality for administration and maintenance. Notably, this base class stores the following:

the 'entry number': the index of each primitive in its vector is stored as hardware-independent pointers.
a bit flag: can be used to code information for each primitive; this is used for storing the traversal state, for example.
the heap position: some algorithms make use of heap structures (priority queues), and the heap position/value and the information whether the primitive is registered in a heap at all is stored in the primitives themselves.

Pointers to indicient primitives (like to the preceding and succeeding edges of the WEMEdge, or to all the incident faces of a WEMNode) are stored in the according primitives themselves.

WEMNode

The WEMNode holds the geometrical properties of the mesh. In here, a position and a normal is stored.

The WEMNode stores the pointer to its incident edges and faces in private arrays of the size WEM_MAX_VALENCE.

The pointers to edges and faces in these arrays do not have to be in any special order.

The pointer links of a node to its edges and its faces.

WEMEdge

The WEMEdge plays a central role in the WEM, and the edge's pointer structure that gave name to the data structure. The edge is directed, having a head and a tail node. On base of this direction, the edge has a left and a right face (when 'looked from above', regarding the surface normals).

Since a valid winged-edge mesh is a 2-manifold, there must be a left and a right face. But in application, there can be holes or borders. In this case, one or both pointers to the edge's incident faces are NULL. The most of the processing modules take this into regard and handle borders accordingly. The SoWEMDiagnosis module would report such NULL faces at edges, but it can optionally be switched to ignore them.

For the most processing modules, the wing-pointers must be set. These are the left and the right preceding and succeeding edges, respectively. The terms 'preceding' and 'succeeding' for lPred, lSucc, rPred and rSucc refer to a clockwise by-pass around the edge's incident faces.

The pointer links of an edge to its nodes, edges and faces with the according names.

WEMFace

The WEMFace is a base class and there are three implementations: WEMTriangle, WEMQuad and WEMPolygon. This distinction has been made for efficiency reasons.

The nodes and edges have to be ordered in clockwise order. Note that the nodes and the edges of a face must be aligned. This means that the first node must be the head or the tail of the first edge, the second node must be the head or the tail of the second edge, and so on.

The pointer links of a face to its nodes and its edges.

Pointers of a WEMFace Neighborhood

If all the primitives are put together, all their links have backlinks to the incident primitives.

A face with its pointers in a WEM neighborhood.

WEMPatch

A WEM consists of a number of WEMPatches. These can be of type WEMTrianglePatch, WEMQuadPatch, or WEMPolygonPatch. Different patch types can be part of a single WEM, but the faces in a patch must be of one type, the same as the patch type. For example, a WEMTrianglePatch must consist of WEMTriangles only, where a WEM can consist of a WEMTrianglePatch and a WEMQuadPatch.

Generally, there is only one patch per WEM. This is the case if a WEM has just been generated by the WEMIsoSurface module. However, for some algorithms it can be useful to compute per patch. The module WEMDemergePatches can demerge a WEM into a number of patches, based on a connected component analysis.

WEMPrimitiveValueList

For each WEMPatch, a number of WEMPrimitiveValueLists (PVLs) can be established dynamically. These lists can store additional information on the nodes, edges, or faces and the stored values can be used for statistical investigation (WEMInfo) or for coloring the rendering (SoWEMRenderer, using it in LUT mode).

PVLs can optionally be made non-persistent (for the .wem format).