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

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 , 分别。

首先，我们选择一个多边形(最终我想找到一个看起来最适合根分割平面的多边形)，然后我们遍历我们的原始列表，检查 3 种情况之一:

(注意 - 为了简洁起见，我将我们的根分区多边形命名为 root)

• POSITION_FRONT : 我们知道列表中的当前多边形位于 root 的前面，因此我们很自然地将此多边形添加到前面的列表中。

• POSITION_BACK : 和position一样，唯一不同的是这个多边形在root的后面。

• POSITION_SPLIT : 我们无法确定这个多边形是在 root 的前面还是后面，所以我们将它分成两部分，并将它的前面和后面的部分插入到各自的列表中。 p>

最后，一旦我们将多边形划分为前后列表，我们将进一步 segmentation 我们的空间，使用根作为初始 segmentation 的基础。

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

现在，我们执行非常相似的操作序列，主要区别在于我们进一步 segmentation 已经划分的空间，直到每个多边形在节点树中都有一个给定位置，它在前面或后面它的父节点。当然，我们递归地这样做。

我目前看到的问题在于 POSITION_SPLIT上面 switch 语句中的案例评估:

        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(...)生成检查以查看其接收列表是否为空。如果是，则什么都不做，并且已完成对该列表的递归 segmentation 。

由于这两个因素，我不禁认为，在POSITION_SPLIT案例评估，第二次调用SplitSpace(...)没有用:在进行第二次调用(以适应拆分的后面部分)之前，列表将用完。

问题

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

Answer 1

您应该将 BSPTree 构造函数重构为您的递归逻辑并应用分而治之。
1. 输入是一个多边形列表。
2. 选择一个分割平面，这是BSP 中的当前节点。
3. 将多边形 segmentation 为前后。
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;