Overview Schedule Resources Assignments


MATH 385: Computer Graphics

Reed College Mathematics Spring 2015



Instructor: Jim Fix.
Lecture Hours: 1pm-2pm MWF.
Lecture Classroom: Library 204.
Office hours: 2pm-4pm MWF, or by appointment.
Office: Library 314.

Full course for one semester. Introduction to computer image synthesis and mathematical modeling for computer graphics applications. Topics include coordinate systems, vector and affine spaces, 2-D and 3-D transformations, projection, modeling of curves and surfaces, 3-D rendering, animation, graphics hardware, and geometric algorithms and data structures. Prerequisite: Mathematics 121 and 211. Mathematics 331 recommended.


Schedule of Topics


Geometry I
. linear and affine spaces, homogeneous coordinates
. interpolation, barycentric coordinates
. meshes and surface representation, OBJ files
. surface data structures
. intro to OpenGL: points, lines, triangles, fans, and strips
. Samples: terrains, VBOs
Geometry II
. transformations & transformation matrices
. coordinate frames
. projection
. OpenGL: viewport transformation, transformation stack
. Samples: fib figure,
Rendering
. color representation
. shading models
. hidden surfaces, z-buffering
. OpenGL: view volume, anti-aliasing, shading, depth
. shaders for the Phong surface modeling
Geometry III
. keyframing and interpolation
. Bezier curves, de Casteljau evaluation, Bezier patches
. convolution, B-spline curves
. B-spline subdivision
. subdivision surfaces
Animation
. keyframing, animation principles
. physics: mass & springs, particle systems, boidz
. numeric integration
Hardware and Parallelism
. GPU and the graphics pipeline
. sources of parallelism in hardware
. GPGPU and parallel processing
. OpenCL
. parallel prefix and parallel sorting
Geometric Algorithms & Data Structures
. scan-line algorithms
. Voronoi diagrams
. (Delauney triangulation)
. (space-partitioning trees)



Texts

There are several good computer graphics textbooks that all roughly cover the same material. Foley & van Dam is the most lauded and its first edition was one of the first of its kind. This was recently updated but the two older versions are also worth looking at, especially to see in what ways graphics technology has, and hasn't, changed. Of the remaining, I found Peter Shirley's and Samuel Buss' to be the most focused on the mathematical fundamentals of the field. (I should note that Peter Shirley is an alum.) Several are nice in that they incorporate OpenGL, the graphics library that we'll rely on, in their treatment of the course material. One text is specifically on ray tracing and another only covers radiosity. Both were published when each rendering technique had just matured. Finally, Jim Blinn's series is a wonderful cross-cutting survey of several graphics ideas from one of the field's inventors.

