views:

336

answers:

2

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

A: 

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
David Rutten
To avoid people thinking you're just rep-harvesting, it's probably best to 1) wait a while before posting your own answer or 2) move this answer up to the original question.
Scottie T
@Scottie T: Self-answers of this sort are allowed, or even encourages by the faq. I tend to make the answer CW beacuse otherwise it feels like gaming the TFGITW problem. See: http://stackoverflow.com/questions/18557/how-does-stackoverflow-work-the-official-faq/119658#119658
dmckee
Scottie, I had no idea, thanks for pointing it out. I think I won't tinker with it anymore now though.
David Rutten
+1  A: 

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.

Ofek Shilon