Home > Research Groups > Algorithms and Complexity > Teaching > Algorithms for Highly Complex Virtual Scenes

Algorithms for Highly Complex Virtual Scenes

Lecture, Winter Term 2021/22

Virtual scene with 6 billion triangles

click to enlarge


Walkthrough systems provide you to view and walk through 3D virtual scenes. Applications are architectural programs, simulations, games and many more. The efficiency of real-time rendering algorithm is crucial for a fast and smooth rendering of 3D virtual scenes in a Walkthrough System. There are various approaches to reduce highly complex geometric 3D data and to provide a real-time rendering of the data. In the lecture we will learn elementary algorithmic approaches from various fields, e.g., visibility-culling, simplification, level of detail, image-based rendering and others.

  • Introduction: Walkthrough problem
  • Data Structures: kd-tree, BSP-tree, Octree, Loose-Octree
  • Level of Detail: Adaptive LOD Management, Mesh Simplification, Progressive Meshes
  • Visibility Culling: View Frustum Culling, Potentially Visible Sets, Dynamic Computation of PVS, Hierarchical Z-Buffer, Hierarchical Occlusion Maps, Aspect-Graph
  • Replacement: Color-Cubes, Randomized Z-Buffer, Hierarchical Image Caching
  • Parallel Rendering: Classification and modeling, parallel rendering as sorting problem, hybrid sort-first / sort-last rendering

The lecture content based on chapters from books, which can be found in the literature hints and on original works, which are given. In addition to the slides the original works are recommended for reworking. Books can be found in the course reserve collection.


Basic knowledge of computer graphics is advantageous but not essential.



  • The lecture times can be found in PAUL.
  • The tutorials begin in the second week of lectures.


  • New System: Focus Areas: 2. Algorithm Design, 6 ECTS Credits, V3 + Ü2 SWS
  • Old System: Modules: III.2.1 Algorithms I (MuA), III.2.2 Algorithms II, 4 ECTS Credits, V2 + Ü1 SWS (MuA)


  • The examinations will be oral exams.
  • The content covers all exercises and all lectures.

Examination Requirements: "Studienleistung"

  • Every week you will get a homework sheet in PANDA.
  • The homework will be solved in groups of 2-5 persons.
  • The homework sheet is rated. Plagiarism does not receive any marks. You must achieve 40% of the points to be able to take part in the exam. In this way you will receive the course achievement (Studienleistung).

Lecture and Tutorials

Lectures and exercises will be held in person.


The following literature deals with methods and algorithms for the rendering of three-dimensional data. The list is only an excerpt of the available literature.

  • Real-Time Rendering; Tomas Akenine-Möller, Eric Haines; AK Peters, 2002.
  • Level of Detail for 3D Graphics; David Luebke, Martin Reddy, Jonathan D. Cohen; Morgan Kaufmann Publishers, 2002.
  • Algorithmen in der Computergraphik; Thomas Rauber; Teubner, 1993.
  • Wavelets for Computer Graphics: Theory and Applications; Eric Stollnitz, David H. Salesin, Anthony D. DeRose; Morgan Kaufmann Publishers, 1996.
  • Graphic Gems; Andrew S. Glassner; Academic Press; 1990.
    Also volumes 2 to 5 are published.
  • Game Programming Gems; Mark DeLoura; Charles River Media; 2000.
    Also volumes 2 to 6 are published.

Computational Geometry

Methods of the algorithmic geometry are presented in the lecture only as far as they are required for the rendering algorithms (Octrees, BSP-trees, kD-trees, ...). The data structures can be found, for example, in the following books:

  • Computational Geometry - Algorithms and Applications; Mark de Berg, Marc de Kreveld, Mark Overmars; Springer Verlag, 2000.
  • Computational Geometry in C; Joseph O'Rourke; Cambridge University Press, 1998.
  • Algorithmic Geometry; Jean-Daniel Boissonnat, Herve Bronniman;Cambridge University Press, 1998.
  • Algorithmische Geometrie Grundlagen, Methoden, Anwendungen; Rolf Klein; Springer Verlag, 2005.

General principles of computer graphics

  • 3D Computer Graphics; Alan Watt; Addison Wesley, 1999.
  • Computer Graphics, Principles and Practice; James Foley, Andries van Dam, Steven Feiner, John Hughes; Addison Wesley, 1995.
  • Computer Graphics; Donald Hearn, M. P. Baker; Prentice Hall, 2003.