Skip to content

Mesh Topology

Often we need to perform geometric operations by examining relationships between the vertices, edges and faces of a mesh. Indicative examples include finding: the edge or faces connected to a vertex or the edge shared between two faces. All those relationships are captured by the notion of mesh topology. Already the indexed mesh representation is topological in the sense that it encodes mesh faces in terms of their relationship with the list of vertices.

Definitions

Nodes

Conceptually, a node is a shared point of a mesh. The list of points in an indexed mesh can be considered as its node list. However, a node i is the index of the point in the list, not the 3D point itself. Typically, nodes are integers serially numbered from 0 to n - 1, where n is the number of points. Another important property of nodes is that they represent unique points, so the mesh needs to be deduplicated.

Edges

Mesh edges are represented by pairs of nodes [s, t], where s and t are integer indices expressing which two points are connected. In cases we do not care about the direction of the edge [s, t] and [t, s] represent the same edge. However, if we do, then those two pairs represent edges with opposite directions.

Faces

Mesh faces are represented by triplets of nodes [a, b, c] for triangulations, where a, b and c are the nodes. This is the convention already used for indexed meshes. Generally, the nodes in a face are oriented, that is their order in important, as explained in the earlier discussion about mesh normals.

Connectivity

Face to Node

The face-to-node map enables queries such as which nodes are connected to a particular face: face → list( node ). This information is already available in the mesh faces list.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    ''' Face Index -> Node Indices
    '''
    def NodesFromFace( self, face ):
        return self.Faces[face]

Node to Face

The node-to-face map enables queries such as which faces are connected to a particular node: node → list( face ). It is the exact opposite of a mesh's face list which conveys which nodes are connected to a face: face → list( node ). It may be represented as a list with the same length as the number of points, with each item containing another list of indices pointing to the mesh's faces. The faces about a node are also known as a fan or umbrella.

The method BuildNodeToFaceMap( ) creates a list of sets, one per node, and then iterates over each face updating the map with the node indices encountered. Sets are used because they cull duplicate node indices but they are simplified away into lists before completing the mapping. The method FacesFromNode( ) returns a list of the faces connected to a node.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

        self.BuildNodeToFaceMap( )

    def BuildNodeToFaceMap( self ):
        self.NodeToFace = [set( ) for _ in self.Vertices]
        for index, nodes in enumerate( self.Faces ):
            for node in nodes:
                self.NodeToFace[node].add( index )
        self.NodeToFace = [list( indices )
            for indices in self.NodeToFace]
        return self

    ''' Node Index -> Face Indices
    '''
    def FacesFromNode( self, node ):
        return self.NodeToFace[node]

Face to Edge

The face-to-edge map enables queries such as which edges are connected to a particular face: face → list( edge ). Since these relationships are trivially computed from the face list, we do not need to store the data. Instead we can implement this in the form of an iterator. Additionally, in some cases we need the same edge expressed as both ( s, t ) and ( t, s ).

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    ''' Face Index -> Edge Indices
    '''
    def EdgesFromFace( self, face, both_ways = True ):
        nodes = self.Faces[face]
        count = len( nodes )
        for index in range( count ):
            s = nodes[index]
            t = nodes[( index + 1 ) % count]
            yield ( s, t )
            if( both_ways ):
                yield ( t, s )

Node to Node

The node-to-node map enables queries such as which nodes are connected to a particular node: node → list( node ). It has as many items as the number of points, with each item containing a list of connected nodes. It is constructed by iterating over each face, collecting the three edges encountered. Again the use of sets is to prevent duplicates. The edges between a node and its adjacent nodes are also known as spokes.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

        self.BuildNodeToNodeMap( )

    def BuildNodeToNodeMap( self ):
        self.NodeToNode = [set( ) for _ in self.Vertices]
        for a, b, c in self.Faces:
            self.NodeToNode[a].add( b ) #-- a -> b
            self.NodeToNode[a].add( c ) #-- a -> c

            self.NodeToNode[b].add( c ) #-- b -> c
            self.NodeToNode[b].add( a ) #-- b -> a

            self.NodeToNode[c].add( a ) #-- c -> a
            self.NodeToNode[c].add( b ) #-- c -> b
        self.NodeToNode = [list( indices )
            for indices in self.NodeToNode]
        return self

    ''' Node Index -> Node Indices
    '''
    def NodesFromNode( self, node ):
        return self.NodeToNode[node]

