Advanced Graphics

Universiteit Utrecht - Information and Computing Sciences

academic year 2015/16 – 3rd period

title image title image title image
   support forum:
  magr2016.freeforums.org

Navigation

News (Archive)

Course Overview

Schedule

Grading

Format & Organization

Topics

Lecture Slides

Practicals

Literature & Links

News

Recent news

Apr 21:

Apr 14:

  • Final lecture uploaded: Grand Recap / Monte Carlo.

Apr 11:

  • Second set of example exam questions is now available.
  • Wednesday April 13: lecture + working college in BBG-023!

Apr 8:

  • Slides for lecture 13 are now available.
  • Slides for lecture 13 updated; most or all typos and errors fixed.

Apr 6:

OLDER POSTS

Assignment 2 Galery - 2016


















Assignment 3 Galery - 2016
















Course Overview

Overview

The master course Advanced Graphics addresses advanced topics in 3D computer graphics. The focus of the course is Physically-based rendering of 3D scenes. The course has two main focus areas: Rendering Algorithms and Making Rendering More Efficient. Efficiency will be sought through Acceleration Structure Construction and Traversal and Variance Reduction (rather than low level optimization).

The course starts with a recap of Whitted-style ray tracing. We then explore various acceleration structures that help to run the ray tracing algorithm in real-time on commodity hardware. We will see that a well-built Bounding Volume Hierarchy provides both flexibility and speed, for static and dynamic scenes.

The second part of the course introduces the path tracing algorithm, and related light transport theory. We investigate various methods to improve the efficiency of the algorithm using probability theory. We will see that efficient path tracing can yield interactive frame rates.

In the third part of the course we use GPGPU to run ray tracing and path tracing on the GPU. We will explore recent research in high performance stochastic rendering.

Check the (centrally managed) schedule on Osiris. Uniform course information via www.cs.uu.nl. Check here for a list of students for this course.


Format and Organization

PEOPLE

Lecturer: Jacco Bikker (bikker.j@gmail.com)

Lecture

  • Two lectures per week: Wednesday afternoon, Friday morning
  • One lecturer supervised lab per week
  • Time slots & Rooms: TBD

Practicals

This course has a practical project track. During this course, you will develop an interactive renderer. You may work on this project alone, or with one other student. The practical project has three milestones, of which two will be graded.

Final Exam

For this course, there will be one exam at the end of the block (i.e., no mid-term exam). A retake exam can be used to compensate some deficits (see grading section for details).

Overall grading

You must have a sufficient score (6 or better) for the practical part and the final exam to pass this course. The final grade is a weighted average of the two parts (see grading section for details).


Prerequisites

  • Basic knowledge in linear algebra, calculus and probability theory, as required for the masters program. See "Elementary maths for GMT".
  • Fundamentals in algorithms and data structures.
  • Bachelor level knowledge in computer graphics is strongly recommended. Without prior graphics knowledge, you will need substantial additional time (and probably some talent).
  • Good programming skills; C# and C++ will both work, but for optimal performance and certain low level aspects, C++ is recommended. Plan for additional time if you plan to familiarize yourself with C++ during the course.
  • Good to have: basic experience with graphics programming (e.g. OpenGL / DirectX).
 

Topics

Ray Tracing

Whitted-style Ray Tracing

  • Recap
  • Beer's Law, Fresnel

Acceleration Structures

  • Octree, kD-tree, BSP
  • Bounding Volume Hierarchy
  • Efficient Construction & Traversal

Dynamic Scenes

  • The Top-Level BVH

Real-time

  • Ray Packet Traversal
 
Path Tracing

Light Transport

  • The Rendering Equation

Monte-Carlo Algorithms

  • Distributed Ray Tracing
  • Path Tracing

Variance Reduction

  • Stratification
  • Importance Sampling
  • Next Event Estimation

Interactive

  • Multi-branching BVHs
 
Efficiency

GPU implementations

  • Streaming Algorithms
  • Wavefront Path Tracing

Variance reduction

  • Multiple Importance Sampling
  • Resampled Importance Sampling
  • Bi-directional Path Tracing
  • Photon Mapping

Image Postprocessing

  • Bias
  • Filtering Techniques

Schedule

Period 3 Schedule

Week Date Lecture / Exams Working College Practical #1 Practical #2 Practical #3
6 Wed Feb 10
13:15-15:00
NO LECTURE        
Fri Feb 12
13:15-15:00
Lecture 1:
Introduction
       
