#### Archived

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

# Uses of BSP trees?

This topic is 5276 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?

1. 1
2. 2
3. 3
frob
15
4. 4
5. 5

• 11
• 20
• 12
• 13
• 14
• ### Forum Statistics

• Total Topics
632146
• Total Posts
3004433

×