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