Course Overview
This course emphasizes CAD theory and computational methods rather than software tools. The instruction does NOT teach how to use a CAD package but teaches how to build a CAD package. Students learn the underlying algorithms and mathematical foundations used in professional design software.
Course Philosophy
The course focuses on four main areas:
- Basic Geometry: 3D point/line/plane representation and calculations
- Mesh-based Modeling: STL, VRML file formats and mesh operations
- Curve and Surface Modeling: Parametric curves including Hermite, Bezier, and B-Spline
- Solid Modeling: B-Rep, CSG, and Voxel structures
Detailed Syllabus
Part I: Foundations (Weeks 1-4)
Week 1: Introduction and Basic Concepts
- Course overview and motivation
- Geometric primitives and representations
- Floating-point arithmetic issues
- Robustness and degeneracy handling
Week 2: Convex Hulls
- Graham scan algorithm
- Divide-and-conquer approaches
- 3D convex hulls and gift wrapping
- Applications in collision detection
Week 3: Line Segment Intersections
- Sweep line algorithm
- Bentley-Ottmann algorithm
- Applications in CAD systems
- Handling special cases and degeneracies
Week 4: Polygon Algorithms
- Point-in-polygon testing
- Polygon triangulation
- Convex partitioning
- Applications in mesh generation
Part II: Curves and Surfaces (Weeks 5-8)
Week 5: Parametric Curves
- Bezier curves: mathematical foundation
- B-spline curves and knot vectors
- NURBS (Non-uniform rational B-splines)
- Curve fitting and approximation
Week 6: Surface Representations
- Tensor product surfaces
- Triangular patches
- Subdivision surfaces
- Level-of-detail representations
Week 7: Surface-Surface Intersections
- Marching algorithms
- Subdivision-based methods
- Robustness issues
- Applications in Boolean operations
Week 8: Mesh Processing
- Mesh data structures (half-edge, winged-edge)
- Mesh simplification algorithms
- Surface reconstruction from point clouds
- Quality metrics and mesh optimization
Part III: Spatial Data Structures (Weeks 9-10)
Week 9: Range Trees and KD-Trees
- 1D and multi-dimensional range searching
- KD-tree construction and queries
- Applications in nearest neighbor search
- Performance analysis
Week 10: Spatial Hashing and Octrees
- Grid-based spatial subdivision
- Octree construction and traversal
- Applications in collision detection
- Adaptive spatial structures
Part IV: Advanced Topics (Weeks 11-12)
Week 11: Boolean Operations
- Regularized set operations
- Boundary representation methods
- Robust implementation strategies
- Applications in solid modeling
Week 12: Voronoi Diagrams and Applications
- Incremental construction
- Fortune’s sweep line algorithm
- Applications in mesh generation
- Medial axis computation
Programming Assignments
Students implement key algorithms in C++ or Python:
- 2D Convex Hull (Week 2)
- Line Segment Intersection (Week 4)
- Bezier Curve Evaluation (Week 6)
- KD-Tree Implementation (Week 9)
- Final Project (Weeks 11-12)
Final Project Options
Students choose from several options:
- Research Project: Implement and evaluate a recent algorithm from literature
- Application Project: Apply geometric algorithms to solve an industrial problem
- Comparison Study: Benchmark different approaches to a geometric problem
- Extension Project: Extend an existing algorithm with new capabilities
Assessment
| Component | Weight | Description |
|---|---|---|
| Programming Assignments | 50% | Five coding projects |
| Midterm Exam | 20% | In-class theoretical exam |
| Final Project | 25% | Substantial implementation project |
| Class Participation | 5% | Discussion and presentation |
Computational Resources
- Programming Environment: Students may use C++, Python, or MATLAB
- Graphics Libraries: OpenGL, VTK, or similar for visualization
- Development Tools: Git for version control, CMake for building
- Computing Cluster: Access to high-performance computing resources
Prerequisites Details
Students should have solid background in:
- Data Structures: Trees, heaps, hash tables
- Algorithm Analysis: Big-O notation, complexity analysis
- Linear Algebra: Vector operations, matrix computations
- Calculus: Derivatives, partial derivatives, optimization
Office Hours and Support
- Instructor Office Hours: Wednesdays 1:00-2:30 PM
- TA Office Hours: Mondays and Fridays 3:00-4:00 PM
- Discussion Forum: Active Canvas discussion for Q&A
- Code Reviews: Optional code review sessions before major deadlines