kdTree in C++
Im abschließenden Beispiel für Algorithmen und Datenstrukturen habe ich einen kdTree in C++ umgesetzt. Visualisiert wird das Beispiel über Open GL, genauer gesagt mit der GLUT Bibliothek.
kdTree in C++
Ein k-d-Tree oder auch k-dimensionaler Baum ist ein unbalancierter Suchbaum der eine Menge Objekte in ungleichmäßig große Bereiche teilt. Im 3D Raum sind diese Bereiche Boxen. Grund für diese Aufteilung ist eine Optimierung der Kollisionserkennung. Es ist effizienter, wenn man zuerst prüft ob ein Strahl den kdTree als ganzen schneidet oder nicht und erst im Fall einer Kollision weiter prüft welcher Bereich und zuletzt welches Objekt geschnitten wird. In Summe wird so etwas schneller berechnet, als wenn man jedes Objekt einzeln prüft (vor allem dann, wenn es tausende solcher Objekte mit tausenden Polygonen gibt).
Mein Implementation umfasst folgende Punkte:
- definieren beliebiger Objekte im Raum (Dreiecke)
- automatische Erstellung eines kdTrees basierend auf Objekten
- Erstellung eines Strahls über diesen werden Kollisionsabfragen durchgeführt
Wird der kdTree vom Strahl geschnitten, dann werden auch dessen Objekte getestet. Vom Strahl getroffene Geometrie wird grün gezeichnet. Siehe dazu die Screenshots.
Implementierung
Der Source Code ist wie immer auf meiner GitHub Seite zu finden. Anders als die bisherigen Beispiele wurde keine fertige Engine verwendet. Die visuelle Ausgabe wird direkt über OpenGL gezeichnet, genauer gesagt über die GLUT Bibliothek, mit der man mit nur wenigen Funktionen eine fertige Anwendung bekommt (die komplette Initialisierung von OpenGL ist da verborgen). Damit der Code Compiliert mus man die glut.h Datei einbinden und glut.lib dem Linker bekannt geben. Im Ordner der *.exe, bzw. im Projektordner benötigt man noch die glut32.dll. Soweit ich das getestet habe funktioniert nur der x86 Build. Große Teile des Codes habe ich nicht selbst geschrieben sondern aus einer fertigen Math Bibliothek genommen – da das aber schon Jahre her ist habe ich da keine Quellen mehr. Ich vermute aus einem Lehrbuch.
Selbst geschrieben ist in jedem Fall das Beispielprogramm main.cpp und der Baum kdtree.h/-.cpp. Im Beispielprogramm wird ein std::vector mit Dreiecken (Triangles) erstellt. Diese haben beliebige Koordinaten im Raum und können gerne verändert werden. Dieser Vector wird dem kdTree übergeben, welcher sich basierend auf dieser Geometrie selbstständig aufbaut. Sowohl Triangles als auch der kdTree haben eine draw() Methode über die sie gezeichnet werden.
Zusätzlich wird auch ein Strahl (Ray) erzeugt. In der draw() Methode von GLUT wird dieser mit dem kdTree und den Dreiecken geschnitten und im Fall eines Treffers die Füllfarbe auf grün geändert. Über die Tastatur kann man folgendes verändern:
- Wireframe oder Solid Rendering
- Kamera um Y Achse drehen
- Strahl auf Y-Z Achse verschieben
Die Steuerung ist zwar recht eingeschränkt, reicht aber zu demonstrieren, dass die Intersection zwischen Strahl und Geometrie in Echtzeit effizient berechnet wird.
Fazit
Ich habe gezeigt wie man einen kdTree in C++ implementiert. Durch den kdTree beschleunigt man Kollisionsabfragen mit statischen Objekten. Solche Suchbäume wurden schon früh in der Computergrafik und in Spielen zur schnelleren Berechnung einer Szene verwendet. Die Arbeit mit GLUT auf einem 64-bit Windows 10 System zeigt, dass diese Grafikbibliothek mittlerweile stark gealtert ist und wenig Benutzerfreundlich ist. Um GLUT selbstständig zu bauen müsste man 32-bit Windows 7 Komponenten installieren. Ich empfehle bei Interesse die Visualisierung anders zu implementieren.
