CMU 15-864: ADVANCED COMPUTER GRAPHICS (Doug L. James)


	15-864 Advanced Computer Graphics Spring 2004 Computer Science Department Carnegie Mellon University

INSTRUCTOR: Doug James (Asst. Prof CS & Robotics)
UNIVERSITY UNITS: 12
DATE: Spring 2004
LOCATION: WeH 4615A
TIME: TR 10:30--11:50 PM (HUB 1:30 TIME IS WRONG)

TA: Christopher Twigg (Office hours: Thursday 3-5pm, Wean 5336)

NOTE REGARDING LONG WAITLIST: Currently all non-PhD students are being wait-listed, so do not be alarmed if you are on a very long waitlist as there are approx. 35 slots in the class. Priority will be given to PhD and masters students, followed by undergraduate students in higher years. Please come to the first class (Tuesday, Jan 13, 2004) to learn more.

DESCRIPTION:
This course will be a hands-on class on advanced computer graphics. It will cover major aspects of digital image generation: geometric modeling, computer animation, and rendering. The goal of the course is to provide a strong foundation for computer graphics principles, and provide a hands-on introduction to recent advanced topics, e.g., subdivision surfaces, real-time global illumination, and physically based animation. The course should be appropriate for graduate students in all areas and for advanced undergraduates.

PREREQUISITES:
Prior exposure to computer graphics (e.g., 15-462 Introduction to computer graphics) or approval of instructor. Good programming skills, and knowledge of linear algebra, 3D calculus, and numerical computing will be helpful.

TEXT:
Various course notes and papers will be made available.

SIMILAR COURSES:
Princeton, Computer Science 526, Tom Funkhouser [link]
...

METHOD OF EVALUATION:
Grading will be based on a set of programming and written assignments and a class project.

TOPICS TO BE COVERED:

Light/object interaction
Geometric object representation; multiresolution modeling
Topics in computer animation and physically based modeling

Anti-aliasing
Texture and environment mapping
Ray tracing
Radiosity
Global illumination
Advanced real-time rendering

CLASS DATE	TOPICS	Material (Partly "CMU Only" access)
Tu Jan 13	Introduction	N/A
Th Jan 15	Mesh data structures Introduction to subdivision surfaces	Read "Adjacency Data Structures" web summary by Justin Legakis (esp. HalfEdge and QuadEdge) Subdivision course notes (SIGGRAPH 98-00) Foundations I: Basic Ideas
Jan 20 & 22	No classes (SIGGRAPH submission deadline Jan 21)	Continue reading subdivision course notes: Foundations I: Basic Ideas (finish reading) Foundations II: Subdivision for Surfaces (read--quiz on Tuesday)
Tu Jan 27	Quiz Subdivision Zoo Geri's Game	Subdivision course notes (SIGGRAPH 98-00)
Th Jan 29	Multiresolution analysis (MRA) Normal meshes	P. J. Burt and Ed H. Adelson, Laplacian Pyramid as a Compact Image Code, IEEE Trans. Commun. 31, 4 (1983), 532-540. Matthias Eck, Tony D. DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, Werner Stuetzle, Multiresolution Analysis of Arbitrary Meshes,Proceedings of SIGGRAPH 95. pp. 173-182, 1995. Peter Schröder, Wim Sweldens, Spherical Wavelets: Efficiently Representing Functions on the Sphere, Proceedings of SIGGRAPH 95. pp. 161-172, 1995. Denis Zorin, Peter Schröder, Wim Sweldens, Interactive Multiresolution Mesh Editing, Proceedings of SIGGRAPH 97. pp. 259-268, 1997. Igor Guskov, Wim Sweldens,Peter Schröder, Multiresolution Signal Processing for Meshes, Proceedings of SIGGRAPH 99. pp. 325-334, 1999. Igor Guskov, Kiril Vidimce, Wim Sweldens, Peter Schröder, Normal Meshes, Proceedings of ACM SIGGRAPH 2000. pp. 95-102, 2000. Aaron Lee, Henry Moreton, Hugues Hoppe, Displaced Subdivision Surfaces, Proceedings of ACM SIGGRAPH 2000. pp. 85-94, 2000.
	Assignment #1: Subdivision Surfaces	See assignment web page Due date: Friday February 13 before midnight; Late policy: Don't be late: 20% maximum grade deducted every additional day.
