← Back to all projects

LEARN COMPUTATIONAL GEOMETRY CAD KERNEL DEEP DIVE

Modern civilization is literally built on Computational Geometry. From the Boeing 787 to the microchips in your phone, every physical object begins its life as a set of mathematical definitions in a CAD kernel.

Learn Computational Geometry & CAD Kernel Engineering: From Zero to Kernel Master

Goal: To deeply understand the mathematical and algorithmic foundations of Computer-Aided Design (CAD). You will progress from simple 2D geometric predicates to building a B-Rep (Boundary Representation) engine capable of NURBS evaluation and robust Boolean mesh operations. By the end, you will understand not just how to draw shapes, but how to maintain the complex topological integrity required by industrial-grade engineering software.

Why Computational Geometry Matters

Modern civilization is literally built on Computational Geometry. From the Boeing 787 to the microchips in your phone, every physical object begins its life as a set of mathematical definitions in a CAD kernel.

Traditional “graphics” (like in games) care about what looks right. CAD kernels care about what is right. A gap of $10^{-7}$ millimeters in a mesh might not matter for a video game character, but it will cause a 3D printer or a CNC machine to fail catastrophically.

Understanding this field unlocks:

  • Aerospace & Automotive Engineering: Building the kernels that design wings and engines.
  • Robotics: Path planning and collision detection.
  • GIS (Geographic Information Systems): Analyzing spatial data at a planetary scale.
  • Architecture (BIM): Structural analysis and generative design.

Core Concept Analysis

1. The Geometry vs. Topology Split

The single most important concept in CAD is the separation of Geometry (the “where”) and Topology (the “how it’s connected”).

GEOMETRY (The Math)              TOPOLOGY (The Structure)
-------------------              ------------------------
Point (x, y, z)        <---->    Vertex
Equation of a Line     <---->    Edge
Equation of a Plane    <---->    Face
Spline Surface         <---->    Shell / Solid

2. B-Rep (Boundary Representation)

B-Rep represents a solid by its boundaries. A cube isn’t “a block of matter”; it’s a collection of six faces that happen to enclose a volume.

       [SOLID]
          |
       [SHELL]
          |
    +-----+-----+
    |     |     |
 [FACE] [FACE] [FACE] ...
    |     |
 [WIRE] [WIRE]
    |     |
 [EDGE] [EDGE]
    |
 [VERTEX]

3. NURBS (Non-Uniform Rational B-Splines)

NURBS are the “Gold Standard” for geometry. They can represent both simple shapes (circles, lines) and complex organic curves (car bodies) using the same underlying math.

The NURBS ingredients:

  • Control Points: The “magnets” that pull the curve.
  • Weights: How strong each magnet is.
  • Knot Vector: The “timing” of the curve—where one segment ends and another begins.
  • Degree: The smoothness (linear, quadratic, cubic).

4. Robustness and Floating Point

In geometry, if (x == y) is a trap. Because of floating-point errors, three lines that should meet at a point often form a tiny, microscopic triangle. You will learn to use Epsilon-based math and Exact Geometric Predicates to prevent your kernel from “leaking” or crashing.

Concept Summary Table

Concept Cluster What You Need to Internalize
Robust Predicates Floating point is imprecise. You must use exact arithmetic or symbolic logic for “Is point on line?”
Manifold Topology Every edge must be shared by exactly two faces. “Watertight” is the goal.
Half-Edge Data Structure A clever way to store meshes that allows O(1) navigation from a face to its neighbors.
Parametric Evaluation Transforming a u, v coordinate into a x, y, z 3D point on a surface.
Boolean Operations The logic of Union, Intersection, and Difference—the “CSG” of CAD.

Deep Dive Reading by Concept

Foundational Geometry

Concept Book & Chapter
Geometric Predicates “Computational Geometry” by de Berg et al. — Ch. 1: “Introduction”
Convex Hulls “Computational Geometry” by de Berg et al. — Ch. 2: “Convex Hulls”
Data Structures “Polygon Mesh Processing” by Botsch et al. — Ch. 2: “Data Structures”

Parametric Modeling (NURBS)

Concept Book & Chapter
BĂ©zier Curves “The NURBS Book” by Piegl & Tiller — Ch. 1: “Curve and Surface Basics”
B-Splines “The NURBS Book” by Piegl & Tiller — Ch. 2: “B-Spline Basis Functions”
NURBS Geometry “The NURBS Book” by Piegl & Tiller — Ch. 4: “Fundamental Geometric Algorithms”

CAD Operations

Concept Book & Chapter
Boolean Ops “Geometric and Solid Modeling” by Christoph Hoffmann — Ch. 3: “Boolean Operations”
B-Rep Internals “Geometric Modeling” by Mortenson — Ch. 12: “Solid Modeling”

