# DMesh3: A Dynamic Indexed Triangle Mesh

/If you are using the g3Sharp library, there is a good chance it's because you need to do some things with triangle meshes. If so, then the triangle mesh data structure is kind of important! In g3Sharp, this is the **DMesh3** class. In this post I will dive into the details of this data structure and the operations it provides. Along the way I will try to explain some of the central concepts of triangle mesh data structures, which should also apply to other triangle mesh libraries.

At its core, DMesh3 is an **index-based triangle mesh**. This means that we reference components of the mesh - ie the vertices and triangles - by integer indices, rather than pointers. This is similar to the basic mesh data structures used in many other libraries. For example, Unity's **Mesh** class is also an indexed mesh, and the vertex buffers you might pass to a low-level graphics API like OpenGL/Direct3D/Vulkan/Metal are indexed meshes. The diagram below shows how these things connect up. Each vertex is a triplet or 3-tuple of real values (x,y,z) which are the 3D coordinates. In DMesh3 we store these in double-precision floating point. Then, each triangle is an integer 3-tuple (a,b,c), where each integer is the index of one of the vertices.

For many mesh processing tasks, this is all we really need. For example to render the triangles we just need the vertices of each triangle. If we want to estimate vertex normals, we can iterate over the triangles and accumulate their facet normals at the vertices. If we want to animate the mesh, we can modify the vertices. We can do a lot with just the basic indexed mesh, and it is the most memory-efficient mesh representation. The **SimpleMesh** class stores a mesh in this format.

But what if we want to know which triangles are connected to a specific vertex, or find the triangles connected to a specific triangle? These are common tasks in mesh processing. Even for something as basic as deleting a set of vertices, we'll need to find the list of affected faces. Of course we can compute this information from the triangle indices - this is called the **adjacency graph**, and we frequently refer to it as part of the **mesh topology**. However, computing the adjacency graph takes time, and in g3Sharp we use it often enough that we want to just keep it around all the time. So, we will add it directly into our mesh data structure.

