Triangular mesh topology

Question

Hi,

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

Answer 1

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

Answer 2

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.