7 Wed Feb 17
13:15-15:00
Lecture 2:
Acceleration Structures
 

Assignment 1
Basic framework

   
Fri Feb 19
13:15-15:00
Lecture 3:
The Perfect BVH
Working College #1
Fri 15:15-17:00
   
8 Wed Feb 24
13:15-15:00
Lecture 4:
Real-time Ray Tracing
     
Fri Feb 26
13:15-15:00
Lecture 5:
SIMD (optional)
Working College #2
Fri 15:15-17:00
   
9 Wed Mar 2
13:15-15:00
Lecture 6:
Light Transport
   

Assignment 2:

Acceleration structures

 
Fri Mar 4
13:15-15:00
Lecture 7:
Path Tracing
Working College #3
Fri 15:15-17:00
   
10 Wed Mar 9
13:15-15:00
Lecture 8:
Variance Reduction
     
Fri Mar 11
13:15-15:00
Lecture 9:
"Various"
Working College #4
Fri 15:15-17:00
   
11 Wed Mar 16
13:15-15:00
Lecture 10:
Questions: project, test exam
   

Assignment 3:

Specialize

Fri Mar 18
13:15-15:00
Lecture 11:
GPGPU (optional)
Working College #5
Fri 15:15-17:00
  Deadline:
Thu Mar 17, 23:59h
12 Retake Week

13 Wed Mar 30
13:15-15:00
Lecture 12:
GPU Path Tracing (1)
Working College #6
Wed 15:15-17:00
   
Fri Apr 1
13:15-15:00
NO LECTURE
NO WORKING COLLEGE
   
14 Wed Apr 6
13:15-15:00
Lecture 13:
GPU Path Tracing (2)
Working College #7
Wed 15:15-17:00
   
Fri Apr 8
13:15-15:00
Lecture 14:
BRDFs & Bidirectional

   
15 Wed Apr 13
13:15-15:00
Lecture 15:
STAR & Future Work, Recap
 
   
Fri Apr 15
13:15-15:00
Working College #8
Fri 13:00-17:00
   
16 Block 3 Exam Week Deadline:
Tue Apr 19, 23:59h

 

Downloads

LECTURE Slides

Lecture 1: Introduction & Whitted (updated)
Lecture 2: Acceleration Structures
Lecture 3: The Perfect BVH
Lecture 4: Real-time Ray Tracing
Lecture 5: SIMD Recap
Lecture 6: Light Transport
Lecture 7: Path Tracing
Lecture 8: Variance Reduction
Lecture 9: Various
Lecture 10: GPGPU recap
Lecture 11: GPU Ray Tracing (1)
Lecture 12: GPU Ray Tracing (2)
Lecture 13: BRDFs
Lecture 14: Grand Recap


FILES

gamma.gif for lecture 9
List of example questions for the final exam
List of example questions for the final exam, PART TWO.
 C++ template for VS2013 and VS2015: tmpl85.00a_2013.zip
C# template: template_Csharp.zip
C# OpenCL template: template_CL.zip



Practical Assignments

Organization

The course includes a software project that should be worked on in small groups. It is allowed to work on this alone, but be aware that the scope of the project is tuned for duos.

There are three milestones for this project:

  1.  Basics: during the first phase of the project, you will design and implement a framework with most of the low level functionality for the subsequent milestones. This includes scene management, ray generation, primitive intersection and simulation of optics.
  2.  Interactivity: based on the theory, you will transform the framework into an interactive renderer. The framework is extended with basic animation support.
  3.  For the final version of your project, you will be adding global illumination to the renderer. The default approach for this is a path tracer; however other options exist as well. You are free to chose your specific focus in this phase of the project, e.g. GPU rendering or advanced variance reduction.

The final grade for the software project is calculated as follows:

practical grade = (M2 + 2 * M3) / 3


(1) Ray Tracer

Tasks:

  • Setup a basic ray tracing framework for rendering a depth map for a hard-coded scene consisting of spheres and planes
  • Implement a complete Whitted-style ray tracer with reflection, refraction (Fresnel), absorption (Beer)
  • Add triangle mesh support and import meshes in *.obj format
 
(2) Interactive Ray Tracer

Tasks:

  • Add a bounding volume hierarchy
  • Add a scene graph
  • Add a top-level BVH
  • Add ray packet traversal

Full details in the official assignment 2 document.

 
(3) Global Illumination

