Mesh Iterators and Circulators

• Iterators
• How to use iterators in OpenMesh
• Skipping Iterators
• Circulators
• How to use circulators in OpenMesh

Iterators

The mesh provides linear iterators (that enumerate vertices, halfedges, edges, and faces). These can be used to easily navigate through a mesh. Each iterator XYZIter also exists in a const version ConstXYZIter.

All iterators are defined in the namespace OpenMesh::Iterators. They are template classes that expect a mesh as template argument to be fully specified. You should use the iterator types provided by the mesh itself, i.e. MyMesh::VertexIter instead of OpenMesh::Iterators::VertexIterT<MyMesh>.

The iterators are:

MyMesh mesh;

// iterate over all vertices
for (MyMesh::VertexIter v_it=mesh.vertices_begin(); v_it!=mesh.vertices_end(); ++v_it) 
   ...; // do something with *v_it, v_it->, or *v_it

// iterate over all halfedges
for (MyMesh::HalfedgeIter h_it=mesh.halfedges_begin(); h_it!=mesh.halfedges_end(); ++h_it) 
   ...; // do something with *h_it, h_it->, or *h_it

// iterate over all edges
for (MyMesh::EdgeIter e_it=mesh.edges_begin(); e_it!=mesh.edges_end(); ++e_it) 
   ...; // do something with *e_it, e_it->, or *e_it

// iterator over all faces
for (MyMesh::FaceIter f_it=mesh.faces_begin(); f_it!=mesh.faces_end(); ++f_it) 
   ...; // do something with *f_it, f_it->, or *f_it

The corresponding const counterparts are

• ConstVertexIter,
• ConstHalfedgeIter,
• ConstEdgeIter,
• ConstFaceIter.

The linear iterators are conformant to STL iterators. For a description of their interface see OpenMesh::Concepts::IteratorT.

When using iterators, use the pre-increment operation (++it) for efficiency reasons.

Deprecated:

While it is possible to use handle() to get the handle of the item referred to by the iterator, this function is deprecated. Simply dereference the iterator instead.

Deleted Elements

If no elements of a mesh are marked as deleted, the indices provided by idx() are consecutive numbers from 0 to number of elements-1 (in the case of vertices this would be from 0 to n_vertices()-1).

However, note that this is not the case when elements are marked as deleted and OpenMesh::ArrayKernel::garbage_collection() has not yet been called.

After garbage_collection() has been called the elements are reorganized and their handles and iterators are guaranteed to be consecutive numbers again.

OpenMesh uses a lazy deletion scheme to avoid unnecessary updates to the data structure. The halfedge data structure will always be updated directly to ensure that following algorithms will have the correct iterator setups.

So if you delete a face, The face itself will still exist but the halfedges which are now located at the hole will be updated directly, which means that circulators on the adjacent vertices will not come across the face anymore.

If an edge is deleted, the adjacent faces will be removed as well (flagging them deleted and updating the surrounding halfedges). The edge itself will also be flagged as deleted. Again the circulators will not see the deleted primitives anymore.

For a vertex, all adjacent faces and edges are deleted with the schemes above and the vertex flagged as deleted.

The iterators, going across vertices edges and faces will still enumerate all primitives (including deleted ones). Except if you use the skipping iterators, which will skip deleted primitives. The circulators always only enumerate primitives which are not deleted.

Note

• If you delete elements on the mesh, they will still be enumerated by the standard iterators. To skip deleted elements, use the Skipping Iterators
• An iterator to an item usually needs more memory than a handle of an item. To store many references to an item, it is therefore better to use handles.

How to use iterators in OpenMesh

This example shows how to iterate over all faces of a mesh:

MyMesh mesh;

for(MyMesh::FaceIter f_it = mesh.faces_begin(); f_it != mesh.faces_end(); ++f_it) {
    std::cout << "The face's valence is " << mesh.valence( *f_it ) << std::endl;
}

Skipping Iterators

All iterators are also available as skipping iterators. If elements are deleted on a mesh, the standard iterators go over all elements, even deleted ones(which are available until a garbage_collection is done). The skipping iterators ignore these elements. You can retrieve a skipping iterator by calling one of the following functions:

• vertices_sbegin(),
• edges_sbegin(),
• halfedges_sbegin(),
• faces_sbegin()

The ends for these iterators are equal to the standard iterator ends (e.g. vertices_end() ).

Circulators

OpenMesh also provides so called Circulators that provide means to enumerate items adjacent to another item of the same or another type. For example, a VertexVertexIter allows to enumerate all vertices immediately adjacent to a (center) vertex (i.e. it allows to enumerate the so-called 1-ring of the center vertex). Analogously, a FaceHalfedgeIter enumerates all the halfedges belonging to a face. In general, CenterItem_AuxiliaryInformation_TargetItem_Iter designates a circulator that enumerates all the target items around a given center item.

The constructor of a circulator is of the form Circulator(MeshType mesh, TargetHandle center_handle), i.e. it takes a mesh and the handle of the item to circulate around.

The circulators around a vertex are:

• VertexVertexIter: iterate over all neighboring vertices.
• VertexIHalfedgeIter: iterate over all incoming halfedges.
• VertexOHalfedgeIter: iterate over all outgoing halfedges.
• VertexEdgeIter: iterate over all incident edges.
• VertexFaceIter: iterate over all adjacent faces.

The circulators around a face are:

