Startseite > Fachgruppen > Algorithmen und Komplexität > Lehre > Algorithms for Highly Complex Virtual Scenes

Algorithms for Highly Complex Virtual Scenes

Lecture, Winter Term 2018/19

Virtual scene with 6 billion triangles

click to enlarge

Computations for the Approximation of a Virtual Scene (Blue Surfels)

click to enlarge

Visibility Computations (Scene Properties, and Hierarchy of Objects)

click to enlarge

Our rendering system for the implementation and evaluation of algorithms:

Thanks to Claudius, Ralf, Benjamin and Sascha


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 basics necessary for this event are briefly addressed in every topic. There is, however, no basic introduction to computer graphics, so it is advantageous to attend computer graphics lectures of Gitta Domik.



  • The lecture times can be found in PAUL.
  • The exercises 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 are oral examinations, the content based on the lecture material and the tutorials.

Examination Requirements: "Studienleistung"

  1. Required for the examination is a so-called exercise chat about the contents of the exercises. The exercise chat takes about 10-15 minutes and covers the contents of arbitrary exercises. The student should demonstrate that he is familiar with the problem definition and the solution of the exercise.
  2. You have to pass two exercise chats: The first one takes place in the middle of the lecture and the second one takes place close to the end of the lecture.
  3. In order to get practical experience in graphics programming, you have to implement a small programming task. To do this, you implement a simple small renderer in groups of 3-5 students. The renderer is implemented with the PADrend system, you have to learn the PADrend-system yourself. In the last lecture (February 1, 2019), you will present your implementation in a short talk (20 min).
  4. In order to get the examination requirement "Studienleistung" you have to pass the two exercise chats and successfully implement and present your programming task.

Examination Appointment

  1. Use PAUL's regular examination periods to register for an exam.
  2. You can do the exam individually anytime. To make an appointment for an examination, please contact Mrs. Petra Schäfermeyer. Fill out the form you find here and send the completed form by e-mail to Mrs. Petra Schäfermeyer. It is recommended to make an appointment approx. 3 weeks before the exam.


The tutorials are done in face-to-face style: At the beginning of the exercise, we distribute an exercise sheet with 1-2 exercises and then we discuss solutions.

Lecture materials

The lecture mainly provides slides, which are available in PANDA. 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.


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.