Tasks (tentative):

  • Convert the Whitted-style ray tracer to a uni-directional path tracer
  • Add support for the MBVH
  • Add various variance reduction techniques

Full details in the official assignment 3 document.


Grading

GRADING

In order to pass the course, there are three requirements:

(i) You have to complete the practical project successfully, at least with a grade of 5.0. The project will be done as group work, but it must be clear that each individual student has contributed sufficiently.

(ii) You have to participate in a final exam and obtain a minimum score of 5.0.

(iii) The overall score is a weighted average of practicals (50%), and final exam (50%). The overall score must be at least 6.0 (after rounding) to pass the course.

RETAKES AND REQUIREMENTS

There will be an opportunity for a retake exam. In order to qualify, a grade of at least 4.0 is required in both areas (final exam, practicals). The result of the retake exam will be weighted by 50% and the original overall course score also by 50%. If the new grade resulting from this average is better than the original one, it will replace the original grade. Otherwise, the retake exam has no effect.

You have to contact the lecturer within two weeks after the final exam if you want to participate in the retake.

IMPORTANT: Due (recently refined) university regulations, you can only take the retake exam if you have both a high-enough but non-passing grade (i.e., at least 4.0 and less than 6.0).


Transfers from the previous lecture

Due to the restructuring of this course for the academic year 2015/2016, it is not possible to transfer partial achievements from previous year, i.e., the Advanced Graphics at UU from the academic year 2014-2015.

Literature & Links

LITERATURE

  • T. Whitted. An Improved Illumination Model for Shaded Display. Commun. ACM, 23(6):343–349, 1980.
  • Interactive Rendering with Coherent Ray Tracing, Wald et al., 2001.
  • Large Ray Packets for Real-time Whitted Ray Tracing, Overbeck et al., 2008.
  • Fast Agglomerative Clustering for Rendering, Walter et al., 2008.
  • Heuristics for Ray Tracing using Space Subdivision, MacDonald & Booth, 1990.
  • Distributed Ray Tracing, Cook et al., 1984.
  • The Rendering Equation, Kajiya, 1986.
  • Importance Sampling for Production Rendering, pages 5-38.
  • Ray tracing on programmable graphics hardware. Purcell et al., 2002.
  • Interactive k-d tree GPU raytracing. Horn et al., 2007.
  • Understanding the Efficiency of Ray Tracing on GPUs. Aila & Laine, 2009.
  • Getting Rid of Packets - Efficient SIMD Single-Ray Traversal using Multi-branching BVHs. Wald et al., 2008.
  • Megakernels Considered Harmfull: Wavefront Path Tracing on GPUs. Laine et al., 2013.
  • Theory for Off-Specular Reflection from Roughened Surfaces. Torrance & Sparrow, 1967.

Recommended literature

Physically Based Rendering, Second Edition - From Theory to Implementation, Pharr & Humphreys. Morgan Kaufmann, 2010. ISBN-10: 0123750792.

PAPERS & ONLINE MATERIALS

Lecture 1:

Lecture 2:

  • Benthin et al., Packet-based Ray Tracing of Catmull-Clark Subdivision Surfaces. 2007.
  • Knoll et al., Interactive Ray Tracing of Arbitrary Implicits with SIMD Interval Arithmetic. RT’07 Proceedings, Pages 11-18.
  • Hart et al., Ray Tracing Deterministic 3-D Fractals. In Proceedings of SIGGRAPH ’89, pages 289-296.
  • S. M. Rubin and T. Whitted. A 3-Dimensional Representation for Fast Rendering of Complex Scenes. In: Proceedings of SIGGRAPH ’80, pages 110–116.
  • J. Amanatides and A. Woo. A Fast Voxel Traversal Algorithm for Ray Tracing. In Eurographics ’87, pages 3–10, 1987.
  • A. S. Glassner. Space Subdivision for Fast Ray Tracing. IEEE Computer Graphics and Applications, 4:15–22, 1984.
  • K. Sung, P. Shirley. Ray Tracing with the BSP Tree. In: Graphics Gems III, Pages 271-274. Academic Press, 1992.
  • V. Havran, Heuristic Ray Shooting Algorithms. PhD thesis, 2000.
  • On building fast kD-trees for ray tracing, and on doing that in O(N log N), Wald & Havran, 2006.
  • Space-Tracing: a Constant Time Ray-Tracer, Kaplan, 1994.
  • Data Structures for Ray Tracing, Jansen, 1986.

