• Advertisement
Sign in to follow this  

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

This topic is 4487 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
Guest Anonymous Poster
I think portals are a type of PVS method. Calculating potentially visible sets is hard, so there have been lots of methods developed to do it. Usually the world is split into regions and each region has its PVS calculated. Portals are the connections between regions, so when calculating the PVS only the portals need to be considered.

Share this post


Link to post
Share on other sites
Well, technically, BSPs are PVS systems as well.

In short, you have to decide what algorithm you want to use, or invent your own mixture.

-= BSP =-

Pros - Still good for indoor area, but instead of taking all of the polys in a region and then subdividing all of the polys in a high density area, have the artists create a much more poly reduced version of the level that just includes the walls, floor and cieling. Have them tie the small map together with the big map and viola, now your bsp tree can still do some fantastic speed optimizations and physics operations.

Cons - Design it very carefully. Cache missing can kill your framerate, so focus very highly on memory coherence.

-= Oct Tree =-

Pros - Extremely easy to implement and you have control over how far the tree subdivides.

Cons - Not nearly as accurate as a true BSP representation, and suffers from the same design problems as BSP(cache missing).

-= Portal =-

Pros - Even easier to implement, and the results are very impressive, considering it is all artist controlled.

Cons - The artists will bitch and whine if they don't really have a cool, comprehensive tool they can use to edit the portals. You'll have to spend some time here to please them.

-= Other =-

Grid style systems often don't do well with large data sets, however there are several circumstances where this may be the most attractive solution. Overall, you need to look at the design of you level(s) and determine what is most important to you and which algorithm addresses the issues you want resolved.

Best of luck to ya!
-Krad

Share this post


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

  • Advertisement