Fundamentals of Spatial Computing
MAT 594CM S2009
Angus Forbes & Wesley Smith, Instructors




This course provides a foundation for computing in multidimensional spaces, investigating the synthetic and generative potentials of elementary geometric constructs. Subjects covered will include vector and matrix math, space partitioning, collision detection, and kinematics. We will focus both on mathematical foundations and practical computational techniques for creating real-time 3D graphics via OpenGL.

Students will produce a number of investigations into the topics covered, culminating in a final programming project. No prerequisites are required, although some basic knowledge of programming is assumed. The course will consist of one lecture class and one lab class per week.


Lab Sessions
Lab sessions will be an opportunity to synthesize the lectures and get your hands dirty with the various concepts and algorithmic techniques. All lab work will be done in OpenGL on the platform of your choice. Suggested platforms are GLUT-Muro, OpenFrameworks, LuaAV, and Processing-JOGL.

In addition, lab sessions will be used to teach advanced software design techniques for real-time multimedia from a holistic perspective. In orther words, we will be working not just on the coding itself, but also on the toolsets that support effective coding practices and workflow. Students will be required to manage their code with a source code manager (SCM). The MAT servers are currently equipped with Subversion (SVN), which is the recommended SCM, see Introduction to Subversion. If you're on Windows, the recommended SVN client is Tortoise Subversion.

Week 1: Transformations and Graphics
Topics: Introduction to OpenGL, vectors, matrices, homogeneous coordinates, affine and perspective transformations.

Links: [OpenGL Red Book (into to OpenGL)] [Avoiding Pitfalls in OpenGL] [OpenGL Exposition and Tutorials] [Lecture 1 Slides]
Lab: [OpenGL Shading Language] [NeHe GLSL Tutorial] [OpenGL Extension Wrangler] [Muro GLSL Backend]
Code: [ofShader Example] [modded ofxShader] [Muro-GLUT Shader Example]
Week 2: Dynamics
Topics: Implicit/explicit Euler, Runge-Kutta, Verlet integration, physical simulation, particle systems.

Links: [Dynamics Equations] [OpenGL Cheat Sheet] [Advanced Character Physics] [Andrew Witkin's Particle System Slides] [Course Notes for Week 2]
Code: [Muro Shader with Vector3 and Camera] [Processing code for numerical methods and 1D Spring Demo] [Basic Java/OpenGL template] [Example Processing code for loading GLSL shaders]
Week 3: Curves and Interpolation
Topics: Parametric curves, Bezier curves, b-splines, NURBS, animation over curves, easing, parametric surfaces, Catmull-Clark subdivision surfaces, implicit surfaces.

Links: [Red book - "Evaluators & NURBS"] [Course Notes for Week 3] [Metaball Math] ["Subdivision Surface Theory" - Brian Sharpe] ["Implementing Subdivision Surface Theory" - Brian Sharpe] ["Platonic Solids" - Michael Hansmeyer]
Code: [Basic openGL Bezier curve code - bezcurve.c] [Basic openGL NURBS code - surface.c]
Week 4: Computational Geometry
Topics: Computational complexity, convex hulls, Voronoi diagrams, Delaunay triangulations.

Links: ["Big O Notation" - Wikipedia] ["Voronoi Diagrams and A Day at the Beach" - David Austin] ["Voronoi Fractals" - W:BLUT] ["Voronoi Morphologies" - Andrew Kudless] ["Yearbook Photos" - Golan Levin]

Code: [QHull library for convex hull, voronoi, and delaunay algorithms]
Project 1
Cast Shadow, Melissa Carrasco
Origami Particles, Ryan McGee
Flocking, Pehr Hovey
B-spline Hell, Pablo Colapinto
Drawing Rope, Javier Villegas
iPhone Metaballs, Charlie Roberts
Tangletree, Karl Yerkes
Goo3D, Greg Shear
Transformation Based Spatial Forms, Syed Reza Ali
Week 5: Rotations and Orientation
Topics: Rotation matrices, Euler angles, axis-angle, quaternions, rotation interpolation.

Links: [Animating rotation with quaternion curves] [Quaternions and SLERP] [Rotation Representations and Performance Issues] [Geometric Algebra] [Gaigen 2: a Geometric Algebra Implementation Generator]
Lab: ["Display Lists" - Red book] [Nehe Vertex Array & VBO lesson] ["Using VBOs" - Nvidia white paper] [Dynamic VBO example - Song Ho Ahn]
Code: [Quaternion Survival Kit] [GA Sandbox]
Week 6: Partitioning Space and Collisions
Topics: Binary Space Partitioning, Octrees, Bounding Box Approximations, Separating Axis Theorem, GJK

Links: [BSP Tree FAQ] ["Advanced Collision Detection Techniques" - Nick Bobic] [GAMMA Collision Detection research page] [Separating Axis Theorem applets] [Minkowski Difference applet] ["A fast procedure for computing the distance between complex objects in three-dimensional space" - Gilbert, Johnson, Keerthi] ["Implementing GJK" - Casey Muratori] [GJK code - OUCL]
Modeling Curling Effects, Melissa Carrasco
Musical Applications of Complex Geometries, Ryan McGee
Recursive Processes, Pehr Hovey
Motors, Pablo Colapinto
Fitting of Planar Objects, Javier Villegas
Stereoscopic Vision and Rendering, Charlie Roberts
Oren-Nayar Diffuse Lighting, Greg Shear
Constructing Bezier Curves on the Surface of a Sphere, Syed Reza Ali
Real-time 3D Fluid Dynamics, Graham Wakefield
Week 7: 3D Delaunay/Voronoi
Topics: 3D Delaunay triangulations and 3D Voronoi diagrams
Week 8: Surfaces and Topology
Topics: Subdivision surfaces, topological properties and representation
Week 9: Open Topic
Topics: TBD
Week 10: Lab sessions
Work on final project. Project-specific discussions
Project 2
Animating Shadows, Melissa Carrasco
Experiments in the Superformula and Hexany, Ryan McGee
Cubic Playgrounds, Pehr Hovey
Energy Cube, Pablo Colapinto
Object-Oriented Portraits, Javier Villegas
Objective 3D, Charlie Roberts
lsys, Karl Yerkes
3D Modeling of Archeological Ceramics, Greg Shear
Light Storm, Syed Reza Ali
Makeshift, Graham Wakefield


Generative Processes:
The Self-Made Tapestry: Pattern Formation in Nature
Pamphlet Architecture 27: Tooling

Applied C++: Practical Techniques for Building Better Software
Modern C++ Design: Generic Programming and Design Patterns
C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond

Beyond Geometry: Classic Papers from Riemann to Einstein
The Curves of Life
Algebraic Topology
Curves and Surfaces for CAGD: A Practical Guide

Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace and Virtual Reality
Visualizing Quaternions
Rotations, Quaternions, and Double Groups

Geometric Algebra:
Geometric Algebra for Computer Science (Revised Edition): An Object-Oriented Approach to Geometry
Geometric Algebra for Computer Graphics
Geometric Algebra for Physicists

Advanced Lighting and Materials with Shaders
Real-Time Rendering