Edge to Face

The edge-to-face map enables queries such as which faces are connected to a particular edge: edge → list( face ). Unlike the previous maps, we do not know the number of edges in advance. Since an edge requires two indices s and t, we cannot use a lists but instead a dictionary with tuples ( s, t ) for keys. The edge-to-face map is constructed by iterating over each face, collecting the edges encountered. Again the use of sets is to prevent duplicates and we double store each edge ( s, t ) and ( t, s ) for convenience.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

        self.BuildEdgeToFaceMap( )

    def BuildEdgeToFaceMap( self ):
        self.EdgeToFace = { }
        for index in range( len( self.Faces ) ):
            for edge in self.EdgesFromFace( index, both_ways = True ):
                if( not ( edge in self.EdgeToFace ) ):
                    self.EdgeToFace[edge] = set( )
                self.EdgeToFace[edge].add( index )
        self.EdgeToFace = [list( indices )
            for indices in self.EdgeToFace]
        return self

    ''' Edge Indices -> Face Indices
    '''
    def FacesFromEdge( self, edge ):
        return self.EdgeToFace[edge]

Face to Face

The face-to-face map enables queries such as which faces are connected to a particular face: face → list( face ). This map can be represented using a list since we know the number of faces in advance. The construction below uses the edge-to-face map as a shortcut. Since two faces are connected with one another through a shared edge, the values of the EdgeToFace dictionary contains faces that are incident. Thus, we just need to use their combinations making sure we don't make the superfluous association between a face and itself.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

        self.BuildEdgeToFaceMap( )
        self.BuildFaceToFaceMap( )

    def BuildFaceToFaceMap( self ):
        self.FaceToFace = [set( ) for _ in self.Faces]
        for faces in self.EdgeToFace.values( ):
            for source in faces:
                for target in faces:
                    if( source != target ):
                        self.FaceToFace[source].add( target )
        self.FaceToFace = [list( indices )
            for indices in self.FaceToFace]
        return self

    ''' Face Index -> Face Indices
    '''
    def FacesFromFace( self, face ):
        return self.FaceToFace[face]

Rhino Topology

In Rhino mesh topology is available via the MeshTopologyVertices and MeshTopologyEdges properties of a mesh object. The term topology vertices is associated with the concept of a node and it is used to contrast with geometry vertices or just mesh vertices.

Rhino performs vertex deduplication before constructing the topology data structures. If the mesh has no duplicates then the topology vertices, or nodes, are identical to the geometry vertices. However, if there are duplicate geometry vertices then a single topology vertex, or node, is associated with all of them. Therefore, conversion between geometry to topology vertices is one-to-one but reverse is in general one-to-many.

""" Mesh has duplicates if counts are unequal
"""
print( mesh.Vertices.Count )
print( mesh.TopologyVertices.Count )

''' Topology Vertex to Geometry Vertex ( 1 -> n )
'''
indices = mesh.TopologyVertices.MeshVertexIndices( node )

''' Geometry Vertex to Topology Vertex ( 1 -> 1 )
'''
node = mesh.TopologyVertices.MeshVertexIndices( index )

Adjacencies between nodes and other topology entities can be accessed as seen below.

''' Node Adjacencies
'''
nodes = mesh.TopologyVertices.ConnectedTopologyVertices( node )
edges = mesh.TopologyVertices.ConnectedEdges( node )
faces = mesh.TopologyVertices.ConnectedFaces( node )

Topology edges are expressed as IndexPair objects containing the source s and target t topology vertices, named as I and J, respectively. Edges are stored in a serial format and they are accessible by index as seen below.

''' Node Indices -> Edge Index
'''
index = mesh.MeshTopologyEdges.GetEdgeIndex( s, t )

