Triangular mesh topology
-
21-08-2019 - |
Question
I've got a triangular mesh class which contains a list of nodes (2d in my case but that shouldn't matter) and a list of faces. Each face is a triangle and it only contains the indices into the node array. The mesh comes out of a Delaunay algorithm so it's very clean.
For every node in the mesh I need to find which nodes are connected to it with a single edge. What would be a fast way to construct and search this topology database?
Much obliged, David Rutten
Solution
There are two somewhat-standard data structs that facilitate mesh topology-queries. One is Winged Edges (commonly referred to also as half-edge), and the other is Directed Edges. Google around and you'd get kajillions of details, and various-level intros into each one.
Don't know enough about your scenario to recommend one of them. E.g., directed edges is storage-optimized, and best suited for very large meshes. Winged edges is considered a 'classic', and is a good starting point for more advanced flavours.
Actually if you're certain that's the only query you'd need, then both are an overkill and you'd do just fine with a single hash. If, however, you find yourself in need of efficient answers to queries like -
- Which faces use this vertex?
- Which edges use this vertex?
- Which faces border this edge?
- Which edges border this face?
- Which faces are adjacent to this face?
You should consider diving into one of them.
OTHER TIPS
I think I've stared myself blind on HashTables, Dictionaries and Sorted Lists... The following is probably the easiest and fastest:
Public Sub SolveConnectivity(ByVal nodes As Node2List, ByVal faces As List(Of Face))
m_map = New List(Of List(Of Int32))(nodes.Count)
'Create blank lists
For i As Int32 = 0 To nodes.Count - 1
m_map.Add(New List(Of Int32)(6))
Next
'Populate connectivity diagram
For i As Int32 = 0 To faces.Count - 1
Dim F As Face = faces(i)
m_map(F.A).Add(F.B)
m_map(F.A).Add(F.C)
m_map(F.B).Add(F.A)
m_map(F.B).Add(F.C)
m_map(F.C).Add(F.A)
m_map(F.C).Add(F.B)
Next
End Sub