Essential Reading Order

  1. The Math foundation (Week 1):
    • de Berg Ch 1 (Robustness)
    • Mortenson Ch 1 (Point/Line math)
  2. The Mesh foundation (Week 2):
    • Botsch Ch 2 (Half-Edge structure)
  3. The Spline foundation (Week 3):
    • Piegl Ch 1-2 (B-Splines)

Project List

Projects are ordered from fundamental understanding to advanced implementations.

Project 1: The Robust Predicate Engine (The Foundation)

  • File: PROJECT_01_PREDICATES.md
  • Main Programming Language: C
  • Alternative Programming Languages: C++, Rust, Zig
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 1. The “Resume Gold”
  • Difficulty: Level 3: Advanced
  • Knowledge Area: Numerical Analysis / Logic
  • Software or Tool: Custom math library
  • Main Book: “Computational Geometry” by de Berg

What you’ll build: A library of “Geometric Predicates”—functions like orient2d (is a point left or right of a line?) and incircle (is a point inside a circle?) that work correctly even when the points are nearly collinear.

Why it teaches robustness: This project forces you to confront the “Floating Point Lie.” You’ll learn why a + b == c is dangerous and how to use techniques like “Adaptive Precision Arithmetic” or “Epsilons” to ensure topological decisions don’t change based on zoom level.

Core challenges you’ll face:

  • Determinant computation → maps to spatial orientation logic
  • Precision loss → maps to numerical stability
  • Collinearity handling → maps to degeneracy management

Key Concepts:

  • Orient2D Predicate: de Berg, Ch 1.1
  • Floating Point Arithmetic: “What Every Computer Scientist Should Know About Floating-Point Arithmetic” - David Goldberg
  • Exact Arithmetic: Jonathan Shewchuk’s “Robust Adaptive Floating-Point Geometric Predicates”

Difficulty: Advanced Time estimate: 1 week Prerequisites: Understanding of matrices and floating-point bit representation.

Real World Outcome

You will have a library that can tell you with 100% certainty if three points form a clockwise or counter-clockwise turn, even if they are only $10^{-15}$ units apart.

Example Output:

$ ./test_predicates
Point A: (0.1, 0.1)
Point B: (0.2, 0.2)
Point C: (0.10000000000000001, 0.10000000000000002)

Standard double precision result: COLLINEAR (Incorrect!)
Robust predicate result: COUNTER_CLOCKWISE (Correct!)

The Core Question You’re Answering

“In a world of imprecise numbers, how can we make binary topological decisions (Inside vs Outside) that never fail?”

Before you write any code, sit with this: if a point is “almost” on a line, and your math says “left”, but a later calculation says “right”, your mesh will have a hole. In CAD, “almost” is the enemy of “solid.”

Concepts You Must Understand First

Stop and research these before coding:

  1. Determinants
    • How does a $2\times2$ determinant represent the area of a parallelogram?
    • How does the sign of that area relate to orientation?
    • Book Reference: “Computational Geometry” Ch 1.1
  2. Machine Epsilon
    • What is the smallest difference between two floating point numbers?
    • Why does error accumulate during multiplication?

Project 2: The Sutherland-Hodgman Polygon Clipper

  • File: PROJECT_02_CLIPPER.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust, Go, Python
  • Coolness Level: Level 2: Practical but Forgettable
  • Business Potential: 2. The “Micro-SaaS / Pro Tool”
  • Difficulty: Level 2: Intermediate
  • Knowledge Area: 2D Topology
  • Software or Tool: SDL2 or Canvas for visualization
  • Main Book: “Geometric Modeling” by Mortenson

What you’ll build: An algorithm that takes two polygons (Subject and Clip) and outputs a new polygon representing their intersection.

Why it teaches topology: You’ll learn how to “walk” along edges, detect intersections, and stitch new vertices together to maintain a closed loop. This is the 2D precursor to 3D Boolean operations.

Core challenges you’ll face:

  • Intersection point calculation → maps to linear algebra basics
  • Re-entrant polygons → maps to handling concave shapes
  • Maintaining vertex order → maps to winding number logic

Key Concepts:

  • Sutherland-Hodgman Algorithm: Mortenson, Ch 9
  • Winding Order: “Real-Time Rendering” - Akenine-Möller

Difficulty: Intermediate Time estimate: Weekend Prerequisites: Project 1 (Predicates), basic vector math.

Real World Outcome

A visual tool where you can drag two polygons over each other and see the resulting intersection polygon update in real-time.

Example Output:

[User drags Square over Triangle]
Subject: (0,0), (10,0), (10,10), (0,10)
Clip: (5,5), (15,5), (10,15)
Result: (5,5), (10,5), (10,10), (7.5, 10) 
# Note how the result has 4 vertices, different from both inputs!

The Core Question You’re Answering

“How do we generate new geometry where none existed before, simply by the interaction of two existing shapes?”

