2013 Graphics Qual - Main Reading List

2013 Graphics Qual - main reading list.

A more official place to look for information about the Graphics Qual is at http://graphics.cs.wisc.edu/GraphicsQual/, however, that might just lead you back to here.

This is the Graphics Qual Reading List for 2013. It is an adaptation of the 2011 Reading List. It is substantively the same, however, some of the broader suggestions are made concrete. (it might seem like new topics were added, but they actually are all mentioned on the old list - it’s just that now we’re being specific about what we mean by things like ``differential geometry.’')

This list still has carry over issues from the old reading lists, so if a paper references is difficult to identify, you might go back to the 2004 Qual Reading List.

This list should be considered temporary and specific to the Fall 2013 Qual

1.@ New for 2013: The Modern Paper

In addition to the standard reading list of core topics, the qualifying exam includes a short (1 for 2013) list of modern papers. Students are expected to understand this paper, including the background required (e.g. by looking through its reading list). The goal of this section of the qual is less to see that the student understands the specifics of this one paper, but rather, that they are capable of interpreting a modern paper including traversing its background.

The paper will be assigned no later than 4 weeks prior to the examination date.

The Paper for Spring 2017 is:

The Paper for Fall 2017 is:

The Paper for Spring 2014 is:

The Paper for Fall 2013 is:

2.@ Foundations: Graphics Texts

Students are expected to have mastery of the topics covered in anintroductory graphics course. The introductory graphics course isCS559, and its recent syllabus should be used as a guide. Note thatsome topics may only covered in passing in the class, but arestill considered important for the Qualifying Exam. For some topics, we expect more depth than the intro class may provide.

The textbooks for CS559 (both required and recommended) are suggestedas the core references for the Qualifying Exam. The editions listedare current as of the writing of this list, but students should seekthe most current text available. Chapter numbers refer to the versionslisted.

[FCG] Shirley, Marschner, et. al. Foundations of Computer Graphics, 3e. AK Peters Publisher, 2009.

[RTR] Akienne-Moller, Haines, and Hoffman. Real-Time Rendering, 3e. AK Peters Publisher, 2009.

[OGL] Shreiner, et al. OpenGL Programming Guide, 7e. Addison Wesley, 2009.

2.1@ Topics from Foundations of Computer Graphics

In the order they appear in [FCG] - note that [FCG] is not always the preferred resource for the topic.

• Mathematical Basics [FCG 2,5]: Linear Algebra (including the SVD), interpolation
• Raster Imaging [FCG 3]: The content of this chapter of FCG is really just a preliminary sketch of things that come later.
• Ray Tracing [FCG 4,13]: the basic ideas are important, the ray/primitive intersection methods are not. (see the realistic rendering section below)
• Transformations, Viewing [FCG 6,7][RTR 4]: FCG misses some important things like Quaternions (covered in RTR). RTR also includes the basics of other important ideas like morphing and vertex blending (although, other readings may enhance those). Jehee Lee’s survey of the issues in rotations (below) is required for concepts like Quaternions and rotation vectors.
• The “Traditional” Graphics Pipeline [FCG 2,8] [RTR2]: This includes basic rasterization algorithms, clipping, and anti-aliasing.
• Image and Signal Processing [FCG 9]:
• Lighting (local shading models) [FCG 10] [OGL] [RTR]:The OpenGL bookdescribes the model well, but the syntactic details of using it withinOpenGL are an ugly legacy that is not required. Stylized shading is another seperate topic.
• Texturing [FCG 11][RTR 6]: RTR is the key resource here, includingsampling issues and strategies, and tricks for using texturing to achieve other means.
• Data Structures / Acceleration Algorithms [FCG 12] [RTR 14]: [FCG12] is a hodgepodge of basic stuff that everyone should know. [RTR 14] has too much detail, but replaces the Visibility section of the old qual reading list
• Curves and Surfaces [FCG 15][RTR 13]: [FCG] completely omits surfaces. The topic (especially subdivision and meshes) deserves more than what RTR provides (more readings below), but its a good start.
• Animation [FCG16]: Covers the basics (which might not appear in the more detailed papers below).
• Programmable Graphics Hardware [FCG 18][RTR 3][OGL 15]:While this is amoving target, the key ideas of the pipeline seem to have settled overthe past few years. Students should understand the idea behind ashading language (like GLSL) as a reflection of the computationalmodel, but the syntactic details of particular languages are unimportant.
• Interactive Architectures [FCG19]: The chapter has a lot of stuff that’s way too basic, but students should understand event models vs. polling and MVC.
• Color [FCG21]: Students should understand both the perceptual foundations (presented, in an albeit obtuse way in FCG), as well as more practical issues
• Visual Perception [FCG22]: The FCG chapter is a good starting point.
• Tone Reproduction [FCG23]: Clearly a case where the basic issues and ideas are more important than the details.
• Global Illumination [FCG 24] [RTR 9]: The basic concepts are important, but the methods are not well described in either text (and not important). See the Photorealistic Rendering section below. The hacks described in RTR for achieving global illumination effection within the standard rendering pipeline (like 40 pages of shadow mapping tricks) are not essential for the qual, except for the way they bring in the issues of what kinds of effects are difficult to achieve with various rendering approaches.
• Visualization [FCG27,28]: In the future, this will be an entire section of the qual. For now, what is here serves as a good introduction.

2.2@ Topics from Real-Time Rendering

Topics in RTR that are only mentioned briefly in FCG, but stillrequired. These are places where the text is the best starting point (as opposed to the older Qual reading list where we recommended the original source papers for the concepts). Topics where additional papers are needed are discussed in subsequent sections:

• Transformations [RTR4] - A lot of basic animation concepts (skinning, morphing) are hidden here.

• Visual Appearance [RTR5] - RTR organizes a lot of material scattered aboutFCG in one place. (gamma, anti-aliasing, compositing, …)

• Rendering [RTR7, RTR8, RTR9] - The three chapters of RTR that cover “lighting and shading” give enough of the basic concepts of rendering. They generally are sufficient (see the rendering section below for a few exceptions). The discussions of “real-time hacks” can be skipped.

  • Chapter 7 - Gives more details on the physics than necessary, but the intuitions are useful for understanding the more essential material. The concepts of surface appearance (like “what is the BRDF”) are essential, the specific surface models given are not.
  • Chapter 8 - The details of geometric lighting are less important than the idea of image-based lighting (using environment maps), including spherical harmonics.
  • Chapter 9 gives a good overview of global lighting, including introducing the light-path calculus (which is extremely important). The specific “hack algorithms” for faking global illumination in real-time rendering are not important for the qual (9.1.X, 9.2.5, 9.3 and 9.4 can be skipped).

• Non-Photorealistic Shading [RTR11] - a good introduction to the basics that should be augmented with the important papers below

• Polygonal Techniques [RTR12] - a good coverage of the basics that sufficiently replaces various sections of the older qual list.

• Surfaces [RTR13] - provides the basics of parametric surfaces and subdivision.

3.@ Other Topics

These are topics where reading beyond the texts is required.

3.1@ Differential Geometry and Surface Parameterization

Differential Geometry is an important foundation for much of graphics. Students must have a sense of the basic concepts (curvature, distortion, …). Parts of #1 and #2 below should provide sufficient background.

Otherwise for a good primer, see the notes (and slides) from the SIGGRAPH Discrete Differential Geometry course (particularly Lecture 2). For further details refer to the resources listed at The 2009 Advanced Graphics Course Readings.

Surface parameterization is a useful tool for many graphics applications and a setting for applying differential geometry concepts. Students should be aware of the key issues in surface parameterizations, and have some sense of the kinds of approaches available. Suggested readings (any one should be enough):

1. Floater, M., & Hormann, K. (2005). Surface Parameterization: a Tutorial and Survey. In N. A. Dodgson, M. S. Floater, & M. A. Sabin (Eds.), Advances in Multiresolution for Geometric Modelling (pp. 157@186). Berlin/Heidelberg: Springer-Verlag. doi:10.1007/b138117 (author copy) - a very widely cited survey, with a nice introduction and tutorial to differential geometry that gets too mathematical too fast.
2. Floater, Sheffer, and others. Mesh Parameterization SIGGRAPH Course (offered in 2008 and 2007), notes online. The Differential Geometry primer is useful not only as a tutorial on differential geometry, but also on the basic issues in parameterization.
3. Sheffer, A., Praun, E., & Rose, K. (2006). Mesh Parameterization Methods and Their Applications. Foundations and Trends@ in Computer Graphics and Vision, 2(2), 105@171. doi:10.1561/0600000011 (author version) - also a nice survey that covers many of the techniques. Provides an excellent survey of the applications of parameterizations and the methods for doing it - with a little less background on the issues.

3.2@ Computational Geometry

Students should have an awareness of the basic problems and strategies. Details of algorithms are not required. Specifically, students should know about:

• convex hulls
• triangulations, with focus on Delaunay triangulations
• Voronoi diagrams
• Polygon triangulation

Any basic text should suffice, however recommendations include:

• de Berg, van Keveld, Overmars and Schwarzkopf. ``Computational Geometry: Algorithms and Applications, 2e.’’ Springer, 1998.
• O’Rourke. Computational Geometry in C. Cambridge, 1998. (web page)

3.3@ Image-Based Rendering

Modern IBR is covered in RTR. These seminal papers are mainly for historical perspective.

• [McMillan:1995:PMA] Plenoptic Modeling. (a more rigorous variant of Quicktime VR [Chen:1995:QVI] - which is still interesting because of its commercial success).
• Levoy:1996:LFR Light Field Rendering

3.4@ Image Warping

The first paper is important because it is so seminal and gets at the issues in warping and morphing. The second is important as an example of a kind of method:

• [Beier:1992:FIM] Beier, T., & Neely, S. (1992). Feature-based image metamorphosis. ACM SIGGRAPH Computer Graphics, 26(2), 35@42. doi:10.1145/142920.134003. This paper (and the method it introduces) is important because it is the first highly successful warping technique. What differentiates it from what came before is that it is designed to be useful by artists.
• Igarashi, T., Moscovich, T., & Hughes, J. F. (2005). As-rigid-as-possible shape manipulation. ACM Transactions on Graphics, 24(3), 1134. doi:10.1145/1073204.1073323 - a basic optimization-based warping technique that inspired many later methods.

3.5@ Modeling and Shape Representation

Students should have a familiarity with the major methods forrepresenting shape (surfaces and solids) in ComputerGraphics. Familiarity with polygon models, parametric surfaces (Bezierpatches, B-Splines, NURBS), subdivision surfaces, point setrepresentations, constructive solid geometry and implicit surfaces isimportant. Students should have the basic concepts of each, andunderstand the tradeoffs to know where each is appropriate.

The core readings generally cover these topics (mainly RTR13).

These topics are generally covered in the core. The readings augment this:

• Subdivision surfaces: [DeRose:1998:SSI] Practical issues (and motivation) for Subdivision surfaces (a seminal paper for its motivating aspects). (this augments RTR13)
• Smoothing: RTR12 is sufficient. Understanding Taubin’s early work (e.g. the “Taubin smoothing method”) is important for the intuitions.
• Simplification: Chapter 12 of RTR is probably sufficient, but the original sources are good but optional ([Garland:2005:QSD] is a newer reference than the original 1997 SIGGRAPH paper, it has the advantage of giving some perspective on the technique; [Hoppe:1996:PM] Progressive Meshes: The first technique for continuous level of detail, is also an optional seminal paper)
• Free-Form Deformations: It seems obvious now, but it was an important idea at the time. The paper is seminal. [Sederberg:1986:FDO] Free Form Deformations.
• Implicit representations, Level Sets, and Signed Distance Fields: you should know what these are and why they are important. (Chapter 16 of FCG covers the main points, but Section 6.2 “Level Sets” of Bridson’s Fluid Course Notes (or text) is recommended to Level sets).

3.6@ Photorealistic Rendering

The basic ideas of rendering (which are really about lights and surfaces, not necessarily the algorithms) are sufficiently covered by the RTR chapters described above. At least until there is a real rendering course. FCG sufficiently covers ray tracing.

Two key concepts that might deserve more reading:

• The light-path calculus, and the need for radiance caching is introduced in RTR9. The original paper [Heckbert:1990:ART]]] gives more explanation to these critical ideas.
• Photon map techniques are important as they give a practical way to implement radiance caching, and make the central issues clear. The seminal paper [Jensen:1995:PMI] gives far more than the basic intuitions required for the qual.

