Halfedge_Mesh
In our code, a halfedge mesh -- represented by the Halfedge_Mesh
structure -- is a pointer-based repository for manifold mesh connectivity and data.
This section provides an overview of some key ideas about halfedge meshes and the Halfedge_Mesh
structure in particular. Consider it a supplement to a thorough reading of src/geometry/halfedge.h
.
A Halfedge_Mesh
wrangles four mesh element types: Vertices
, Edges
, Faces
, and Halfedges
:
As a pointer-based structure, Halfedge_Mesh
operations will often require the allocation and deallocation of new elements. Rather than using the C++ new
and delete
operators directly, Halfedge_Mesh
instead provides emplace_*
and erase_*
functions to allocate and free (respectively) mesh elements. This allows the mesh to track all of the elements that belong to it in std::list
s (called vertices
, edges
, faces
, and halfedges
).
The functions also maintain a unique-within-the-mesh id
value for mesh elements, which can be useful for debugging (printing v->id
for debug messages is a lot more readable than &*v
). As an additional feature, the high-order bit of the id
is set by the erase_*
functions. So if you start seeing very very large id values, probably you have a use-after-free bug.
In our halfedge mesh structure, elements store both connectivity information as references (really, std::list< >
iterators) to other elements.
Vertices store a reference to one of the halfedges directed away from them in Vertex::halfedge
:
Edges store a reference to one of the halfedges that make them up in Edge::halfedge
:
Faces store a reference to one of the halfedges that circulate around them in Face::halfedge
:
Halfedges store the bulk of the connectivity information. They store a reference to the halfedge on the other side of their edge in Halfedge::twin
, a reference to the halfedge that follows them in their current face in Halfedge::next
, a reference to the vertex they leave in Halfedge::vertex
, a reference to the edge they border in Halfedge::edge
, and a reference to the face they circulate in Halfedge::face
:
In addition to the mesh connectivity, the mesh stores data on each of the mesh features.
Vertices store their location in position
, and information about skinning (A4!) in bone_weights
.
Edges store a sharp
flag which is used in shading normal computation.
Faces store a boundary
flag which tells you if the face is a solid face or a face that exists to book-keep holes in the model:
Halfedges store corner_uv
and corner_normal
values, which are used to set texture coordinates and shading normals for the corner of the face associated with the halfedge.
Since it is often the case that you are adding or removing features from the mesh, we include an overloaded interpolate_data
helper function to help in interpolating/merging Vertex::bone_weights
and Halfedge::corner_*
data. (Handling of Edge::sharp
is probably either obvious [as in splits] or arbitrary [as in merges with different flags]. Handling of Face::boundary
is generally specified by the operation.)
Check the comments near interpolate_data
in halfedge.h
for some usage examples.
Sometimes it is useful to associate temporary storage with the various mesh elements. E.g., to store a position or flag on a mesh element during an algorithm. You can use the fact that mesh elements have stable addresses (and we provide a std::hash
specialization that hashes their addresses) to do this:
std::unordered_map< VertexRef, Vec3 > next_position; //store data per-element
std::unordered_set< VertexRef > special; //store a set of
for (VertexRef v = vertices.begin(); v != vertices.end(); ++v) {
next_position[v] = Vec3(0.0f, 0.0f, 0.0f);
if (check_something(v)) {
was_special.emplace(v);
}
}
//... later ...
for (VertexRef v = vertices.begin(); v != vertices.end(); ++v) {
v->position = next_position.at(v);
if (was_special.count(v)) {
//...
}
}
Keep in mind that neither addresses or the order of iteration of hashed containers (unordered_*
) will be stable between OS's, standard library versions, or even (if using address-space layout randomization) runs of the same program. This probably won't matter for you, but I'm mentioning it now just in case.
A Halfedge_Mesh
structure is a sea of pointers. It is surprisingly easy to tangle these pointers into a mess that fails to represent a manifold mesh (or, really, a consistent mesh at all). In order to provide guidance on what constitutes a reasonable setting for a mesh, we define a valid mesh as one for which the following properties hold:
e
, e->halfedge(->twin)^n
is a cycle of exactly two halfedges, and these are exactly the halfedges with h->edge
equal to e
.f
, f->halfedge(->next)^n
is a cycle of at least three halfedges, and these are exactly the halfedges with h->face
equal to f
.v
, v->halfedge(->twin->next)^n
is a cycle of at least two halfedges, and these are exactly the halfedges with h->vertex
equal to v
.These properties are checked by the Halfedge_Mesh::validate()
function, which returns nullopt
if the mesh is valid or an element reference and an explanatory message if something is wrong with the mesh.
Table of Content