Startseite > Fachgruppen > Algorithmen und Komplexität > Lehre > Algorithmen für hochkomplexe Virtuelle Szenen

Algorithmen für hochkomplexe Virtuelle Szenen

Inhalt

Walkthrough-Systeme erlauben das Betrachten und Durchlaufen von virtuellen 3D-Szenen und finden Anwendung bspw. in Architekturprogrammen, Simulationen oder Spielen. Die Effizienz von Echtzeit-Rendering Algorithmen ist entscheidend für eine flüssige und schnelle Darstellung der virtuellen 3D-Szenen in einem Walkthrough-System. Es gibt verschiedene Ansätze, um hochkomplexe geometrische 3D-Daten zu reduzieren und eine Darstellung der Daten in Echtzeit zu erreichen. Wir werden in der Vorlesung elementare algorithmische Ansätze aus den Bereichen Visibility-Culling, Simplification, Level of Detail, Image-Based Rendering und weitere kennenlernen.

  • Einleitung: Walkthrough-Problem
  • Datenstrukturen: kd-Baum, BSP-Baum, Octree, Loose-Octree
  • Level of Detail: Adaptives LOD-Management, Mesh Simplification, Progressive Meshes
  • Visibility Culling: View Frustum Culling, Potentially Visible Sets, Dynamische Berechnung der PVS, Hierarchischer Z-Buffer, Hierarchische Occlusion Maps, Aspect-Graph
  • Replacement: Color-Cubes, Randomisierter Z-Buffer, Hierarchical Image Caching
  • Paralleles Rendern: Klassifizierung und Modellierung, Paralleles Rendering als Sortierproblem, Hybrides Sort-First/Sort-Last-Rendering

Virtuelle Szene mit 6 Milliarden Dreiecken

Berechnungen zur Approximation der virtuellen Szene (Blue Surfels)

Berechnungen zur Sichtbarkeit (Szeneneigenschaften)

Berechnungen zur Sichtbarkeit (Hierarchie von Objekten)

Unser Rendering-System zur Implementierung und Evaluierung der Algorithmen: www.padrend.de

Voraussetzungen

Die für diese Veranstaltung notwendigen Grundlagen werden bei jedem Themengebiet kurz angesprochen. Es wird jedoch keine grundlegende Einführung in die Computergrafik gegeben, so dass es von Vorteil ist die Vorlesungen Computergrafik I/II von Gitta Domik gehört zu haben.

Modulinformation

  • MuA: III.2.1 Algorithmen I, III.2.2 Algorithmen II
  • V2 + Ü1 SWS (Kontaktzeit)
  • 4 ECTS Credits (Workload)

Dozent

  • Matthias Fischer

Termine

  • Die Vorlesungszeiten sind in PAUL zu finden.
  • Die Übungen beginnen in der zweiten Vorlesungswoche

Scheinerwerb

  • Prüfungsgebiet: III.2.1 Algorithmen I (MuA), III.2.2 Algorithmen II, 4 ECTS Credits, V2 + Ü1 SWS (MuA).
  • Die Prüfungen sind mündliche Einzelprüfungen, deren Inhalt sich auf Vorlesung und Übung bezieht.
  • Prüfungsvorleistung ist ein regelmäßiger Übungsbesuch und ein Übungsgespräch über den Inhalt der Übungen. Das Übungsgespräch dauert ca. 5-10 Minuten und wird über den Inhalt von zwei in den Übungen behandelten Übungsaufgaben geführt. In dem Gespräch soll der Studierende nachweisen, dass er mit der Problemstellung und Lösung der Übungsaufgabe vertraut ist.
  • Das Übungsgespräch findet gegen Ende der Vorlesung statt.

Übungen

Die Übungen werden vorwiegend als Präsenzübungen abgehalten: Am Anfang der Übungsstunde werden wir ein Übungsblatt mit 1-2 Aufgaben verteilen und anschließend bearbeiten.

Vorlesungsmaterialien

Die Vorlesung wird überwiegend mit Folien durchgeführt, die in koala erhältlich sind. Der Vorlesungsinhalt orientiert sich an Kapiteln aus Büchern, die unter der Literatur zu finden sind und an Originalarbeiten, die angegeben werden. Sie empfehlen sich daher neben den Folien und eigenen Mitschriften zur Nacharbeitung. Bücher sind im Semesterapparat zu finden.

Literatur

Die folgende Literatur behandelt Methoden und Algorithmen zur Darstellung dreidimensionaler Daten. Die Liste ist nur ein Auszug der vorhandenen Literatur.

  • 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.
    Es sind weiter die Bände II bis V erschienen.
  • Game Programming Gems; Mark DeLoura; Charles River Media; 2000.
    Es sind weiter die Bände 2 bis 6 erschienen.

Algorithmische Geometry

Methoden der Algorithmischen Geometrie werden in der Vorlesung nur soweit vorgestellt, wie sie für die Renderingalgorithmen benötigt werden (Octrees, BSP-Trees, kD-Trees, ...). Die Datenstrukturen können bspw. in folgenden Büchern gefunden werden:

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

Allgemeine Grundlagen der Computergrafik

  • 3D Computer Graphics; Alan Watt; Addison Wesley, 1999. (Gibt es auch in einer deutschen Übersetzung.)
  • 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.