X

Halfedge Data Structure

Contents

Brief Description

The most basic way of storing scene information is normally using a shared list of vertices. Lists of faces are then added, each face containing pointers to the vertices it uses out of the shared list. While this is a straight forward way of dealing with the scene data, consider a scenario where you are interested in finding adjacent faces or vertices. Finding this sort of information will in the worst case involve searching through the entire list of vertices, the entire list of faces, or both.

The halfedge data structure allows adjacency information to be found in near constant time, making it especially useful for mesh simplification, subdivision surfaces, meshing for radiosity, and other applications where frequent access is needed to different types of adjacency information.

The Data Structure

Central to the idea of the half-edge structure is that each edge in a mesh can infact be thought of as two half-edges, and each of these half-edges can only be connected to a single face.

Note: The half-edge structure does generally not support non-manifold geometry

A single standard edge
Enlarge
A single standard edge
Edge split into two half-edges
Enlarge
Edge split into two half-edges
Half-edge pointers
Enlarge
Half-edge pointers

Implementation

External Links





The Society

The CGSociety is the most respected and accessible global organization for creative digital artists. The CGS supports artists at every level by offering a range of services to connect, inform, educate and promote digital artists worldwide

Contact | Privacy | Advertising | About CGS