Project 3: The Half-Edge Mesh Library

  • File: PROJECT_03_HALFEDGE.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust, Swift
  • Coolness Level: Level 3: Genuinely Clever
  • Business Potential: 1. The “Resume Gold”
  • Difficulty: Level 3: Advanced
  • Knowledge Area: Data Structures / Mesh Processing
  • Software or Tool: OpenGL or Dear ImGui
  • Main Book: “Polygon Mesh Processing” by Botsch et al.

What you’ll build: A 3D mesh data structure that doesn’t just store triangles (the “face-vertex” approach), but stores “Half-Edges” that point to their twins, next edges, and faces.

Why it teaches mesh topology: In a simple STL file, triangles don’t know who their neighbors are. In a CAD kernel, if you move a vertex, you need to know every face that shares it. The Half-Edge structure is the industry standard for answering “Who is next to me?” in $O(1)$ time.

Core challenges you’ll face:

  • Pointer management (The “Twin” link) → maps to non-manifold detection
  • Iterating around a vertex → maps to circulator patterns
  • Mesh validation → maps to Euler Characteristic (V - E + F = 2)

Key Concepts:

  • Half-Edge Data Structure: Botsch, Ch 2.2
  • Manifoldness: “Geometric and Solid Modeling” - Hoffmann, Ch 2
  • Euler Characteristic: Mortenson, Ch 12

Difficulty: Advanced Time estimate: 2 weeks Prerequisites: Proficiency with pointers/references, Project 1.

Real World Outcome

A program where you can load an OBJ file and, by clicking a face, highlight all neighboring faces, or highlight the “boundary” edges (holes in the mesh).

Example Output:

$ ./mesh_explorer cube.obj
Mesh Loaded: 8 Vertices, 12 Faces, 24 Half-Edges
Query: Select Face 0
Neighbors: Face 1, Face 2, Face 4, Face 5
Topology check: Euler Characteristic = 2 (Valid Closed Manifold)

The Core Question You’re Answering

“How can we navigate a 3D surface like a map, knowing exactly how to step from one face to another without searching?”

Implementation Hints (Project 3)

The Half-Edge structure relies on the “Twin” property. For every edge between Vertex A and B, there are actually two directed half-edges: one going $A \to B$ and one going $B \to A$.

Key Structs:

  • Vertex: stores position and one outgoing half-edge.
  • Face: stores one bounding half-edge.
  • HalfEdge: stores target_vertex, face, next_edge, and twin_edge.

Mental Model: Think of a half-edge as a person walking along the inside boundary of a face. Their next is the next person in front of them. Their twin is the person walking in the opposite direction on the other side of the “wall” (edge).

Project 4: NURBS Curve Evaluator (The Smooth Math)

  • File: PROJECT_04_NURBS_CURVE.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust, Python (with NumPy)
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 1. The “Resume Gold”
  • Difficulty: Level 4: Expert
  • Knowledge Area: Parametric Geometry
  • Software or Tool: Matplotlib or custom GL renderer
  • Main Book: “The NURBS Book” by Piegl & Tiller

What you’ll build: A mathematical engine that takes control points, weights, a knot vector, and a degree, and produces the $x, y, z$ coordinates of a NURBS curve.

Why it teaches CAD math: This is the heart of CAD geometry. You’ll learn the De Boor algorithm, which is the stable way to evaluate B-splines. You’ll understand how “weights” allow a NURBS curve to represent a perfect circle (which standard BĂ©zier curves cannot do).

Core challenges you’ll face:

  • B-Spline Basis Functions → maps to understanding local control
  • De Boor’s Algorithm → maps to stable numerical evaluation
  • Rational curves (The “R” in NURBS) → maps to projective geometry basics

Key Concepts:

  • Knot Vectors (Uniform vs Non-uniform): Piegl, Ch 2.1
  • De Boor Algorithm: Piegl, Ch 2.3
  • Conic Sections as NURBS: Piegl, Ch 7

Difficulty: Expert Time estimate: 1-2 weeks Prerequisites: Project 1, understanding of recursive functions.

Real World Outcome

You’ll have a mathematical plotter that can generate complex, infinitely smooth curves. Unlike a simple polyline, this curve can represent a perfect circle or an ellipse with mathematical precision.

Example Output:

$ ./nurbs_eval --degree 2 --knots 0,0,0,1,1,1 --weights 1,0.707,1 --pts (1,0),(1,1),(0,1)
Evaluating NURBS curve at u=0.5...
Resulting Point: (0.707106, 0.707106)
# Success: The point at 45 degrees on a unit circle is exactly 1/sqrt(2).

The Core Question You’re Answering

“How can we describe an infinitely smooth curve using only a few discrete points and some ‘weight’ magnets?”

Most developers think curves are just lots of tiny lines. In CAD, a curve is a continuous function. This project answers how to bridge discrete control points to continuous mathematical truth.

Concepts You Must Understand First

