二进制空间分区 - 空间分区逻辑错误

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

简而言之，我们收到一个类型定义std::vector< Polygon* >，其中包含任意数量的堆分配的 Polygon 对象。然后，我们要将它们分为两类：某个中心元素前面的元素和后面的元素。当然，我们声明了两个相同 typedef 的列表，并分别称它们为 front 和 back。

首先，我们选择一个多边形

(最终我想找到一个似乎最适合根分区平面的多边形(，然后我们遍历原始列表，检查以下 3 种情况之一：

(注意 - 为了简洁起见，我只是将我们的根分区多边形称为 root(

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

现在，我们

执行非常相似的操作序列，关键区别在于我们进一步细分已经分区的空间，直到每个多边形在节点树中都有一个给定的位置，该位置位于其父节点的前面或后面。当然，我们以递归方式执行此操作。

我目前看到的问题在于上面 switch 语句中的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(...)的第二次调用是没有用的：在进行第二次调用(以适应拆分的后半部分(之前，列表将用尽。

问题

那么，这个问题的解决方案是什么，至少能让我回到正确的轨道上？

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;

}