Sign in to follow this  
ill

Should levels still be made with convex shapes?

Recommended Posts

So games like Quake, Halflife 2, Doom 3, Unreal... All use convex shapes and CSG to create the levels. BSP was a good spatial data structure for this kind of thing. It allowed for sorting polygons somehow, not sure how yet since I didn't look in to it.

Nowadays there are games like Crysis, Battlefield, Rage, Fallout 3, Elder Scrolls... with outdoor areas mixed with indoor. I tried to do some research on what kind of data structures they use and if they still require convex brush shapes but I can't really find that info. Those kinds of engines allow a level designer to make a level and play it right then no problem.

I'm just wondering, do those kinds of games still use convex shapes for geometry and BSP trees? Or do they use completely different data structures?

Right now I use 3DS max for making levels and just create triangles that are stored in a uniform 3D grid which worked well for a 2D side scroller.

Now I want to make an FPS and I think I need a much better data structure than a 3D uniform grid. The only thing I know FPSes use is BSP trees but I think BSP might be kind of outdated now. Basically everyone knows Quake used BSP... No one ever seems to openly talk about how those other games do what they do though.The best I could come up with was mixing Octtrees for the outdoor areas and BSP trees for the indoor areas but that's just a guess and sounds a little complicated. It can probably be done but I don't want to waste my time implementing some solution if a better one exists.

Share this post


Link to post
Share on other sites
[b]On the shape.[/b]
As far as I understand, they're still used in the communities.
[b]I'd like to know more on their use in the industry.[/b]
Personally I believe that they're not really used much anymore. Nowadays games have way too much geometry detail. No way to model those with brushes. Static trimeshes imported from your app of choice will do.
Perhaps still good to "brush out" the level, no leaks and such, while the real deal is done by using more accurate tools. (?)

[b]On the data structure.[/b]
BSP was much more attractive in the early days of 3D than it is now. I have read a few other papers[1] suggesting to use other structures.
Personally I am a "geometry fanatic"... I don't like the idea of splitting the geometry just to satisfy some requirement. Everything that requires partitioning will not deal well with dynamic scenery and this appears to be a requisite in many cases those days.
So far, I've been "fairly happy" with a crappy Bounding Volume Hierarchy. Bullet uses a tree of AABB for its broad phase rejection tests.
Having the ability to encapsulate a lot of detail in each "leaf", it seems to me those structures are way more future proof.

[1] I think one was about a Splinter Cell game. I haven't managed to find the original file, but I've found [url="http://www.selfshadow.com/talks/rwc_gdc2010_v1.pdf"]this (click)[/url]. I'm not sure this was what I was searching for...

Share this post


Link to post
Share on other sites
Modern games definitely don't just make levels out of brushes anymore, it's too limiting for the artists. Games are starting to trend towards more generic visibility systems, both because it's easier on the artists as well as for CPU performance reasons.

Share this post


Link to post
Share on other sites
Convex volumes (or simplified geometry) should still be considered for physics and collision detection, however (and maybe even occlusion culling too if you are doing it dynamically).

I second Krohm's thoughts on using a BVH as the scene data structure - an AABB Tree is extremely simple to construct (don't have to worry about splitting geometry like in an octree), especially if you are just dealing with static geometry.

Share this post


Link to post
Share on other sites
Yeah I was thinking BVH is the way to go. What I'm confused about though is how to track all the in game moving objects like characters.

In my 3D uniform grid, it's very easy to index into which grid I want to be in based on object position. My object moves, I know exactly what grids it's in based on its AABB. I have ways to process objects only once if they are in more than 1 grid partitions at once which I will probably bring over to the BVH.

For the BVH, I guess I'd construct it only for the static geometry and have dynamic objects move around between the static BVH nodes. Then I'd also have a nice scene graph tree based on my BVH.

I guess I take a moving object, traverse through the tree until I get to the BVH leaf it's in, but what if it ends up outside any leaves? My 3D grid handles objects outside the level by just placing them in the nearest partition close to the level boundary. Would I somehow determine the closest leaf to put the object in to so it doesn't get "lost"

Share this post


Link to post
Share on other sites
[quote name='ill' timestamp='1317577452' post='4868321']I guess I take a moving object, traverse through the tree until I get to the BVH leaf it's in, but what if it ends up outside any leaves?[/quote]Impossible. In gameplay terms, this means the player somehow managed to go outside the level.
This should be prevented by all means. I'd have an impenetrable, infinitely tick wall around everything.
I case something goes out - it is indeed useful for debugging - just create a new root for the BVH. In terms of data structures, this will create a very unbalanced tree... but in real world terms, wasting a test is not very likely to be a real problem.

As a side note, the term [i]scene graph[/i] is typically tied to the concept of "inheriting (some graphic) state from root", which is considered bad. You might consider "geometry graph", "transformation graph", "culling graph" or stuff like that - depending on the usage.

Share this post


Link to post
Share on other sites
I was talking to my graphics teacher and she basically said not to use BVH since it doesn't really partition space like I want. I don't really even need it for collision detection since I use PhysX. It's more for helping me do View Frustum Culling and Portal Culling. How I will use PhysX efficiently is something else I need to figure out. (I'm guessing loading the entire level in as a triangle mesh miiight not be the most efficient thing?)

Right now I'm thinking of going with either KD trees or Octtrees, or maybe even just sticking with uniform 3D grids. An occtree would probably be an extension of my implementation of 3D uniform grid. I can't find very good info on what is the best for an FPS that I am trying to make (Indoor areas mixed with some outdoor hills sometimes). I did some searching and can't find a very good comparison of KD trees versus Occtrees.

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