如何合并两个BSP树？CSG对象实现中的技术方案问询

我正在基于BSP树实现CSG对象，需要合并两个BSP树，但不清楚具体实现方式。已经掌握向BSP树插入新多边形的方法，想了解合并两个BSP树的可行方案。我有一个初步思路并写出了如下代码片段，不确定方向是否正确，希望得到实现该算法的通用思路或路径。

void
BSPMerge(std::unique_ptr<bsp_node>& A, const std::unique_ptr<bsp_node>& B)
{
    //std::unique_ptr<bsp_node> NewNode = std::make_unique<bsp_node>();
    //NewNode->Polygons = A->Polygons;
    //NewNode->Plane = A->Plane;

    std::vector<polygon> APolygons, AFront, ABack;
    vec4 ASplitPlane = A->Plane;

    std::queue<bsp_node*> TreeNodeQueue;
    TreeNodeQueue.push(B.get());
    while(!TreeNodeQueue.empty())
    {
        bsp_node* Node = TreeNodeQueue.front();
        TreeNodeQueue.pop();

        for(uint32_t i = 0;
            i < B->Polygons.size();
            i++)
        {
            std::vector<polygon> Polygon;
            Polygon.push_back(B->Polygons[i]);
            BSPInsert(A, Polygon);
        }

        if(Node->Front)
            TreeNodeQueue.push(Node->Front.get());
        if(Node->Back)
            TreeNodeQueue.push(Node->Back.get());
    }

    if(A->Front)
        BSPMerge(A->Front, B);
    if(A->Back)
        BSPMerge(A->Back, B);

    //return NewNode;
}

当前代码的问题 #

你的代码存在两个核心问题：

1. 遍历B树节点时，错误地重复插入B树根节点的多边形（B->Polygons[i]），而非当前遍历到的节点的多边形（应该是Node->Polygons[i]），会导致大量冗余插入。
2. 递归合并A的子节点时，又会把整个B树重新插入一遍，进一步放大冗余操作，效率极低。

通用合并思路（基于你已掌握的多边形插入能力） #

方案一：提取B树所有多边形，批量插入A树

这是最直接、适配你现有能力的方案：

• 深度或广度优先遍历B树的所有节点，收集所有节点中的多边形，形成完整的多边形列表。
• 调用你已实现的BSPInsert方法，将收集到的多边形逐个插入到A树中。

方案二：递归节点合并（高效版，适合大型B树）

如果B树规模较大，直接提取所有多边形插入效率偏低，可以采用节点级递归合并：

1. 若B树为空，直接返回；若A树为空，将B树的节点结构和多边形完整复制到A树。
2. 用A树当前节点的分割平面，对B树当前节点的多边形进行分类：前侧、后侧、共面。
3. 共面多边形直接合并到A树当前节点的多边形列表。
4. 前侧多边形递归插入到A树的前子节点（无则创建），后侧多边形递归插入到A树的后子节点（无则创建）。
5. 递归处理B树的前/后子节点，重复上述分割-合并逻辑，将结果合并到A树对应子节点中。

修正后的代码示例（方案一简化版） #

void BSPMerge(std::unique_ptr<bsp_node>& A, const std::unique_ptr<bsp_node>& B) {
    if (!B) return;

    // 插入当前B节点的所有多边形到A树
    for (const auto& poly : B->Polygons) {
        std::vector<polygon> polyVec{poly};
        BSPInsert(A, polyVec);
    }

    // 递归合并B的子节点到A树
    if (B->Front) {
        BSPMerge(A, B->Front);
    }
    if (B->Back) {
        BSPMerge(A, B->Back);
    }
}

内容的提问来源于stack exchange，提问作者Zhukov Artem