Tu Feb 3	Mesh Simplification	Class slides (pdf; cmu only) David P. Luebke, A Developer's Survey of Polygonal Simplication Algorithms, IEEE Computer Graphics & Applications, 21(3):24-35, May / June 2001. ISSN 0272-1716. Michael Garland and Paul S. Heckbert, Surface Simplification Using Quadric Error Metrics, Proceedings of SIGGRAPH 97, pp. 209-216, 1997. [SOFTWARE] Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick P. Brooks Jr. and William Wright, Simplification Envelopes, Proceedings of SIGGRAPH 96, pp. 119-128, 1996. [SOFTWARE] P. Cignoni, C. Rocchini and R. Scopigno, Metro: measuring error on simplified surfaces, Computer Graphics Forum, Blackwell Publishers, vol. 17(2), June 1998, pp 167-174. [SOFTWARE]
Th Feb 5	Progressive Meshes Mesh Smoothing and Fairing	Progressive meshes: Hugues Hoppe, Progressive Meshes, Proceedings of SIGGRAPH 96. pp. 99-108, 1996. (READ BEFORE CLASS) ... lots of PM refs <skip> ... Andrei Khodakovsky, Peter Schröder and Wim Sweldens, Progressive Geometry Compression, Proceedings of ACM SIGGRAPH 2000. pp. 271-278, 2000. Mesh smoothing and fairing: Gabriel Taubin,A Signal Processing Approach to Fair Surface Design, Proceedings of SIGGRAPH 95. pp. 351-358, 1995. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr, Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow, Proceedings of SIGGRAPH 99. pp. 317-324, 1999. [project page]
Tu Feb 10	Implicit Surfaces	Slides: Summary of implicit surfaces Jules Bloomenthal and Ken Shoemake, Convolution Surfaces, Computer Graphics (Proceedings of SIGGRAPH 91). 25(4), pp. 251-257, 1991. Jules Bloomenthal, Implicit Surfaces, to appear in the Encyclopedia of Computer Science and Technology (copyright Marcel Dekker, Inc., NY). Slides: Detailed discussion of selected topics Greg Turk and James O'Brien, Shape Transformation Using Variational Implicit Functions, Proceedings of SIGGRAPH 99. pp. 335-342, 1999. Sarah F. Frisken, Ronald N. Perry, Alyn P. Rockwood and Thouis R. Jones,Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics, Proceedings of ACM SIGGRAPH 2000. pp. 249-254, 2000. Leif P. Kobbelt, Mario Botsch, Ulrich Schwanecke and Hans-Peter Seidel, Feature-Sensitive Surface Extraction From Volume Data, Proceedings of ACM SIGGRAPH 2001. pp. 57-66, 2001. Jonathan C. Carr, Richard K. Beatson, Jon B. Cherrie, Tim J. Mitchell, W. Richard Fright, Bruce C. McCallum and Tim R. Evans, Reconstruction and Representation of 3D Objects With Radial Basis Functions, Proceedings of ACM SIGGRAPH 2001. pp. 67-76, 2001. (Aranz company web page)
Th Feb 12 Tu Feb 17 Th Feb 19	Point-based Models	Finish off Reconstruction and Representation of 3D Objects With Radial Basis Functions Globally consistent normals can be computed using the Euclidean MST of a Riemannian Graph on the point set. For details, see section 3 of Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle, Surface Reconstruction from Unorganized Points, Computer Graphics (Proceedings of SIGGRAPH 92). 26(2), pp. 71-78, 1992. Point-based Rendering: Marc Levoy and Turner Whitted, The Use of Points as a Display Primitive, Technical Report 85-022, Computer Science Department, University of North Carolina at Chapel Hill, January, 1985. Hanspeter Pfister, Matthias Zwicker, Jeroen van Baar and Markus Gross,Surfels: Surface Elements as Rendering Primitives, Proceedings of ACM SIGGRAPH 2000. pp. 335-342, 2000. Szymon Rusinkiewicz and Marc Levoy, QSplat: A Multiresolution Point Rendering System for Large Meshes, Proceedings of ACM SIGGRAPH 2000. pp. 343-352, 2000. Point-based Modeling PointShop3D, CGL, ETH Zurich,2002 M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin and C. T. Silva, Point Set Surfaces, IEEE Visualization 2001. pp. 21-28, 2001. Shachar Fleishman, Daniel Cohen-Or, Marc Alexa and Cl\'{a}udio T. Silva, Progressive Point Set Surfaces, ACM Transactions Vol. 22, No. 4, October 2003, Pages 997-1011. Slides for selected topics
	Assignment #2: Mesh Smoothing	See assignment web page Due date: Monday, February 23 before midnight (Start early!)