The first four are in the bookstore. I'll put these and also the supplemental texts on reserve in the library. I'll also keep my personal copies of all these texts in Library 382 (unless of course I'm looking at them, myself, at the moment).

I've chosen to require two texts: Gortler and Shirley & Marschner. The first, Gortler, I'll rely heavily on in first month of preliminaries, namely, in a coordinate-free approach to specifying scene geometry, transformations of scene objects' geometry, and scene view transformations. The book is, at times, fairly cavalier in its approach to the remaining topics. Gortler is a remarkable researcher who gets the fact that most graphics work comes down to having skill (and confidence) in the mathematics that drives it, and that, for the most part, nothing else about graphics techniques needs to be set in stone. We'll then switch to the Shirley & Marschner text, as it does a better job of setting standard, well-known techniques down in stone.

Required:

Recommended:

Supplemental:
The best collection of materials on computer graphics, including the most up-to-date write-ups of techniques, can be found in the research paper proceedings of the annual SIGGRAPH conference. The 2014 conference is linked below through the ACM digital library. I highly recommend browsing through several recent years, and also ones from many years' past, to get a sense of what the computer graphics research community works on. The papers are generally very readable to anyone with a solid undergraduate math (and/or physics) background. We will look at papers and tutorials from this conference throughout the semester.

Programming

We will be writing Python v3 code that relies on the OpenGL and GLUT libraries, as provided by the PyOpenGL package. You are also welcome to write code in C (again, using OpenGL and GLUT) should you choose to do so. For the GPU portion of the course we will be writing OpenCL kernels, installable through the PyOpenCL package. Some of your coding might require NumPy and SciPy for numeric calculations. I recommend Sage for any symbolic calculations, should you choose to do them on the computer.

Useful Links

the Red OpenGL book on-line
OpenGL on-line documentation
GLSL documentation
PyOpenGL
PyOpenCL
Nate Robins' OpenGL tutorial programs
The ACM SIGGRAPH
papers from SIGGRAPH 2014
selected papers from SIGGRAPHs past
selected subdivision papers
DeRose (Pixar) on subdivision math
Pixar on OpenSubDiv
General Purpose GPU programming site
cloud dissertation with GPGPU
AMD's ISA doc for Evergreen
one of AMD's "Evergreen" family
other GPU documentation
OpenCL programming guide
PyOpenCL





Assignments

There will be seven programming assignments, roughly one every two weeks, on the topics listed above.

‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐

Homework 0

Get ready for the course by doing the following:
  1. Install Python version 3 on your system.
  2. Install numpy, scipy, pyopengl, and pyopencl.
For the above, once I had python3 on my Mac, I was just able to do the following:
pip3 install nose
pip3 install numpy
pip3 install scipy
pip3 install pyopengl
pip3 install pyopencl
With these, I am now able to run the code I've written for this course on my Mac.


‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐

Homework 1 solution

Part I. Using a version of my sample GL/GLUT python programs write programs that generate faceted models of the following:
> A triangular mesh that forms the surface of a cube.
> A triangular mesh that forms the surface of a cylinder.
> A triangular mesh that forms the surface of a sphere.
> A triangular mesh that forms the surface of a torus.
The last three will only approximate their figures. Write the code so that the mesh generated has different levels of smoothness. For the cube, split each face into two triangular halves.

Part II. Write a fifth program that reads wavefront OBJ files, essentially a list of vertex locations along with an index-based description of a "soup" of triangular facets, and displays them using GL/GLUT.

An alterative strategy is to build Part II first, then solve Part I by instead writing programs that output OBJ files.

BONUS: figure out a way to shade or light the faceted model to illustrate its geometry. See my 'withgeom' code for an example of how to do this.

BONUS: extend my rotation interface so that a keypress spins the object around the z-axis (the view direction).

BONUS: modify my rotation interface so that it instead uses the mouse.

Various samples and repositories of OBJ files:
> an MIT source
> the Stanford bunny
> an FSU source
> a Clemson source


‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐

Homework 2 pt 1 solution pts 2 and 3 solution

You are welcome to work with a partner (or partner(s)) for each part of this assignment, just let me know who they are.

Part I. (written, due: 2/9/2015) Using our point and vector operations, devise the expression for the intersection of a triangular facet with a ray, both living in 3-space. You can assume the ray is described by an endpoint R and a unit direction d along which the ray emanates. You can assume that the facet is described by three points Q1, Q2, and Q3. Describe the conditions for which the two objects intersect. If they do, then give an expression for the intersection point P as an affine combination of those three facet vertices.

Part II. (code, due 2/18/2015) Using your own .obj scene viewer, or modifying mine, change the code so that it represents the surface as a "winged half-edge data structure" like what is described in Chapter 12 of the Shirley and Marschner text. You'll want to devise classes for a vertex, a half-edge, and a face.

Include in your face class a method with_ray that returns the barycentric coordinates of the point that is at the intersection of a ray with that facet. It should return None if they don't intersect.

Part III. (code: due 2/20/2015) You can test your code for the surface data structure by performing "walks" on the surface. This will lead your code to traverse objects that constitute that structure. Here is an example of a walk that I'd like yout to implement. When the user of your .obj viewer clicks their mouse, determine which facet was selected. That is, shoot a ray along the view direction into the scene and determine which face would be hit by that ray. Having done that, walk along the facets, starting at that facet and crossing half-edges choosing neighboring facets according to some criterion. You could, for example, have the user drag a "slice direction" from that clicked point. That would define a slicing plane to "slice" a cross section of that object. In this case, I would like you to compute the slice by walking along the facets from the clicked facet, choosing a neighbor facet that is hit by the slicing plane.


‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐

Homework 3 shadow_solution

Part I. (due: 2/27/2015) Using OpenGL's MODELVIEW transformation stack operations, namely glRotate, glTranslate, glScale, glPushMatrix, and glPopMatrix, write an GLUT/GL program that produces an oriented Sierpinski figure. It can be 2D or 3D.

Part II. (written due: 3/2/2015; program due: 3/4/2015) Let L be the position of a point light source and let ( P, n ) designate a plane containing point P with surface normal n. Figure out the criteria for whether a point Q on an object would cast a shadow on that plane (based on its position and the position of the light, both relative to the plane). For each such point Q determine its shadow's projection point Q' on that plane.

Modify your object viewer (or mine) so that it displays a planar floor underneath the object. Render the object's shadow onto that floor according to the position of the light source illuminating the object. BONUS: it's possible to do this rendering in hardware. That is to say: you can draw the object using the standard Phong shaders to render the lit object, then you can reissue the object's facet descriptions through a diferent pair of shaders so as to produce the shadow.


‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐
Homework 4

Please see the write up.

‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐
Homework 5 (code due electronically on 4/1/15)

Modify your winged-edge based object viewer from homework 2 part ii so that it implements Loop subdivision surfaces. You may also use my winged-edge solution as a starting point. My source includes detailed description in the object viewer and winged-edge data structure Python source comments.

I've summarized the Loop subdivision coefficients in this note.


‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐
Homework 6

Write an N-body numeric simulation, preferably having bodies subject to Newton's laws of gravity, using RK4.

‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐
Homework 7

Using my example PyOpenCL code as a guide, write the PyOpenCL code to perform the Ladner and Fischer parallel prefix sum algorithm. Note that PyOpenCL is installed and working on the ETC machines, but not on the MathLab machines.
‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐
Homework 8

Indpendent project.

‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐

Overview Resources Schedule Assignments