Двоичное пространственное разделение - ошибка в логике разбиения пространства

Question

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

Вот конструктор (объяснение следует):

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 соответственно.

Сначала мы выбираем Polygon (в конце концов, я бы хотел найти многоугольник, который наилучшим образом подходит для плоскости разбиения корня), а затем мы перебираем исходный список, проверяя один из 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, мы укажем указатель, который содержит этот многоугольник в списке после присвоения его временному.

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

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

Вопрос

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

Answer 1

Вы должны реорганизовать конструктор BSPTree как свою рекурсивную логику и применить разделение и завоевание.
1. Ввод - список полигонов.
2. Выберите плоскость разделения, это текущий узел в BSP.
3. Разделить полигоны спереди и сзади.
4. Передайте передний список этой же функции (рекурсия), верните дочерний узел.
5. Передайте задний список этой же функции (рекурсия), верните дочерний узел.
6. Верните текущий узел.

bspNode_t* BuildBSP(const polygonList_t& list) 
{ 
polygonList_t front, back; 
Polygon* rootSplitter = list[ 0 ]; 
bspNode_t* currentNode = new bspNode_t(rootSplitter); 

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

currentNode->frontChild = BuildBSP(front); 
currentNode->backChild = BuildBSP(back); 

return currentNode; 

}