Neverending ODC
Die interne Optimierungsstruktur der Physikengine

Version 1.1.1

Martin Bader

02.12.2002

Abstract: Hier soll die von der Physikengine verwendete Optimierungsstruktur erläutert werden. Das Dokument umfasst Interface-Spezifikationen, einen Überblick über die verwendeten Klassen, eine Erläuterung der Methoden sowie der wichtigsten Algorithmen.

1 Grundgedanke
2 Die externe Schnittstelle
3 Interner Aufbau
4 Ausblick

1 Grundgedanke

Für die Physikengine von Neverending ODC wurde eine Objektverwaltungsstruktur benötigt, die effiziente räumliche Anfragen für Objekte und die Ermittlung von potentiellen Kollisionen ermöglicht. Die Verwendung von sortierten Listen würde zwar eine schnelle Kollisionserkennung ermöglichen, räumliche Anfragen sind jedoch nur in linearer Zeit über die Listengrösse möglich. Die Verwendung eines Quad-Trees ¹ ermöglicht zwar räumliche Anfragen in O(log(n)), aber Objekte im Wurzelknoten müssten mit allen anderen Objekten auf Kollisionen überprüft werden.

Der hier vorgestellte Ansatz versucht nun, die Vorteile beider Strukturen zu vereinen, um so beide Anfragen effizient zu gestalten. Dazu wurde das zu verwaltende Gebiet in Quadrate fixer Grösse aufgeteilt, welche jeweils mit Listen vrwaltet werden. Über diese Quadate wurde ein Quad-Tree aufgebaut. Es ist jedoch auch möglich, direkt auf die Blätter des Baumes zuzugreifen, ohne den Umweg über die Baumstruktur zu nehmen.

Objekte werden immer in dem Knoten gespeichert, der ihre Bounding Box vollständig umschliesst. Inaktive Objekte² werden zusätzlich in allen Blättern gespeichert, die sich mit ihrer Bounding Box überlappen. Aktive Objekte, die sich nicht in Blättern befinden, werden zusätzlich in einer separaten Liste verwaltet, der m_pActiveList. Räumliche Anfragen können jetzt ganz normal über den Quad-Tree erfolgen. Für das Erkennen potentieller Kollisionspartner muss man folgende drei Fälle testen:

Kollisionen können innerhalb eines Blattes stattfinden
Objekte der m_pActiveList müssen mit allen Blättern überprüft werden, welche sich mit ihrer Bounding Box überlappen.
Es können Objekte innerhalb der m_pActiveList kollidieren.

Objekte, deren Ausdehnung nicht grösser als die Kantenlänge eines Blattes ist, müssen also im worst case mit 4 Blättern getesten werden (im Gegensatz zur Überprüfung mit allen Blättern bei einer reinen Baumstruktur). Desweiteren ist die Anzahl physikalisch aktiver Objekte wesentlich kleiner als die der inaktiven, und die Wahrscheinlichkeit, dass sich aktives ein Objekt nicht innerhalb eines Blattes befindet, ist ebenfalls gering. Dadurch befinden sich relativ wenige Objekte in der m_pActiveList.

2 Die externe Schnittstelle

Extern erfolgt der Zugriff auf die Struktur über die Klasse ContainerTree. Sie bietet folgende Schnittstelle an:

2.1 statische Konstanten

Der Aufbau des Baumes ist über folgende Konstanten definiert:

ms_ContainerLength: ist ein float-Wert, welcher die Kantenlänge eines Blattes in Metern definiert. Der Wert in der momentanen Implementation ist 16m.
ms_TreeDepth: gibt die Tiefe des Baumes an. Hierbei würde 0 bedeuten, der Baum würde nur aus seiner Wurzel bestehen. Die momentane Baumtiefe beträgt 4.
ms_NodeOffsets: bietet Offset-Werte, mit denen man schnell die Nummer eines Knotens errechnen kann. Näheres zur Berechnung in Kapitel 2.16. Die Werte hängen direkt mit der Baumtiefe zusammen und sind als int[ms_TreeDepth + 1]-array gespeichert.
ms_NumEdgeNodes: gibt die Anzahl der Blätter pro Kante des Quad-Trees an. Sein Wert kann direkt aus der Tiefe t des Baumes mit der Formel 2^t errechnet werden, wurde jedoch aus Effizienzgründen extra abgespeichert.

2.2 Der Konstruktor

ContainerTree() erzeugt einen neuen, leeren ContainerTree, dessen Variablen jedoch zunächst noch mit init(2.4) initialisiert werden müssen.

2.3 Der Destruktor

Der Destruktor löscht alle in init(2.4) angelegten Variablen und gibt den belegten Speicherplatz wieder frei.

2.4 init

Hier wird der Speicherplatz für nichtprimitive Klassenvariablen allokiert und diese erzeugt. Diese Methode muss unbedingt nach dem Aufruf des Konstruktors aufgerufen werden.

2.5 overlappingBoundingBoxes

