• 9
• 11
• 9
• 20
• 12

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

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

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 on other sites
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 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 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 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 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 on other sites
Quote:
 Original post by robert_pA 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 on other sites
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 on other sites
for collision detection, I'm using a physics SDK, so this wont' matter much. how is it beneficial to rendering?