Storing the triangle edges in this way is redundant. 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. This involves iterating over each edge one-ring of each of the vertices of the triangle.
In particular, consider finding the three neighbour triangles for a given triangle. However, because of this variable-sized list, some common tasks are still relatively expensive. 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. 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. But at the conceptual level, we have largely solved our connectivity problems. At the implementation level, this means we need dynamically-sized per-vertex lists, which we will discuss further below. Storing the set of edges connected to a vertex adds a significant complication, because the number of edges is variable. So, we will add it directly into our mesh data structure. 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. Even for something as basic as deleting a set of vertices, we'll need to find the list of affected faces. The SimpleMesh class stores a mesh in this format.īut 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. We can do a lot with just the basic indexed mesh, and it is the most memory-efficient mesh representation. If we want to animate the mesh, we can modify the vertices. If we want to estimate vertex normals, we can iterate over the triangles and accumulate their facet normals at the vertices. For example to render the triangles we just need the vertices of each triangle. Then, each triangle is an integer 3-tuple (a,b,c), where each integer is the index of one of the vertices.įor many mesh processing tasks, this is all we really need. In DMesh3 we store these in double-precision floating point.
Each vertex is a triplet or 3-tuple of real values (x,y,z) which are the 3D coordinates. The diagram below shows how these things connect up. 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. This is similar to the basic mesh data structures used in many other libraries. This means that we reference components of the mesh - ie the vertices and triangles - by integer indices, rather than pointers. 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.Īt its core, DMesh3 is an index-based triangle mesh. In this post I will dive into the details of this data structure and the operations it provides. If so, then the triangle mesh data structure is kind of important! In g3Sharp, this is the DMesh3 class. If you are using the g3Sharp library, there is a good chance it's because you need to do some things with triangle meshes.
0 kommentar(er)
