Neighborhood traversal

A basic task in any mesh processing algorithm is the systematic traversal of mesh items and their local neighborhoods. The halfedge based mesh representation is very efficient in this respect.

Accessing vertices, faces, and halfedges

Once a mesh has been constructed, its items (vertices, halfedges, and faces) can be accessed via properties vertices, halfedges, and faces. The vertex coordinate array is exposed via points. Note the distinction between vertices and points in \(\mathbb{R}^3\) – vertices are topological entities that have a location attribute point, vertex coordinates can change without changing mesh topology.

Note

Elements of the vertex list and rows of the coordinate array correspond by index. Elements are stored in insertion order. The same is true for the face list.

Modifying vertex coordinates

We want to project the mesh onto the \(xy\)-plane. There are several equivalent ways to do this. We can use the vertex list of a mesh and access vertex coordinates via the point property of a vertex:

for v in mesh.vertices:                     # mesh.vertices is a list
    v.point[2] = 0.0                        # set the z-coordinate to zero

We can directly access the vertex coordinate array. The correspondence of vertices to coordinates is given by index but not needed for this task:

for p in mesh.points:                       # mesh.points is of type ndarray
    p[2] = 0.0                              # set the z-coordinate to zero

Since the vertex coordinate array is of type ndarray we can use slicing to set all \(z\)-coordinates:

mesh.points[:, 2] = 0.0                     # set all z-coordinates to zero

Computing edge midpoints

The halfedges dictionary maps pairs of Vertex objects to Halfedge objects. The following loop will compute (half)edge midpoints:

for h in mesh.halfedges.values():
    m = 0.5 * (h.origin.point + h.target.point)

Extracting face definitions

As already explained the face defining sequence of vertices of a face \(f\) can be extracted from any incident halfedge of \(f\) by following its next attribute:

v = [f.halfedge.origin.index]
h = f.halfedge.next

while h is not f.halfedge:
    v.append(h.origin.index)
    h = h.next

The above loop is equivalent to the following list comprehension:

v = [x for x in f]

Note

The vertices and faces attributes of a mesh expose deleted mesh items. Applying one of the corresponding predefined iterators verts() and faces() to a mesh will skip those items.

Local neighborhood traversal

The following recipe will visit adjacent vertices of a vertex \(v\) in counter-clockwise order:

# Start with the halfedge stored as attribute of a vertex v
h = v.halfedge

# Visit the adjacent vertices of v in ccw-order.
while True:
    # Get the target vertex of h and do something with it.
    w = h.target
    ...
    # Rotate the halfedge counter-clockwise.
    h = h.prev.pair

    # Check if we have reached the starting halfedge again.
    if h is v.halfedge:
        break

The iterators module provides several generic iterators. The most basic ones being verts(), halfs(), edges(), and faces(). The behavior of an iterator depends on the type of the provided argument. Using the verts() iterator, the above recipe simplifies to

import m3sh.iterators as it

# Visit the adjacent vertices of v in ccw-order.
for w in it.verts(v):
    # Do something with w ...
    ...

Vertex neighborhood iterators

When applied to a vertex instance, the verts() iterator can be used to visit the 1-ring neighbors of a vertex in counter-clockwise order as induced by the mesh orientation:

import m3sh.iterators as it

# Visit all vertices of a mesh in the order they were added.
for v in mesh.vertices:
    print(f'1-ring neighbors of vertex {int(v)}:')
    print('\t', end='')

    # Visit all vertices adjacent to vertex v, i.e., all vertices
    # connected to v via an edge.
    for w in it.verts(v):
        print(int(w), end=' ')

    print()

When applied to a vertex \(v\), the faces() iterator will traverse all faces \(f\) with \(v \in f\) in counter-clockwise order:

import m3sh.iterators as it

for v in mesh.vertices:
    print(f'Faces incident to vertex {int(v)}:')
    print('\t', end='')

    for f in it.faces(v):
        print(int(f), end=' ')

    print()

Face neighborhood iterators

Two facs are adjacent if they share a common edge. When applied to a face \(f\), the face() iterator visits all adjacent faces in counter-clockwise order:

import m3sh.iterators as it

for x in it.faces(f):
    print(x)