• FaceVertexIter: iterate over the face's vertices.
• FaceHalfedgeIter: iterate over the face's halfedges.
• FaceEdgeIter: iterate over the face's edges.
• FaceFaceIter: iterate over all edge-neighboring faces.

Other circulators:

• HalfedgeLoopIter: iterate over a sequence of Halfedges. (all Halfedges over a face or a hole)

All circulators provide the operations listed in CirculatorT<Mesh>, which are basically the same as the iterator funtions.

Note

Circulators are similar to bidirectional iterators and therefore they have the bidirectional_iterator_tag. However, the bidirectional requires that the attribute OpenMesh::Attributes::PrevHalfedge is available. Otherwise it is just a forward iterator.

Deprecated:

While it is possible to use operator bool(), which returns true, as long as the circulator hasn't reached the end of the sequence, this function is deprecated. Use the function is_valid() instead.

OpenMesh provides the following functions (defined in OpenMesh::PolyConnectivity) to get circulators around a specified center item:

/**************************************************
 * Vertex circulators
 **************************************************/

// Get the vertex-vertex circulator (1-ring) of vertex _vh
VertexVertexIter OpenMesh::PolyConnectivity::vv_iter (VertexHandle _vh);

// Get the vertex-incoming halfedges circulator of vertex _vh
VertexIHalfedgeIter OpenMesh::PolyConnectivity::vih_iter (VertexHandle _vh);

// Get the vertex-outgoing halfedges circulator of vertex _vh
VertexOHalfedgeIter OpenMesh::PolyConnectivity::voh_iter (VertexHandle _vh);

// Get the vertex-edge circulator of vertex _vh
VertexEdgeIter OpenMesh::PolyConnectivity::ve_iter (VertexHandle _vh);

// Get the vertex-face circulator of vertex _vh
VertexFaceIter OpenMesh::PolyConnectivity::vf_iter (VertexHandle _vh);

/**************************************************
 * Face circulators
 **************************************************/

// Get the face-vertex circulator of face _fh
FaceVertexIter OpenMesh::PolyConnectivity::fv_iter (FaceHandle _fh);

// Get the face-halfedge circulator of face _fh
FaceHalfedgeIter OpenMesh::PolyConnectivity::fh_iter (FaceHandle _fh);

// Get the face-edge circulator of face _fh
FaceEdgeIter OpenMesh::PolyConnectivity::fe_iter (FaceHandle _fh);

// Get the face-face circulator of face _fh
FaceFaceIter OpenMesh::PolyConnectivity::ff_iter (FaceHandle _fh);

Additionally to the normal circulators there exists some for each direction (clock-wise, counterclock-wise). Those circulators might be slower than the normal one, but the direction of circulation is guaranteed. You can get these types of circulators by adding the infix "ccw" or "cw" to the function used to request the circulator of an item after the underscore. Example:

VertexVertexIter vvit = mesh.vv_iter(some_vertex_handle);          // fastest (clock or counterclockwise)
VertexVertexCWIter vvcwit = mesh.vv_cwiter(some_vertex_handle);    // clockwise
VertexVertexCCWIter vvccwit = mesh.vv_ccwiter(some_vertex_handle); // counter-clockwise

It is also possible to convert a cw circulator to a ccw circulator and vice versa. For this purpose, each circulator provides a constructor taking the other circulator as input. If a cw circulator is converted, the ccw circulator points on the same element as the cw circulator pointed on, but the direction for the increment and decrement changed.
The conversion is only valid for valid circulators. The resulting circulator from a invalid circulator is still invalid, but might behave in a fashion not expected by normal iterators. Example:

VertexVertexCWIter vvcwit = mesh.vv_cwend(some_vertex_handle);
VertexVertexCCWIter vvccwit = VertexVertexCCWIter(vvcwit); //conversion of an invalid circulator
 --vvcwit;  //is valid now (if the range >= 1)
 ++vvccwit; //can still be invalid

CW and CCW circulators requires that OpenMesh::Attributes::PrevHalfedge is available.

Note

For every circulator there also exists a constant version. To make use of these constant circulators just add the prefix
"Const" to the type specifier and add the prefix "c" to the function used to request the circulator of an item. Example:

ConstVertexVertexIter cvvit = mesh.cvv_iter(some_vertex_handle);

Note

When constructing Circulators from iterators, make sure you don't create a circulator of an deleted element(e.g. FaceVertexiter of a deleted Face), as this will lead to unpredictable behaviour. Using skipping iterators for iterating over the elements and creating circulators from them is safe as they don't contain deleted elements.

How to use circulators in OpenMesh

The following code example now shows how to enumerate the 1-ring of each vertex:

MyMesh mesh;

// (linearly) iterate over all vertices
for (MyMesh::VertexIter v_it=mesh.vertices_sbegin(); v_it!=mesh.vertices_end(); ++v_it)
{
  // circulate around the current vertex
  for (MyMesh::VertexVertexIter vv_it=mesh.vv_iter(*v_it); vv_it.is_valid(); ++vv_it)
  {
    // do something with e.g. mesh.point(*vv_it)
  }
}

Enumerating all halfedges adjacent to a certain face (the inner halfedges) is accomplished as follows:

MyMesh mesh;

...

// Assuming faceHandle contains the face handle of the target face

MyMesh::FaceHalfedgeIter fh_it = mesh.fh_iter(faceHandle);

for(; fh_it.is_valid(); ++fh_it) {
    std::cout << "Halfedge has handle " << *fh_it << std::endl;
}