Diese Woche war kurz, am Montag und Dienstag arbeitete ich weiter an einem 2D-Beleuchtungssystem . Den Rest der Zeit habe ich mit der Implementierung von Quadtree-Bäumen verbracht.

In diesem Artikel werde ich meine Implementierung und Gedanken teilen, die während des Entwurfs entstanden sind.

Zunächst muss ich sagen, warum ich mich entschieden habe, einen Quadrantenbaum zu implementieren.

Quadtree ist eine Space-Partition-Datenstruktur . Der Hauptvorteil gegenüber anderen Datenstrukturen ist die Anpassungsfähigkeit. Es bietet eine gute Leistung beim Einfügen, Löschen und Suchen. Das heißt, wir können diesen Baum in einem dynamischen Kontext verwenden, in dem sich Daten häufig ändern. Darüber hinaus ist diese Struktur recht einfach zu verstehen und zu implementieren.

Wenn die Speicherpartitionierung ein neues Thema für Sie ist, empfehle ich, diesen Artikel von Robert Nistrom zu lesen. Wenn Sie mehr über Quadrantenbäume erfahren möchten, lesen Sie diesen oder diesen Artikel.

Es gibt Bereiche in meinem Spiel, in denen sich die Verwendung von Quadtree sofort auszahlt:

• Bei der Erkennung von Kollisionen ist der Quadrantenbaum viel effizienter als die Brute-Force-Methode (Testen aller Paare). Dies ist jedoch nicht der effektivste Ansatz. In diesem Artikel kann ein Überblick über verschiedene Techniken und Benchmarks gegeben werden. Für die erste Version meiner Physik-Engine verwende ich sie jedoch. Vielleicht werde ich später, falls nötig, einen spezielleren Algorithmus wählen.
• Im Szenendiagramm kann ich beim Ausschneiden mit quadtree nach allen sichtbaren Knoten suchen.
• In einem Beleuchtungssystem können Sie mit quadtree Wände finden, die das Polygon der Sichtbarkeit der Lichtquelle schneiden.
• Im KI-System können Sie mit quadtree nach allen Objekten oder Feinden suchen, die der Essenz nahe stehen.
• Usw...

Wie Sie sehen können, sind Quadrantenbäume ziemlich vielseitig. Sie sind eine gute Ergänzung in Ihrem Toolkit.

Der gesamte im Artikel gezeigte Code ist auf GitHub zu finden.

Vorbereitende Vorbereitung

Bevor wir den Quadtree-Code detaillieren, benötigen wir kleine Klassen für geometrische Vector2 : die Vector2 Klasse zum Definieren von Punkten und die Box Klasse zum Definieren von Rechtecken. Beide werden Boilerplate sein.

Vektor2

Die Vector2 Klasse Vector2 minimalistisch. Es enthält nur Konstruktoren sowie + und / Operatoren. Das ist alles was wir brauchen:

 template<typename T> class Vector2 { public: T x; T y; constexpr Vector2<T>(TX = 0, TY = 0) noexcept : x(X), y(Y) { } constexpr Vector2<T>& operator+=(const Vector2<T>& other) noexcept { x += other.x; y += other.y; return *this; } constexpr Vector2<T>& operator/=(T t) noexcept { x /= t; y /= t; return *this; } }; template<typename T> constexpr Vector2<T> operator+(Vector2<T> lhs, const Vector2<T>& rhs) noexcept { lhs += rhs; return lhs; } template<typename T> constexpr Vector2<T> operator/(Vector2<T> vec, T t) noexcept { vec /= t; return vec; } 

Box