Tu Feb 24 Th Feb 26	Cloth Modeling and Animation	Slides: Part I: Introduction to cloth (Chris Twigg) Part II: Advanced cloth (Chris Twigg) READ: Xavier Provot, Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behaviour, Graphics Interface, Quebec City, Quebec, Canada, 1995 References: Xavier Provot, Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior, Graphics Interface '95, pp. 147-154, 1995. David Baraff and Andrew P. Witkin, Large Steps in Cloth Simulation, Proceedings of SIGGRAPH 98, pp. 43-54, 1998. D. E. Breen, D. H. House, P. H. Getto, A Physically-Based Particle Model of Woven Cloth, The Visual Computer. 8(5-6), pp. 264-277, 1992. David E. Breen, Donald H. House, Michael J. Wozny, Predicting the Drape of Woven Cloth Using Interacting Particles, Proceedings of SIGGRAPH 94. pp. 365-372, 1994. Robert Bridson, Ron Fedkiw, and John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of SIGGRAPH 2002, pages 594--603. Kwang-Jin Choi and Hyeong-Seok Ko. Stable but responsive cloth, Proceedings of SIGGRAPH 2002, pages 604--611, 2002. X. Provot, Collision and Self-collision Handling in Cloth Model Dedicated to Design, Computer Animation and Simulation '97, pp. 177-190, 1997. Martin Courshesnes, Pascal Volino, Nadia Magnenat-Thalmann, Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects, Proceedings of SIGGRAPH 95, pp. 137-144, 1995.
Tu Mar 2 Th Mar 4	Programmable Graphics Hardware	Slides: OpenGL ARB Vertex Program (presented by Cass Everitt at GDC 2003) OpenGL ARB Fragment Program (presented by Evan Hart at GDC 2003) References: William R. Mark, R. Steven Glanville, Kurt Akeley and Mark J. Kilgard, Cg: A System for Programming Graphics Hardware in a C-like Language, ACM Transactions on Graphics. 22(3), pp. 896-907, 2003.
	Assignment #3: Cloth Animation	See assignment web page Due date: Saturday, March 6 before midnight (Start early!)
Tu Mar 16 Th Mar 18	Character Skinning	Class slides of figures References: (used on whiteboard) J. P. Lewis, Matt Cordner and Nickson Fong, Pose Space Deformations: A Unified Approach to Shape Interpolation and Skeleton-Driven Deformation, Proceedings of ACM SIGGRAPH 2000. pp. 165-172, 2000. [An excellent related work section] Peter-Pike J. Sloan, Charles F. Rose III and Michael F. Cohen, Shape by Example, 2001 ACM Symposium on Interactive 3D Graphics. pp. 135-144, 2001. Xiaohuan Corina Wang and Cary Phillips, Multi-Weight Enveloping: Least-Squares Approximation Techniques for Skin Animation, ACM SIGGRAPH Symposium on Computer Animation. pp. 129-138, 2002. Paul G. Kry, Doug L. James and Dinesh K. Pai, EigenSkin: Real Time Large Deformation Character Skinning in Hardware, ACM SIGGRAPH Symposium on Computer Animation. pp. 153-160, 2002. Alex Mohr and Michael Gleicher, Building Efficient, Accurate Character Skins From Examples, ACM Transactions on Graphics. 22(3), pp. 562-568, 2003.
Tu Mar 23	Radiometry and Reflectance	Class slides References: Radiometry vs Photometry FAQ Peter Shirley's BRDF class at Utah Robert L. Cook and Kenneth E. Torrance, A reflectance model for computer graphics, Computer Graphics (Proceedings of SIGGRAPH 81). 15(3), pp. 307-316, 1981.
	Proposal Info and Class Schedule	Slides LaTeX Proposal Template (zip)