Stop and research these before coding:

  1. B-Spline Basis Functions
    • What does it mean for a curve to have “Local Support”?
    • How does a knot vector determine where a curve starts and ends?
    • Book Reference: “The NURBS Book” Ch 2.
  2. Rational vs. Non-Rational
    • Why can’t a standard polynomial (BĂ©zier) represent a circle?
    • How does adding a $w$ (weight) to $(x, y, z)$ solve this?

Questions to Guide Your Design

  1. Evaluation Loop
    • Will you implement De Boor’s algorithm recursively or iteratively?
    • How will you handle the case where a knot appears multiple times (knot multiplicity)?
  2. Projective Geometry
    • How do you perform the “perspective divide” to turn 4D homogeneous coordinates $(xw, yw, zw, w)$ back into 3D points?

Thinking Exercise

The Weight of a Point

Given 3 control points in a line: $A(0,0), B(5,0), C(10,0)$. If you increase the weight of $B$ from 1 to 100, what happens to the curve? Does it stay a line? Does it move towards $B$? Trace the midpoint $u=0.5$ as $w_B \to \infty$.

The Interview Questions They’ll Ask

  1. “What is the difference between a BĂ©zier curve and a B-Spline?”
  2. “How do weights in NURBS allow for the representation of conic sections?”
  3. “Explain the purpose of the knot vector in a B-Spline.”
  4. “What is De Boor’s algorithm and why is it preferred over evaluating the basis functions directly?”
  5. “What happens to a B-Spline curve when you move a single control point?”

Hints in Layers

Hint 1: Start with BĂ©zier Implement a simple De Casteljau algorithm for BĂ©zier curves first. It’s a subset of B-splines where the knots are just $[0,0,0,1,1,1]$.

Hint 2: The Basis Write a function N(i, k, u) that calculates the basis function for knot index i, degree k, at parameter u. Watch out for division by zero!

Hint 3: De Boor NURBS evaluation is essentially a series of linear interpolations. If you look at De Boor’s algorithm as a triangle of calculations, it becomes much clearer.

Hint 4: Verification Use a unit circle. If your NURBS can’t hit $(0.707, 0.707)$ with three points, your weights or basis logic is off.

Books That Will Help

Topic Book Chapter
B-Spline Basis “The NURBS Book” Ch. 2
De Boor’s Algo “The NURBS Book” Ch. 2.3
Conics “The NURBS Book” Ch. 7

Project 5: NURBS Surface Generator

  • File: PROJECT_05_NURBS_SURFACE.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust, Julia
  • Coolness Level: Level 5: Pure Magic (Super Cool)
  • Business Potential: 1. The “Resume Gold”
  • Difficulty: Level 4: Expert
  • Knowledge Area: Surface Modeling
  • Software or Tool: OpenGL / Vulkan
  • Main Book: “The NURBS Book” by Piegl & Tiller

What you’ll build: An extension of Project 4 that evaluates a grid of control points to create a 3D surface $S(u, v)$.

Why it teaches surface theory: You’ll learn how a 2D parameter space $(u, v)$ maps to a 3D object. This is how car bodies and plane wings are defined. You’ll also implement surface normal calculation, which is vital for rendering and offset operations.

Core challenges you’ll face:

  • Tensor product evaluation → maps to scaling from curves to surfaces
  • Partial derivatives → maps to calculating surface normals
  • Tessellation → maps to turning a smooth math surface into renderable triangles

Key Concepts:

  • NURBS Surfaces: Piegl, Ch 3
  • Surface Normals: Piegl, Ch 3.4
  • Tessellation Strategies: “Polygon Mesh Processing” - Botsch, Ch 6

Difficulty: Expert Time estimate: 2 weeks Prerequisites: Project 3 (Half-Edge), Project 4 (NURBS Curve).

Real World Outcome

You will have a 3D visualization of a smooth, “organic” surface. By moving control points in a grid, you can see the surface stretch and bend like a sheet of rubber, while your code calculates the exact 3D normal for every point to ensure correct lighting.

Example Output:

$ ./nurbs_surface --rows 4 --cols 4
Evaluating Surface S(u, v)...
Tessellating into 800 triangles...
Center Point (0.5, 0.5): (12.4, 5.2, -1.0)
Normal at (0.5, 0.5): (0.12, 0.98, -0.05)
# Note: The normal is normalized (length = 1.0).

The Core Question You’re Answering

“How do we define a 3D volume’s ‘skin’ mathematically so that we can calculate the exact slope and curvature at any microscopic location?”

In 3D printing or CNC, “close enough” isn’t enough. You need the normal vector to calculate the tool path. This project teaches you how to derive that vector from the surface equations.

Concepts You Must Understand First

Stop and research these before coding:

  1. Tensor Products
    • How do you combine two 1D curve functions (in $u$ and $v$) into a 2D surface function?
    • Book Reference: “The NURBS Book” Ch 3.
  2. Partial Derivatives
    • How do you calculate $\partial S / \partial u$ and $\partial S / \partial v$?
    • Why is the cross product of these two vectors the surface normal?

