Algorithmen für Computerspiele

  Organisatorisches    
SS 2010,  (Sonstige Veranstaltung),   / Softwaretechnik
2S (Vorlesungen + Übungen)
Dozenten: Daniel Weiskopf   (Homepage)
Tutoren: Sven Bachthaler  
Michael Krone  
Markus Üffinger  
Termine: Mo   13:10  -  14:00    in 0.363   Seminar
  Wichtige Hinweise    

Die Vorbesprechung und Themenvergabe findet am Dienstag den 16. Februar 2010 um 13:00h in Raum 0.363 statt. (siehe Veranstaltungsankündigung)

Die Folien der Vorbesprechung können → hier heruntergeladen werden, die Themen- und Terminliste wurde hinzugefügt (s.u.). Die Referenzen zu den einzelnen Themen werden in Kürze bekannt gegeben.

Terminänderung!

Anders als in der Vorbesprechung angekündigt findet der erste Vortragstermin am 19.4.2010 doch statt (siehe Themenliste unten).
Die Termine am 31. Mai und am 7. Juni 2010 fallen aus!

  Beschreibung    

In diesem Seminar sollen Verfahren und Methoden behandelt werden, wie sie in modernen Computerspielen zum Einsatz kommen. Computer- oder Videospiele zeichnen sich durch ständig verbesserte graphische Darstellungen aus und versetzen die Spieler in realistische und/oder virtuelle Welten.

Ein entscheidender Punkt bei der Realisierung ist eine hohe Verarbeitungsgeschwindigkeit für die graphische Darstellung, Animation, Simulation physikalisches Vorgänge und künstliche Intelligenz. In diesem Seminar sollen entsprechende Algorithmen aus der 3D-Computergraphik und verwandten Gebieten vorgestellt und diskutiert werden. Besonderes Augenmerk wird auf Techniken zur Echtzeitgraphik und auf Hardwareunterstützung gelegt.

Die Themen (Bekanntgabe folgt) werden aus den folgenden Bereichen gewählt:

  • Starrkörperphysik und Kollisionserkennung
  • Rämliche Datenstrukturen
  • Computeranimation und Motion Capturing
  • Künstliche Intelligenz, Wegfindungsalgorithmen
  • Multiplayer-Technologien
  • Hierarchische und adaptive Verfahren
  • Prozedurale Modellierung
  • GPU-Architekturen und Shader-Programmierung
  • Licht und Schatten
  • Volumetrische Effekte
  • Spezialeffekte und Post-Processing mit Grafikhardware
  • 3D Game Engines
  Literatur    
1.  Computer Graphics, James Foley, Andries van Dam, Steven Feiner, John Hughes, 1995
2.  OpenGL programming guide, Mason Woo and others, Addison-Wesley, 1999
3.  3D Game Engine Design, David H. Eberly, Morgan Kaufman, 2001
4.  Game Design, X-Games, Marc Saltzmann, 2. Auflage, München, 2000
5.  Graphics Gems I-V, Various, Academic Press
6.  Game Programming Gems, Marc DeLoura, Charles River Media
7.  Introduction to 3D Game Programming with DirectX 9.0c A Shader Approach, Frank D. Luna, Wordware Publishing Inc., 2006
8.  OpenGL Shading Language, Randi J. Rost
  Sonstiges    
Ausarbeitung und Vortrag

Der Vortrag sollte vom Umfang etwa 30-35 Minuten lang sein und einen detaillierten Einblick in das jeweilige Thema geben. Die angegebenen meist englischsprachigen Referenzen dienen hierbei als Grundlage und können/sollen in Absprache mit dem Betreuer je nach Bedarf um weitere Referenzen erweitert werden. Dabei sollen die für das jeweils vorgetragene Thema wesentlichen Aspekte der Referenzen herausgearbeitet und im Detail erklärt werden. Nicht im Schwerpunkt des Vortrags liegende Teilaspekte können sehr knapp behandelt oder nur am Rande erwähnt werden.

Dasselbe gilt natürlich für die schriftliche Ausarbeitung, wobei hier mehr ins Detail gegangen werden sollte. Die Ausarbeitung sollte (inklusive Abbildungen) insgesamt etwa 10-15 Seiten (10pt, einfacher Zeilenabstand) umfassen.
Eine reine Übersetzung der Vorlage(n) als Ausarbeitung wird nicht akzeptiert. Die Ausarbeitung muss in eigenen Worten formuliert werden!