Tu Mar 30	Introduction to Global Illumination	Class slides Resources: David Banks, Holly Rushmeier, and Peter Shirley, A Basic Guide to Global Illumination, Course 5, SIGGRAPH 98. Paul Heckbert's "Global Illumination" course webpage Ray tracing bibliography BOOK: Philip Dutré, Philippe Bekaert and Kavita Bala, Advanced Global Illumination, A. K. Peters Ltd., 2003. [Amazon] [webpage] BOOK: Henrik Wann Jensen, Realistic Image Synthesis Using Photon Mapping, A. K. Peters Ltd., 2001. [Amazon] [webpage] Philip Dutré's online Global Illumination Compendium
Th Apr 1	Monte Carlo Path Tracing	Class slides Helper slides from [Dutré, Bekaert and Bala, 2003] References: Robert L. Cook, Thomas Porter and Loren Carpenter, Distributed Ray Tracing, Computer Graphics (Proceedings of SIGGRAPH 84). 18(3), pp. 137-145, 1984. James T. Kajiya,The Rendering Equation, Computer Graphics (Proceedings of SIGGRAPH 86). 20(4), pp. 143-150, 1986. Eric Lafortune and Yves Willems, Using the Modified Phong Reflectance Model for Physically Based Rendering, Report CW 197, Dept. of Computer Science, K.U. Leuven, November 1994. State of the Art in Monte Carlo Ray Tracing for Realistic Image Synthesis, Henrik Wann Jensen, James Arvo, Marcos Fajardo, Pat Hanrahan, Don Mitchell, Matt Pharr, Peter Shirley, Siggraph 2001 Course 29, August, 2001.
Tu Apr 6 Th Apr 8	Biased Monte Carlo Methods; Photon Mapping	Class slides: Biased Monte Carlo Ray Tracing: Filtering, Irradiance Caching, and Photon Mapping, Henrik Wann Jensen, Stanford University, May 23, 2002. Helper slides from [Dutré, Bekaert and Bala, 2003] and [Jensen, 2001]. References: Russian roulette and the pros/cons of ray branching are described in James Arvo and David B. Kirk, Particle Transport and Image Synthesis, Computer Graphics (Proceedings of SIGGRAPH 90). 24(4), pp. 63-66, 1990. Irradiance caching: Gregory J. Ward, Francis M. Rubinstein and Robert D. Clear, A Ray Tracing Solution for Diffuse Interreflection, Computer Graphics (Proceedings of SIGGRAPH 88). 22(4), pp. 85-92, 1988. Gregory J. Ward and Paul Heckbert, Irradiance Gradients, Eurographics Rendering Workshop, pp. 85-98, 1992. Gregory J. Ward,The RADIANCE Lighting Simulation and Rendering System, Proceedings of SIGGRAPH 94. pp. 459-472, 1994. Photon Mapping: See Henrik Wann Jensen's publications and book. Henrik Wann Jensen et al., A Practical Guide to Global Illumination using Photon Maps, Course 43, SIGGRAPH 2002. Henrik Wann Jensen and Niels Jørgen Christensen, Photon Maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects, Computers & Graphics vol. 19 (2), pp. 215-224, March 1995 Henrik Wann Jensen, Global Illumination using Photon Maps, In "Rendering Techniques '96". Eds. X. Pueyo and P. Schröder. Springer-Verlag, pages 21-30, 1996 SIGGRAPH 2001 Course Notes: A Practical Guide to Global Illumination Using Photon Mapping, ACM SIGGRAPH 2001, Los Angeles, California.
	Assignment #4: Photon Mapping	Assignment description Assignment webpage (with software info)
