3

所以我一直在实现我的第一个 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 对象的 typedefed。然后我们想把它们分成两类：在某个中心元素前面的和后面的。自然地，我们声明了两个具有相同 typedef 的列表，front并back分别称它们为 和 。

首先，我们选择一个多边形（最终我想找到一个看起来最适合根分区平面的多边形），然后我们遍历我们的原始列表，检查以下三种情况之一：

（注意 -为简洁起见，我只是将我们的根分区多边形命名为root）

  • POSITION_FRONT：我们知道列表中的当前多边形在root前面，所以我们自然地将这个多边形添加到我们的前面列表中。

  • POSITION_BACK: 与 position 相同，唯一的区别是这个多边形在root后面。

  • 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上面 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(...)产生一个检查，看看它收到的列表是否为空。如果是这样，则什么都不做，并且该列表的递归细分已经完成。

由于这两个因素，我不禁认为，在POSITION_SPLIT案例评估中，第二次调用是没有用的：在第二次调用（以容纳拆分的后面部分）SplitSpace(...)之前，列表将被耗尽。

问题

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

4

1 回答 1

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;

}

于 2013-10-09T05:00:26.163 回答