Für die Ausarbeitung steht eine LaTeX-Vorlage mit UTF-8-Unterstützung und eine mit latin-1 zur Verfügung (Abgaben in MS Word werden nicht akzeptiert!), für die Erstellung der Vortragsfolien stehen Vorlagen sowohl für OpenOffice als auch PowerPoint zur Verfügung.

   Abgabefristen    

Spätestens drei Wochen vor dem eigenen Vortrag ...
... hält der Vortragende Rücksprache mit den Betreuern über die Gliederung und Zusammenfassung des Vortrages.
... reicht der Teilnehmer ein HTML-Dokument bei den Betreuern ein, das als Vortragsankündigung dient und dem Leser einen Einstieg in das Thema ermöglicht. Das Dokument sollte eine Zusammenfassung des Vortrags und Links zu weiteren Quellen insbesondere den behandelten Veröffentlichungen bieten, damit die anderen Seminarteilnehmer sich auf den Vortrag vorbereiten können. Eine Vorlage findet sich hier.
Von Microsoft Word generierte HTML-Dateien werden abgelehnt.

Spätestens zwei Wochen vor dem eigenen Vortrag ...
... bespricht der Vortragende die ausgearbeiteten Vortrags-Folien mit dem Betreuer. Eine Vorlage für OpenOffice findet sich hier und für PowerPoint hier.

Direkt nach dem Vortrag ...
... gibt der Vortragende seine Folien bei den Betreuern in elektronischer Form ab (Source-File und pdf-Datei).

Innerhalb von 4 Wochen nach dem Vortrag und spätestens bis zum Vorlesungsende (was früher eintritt!)...
... gibt der Vortragende seine Ausarbeitung in elektronischer Form (Source-File und pdf-Datei) bei den Betreuern ab.
   Themen    
0. Titel: Vergleich von 3D Game Engines
Datum: 19. April 2010
Bearbeitung: Zhen Peng
Betreuung: Sven Bachthaler / Michael Krone
Referenzen:
[Kommerzielle Game Engines]
   Epic Games: Unreal Engine
   Crytek: CryENGINE
   GarageGames: Torque 3D Engine
[Freie Game Engines]
   OGRE
   Irrlicht
 
1. Titel: Physik
Datum: 26. April 2010
Bearbeitung: Tobias Schnabel
Betreuung: Markus Üffinger
Referenzen:
[Allgemein] Game Physics, GPGPU: Physics Simulation
[GPU Physics APIs] NVidia PhysX, ATI Havok
[Rigid Body Physics] GPU Gems 3: Real-Time Rigid Body Simulation on GPUs
 
2. Titel: KI
Datum: 03. Mai 2010
Bearbeitung: Manuel Bischof
Betreuung: Sven Bachthaler
Referenzen:
Enhancing Gameplay Challenges for Artificial Intelligence in Digital Games,
Expressive AI Games and Artificial Intelligence,
It Knows What You’re Going To Do Adding Anticipation to a Quakebot
 
3. Titel: Multiplayer-Technologien
Datum: 10. Mai 2010
Bearbeitung: Alexander Beljawski
Betreuung: Sven Bachthaler
Referenzen:
Networking for Games 101,
Dead Reckoning: Latency Hiding for Networked Games,
Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization
 
4. Titel: Animation und Motion Capturing
Datum: 17. Mai 2010
Bearbeitung: Jordanis Andreanidis
Betreuung: Michael Krone
Referenzen:
[Keyframe Animation & Inverse Kinematik]
   Funkhouser: Princeton University Lecture Slides
   Keyframing
[Motion Capturing]
   xsense, animazoo (Hersteller)    Bacherlorarbeit Kai Kajus Noack
[Prozedurale Animation] Cenydd, Teahan: "The Dynamic Animation of Ambulatory Arthropods" (Proceedings of TPCG 2007)
 
5. Titel: Räumliche Datenstrukturen - fällt aus!
Datum: 31. Mai 2010
Bearbeitung: faellt aus
Betreuung: Markus Üffinger
Referenzen:
[Basics, Raumaufteilung] Kd-Trees, BSP Trees, Quadtree, Octree
[Visibility Surveys] A Survey of Visibility for Walkthrough Applications
GPU Gems 2: Hardware Occlusion Queries Made Useful
 
