Archived

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

BSP Trees : Octrees :: Indoors : Outdoors

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

Im trying to learn up on BSP trees, and space partitioning data structures in general, and I keep coming across this statement, or something similar: "BSP trees are better suited for indoor areas. If you plan to have primarily large outdoor areas, look into octrees or something else." After hearing this enough, I decided I wanted to find out WHY this is the case. After a few days of searching, Ive come up with nothing. Everywhere I look, people are repeating that same sentence (more or less), but no one ever offers any explanation why. Its as if some dude way back just said that for the heck of it, and everyone''s followed suit without really questioning it. Ive even done my own research. I know quite a bit of BSP theory now, although not too much about octrees yet. However, I cant think of any specific property of BSP trees that would make it good for indoor, yet bad for outdoors. Someone here must know.

Share this post


Link to post
Share on other sites
BSP's are based on a portal based system. When a BSP is compiled, a list of portals is generated that contains what objects are blocking what objects and it creates a heirarchy of what to draw from that point, based on the blocking (also known as VIS(ability) blocking).

So say you have a map that looks like this:

(Numbers represent floor / portals, * = Wall)


****** *****
*1111****333*
*11112222333*
*1111****333*
****** *****


From this incredibly piss-poor ASCII art, we can see that if you're standing in portal 1, you can see portal 2 and portal 3, and thus, it will be drawn. If you're standing in portal 2, you can see both portal 1 and portal 3 (ignoring the frustum for now).

But what if the example looked more like this:

******
*1111*
*1111*
*2****
*2*
*2*****
*33334*
*****4*
*4****
*5555*
******


With a long, winding path, you'll start to see that from portal 1 you can longer see portals 4 and 5, so they WON'T get drawn, and I'm sure you can notice all the others.

You'll see a winding hall all the time in games like Quake and Half-Life, simply to keep the renderings down from portal to portal.

But if you extend this to outdoors, it doesn't fair so well.

*****************
*111111111111111*
*111111111111111*
*111111111111111*
*****************


Theres nothing blocking you, that entire portal is goign to be rendered. And if you expand this to really, really large outdoor areas, there won't be enough blocking and way too much will be drawn, thus throwing your framerate down the crapper.

By combining a frustum with an octree, you can drastically cut the scene down to size.


*****************
*111122223333444*
*111122223333444*
*111122223333444*
*****************


If we're standing in portal (not really a portal in an Octree) 2, and facing left, we know we don't have to draw anything in portal 3 and 4.

Octrees don't depend on 'vis blocking' like BSPs do, and this is what makes them better for outdoor areas and BSPs phenominally fast for indoor areas.


[edited by - GroZZleR on March 22, 2004 1:12:28 AM]

Share this post


Link to post
Share on other sites
Thanks for the reply, GroZZleR. It seems not many people know the answer because a lot of people have viewed this, but few have answered.

I did not know that BSP''s are based on a portal system. I thought BSPs and portals are 2 different things. Sure they can be used together, but they are still 2 different things. My question was why are BSPs better for indoor areas. Are you saying that BSPs are only better because you can use them with portals?

I have a BSP implemented, but it doesnt do any of the PVS or ''blocking'' stuff as you called it. It cull stuff that is behind the view frustum (ie you are not looking in that direction), but it draws all polyons that are in front of you.

Hence, I am not getting any different performance between outdoor and indoor levels.

Does this make sense?

Share this post


Link to post
Share on other sites
Indoor areas have lots of things that block one another, like seeing around a wall. That "blocking" is called occlusion and is useful for speed increases in indoor areas. Outdoor rendering has much much less occlusion which is why it wouldn''t be necessary to use a BSP for such a purpose.

Quadtrees/octrees can be used for LOD for which BSPs weren''t intended. Dynamic LOD is clearly more important for terrain.

But I think the main reason is the method of how BSPs split polygons and create sectors - it makes sense with there are many walls and closer areas but for something like rolling hills - where is the best splitting plane? Well would it be right in the center of the terrain? Ok then each sub node on the BSP would just be the middle of the terrain patch... now you are basically implementing a quadtree/octtree in a less useful data structure.

Share this post


Link to post
Share on other sites
Here are my thoughts: It''s all about the terrain.

Terrains are generally organized in a grid, so a grid-friendly partitioning scheme will have advantages. Further, some terrain-rendering algrithms are based on quadtrees. The interesting exception is ROAM, which is essentially a BSP-based algorithm.

The typical BSP tree partitioning scheme takes a poly, partitions the scene, and splits any polys that cross the plane. Terrain polys are relatively parallel to each other and generally close to the same plane. That is going to cause big problems with splitting.

Also, LOD is important in terrain rendering. That can cause cause problems because BSP trees work best with static geometry.

Share this post


Link to post
Share on other sites