Sign in to follow this  
ill

Spatial Datastructures

Recommended Posts

So my previous game was a side scroller but rendered in 3D. I went with a simple uniform 3D grid.

Now I am moving to making a First Person Shooter and basically a full 3D game. I hate being limited to one specific thing and I want to support both indoor and outdoor environments seamlessly. It's pretty interesting how Quake Wars and the upcoming Rage and Doom 4 on the new idtech 5 engine seem to support both environments well. Games like Crysis seem to be mostly built for outdoor with some indoor environments.

I am familiar with uniform grids, quad/octtrees, BSP, KD, BVH and all have their tradeoffs. Some are good for indoor and others good for outdoor. Is it a good idea to mix structures? Say I have the root structure and it has some sub nodes. Then those subnodes contain other structures that are better suited for the type of area that it is.

A good example is the Yosemite map in Quake Wars. It's a huge outdoor area. Then there is a massive tunnel with some hallways branching off to the side creating a huge indoor area. This is all inside a hill.

Another good example is a snow map that is all outdoors but also has a huge science facility with extensive indoor hallways. I notice my FPS going up a lot on my older computer when I am indoors so I can tell that they handle the indoor areas very efficiently too.

Then there is a really crazy map where you start in Africa or something and take a teleport to Antarctica. Two completely different outdoor areas that you seamlessly teleport between.

I am thinking that a BVH would best support all types of environments for the most part. This would store the static geometry. Dynamically moving objects would put themselves into the existing bounding box areas.

I could also just go with a BSP tree. Unreal Engine 2 seems to support both kinds of environments beautifully. Not sure what they use in Unreal Engine 3. Do those still take long to generate? I want to make a map and have it runnable immediately without a super long prebaking session.

If I am correct Doom 3 doesn't even use BSP trees anymore. They have areas separated by vis portals. They just send all geometry in the area to render even if it's behind a wall. But the visible areas are kept small by the vis portals so it's not too expensive. This would only work well for indoor environments though.

Share this post


Link to post
Share on other sites
I think BSP-trees are a little out-dated, as processors have become really fast since the times of Quake 2. My preference is to use an Octtree for outside scenes and portals for inside scenes. Things like houses, etc. can just be put into the Octree including the portals. In the end everything can be abstracted to a graph-structure for which things like "Is the content of this node (subgraph) visible?" can be reduced to "Do I need to follow this edge?". Then you just traverse the graph an and render things you encounter..

- Michael

Share this post


Link to post
Share on other sites
The original quake only chose BSP because it allows you to sort objects from back to front while traversing the scene -- and they supported software rendering without a Z-buffer, which means you need to sort your polygons...
At level compilation time, the BSP tree's splits were used to automatically split the level into sectors and portals between the sectors. The 'vis' tool then used the portals to build a PVS table for the sectors.
At runtime, the most important thing the BSP-tree was used for ([i]in hardware rendering mode[/i]) was to quickly find out which sector the camera is inside of -- once you know what sector the camera is in, the list of visible sectors were simply retrieved from the PVS table.

Also, in the traditional quake setup, the sectors form an undirected cyclic graph ([i]not a tree[/i]) which can be traversed.

Half-Life 2 is still quite closely related to Quake1 though it's lineage, and their main addition to the BSP/VIS/PVS system is the addition of [url="http://developer.valvesoftware.com/wiki/Func_occluder"]occluders[/url] and [url="http://developer.valvesoftware.com/wiki/Func_areaportal"]closeable portals[/url], which makes handling of outdoor areas a bit easier.

Sectors, portals and occluders (aka anti-portals) are still the backbone of a lot of engines.
Fallout 3's [url="http://geck.bethsoft.com/index.php/Occlusion_Culling"]dev wiki page[/url] has a good description of how they use these 3 culling primitives to render both indoor and outdoor areas.

These days, I'm not a fan of complicated tree structures for culling objects.
If possible, I prefer a flat array of bounding boxes, each of which is associated with a flat array of drawables. The array of bounding-boxes is processed by the portal/occluder system, and then the visible boxes submit their drawables.

Share this post


Link to post
Share on other sites
[quote name='Michael N.' timestamp='1307838419' post='4822226']
I think BSP-trees are a little out-dated, as processors have become really fast since the times of Quake 2. My preference is to use an Octtree for outside scenes and portals for inside scenes. Things like houses, etc. can just be put into the Octree including the portals. In the end everything can be abstracted to a graph-structure for which things like "Is the content of this node (subgraph) visible?" can be reduced to "Do I need to follow this edge?". Then you just traverse the graph an and render things you encounter..

- Michael
[/quote]

Hmm the ordering would make it nice and easy to sort transparent polygons. Not sure how it would do it off the top of my head though.

Do BSP trees need the level geometry to be made out of convex brush objects? I remember reading about it and it says something along the lines of it splitting the brush sides in half or something. I'm making my levels out of plain triangle meshes made in 3DS max.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this