''' Edge Index -> Node Indices
'''
nodes = mesh.MeshTopologyEdges.GetTopologyVertices( index )
print( nodes.I, nodes.J )

Adjacencies between edges and other topology entities can be accessed as seen below.

''' Edge Adjacencies
'''
edges = mesh.MeshTopologyEdges.GetEdgesForFace( face )
faces = mesh.MeshTopologyEdges.GetConnectedFaces( edge )

Topology Analysis

The connectivity maps developed enable understanding several interesting mesh properties and performing operations that require information about the local neighborhood of a vertex or face.

Boundary Edges

The number of faces incident to an edge provides insight regarding whether the mesh is an open surface or potentially a closed solid. Edges with only one adjacent face must be on a surface boundary. Therefore, such a mesh cannot not represent a closed solid, which ought to have no boundary edges. Boundary edges are also known as naked.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    def HasBoundaryEdges( self ):
        for faces in self.EdgeToFace.values( ):
            if( len( faces ) == 1 ):
                return True
        return False

    def BoundaryEdges( self ):
        edges = set( )
        for ( s, t ), faces in self.EdgeToFace.items( ):
            if( len( faces ) == 1 ):
                if( s > t ): s, t = t, s
                edges.add( ( s, t ) )
        return list( edges )

Non-Manifold Edges

Edges with more than two incident faces are also known as non-manifold. Surfaces with non-manifold edges cannot be properly oriented in the sense of making their normals consistently points towards an interior and an exterior direction. Therefore, meshes with non-manifold edges cannot also represent closed solids.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    def HasNonManifoldEdges( self ):
        for faces in self.EdgeToFace.values( ):
            if( len( faces ) > 2 ):
                return True
        return False

    def NonManifoldEdges( self ):
        edges = set( )
        for ( s, t ), faces in self.EdgeToFace.items( ):
            if( len( faces ) > 2 ):
                if( s > t ): s, t = t, s
                edges.add( ( s, t ) )
        return list( edges )

Two-Manifold Edges

One of the conditions for determining whether a mesh represents a solid object is such that all its edges have exactly two adjacent faces. This is easy to check using the edge-to-face map.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    def HasSolidEdges( self ):
        for faces in self.EdgeToFace.values( ):
            if( len( faces ) != 2 ):
                return False
        return True

Multiple Domains

A mesh may contain multiple surface fragments that are not connected with one another. This is also known as a multiply connected domain condition. To check whether a mesh represents one continuously connected surface or solid we need to start from a face, say the first one, and walk from face to face until we visit all connected faces once. If by the end of this process the number of faces visited is not equal with total number of faces, then we know that the mesh has multiply connected domains.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    def HasMultipleDomains( self, seed = 0 ):
        visited = set( [seed] )
        queue = [seed]
        while len( queue > 0 ):
            face = queue.pop( 0 )
            for adjacent in self.FaceToFace[face]:
                if( adjacent in visited ): continue
                visited.add( adjacent )
                queue.append( adjacent )
        return len( visited ) != len( self.Faces )

Face Orientation

Checking whether the normals of a simply connected mesh are consistently oriented can be performed by examining pairs of adjacent faces and evaluating the sign of their dot products. If all normals are aligned then the mesh fulfils another necessary condition for representing a solid.

class IndexedMesh:
    def __init__( self, vertices, faces ):
        self.Vertices = vertices
        self.Faces    = faces

    ''' Face Index -> Face Normal
    '''
    def FaceNormalAt( self, face ):
        pa, pb, pc = self.TriangleAt( face )
        return Vector3d.CrossProduct(
            pb - pa, pc - pb )

    def HasInconsistentNormals( self ):
        visited = set( [0] )
        stack = [0]
        while len( queue > 0 ):
            face = stack.pop( )
            normal = self.FaceNormalAt( face )
            for adjacent in self.FaceToFace[face]:
                if( adjacent in visited ): continue
                if( normal * self.FaceNormalAt( adjacent ) < 0 ):
                    return True
                visited.add( adjacent )
                stack.append( adjacent )
        return False