c++algorithmbsp-tree

How can I merge 2 bsp trees?


I am in work of implementing csg objects with bsp trees. For this purpose I need to merge 2 bsp trees and work with them, but I don't quite understand how to implement this merging. I know how to insert new polygons into bsp tree. But what could be possible solution for merging 2 bsp trees?

I have a really general idea which looks like this code snippets, but I don't even know if I go the right way:

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

The only thing I want is just a general idea/path with which I can go to implement this algorithm. Thanks.


Solution

  • Well, it is quite simple, if you already have function, that inserts vector of polygons. Just inserting polygons of B tree into A tree. Something like this:

    void BSPMerge(std::unique_ptr<bsp_node>& A, std::unique_ptr<bsp_node>& B)
    {
        // NOTE: Insert B part to A
        BSPInsert(A, B->Polygons);
    
        if(B->Front)
            BSPMerge(A, B->Front);
        if(B->Back)
            BSPMerge(A, B->Back);
    }