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

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

INSTRUCTOR:� Doug James (Asst. Prof CS & Robotics)
UNIVERSITY UNITS: 12
DATE: Spring 2006
LOCATION: WeH 4615A
TIME: MW 1:30--2:50 PM

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
Deformation modeling
Topics in computer animation and physically based modeling

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

CLASS DATE	TOPICS	Material�� (Partly "CMU Only" access)
We Jan 18	Introduction	N/A
We Jan 18	Subdivision surfaces	Subdivision course notes (SIGGRAPH 98-00) Foundations I: Basic Ideas Foundations II: Subdivision for Surfaces The Subdivision Zoo Caltech curve subdivision applets
Jan 23 & 25	No classes (SIGGRAPH deadline)	Read subdivision course note chapters 1, 2, 3 and 4.
	Assignment #1: Subdivision Surfaces	See assignment web page Due date: Monday February 13 before midnight; Late policy: Don't be late: 15% maximum grade deducted every additional day.
Mo Jan 30	Subdivision Wrap-up	Subdivision course notes (SIGGRAPH 98-00) CLASS VIDEO: Le-Jeng Shiue, Ian Jones, J�rg Peters, A realtime GPU subdivision kernel, ACM Transactions on Graphics. 24(3), pp. 1010-1015, 2005. (pdf)
We Feb 1	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. CLASS VIDEO: Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, Hugues Hoppe, Fast exact and approximate geodesics on meshes, ACM Transactions on Graphics. 24(3), pp. 553-560, 2005. (pdf)
Mo Feb 6	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] CLASS VIDEO: Andrei Khodakovsky, Nathan Litke, Peter Schr�der, Globally Smooth Parameterizations With Low Distortion, ACM Transactions on Graphics. 22(3), pp. 350-357, 2003.
Wed Feb 8	Progressive Meshes	Hugues Hoppe, Progressive Meshes, Proceedings of SIGGRAPH 96. pp. 99-108, 1996. Hugues Hoppe, View-dependent Refinement of Progressive Meshes, Proceedings of SIGGRAPH 1997, ACM Press/Addison-Wesley Publishing Co., New York, NY, 189-198, 1997. Andrei Khodakovsky, Peter Schr�der and Wim Sweldens, Progressive Geometry Compression, Proceedings of ACM SIGGRAPH 2000. pp. 271-278, 2000. CLASS VIDEO:� David Cohen-Steiner, Pierre Alliez, Mathieu Desbrun, Variational shape approximation, ACM Transactions on Graphics. 23(3), pp. 905-914, 2004.
Mon Feb 13	Streaming Meshes	LOCAL: Locality-Optimizing Caching Algorithms and Layouts� (read this summary) Martin Isenburg and Peter Lindstrom, Streaming Meshes, IEEE Visualization 2005, October 2005, pp. 231-238. (webpage) CLASS VIDEO:� Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Streaming Compression of Triangle Meshes (660KB, paper), Proceedings of 3rd Symposium on Geometry Processing, pages 111-118, July 2005.� (Video from SIGGRAPH 2005 sketch)
Wed Feb 15	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] T. R. Jones, F. Durand and M. Desbrun, Non-iterative, feature-preserving mesh smoothing, ACM Trans. Graph. 22, 3, 943-949, 2003.
Mon Feb 20+	Laplacian Mesh Editing	Olga Sorkine, State-of-the-art report: Laplacian Mesh Processing, Presented at Eurographics 2005. CLASS VIDEO: Yaron Lipman, Olga Sorkine, David Levin, and Daniel Cohen-Or, Linear Rotation-Invariant Coordinates for Meshes, SIGGRAPH 2005. Also discussed... Robert W. Sumner, Jovan Popovic', Deformation Transfer for Triangle Meshes, ACM Transactions on Graphics. 23(3), pp. 399-405, 2004. CLASS VIDEO:� Robert W. Sumner, Matthias Zwicker, Craig Gotsman, Jovan Popovic', Mesh-based Inverse Kinematics, ACM Transactions on Graphics. 24(3), pp. 488-495, 2005.
FYI	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)
Wed Feb 22	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: Thin Shells	Assignment description (pdf) Eitan Grinspun, Anil N. Hirani, Mathieu Desbrun, Peter Schroeder, Discrete Shells, 2003 ACM SIGGRAPH / Eurographics Symposium on Computer Animation. pp. 62-67, 2003.
Mon Feb 27 Wed Mar 1	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. David Baraff, Andrew Witkin, Michael Kass, Untangling Cloth, ACM Transactions on Graphics. 22(3), pp. 862-870, 2003. R. Bridson, S. Marino, R. Fedkiw, Simulation of clothing with folds and wrinkles, 2003 ACM SIGGRAPH / Eurographics Symposium on Computer Animation. pp. 28-36, 2003. CLASS VIDEO: Robert Bridson, Cloth Collisions, from SIGGRAPH 2005 Course on "Advanced Topics on Clothing Simulation and Animation."
Mon Mar 6	The Conjugate Gradient Method	Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, Technical report, Carnegie Mellon University, August 1994. G. H. Golub and C. F. van Loan, Matrix Computations, third ed., Johns Hopkins University Press, Baltimore, 1996.
Wed Mar 8	Newmark Integration, etc.� Subspace and multi-resolution integrators	Numerical integration Quick: web link W. L. Wood, Practical Time-stepping Schemes, Clarendon Press, Oxford, 1990. .... or any other standard mechanics reference. Ascher, U. and Petzold, L. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. Philadelphia, PA: SIAM Press, 1998. [Good numerical ODE/DAE reference] C. Kane, J. E. Marsden, M. Ortiz and M. West, Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems, International Journal for Numerical Methods in Engineering 49(10), 1295-1325, 2000.� [For the braver student] Multi-resolution/adaptive integration: Eitan Grinspun, Petr Krysl, Peter Schr�der, CHARMS: A Simple Framework for Adaptive Simulation, ACM Transactions on Graphics. 21(3), pp. 281-290, 2002. Subspace integration: Jernej Barbic and Doug James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM Transactions on Graphics. 24(3), pp. 982-990, 2005. P. Krysl, S. Lall and J. E. Marsden, Dimensional Model Reduction in Non-linear Finite Element Dynamics of Solids and Structures, Int. J. Numer. Meth. Engng, 51, 479-504.

	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.
	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.
	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.
	Project Proposal (due April 14 in class)	Slides LaTeX Proposal Template (zip)
	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
	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.
	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 #3: Photon Mapping	Assignment description Assignment webpage (with software info) Software overview slides Rendering contest entries
	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.
	Visual Importance	Class slides References: SIGGRAPH 2001 Course Notes: A Practical Guide to Global Illumination Using Photon Mapping, ACM SIGGRAPH 2001, Los Angeles, California. ...
	Visibility	Class slides Reference: Fr�do Durand, A multidisciplinary survey of visibility, in ACM SIGGRAPH course notes "Visibility, Problems, Techniques, and Applications," July 2000.
	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.