Lecture 3:

  • Heuristics for Ray Tracing using Space Subdivision, MacDonald & Booth, 1990.
  • Early Split Clipping for Bounding Volume Hierarchies, Ernst & Greiner, 2007.
  • Spatial Splits in Bounding Volume Hierarchies, Stich et al., 2009.
  • On fast Construction of SAH-based Bounding Volume Hierarchies, Wald, 2007.
Lecture 4:
  • Interactive Rendering with Coherent Ray Tracing, Wald et al., 2001.
  • Large Ray Packets for Real-time Whitted Ray Tracing, Overbeck et al., 2008.
  • Fast Agglomerative Clustering for Rendering, Walter et al., 2008.

Lecture 5:

Lecture 6:

Lecture 7:

Lecture 8:

Lecture 9:

  • Development and testing of a color space (IPT) with improved hue uniformity, Ebner & Fairchild, 1998

Lecture 10:

Lecture 11:

  • Ray tracing on programmable graphics hardware. Purcell et al., 2002
  • Interactive multi-pass programmable shading. Peercy et al., 2000
  • Accelerated ray tracing system. Fujimoto et al., 1986
  • KD-Tree Acceleration Structures for a GPU Raytracer. Foley & Sugerman, 2005
  • Interactive k-d tree GPU raytracing. Horn et al., 2007
  • Stackless KD-tree traversal for high performance GPU ray tracing. Popov et al., 2007
  • Ray tracing with rope trees. Havran et al., 1998
  • Realtime ray tracing on GPU with BVH-based packet traversal. Günther et al., 2007
  • Real-time Ray Tracing Part 2. Smash / Fairlight, 2013.
  • GPU Gems 2, chapter 42: Conservative Rasterization. Hasselgren et al., 2005
  • The Basics of GPU Voxelization. Masaya Takeshige, 2015
  • Bokeh depth of field – going insane! part 1. Bart Wroński, 2014

Lecture 12:

  • Understanding the Efficiency of Ray Tracing on GPUs. Aila & Laine, 2009
  • Understanding the Efficiency of Ray Tracing on GPUs – Kepler & Fermi addendum. 2012
  • Latency Considerations of Depth-first GPU Ray Tracing. Guthe, 2014
  • Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays. Dammertz et al., 2008
  • Getting Rid of Packets - Efficient SIMD Single-Ray Traversal using Multi-branching BVHs. Wald et al., 2008
  • Megakernels Considered Harmfull: Wavefront Path Tracing on GPUs. Laine et al., 2013
  • Improving SIMD Efficiency for Parallel Monte Carlo Light Transport on the GPU. Van Antwerpen, 2011
  • The Brigade Renderer: A Path Tracer for Real-time Games. Bikker & Van Schijndel, 2012.
  • Xorshift RNGs. Marsaglia, 2003.

Lecture 13:

  • Illumination for Computer Generated Images. Bui-Tuong Phong, 1975
  • Phong Normalization Factor Derivation. Farbrausch.
  • Using the Modified Phong Reflectance Model for Physically Based Rendering. Lafortune & Willems, 1994
  • Theory for Off-Specular Reflection from Roughened Surfaces. Torrance & Sparrow, 1967

News Archive

Old posts

Mar 30:

  • Slides for lecture 11 on GPU ray tracing are now available.

Mar 23:

  • C++ OpenCL template is available via the forum. Support will also be provided there, if needed.

Mar 18:

  • Grades for assignment 2 can be viewed by clicking this link.

Mar 18:

Mar 14:

Mar 14:

Mar 11:

Mar 9:

  • Lecture 8 slides on variance reduction now available for download.
  • Schedule updated: Wednesday March 16 is now dedicated to an example exam and the second assignment.
  • Literature list updated in preparation of example exam.

Mar 7:

  • Updated lecture 7 slides with additional path tracing resources (last slide).
  • Small fix to Snell / Fresnel slides in lecture 1 slides (vector D reversed in dot).
  • Updated Snell / Fresnel demo application, get it here.

Mar 4:

  • Path tracing slides (lecture 7) now available.

Mar 2:

  • Slides for lecture 6 now online.

Feb 26:

  • Slides for lecture 5 (SIMD recap) now online.

Feb 24:

  • Details on assignment 2 now available.
  • Slides for lecture 4 have been uploaded.
  • Schedule changed: SIMD recap now on Friday Feb 26!

Feb 22:

Feb 19:

Feb 18:

Feb 12:

Dec 3:

  • Initial page for academic year 2015/2016.