Tu Apr 13 Tu Apr 20	Radiosity	Class slides Petrov-Galerkin discretization of the radiosity equation (pdf handout) References: Michael F. Cohen and Donald P. Greenberg, The hemi-cube: a radiosity solution for complex environments, ACM SIGGRAPH Computer Graphics, Volume 19 Issue 3, July 1985. James T. Kajiya,The Rendering Equation, Computer Graphics (Proceedings of SIGGRAPH 86). 20(4), pp. 143-150, 1986. Michael F. Cohen, Shenchang Eric Chen, John R. Wallace and Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, ACM SIGGRAPH Computer Graphics, Volume 22, Issue 4, June 1988. Shenchang Eric Chen, Holly E. Rushmeier,Gavin Miller and Douglass Turner, A Progressive Multi-Pass Method for Global Illumination, Computer Graphics (Proceedings of SIGGRAPH 91). 25(4), pp. 165-174, 1991. Michael F. Cohen, John Wallace and Pat Hanrahan, Radiosity and Realistic Image Synthesis, Academic Press Professional, Inc., San Diego, CA, 1993 Steven J. Gortler, Peter Schröder, Michael F. Cohen and Pat Hanrahan, Wavelet Radiosity, Proceedings of SIGGRAPH 93. pp. 221-230, 1993. Alexander Keller, Instant Radiosity, Proceedings of SIGGRAPH 97. pp. 49-56, 1997.
Th Apr 22	Visual Importance	Class slides References: SIGGRAPH 2001 Course Notes: A Practical Guide to Global Illumination Using Photon Mapping, ACM SIGGRAPH 2001, Los Angeles, California. ...
Tu Apr 27	Visibility	Class slides Reference: Frédo Durand, A multidisciplinary survey of visibility, in ACM SIGGRAPH course notes "Visibility, Problems, Techniques, and Applications," July 2000.
Th Apr 29	Image-based Rendering	Class cancelled Suggested readings: Introduction: Leonard McMillan and Steven Gortler, Image-Based Rendering:A New Interface Between Computer Vision and Computer Graphics, Computer Graphics Newsletter, ACM SIGGRAPH, Vol.33 No.4 (Applications of Computer Vision to Computer Graphics), pp. 61-64, November 1999. Other references: Shenchang Eric Chen and Lance Williams, View Interpolation for Image Synthesis, Proceedings of SIGGRAPH 93. pp. 279-288, 1993. Shenchang Eric Chen, Quicktime VR - An Image-Based Approach to Virtual Environment Navigation, Proceedings of SIGGRAPH 95. pp. 29-38, 1995. Leonard McMillan and Gary Bishop, Plenoptic Modeling : An Image-Based Rendering System, Proceedings of SIGGRAPH 95. pp. 39-46, 1995. Marc Levoy and Pat Hanrahan, Light Field Rendering, Proceedings of SIGGRAPH 96. pp. 31-42, 1996. Steven J. Gortler, Radek Grzeszczuk, Richard Szeliski, Michael F. Cohen, The Lumigraph, Proceedings of SIGGRAPH 96. pp. 43-54, 1996. Steven M. Seitz and Charles R. Dyer, View Morphing: Synthesizing 3D Metamorphoses Using Image Transforms, Proceedings of SIGGRAPH 96. pp. 21-30, 1996. Paul E. Debevec, Camillo J. Taylor, Jitendra Malik, Modeling and Rendering Architecture from Photographs: A Hybrid Geometry- and Image-Based Approach, Proceedings of SIGGRAPH 96. pp. 11-20, 1996. Jonathan Shade, Steven J. Gortler, Li-wei He, Richard Szeliski, Layered Depth Images, Proceedings of SIGGRAPH 98. pp. 231-242, 1998.