Questions to Guide Your Design

  1. Efficiency
    • Evaluating a surface is $O(N^2)$. How can you cache $u$-evaluations while iterating over $v$?
  2. Tessellation
    • How many triangles do you need to “faithfully” represent the curve?
    • Should you use a fixed grid or adaptive subdivision?

Thinking Exercise

The Flatness Test

If you have a $4\times4$ grid of control points, and all of them have the same $Z$ coordinate, what is the normal vector at every point $(u, v)$? Now, if you move just one corner control point up in $Z$, which areas of the surface change their normals? How “far” does the change spread? (Think about B-Spline local support).

The Interview Questions They’ll Ask

  1. “Explain the concept of a tensor product surface.”
  2. “How do you calculate the surface normal of a NURBS surface at a specific $(u, v)$?”
  3. “What is the difference between global and local control in surface modeling?”
  4. “Why is $(u, v)$ parameterization important for texture mapping or tool-pathing?”
  5. “What happens if $\partial S / \partial u$ and $\partial S / \partial v$ are parallel?”

Hints in Layers

Hint 1: The Grid Think of the control points as a 2D array. First, evaluate all rows as curves to get “temporary” control points. Then, evaluate those temporary points as a curve in the other direction.

Hint 2: Normals The normal is $\mathbf{n} = \frac{\partial S}{\partial u} \times \frac{\partial S}{\partial v}$. You need to calculate the derivative of the basis functions.

Hint 3: Surface Triangulation To see your surface, you must turn it into triangles. Iterate $u$ from 0 to 1 and $v$ from 0 to 1 in steps (e.g., 0.1) and create two triangles for every square in the grid.

Books That Will Help

Topic Book Chapter
Surface Eval “The NURBS Book” Ch. 3
Derivatives “The NURBS Book” Ch. 3.4
Mesh Tiling “Polygon Mesh Processing” Ch. 6

Project 6: The B-Rep Topology Engine

  • File: PROJECT_06_BREP_ENGINE.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 4. The “Open Core” Infrastructure
  • Difficulty: Level 5: Master
  • Knowledge Area: Solid Modeling
  • Software or Tool: Custom CAD framework
  • Main Book: “Geometric Modeling” by Mortenson

What you’ll build: A system that links the Topology (Faces, Edges, Vertices) to the Geometry (NURBS Surfaces, NURBS Curves, Points).

Why it teaches the “CAD Secret”: This is where you realize an “Edge” is not just a line; it’s a topological entity that points to a 3D curve and knows which two faces it separates. This project is the bridge between “pure math” and “functional CAD.”

Core challenges you’ll face:

  • The Trimmed Surface Problem → maps to defining boundaries on a surface
  • Orientation Consistency → maps to ensuring normals point ‘out’ of a solid
  • Adjacency Mapping → maps to linking 3D edges to 2D parameter space (p-curves)

Key Concepts:

  • Manifold B-Rep: Hoffmann, Ch 2
  • Trimmed Surfaces: “The NURBS Book”, Ch 11
  • Face-Loop-Edge Structure: Mortenson, Ch 12.3

Difficulty: Master Time estimate: 3-4 weeks Prerequisites: Project 3, Project 5.

Real World Outcome

You will have a data structure that can represent a “Solid” (like a cube with a cylindrical hole). You can query the solid to find which faces share an edge, or verify that the entire object is “watertight” and has a valid volume.

Example Output:

$ ./brep_explorer my_part.brep
Solid: "EngineBlock_v1"
Status: CLOSED_MANIFOLD
Face 1: NURBS Surface (3x3), Outer Loop (4 Edges), Inner Loop (1 Hole)
Edge 12: NURBS Curve (Degree 3), Left Face: 1, Right Face: 5
Result: Topology is Valid.

The Core Question You’re Answering

“How do we distinguish between an infinite mathematical surface and a finite physical ‘part’ with boundaries?”

In math, a plane goes on forever. In CAD, a “Face” is a plane trimmed by edges. This project answers how to maintain the links between those infinite surfaces and their finite boundaries.

Concepts You Must Understand First

Stop and research these before coding:

  1. Trimming Curves (P-curves)
    • Why do we need to store the boundary in 2D $(u, v)$ space and 3D $(x, y, z)$ space?
    • Book Reference: “The NURBS Book” Ch 11.
  2. Manifold Connectivity
    • What is the Euler-PoincarĂ© formula?
    • How many edges must meet at a vertex for a manifold solid?

Questions to Guide Your Design

  1. Hierarchy
    • How will you handle “Holes” in a face? (Hint: Use Loops).
  2. Tolerances
    • If a 3D edge curve doesn’t perfectly match the $(u, v)$ boundary of a surface, how do you handle the gap?

Thinking Exercise

The Donut Hole

Imagine a “Solid” that is a cube with a hole through the middle.

  • How many Faces does it have?
  • How many Loops?
  • Is there an “Inner Shell” or just an “Inner Loop” on several faces? Try to sketch the graph of connections (Shell $\to$ Face $\to$ Loop $\to$ Edge).