Note: for rendering, it is important to understand the properties of lighting, and what different kinds of effects different types of renderers can and cannot achieve. The specific details of rendering algorithms are not required.

3.7@ Stylized Rendering

The core readings discuss a variety of the basic styles, and should be a first starting point (especially for things like silhouettes and toon shading). Impressionist or painting-based styles are included for historical significance.

• Gooch shading is important, but is in the core readings
• Suggestive Contours, DeCarlo et al. SIGGRAPH 2003.
• Image Abstraction (DeCarlo and Santenella, SIGGRAPH 2002)

3.8@ Human Figure Animation

• Inverse Kinematics: core reading [FCG 16] has basics. Knowing the basic approaches to how IK is done (e.g. numerical, closed-form, example-based), and the core issues in IK is essential.
• Skinning: basics covered in core, but [Mohr:2003:SBE] Skinning by example is still important - less for the methods, but more for its discussion of basic skinning techniques and their good and bad points. Harmonic Coordinates [Joshi] is important because it introduces Cage-Based Skinning.
• Animation by Example (motion capture): still looking for a good survey that covers the basic issues and gets at the modern “Synthesis-By-Example” approaches. For now, the papers from the old list are good for getting at the issues: Retargeting Motion to New Characters Gleicher:1998:RMT] (but ignore the actual spacetime methods), Motion Graphs [Kovar:2002:MG], and Registration Curves [Kovar:2003:RC].