Die Box Klasse ist nicht viel komplizierter:

 template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : left(Left), top(Top), width(Width), height(Height) { } constexpr Box(const Vector2<T>& position, const Vector2<T>& size) noexcept : left(position.x), top(position.y), width(size.x), height(size.y) { } constexpr T getRight() const noexcept { return left + width; } constexpr T getBottom() const noexcept { return top + height; } constexpr Vector2<T> getTopLeft() const noexcept { return Vector2<T>(left, top); } constexpr Vector2<T> getCenter() const noexcept { return Vector2<T>(left + width / 2, top + height / 2); } constexpr Vector2<T> getSize() const noexcept { return Vector2<T>(width, height); } constexpr bool contains(const Box<T>& box) const noexcept { return left <= box.left && box.getRight() <= getRight() && top <= box.top && box.getBottom() <= getBottom(); } constexpr bool intersects(const Box<T>& box) const noexcept { return !(left >= box.getRight() || getRight() <= box.left || top >= box.getBottom() || getBottom() <= box.top); } }; 

Es enthält einige nützliche Getter.

Interessanter ist, dass es die Methode enthält enthält, die prüft, ob sich das Rechteck in einem anderen befindet, und die Methode intersects , die prüft, ob sich das Rechteck mit einem anderen schneidet.

Wir werden beim Einfügen und Löschen Includes verwenden und beim Erkennen von Schnittpunkten überschneiden.

Quadtree

Hier ist das Quadtree der Quadtree Klasse:

 template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { static_assert(std::is_convertible_v<std::invoke_result_t<GetBox, const T&>, Box<Float>>, "GetBox must be a callable of signature Box<Float>(const T&)"); static_assert(std::is_convertible_v<std::invoke_result_t<Equal, const T&, const T&>, bool>, "Equal must be a callable of signature bool(const T&, const T&)"); static_assert(std::is_arithmetic_v<Float>); public: Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(), const Equal& equal = Equal()) : mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal) { } private: static constexpr auto Threshold = std::size_t(16); static constexpr auto MaxDepth = std::size_t(8); struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; }; Box<Float> mBox; std::unique_ptr<Node> mRoot; GetBox mGetBox; Equal mEqual; bool isLeaf(const Node* node) const { return !static_cast<bool>(node->children[0]); } }; 

Wie Sie sehen können, ist Quadtree eine Vorlagenklasse. Auf diese Weise können wir die Klasse für verschiedene Zwecke verwenden, über die ich zu Beginn gesprochen habe.

Vorlagenoptionen:

• T : Die Art der Werte, die in quadtree enthalten sein werden. T sollte eine einfache Klasse sein, da sie in einem Quadtree gespeichert wird. Idealerweise sollte dies ein Zeiger oder eine kleine einfache Datenstruktur (POD) sein.
• GetBox : Der Typ des aufgerufenen Objekts, der den Wert an der Eingabe empfängt und ein Rechteck GetBox .
• Equal : Der Typ des aufgerufenen Objekts, um zu überprüfen, ob zwei Werte gleich sind. Standardmäßig verwenden wir den Standard-Gleichheitsoperator.
• Float : Der in Berechnungen verwendete arithmetische Typ. Standardmäßig verwenden wir float .

Zu Beginn der Klassendefinition gibt es drei statische Zusicherungen zum Überprüfen der Gültigkeit der Vorlagenparameter.

Werfen wir einen Blick auf die Definition eines Knotens. Ein Knoten speichert einfach Zeiger auf seine vier untergeordneten Knoten und eine Liste der darin enthaltenen Werte. Wir speichern darin weder den Begrenzungsrahmen noch die Tiefe, sie werden im laufenden Betrieb berechnet.

Ich führte Benchmarks für beide Ansätze durch (Beibehalten eines Rechtecks ​​mit Tiefe und ohne Beibehalten) und stellte bei der Berechnung im laufenden Betrieb keine Leistungseinbußen fest. Außerdem spart es ein wenig Speicher.

Um einen internen Knoten von einem Blatt unterscheiden zu können, isLeaf die Methode isLeaf . Es wird nur überprüft, ob das erste Kind nicht null ist. Da null entweder alle untergeordneten Knoten oder keiner von ihnen sind, reicht es aus, nur den ersten zu überprüfen.