The Interview Questions They’ll Ask

  1. “What is B-Rep and how does it differ from CSG?”
  2. “Explain the relationship between a Face, a Loop, and an Edge.”
  3. “What is a ‘Trimmed Surface’?”
  4. “Why is it important for a CAD model to be ‘Manifold’?”
  5. “How do you represent a hole in a 3D face?”

Hints in Layers

Hint 1: The Structure Build the classes: Vertex, Edge, Loop, Face, Shell, Solid. Don’t add geometry yet, just pointers/IDs to check connectivity.

Hint 2: Orientation Every edge in a Loop must follow a winding order (e.g., CCW). The “Twin” half-edge on the adjacent face must go in the opposite direction.

Hint 3: Mapping Add a pointer from Face to NURBS_Surface and from Edge to NURBS_Curve. Now you have a true B-Rep.

Books That Will Help

Topic Book Chapter
B-Rep Structure “Geometric Modeling” Ch. 12
Solid Modeling “Geometric and Solid Modeling” Ch. 2
Trimming “The NURBS Book” Ch. 11

Project 7: Simple CSG Engine (Constructive Solid Geometry)

  • File: PROJECT_07_CSG_ENGINE.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust, JavaScript (for web-based CSG)
  • Coolness Level: Level 3: Genuinely Clever
  • Business Potential: 2. The “Micro-SaaS / Pro Tool”
  • Difficulty: Level 3: Advanced
  • Knowledge Area: Boolean Logic / Spatial Partitioning
  • Software or Tool: BSP Trees
  • Main Book: “Geometric and Solid Modeling” by Christoph Hoffmann

What you’ll build: A system that performs Union, Intersection, and Difference on primitive shapes (Spheres, Cubes) using Binary Space Partitioning (BSP) trees.

Why it teaches Booleans: CSG is the “conceptual” way Booleans work. By using BSP trees, you learn how to classify points as “Inside”, “Outside”, or “On Boundary.” This is much easier than B-Rep Booleans and provides the mental model for the harder 3D mesh operations.

Core challenges you’ll face:

  • Plane-splitting → maps to dividing geometry along boundaries
  • Recursive tree traversal → maps to efficient spatial queries
  • Robustness in slicing → maps to handling “coplanar” polygons

Key Concepts:

  • BSP Trees for Booleans: Hoffmann, Ch 3.3
  • Point-in-Solid classification: “Real-Time Rendering”, Ch 16

Difficulty: Advanced Time estimate: 1-2 weeks Prerequisites: Project 1, basic tree data structures.

Real World Outcome

A program that can take two primitive meshes (cube, sphere) and compute the logical combination. You’ll see the exact moment the sphere “cuts” into the cube, creating a clean subtracted volume.

Example Output:

$ ./csg_tool --op SUBTRACT --base cube.stl --tool sphere.stl
Building BSP Tree A (Cube)...
Building BSP Tree B (Sphere)...
Intersecting Trees...
Pruning Nodes...
Reconstructing Mesh...
Output: result.stl (342 Triangles)

The Core Question You’re Answering

“How can we use spatial partitioning (Inside vs Outside) to resolve the interaction of two separate volumes?”

Concepts You Must Understand First

  1. Binary Space Partitioning (BSP)
    • How does a plane divide space into two half-spaces?
    • How do you classify a triangle as “In”, “Out”, or “Spanning” a plane?
  2. Set Operations
    • Union: Inside A OR Inside B.
    • Intersection: Inside A AND Inside B.
    • Difference: Inside A AND NOT Inside B.

The Interview Questions They’ll Ask

  1. “What is a BSP tree and how is it used in CSG?”
  2. “How do you handle the case where a polygon is coplanar with a splitting plane?”
  3. “Compare the performance of BSP-based Booleans vs Mesh-based Booleans.”

Project 8: Mesh Boolean Evaluator (The Hard Part)

  • File: PROJECT_08_MESH_BOOLEANS.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust
  • Coolness Level: Level 5: Pure Magic (Super Cool)
  • Business Potential: 5. The “Industry Disruptor”
  • Difficulty: Level 5: Master
  • Knowledge Area: Mesh Processing
  • Software or Tool: Custom Mesh Kernel
  • Main Book: “Polygon Mesh Processing” by Botsch et al.

What you’ll build: A robust Boolean algorithm that works directly on Half-Edge meshes by finding intersection curves, splitting faces, and re-stitching topology.

Why it teaches CAD internals: This is the “Everest” of geometry. You’ll deal with exact intersection points and topological re-routing.

Core challenges you’ll face:

  • Intersection Curves → maps to finding the ‘seam’ between two objects
  • Local Remeshing → maps to inserting new vertices into an existing mesh

Prerequisites: Project 1, Project 3, Project 7.

Real World Outcome

