San José State University
Department of Computer Science
CS-116B: Computer Graphics Algorithms

Instructor

Robert Bruce

Prerequisites

CS 116A (with a grade of "C-" or better) or instructor consent

Course Description

In-depth discussion of algorithms and techniques used in computer graphics and their implementation. Topics include: animation, fractals, anti-aliasing, fill algorithms, visible surface algorithms, color and shading, ray tracing, radiosity and texture maps. Substantial programming required.

Learning Outcomes

Upon successful completion of this course, students will be able to:

  • Create a physics engine based on Newton's three laws of motion.
  • Apply vector kinematics to a particle system for soft body dynamics.
  • Apply vector mathematics to compute the surface normal for light reflection.
  • Apply the Mass Spring Model to simulate cloth.
  • Apply the Marching Squares algorithm to create two-dimensional meta-balls.

Required Texts/Readings

Physics for game developers (2nd Edition) by David M. Bourg and Bryan Bywalec.

Other Readings

Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior by Xavier Provot.

Advanced Character Physics by Thomas Jakobsen.

Real time physics class notes by Matthias Müller, Jos Stam, Doug James, and Nils Thürey.

Mass Spring Particle Systems by Stephen Spinks.

Grading

Grading will be based on a total accumulation of 100 possible points, distributed as follows:

Assignment Points
Programming assignment 1: Marching Squares 10
Programming assignment 2: Particle explosion simulation 10
Programming assignment 3: Rope simulation with gravity and collision detection 10
Programming assignment 4: Cloth simulation with gravity 15
Programming assignment 5: Cloth simulation with gravity, wind, and collision detection 25
Midterm Exam 15
Final Exam 15
TOTAL POINTS 100

Grading Scale

Percent range Grade
97% to 100% inclusive A+
93% to 96% inclusive A
90% to 92% inclusive A-
87% to 89% inclusive B+
83% to 86% inclusive B
80% to 82% inclusive B-
77% to 79% inclusive C+
73% to 76% inclusive C
70% to 72% inclusive C-
67% to 69% inclusive D+
63% to 66% inclusive D
60% to 62% inclusive D-
Below 60% F

Course Schedule

Week Topic Readings and Deadlines
1 Introduction: Course overview and objectives  
1 Marching cubes algorithm Read: Marching cubes: A high resolution 3D surface construction algorithm, pp. 163-169
2 Marching squares algorithm  
2 Building a Physics Engine Read: Physics for game developers, pp. 281-289
3 Vector operations Read: Physics for game developers, pp. 495-505
3 A review of classical mechanics in physics Read Physics for game developers, pp. 3-33
4 Kinematics Read: Physics for game developers, pp. 35-69
DUE: Programming Project 1
4 Force Read: Physics for game developers, pp. 71-83
5 Real-time simulations Read: Physics for game developers, pp. 143-159
5 Particles Read: Physics for game developers, pp. 161-187
6 Explosions Read: Physics for game developers, pp. 353-368
6 Connecting objects Read: Physics for game developers, pp. 255-279
7 Mass Spring Model Read: Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior, pp. 1-8
7 Runge-Kutta Integration Read: Advanced Character Physics, pp. 1-19
8 Verlet integration simulation DUE: Programming assignment 2
8 MIDTERM EXAM  
9 Newton-Raphson method  
9 Collision detection Read: Physics for game developers, pp. 205-225
10 Rigid body simulation  
10 Volumetric mesh creation using Delaunay tetrahedralization Read: Real Time Physics Class Notes, Section 3.6 (pp. 17-18)
DUE: Programming Project 3
11 Cloth simulation mistakes  
11 Position-based fluid simulations  
12 Image Morphing  
12 Rendering Smoke and Fire in Real-Time  
13 Perlin Noise DUE: Programming assignment 4
13 Breshenham's Algorithm  
14 Floyd–Steinberg dithering  
14 Quaternions and Spherical Linear Interpolation (SLERP) for animation.  
15 Final Exam Review  
15 FINAL EXAM DUE: Programming assignment 5