Mesh
Introduction to Mesh and it's properties
Piecewise linear approximation with error

Mesh elements
- Face: Subset of a 3d plane
- Edge: Incident points of 2 or more faces
- Vertex: Incident points of 2 or more edges
Mesh Local Structure
- Element type: Triangle, Quad meshes, or polygon meshes. We always use triangles as they are always planar.
- Element shape: Isotropic, i.e. locally uniform in all directions, or anisotropic, i.e. non-uniform in all directions.
- Element density: Uniform or non-uniform. Non-uniform density is used to refine the mesh in regions of interest.
Note
For better illustrations, see lecture slides on google classroom. I might add some illustrations here in the future myself but for now, I will just leave it as it is.
Regularity of Mesh
- Irregular: any number of irregular vertices
- Semi-regular: small number of irregular vertices
- Highly regular: most vertices are regular
- Regular: all vertices are regular
Info
A Vertex is regular if it is incident to 6 edges. We generally use regular meshes as they are easier to work with.
Mesh Data Structures
Face Set
It is simply a list of faces. Each face is represented by a list of vertices.
Faces |
---|
Face |
---|
Vertex |
Vertex |
Vertex |

Indexed Face Set
This time we are using indices to represent the vertices. This is useful when we have a large number of vertices and faces. This reduces redundancy and makes the data structure more compact.
Face | |
---|---|
VertexRef | |
FaceRef | |
FaceData | data |
Vertex | |
---|---|
Point | |
FaceRef | data |
VertexData | data |
Vertices |
---|
Faces |
---|

Winged Edge
This is a more complex data structure. Each Vertex and Face have a reference to an edge along with some other data. Each edge has the following
- Vertex references (
being the source and being the target) - Face references (
and ) - Previous and Next edge references for the left and right face
- Edge data
Warning
Edges in a face always follow anti-clockwise order.
Vertex | |
---|---|
Point | position |
EdgeRef | edge |
VertexData | data |
Face | |
---|---|
EdgeRef | edge |
FaceData | data |
Edge | ||
---|---|---|
VertexRef | ||
FaceRef | ||
EdgeRef | ||
EdgeRef | ||
EdgeData | data |

One Ring Traversal in Winged Edge
- Start with a vertex
- Get one of its edges
- Add the other vertex of the edge to the one ring
- Switch to the opposite edge
- Set
curr_edge = ePrevR
- Till
curr_edge->v0
is not equal to the first vertex in ring, add it - Repeat for
ePrevR

Half Edge
Half edge is a more compact data structure. Each edge is split into two half edges. Each half edge has the following
- Vertex reference
- Face reference (always the one in anti-clockwise direction)
- Next half edge reference
- Previous half edge reference
- Twin half edge reference
- Half edge data
Vertex | |
---|---|
Point | position |
HalfEdgeRef | edge |
VertexData | data |
Face | |
---|---|
HalfEdgeRef | edge |
FaceData | data |
Edge | |
---|---|
VertexRef | vertex |
FaceRef | face |
HalfEdgeRef | prev |
HalfEdgeRef | next |
HalfEdgeRef | twin |
EdgeData | data |

One Ring Traversal in Half Edge
- Start with a vertex
- Go to one of its half edges
- Switch to reverse edge (twin)
- Go to the next half edge (original vertex)
- Repeat until you repeat the original edge

Boundary Traversal in Half Edge
- Start with a boundary edges
- Go to the next boundary edge
- Switch to the reverse edge (twin)
- Repeat until you reach the original edge

Directed Edge
Half edge modification for triangular meshes.
- Store all 3 half-edges of common face next to each other in memory.
- Let
be the index of the same face. Place it's th half-edge at index in the array. - Then
th half-edge belongs to th face = - Index of
th half-edge in the array = - No need to store face-to-edge and face-to-edge references.
Performance Comparison of Mesh Data Structures
One Ring, Two Ring, and k-Ring
- One Ring: All vertices connected to a vertex by an edge.
- Two Ring: Vertex connected to a vertex in the one ring.
- k-Ring: All vertices connected to a vertex by an edge or a vertex connected to a vertex in the k-1 ring.
Roughly speaking, the one ring is the immediate neighbors of a vertex, the two ring is the neighbors of the neighbors, and so on.
Data Structure | Space per Vertex | Mesh Topology | Rendering | One-Ring Traversal | Boundary Traversal |
---|---|---|---|---|---|
Face Set | 72 bytes | Static, fixed (3,4) | Fast | Slow | Slow |
Indexed Face Set | 36 bytes | Static, fixed (3,4) | Fast | Slow | Slow |
Winged Edge | 120 bytes | Any (2 manifolds) | Medium | Slow (case distinctions) | Slow |
Half Edge | 144 / 96 bytes | Any (2 manifolds) | Medium / Slow | Fast | Fast |
Directed Edge | 64 bytes | Regular Triangular / Quad Meshes (2 manifolds) | Medium/Slow | Medium | Medium |
Pros and Cons of Mesh Data Structures
Data Structure | Pros | Cons |
---|---|---|
Face Set | Static meshes; rendering | No explicit connectivity information; data redundancy |
Indexed Face Set | Simple and efficient storage; Static meshes; rendering | No explicit connectivity information; Not efficient for most algorithms |
Winged Edge | Arbitrary Polygonal Meshes | Massive case distinctions for one-ring traversal |
Half Edge | One-ring traversal; explicit representation of edges | Slow rendering |
Applications of Mesh Data Structures
Data Structure | Applications |
---|---|
Face Set | Stereolithography (3D printing) |
Indexed Face Set | Rendering |
Winged Edge | Rarely used |
Half Edge | Mesh refinement, decimation, smoothing |