Advanced Computer Graphics - SS 2020

This course will introduce students to advanced and more complex methods and techniques of computer graphics. Some of the topics that were touched upon in the Bachelor course "Computer Graphics" will be covered in more depth. In addition, more and other topics will be covered that were not taught in the Bachelor's course. This approach will both broaden and deepen students' knowledge about the field of computer graphics.

This course is for you, if you want to acquire ...

• Knowledge of advanced and more complex methods and techniques of computer graphics.
• Mastering of some of the topics that were already touched upon in the basic computer graphics course, by expanding them in greater depth.
• Ability to follow the current research literature on those topics.
• Skills to implement complex techniques in those areas.
• Knowledge of the principles of photorealistic image generation.
• Larger overview over the amazing wealth of topics and research questions in computer graphics,

There are no formal prerequisites, but some degree of the following skills are desirable:

1. A little bit of experience with C/C++ ; note that you will need just "C with classes" during this course.
2. Knowledge of the material of the Bachelor course "Computer Graphics" (if you didn't manage to attend that course, you can easily recap that material for yourself).
3. Algorithmic thinking (and, hopefully, some pleasure when thinking about algorithms)

Some of the envisioned topics (these can change during the semester):

1. Data structures and the theory of boundary representations (meshes);
2. Advanced texturing methods;
3. Generalized barycentric coordinates and parameterization of meshes;
4. Advanced shader programming (special effects);
5. Culling techniques (real-time rendering);
6. Ray-tracing (photo-realistic images);
7. Alternative object representations (modeling);
8. Mesh processing

News

We will meet at Twitch.
You can also join our Discord.

Slides

The following table contains the topics and the accompanying slides (it will be filled step-by-step).

Lecture	Topics	Slides	Voluntary assignments	Frameworks
1.	Organization; Ray-tracing 1: principle, the rendering equation, Whitted-style ray-tracing	PDF 0 PDF 1
2.	Ray-tracing 2: camera models, lighting model, reflected rays, refraction, Fresnel terms, attenuation, scattering, dispersion	PDF
3.	Ray-tracing 3: intersection ray-polygon, intersection ray-triangle, intersection ray-box, ray-sphere intersection, ray-tracing height fields, numerical robustness	PDF
4.	Ray-tracing 4: limitations of Whitted-style ray-tracing, distribution raytracing: anti-aliasing, soft shadows, glossy-matte reflection, depth-of-field, motion blur	PDF
5.	Object representations 1: quadrics and superquadrics, implicit surfaces, root finding methods (bisection, regula falsi, Newton-Rhapson), metaballs	PDF
6.	Object representations 2: normals for implicit surfaces, polygonization of implicit surfaces using marching cubes, marching tetrahedra, polygonization with particle systems	PDF	Sheet 1	Raytracing Framework
7.	Object representations 3: instancing, constructive solid geometry (raytracing and polygonization), procedurally defined fractals, implicite surfaces from point clouds	PDF
8.	Acceleration data structures 1: taxonomy, light buffer, beam and cone tracing, bounding volumes	PDF	Sheet 2	Extended Raytracing Framework
9.	Acceleration data structures 2: 3D grids, mailbox technique, traversal and storage, optimal grid resolution, recursive grid, octree	PDF
10.	Acceleration data structures 3: kd-trees, kd-tree traversal, kd-tree construction, surface area heuristic (SAH)	PDF
11.	Acceleration data structures 4: efficient storage of kd-trees, Bounding volume hierarchies (BVHs), BVH traversal using p-queue, principle of construction of BVHs, median cut heuristic, plane sweep along principal axis with SAH. irregular grids (construction and ray traversal)	PDF
12.	Collision Detection 1: requirements, pipeline, collision matrix, broad phase, narrow phase, 3D grid, sweep and prune, temporal coherence, separating planes	PDF	Sheet 3
13.	Collision Detection 2: hierarchical collision detection, bounding volume, BV hierarchies, k-DOPs, inner sphere trees, penetration measures	PDF
14.	Culling Part 1: bottlenecks in the rendering pipeline, types of culling, backface culling	PDF
15.	Culling Part 2: hierarchical clustered backface culling	PDF	Recap Clipping
16.	Culling Part 3: view frustum culling, hierarchical view frustum culling, occlusion culling, batched queries, naive wait-and-draw algorithm, multiqueries, coherent hierarchical culling (CHC++)	PDF
17.	Culling Part 4: portal culling, detail culling, aggresive approximate culling. Advanced shader techniques 1: recap of programmable pipeline and GLSL	PDF1 PDF2
18.	Advanced shader techniques 2: procedural textures in the shader, value noise, gradient noise, simplex noise, example: procedural textures with noise,	PDF
19.	Advanced shader techniques 3: refractive objects, the geometry shader, simple examples, rendering furry objects with shells and fins, rendering silhouettes.	PDF
20.	Advanced texturing methods 1: seams, texture atlas, cube maps, polycube maps	PDF
21.	Advanced texturing methods 2: polycube maps, concept of environment mapping, spherical environment mapping, parabolic environment mapping, cube environment mapping, dynamic environment mapping Procedural modeling 1: seashells	PDF1 PDF2
22.	Procedural modeling 2: fractal terrain modeling, terrain modelling using fault lines, L-systems (D0L, parametric, stochastic), L-system for modeling rocks	PDF

You can download some of the shaders that were discussed in class, plus some some very simple ones (discussed in the Bachelor course).

Textbooks

The following textbooks can help review the material covered in class:

• Andrew Glassner (ed.): An Introduction to Ray Tracing; Morgan Kaufman
• Peter Shirley: Realistic Ray Tracing; AK Peters.
• Foley, van Dam, Feiner, Hughes: Computer Graphics -- Principles and Practice; Addison Wesley.
• Tomas Akenine-Möller, Eric Haines: Real-Time Rendering; AK Peters.
• Matt Pharr, Wenzel Jakob, Greg Humphreys: Physically-Based Rendering; Morgan Kaufmann. (Commonly referred to as PBRT)
• Alan Watt, Mark Watt: Advanced Animation and Rendering Techniques. Addison-Wesley
• Online Literature, see below

Please note that the course is not based on one single textbook! Some topics might even not be covered in any current textbook! So, I'd suggest you first look at the books in the library before purchasing a copy.

If you plan on buying one of these books, you might want to consider buying a used copy -- they can often be purchased for a fraction of the price of a new one. Two good internet used book shops are Abebooks and BookButler.

Additional Literature and Demos for Deeper Insights

• On Raytracing (global illumination):
  • Siggraph course on Physically-Based Shading Models in Film and Game Production by Naty Hoffman (Activision Studio Central), Yoshiharu Gotanda, Adam Martinez (Sony), Ben Snow (ILM), 2010 (source).
  • An animated video explaining the rendering equation by Matthias Parchettka; it's only in German (ist ein wenig albern, aber vielleicht trotzdem hilfreich; source).
  • Siggraph course notes on ray-tracing and photon mapping by Henrik Wann Jensen (UCSD) and Per Christensen (Pixar), 2008.
  • The classic book Principles of Digital Image Synthesis by Andrew Glassner, 1995.
  • Siggraph course notes on interactive ray-tracing, 2006.
  • Alex Ryer: Light Measurement Book (source); explains a lot of the principles of light sources, light perception, and light transportation.
  • Ray Tracing in One Weekend by Peter Shirley, Steve Hollasch and Trevor David Black walks you through programming a simple raytracer. It does not contain a lot of math, but explains the code nicely, and contains lots of example images showing what the code does.
• Siggraph course notes on implicit surfaces, 1996.
• Literature on advanced texturing techniques:
  • The tutorial OpenGL cube map texturing by NVIDIA, 1999.
  • Siggraph course notes lighting and shading techniques for interactive applications , 1999 (chapters 6, 10, and 11).
• On GLSL, shader programming:
  • Our shader editor Shader Maker is a simple, cross-platform GLSL editor. It works on Windows, Linux, and Mac OS X. (Includes lots of simple GLSL program examples.)
  • BKcore's Shdr, a shader editor that runs in the browser. Pretty cool, except it lacks a few features of our ShaderMaker: it does not have a geometry shader, no time uniform, no textures, and I don't see a way to change the values of uniforms interactively. But very nice for simple GLSL programs. (Source code can be found here, in case you want to improve it.)
  • Lots of demos and tutorials on shader programming can be found at OGLdev.
  • A GLSL Quick Reference Guide (Quelle).
  • Die offizielle GLSL Spezifikation (falls man etwas nochmal ganz genau nachschlagen muß).
  • Die OpenGL 4.1 Reference Pages (sehr praktisch zum schnellen Nachschlagen).
  • Eine leicht verständliche Einführung in Framebuffer Objects von gamedev.net (Rob Jones) (Quelle).
• An easy introduction to simplex noise by Stefan Gustavson (source).
• A fairly comprehensive explanation of Spherical, Cubic, and Parabolic Environment Mappings by Paul Zimmons.
• On Culling:
  • Hansong Zhang, Kenneth E. Hoff III: Fast Backface Culling Using Normal Masks
  • Andreas Johannsen, Michael B. Carter: Clustered Backface Culling
  • Ulf Assarsson and Tomas Möller: Optimized View Frustum Culling Algorithms for Bounding Boxes
  • Lighthouse 3D: View Frustum Culling Tutorial
• Literature complementing the chapter on boundary representations:
  • A paper on array-based mesh data structures (for our course, only the first part is relevant)
  • A nice tutorial on the DCEL data structure by Ryan Holmes (source)
  • A tutorial on specification, representation, and construction of non-manifold geometric structures (this is only partially relevant for our course, but it can serve as an outlook on how to extend the concepts into n-dimensional geometry)
  • Two essays on the Euler characteristic: one by Edward Early (source), and one by Sudesh Kalyanswamy (source), the latter being more geared towards graphs, but still relevant in computer graphics, too.
  • A simple proof of the Jordan Curve Theorem for the important class of polygons (source)
  • Similar to regular polyhedra, one can even define Infinite Regular Polyhedra, and, here too, the genus plays a very important characterizing role (source)
  • Rediscovering Euler's formula with a mug
• An interactive demo for DCEL's (javascript), created by one of your fellow students.
• Literature on generalized barycentric coordinates:
  • Hormann & Floater: Mean Value Coordinates for Arbitrary Planar Polygons
  • Surazhsky & Gotsman: Intrinsic Morphing of Compatible Triangulations
  • Floater: Mean Value Coordinates
• The SIGGRAPH 2007 course notes on Mesh Parameterization by Kai Hormann, Bruno Levy, and Alla Sheffer. (Source)
• Literature and links on L-systems:
  • The wonderful book The Algorithmic Beauty of Plants by Przemyslaw Prusinkiewicz and Aristid Lindenmayer, 2004. (Source)
  • Arbaro is a free software to generate tree models for povray.
• A tutorial on the PCA by Prof. Laurenz Wiskott, 2004. (Source)

Other Interesting Bits and Pieces

• Not exactly about computer graphics, but here is a clip from an interview with Linus Torvalds, where he speaks about tasteful code. And although he does not explicitely mention it, I strongly believe that tasteful code is what makes robust code. (Source: Linus Torvalds: The mind behind Linux, February 2016 at TED2016.)
• Interview with Vint Cerf, one of the fathers of the Internet (think TCP/IP, not HTML). He begins with its inception, continues through its evolution, and touches upon the future.

Gabriel Zachmann
Last modified: Tue Jan 19 09:41:33 CET 2021