3.9@ Seminal Systems

Students should have enough of a sense of the history of the field, and be aware of some key systems and why they are significant. While the exact details of these systems are not important, an appreciation for why they were important is. (this list is greatly reduced)

• Sutherland:1963:SAM] Sketchpad.
• Cook:1987:TRI] Renderman and Reyes Renderers.
• Chen:1995:QVI] Quicktime VR

3.10@ Rotations

Lee’s article is a good place to learn the key concepts.

• Lee, J. (2008). Representing Rotations and Orientations in Geometric Computing. IEEE Computer Graphics and Applications, 28(2), 75@83. doi:10.1109/MCG.2008.37

3.11@ Laplacian Editing Approaches

Approaches that use optimization to create smooth changes to complex objects are successful in image processing, mesh editing, motion processing, and other things. Students should be familiar with the basic idea of the approach, by learning some specific manifestation. The details of any particular method is less important than the overall approach.

• Igarashi, T., Moscovich, T., & Hughes, J. F. (2005). As-rigid-as-possible shape manipulation. ACM Transactions on Graphics, 24(3), 1134. doi:10.1145/1073204.1073323 (mentioned in another section as well)
• Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rossl, C., & Seidel, H.-P. (2004). Laplacian surface editing. Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing - SGP @04 (p. 175). New York, New York, USA: ACM Press. doi:10.1145/1057432.1057456 (a seminal paper that shows the advantages of the approach and ways to deal with the issues)

3.12@ Gradient Domain Approaches

These are closely related to the Laplacian approaches above. Students should have an intuition as to where gradient-domain approaches may be of value. Here we provide some example papers that apply the approach - but the thing of interest is the approach, not the specifics.

• Perez, P., Gangnet, M., & Blake, A. (2003). Poisson image editing. ACM Transactions on Graphics, 22(3), 313. doi:10.1145/882262.882269

3.13@ Physically-based Modeling and Animation

Students should understand the basics of physical simulation, including how the world is modeled as a differential equation, the issues in solving these equations, and the basic methods for dealing with these issues. The Witkin and Baraff Course Notes (the 2001 version is available at the Pixar website) are the standard reference. (constrained dynamics and collisions and contact are not required for the qual)

3.14@ Specific, Smaller Techniques

Students should be familiar with what these are and why they are used.

• Bi-lateral filters
• Perlin noise