Project 9: Constrained Sketch Solver (Newton-Raphson)
Build a 2D sketch constraint solver that satisfies distances, angles, and tangency.
Project Overview
| Attribute | Value |
|---|---|
| Difficulty | Level 3: Advanced |
| Time Estimate | 2-3 weeks |
| Main Language | C++ |
| Alternative Languages | Python, Rust, C |
| Knowledge Area | Nonlinear constraint solving |
| Tools | Visualization or plotting tool |
| Main Book | “Geometric Constraint Solving” by Hoffmann, Lomonosov, and Sitharam |
What you’ll build: A sketch solver that adjusts points and lines to satisfy geometric constraints.
Why it teaches computational geometry: CAD sketching is a numerical constraint problem disguised as drawing.
Core challenges you’ll face:
- Formulating constraints as equations
- Solving nonlinear systems iteratively
- Handling under- and over-constrained sketches
Real World Outcome
You will define a sketch with constraints and watch the solver adjust geometry into a valid solution. The system should converge or report failure.
Example Output:
$ ./sketch_solver --input sketch.json
Constraints: 12
Unknowns: 10
Status: converged in 8 iterations
Verification steps:
- Visualize before/after geometry
- Check residual errors are near zero
The Core Question You’re Answering
“How does a CAD system keep your sketch consistent when you drag a point?”
Constraint solving is the engine behind parametric design.
Concepts You Must Understand First
Stop and research these before coding:
- Constraint formulation
- How do you express distance and angle constraints as equations?
- Book Reference: “Geometric Constraint Solving” by Hoffmann et al., Ch. 2
- Newton-Raphson method
- How does iterative solving converge to a solution?
- Book Reference: “Numerical Methods for Engineers” by Chapra & Canale, Ch. 6
- Constraint graph
- How do you detect under- or over-constrained systems?
- Book Reference: “Geometric Constraint Solving” by Hoffmann et al., Ch. 4
Questions to Guide Your Design
- Solver strategy
- Will you use Jacobians explicitly or numerical approximation?
- How will you detect divergence?
- User feedback
- How will you explain when a sketch is unsolvable?
- How will you show constraint violations?
Thinking Exercise
Distance Constraint
Write the equation for maintaining a fixed distance between two points (x1,y1) and (x2,y2). Then derive the partial derivatives with respect to each coordinate.
Questions while working:
- Why do you need derivatives for Newton-Raphson?
- What happens if the distance is zero?
The Interview Questions They’ll Ask
Prepare to answer these:
- “How do constraint solvers work in CAD?”
- “Why is Newton-Raphson useful for nonlinear constraints?”
- “What is an over-constrained sketch?”
- “How do you handle constraint conflicts?”
- “Why do solvers sometimes fail to converge?”
Hints in Layers
Hint 1: Starting Point Start with only distance constraints between points.
Hint 2: Next Level Introduce angle or perpendicular constraints after distances work.
Hint 3: Technical Details Compute residuals and stop when they fall below a threshold.
Hint 4: Tools/Debugging Visualize constraint errors as vectors to spot instability.
Books That Will Help
| Topic | Book | Chapter |
|---|---|---|
| Constraint modeling | “Geometric Constraint Solving” by Hoffmann et al. | Ch. 2 |
| Newton-Raphson | “Numerical Methods for Engineers” by Chapra & Canale | Ch. 6 |
| Constraint graphs | “Geometric Constraint Solving” by Hoffmann et al. | Ch. 4 |
Implementation Hints
- Start with small systems and add constraints gradually.
- Provide debug output for each iteration.
- Keep geometry units consistent to avoid scale issues.
Learning Milestones
- First milestone: You can solve simple distance constraints.
- Second milestone: You can handle angles and tangency.
- Final milestone: You can explain why constraints fail or converge.