Culling-Verfahren

Um hochkomplexe, dreidimensionale Szenen in Echtzeit per Rasterisierung visualisieren zu können, sind beschleunigende Algorithmen unerlässlich. Eine wichtige Technologie ist das Culling. Dabei wird versucht, möglichst früh Geometrie herauszufiltern, die im finalen Bild nicht sichtbar sein wird. Diese kann einfach aus der Berechnung verworfen werden, ohne das finale Bild zu verändern. Dadurch werden unnötige Rechenoperationen auf der Grafikkarte vermieden und die Geschwindigkeit der Bildsynthese nimmt rapide zu.

Culling wurde schon seit den Anfängen der Computergrafik benutzt und bleibt auf moderner Hardware weiterhin wichtig. Daher existieren viele verschiedene Algorithmen, die sich in ihrer Funktionsweise, ihrem Rechenaufwand und der Flexibilität drastisch unterscheiden. Dieses Proseminar soll einen Überblick über die in Computerspielen am häufigsten benutzten Culling-Algorithmen geben und ihre Anwendung diskutieren.

Inhalt

• Grundlagen
  • Struktur einer 3D-Szene
  • Einführung in das Kameramodell
  • Zwischenschritte eines Zeichendurchlaufs
• Sektor-basiertes Culling
• Contribution-Culling
  • Level of Detail (LOD)
• View-Frustum Culling
  • Geometrischer Ansatz
  • Ansatz mit Polarkoordinaten
• Bounding Volume Hierarchies (BVH) und Spatial Subdivision
  • Octrees, Quadtrees
  • Binary Space Partition Trees (BSP-Trees)
  • Potentially Visible Sets (PVS)
• Portale
  • Optimiertes View-Frustum Culling
  • Portale für nicht-euklidische Räume
• Occlusion-Culling
  • Antiportale / Occlusion-Volumes
• Occlusion Quieries
  • Hardware Queries
  • Software Queries
  • Hierarchical Occlusion Maps (HOM)
  • Contribution-Culling mit Occlusion Queries
• Clipping
  • Tessellierung nach Hugues Hoppe
• Back-Face Culling
• Early Fragment Tests

Literatur und Informationen

• Cryengine Documentation: Culling Explained
• Tomas Akenine-Möller, Eric Haines, Naty Hoffman. Real-Time Rendering; 3rd Edition
• Jason Gregory. Game engine architecture
• David H. Eberly. 3D game engine design: a practical approach to real-time computer graphics; 2nd Edition
• Stephen Hill and Daniel Collin. Practical Dynamic Visibility for Games

Bildquellen

• Mitte: Valve Corp. Half Life 2. Valve Corp. und Sierra Entertainment. PC 2004 u.a.
• Rechts: Nickolay Kasyan, Nicolas Schulz, Tiago Sousa. Sectrets of cryengine 3 graphics technology. In SIGGRAPH'11