#### Archived

This topic is now archived and is closed to further replies.

# Uses of BSP trees?

This topic is 5098 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I recall someone saying once that BSP trees are better suited for _____ areas. I dont remember if the blank was "outside" or "inside". I think it was inside, but Im not sure. Can someone tell me which one it was? Also, I think that they said quadtrees were better suited for the other one; which ever one BSP trees wern''t good for. I dont know anything about quadtrees, and only vaguely know a little about BSP trees. Also is there such thing as Octrees? It sounds familiar. I want to know which data structure is better suited for which type of world, and most importantly, why ? Links to articles or other sources are greatly appreciated. Thanks!

##### Share on other sites
inside

Though you could use BSP trees for outside worlds, there are way better technologies...

cya,
Drag0n

-----------------------------
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to build bigger and better idiots. So far, the universe is winning..." -- Rich Cook

##### Share on other sites
Coughselfplugcough

http://www.3dtechdev.com/tutorials/leafbsp/3dbsptrees.html

-=[ Megahertz ]=-

Coughthankscough

##### Share on other sites
Hey I just read through the article, Megahertz.

I have a question about BSP trees in general that hopefully you or someone else can answer:

The following code to draw the BSP tree is given in the article:

int RenderBSP (BSP_node *node){    int side;    Vector3d Position;    //The current position of the player/viewpoint    Position.x=xpos;    Position.y=ypos;    Position.z=zpos;    if (!node->leaf) {        side=ClassifyPoint (&node->partition, &Position);        if (side==CP_BACK) {            RenderBSP (node->frontnode);            RenderBSP (node->backnode);        }        else {            RenderBSP (node->backnode);            RenderBSP (node->frontnode);        }    }    if (node->leaf) {        //Draw polygons that are in the leaf        }    }    return 1;}

What surpsised me is the fact that you seem to draw all the polygons in the level, regardless of where the camera is. I thought that using a BSP tree allowed you to omit drawing certain branches of the tree depending on where the camera was standing and what direction it was looking in.

My question is: If your going to draw all the polygons in the level anyway, whats the point of a BSP tree? Why not just have one big list of all the polygons and draw them? Why do you need this fancy shmancy datastructure?

I realize there are probably other optimizations you can do once your polygons are in a BSP tree, but as the code is above, I dont see what the point is. Someone please explain!

[edited by - AndreTheGiant on March 4, 2004 5:04:46 PM]

##### Share on other sites
Well fuck.

[edited by - GroZZleR on March 6, 2004 2:43:57 PM]

##### Share on other sites
quote:
Original post by GroZZleR
Did you read the article? =P

A) It says its psuedo-code.
B) It''s a recursive function (as its calling itself)
C) It clearly says at the bottom "Render Leaf Node"
D) Its clearly not drawing the whole level

Good luck! =)

I read the article and, given the pseudo-code, agree with AndreTheGiant that the entire level would be drawn. I assume that the given code would need to be combined with some view distance logic to prevent the entire level from being drawn.

##### Share on other sites
you can associate BPSs with PVS (potential visibility sets?) and other occlusion techniques to reduce the overdraw.

##### Share on other sites
The purpose of that code is simply to draw the polygons in the order of farthest to nearest. That was very important in the days before the Z-buffer, but now there is not much use for BSP trees.

##### Share on other sites
quote:
Original post by JohnBolton
The purpose of that code is simply to draw the polygons in the order of farthest to nearest. That was very important in the days before the Z-buffer, but now there is not much use for BSP trees.

Even with the Z-buffer, don''t you want to limit the number of polygons in the buffer? It seems like a BSP tree could be used to divide a large level into smaller segments. Then when you are populating the buffer with polygons to be drawn, you would only need to include the polygons from segments that are at least partially visible. Would this be more efficient than relying on the Z-buffer alone?

##### Share on other sites
Yes, it would. If you get as far as the Z-buffer you''ve drawn the polygon. A poly not drawn at all is going to be faster.

##### Share on other sites
That pseudocode will draw the entire level, but the purpose of that article was just to show how a bsp tree is used and one way it can be used, you can simply add a bounding box to a bsp node and test if the node is in the view frustum before drawing it. Pretty simple.

##### Share on other sites
quote:
Original post by Anonymous Poster
Even with the Z-buffer, don''t you want to limit the number of polygons in the buffer? It seems like a BSP tree could be used to divide a large level into smaller segments. Then when you are populating the buffer with polygons to be drawn, you would only need to include the polygons from segments that are at least partially visible. Would this be more efficient than relying on the Z-buffer alone?

Definitely you want to partition the level so you can cull things that can''t be seen, so you don''t end up drawing everything. I''m just saying that there are usually better ways to do it than using a BSP tree.

Back when 3D was done a triangle at a time and there was no Z buffer, BSP trees were a breakthrough because it all had to be computed on the CPU. The hardware is way beyond that now...

However, I think that the BSP tree is a fundamental concept and will continue to be the solution to difficult problems in the future. Everyone should understand how they work.

##### Share on other sites
JohnBolton,

So your saying that since BSP trees merely determine the correct order to draw the polygons in, and since a z buffer can take care of that problem for you anyway, that BSP trees are obsolete?
What about the speed of using the z buffer? Is it not faster to use the BSP tree to get the correct order, than to cause the z buffer to do all of those updates and comparisons?

I realize you can do all kinds of fancy things to the BSP tree, like prune the branches if you can determine somehow that you dont need to draw them, but Im talking about just a plain old BSP tree, with no "add ons" like PVS or bounding box stuff, that can only give you the correct ordering of the polys in your level. Your saying that if that is all you were going to use the BSP tree for, then you''re better off just using a plain old list of all the polys in your level, and using the z buffer ?

I hope ive said this clearly. It makes sense to me, but that doesnt mean its correct. Im getting more and more confused about the actual benefits of using a BSP tree.

##### Share on other sites
First, if you use a BSP tree to sort triangles, in most cases you would still use the Z-buffer and sort front-to-back. The Z-buffer can speed up rendering by rejecting occluded fragments.

Sorting

Sorting by material is usually much more effective than sorting front-to-back. Sorting the triangles front-to-back after sorting by material may not accomplish much.
Sorting front-to-back means that the vertex data is reconstructed every frame. This is hardware-unfriendly because the data must be transferred to the video card every frame. If the triangles are not sorted every frame, the vertex data only needs to be sent to the video card once (ideally).
Triangle splitting can increase the size of the data a lot. It can also cause other problems like T-junctions. If your triangles are not required to be perfectly in order, you probably don''t want to split triangles.

Culling

If your level is a polygon soup, then perhaps a BSP tree and a PVS is a good way to do culling. However, if your level has any organization, there are probably better ways to cull that can take advantage of that organization. I don''t have a lot of experience with this, so that''s all I will say.

Transparency

One use for a BSP tree might be sorting triangles with transparency. Triangles with transparency must be drawn last and must be drawn back-to-front, in order for them to look right.