Разделение двоичного пространства — Ошибка в логике разделения пространства

Итак, я реализовал свой первый BSP Tree, и я думаю, что нашел ошибку в моей логике. Я довольно растерян, чтобы понять, как я мог бы на самом деле правильно это изменить

Вот конструктор (пояснение приведено ниже):

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 );
}

В двух словах, мы получаем typedeffed std::vector< Polygon* > с произвольным числом выделенных в куче объектов Polygon. Затем мы хотим разделить их на две категории: те, которые находятся перед определенным центральным элементом, и те, которые находятся позади. Естественно, мы объявляем два списка одного и того же typedef и вызываем их front а также backсоответственно.

Сначала мы выбираем полигон (в конце концов я хотел бы найти полигон, который, как представляется, лучше всего подходит для корневой плоскости разбиения), а затем мы перебираем наш первоначальный список, проверяя один из 3 случаев:

(НОТА — для краткости, я просто дублирую наш полигон корневого раздела как корень)

• POSITION_FRONT: Мы знаем, что наш текущий многоугольник в списке находится перед корень, поэтому мы естественным образом добавляем этот многоугольник в наш первый список.

• POSITION_BACK: То же, что и позиция, единственное отличие в том, что этот многоугольник позади корень.

• POSITION_SPLIT: Мы не можем определить, находится ли этот многоугольник перед корень или за ним, поэтому мы разбиваем его на две части и вставляем переднюю и заднюю части в соответствующие списки.

Наконец, как только мы разделили наши многоугольники на их передний и задний списки, мы еще больше поделили наше пространство, используя корень в качестве основы для начального деления.

void BSPTree::SplitSpace( bspNode_t* node, polygonList_t& polygons )
{
if ( polygons.size() == 0 ) return;

// grab the first polygon within the list,
// and then subtract it from the list itself.
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;
}
}

Теперь мы выполняем очень похожую последовательность операций, главное отличие в том, что мы дальнейшее подразделение уже разделенного пространства до тех пор, пока каждый многоугольник не займет заданную позицию в дереве узлов, которое находится либо перед, либо позади его родительского узла. Конечно, мы делаем это рекурсивно.

Проблема, которую я сейчас вижу, заключается в POSITION_SPLIT оценка случая в заявлении о переключении выше:

        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 ); // here
SplitSpace( node->back, polygons );  // and here
}

В сочетании с двумя другими факторами:

• Для каждого многоугольника, полученного от заданного опорного параметра polygonsмы pop_back() указатель, который удерживает этот многоугольник в списке после присвоения ему временного объекта.

• Связывая с вышеупомянутым, каждый призыв к SplitSpace(...) выдает проверку, чтобы убедиться, что полученный список пуст. Если это так, ничего не сделано, и рекурсивное подразделение было завершено для этого списка.

Из-за этих двух факторов я не могу не думать, что в POSITION_SPLIT оценка случая, второй вызов SplitSpace(...) бесполезен: список будет исчерпан до второго вызова (для размещения назад часть раскола) сделано.

Вопрос

Итак, каково решение этой проблемы, которое, по крайней мере, заставит меня вернуться на правильный путь?