Jump to content
  • Advertisement

Archived

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

AndreTheGiant

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!