Dies ist eine statische Methode, die überprüft, ob sich zwei Bounding Boxes überlappen. Funktionparameter sind die beiden Bounding Boxes, die jeweils ein float[6]-array sein müssen. Die ersten drei Werte werden als die minimalen x-, y- und z-Werte der Bounding Box interpretiert, die anderen drei als die maximalen Werte. Mögliche Rückgabewerte sind true, falls sich die Bounding Boxes überlappen, ansonsten false.

2.6 insertEntity

Mit dieser Methode können Entities in den ContainerTree eingefügt werden. Übergeben wird ein Pointer auf das PhysicalEntity, das eingefügt werden soll. Der Rückgabetyp dieser Methode ist void.

2.7 toggleActive

Diese Methode ändert den Zustand des active-flags eines Entities. Dieser Änderung darf nicht direkt im Entity vorgenommen werden, da der ContainerTree aktive und inaktive Objekte unterschiedlich behandelt und eventuell umstrukturiert werden muss. Übergabeparameter ist ein Pointer auf das PhysicalEntity, dessen flag geändert werden soll. Der Rückgabetyp ist void.

2.8 moveEntities

Diese Methode bewegt alle Entities, die im Baum eingefügt sind. Dabei wird darauf geachtet, dass der Baum konsistent bleibt. Der Übergabeparameter vom Typ float spezifiziert das Zeitintervall in Sekunden, für das die Bewegung berechnet werden soll. Die Bewegung betrifft nur aktive Objekte und besteht aus der dem Objektzustand entsprechenden Rotation und Translation. Der Rückgabetyp ist void.

2.9 initSearch

Dies initialisiert die Suche nach Objekten in einer gegebenen Bounding Box. Die Übergabeparameter sind eine Bounding Box, welche wie in OverlappingBoundingBoxes (2.5) beschrieben aufgebaut sein muss. Der zweite Parameter ist eine boolesche Variable, welche angibt, ob bei der Suche nur aktive Objekte zurückgegeben werden sollen. Beim Aufruf dieser Methode muss die letzte Suche geschlossen sein, entweder durch closeSearch(2.12) oder durch das Auslesen aller Elemente. Ist noch eine Suche geöffnet, wird über den Logger eine Warnung ausgegeben und keine neue Suche initialisiert. Um die Entities dieser Suche zu erhalten, muss sukzessive getNextEntity(2.11) aufgerufen werden. Der Rückgabetyp dieser Methode ist void.

2.10 initNodeSearch

Diese Methode initialisiert die Suche nach Objekten in einem bestimmten Knoten des Baumes. Ebenso wie in initSearch(2.9) muss die letzte Suche geschlossen sein, ansonsten wird nur eine Warning über den Logger ausgegeben und keine neue Suche initialisiert. Die Übergabeparameter sind:

Die Nummer des Knotens (vom Typ int), welche sich wie in 2.16 beschrieben ergibt.
Eine boolesche Variable, die indiziert, ob nur nach aktiven Objekten gesucht werden soll.
Eine boolesche Variable, die indiziert, ob nur nach Objekten, die vollständig in diesem Knoten sind, gesucht werden soll. Inaktive Objekte, welche zusätzlich zu iherm eigentlichen Knoten in Blätter gespeichert wurden, können so bei der Suche in Blättern herausgefiltert werden. Die Filterung wird durch das Setzen auf true dieser Variable aktiviert.
Eine Bounding Box, wie in 2.5 beschrieben. Dieser Parameter ist optional. Wird er gesetzt, wird nur nach Entities, die sich mit dieser Bounding Box überlappen, gesucht.

Um die Entities dieser Suche zu erhalten, muss sukzessive getNextEntity (2.11) aufgerufen werden. Der Rückgabetyp dieser Methode ist void.

2.11 getNextEntity

Diese Methode gibt einen Pointer auf das nächste Entity der aktuellen Suche zurück. Ist keine Suche geöffnet (entweder mit initSearch (2.9) oder mit initNodeSearch(2.10), wird eine Warning auf dem Logger ausgegeben und NULL zurückgegeben. Liefert die Suche keine weiteren Entities mehr, wird ebenfalls NULL zurückgegeben und die Suche geschlossen.

2.12 closeSearch

Diese Methode schliesst explizit eine Suche, falls es eine geöffnete Suche gibt. Der Rückgabetyp ist void.

2.13 getOverlappingBoundingBoxes

Diese Methode sucht nach Objektpaaren mit überlappenden Bonding Boxes. Der Übergabeparameter ist ein Pointer auf ein PairSet, welches als set<pair<PhysicalEntity*, PhysicalEntity*> > definiert ist. Alle gefundenen Objektpaare werden zu diesem Set hinzugefügt, Duplikate werden automatisch eliminiert. Der Rückgabetyp ist void, alle Informationen werden durch den Seiteneffekt im Übergabeparameter zurückgegeben.

2.14 debug

Diese Methode dient zum debuggen des ContainerTree. Sie nimmt verschiedene Konsistenzprüfungen vor und bricht das Programm mit einem Logger::fatal ab, wenn irgendeine Inkonsistenz entdeckt wurde. Der Rückgabetyp ist void. Da diese Methode sich häufig ändern kann, bitte für genauere Informationen die Dokumentation in containerTree.h lesen.

2.15 dump

Diese Methode gibt den gesamten Inhalt des ContainerTree über den Logger aus. Der Rückgabetyp ist void. Sie ist zum debuggen gedacht und kann sich in ihrer Implementierung häufig ändern. Genauere Informationen gibt es in der Dokumentation in containerTree.h.

2.16 Berechnung von Knotennummern

Für den Zugriff auf Knoten des ContainerTree gibt es prinzipiell zwei Möglichkeiten. Welche dieser Möglichkeiten angewandt wird, hängt von der aufgerufenen Methode ab.

Für Blätter kann die Position im m_pQuads-array relativ einfach errechnet werden. Die Blätter sind hier reihenweise durchnummeriert, das Blatt in der i-ten Zeile und j-ten Spalte des gesamten ContainerTree hat also die Position
(i - 1) · ms_NumEdgeNodes + j - 1
im m_pQuads-array.
Die Position im m_pNodes-array setzt sich aus Knotennummer und Offset zusammen. Die Knotennummer des root-Knotens ist 0, für alle anderen Knoten gilt

$\begin{displaymath} Knotennummer = Knotennummer_{Vater} \cdot 4 + \left\{ \begi... ...s} \\ 3 & \mbox{wenn Kind unten rechts} \end{array} \right\} \end{displaymath}$