6. Titel: Hierarchische und adaptive Verfahren - fällt aus!
Datum: 7. Juni 2010
Bearbeitung: faellt aus
Betreuung: Markus Üffinger
Referenzen:
[Buch] Level of detail for 3D graphics (Luebke, David), GPU Gems 3: Generic Adaptive Mesh Refinement
[Fokus Terrain Rendering] VTerrain.org, Survey on semi-regular multiresolution models for interactive terrain rendering
[GPU] DirectX 11 - Tesselation (C't Artikel, link coming soon)
 
7. Titel: Prozedurale Modellierung
Datum: 14. Juni 2010
Bearbeitung: Katrin Scharnowski
Betreuung: Michael Krone
Referenzen:
[Modellierung von Pflanzen]
   Palubicki et al.: "Self-organizing tree models for image synthesis" (ACM Transactions on Graphics 28, 2009)
   Algorithmic Botany, Biological Modeling and Visualization research group, University of Calgary
[Modellierung von Städten & Gebäuden] Mueller, Wonka, Haegler, Ulmer, Van Gool: "Procedural Modeling of Buildings" (ACM SIGGRAPH 2006)
[Modellierung von Terrains]
   Geiss: "Generating Complex Procedural Terrains Using the GPU" (GPU Gems 3)
   Olsen: "Realtime Procedural Terrain Generation"

 
8. Titel: GPU Architekturen und Shader-Programmierung
Datum: 21. Juni 2010
Bearbeitung: Frank Steimle
Betreuung: Sven Bachthaler
Referenzen:
Shader Grundlagen
nVIDIA Fermi Architektur
From Shader Code to a Teraflop: How a Shader Core works
A Closer Look at GPUs
 
9. Titel: Licht und Schatten
Datum: 28. Juni 2010
Bearbeitung: Oleg Martin
Betreuung: Sven Bachthaler
Referenzen:
High-Quality Adaptive Soft Shadow Mapping,
Programming Vertex, Geometry, and Pixel Shaders,
 
10. Titel: Raycasting Techniken
Datum: 5. Juli 2010
Bearbeitung: Florian Fieber
Betreuung: Michael Krone
Referenzen:
[Grundlagen Ray Casting] Funkhouser: Princeton University Lecture Slides
[Bump Mapping] Tutorial: Bump Mapping using GLSL
[Relief Mapping] Oliveira, Bishop, McAllister: "Relief Texture Mapping" (SIGGRAPH 2000)
[Displacement Mapping] Donnelly, "Per-Pixel Displacement Mapping with Distance Functions" (GPU Gems 2)
 
11. Titel: Volumetrische Effekte
Datum: 12. Juli 2010
Bearbeitung: Nadine Siegmund
Betreuung: Markus Üffinger
Referenzen:
[Allgemein] Game Physics, GPGPU: Physics Simulation
[Fluid Effects] GPU Gems 3: Real-Time Simulation and Rendering of 3D Fluids,
Smoothed Particle Hydrodynamics, Smoothed Particle Hydrodynamics on GPUs
 
12. Titel: Postprocessing
Datum: 19. Juli 2010
Bearbeitung: Alexander Martin
Betreuung: Michael Krone
Referenzen:
[Grundlagen Deferred Shading]
   Hargreaves: "Deferred Shading" (Game Developers Conference 2004)
   Dachsbacher: Uni Erlangen Vorlesungsfolien
[Screen Space Ambient Occlusion & ähnliche Techniken]
   Luft, Colditz, Deussen: "Image Enhancement by Unsharp Masking the Depth Buffer" (ACM Transactions on Graphics 25, 2006)
   Fox, Compton: "Ambient Occlusive Crease Shading" (Game Developer Magazine, March 2008) → originaler GDM-Artikel auf Anfrage
   Überblick SSAO-Techniken
[Fokustiefe, Abbildungstiefe & Tiefen(un)schärfe]
   Hammon: "Practical Post-Process Depth of Field" (GPU Gems 3)
   Kraus, Strengert: "Depth-of-Field Rendering by Pyramidal Image Processing"(Proceedings of EuroGraphics 2007)
[Motion Blur] Rosado: "Motion Blur as a Post-Processing Effect" (GPU Gems 3)
 


»Stundenplanübersicht«   »Listenübersicht«