Fundamentals of Spatial Computing
MAT 594CM S2010

Angus Forbes, Instructor

Tu/Th 10am-12pm in Room 2003, Elings Hall


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 interactive, real-time 3D graphics via OpenGL and GLSL.

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.

Please subscribe to the MAT 594CM Spring 2010 class forum. Announcements and assignments will posted there, along with links to articles, code, and other resources.

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 Processing-JOGL, OpenFrameworks, GLUT-Muro, LuaAV, or JOGL/Netbeans.

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) and git. For subversion, see Introduction to Subversion. If you're on Windows, you can use Tortoise Subversion. For git, see

Week 1: Introduction to OpenGL; The Rendering Pipeline
Topics: Introduction to OpenGL, vectors, matrices, homogeneous coordinates, affine and perspective transformations.

Links: [OpenGL Red Book (intro to OpenGL)] [Avoiding Pitfalls in OpenGL] [OpenGL Exposition and Tutorials] [OpenGL Reference Pages] [Homogeneous Coordinates]
Slides: [Week 1, Day 1 Slides] [Week 1, Day 2 Slides]
Processing Demos: [Vertex Transformation] [Lighting Demo] [Animation Demo] [Texture Demo]
Assignment due 04/01/10: Set up an OpenGL environment of your choice on your laptop and make sure you can run the basic tutorials from the Nehe OpenGL tutorial website.
Week 2: OpenGL Basics
Topics: Animation, easing functions, cameras, textures, lighting, materials.
Processing Demos: [OpenGL / 6DOF Camera / Simple Animation]
Links: [Easing Generator] [Red Book - "Lighting and Materials"] [Lighting Tutorial] [Red Book - "Texture Mapping"] [GameDev Texture Mapping Introduction] [Nehe Texture lesson]
Slides: [Week 2 Slides]
Assignment due 04/20/10: Problem Set 1
Week 3: Numerical Methods; Physics Simulations; Vertex Rendering
Topics: Implicit/explicit Euler, Runge-Kutta, Verlet integration, Physical simulation, Particle systems, Vertex Arrays, Vertex Buffer Objects, Display Lists.
Processing Demos: [Numerical Methods / Spring Simulation] [Cloth Simulation] [Spring Graph]
JOGL code: [JOGL code for Display Lists, Vertex Arrays, VBOs]
Links: [Song Ho Ahn's OpenGL Tutorials] [Advanced Character Physics] [Andrew Witkin's Particle System Slides] [Dynamics Equations] ["Display Lists" - Red book] [Nehe Vertex Array & VBO lesson] ["Using VBOs" - Nvidia white paper]
Slides: [Week 3 Slides]
Week 4: Curves and Surfaces; Introduction to GLSL Shaders
Topics: Parametric curves, Bezier curves, Hermite curves, Catmull-Rom splines, b-splines, NURBS curves and surfaces, vertex shaders, fragment shaders.

