Home > Research Groups > Algorithms and Complexity > Teaching > Archive > 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
Algorithmen für hochkomplexe Virtuelle Szenen
Algorithmen für hochkomplexe Virtuelle Szenen
Algorithmen für hochkomplexe Virtuelle Szenen

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

  • Vorlesung (V2): Di., 16:15-17:45, F 1.110 Matthias Fischer
  • Übung (Ü1): Mo., 10:00-10:45, F1.110 Matthias Fischer
  • Übung (Ü1): Mi., 11:00-11:45, F1.110 Matthias Fischer
  • Erste Vorlesung beginnt am 3.4.2012, die erste Übung am 9.4.2012
  • Zur Vorlesung ist eine Anmeldung bei PAUL erforderlich.

Scheinerwerb

  • Prüfungsgebiet: III.2.1 Algorithmen I (MuA), III.2.2 Algorithmen II, 4 ECTS Credits, V2 + Ü1 SWS (MuA) Weitere Informationen
  • http://www.cs.uni-paderborn.de/studierende/studiengaenge.htmlDie 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 einer in den Übungen behandelten Übungsaufgabe geführt. In dem Gespräch soll der Studierende nachweisen, dass er mit der Problemstellung und Lösung der Übungsaufgabe vertraut ist. Nur wenn dieser Nachweis gelingt, kann der Studierende an der Prüfung teilnehmen. Das Übungsgespräch findet gegen Ende der Vorlesung statt.
  • Die Prüfungsnummer ist 5777, siehe auch Prüfungstermine.
  • Beachten Sie die Hinweise zu Prüfungsanmeldung auf den Seiten des Prüfungswesen des Prüfungssekretariats.

Ü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 auf dieser Webseite 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 ddd 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.