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

Algorithms for Highly Complex Virtual Scenes

Lecture, Winter Term 2016/17

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: www.padrend.de

Thanks to Claudius, Ralf, Benjamin and Sascha

Inhalt

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

Prerequisites

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.

Lecturer

Dates

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

Examination

  • 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.
  • 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 two arbitrary exercises. The student should demonstrate that he is familiar with the problem definition and the solution of the exercise.
  • The exercise chat takes place at the end of the lecture.

Tutorials

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 koaLA. 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.

Literature

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.