Jetzt können wir uns die Quadtree Mitgliedsvariablen Quadtree :

• mBox ist ein globaler Begrenzungsrahmen. Alle in quadtree eingefügten Werte müssen darin enthalten sein.
• mRoot ist die Wurzel von quadtree.
• mGetBox ist das aufgerufene Objekt, mit dem wir das Rechteck aus dem Wert mGetBox .
• mEqual ist das aufgerufene Objekt, mit dem wir die Gleichheit der beiden Werte überprüfen.

Der Konstruktor setzt einfach mBox , mGetBox und mEqual und erstellt auch einen Wurzelknoten.

Die letzten beiden Parameter, über die wir noch nicht gesprochen haben, sind Threshold und MaxDepth . Threshold ist die maximale Anzahl von Werten, die ein Knoten enthalten kann, bevor wir ihn teilen. MaxDepth ist die maximale Tiefe eines Knotens. Wir versuchen nicht mehr, die Knoten in MaxDepth zu MaxDepth . Wenn Sie zu viel teilen, kann dies die Leistung beeinträchtigen. Ich habe diesen Konstanten vernünftige Werte gegeben, die für die meisten Fälle geeignet sind. Sie können versuchen, sie für Ihre Konfiguration zu optimieren.

Jetzt sind wir bereit, weitere interessante Operationen zu starten.

Einfügen und löschen

Bevor ich den Einfügecode zeige, müssen wir diskutieren, welche Knoten die Werte enthalten. Es gibt zwei Strategien:

• Werte werden nur in Blättern gespeichert. Da der Begrenzungsrahmen eines Werts mit mehreren Blättern interagieren kann, wird der Wert in allen diesen Blättern gespeichert.
• Werte können in allen Knoten gespeichert werden. Wir speichern den Wert im kleinsten Knoten, der seinen Begrenzungsrahmen vollständig enthält.

Wenn die Begrenzungsrechtecke klein und ungefähr gleich groß sind, ist die erste Strategie bei der Suche nach Schnittpunkten effektiver. Wenn jedoch große Rechtecke vorhanden sind, können entartete Fälle auftreten, in denen die Leistung sehr schlecht ist. Wenn wir beispielsweise einen Wert einfügen, dessen Rechteck sich im globalen Begrenzungsrahmen befindet, wird er allen Blättern hinzugefügt. Wenn wir einen Threshold für solche Werte einfügen, werden alle Knoten geteilt, bis MaxDepth erreicht ist und die Werte nicht in allen Blättern enthalten sind. Daher wird quadtree enthalten $$$\ texttt {Threshold} \ times 4 ^ {\ texttt {MaxDepth}}$Werte, und das ist ... viel.

Darüber hinaus ist das Einfügen und Löschen bei der ersten Strategie etwas langsamer, da alle Knoten, die den Wert schneiden, eingefügt (oder gelöscht) werden müssen.

Daher werde ich die zweite Strategie anwenden, bei der es keine entarteten Fälle gibt. Da ich Quadtree in verschiedenen Kontexten verwenden möchte, ist dies bequemer. Darüber hinaus eignet sich diese Strategie besser für dynamische Kontexte, in denen viele Einfügungen und Löschungen durchgeführt werden, um Werte zu aktualisieren, z. B. in einer physischen Engine, in der Entitäten verschoben werden.

Um herauszufinden, in welchen Knoten wir einen Wert einfügen oder löschen, verwenden wir zwei Hilfsfunktionen.

