Jump to content
  • Advertisement
Sign in to follow this  
Code-R

Benefits of a BSP Tree over a simple block (cell?) based system?

This topic is 4662 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

What are the benefits to using a BSP tree intead of a simple, block based system (pseudocode)
int index = FindCell(Scene, Camera);
Render(Scene.Cell[index]);
for(i = 0; i < Scene.Cell[index].VisibleCellIndices.size(); ++i)
{
 Render(Scene.Cell[ Scene.Cell[index].VisibleCellIndices ]);
}

forgive the noobish question, but that really got me thinking TIA

Share this post


Link to post
Share on other sites
Advertisement
There are many variantions and specific kinds of BSP trees each one better suited to a particular type of operation/setting etc.

To put it simply you can think of

BSP trees Vs Voxel Grids/Cells as along the lines of

Binary Search trees (BSTs) Vs Plain Arrays (not sorted/ordered).

BSP trees are generalization of BSTs for multidimensional data sets while Grids/Cells are essentially multidimensional arrays.

[Edited by - snk_kid on October 9, 2005 6:53:42 AM]

Share this post


Link to post
Share on other sites
In a grid, there's no hierarchy, you have to treat each cell individually.
In a tree structure, you can discard a whole subtree in one shot.

Also, a BSP tree stores empty/solid space information. It can be usefull for some operations like CSG.

Share this post


Link to post
Share on other sites
Lets say you have one giant outdoor map. First level of bsp is the entire map. Second level is the map split into 4. So, you find out where you are on the bsp's lowest level and only check the blocks in that portion.

Share this post


Link to post
Share on other sites
but this could be achieved with this structure, as each cell has a list of cells that should be drawn when the camera is inside it. what gives?

Share this post


Link to post
Share on other sites
A cell system is more like a hash table whith O(1) lookup and the '1' is very small. Tiles/Cells are very simple to impliment and very fast, this makes them ideal for alot of situations. A BSP tree can help though in a 3d game with the rendering.

Share this post


Link to post
Share on other sites
Quote:
Original post by robert_p
A BSP tree can help though in a 3d game with the rendering.


Isn't BSP more suited to collision detection now that we've pretty much done away with software rendering?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What you are describing sounds like potentially visible sets, which is another technique. For some purposes one structure may be better than the other. It is even possible to have both a BSP tree and a potentially visible set structure at the same time, and use each of them for different purposes.

Share this post


Link to post
Share on other sites
for collision detection, I'm using a physics SDK, so this wont' matter much. how is it beneficial to rendering?

Share this post


Link to post
Share on other sites
BSPs are not, and have not been for many years, an optimal rendering solution. For rendering, they haven't been useful since Quake came out. They have some nice properties in terms of collisions, although physics engines have by and large come up with more robust ways to deal with collision.

It's unclear to me whether you're describing a PVS based system (which all of the Quake series and Quake based games, as well as Half Life 2 use), or a portal system (used in Doom 3 and a few others). Both are decent solutions for rendering nowadays, although cell based rendering is far simpler to do indoors than outdoors.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!