Also, ich habe meinen ersten BSP-Baum implementiert und ich glaube, ich habe einen Fehler in meiner Logik gefunden. Ich bin ziemlich ratlos, wie ich das richtig umstrukturieren könnte, damit es so funktioniert, wie es sollte.
Hier ist der Konstruktor (eine Erklärung folgt):
BSPTree::BSPTree( const polygonList_t& list )
: mRoot( nullptr )
{
polygonList_t front, back;
auto eol = list.end();
Polygon* rootSplitter = list[ 0 ];
vec3 rootSplitPos;
rootSplitter->GetPosition( rootSplitPos );
for( auto iPoly = list.begin() + 1; iPoly != eol; ++iPoly )
{
vec3 resolvePos;
( *iPoly )->GetPosition( resolvePos );
switch( ResolvePosition( rootSplitPos, resolvePos ) )
{
case POSITION_FRONT:
front.push_back( *iPoly );
break;
case POSITION_BACK:
back.push_back( *iPoly );
break;
case POSITION_SPLIT:
{
Polygon* toSplit = *iPoly;
list.erase( iPoly );
Polygon* outFront = new Polygon;
Polygon* outBack = new Polygon;
SplitPolygon( resolvePos, toSplit, outFront, outBack );
front.push_back( outFront );
back.push_back( outBack );
// finally we kill this one off
delete toSplit;
toSplit = nullptr;
}
break;
}
}
mRoot = BSP_MakeNode();
mRoot->splitter = rootSplitter;
SplitSpace( mRoot, front );
SplitSpace( mRoot, back );
}Zusammengefasst erhalten wir also einen definierten std::vector< Polygon* > mit einer beliebigen Anzahl von auf dem Heap allokierten Polygon-Objekten. Wir wollen diese dann in zwei Kategorien aufteilen: diejenigen vor einem bestimmten Mittelpunktselement und diejenigen dahinter. Natürlich deklarieren wir zwei Listen des gleichen Typs und nennen sie entsprechend front und back.
Zuerst wählen wir ein Polygon aus (letztendlich möchte ich ein Polygon finden, das am besten für eine Wurzelpartitionierungsebene geeignet ist), und dann durchlaufen wir unsere ursprüngliche Liste, um einen der 3 Fälle zu überprüfen:
(HINWEIS - der Einfachheit halber nenne ich unser Wurzelpartitionspolygon einfach root)
-
POSITION_FRONT: Wir wissen, dass unser aktuelles Polygon in der Liste vor root liegt, also fügen wir dieses Polygon natürlich zu unserer vorderen Liste hinzu. -
POSITION_BACK: Genau wie Position, mit dem einzigen Unterschied, dass dieses Polygon hinter root liegt. -
POSITION_SPLIT: Wir können nicht feststellen, ob dieses Polygon vor root oder dahinter liegt. Deshalb teilen wir es in zwei Teile auf und fügen die vorderen und hinteren Teile in ihre entsprechenden Listen ein.
Zuletzt, nachdem wir unsere Polygone in ihre vorderen und hinteren Listen aufgeteilt haben, unterteilen wir unseren Raum weiter, wobei wir root als Grundlage für die anfängliche Unterteilung verwenden.
void BSPTree::SplitSpace( bspNode_t* node, polygonList_t& polygons )
{
if ( polygons.size() == 0 ) return;
// das erste Polygon in der Liste holen
// und es dann aus der Liste entfernen.
Polygon* next = polygons[ 0 ];
polygons.pop_back();
vec3 splitPos;
node->splitter->GetPosition( splitPos );
vec3 toResolve;
next->GetPosition( toResolve );
switch( ResolvePosition( splitPos, toResolve ) )
{
case POSITION_FRONT:
node->front = BSP_MakeNode();
node->front->splitter = next;
SplitSpace( node->front, polygons );
break;
case POSITION_BACK:
node->back = BSP_MakeNode();
node->back->splitter = next;
SplitSpace( node->back, polygons );
break;
case POSITION_SPLIT:
{
Polygon* outFront = new Polygon;
Polygon* outBack = new Polygon;
SplitPolygon( toResolve, next, outFront, outBack );
node->front = BSP_MakeNode();
node->back = BSP_MakeNode();
node->front->splitter = outFront;
node->back->splitter = outBack;
SplitSpace( node->front, polygons );
SplitSpace( node->back, polygons );
}
break;
}
}Jetzt führen wir eine sehr ähnliche Abfolge von Operationen durch, wobei der wesentliche Unterschied darin besteht, dass wir einen bereits unterteilten Raum weiter unterteilen, bis jedes Polygon eine bestimmte Position im Knotenbaum hat, entweder vor oder hinter dem übergeordneten Knoten. Natürlich machen wir das rekursiv.
Das Problem, das ich derzeit sehe, liegt in der Bewertung des POSITION_SPLIT-Falls innerhalb der oben genannten switch-Anweisung:
case POSITION_SPLIT:
{
Polygon* outFront = new Polygon;
Polygon* outBack = new Polygon;
SplitPolygon( toResolve, next, outFront, outBack );
node->front = BSP_MakeNode();
node->back = BSP_MakeNode();
node->front->splitter = outFront;
node->back->splitter = outBack;
SplitSpace( node->front, polygons ); // hier
SplitSpace( node->back, polygons ); // und hier
}Zusammen mit zwei weiteren Faktoren:
-
Für jedes Polygon, das aus dem übergebenen Referenzparameter
polygonserhalten wird, entfernen wir den Zeiger, der dieses Polygon innerhalb der Liste hält, nachdem wir es einem temporären Wert zugewiesen haben. -
In Verbindung mit dem zuvor erwähnten führt jeder Aufruf von
SplitSpace(...)dazu, dass überprüft wird, ob die empfangene Liste leer ist. Ist dies der Fall, wird nichts getan und die rekursive Unterteilung für diese Liste ist abgeschlossen.
Aufgrund dieser beiden Faktoren kann ich nicht anders, als zu denken, dass im POSITION_SPLIT-Falle die zweite Überprüfung von SplitSpace(...) sinnlos ist: Die Liste wird erschöpft sein, bevor der zweite Aufruf (um den back-Teil der Teilung unterzubringen) durchgeführt wird.
Frage
Also, was ist eine Lösung für dieses Problem, die mich zumindest wieder in die richtige Richtung weist?
