Project 8: Mesh Boolean Evaluator (The Hard Part)

Build a boolean operation engine that computes union, intersection, and difference between triangle meshes.

Project Overview

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 3-4 weeks
Main Language C++
Alternative Languages Rust, C, Python
Knowledge Area Robust mesh intersections
Tools Mesh viewer, validation scripts
Main Book “Polygon Mesh Processing” by Botsch et al.

What you’ll build: A boolean evaluator that splits meshes at intersections and recombines them into a new solid.

Why it teaches computational geometry: Mesh booleans expose every numerical and topological weakness. If this works, your kernel is real.

Core challenges you’ll face:

  • Robust triangle-triangle intersection
  • Stitching new edges and faces correctly
  • Maintaining manifold topology

Real World Outcome

You will input two meshes (like two overlapping cubes) and output a new mesh representing the boolean result. The output will be watertight and valid.

Example Output:

$ ./mesh_boolean --op union --a box.obj --b cylinder.obj --output result.obj
Intersections: 128
Output faces: 1024
Validation: watertight

Verification steps:

  • Visualize the result and confirm geometry
  • Run mesh validation for non-manifold edges

The Core Question You’re Answering

“How do you actually compute booleans on real meshes without breaking topology?”

This is the problem that separates toy geometry engines from production CAD.

Concepts You Must Understand First

Stop and research these before coding:

  1. Triangle intersection
    • How do you compute robust triangle-triangle intersections?
    • Book Reference: “Real-Time Collision Detection” by Christer Ericson, Ch. 5
  2. Mesh topology repair
    • How do you stitch edges after splitting?
    • Book Reference: “Polygon Mesh Processing” by Botsch et al., Ch. 7
  3. Inside/outside classification
    • How do you classify faces after cutting?
    • Book Reference: “Computational Geometry: Algorithms and Applications” by de Berg et al., Ch. 3

Questions to Guide Your Design

  1. Intersection handling
    • How will you store new intersection vertices?
    • How will you prevent cracks from floating-point error?
  2. Topology rebuild
    • Will you rebuild the mesh from scratch or patch it in place?
    • How will you ensure consistent face orientation?

Thinking Exercise

Boolean Pipeline

List the steps needed to compute a mesh union from two intersecting solids.

Questions while working:

  • Where do most boolean failures happen?
  • How do you detect and fix non-manifold edges?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Why are mesh booleans difficult to implement?”
  2. “How do you handle triangle-triangle intersections?”
  3. “What causes non-manifold topology in boolean results?”
  4. “How do you classify which triangles to keep?”
  5. “How do you validate a boolean output?”

Hints in Layers

Hint 1: Starting Point Start with boolean operations on very simple meshes (two cubes).

Hint 2: Next Level Split faces where intersections occur and build new edges.

Hint 3: Technical Details Use robust predicates to classify inside/outside and avoid cracks.

Hint 4: Tools/Debugging Visualize intersection curves and validate manifold properties.

Books That Will Help

Topic Book Chapter
Triangle intersection “Real-Time Collision Detection” by Christer Ericson Ch. 5
Mesh repair “Polygon Mesh Processing” by Botsch et al. Ch. 7
Boolean classification “Computational Geometry: Algorithms and Applications” by de Berg et al. Ch. 3

Implementation Hints

  • Keep intersection logic separate from topology rebuilding.
  • Validate after each stage to catch broken meshes early.
  • Expect to iterate on robustness before it works reliably.

Learning Milestones

  1. First milestone: You can detect and split intersecting triangles.
  2. Second milestone: You can rebuild a watertight mesh.
  3. Final milestone: You can explain why booleans are fragile.