INFOMOV Optimization and Vectorization

Academic year 2025/26 -- period 4

Format and Organization

Overview

INFOMOV is a practical course on optimization: the art of improving software performance, without affecting functionality. We apply high level and low level optimizations, in a structured manner. Especially for the low level optimizations, we must intimately understand the hardware platform (CPU, GPU, memory, caches) and modify our code to use it efficiently.

Vectorization: Modern processors achieve their performance levels using parallel execution. This happens on the thread level, but also on the instruction level. Being able to produce efficient vectorized code is an important factor in achieving peak performance.

GPGPU: Graphics processors employ a streaming code execution model, taking vectorization to extremes, both in the programming model and the underlying architecture. Leveraging GPU processing power is an important option when optimizing existing code.

Context: Optimization is a vital skill for game engine developers, but also applies to other fields.

Prerequisites

This course builds on all of the prerequisites of the MSc Game and Media Technology programme. In particular:

• Mathematics: integral and differential calculus, linear algebra, and probability theory.
• Data structures and algorithms: tree data structures, complexity of algorithms, big-O notation.
• Computer graphics: bachelor-level knowledge of computer graphics, specifically experience developing a Whitted-style ray tracer from scratch. If you don't have this prior graphics experience, you should familiarize yourself before the practical assignments start by working through a tutorial such as the Ray Tracing in One Weekend series.
• Programming: fluency in an appropriate language such as C# or C++. For optimal performance and certain low level aspects, C++ is recommended. It would require a lot of additional time to familiarize yourself with C++ during the course. Other appropriate programming languages may be agreed with the lecturer on an individual basis.
• Good to have, but not absolutely required: basic experience with graphics APIs (e.g. OpenGL / DirectX / Vulkan). No specific graphics API is required for the assignments.

Intended Learning Outcomes (ILOs)

Students will:

1. Understand the physical basis of light transport simulation
2. Have knowledge of the main ray tracing-based rendering methods
3. Have knowledge of acceleration structures for ray-scene intersection and how to construct an efficient BVH for static and dynamic scenes
4. Have knowledge of the characteristics of GPUs related to ray tracing and be aware of algorithms that specifically target these processors
5. Understand Monte Carlo and variance reduction techniques, specifically the application of probability density functions in the context of light transport
6. Have knowledge of state-of-the-art developments in the field of physically based rendering

Links

• Teams: discussion, collaboration, support, slides, assignments, and lecture streams and recordings
• Brightspace: practical assignment submissions, grades, and feedback
• Course catalog: official (centrally managed) course information
• This page: 'static' course information

Lecturer

Angelos Chatzimparmpas (a.chatzimparmpas@uu.nl)

Lectures

• Lectures and labs are in BBG 201 - but check the schedule below or MyTimetable / the MyUU app for changes
• Two lectures per week: Tuesday 10:00 - 11:45, Thursday 13:15 - 15:00
• Lecturer-supervised discussion / support labs: Tuesday 9:00 - 9:45 (optional) and 12:00 - 12:45, Thursday 15:15 - 17:00

Lectures will be streamed live on Teams for students who cannot be physically on campus. Lecture recordings will be made available for later reference. Slides will be made available in advance.

Assessment

• Practical assignment 1 (ILOs 2 and 3)
• Practical assignment 2 (ILOs 2 and 3, and others depending on your specific project choice)
• Final Exam (ILOs 1-6)

Extensions and Exceptions

• Skip an exam: Follow the procedure to deregister for this exam and apply for a retake. (This page describes the procedure for students on GSNS programmes only. Your programme may vary.)
• Postpone a practical assignment deadline: Email the course coordinator with a brief reason (no sensitive details are needed) and a proposed new deadline date and time.

You are not automatically eligible for a retake if you miss a deadline or exam without following the correct procedure.

Topics

Tentative Schedule

Practical Assignments

This course has two practical assignments that take the form of small projects, developing parts of an advanced ray tracing-based renderer. You may work on the practical assignments in groups of two students. Only if you cannot find a partner, you may do the practical assignments by yourself, but the expected magnitude of the project remains the same. The practical assignments have as outcomes a ray tracing-based renderer with a relevant advanced feature, which make great additions to your portfolio.

1. Acceleration structures: You will (implement and) compare the performance of at least two acceleration structures in a ray tracing-based renderer.
2. Recent research: You will implement a recent research paper in a ray tracing-based renderer. You are free to choose your specific focus from a list of suggested papers.

For both practical assignments you may start from a template or an existing open-source renderer. One possible C++ template is available on GitHub. Other good open-source renderers include PBRT (C++) or Mitsuba (C++ core with Python bindings). Other interesting renderers: Lighthouse 2, VoxelWorld template.

Implementing a renderer from scratch is also allowed, but it's a considerable effort that will not contribute towards the grade. It will take precious time away from the graded parts of the assignment.