Links: [Red book - "Evaluators & NURBS"] [Parametric Curves Tutorial] [Curves and Surfaces for CAGD demo applets] [OpenGL Shading Language reference and spec] [GLSL Quick Reference] [NeHe GLSL Tutorial] [Andres Colubri's GLGraphics Processing Library]
Code: [Basic openGL Bezier curve code - bezcurve.c] [Basic openGL NURBS code - surface.c] [Simple Processing shading loader / basic vertex & fragment shaders]
Slides: [Week 4, day 1 Slides] [Week 4, day 2 Slides]
Assignment due 05/04/10: Research Project
Week 5: GLSL Basics
Topics: GLSL syntax, vertex displacement, per-pixel lighting, multi-texturing.

Processing Demos: [Vertex Displacement] [Per-Vertex Lighting] [Per-Pixel Lighting] [Multi-texturing]
Real-Time GPU Demos: [Nvidia GPU demos] [ATI GPU demos] [Farbrausch demoscenes] [ demoscene awards] [ demoscenes] [ demoscenes]
Links: [OpenGL Orange Book GLSL examples] [Typhoon Labs GLSL Courses] [Swiftless GLSL Tutorials] [Phong shading] [Wikipedia: Demoscene]
Slides: [Week 5 Slides]
Guest: Jonathan Ventura of the UCSB Four Eyes Lab discusses recent research in augmented reality, multiple view geometry, and computer graphics.
Week 6: Research Presentations
Blueprint Rendering, Syed Reza Ali
Particle System with Collision Detection, YanYi Fan
Bump Mapping, David Adams
OpenCL, Ben Alun-Jones
Sketchy Drawings, Qian Liu
Homogeneous Transforms / OpenCV, Ritesh Lala
Conjugate Gradient Solutions and Sparse Matrix Classes, John Delaney
Metaballs and Particle Physics, Bryce Yoshimura

Guest: MAT student and Allosphere researcher Basak Alper presents highlights from the recent CHI 2010 conference.
Week 7: 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 and Delaunay Techniques" - Henrik Zimmer] ["Voronoi Fractals" - W:BLUT] ["Voronoi Morphologies" - Andrew Kudless] ["Yearbook Photos" - Golan Levin] [QHull library for convex hull, voronoi, and delaunay algorithms]
Guests: MAT student Greg Shear discusses and demonstrates his GPU implementation of the Oren-Nayar reflectance model. MAT student Charlie Roberts discusses stereographic rendering and his research in the Allosphere and demonstrates the Stereo library for Processing.
Week 8: 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]

Guest: Brie Finegold, UCSB researcher in Geometric Group Theory, discusses topics in topology.
Deadline: Projects for the End of the Year Show (May 24th-28th) are due this weekend! [schedule]
Week 9: Surfaces and Topology
Topics: Subdivision surfaces, topological properties and representation
["Sketches of Topology" - Kenneth Baker] ["Space Symmetry Structure" - Daniel Piker] [Metaball Math] ["Subdivision Surface Theory" - Brian Sharpe] ["Implementing Subdivision Surface Theory" - Brian Sharpe] ["Platonic Solids" - Michael Hansmeyer]
Guest: MAT student Pablo Colapinto discusses Geometric Algebra and demonstrates his implementation of a fast GA library.
Week 10: Final Projects
BioRhythm, Syed Reza Ali
Classical Ising, Bryce Yoshimura
BioRhythm & BioSuperFormula, YuanYi Fan
Re-Act, Ritesh Lala & Qian Liu
Fusilli, John Delaney
Springy Sketch, David Adams
Gesture, Ben Alun-Jones
References & Resources

Previous Course Pages:
MAT 594CM Spring 2009

Real-Time Rendering / Real-Time Rendering Resources
Advanced Lighting and Materials with Shaders

GPU Programming:
OpenGL Shading Language (The Orange Book) / Orange Book Resources
GPU Gems 1 (online)
GPU Gems 2 (online)
GPU Gems 3 (online)
D3D Book (online)
ShaderX 1-7, GPU Pro (some of these are online)
The CG Tutorial (online)

OpenGL & Game Programming:
OpenGL Programming Guide (The Red Book) / (old edition available online)
Interactive Computer Graphics: A Top Down Approach
Game Programming Gems 1-7, Best of

General Mathematics:
Mathematics for Computer Graphics (online, requires UCSB login)
Mathematics for 3D Game Programming and Computer Graphics

Beyond Geometry: Classic Papers from Riemann to Einstein
The Curves of Life
Algebraic Topology
Curves and Surfaces for CAGD: A Practical Guide
Geometry for Computer Graphics (online, requires UCSB login)
Computational Geometry in C / C and Java Resources
Computational Geometry: Algorithms and Applications
Paul Bourke's Geometry Pages

Physics & Simulations
Real-time Collision Detection
Physics for Game Programmers / Resources
Vector Analysis for Computer Graphics (online, requires UCSB login)

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: An Object-Oriented Approach to Geometry / Resources
Geometric Algebra: An Algebraic System for Computer Games and Animation (online, requires UCSB login)
Geometric Algebra for Physicists

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