Die erste, computeBox , berechnet das Rechteck des computeBox Knotens anhand des Rechtecks ​​des übergeordneten Knotens und des Index seines Quadranten.

 Box<Float> computeBox(const Box<Float>& box, int i) const { auto origin = box.getTopLeft(); auto childSize = box.getSize() / static_cast<Float>(2); switch (i) { // North West case 0: return Box<Float>(origin, childSize); // Norst East case 1: return Box<Float>(Vector2<Float>(origin.x + childSize.x, origin.y), childSize); // South West case 2: return Box<Float>(Vector2<Float>(origin.x, origin.y + childSize.y), childSize); // South East case 3: return Box<Float>(origin + childSize, childSize); default: assert(false && "Invalid child index"); return Box<Float>(); } } 

Der zweite, getQuadrant , gibt den Quadranten zurück, in dem sich der Wert befindet:

 int getQuadrant(const Box<Float>& nodeBox, const Box<Float>& valueBox) const { auto center = nodeBox.getCenter(); // West if (valueBox.getRight() < center.x) { // North West if (valueBox.getBottom() < center.y) return 0; // South West else if (valueBox.top >= center.y) return 2; // Not contained in any quadrant else return -1; } // East else if (valueBox.left >= center.x) { // North East if (valueBox.getBottom() < center.y) return 1; // South East else if (valueBox.top >= center.y) return 3; // Not contained in any quadrant else return -1; } // Not contained in any quadrant else return -1; } 

Es gibt -1 wenn es in keinem der Quadranten enthalten ist.

Jetzt sind wir bereit, Methoden zum Einfügen und Löschen in Betracht zu ziehen.

Einfügen

Die add Methode ruft einfach eine private Hilfsmethode auf:

 void add(const T& value) { add(mRoot.get(), 0, mBox, value); } 

Hier ist der Code der Hilfsmethode:

 void add(Node* node, std::size_t depth, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Insert the value in this node if possible if (depth >= MaxDepth || node->values.size() < Threshold) node->values.push_back(value); // Otherwise, we split and we try again else { split(node, box); add(node, depth, box, value); } } else { auto i = getQuadrant(box, mGetBox(value)); // Add the value in a child if the value is entirely contained in it if (i != -1) add(node->children[static_cast<std::size_t>(i)].get(), depth + 1, computeBox(box, i), value); // Otherwise, we add the value in the current node else node->values.push_back(value); } } 

Zu Beginn gibt es einige Annahmen, die bestätigen, dass wir nichts Unlogisches tun. Beispielsweise fügen wir keinen Wert in einen Knoten ein, der keinen Begrenzungsrahmen enthält.

Wenn dann der Knoten ein Blatt ist und wir einen neuen Wert in ihn einfügen können, d.h. Wir haben MaxDepth oder Threshold nicht erreicht. MaxDepth das Einfügen durch. Andernfalls teilen wir diesen Knoten und versuchen es erneut.

Wenn der Knoten intern ist, berechnen wir den Quadranten, der den Begrenzungsrahmen des Werts enthält. Wenn es vollständig im untergeordneten Knoten enthalten ist, führen wir einen rekursiven Aufruf durch. Andernfalls fügen Sie in diesen Knoten ein.

Hier ist das Trennverfahren:

 void split(Node* node, const Box<Float>& box) { assert(node != nullptr); assert(isLeaf(node) && "Only leaves can be split"); // Create children for (auto& child : node->children) child = std::make_unique<Node>(); // Assign values to children auto newValues = std::vector<T>(); // New values for this node for (const auto& value : node->values) { auto i = getQuadrant(box, mGetBox(value)); if (i != -1) node->children[static_cast<std::size_t>(i)]->values.push_back(value); else newValues.push_back(value); } node->values = std::move(newValues); } 

Wir erstellen vier untergeordnete Knoten und entscheiden dann für jeden Wert des übergeordneten Knotens, in welchem ​​Knoten (untergeordnet oder übergeordnet) der Wert gespeichert werden soll.

Löschen

Die Methode remove ruft auch einfach eine Hilfsmethode auf:

 void remove(const T& value) { remove(mRoot.get(), nullptr, mBox, value); } 

Hier ist der Code der Hilfsmethode, der dem Einfügecode sehr ähnlich ist:

 void remove(Node* node, Node* parent, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Remove the value from node removeValue(node, value); // Try to merge the parent if (parent != nullptr) tryMerge(parent); } else { // Remove the value in a child if the value is entirely contained in it auto i = getQuadrant(box, mGetBox(value)); if (i != -1) remove(node->children[static_cast<std::size_t>(i)].get(), node, computeBox(box, i), value); // Otherwise, we remove the value from the current node else removeValue(node, value); } } 

Wenn der aktuelle Knoten ein Blatt ist, entfernen wir den Wert aus der Werteliste des aktuellen Knotens
und versuchen Sie, diesen Knoten mit den Schwesterknoten und seinem übergeordneten Knoten zusammenzuführen. Andernfalls bestimmen wir, in welchem ​​Quadranten sich der Begrenzungsrahmen des Werts befindet. Wenn es vollständig im untergeordneten Knoten enthalten ist, führen wir einen rekursiven Aufruf durch. Andernfalls löschen Sie aus den Werten des aktuellen Knotens.

Da uns die Reihenfolge der im Knoten gespeicherten Werte beim Löschen egal ist, verwende ich eine kleine Optimierung: Ich ändere einfach den gelöschten Wert mit dem letzten und lösche ihn:

 void removeValue(Node* node, const T& value) { // Find the value in node->values auto it = std::find_if(std::begin(node->values), std::end(node->values), [this, &value](const auto& rhs){ return mEqual(value, rhs); }); assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); // Swap with the last element and pop back *it = std::move(node->values.back()); node->values.pop_back(); } 

Wir müssen uns auch tryMerge :

 void tryMerge(Node* node) { assert(node != nullptr); assert(!isLeaf(node) && "Only interior nodes can be merged"); auto nbValues = node->values.size(); for (const auto& child : node->children) { if (!isLeaf(child.get())) return; nbValues += child->values.size(); } if (nbValues <= Threshold) { node->values.reserve(nbValues); // Merge the values of all the children for (const auto& child : node->children) { for (const auto& value : child->values) node->values.push_back(value); } // Remove the children for (auto& child : node->children) child.reset(); } } 

tryMerge überprüft, ob alle tryMerge Knoten Blätter sind und ob die Gesamtzahl seiner Werte und der Werte der tryMerge Knoten unter dem Schwellenwert liegt. Wenn ja, kopieren wir alle Werte von den untergeordneten Knoten auf den aktuellen Knoten und löschen die untergeordneten Knoten.

Schnittpunktsuche

Schnittpunkt mit Rechteck

Schließlich kamen wir zum interessantesten: zur Suche nach Kreuzungen. Die erste Möglichkeit besteht darin, alle Werte zu ermitteln, die ein bestimmtes Rechteck schneiden. Dies ist beispielsweise erforderlich, um das Abschneiden durchzuführen.

Dies query :

 std::vector<T> query(const Box<Float>& box) const { auto values = std::vector<T>(); query(mRoot.get(), mBox, box, values); return values; } 

Bei dieser Methode wählen wir einfach std::vector , der die Werte enthält, die den Begrenzungsrahmen schneiden, und rufen die Hilfsmethode auf:

 void query(Node* node, const Box<Float>& box, const Box<Float>& queryBox, std::vector<T>& values) const { assert(node != nullptr); assert(queryBox.intersects(box)); for (const auto& value : node->values) { if (queryBox.intersects(mGetBox(value))) values.push_back(value); } if (!isLeaf(node)) { for (auto i = std::size_t(0); i < node->children.size(); ++i) { auto childBox = computeBox(box, static_cast<int>(i)); if (queryBox.intersects(childBox)) query(node->children[i].get(), childBox, queryBox, values); } } } 

Zuerst addieren wir alle im aktuellen Knoten gespeicherten Werte, die sich mit dem angeforderten Rechteck schneiden. Wenn der aktuelle Knoten intern ist, führen wir einen rekursiven Aufruf für jeden untergeordneten Knoten durch, dessen Begrenzungsrechteck das angeforderte Rechteck schneidet.

Alle paarweisen Schnittpunkte

Der zweite unterstützte Anwendungsfall besteht darin, nach allen Wertepaaren zu suchen, die im sich überschneidenden Quadrantenbaum gespeichert sind. Dies ist besonders nützlich, wenn Sie eine physische Engine erstellen. Dieses Problem kann mit der query gelöst werden. Tatsächlich können wir die query für den Begrenzungsrahmen aller Werte aufrufen. Dies kann jedoch effizienter durchgeführt werden, indem nur ein Schnittpunkt für ein Paar hinzugefügt wird (bei query werden diese zweimal gefunden).

Um dies zu realisieren, müssen wir berücksichtigen, dass der Schnittpunkt nur auftreten kann

• zwischen zwei in einem Knoten gespeicherten Werten

oder

• zwischen dem im Knoten gespeicherten Wert und einem anderen Wert, der im Nachkommen dieses Knotens gespeichert ist.

Aus diesem Grund müssen wir nur den Schnittpunkt zwischen:

• Wert und die folgenden Werte im selben Knoten gespeichert

und

• Wert und im Nachkommen gespeicherte Werte.

Daher werden wir definitiv nicht zweimal dieselbe Kreuzung melden.

Hier ist der findAllIntersections Code:

 std::vector<std::pair<T, T>> findAllIntersections() const { auto intersections = std::vector<std::pair<T, T>>(); findAllIntersections(mRoot.get(), intersections); return intersections; } 

Auch hier weisen wir einfach std::vector zu, um die Schnittpunkte zu speichern und die Hilfsfunktion aufzurufen:

 void findAllIntersections(Node* node, std::vector<std::pair<T, T>>& intersections) const { // Find intersections between values stored in this node // Make sure to not report the same intersection twice for (auto i = std::size_t(0); i < node->values.size(); ++i) { for (auto j = std::size_t(0); j < i; ++j) { if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) intersections.emplace_back(node->values[i], node->values[j]); } } if (!isLeaf(node)) { // Values in this node can intersect values in descendants for (const auto& child : node->children) { for (const auto& value : node->values) findIntersectionsInDescendants(child.get(), value, intersections); } // Find intersections in children for (const auto& child : node->children) findAllIntersections(child.get(), intersections); } } 

In der ersten Phase werden Schnittpunkte zwischen den im aktuellen Knoten gespeicherten Werten überprüft. Wenn der aktuelle Knoten intern ist, findIntersectionInDescendants nach Schnittpunkten zwischen den in diesem Knoten gespeicherten Werten und den in seinen Nachkommen gespeicherten Werten. Schließlich machen wir rekursive Aufrufe.

findIntersectionsInDescendants findet rekursiv Schnittpunkte zwischen dem angegebenen Wert und allen im Teilbaum gespeicherten Werten:

 void findIntersectionsInDescendants(Node* node, const T& value, std::vector<std::pair<T, T>>& intersections) const { // Test against the values stored in this node for (const auto& other : node->values) { if (mGetBox(value).intersects(mGetBox(other))) intersections.emplace_back(value, other); } // Test against values stored into descendants of this node if (!isLeaf(node)) { for (const auto& child : node->children) findIntersectionsInDescendants(child.get(), value, intersections); } } 

Das ist alles! Ich wiederhole, der gesamte Code ist auf GitHub veröffentlicht .

Nützliche Ressourcen

Wenn Sie mehr über die Kollisionserkennung und Partitionierung von Datenstrukturen erfahren möchten, empfehlen wir Ihnen, das Buch von Christer Erickson Real-Time Collision Detection zu lesen. Viele Themen sind darin tief verwurzelt und gleichzeitig ist das Buch in einer sehr verständlichen Sprache verfasst. Darüber hinaus können Kapitel separat gelesen werden. Dies ist eine großartige Referenzquelle.

Fazit

Damit ist die Arbeit mit der Kollisionserkennung abgeschlossen. Es ist jedoch nur die Hälfte des physischen Motors. Die zweite Hälfte ist die Auflösung von Kollisionen .