Effiziente Kollisionserkennung in Simulationen
06/04/2025Entwickle High-Performance Kollisionserkennung, damit wir Menschen endlich große, komplexe Herausforderungen in den Griff bekommen! Wie bei den meisten anderen Themen können wir den Umfang auf verschiedene Module wie eine Bachelor- oder Masterarbeit oder ein Game Research Lab abstimmen.
Hintergrund & Motivation
Die digitale Planung moderner Bauprojekte erfordert eine anspruchsvolle Koordination zahlreicher beweglicher Geräte, Maschinen und Objekte, sowohl räumlich als auch zeitlich. Um potenziell gefährliche oder physikalisch unmögliche Überschneidungen (Kollisionen) frühzeitig zu erkennen, ist eine leistungsfähige und dynamische Kollisionserkennung unverzichtbar. Dies gilt insbesondere dann, wenn Nutzerinteraktionen kontinuierlich neue Bewegungsdaten (Samples) hinzufügen oder bestehende entfernen und die Ergebnisse in Echtzeit benötigt werden.
Ein anschauliches Beispiel ist eine Großbaustelle, auf der sich täglich Bagger, Kräne und LKW über einen längeren Zeitraum hinweg bewegen. Wenn eine Bauplanerin die Reihenfolge einzelner Arbeitsschritte verändert, beeinflusst dies nicht nur den zeitlichen Ablauf, sondern auch die Bewegungsrouten zahlreicher Geräte. Die Herausforderung besteht darin, trotz solcher Änderungen jederzeit die Sicherheit und Effizienz aller Abläufe zu gewährleisten. Ein algorithmisch gestütztes System kann dabei entscheidend unterstützen und die Planerin entlasten.
Klassische Methoden der Kollisionserkennung funktionieren typischerweise "online" und haben daher kein vollständiges Wissen über vergangene oder zukünftige Positionen. Bei Millionen von Objekten über lange Zeiträume hinweg stoßen diese Verfahren jedoch schnell an ihre Grenzen. Reduziert man kollidierende Objekte hingegen auf einfache Primitive wie Bounding Boxes, interpoliert linear zwischen Zeit- und Positionssamples und nutzt umfassende Informationen zum Positionsverlauf, eröffnen sich vielfältige Möglichkeiten, um Anfragen in dynamischen und interaktiven Szenarien effizient und skalierbar zu beantworten.
Aufgabenstellung
Ziel der Arbeit ist die Implementierung einer Schnittstelle in C#, welches es ermöglicht Kollisionsereignisse bewegter Bounding-Volumes in einer Simulation zu tracken, sowie diese Implementierung zu evaluieren. Dieses Thema kann je nach Interesse in verschiedene Richtungen von einer Bachelorarbeit bis hin zur Masterarbeit erweitert werden.
Kernaufgaben:
- Literaturüberblick: Zusammenfassung des State-of-the-Art in Sachen Kollisionstracking
- Design & Implementierung des Systems: Verwaltung und effizientes Update von Millionen Samples (Oriented Bounding Boxes zu bestimmten Zeitpunkten), zwischen welchen wird linear interpoliert wird. Erkennen aller Kollisionen/Überschneidungen von Bounding-Boxen (inkl. Start- und Endzeitpunkt) im beobachteten Zeitraum, Meldung von Änderungen via Event.
- Dynamisches Sample-Management: Unterstützung für häufiges Einfügen und Entfernen von Samples durch Nutzerinteraktion, ohne dass die gesamte Struktur neu aufgebaut werden muss.
- Grundlegende Benchmarks: Performance-Messungen bezüglich Update-Zeiten und Skalierbarkeit der Kollisionsverfolgung im Vergleich zu naiven Methoden.
Erweiterungen:
- Gruppen-/Layerfilter: Erlauben, dass z.B. nur bestimmte Gerätegruppen aufeinander stoßen können.
- Komplexere Bounding Volumes: Unterstützung von Meshes oder verformbaren Objekten.
- Formale Komplexitätsanalyse: Untersuchung der theoretischen Laufzeit- und Speichergrenzen sowie Worst-Case-Szenarien.
- Erweiterte Benchmarks: Umfangreiche, realitätsnahe Testszenarien mit zufälligen, extremen oder kritischen Objektverteilungen und Bewegungen; Vergleich mit bestehenden Ansätzen.
- Rudimentäre Proximity Queries: Mitschreiben der k-nächsten Objekte um "beinahe"-Kollisionen mitverfolgen zu können.
Startpunkte & Literatur
- Collision Detection: A Survey, Kockara et al., 2007, Link
- A Survey on Collision Detection Techniques for Virtual Environments, Figueiredo et al., 2002, Link
- CS5643 – 07 Collision Detection, Marschner, 2025, Link
- Examination of Database Supported Spatio-Temporal Intersection Queries, Breunig et al., 2002, Link
- Indexing the Positions of Continuously Moving Objects, Šaltenis et al., 2006, Link
- Efficient Continuous Collision Detection for Bounding Boxes under Rational Motion, Albocher et al., 2006, Link
Supervision
Prof. Dr. Sebastian von Mammen
Yasin Raies, M.Sc., BII GmbH