First, we will explicitly represent the **edges** of the mesh. In a **manifold** triangle mesh, each edge has a vertex at either end, and is connected to one or two triangles (if it's just one, then this edge is on an **open boundary** of the mesh). So each edge is a 4-tuple (v_{0}, v_{1}, t_{0}, t_{1}), where if the edge is a boundary edge, then t_{1} will be set to the **invalid** index (which is -1, but you should use the constant **DMesh3.InvalidID**). These edges connect up pairs of vertices and faces, but we still need to know how to get from vertices to edges. So, for each vertex, DMesh3 stores a list of connected edges. The diagrams below illustrate this connectivity.

Storing the set of edges connected to a vertex adds a significant complication, because the number of edges is variable. At the implementation level, this means we need dynamically-sized per-vertex lists, which we will discuss further below. But at the conceptual level, we have largely solved our connectivity problems. If we have a vertex and want to find the set of faces it connects to - we call this it's **one-ring** - we can iterate over the edges, and collect up the unique triangle indices. If we would like to find the edge between two vertices A and B, we can just iterate over the edges at A and search for the one that connects to vertex B.

However, because of this variable-sized list, some common tasks are still relatively expensive. In particular, consider finding the three neighbour triangles for a given triangle. This involves iterating over each edge one-ring of each of the vertices of the triangle. When we manipulate regions of selected triangles, we need to do this search for each triangle in the selection, often many times, and so this search overhead is significant.

We can avoid these searches by explicitly storing the triplet of edges (e_{ab}, e_{bc}, e_{ca}) for each triangle, as shown in the diagram below.

Storing the triangle edges in this way is redundant. However it vastly simplifies many algorithms, and we find it to be worth the memory cost. For example, although one can find the edge between vertices A and B using the list-search described above, if A and B come from a known triangle, then the edge can be found in constant time. This is also a very frequent operation in many mesh processing algorithms.

# Accessors and Internal Storage

The **DMesh3** class provides interfaces for accessing the above elements. For example, **GetVertex(vi)** returns (x,y,z) for a given vertex index, and **GetTriangle(ti)** returns the (a,b,c) tuple. For edges, **GetEdgeV(ei)** returns the two edge vertices, **GetEdgeT(ei)** returns the triangles, and **GetEdge(ei)** returns both in a 4-tuple **Index4i** struct. **FindEdge(a,b)** returns the index of the edge between a and b, while **FindEdgeFromTri(a,b,ti)** uses the more efficient triangle-based query described above.

Similarly, convenient iterations are provided like **VtxVerticesItr(vi)** to iterate over the vertices connected to vertex vi, as well as **VtxEdgesItr(vi)** and **VtxTrianglesItr(vi)**. The **GetTriEdges(ti)** function returns the triangle-edge triplet, while **GetTriNeighbourTris(ti)** returns the neighbour triangles, and **TriTrianglesItr(ti)** provides the same values via an ** IEnumerable<int>**. So, you can iterate over an edge-one ring like so:

```
foreach (int eid in mesh.VtxEdgesItr(vid)) {
//....
}
```

There are also various task-specific queries that are useful in certain situations. For example, **GetVtxNbrhood(eid,vid)** looks up the "other" vertex of edge eid, as well as the connected triangles and "opposing" vertices, which are needed to compute the cotangent weights used in Laplacian mesh processing. You can of course compute this yourself using the above functions, but DMesh3 can do it more efficiently because it can directly query its internal data structures.

And what are these data structures, exactly? Most DMesh3 clients will not need to know, but it is relevant in some situations, so I will describe it in detail here. DMesh3 stores its indexable lists using the **DVector<T>** class. This class provides an array/list-like interface, ie the i'th element of type T can be accessed as array[i], and set as array[i] = v. However, internally the elements are not stored in a single contiguous array. Instead, DVector allocates memory in blocks, and the index accessor maps between the external linear index and the internal block/index pair.

In the current DVector implementation, each block is 2048 items. This is a hardcoded value to optimize indexing via bitwise operations. If you profile g3Sharp code, you will often find that DVector.this[] is the top hotspot, called via many DMesh3 functions. This is why DMesh3 stores the redundant triangle edges, and provides many variations on its accessor functions - because these allow us to minimize unnecessary queries that, when done millions of times, can really add up!

Why use a DVector instead of a C# List? The main reason is to avoid allocating huge linear blocks of memory. A triangle mesh can easily involve millions of elements, which means the internal buffers would be very large. In addition, if the mesh is growing - for example when adding triangles - the C# List class will resize itself multiple times, which means new allocations and buffer-copies. In interactive applications this can result in noticeable pauses. With DVector this situation never occurs.

If you look inside **DMesh3**, you may note that rather than the **vertices** list being a **DVector<Vector3d>**, it is instead a **DVector<double>**, and similarly for the triangles, edges, and so on. Because C# does not support returning references, it is not possible to use common C++ idioms that would allow for more efficient access. Frankly, in C# storing structs inside a list is risky, and a common source of errors. In addition, by using POD types, we can directly serialize the DVector buffers, which can be useful in interop situations. However, this is a design decision that is largely encapsulated inside DMesh3 and may be revisited in the future.

# Vertex Edge Lists

As I mentioned above, the variable-length per-vertex edge lists are a significant complication. For a small mesh, using a List<int> for each vertex is not outrageous, but if we have millions of vertices, then we have millions of tiny lists and this starts to become a problem. In particular, if we are *changing* the mesh, we will be updating these lists and so even more memory allocations (and garbage collections) will occur. In fact the initial DMesh3 implementation used Lists and during something like a remeshing pass, the GC was constantly working to clean up all the List objects being generated and discarded.

To alleviate this, the per-vertex lists are represented by a **SmallListSet** object. This class is designed to store a large number of small integer lists, where we have a priori knowledge of how many elements will be in the median list. If the median list size is K, then each list begins with K contiguous elements (think "array", but they are not stored as separate Array objects). If the list grows larger than this, then we *spill* into additional elements stored via a linked-list, as shown in the diagram.

K should be set so that "most" lists fit in the initial block of elements. In a perfectly *regular* mesh each vertex is connected to 6 edges, but in the current implementation we set K = 8. This gives us some breathing room. Internally, SmallListSet is built out of DVector<int> instances, and even can re-use previously-allocated lists that have been freed. As a result, memory allocations due to the vertex_edge lists are very infrequent. In addition, this scheme is approximately 30% more space-efficient than per-vertex Lists. Although most vertices will not need the full 8 ints in the initial per-list array, we make it up on the overhead of managing all those separate C# objects.

# Dynamic Mesh Operations

**DMesh3** is not just an indexed triangle mesh - it is a **dynamic** indexed triangle mesh. This means that we can modify the **mesh topology**, for example by deleting triangles, splitting edges, and so on. This are complex operations because the data structures above must be updated to remain internally consistent. However, these are mainly internal issues. From the perspective of the user of DMesh3, the immediate complication is that, if we delete a triangle, its index is now invalid.

Internally, for each of the **vertices**, **edges**, and **triangles** lists, DMesh3 also stores a **reference count** for each index, implemented via a **RefCountVector** object. When a vertex is deleted, its reference count is set to an invalid value (currently -1), which indicates that this index is no longer in use. The RefCountVector also maintains a list of these free indices, and functions like **AppendVertex()** and **AppendTriangle()** will preferentially re-use free indices. The reference counts themselves are stored as 16-bit short integers, which limits the valence of a vertex to ~65k.

These are internal implementation details - you don't have to interact with the reference counts yourself. However, it is critical to understand that after some mesh processing operations - like after Mesh Simplification via **Reducer **- a DMesh3 instance will have **gaps** in its index space, where certain indices will be invalid. If there are invalid indices, we say the mesh is **Non-Compact**, and **DMesh3.IsCompact** can be used to determine when this is the case.

When the mesh is Non-Compact, you ***cannot*** blindly iterate from 0 to **TriangleCount **or **VertexCount**, because some indices are invalid. The functions **IsVertex(vi)**, **IsTriangle(ti****)**, and **IsEdge(ei)** can be used to check if a given index is valid. However, for a Non-Compact mesh you also cannot rely on VertexCount and TriangleCount as an iteration boundary, because they return the number of valid indices, not the maximum index. If you take a mesh with a million triangles and delete all but 100 of them, it is entirely possible that one of the triangles has an index of 999999. So, to properly iterate via indices over a Non-Compact mesh you must iterate from 0 to **MaxTriangleID** or **MaxVertexID**. These values are the maximum allocated indices.

If this all sounds inconvenient, you are strongly encouraged to instead always use the functions **VertexIndices()** and **TriangleIndices()**. These functions return IEnumerables that iterate over only the valid indices.

In some situations, such as converting a processed DMesh3 to a different mesh format, you may wish to ** Compact** the mesh, so that the index space is

**dense**. The simplest way to do this is to use the compacting copy-constructor like so:

`DMesh3 compactMesh = new DMesh3(noncompactMesh, true)`

The resulting mesh will have indices that are tightly packed. Note that compacting is more computationally and memory intensive than non-compacting copies, because the internal buffers cannot be copied directly. So if you are doing a series of mesh processing operations, it is best to only compact at the end, or when necessary. If you need to know the mapping from old to new indices, you can use **CompactCopy()**, which returns a data structure containing these index maps. And **CompactInPlace()** can compact a given mesh without having to create a copy. However, if the mesh is large and even moderately sparse, this is more expensive than compacting with a copy.

# Vertex Attributes and Triangle Groups

DMesh3 provides a few common per-vertex attribute buffers for **vertex normals**, **colors**, and **uvs**. The normals and colors are stored in single-precision floating point, and for the colors, only RGB values are available, there is no alpha channel. The UVs are stored as 2-element floats.

These buffers are **optional**. By default they are not allocated. The various constructors and copy functions can enable these buffers at setup. You can also use functions like **EnableVertexNormals()**, etc, to initialize vertex attributes for a given mesh, and **DiscardVertexNormals()**/etc to throw them away. The **DMesh3.Components** property returns a **MeshComponents** enum-flags, which will tell you if a mesh has a particular buffer, as can the **HasVertexColors**/etc properties.

There is only one per-triangle attribute, an integer **triangle group** field. Usage of this is up to you. However we do use triangle groups inside g3Sharp to indicate semantic groupings of triangles. For example Remesher and Reducer can be configured to preserve the boundaries of sets of triangles with the same group.

# Modification Operations

Since DMesh3 is dynamic, you can change it. There are various functions to do so, which properly update all the internal data structures to keep the mesh consistent. **RemoveTriangle()** and **RemoveVertex()** can be used to delete elements. **SplitEdge()**, **CollapseEdge()**, and **FlipEdge()** implement the standard mesh refinement operations. **PokeTriangle()** does a 1-to-3 triangle subdivision by adding a vertex at the triangle centroid.

The **MergeEdges****()** function combines two edges into one. Conceptually this is performed by welding each pair of vertices. However a single vertex weld creates a bowtie vertex, so MergeEdges does both, and the mesh is never left in a non-manifold state. In addition, MergeEdges will properly close the zero-area holes that occur when, for example, merging the second-last of a pair of edge loops.

These functions return a **MeshResult** enum, and for the more complex operations, also an operation-specific data structure like **DMesh3.EdgeCollapseInfo**. These structs provide information on what happened to the mesh - indices of elements removed and added, and so on.

# Metadata, Timestamps, Sanity Checks, and Serialization

DMesh3 has a few other capabilities that are useful in certain situations. In the extensibility direction, you can add arbitrary string/object pairs via **AttachMetadata()**, and look up said objects later using **FindMetadata()**. This is a bit of a hack, frankly, but it means that if absolutely necessary, you can attach data to a mesh as it is passed from one place to another. For example, when working with a custom mesh format, you can use AttachMetadata() to hang on to any format-specific mesh attribute data, without having to subclass or duplicate every mesh processing function you need to call. Note, however, that metadata is **not** copied/transferred by the DMesh3 copy constructors.

It is often useful to know if a mesh has changed. We find this happens frequently in interactive contexts, where we need to build caches/buffers to render a mesh, and we want to rebuild these caches if the mesh changes. Rather than events, DMesh3 has **timestamps** which are updated when the mesh is modified. These are not actually date/times, but rather just integers that are incremented on any mesh update. **DMesh3.Timestamp** is incremented when any mesh attribute changes, while **DMesh3.ShapeTimestamp** is only incremented when the mesh topology or shape changes (so, not when a vertex normal/color/uv or face group is updated).

Most of the functions in DMesh3, and the code in the rest of g3Sharp, assumes that the mesh is internally consistent - ie no valid triangle references invalid vertices, that sort of thing. However, particularly when loading mesh files or constructing them from external index buffers, this may not be the case. The function **CheckValidity****()** can be used to verify that the mesh is well-formed. If you are encountering weird issues, it is a good idea to throw in a few calls to this function. Note that by default it will consider **bowtie** vertices to be invalid, this is configurable via the first argument and may not be desirable in certain contexts.

The **IsSameMesh()** function will tell you if two meshes are "the same", and is useful primarily for testing. By default it only checks that the vertices and triangles are the same, checking of other mesh elements can be enabled with the many arguments.

Finally, if you need to serialize a DMesh3, you can use the functions **gSerialization.Store()** and **gSerialization.Restore()**. The restored mesh will preserve all vertex/triangle/edge indices and allocated vertex/triangle attributes. However if you don't care about these things, you can get a much more compact serialization by just storing the vertex coordinates and triangle indices yourself (although reconstructing the DMesh3 from the deserialized buffers will be more expensive).

# Questions Answered

## Why an indexed mesh?

Many mesh libraries that aim to support similar dynamic-mesh capabilities use pointer-based meshes, where a level of indirection allows for the "invalid-index" problem to be avoided. However, such approaches tend to not scale well to huge meshes. If each vertex and triangle is a full object, then the memory allocator must manage millions of tiny objects, which is not ideal. Other clever pointer-like schemes can be used, but if taken to the extremes of efficiency, the result is often essentially an indexed mesh, but without the advantages of being able to make assumptions about indices.

Having indices means we can iterate over them, or over subsets. Even when the index space has gaps, it can be beneficial to iterate over indices and simply test-and-skip invalid indices - particularly in multi-threaded code. An index iteration doesn't become invalid if we modify the mesh during an iteration. We can do math on indices, and serializing index-based data structures is much simpler. And finally, trying to debug pointer-based mesh code is sheer madness, in the author's humble opinion.

## Is this a Winged-Edge Mesh?

No. Although DMesh3 edges do connect two vertices and have two adjacent faces, we do not store the other topological connectivity links common in Winged Edge meshes, and we do not guarantee anything about the ordering of faces.

## Why not Half-Edge?

Half-Edge mesh data structures have the advantage that all elements have fixed size, ie our per-vertex variable-sized list is not necessary. They also have other benefits, and are more efficient for various kinds of element-adjacency iterations. However, Half-Edge is generally a pointer-based mesh data structure, and so inherits some of the problems described above. In addition, half-edge mesh code, although conceptually elegant, can be quite difficult to read.

## Can DMesh3 store non-manifold meshes?

DMesh3 does allow for **bowtie** vertices, ie non-manifold vertices that are connected to more than two boundary edges. However, some functions in DMesh3 will fail to operate properly on edges connected to bowtie vertices, in particular CollapseEdge().

Non-manifold edges, where more than two faces meet at an edge, cannot be represented because the DMesh3 edge elements only reference two triangles. Functions like AddTriangle() will return an error if you try to add a non-manifold triangle. The **NTMesh3** class is a variant of **DMesh3** that can store non-manifold topology, however it currently does not have many of the other DMesh3 operations implemented.