A tool that can merge two separate 3D scans or CAD parts into a single, topologically correct manifold mesh without holes or self-intersections.

Example Output:

$ ./boolean_engine UNION car_body.obj wheel.obj
Intersecting... Found 1 continuous loop.
Splitting 42 triangles on Mesh A.
Splitting 38 triangles on Mesh B.
Stitching boundaries...
Result: 1 Solid, 0 Boundary Edges (Watertight!)

The Core Question You’re Answering

“How do we surgically ‘stitch’ two discrete objects together so that the computer treats them as one continuous skin?”

Thinking Exercise

The Coplanar Nightmare

Imagine two cubes that are placed exactly on top of each other. Their top faces share the exact same mathematical plane. If you perform a UNION, what happens to those two faces? Do they disappear? Do they merge? How does your algorithm know they are the “same”? (Think back to Project 1: Predicates).

The Interview Questions They’ll Ask

  1. “Walk me through the steps of a mesh-based Boolean operation.”
  2. “How do you handle ‘grazing’ intersections (where a vertex just touches a face)?”
  3. “Why are exact predicates necessary for mesh Booleans?”

Project 9: Constrained Sketch Solver (Newton-Raphson)

  • File: PROJECT_09_SKETCH_SOLVER.md
  • Main Programming Language: Python or C++
  • Alternative Programming Languages: Rust, Julia
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 2. The “Micro-SaaS / Pro Tool”
  • Difficulty: Level 4: Expert
  • Knowledge Area: Constraint Satisfaction / Optimization
  • Software or Tool: Numerical Solver
  • Main Book: “Geometric Constraint Solving” by Joan-Arinyo

What you’ll build: A 2D sketcher where you define constraints (length, perpendicularity) and the solver finds the vertex positions.

Prerequisites: Calculus (Derivatives), Linear Algebra (Matrices).

Real World Outcome

A GUI where you can draw a triangle, lock one side to 100px, and lock one angle to 90 degrees. As you drag the third vertex, the rest of the triangle snaps to maintain those constraints.

Example Output:

$ ./solver --solve
Degrees of Freedom (DoF): 6 (3 points * 2 coords)
Constraints: 5
Remaining DoF: 1
Convergence: Success in 4 iterations.
Residual: 1e-12

The Interview Questions They’ll Ask

  1. “What is a Constraint Solver in the context of CAD?”
  2. “Explain how Newton-Raphson can solve a system of geometric equations.”
  3. “What happens to a solver when a sketch is ‘over-constrained’?”
  4. “How do you calculate the Jacobian matrix for a ‘Distance’ constraint?”

Books That Will Help

Topic Book Chapter
Constraint Logic “Geometric Constraint Solving” Ch. 2
Numerical Methods “Numerical Recipes in C” Ch. 9

Project 10: Feature-Based Modeler (Extrude/Revolve)

  • File: PROJECT_10_FEATURE_MODELER.md
  • Main Programming Language: C++
  • Alternative Programming Languages: Rust
  • Coolness Level: Level 5: Pure Magic (Super Cool)
  • Business Potential: 5. The “Industry Disruptor”
  • Difficulty: Level 4: Expert
  • Knowledge Area: Procedural Geometry
  • Software or Tool: Custom CAD Engine
  • Main Book: “Geometric Modeling” by Mortenson

What you’ll build: A tool that takes a 2D sketch (from Project 9) and “Extrudes” it along a vector or “Revolves” it around an axis to create a 3D B-Rep solid.

Why it teaches procedural modeling: This is the final step in the CAD pipeline. You’ll learn how to “sweep” a 2D wire through space to generate new faces and edges, and how to maintain topological connectivity during the sweep.

Core challenges you’ll face:

  • Sweeping topology → maps to generating faces from edges and vertices
  • Handling self-intersection → maps to detecting when a sweep ‘crashes’ into itself
  • Cap generation → maps to creating the start and end faces of the solid

Key Concepts:

  • Generalized Sweeps: Mortenson, Ch 8
  • Rotational Sweeps: “The NURBS Book”, Ch 11.4

Difficulty: Expert Time estimate: 2 weeks Prerequisites: Project 6 (B-Rep), Project 9 (Sketcher).

Real World Outcome

A CAD system where you can draw a profile, extrude it into a solid, and then pick one of the new 3D faces to start a new sketch. This is the “Parametric History” workflow used by professional engineers.

Example Output:

$ ./cad_kernel --cmd "EXTRUDE profile_1 50mm"
Scanning Profile... 4 Edges found.
Generating 4 Sidewall Faces.
Generating Top/Bottom Cap Faces.
Constructing B-Rep Solid...
Result: Solid created with 6 Faces, 12 Edges, 8 Vertices.

The Core Question You’re Answering

“How do we ‘sweep’ a 2D mathematical concept through space to generate a 3D physical object?”