Der Offset, der addiertwerden muss, ist von der Tiefe des Knotens abhängig. Die effektive Knotennummer ergibt sich aus
Knotennummer + ms_NodeOffsets[Tiefe]

3 Interner Aufbau

Die gesamte Optimierungsstruktur besteht aus den Klassen Interval, IntervalListContainer und ContainerTree. Der folgende Abschnitt erläutert ihren internen Aufbau und ihre Funktionalität.

3.1 Die Klasse Interval

Diese Klasse stellt die Projektion einer Bounding Box in eine Dimension dar. Diese Intervalle werden von den IntervalListContainer(3.2) der einzelnen Quads verwaltet. Die Klassenvariablen m_x und m_y stellen den Beginn und das Ende des Intervalls dar, und haben nichts mit den Dimensionen x und y gemein. m_pEntity ist ein Pointer auf das zum Intervall gehörige Entity. Das Flag m_MultipleQuads gibt an, ob das hier abgespeicherte Intervall sich (im Falle von false in dem der Bounding Box zugehörigen IntervalListContainer befindet oder (im Falle von true ob es sich um eine Kopie in den Blättern des Baumes handelt (siehe hierzu auch Kapitel 1).

3.1.1 Die Operatoren

Folgende Operatoren wurden für den Gebrauch mit Intervallen überladen:

<: vergleicht zuerst die Startwerte (m_x) mit <, dann bei Gleichheit die Endwerte (m_y)
>: vergleicht zuerst die Startwerte (m_x) mit >, dann bei Gleichheit die Endwerte (m_y)
==: liefert true zurück, wenn sowohl m_x als auch m_y beider Intervalle übereinstimmen.

3.1.2 Konstruktor und Destruktor

Dem Konstruktor werden sämtliche Klassenvariablen als Parameter übergeben. Der Destruktor ist leer, es wird also nur der Speicherplatz der Klassenvariablen wieder freigegeben.

3.2 Die Klasse IntervalListContainer

Diese Klasse verwaltet Entities in Listen und eignet sich deshalb als Optimierungsstruktur für kleine Bereiche. Sie wird in den einzelnen Knoten des ContainerTree(3.3) eingesetzt und besitzt folgende Klassenvariablen:

m_XList: ist eine Liste von Intervallen, welche die Projektion der Objekte in die x-Dimension darstellen. Sie ist stets aufsteigend sortiert.
m_YList: ist eine Liste von Intervallen, welche die Projektion der Objekte in die y-Dimension darstellen. Sie ist stets aufsteigend sortiert.
m_ZList: ist eine Liste von Intervallen, welche die Projektion der Objekte in die z-Dimension darstellen. Sie ist stets aufsteigend sortiert.
m_NumActives: gibt die Anzahl der aktiven Objekte in diesem Container an.
m_SearchOpened: gibt an, ob momentan eine Suche nach Objekten geöffnet ist.
m_SearchPosition: ist ein iterator, der auf das bei einer Suche als nächstes zu prüfende Entity zeigt. Er zeigt immer auf ein Element der m_XList.
m_SearchActives: gibt an, ob bei der Suche nur nach aktiven Objekten gesucht wird.
m_SearchSingleQuads: gibt an, ob bei der Suche Intervalle, bei denen das m_MultipleQuads-Flag gesetzt ist, ignoriert werden sollen.

3.2.1 Konstruktor und Destruktor

Im Konstruktor wird die Anzahl der aktiven Objekte auf 0 gesetzt und alle Flags, welche die Suche betreffen, auf false gesetzt. Der Destruktor gibt lediglich den Speicherplatz der Klassenvariablen frei.

3.2.2 insertEntity

Diese Methode fügt ein Entity in diesen IntervalListContainer ein. Dazu werden zunächst aufgrund der Bounding Box des Entities drei Intervalle erzeugt, eins für jede Dimension. Nun wird für jedes Interval die jeweilige Liste soweit durchlaufen, bis die korrekte Position des Intervalls in der Liste gefunden ist, wo es dann sortiert eingefügt wird. Ist das Entity aktiv, wird am Ende der Methode der Zähler m_NumActives inkrementiert. Der Aufwand dieser Methode ist linear zur Anzahl der bereits eingefügten Entities.

3.2.3 removeEntity

Diese Methode löscht ein Entity aus diesem IntervalListContainer. Dazu werden alle drei Intervallisten durchlaufen und für jedes Interval überprüft, ob es auf das zu löschende Entity verweist. Diese Intervalle werden dann aus den jeweiligen Listen entfernt. Bei der m_XList muss zusätzlich überprüft werden, ob das Inteval gelöscht werden soll, das der momentanen m_SearchPosition entspricht. In diesem Fall muss m_SearchPosition inkrementiert werden. Wird ein aktives Objekt gelöscht, wird m_NumActives dekrementiert. Falls das Entity nicht in diesem Container gefunden wird, hat der Aufruf der Methode keinerlei Auswirkung. Der Zeitaufwand ist linear zur Anzahl der eingefügten Objekten.

3.2.4 changeNumActives

Diese Methode ändert den Zähler m_NumActives. Wird als Parameter true übergeben, wird der Zähler inkrementiert, ansonsten dekrementiert. Diese Methode nimmt keinerlei Prüfung vor, ob der Zähler danach noch wirklich mit der Anzahl der aktiven Entities in dem Container übereinstimmt, und sollte deshalb nur dann aufgerufen werden, wenn sich die Anzahl tatsächlich ändert. Der Zeitaufwand der Methode ist konstant.

3.2.5 actualizeLists

Diese Methode passt die Intervalle den geänderten Bounding Boxes der Objekte an, nachdem diese bewegt wurden. Dazu wird jede Liste durchlaufen und für aktive Objekte das jeweilige Interval aus der Bounding Box neu ermittelt. Aus Effizienzgründen werden die Listen anschliessend nicht automatisch sortiert, dieser Aufruf muss explizit erfolgen. Die Komplexität ist linear zur Anzahl der eingefügten Entities.

3.2.6 sortLists

Diese Methode ruft für jede IntervalListe sortOneList (3.2.7) auf, welches die Listen sortiert. Die Komplexität ist im average case linear (siehe auch sortOneList(3.2.7).

3.2.7 sortOneList

Diese Methode sortiert eine einzelne Intervalliste. Dazu wird ein modifizierter Shakersort verwendet, der wie folgt funktioniert:
Die Liste wird solange durchlaufen, bis ein Entitypaar gefunden wird, das nicht in sortierter Reihenfolge ist. Auf diese Stelle wird ein Marker gesetzt, von dem aus die Liste rückwärts durchlaufen wird, bis die korrekte Position des zweiten Entities des Paares gefunden ist. Es wird nun an diese Stelle verschoben. Der Algorithmus springt nun vor zum Marker, von welchem aus er die Liste vorwärts durchläuft und nach weiteren unsortierten Entitypaaren sucht.
Die Komlexität dieses Algorithmus ist prinzipiell O(n²). Da die Physikengine jedoch mit relativ kleinen Zeitintervallen und somit kleinen Bewegungen rechnet, sind die Listen im Regelfall schon gut vorsortiert, so dass im average case eine Komplexität von O(n) erreicht wird. Eine genauere Analyse der Komplexität ergibt

v = n + t - 1

wobei

v: Anzahl der Vergleiche
t: Anzahl der unbedingt nötigen Vertauschungen, wenn nur nebeneinanderliegende Elemente vertauscht werden dürfen ³

3.2.8 getNumActives

Diese Methode gibt den momentanen Wert von m_NumActives zurück, welcher der Anzahl der aktiven Objekte im Container entspricht. Die Komlexität der Methode ist konstant.

3.2.9 initSearch

Diese Methode initialisiert die Suche nach Objekten. Dazu wird zunächst abgeprüft, ob bereits eine Suche geöffnet ist. Ist dies der Fall, bricht die Methode mit einer Warning über den Logger ab. Anderenfalls wird das m_SearchOpened-Flag gesetzt, die Suchposition auf den Beginn der m_XList gesetzt und die booleschen Variablen m_SearchActives und m_SearchSingleQuads entsprechend den Übergabeparametern gesetzt. Die Komplexität dieser Methode ist konstant.

3.2.10 getNextEntity

Diese Methode liefert das nächste Entity einer Suche. Ist keine Suche geöffnet, bricht die Methode mit einer Warning auf dem Logger ab. Ansonsten wird das Element der momentanen Suchposition m_SearchPosition überprüft, ob es die von den Flags m_SearchActives und m_SearchSingleQuads geforderten Nebenbedingungen erfüllt. Falls ja, wird m_SearchPosition inkrementiert und das zuvor gefundene Element zurückgegeben. Falls nein, wird das nächste Element geprüft. Erreicht die Suche das Ende der m_XList, wird m_SearchOpened auf false gesetzt und NULL zurückgegeben. Die Komplexität dieser Methode ist im average case konstant.

3.2.11 closeSearch

Diese Methode wird für das explizite Schliessen einer Suche benötigt. Sie setzt lediglich m_SearchOpened auf false. Die Komplexität ist konstant.

3.2.12 getOverlappingBoundingBoxes

Diese Methode ermittelt alle Bounding Box Überlappungen innerhalb dieses Containers und fügt sie zum übergebenen PairSet hinzu. Zwei Bounding Boxes überlappen sich, wenn sich in allen drei Dimensionen ihre Intervalle überlappen.
Zur Überprüfung werden nacheinander die Intervallisten für x, z und y durchlaufen⁴ und auf Überlappungen überprüft. Es werden nur Überlappungen abgespeichert, die in den vorhergehenden Listen ebenfalls gefunden wurde. Der Algorithmus für eine einzelne Liste funktioniert wie folgt:

Zunächst wird eine leere opened-Liste erzeugt. Diese Liste soll alle Intervalle enthalten, die zum Vergleichen mit einem Intervall noch benötigt werden.
Nun wird iterativ durch alle Elemente der Liste gelaufen. Jedes Intervall muss mit jedem Intervall der opened-Liste auf Überlappung überprüft werden.
So gefundene Überlappungen werden zu einem sortierten Pair zusammengefasst und abgespeichert, falls sie in der vorhergehenden Liste ebenfalls gefunden wurden.
Intervalle der opened-Liste, die sich mit einem Intervall der Dimensionsliste nicht überlappen, müssen ihren Endpunkt vor dem Beginn des anderen Intervalls haben, da die Dimensionslisten sortiert sind. Folglich können sie auch keine Überlappung mit allen weiteren Intervallen haben und können somit aus der opened-Liste entfernt werden.
Nachdem das Element aus der Dimensionsliste mit der gesamten opened-Liste überprüft wurde, muss es selbst zur opened-Liste hinzugefügt werden.

Die Komplexität dieser Methode ist O(n log(n)), falls die Objekte relativ zur Listengrösse klein sind und ihre Positionen annähernd gleichverteilt in der xz-Ebene liegen.

3.2.13 debug

Diese Methode checkt alle Intervallisten, ob sie sortiert sind. Dazu wird mit adjacent_find überprüft, ob zwei Elemente in der falschen Reihenfolge in der Liste sind. Wird auf diese Weise eine Inkonsistenz gefunden, wird der Fehler über den Logger ausgegeben und das Programm abgebrochen. Diese Methode dient nur zum debuggen, deshalb kann sich Funktionalität und Implementierung schnell ändern. Für genaue Informationen bitte die Dokumentation in intervalListContainer.h lesen.

3.2.14 dump

Diese Methode gibt den Inhalt des Containers über den Logger aus. Sie ist eine reine Debug-Methode, deren Implementation und Funktionalität sich schnell ändern kann. Für genaue Informationen bitte die Dokumentation in intervalListContainer.h lesen. Momentan werden lediglich alle Elemente der m_XList ausgegeben, zusammen mit ihren Flags.

3.3 Die Klasse ContainerTree

Die Klasse ContainerTree stellt die zentrale Schnittstelle der Optimierungsstruktur dar und verwaltet die einzelnen IntervalListContainer. Sie besitzt folgende Klassenvariablen:

ms_ContainerLength: ist ein statischer float-Wert, der die Kantenlänge eines Blattes im Baum in Metern definiert.
ms_TreeDepth: ist eine statische Variable, die die Tiefe des Baumes angibt. Hierbei bedeutet eine Baumtiefe von 0, dass der Baum nur aus seienr Wurzel besteht.
ms_NodeOffsets: ist ein statisches int-array, welches Offsets zur Berechnung von Knotennummern enthält.
ms_NumEdgeNodes: ist ein statischer int-Wert, welcher angibt, wieviel Blätter an einer Kante des aufgebauten Quad-Trees liegen.
m_pNodes: ist ein array von Pointern auf die IntervalListContainer der einzelnen Knoten. Die array-Positionen der Knoten lassen sich wie in Kapitel 2.16 beschrieben berechnen.
m_pQuads: ist ein array von Pointern auf die Blätter des Baumes. Diese Pointer sind redundant zu den Blatt-Pointern in m_pNodes, aber durch eine andersartige Sortierung des arrays ermöglichen sie eine schnelle Berechnung der array-Position zu einer gegebenen Weltkoordinate.
m_pActiveList: ist ein Pointer auf den IntervalListContainer, in dem die aktiven Entities, welche sich nicht in Blättern befinden, verwaltet werden.
m_QuadLut: ist eine Lookup-table, mit der man aus der Position des Entities im m_pQuads-array seine Position im m_pNodes-array ermitteln kann.
m_EntityStack: ist vom Typ stack<PhysicalEntity*, deque<PhysicalEntity*> >. Es dient zur Speicherung von Pointern auf Entities während der moveEntities-Methode (3.3.6).
m_NodenrStack: ist ein Stack, der zum Speichern von Knotennummern dient. Er wird in den Methoden moveEntities (3.3.6) und getOverlappingBoundingBoxes (3.3.11) verwendet.
m_SearchOpened: gibt an, ob momentan eine Suche initialisiert ist.
m_SearchNodes: ist ein Stack von Integern, auf welchem diejenigen Knoten gespeichert werden, die bei einer Suche noch durchsucht werden müssen.
m_SearchBoundingBox: ist die bei der Suche verwendete Bounding Box, fallsüber eine Bounding Box gesucht wird. Sie ist wie in Kapitel 2.5 beschrieben aufgebaut.
m_BoundedSearch: gibt an, ob bei der Suche eine Bounding Box verwendet werden soll.

3.3.1 Konstruktor und Destruktor

Im Konstruktor werden alle Klassenvariablen initialisiert. Allerdings werden die verwendeten arrays noch nicht angelegt, weshalb das explizite Aufrufen von init (3.3.2) nötig ist. Im Destruktor werden alle angelegten IntervalListContainer wieder über ihren Destruktor gelöscht. Dabei ist zu beachten, dass die von m_pQuads indizierten IntervalListContainer nicht gelöscht werden müssen, da sie nur redundant zu m_pNodes sind und beim Löschen dieses arrays bereits gelöscht wurden.

3.3.2 init

Diese Methode legt die arrays m_pNodes, m_pQuads und m_QuadLut an und initialisiert ihre Variablen. Zunächst wird m_pNodes initialisiert. Danach wird für alle Blätter in einer Schleife über die Baumtiefe berechnet, welche Position sie in diesem Sub-Baum hätten. Der so errechnete Wert wird in m_QuadLut gespeichert, und der entsprechende Pointer aus m_pNodes in m_pQuads gespeichert. Die Komplexität ist O(n log(n)) bezüglich der Anzahl der Blätter des Baumes.

3.3.3 overlappingBoundingBoxes

Dies ist eine statische Methode, welche zwei wie in Kapitel 2.5 beschrieben aufgebaute Bounding Boxes auf Überlappungen prüft. Dazu wird für alle drei Positionen getestet, ob die jeweiligen Startpunkte der Intervalle vor dem Endpunkt des Intervalls der anderen Bounding Box liegt. Scheitert einer dieser Tests, kann false zurückgegeben werden, ansonsten true. Die Komplextität der Methode ist konstant.
Wegen Problemen mit der debug-Methode (3.3.15) wird in der momentanen Implementation bei den Vergleichen eine Toleranz verwendet. Dies wird entfernt werden, sobald debug-Methode nicht mehr benötigt wird.

3.3.4 insertEntity

Diese Methode fügt ein Entity in den ContainerTree ein. Dazu wird zunächst mit getQuadNumbers (3.3.12) ermittelt, über welche Blätter des Baumes sich das Entity erstreckt. Handelt es sich hierbei um nur ein Blatt, kann das Entity direkt in den entsprechenden IntervalListContainer eingefügt werden. Ansonsten muss unterschieden werden, ob das Entity aktiv ist oder nicht. Im ersten Fall wird das Entity in den zugehörigen Knoten, welcher mit getNodeNumber (3.3.13 ermittelt wird, eingefügt. Zusätzlich wird es in die m_pActiveList eingefügt. Inaktive Entities werden auf gleiche Weise wie die aktiven in den zugehörigen Knoten eingefügt. Dazu werden sie in alle Blätter, die sie überdecken, eingefügt. Hierbei wird das Multiple-Quad-Flag in den Intervallen gesetzt. Die Komplexität dieser Methode wird durch das Einfügen in die IntervalListContainer bestimmt, beträgt also O(n), wobei n die Anzahl der Entities im entsprechenden IntervalListContainer ist.

3.3.5 toggleActive

Diese Methode ändert das active-Flag eines Entities, und führt alle dadurch nötigen Änderungen im ContainerTree durch. Dazu müssen zunächst mit getQuadNumbers (3.3.12) alle überdeckten Blätter ermittelt werden. Handelt es sich hierbei um nur ein Blatt, genügt es, das Flag im Entity zu ändern und den Zähler der aktiven Entities im entsprechenden IntervalListContainer zu ändern. Ansonsten muss unterschieden werden, ob das Entity aktiv oder inaktiv gesetzt werden soll. Wird es inaktiv gesetzt, muss im entsprechenden Knoten der Zähler der aktiven Entities dekrementiert werden, das Entity aus der m_pActiveList entfernt werden und in allen von seiner Bounding Box überdeckten Blättern eingefügt werden, wobei das Multiple-Quad-Flag in den Intervallen gesetzt wird. Soll das Entity aktiv gesetzt werden, wird es aus den überdeckten Blättern entfernt, in die m_pActiveList eingefügt und der Zähler der aktiven Entities im entsprechenden Baumknoten erhöht. Die Komplexität wird durch die Einfüge- und Löschoperationen bestimmt, und beträgt deshalb O(n), wobei n die Anzahl von Entities in den entsprechenden IntervalListContainern ist.

3.3.6 moveEntities

Diese Methode berechnet die pjhysikalische Bewegung aller aktiven Entities während eines gegebenen Zeitintervalls und hält den ContainerTree konsistent. Dazu wird für alle Knoten abgefragt, ob sie aktive Entities enthalten. Wenn ja, wird eine Suche nach diesen Entities gestartet und die Entities werden dem Zeitintervall entsprechend rotiert und bewegt. Für die so geänderte Bounding Box muss überprüft werden, ob sie sich immer noch in diesem Knoten befindet. Tut sie dies nicht, wird das Entity aus diesem IntervalListContainer entfernt und temporär auf dem m_EntityStack zwischengespeichert. Die neu berechnete Knotennummer wird auf dem m_NodenrStack zwischengespeichert. Nach dem Durchlaufen jeder Liste müssen die Intervalle mit IntervalListContainer::actualizeLists (3.2.5) den neuen Bounding Boxes angepasst werden, anschliessend werden die Listen mit IntervalListContainer::sortLists (3.2.6) sortiert. Sind alle Knoten durchlaufen, muss zusätzlich die m_pActiveList aktualisiert und sortiert werden, da diese sich durch Seiteneffekte verändert haben kann. Anschliessend werden alle Entities vom m_EntityStack wieder in die im m_NodenrStack abgespeicherten Knoten eingefügt. Die Komplexität der Methode ist linear zur Gesamtzahl der Entities.

3.3.7 initSearch

Diese Methode initialisiert die Suche nach Entities. Zunächst wird überprüft, ob die letzte Suche geschlossen ist, anderenfalls bricht die Methode mit einer Warning über den Logger ab. Dann werden mit calculateNodeNumbers (3.3.14) diejenigen Knoten ermittelt und auf dem m_SearchNodes-Stack abgelegt, welche von der Suche betroffen sind. Alle Flags werden den Parametern entsprechend gesetzt und für den obersten IntervalListContainer wird eine Suche geöffnet. Die Komplexität dieser Methode ist konstant.

3.3.8 initNodeSearch

Diese Methode initialisiert die Suche in nur einem Knoten. Dazu wird zunächst geprüft, ob die letzte Suche geschlossen ist, anderenfalls bricht die Methode mit einer Warning über den Logger ab. Anschliessend werden alle Flags den Parametern entsprechend gesetzt, der Knoten auf dem m_SearchNodes-Stack abgelegt und die Suche für den Knoten initialisiert. Die Komplexität dieser Methode ist konstant.

3.3.9 getNextEntity

Diese Methode liefert das nächste Entity einer Suche. Dazu wird zunächst überprüft, ob m_SearchOpened gesetzt ist, ansonsten wird mit einer Fehlermeldung über den Logger abgebrochen. Danach wird solange in demjenigen IntervalListContainer, das zuoberst auf dem m_SearchNodes-Stack liegt, nach Entities gesucht, bis ein Entity gefunden wird, das alle Nebenbedingungen (wie aktiv, Multiple-Quad-Flag, ...) erfüllt sind. Bekommt man als Zwischenresultat NULL, wird das oberste Element vom m_SearchNodes-Stack entfernt und für den nächsten IntervalListContainer des Stacks die Suche initialisiert. Wird auf diese Weise ein Entity gefunden, das die Nebenbedingungen erfüllt, wird dieses zurückgegeben. Wird zuvor die letzte Knotennummer vom m_SearchNodes-Stack entfernt, wird m_SearchOpened auf false gesetzt und NULL zurückgegeben. Die Komplexität dieser Methode ist im average case konstant.

3.3.10 closeSearch

Diese Methode dient zum expliziten Schliessen einer Suche. Dazu wird im momentan aktuellen IntervalListContainer die Suche geschlossen, der m_SearchNodes-Stack geleert und das m_SearchOpened-Flag auf false gesetzt. Die Komplexität der Methode ist konstant.

3.3.11 getOverlappingBoundingBoxes

Diese Methode durchsucht den ContainerTree nach überlappenden Bounding Boxes. Dies dient zur Kollisionserkennung, daher sind nur solche Kollisionen interessant, bei welchen mindestens ein Entity aktiv ist.
Der Algorithmus unterscheidet drei mögliche Fälle:

Es können Kollisionen in einem Blattknoten stattfinden. Dazu wird einfach für alle Blätter IntervalListContainer::getOverlappingBoundingBoxes (3.2.12 aufgerufen und die gefundenen Kollisionen dem Ergebnis hinzugefügt.
Es können in der m_pActiveList Kollisionen auftreten. Hierzu wird ebenfalls IntervalListContainer::getOverlappingBoundingBoxes aufgerufen.
Zwischen Elementen der m_pActiveList und inaktiven Entities der Blattknoten können Kollisionen auftreten. Dazu wird die m_pActiveList linear durchlaufen. Für jedes Element werden mittels getQuadNumbers (3.3.12) die überdeckten Blätter ermittelt. Jedes dieser Blätter wird nun durchlaufen und alle seine Entities werden auf Kollision mit dem Entity der m_pActiveList überprüft. Befindet sich in der x-Dimension der Startwert eines Entities eines Blattes hinter dem Endwert des Entities der m_pActiveList, kann davon ausgegangen werden, dass dies auch für alle folgende Entities des Blattes gilt. Die Suche in diesem Blatt kann beendet werden. Beim Hinzufügen von Entitypaaren zum Ergebnis ist darauf zu achten, dass die Paare in sich sortiert sein müssen.

Der Hauptaufwand der Methode liegt im Durchlaufen des dritten Falles. Während das Überprüfen eines einzelnen IntervalListContainer O(n log(n)) beträgt (siehe Kapitel 3.2.12), beträgt hier der Aufwand O(mn), wobei m die Anzahl der Entities in der m_pActiveList ist und n die Anzahl der Entities in vier aneinandergrenzenden Blättern⁵. Allerdings ist die Anzahl der aktiven Entities, die sich nicht in Blättern befinden, relativ gering, so dass dieser Aufwand vertretbar ist.

3.3.12 getQuadNumber

Diese Methode errechnet aus der Bounding Box eines Entities die von ihm überdeckten Blätter. Dazu werden diejenigen Blätter berechnet, in welchen die Ecke der Bounding Box mit minimalen x-, y-, und z-Wert und die Ecke der Bounding Box mit maximalen x-, y- und z-Wert liegt. Da das m_pQuads-array zeilenweise durchnummeriert ist, kann dies durch einfache Additionen und Divisionen errechnet werden. Alle Blätter, die zwischen den zwei errrechneten Blättern liegen, werden von der Bounding Box überdeckt. Die Komplexität dieser Methode ist konstant.

3.3.13 getNodeNumber

Diese Methode errechnet aus den Nummern zweier Blättern die Nummer des kleinsten Knotens, der beide Blätter enthält. Es gilt zu beachten, dass die übergebenen Blattnummern die Inidzes im reihenweise sortierten m_pQuads-array darstellen, nicht die in m_pNodes. Deshalb müssen diese Werte zunächst mit Hilfe der m_QuadLut umgewandelt werden. Anschliessend gilt: Die Knotennummer ist diejenige, die man erhält, wenn man von diesen Werten immer die letzten zwei Bit streicht, bis diese identisch sind, und dann noch den passenden Offset addiert. Der Offset ergibt sich aus der Tiefe des Knotens im Baum, welche sich wiederum aus der Anzahl der gestrichenen Bits ermitteln lässt. Siehe hierzu auch Kapitel 2.16. Die Komplexität der Methode ist linear zur Tiefe des Baumes.

3.3.14 calculateNodeNumbers

Diese Methode errechnet alle Knoten, welche sich mit einer gegebenen Bounding Box überlappen, und fügt ihre Indizes zu einem Stack hinzu.
In der momentanen Implementation werden mangels eines effizienten Algorithmus alle Knoten hinzugefügt. Dies verursacht keinerlei Programmfehler, erfordert jedoch in anderen Programmteilen einen erhöhten Rechenaufwand. Dieses Problem wird baldmöglichst gefixt.

3.3.15 debug

Diese Methode dient zum automatischen debuggen und testet den ContainerTree auf Inkonsistenzen. Seine Tests und seine Implementierung können sich öfters ändern, für genauere Informationen deshalb die Dokumentation in containerTree.h lesen.

3.3.16 dump

Diese Methode gibt den Inhalt aller Knoten des Baumes über den Logger aus. Die Art der Ausgabe und die Implemetierung kann sich häufig ändern, für genauere Informationen deshalb die Dokumentation in containerTree.h lesen.

3.3.17 getNodeBoundingBox

Dies ist eine Hilfsmethode der debug-Methode (3.3.15). Sie berechnet die Bounding Box eines Knotens des ContainerTree. Zunächst wird aus der Knotennummer die Tiefe des Knotens im Baum ermittelt, anschliessend der Offset der Knotennummer abgezogen. Aus der Bounding Box des Root-Knotens lassen sich nun sukzessive die Bounding Boxes der Kindknoten errechnen, bis hin zur gewünschten Bounding Box. Die Komplexität der Methode ist linear zur Baumtiefe.

4 Ausblick

Dieser Entwurf des ContainerTree bietet momentan noch keine effizienten Algorithmen für das Bewegen einzelner Entities, was jedoch nötig sein wird⁶. Eventuell können auch eineige Methoden intern optimiert werden.

1: also das sukzessive Aufteilen des Gebietes in Quadrate
2: das sind alle Objekte, die sich nicht bewegen oder rotieren
3: Also den Vertauschungen eines normalen Shaker Sort. Diese Vertauschungen werden jedoch hier keinesfalls vorgenommen, sie dienen nur zur Berechnung der Vergleiche. Ist die korrekte Position des Intervalls ermittelt, erfolgt die Verschiebung unabhängig von der Entfernung in konstanter Zeit.
4: Die y-Liste wird als letztes durchlaufen, da sie die Höheninformation enthält und somit im Regelfall die meissten Überlappungen hat
5: Da die Ausdehnung eines Entities nicht die Kantenlänge eines Blattes überschreiten sollte, überdeckt es im worst case vier Blätter
6: zum Beispiel für vom Netzwerk hervorgerufene Synchronisationsbefehle

This document was translated from L^AT_EX by H^EV^EA.

Neverending ODC Die interne Optimierungsstruktur der Physikengine Version 1.1.1