AI index: Level 3 - AI use allowed for editing and improving your own work, but not for generating parts of the assignment solution. AI tools tend to produce code that they have copied ("learned") from online sources. If that's more than a few lines of code, that will likely be detected as plagiarism and will be treated as such.

Grading

In order to pass the course, you must participate in all assessments to receive a grade:

• Practical assignment 1 grade: P1 (18.75%)
• Practical assignment 2 grade: P2 (18.75%)
• Practical assignment 3 grade: P3 (37.50%)
• Exam grade: E (25.00%)
• Final grade: F = (3P + E) / 4
• Additional requirement: You must score at least 5.0 for the exam (before rounding) to pass this course.

Retakes

To qualify for a retake, the final grade must be at least 4 (before rounding). You may repair your final grade by redoing one of the three assignments, or the exam. Exact terms will be discussed individually.

Transfers from a previous year

If you are repeating this course, it may be possible to transfer only your previous practical assignment grades to this academic year. Contact the lecturer to request this. You must always redo the exam.

Literature

Books (available for free online)

• Pharr et al. 2023. Physically Based Rendering: From Theory to Implementation, Fourth Edition. MIT Press.
• Haines and Akenine-Möller 2019. Ray Tracing Gems: High-Quality and Real-Time Rendering with DXR and Other APIs. Apress.
• Marrs et al. 2021. Ray Tracing Gems II: Next Generation Real-Time Rendering with DXR, Vulkan, and OptiX. Apress.

Papers and Blogs

• Aila and Laine 2009. Understanding the efficiency of ray traversal on GPUs. In Proc. High Performance Graphics 2009, 145-149.
• Benthin et al. 2017. Improved two-level BVHs using partial re-braiding. In Proc. High Performance Graphics 2017, 1-8.
• Bikker 2019. Probability theory for physically based rendering. Blog post series.
• Bikker 2019. Wavefront path tracing. Blog post.
• Bikker 2022. How to build a BVH. Blog post series.
• Bitterli et al. 2020. Spatiotemporal reservoir resampling for real-time ray tracing with dynamic direct lighting. In Proc. ACM SIGGRAPH 2020, ACM Transactions on Graphics 39(4):148.
• Cook et al. 1984. Distributed ray tracing. ACM SIGGRAPH Computer Graphics 18(3):137-145.
• Ganestam et al. 2015. Bonsai: Rapid bounding volume hierarchy generation using mini trees. Journal of Computer Graphics Techniques 4(3).
• Horn et al. 2007. Interactive k-D tree GPU raytracing. In Proc. Symposium on Interactive 3D Graphics and Games 2007, 167-174.
• Kajiya 1986. The rendering equation. ACM SIGGRAPH Computer Graphics 20(4):143-150.
• Laine et al. 2013. Megakernels considered harmful: Wavefront path tracing on GPUs. In Proc. High Performance Graphics 2013, 137-143.
• Lauterbach et al. 2009. Fast BVH construction on GPUs. Computer Graphics Forum 28(2):375-384.
• MacDonald and Booth 1990. Heuristics for ray tracing using space subdivision. The Visual Computer 6:153-166.
• Meister et al. 2021. A survey on bounding volume hierarchies for ray tracing. Computer Graphics Forum 40(2):683-712.
• Overbeck et al. 2008. Large ray packets for real-time Whitted ray tracing. In Proc. IEEE Symposium on Interactive Ray Tracing 2008, 41-48.
• Purcell et al. 2002. Ray tracing on programmable graphics hardware. In Proc. ACM SIGGRAPH 2002, ACM Transactions on Graphics 21(3):703-712.
• Torrance and Sparrow 1967. Theory for off-specular reflection from roughened surfaces. Journal of the Optical Society of America 57(9):1105-1114.
• van Antwerpen 2011. Unbiased physically based rendering on the GPU. Master thesis, TU Delft.
• Veach 1997. Robust Monte Carlo methods for light transport simulation. PhD thesis, Stanford University.
• Vorba et al. 2019. Path guiding in production. ACM SIGGRAPH 2019 Course Notes.
• Wald et al. 2001. Interactive rendering with coherent ray tracing. Computer Graphics Forum 20(3):153-165.
• Wald et al. 2008. Getting rid of packets - Efficient SIMD single-ray traversal using multi-branching BVHs. In Proc. IEEE Symposium on Interactive Ray Tracing 2008, 49-57.
• Walter et al. 2007. Microfacet models for refraction through rough surfaces. In Proc. Eurographics Symposium on Rendering 2007, 195-206.
• Walter et al. 2008. Fast agglomerative clustering for rendering. In Proc. IEEE Symposium on Interactive Ray Tracing 2008, 81-86.
• Whitted 1980. An improved illumination model for shaded display. Communications of the ACM 23(6):343-349.

Additional materials will be mentioned in the lecture slides. The university WiFi gives you free access to many pay-walled publications.