Computer Graphics (CMU 15-462/662)

This page contains lecture slides and recommended additional readings for the Fall 2015 offering of 15-462/662.

(a bit of history on graphics + making a line drawing of a cube!)

(coverage testing as sampling a 2D signals, challenges of aliasing, performing point-in-triangle tests)

Further Reading:

- A Pixel is Not A Little Square, Alvy Ray Smith, 1995
- A Nice Video Illustration of Temporal Aliasing. by Valvano and Yerraballi
- The Fourier Transform and It's Applications (Ch. 5) by B. Osgood (this is an outstanding reference)
- Stanford CS348B's Notes on Sampling. by Pat Hanrahan (also see Chapter 7.1 in the Physically Based Rendering book)

(basic math of coordinate spaces and transforms)

Further Reading:

- Real Time Rendering -- Chapter 4. by T. Akenine Moller, E. Haines, N. Hoffman
- 3D Rotations (exerpt from Ch. 15 of Advanced Animation and Rendering Techniques. by A. Watt, M. Watt)

(understanding perspective projection, texture mapping using the mip-map)

Further Reading:

- Pyramidal Parametrics. by L. Williams (the original mipmapping paper from 1983!)

(occlusion via the depth buffer, alpha composition, the graphics pipeline and modern GPUs)

Further Reading:

- Image Compositing Fundamentals. by Alvy Ray Smith, 1995
- A Closer Look at GPUs. by K. Fatahalian and M. Houston, 2008
- Rise of the Graphics Processor. by D. Blythe, 2008
- The Compute Architecture of Intel Processor Graphics Intel Technical Report, 2015.
- NVIDIA GeForce GTX 980 Whitepaper. NVIDIA Technical Report, 2014

(implicit and explicit representations, geometric data structures)

(manifoldness, geometry of curves and surfaces, curvature, polygon soup, incidence matrices, halfedge data structure)

(incidence matrices, comparison of polygon mesh data structures, overview of digital geometry processing (DGP), edge flip/split/collapse, remeshing, Delaunay criterion, Loop subdivision, quadric error simplification, Delaunay edge flips, basic Laplacian smoothing, isotropic remeshing)

Further Reading:

- Surface Simplification using Quadric Error Metrics by Garland and Heckbert
- A Survey of Subdivision-Based Tools for Surface Modeling by Boier-Martin, Zorin, and Bernardini
- A Remeshing Approach to Multiresolution Modeling by Botsch and Kobbelt
- Polygon Mesh Processing by Botsch, Kobbelt, Pauly, Alliez, Lévy
- Subdivision Methods for Geometric Design by Warren and Weimer.
- Digital Geometry Processing with Discrete Exterior Calculus by Keenan Crane

(quadratic forms, minimizing a quadratic, quadric error simplification, distance queries, point-to-triangle, definition of a ray, ray-sphere intersection, ray-triangle intersection, triangle-triangle intersection)

(acceleration via bounding volume hierarchies and space partitioning structures, rasterization and ray casting as solutions to the same visibility query problem)

(radiometric quantities and units, photometry, radiometry integrals, how real cameras work)

(quadrature, sampling distributions, Monte Carlo integration, importance sampling)

(BRDF, the reflectance equation, transmission and refraction, types of materials)

(the rendering equation, the importance of indirect illumination, path tracing, splitting, Russian roulette)

(Monte Carlo integration, expected value, variance, continuous random variables, variance reduction, bias and consistency, path space formulation of light transport, importance sampling, bidirectional path tracing, Metropolis-Hastings algorithm, multiple importance sampling, sampling patterns, stratified sampling, low-discrepancy sampling, quasi Monte Carlo, Hammersley and Halton sequences, blue noise, Poisson disk sampling, Lloyd relaxation, alias table, photon mapping, finite element radiosity)

Further Reading:

- "Monte Carlo Methods for Light Transport Simulation" the Academy Award-winning PhD thesis by Eric Veach
- "Stratified Sampling of Spherical Triangles" by Jim Arvo
- "Computing the Discrepancy with Applications to Supersampling Patterns" by David Dobkin, David Eppstein, and Don P. Mitchell
- "Generating Antialiased Images at Low Sampling Densities" by Don P. Mitchell

(rasterization-based global illumination, packet-tracing, fast-BVH builds)

(history of (computer) animation, splines, natural splines, cubic Hermite/Bezier, B-splines, interpolation, keyframing, rigging, skeletal animation, inverse kinematics, blend shapes)

