🔒 Locked

Question for BSP trees

Started by kbundy023 Nov 19, 2008 at 5:13 AM 1 replies 800+ views

Original Post

Nov 19, 2008 at 5:13 AM

Hello I am new to Graphics programming. I have a little bit of confusion about building the BSP Tree. If I have a scene with circles and squares, do I select the plane that can build a well balanced trees first. Assume I picked a plane from one of the circles (I know I have to partition other circles too), do I start to subdivide the other planes from the same circle or do I store the whole circle in one node. Maybe a bit of confusion too in my question but I wish you guys can help me. Thank you.

doronf

Nov 19, 2008 at 5:46 AM

You should add only static objects to the scene (elements that don't move). Once you picked the initial plane, you have to subdivide all the other planes (from all static objects) and add them to the tree.
If your objects are dynamic, you only handle them after the tree is ready.
By the way, if all your objects are dynamic, you should not use BSP in the first place because you will spend too much time updating the tree each time the objects move.

kbundy023

Nov 21, 2008 at 12:21 AM

Quote:
Original post by doronf
You should add only static objects to the scene (elements that don't move). Once you picked the initial plane, you have to subdivide all the other planes (from all static objects) and add them to the tree.
If your objects are dynamic, you only handle them after the tree is ready.
By the way, if all your objects are dynamic, you should not use BSP in the first place because you will spend too much time updating the tree each time the objects move.

Thank ...

I have a question from the wiki

http://www.cgafaq.info/wiki/BSP_tree_construction

void Build_BSP_Tree (BSP_tree *tree, list polygons)
{
polygon *root = polygons.Get_From_List ();
tree->partition = root->Get_Plane ();
tree->polygons.Add_To_List (root);
list front_list, back_list;
polygon *poly;
while ((poly = polygons.Get_From_List ()) != 0)
{
int result = tree->partition.Classify_Polygon (poly);
switch (result)
{
case COINCIDENT:
tree->polygons.Add_To_List (poly);
break;
case IN_BACK_OF:
back_list.Add_To_List (poly);
break;
case IN_FRONT_OF:
front_list.Add_To_List (poly);
break;
case SPANNING:
polygon *front_piece, *back_piece;
Split_Polygon (poly, tree->partition, front_piece, back_piece);
back_list.Add_To_List (back_piece);
front_list.Add_To_List (front_piece);
break;
}
}
if ( ! front_list.Is_Empty_List ())
{
tree->front = new BSP_tree;
Build_BSP_Tree (tree->front, front_list);
}
if ( ! back_list.Is_Empty_List ())
{
tree->back = new BSP_tree;
Build_BSP_Tree (tree->back, back_list);
}
}

The one with getPlane() .... What does that mean? Are Plane and Polygon completely different thing. I thought the bsp tree divide the polygons by the best selected polygon. Last thing, what is the algorithm to find the a good partition plane?

Thank you.

Please help ... I know my question maybe abit simple but I want to understand more.

[Edited by - kbundy023 on November 22, 2008 4:21:40 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.