Project 3: The Half-Edge Mesh Library

Build a half-edge data structure that captures mesh topology and adjacency.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Main Language C++
Alternative Languages Rust, C, Python
Knowledge Area Mesh topology
Tools Mesh viewer or OBJ exporter
Main Book “Polygon Mesh Processing” by Botsch et al.

What you’ll build: A half-edge mesh library that supports traversal, adjacency queries, and basic editing.

Why it teaches computational geometry: CAD geometry is meaningless without topology. Half-edge makes connectivity explicit.

Core challenges you’ll face:

  • Designing stable references between half-edges, vertices, and faces
  • Handling boundaries and non-manifold edges
  • Implementing consistent traversal operations

Real World Outcome

You will load or construct a mesh and query its adjacency. You can iterate around a face or find all faces incident to a vertex.

Example Output:

$ ./mesh_info cube.obj
Vertices: 8
Faces: 12
Half-edges: 36
Boundary loops: 0

Verification steps:

  • Traverse a face and confirm edge ordering
  • Identify boundary edges correctly

The Core Question You’re Answering

“How do I represent both the shape and the connectivity of a mesh so that editing is reliable?”

Topology is what keeps geometry consistent during modeling.

Concepts You Must Understand First

Stop and research these before coding:

  1. Half-edge structure
    • Why is each edge represented twice?
    • Book Reference: “Polygon Mesh Processing” by Botsch et al., Ch. 2
  2. Manifold vs non-manifold
    • What does it mean for a mesh to be manifold?
    • Book Reference: “Geometric Modeling” by Michael E. Mortenson, Ch. 6
  3. Traversal patterns
    • How do you walk around a vertex or face?
    • Book Reference: “Polygon Mesh Processing” by Botsch et al., Ch. 2

Questions to Guide Your Design

  1. Data layout
    • Will you store indices or direct pointers?
    • How will you handle deletion and reindexing?
  2. Boundary handling
    • How do you represent boundary loops?
    • How do you detect non-manifold edges?

Thinking Exercise

Edge Connectivity

Sketch a triangle mesh with two adjacent triangles. Label half-edges and show which ones are twins.

Questions while working:

  • How many half-edges exist per triangle?
  • Which half-edges belong to the boundary?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Why use a half-edge data structure?”
  2. “How do you traverse all faces around a vertex?”
  3. “What is a non-manifold edge and why does it matter?”
  4. “How do you detect boundary loops?”
  5. “What are the tradeoffs vs a winged-edge structure?”

Hints in Layers

Hint 1: Starting Point Implement the minimal fields: next, twin, vertex, face.

Hint 2: Next Level Start with a simple mesh like a quad or cube.

Hint 3: Technical Details Write traversal helpers and unit tests for each.

Hint 4: Tools/Debugging Export traversal results to verify winding and adjacency visually.

Books That Will Help

Topic Book Chapter
Half-edge basics “Polygon Mesh Processing” by Botsch et al. Ch. 2
Mesh topology “Geometric Modeling” by Michael E. Mortenson Ch. 6
Traversal algorithms “Polygon Mesh Processing” by Botsch et al. Ch. 2

Implementation Hints

  • Keep constructors simple; build meshes in small steps.
  • Always validate twin relationships after edits.
  • Provide a sanity-check routine that detects broken links.

Learning Milestones

  1. First milestone: You can build and traverse a simple mesh.
  2. Second milestone: You can detect boundaries and non-manifold edges.
  3. Final milestone: You can confidently use topology for modeling tasks.