(physically-based animation, Newton's 2nd law of motion, generalized coordinates, ordinary differential equations (ODE), Lagrangian mechanics, Euler-Lagrange equations, pendulum/double pendulum, n-body systems, mass-spring systems, particle systems, flocking, crowds, particle-based fluids, granular materials, molecular dynamics, hair simulation, numerical integration, forward/backward/symplectic Euler, stability analysis, numerical differentiation, automatic differentiation, symbolic differentiation)

Further Reading:

- Physically Based Modeling: Principles and Practice (Differential Equation Basics) by Andrew Witkin and David Baraff.
- Physically Based Modeling: Principles and Practice (Particle System Dynamics) by Andrew Witkin.
- Geometric Numerical Integration by Ernst Hairer, Christian Lubich, and Gerhard Wanner.
- Structure and Interpretation of Classical Mechanics by Gerald Jay Sussman and Jack Wisdom.

(continuous vs. discrete optimization, standard form of an optimization problem, local vs. global minima, existence and uniqueness of solutions, convex optimization, descent methods, gradient descent, Newton descent, kinematic chains, inverse kinematics)

Further Reading:

- Convex Optimization. by Stephen Boyd and Lieven Vandenberghe

(PDEs in computer graphics, defintion of a PDE, order and linearity, model equations (elliptic/parabolic/hyperbolic), Laplace equation, heat equation, wave equation, numerical solution of PDEs, Lagrangian and Eulerian discretization, the Laplace operator, discrete Laplacian, Dirichlet and Neumann boundary conditions, Jacobi method)

Further Reading:

- Physics-Based Animation by Christopher Batty (list of learning resources and recent papers)
- Fluid Simulation for Computer Animation by Robert Bridson

(linear systems of equations, visualizing linear equations, linear systems in graphics, fundamental linear algebra problems, most important algorithms of the 20th century, NP-hardness of polynomial equations, vector spaces, polynomials, function spaces, numerical linear algebra, visualization of linear maps, matrix representation of linear maps, linear isomorphisms, rotations, reflections, uniform scaling, stretch rotations, shear, symmetric matrices, spectral theorem, determinant as volume scaling, uniqueness of solutions, definiteness, sparse vs. dense matrices, callback functions, direct vs. iterative solvers, linear algebra software)

Further Reading:

- Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III
- Matrix Computations by Gene Golub and Charles van Loan
- SuiteSparse/CHOLMOD by Tim Davis
- NumPy (community project)
- Eigen by Benoît Jacob and Gaël Guennebaud

(frequency decomposition, Fourier transform in computer graphics, modal simulation, sound synthesis, mesh filtering, mesh compression, Fourier analysis in rendering, motion amplification, light field photography, Laplacian eigenfunctions, spectral decomposition, L2 inner product, Fourier transform, spectral theorem, reconstruction, FFT, precomputed radiance transfer)

Further Reading:

- Fast Fourier Transforms by Jeff Erickon; well-written notes giving very different motivation for studying Fourier transform in computer science
- Spectral Geometry Processing with Manifold Harmonics by Vallet et al

(tristimulus nature of color perception, color matching experiments, XYZ primaries, luminance vs. brightness, color spaces, gamma correction, tone mapping)

Further Reading:

- Marc Levoy's Stanford CS178 interactive demos are super helpful understanding color theory. (see section on "Color")
- Recovering High Dynamic Range Radiance Maps from Photographs by Debevec et al.
- Gradient Domain High Dynamic Range Compression by Fattal et al. SIGGRAPH 2002
- Photographics Tone Reproduction for Digital Images by Reinhard et al. SIGGRAPH 2002.

(jpeg compression, image filtering via convolution, separable filters, data-dependent filtering, non-local means, filtering by example)

Further Reading:

- A Non-Local Algorithm for Image Denoising. A. Buades et al. CVPR 2005
- A Gentle Introduction to Bilateral Filtering and its Applications. S. Paris et al. SIGGRAPH 2008 Course Notes
- Sylvain Paris' Fast Bilateral Filter page
- Texture Synthesis by Non-parametric Sampling. A. Efros and T.K. Leung. ICCV 99
- PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. C. Barnes et al. SIGGRAPH 2009

(sensor to image basics, demosaicing, the light field, light field photography)

(descriptions of fluid motion, Navier-Stokes, material derivative, advection, upwinding, PIC/FLIP, semi-Lagrangian advection, numerical diffusion, numerical dissipation, mass conservation, constrained Lagrangian mechanics, constraint projection, Helmholtz-Hodge decomposition, viscosity)

Further Reading:

- Fluid Simulation for Computer Animation by Robert Bridson (popular book on practical implementation of fluid simulation)
- The Art of Fluid Animation by Jos Stam (fun visual introduction to fluids)
- Introduction to the Theory of Incompressible Inviscid Flows by Tom Hou (more rigorous derivation of fluid equations)
- A Mathematical Introduction to Fluid Mechanics by Alexandre Chorin and Jerrold Marsden (concise mathematical discussion of fluid mechanics)
- Level Set Methods and Dynamic Implicit Surfaces by Stanley Osher and Ron Fedkiw (one very effective approach to surface tracking; not covered in class)

(VR hardware, latency and resolution challenges, judder, acquiring VR datasets)

Further Reading:

- Michael Abrash's Valve Blog (Abrash is now head of research at Oculus VR, see all the technical VR posts in the right side bar)
- ifixit's Oculus DK2 Teardown