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 (v0, v1, t0, t1), where if the edge is a boundary edge, then t1 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 (eab, ebc, eca) 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.