The Interview Questions They’ll Ask

  1. “What is a sweep operation in B-Rep?”
  2. “How do you generate the sidewall faces during an extrusion?”
  3. “How do you maintain topological connectivity between the original sketch and the newly created 3D faces?”

Project 11: STEP File Data Explorer (Interoperability)

  • File: PROJECT_11_STEP_EXPLORER.md
  • Main Programming Language: Python or C++
  • Alternative Programming Languages: Rust
  • Coolness Level: Level 1: Pure Corporate Snoozefest
  • Business Potential: 3. The “Service & Support” Model
  • Difficulty: Level 2: Intermediate
  • Knowledge Area: Data Engineering / Standards
  • Software or Tool: ISO 10303 (STEP) Parser
  • Main Book: “Geometric and Solid Modeling” by Hoffmann

What you’ll build: A parser for the .step format, extracting the B-Rep hierarchy and displaying it as a tree.

Prerequisites: Project 6 (B-Rep structure understanding).

Real World Outcome

You can open a file created in SolidWorks or AutoCAD and see exactly how it’s defined: the NURBS surfaces, the control points, and the topological loops. You’ll realize that everyone in the world uses the same B-Rep “language.”

Example Output:

$ ./step_parse gear.step
#10 = PRODUCT('Gear', 'Gear', ...)
#20 = CLOSED_SHELL('', (#30, #40, #50, ...))
#30 = ADVANCED_FACE('', (#31), #32, .T.)
#31 = FACE_BOUND('', #33, .T.)
...
[Tree View]
Solid
 └── Shell
      ├── Face 1 (Plane)
      ├── Face 2 (Cylindrical Surface)
      └── ...

The Core Question You’re Answering

“How does the world agree on how to describe a shape so that a file made in one program works in another?”

The Interview Questions They’ll Ask

  1. “What is the STEP format (ISO 10303)?”
  2. “What is the difference between an ‘Advanced Face’ and a ‘Simple Face’ in STEP?”
  3. “Why is ‘Data Exchange’ one of the hardest problems in CAD?”

Final Overall Project: “Proto-CAD”

What you’ll build: A minimal, functional CAD kernel and viewer.

  • Backend: A B-Rep engine (Project 6) with Booleans (Project 8).
  • Frontend: A constrained 2D sketcher (Project 9).
  • Tooling: An Extrude/Revolve feature set (Project 10) and STEP export.

Why it matters: This ties every concept together. You move from a 2D idea (Sketch) to a 3D math definition (NURBS) to a physical entity (B-Rep Solid) that can be exported and used in the real world.

Project Comparison Table

Project Difficulty Time Depth of Understanding Fun Factor
1. Predicates Level 3 1w High (Robustness) Low
3. Half-Edge Level 3 2w High (Data Structures) Medium
4. NURBS Curve Level 4 2w Extreme (Math) High
6. B-Rep Engine Level 5 4w Extreme (Architecture) Medium
8. Mesh Booleans Level 5 4w+ Extreme (Logic/Ops) High
9. Sketch Solver Level 4 2w High (Optimization) High

Recommendation

If you are a Math wizard: Start with Project 4 (NURBS). It will feel intuitive and rewarding. If you are a Systems geek: Start with Project 3 (Half-Edge). It’s all about efficient data movement. If you want the “Quick Win”: Start with Project 2 (Clipper). It’s visual and satisfying to complete in a weekend.

Summary

This learning path covers Computational Geometry and CAD Kernel Engineering through 11 hands-on projects.

# Project Name Main Language Difficulty Time Estimate
1 Robust Predicate Engine C Level 3 1 week
2 Sutherland-Hodgman Clipper C++ Level 2 Weekend
3 Half-Edge Mesh Library C++ Level 3 2 weeks
4 NURBS Curve Evaluator C++ Level 4 2 weeks
5 NURBS Surface Generator C++ Level 4 2 weeks
6 B-Rep Topology Engine C++ Level 5 4 weeks
7 Simple CSG Engine C++ Level 3 2 weeks
8 Mesh Boolean Evaluator C++ Level 5 1 month+
9 Constrained Sketch Solver Python Level 4 3 weeks
10 Feature Modeler C++ Level 4 2 weeks
11 STEP File Data Explorer C++ Level 2 1 week

For beginners: Projects #1, #2, #3, #11 For intermediate: Projects #1, #3, #4, #7, #9 For advanced: Projects #4, #5, #6, #8, #10

Expected Outcomes

After completing these projects, you will:

  • Understand exactly how floating point errors destroy geometric logic and how to fix them.
  • Be able to implement the De Boor algorithm for stable NURBS evaluation.
  • Understand the complex topological “handshake” between faces, edges, and vertices in a B-Rep.
  • Know how to formulate geometric constraints as mathematical optimization problems.
  • Have built a functional “Proto-CAD” system from first principles.

You’ll have built 11 working projects that demonstrate deep understanding of the CAD world from the bits of a coordinate to the complexity of a Boolean intersection.