potential implementation in 2023-10-04 1345 3 6W.
composed of vertices, faces, half-edges. half-edges are directed edges that form a cyclical ring around a particular face. they store:
- the face to its left, assuming “forward” is the direction of the next half-edge in the ring
- the next half-edge in the ring
- the symmetric half-edge on the edge adjacent to this half-edge’s face. these two should point in opposite directions, so combining them creates a “full” edge.
- the vertex between this half-edge and the next half-edge.
faces are ordered in a counterclockwise fashion (w.r.t. half-edges), assuming we’re viewing the face such that surface normal is pointed directly toward us.
supports operations such as splitting edges, triangulation
some advantages
- fixed size of data structure elements. half-edges have 4 pointers only.
- data is separated
- geometry information is stored at vertices.
- attributes (e.g. color) stored in any other relevant component, not shared.
- topological information stored in half-edges.
- structure enforces proper topology.
- runtime: linear for local information, independent of overall mesh complexity.
skip redundant pointers
only need to store a single pointer for some attributes.
- a face stores a single pointer to any of the half-edges that loop around it.
- a vertex stores a single pointer to an arbitrary half-edge that points to it (meaning direction of half-edge matters). for example, a cube would have three half-edges pointing to a vertex. it should arbitrarily pick any of the three.
edge boundary (end of polygon)
if an edge lies at the boundary, we create “ghost” half-edges, but they have nullptr face pointers.
this is useful for finding the other vertex that bounds a half-edge. switch over to the other symmetrical half-edge, and traverse its pointer to its vertex.
traversing over each half edge
to traverse over each half edge, use a do-while loop so that we don’t get issues with skipping the last edge or not starting at all.
HalfEdge *curr = f->edge;
do {
curr->tag();
curr = curr->next;
} while (curr != f->edge);traversing over adjacent faces
traverse over all half-edges for current face. for each half-edge, traverse to symmetrical half-edge, and traverse its pointer to it face.
void tag_all_neighbor_faces(Face *f) {
HalfEdge *curr = f->edge;
do {
curr->sym->face->tag();
curr = curr->next;
} while (curr != f->edge);
}