Sign in to follow this  
DD-

Are BSP based engine becoming archaic?

Recommended Posts

I've been a level designer for a few years, professionally only recently. The last three years were spent studying CSI. I never got into game programming but I understand a large amount of the programming side and theory because of my CSI background. Yet still I am unable to answer this concretely. It seems more and more BSP based level design/engines are becoming more and more useless, seeing Quake style engines rapidly disappearing. Obviously a mesh/model cached into video card memory will render much faster, but when an engine is entirely mesh the method of culling becomes questionable. I believe a heavy usage of mesh and a light mixture of BSP for culling, allowing for tons of detail in indoor areas with high frames, will never go instinct. However GPU's are becoming so fast that wasting that extra time rendering is becoming faster and faster it seems that it might even be faster then wasting CPU time deciding what to and what not to render. The answer I'm looking for is that BSP will never go away, not because I like level design with BSP, but because, and I say this at the end of my post, I am much more of a fan boy of the Quake engine and games such as half-life, and there is a growing rivalry with fans of the Unreal engine at our office. Arguments between my co-workers and I often lead to mindless debate and noob calling.

Share this post


Link to post
Share on other sites
Great post, and I think that you are quite correct in your assumptions. GPUs are getting much faster at rendering mass amounts of polygons, causing many once popular algorithms to become useless on newer hardware.

Look at the ROAM algorithm for terrain level of detail. It once had a large following of terrain engine developers, but now you are hurting your engine's performance using ROAM with newer hardware. You would get much better performance using static VBOs chunked into blocks with frustum culling, or using Geo-Mipmapping. While I still think the BSP\PVS algorithms have their purpose, their are pros and cons to both. The pros are fairly obvious, especially on older hardware, but a major con that game developers, in my opinion, might be omitting BSP implementation is that it generally doesn't support dynamic meshes, or mesh deformation (without a lot of "handy work"). I don't see BSP completely going away, but I do see more hybrid engines coming out.

Just my 2 cents!

Share this post


Link to post
Share on other sites
BSPs were great for rendering when there was no or little hardware Z-buffer support, because they can give you perfect Z-sorting for free when walking down the tree to render it.
Quake3 already dropped the fully convex leaves concept, but still kept BSPs, same for lots of other engines (unreal), I'm not sure why, probably because using something else would have meant making a whole new bunch of tools.

and about that mesh/culling, you really should use massive culling (frustum + occlusion), if you want highly detailed levels on today's hardware... thinking that a whole mesh for a whole level can run OK today is the symptom: "we've got fast CPUs and GPUs, so we don't need to bother optimizing". but if we do bother, we can display much higher quality, detailed graphics.

BSPs were also probably kept for collision detection, but as time goes on, they're becoming more and more useless and obsolete (it's been quite a while now in fact...)

the big problem with BSPs is that they also are completely static. of course you could rebuild at runtime a whole sub-branch of the tree... but it's damn slow, and that time could be spent doing some _useful_ things, using another more appropriate space partitionning technique, such as octrees, ABTs, KD-trees, whatever...

Quote:
However GPU's are becoming so fast that wasting that extra time rendering is becoming faster and faster it seems that it might even be faster then wasting CPU time deciding what to and what not to render.


that's true for some things, but definitely not for a whole 500 000 triangles level :)
it'll be true if you partition too much and if you don't have enough triangles in each batch (and still, it's not the time needed to do a frustum test that will become annoying, it's the CPU overhead to render the batch, rendering 1000 10 triangles batches will be a _lot_ slower than rendering 10 1000 triangles batches, even without any culling tests whatsoever)

Share this post


Link to post
Share on other sites
Yes, BSPs are getting outdated, but consider it a tool in a toolbox. Just don't always use it, but at least it is there if the situation arises. If you read my above post, I state that BSPs are a decent solution to outdated hardware, which still make up a decent part of the target market. They are outdated for newer hardware, because better solutions have been developed. It depends on what your requirements and design goals are.

As I stated, every algorithm has its pros and cons.

Share this post


Link to post
Share on other sites
Small question:In an interview I read Carmack says that one thing they didn't do in Doom3 was to implement a general solution for rendering transparent surfaces in the right order.It seemed weird to me,because I thought BSP-based PVS can do that.Have they dropped that feature?

Share this post


Link to post
Share on other sites
It probably has alot to do with their lighting engine. Per pixel lighting and alpha blended triangles have trouble with each other (from what I saw of the doom 3 lighting shaders). As for BSP, people forget BSP has alot more use than just what needs to be rendered and what doesn't. Things like sounds being in correct areas, lights only affecting rooms they are in, etc also is part of the BSP process. All the culling you do isn't just for what polygons need rendering, I think BSPs become more and more useful as time goes on, and with the Leafy-bsp system (ALA Quake 3) they're getting better too. BSPs may be static, but you can always put dynamic meshes within leaf areas, there's nothing against doing that.

Share this post


Link to post
Share on other sites
Quote:
Hate to break it to you, but...
Yann Gives some great reasons why BSP's are out dated..


Actually, no.

If you read his posts more clearey, you would see that ABT's and BSP's are practicly the same thing. What he said is that classical Quake style BSP is outdated. However, KD-trees are still usefull (octrees and quad trees), especially binary trees as they require less checks. Anyway, you will use partition tree which suits you best.

Would you say that Octree would be an improvement for Quake 2? I think not. Use tools as you know they'll do their job best.

ABT - axis-aligned binary tree (only cut via planes perpendicular to XY, XZ and YZ)
BSP - Binary Space Partition Tree, self explanatory

Share this post


Link to post
Share on other sites
Quote:
Original post by DD-
The answer I'm looking for is that BSP will never go away, not because I like level design with BSP, but because, and I say this at the end of my post, I am much more of a fan boy of the Quake engine and games such as half-life, and there is a growing rivalry with fans of the Unreal engine at our office.


Unreal uses BSP, with lots of instanced meshes laid on the BSP shell. It can be effective, but mostly for indoord environments where auto-portalization via BSP is practical.

I personally prefer ABT (the A stands for "adaptive", not "axis-aligned", btw) because it's more capable of handling scenes full of complex unique geometry that should be split into manageable chunks, but BSP can't handle it.

Share this post


Link to post
Share on other sites
btw, after reading ffx's post, I need to add a precision to my above post: when talking about BSPs, I referenced what the term "BSP" usually describes: quake-like leafy BSP trees, and not all binary space partitionning techniques of course.

GodBeastX> since Q3 (and maybe Q2), Id doesn't use convex leaves in their BSPs, and cannot use the sort order to sort transparent polygons. having strictly convex leaves in a doom3 level would produce far too many polygon splits, and far too many GCs/render calls.

Share this post


Link to post
Share on other sites
I would agree that classical BSPs are antiquated when it comes to storing your entire level.

However, that doesn't mean they're to be thrown out entirely. I remember reading something on the GDAlgorithms list which talked about a shadowing algorithm that used a BSP tree to sort the faces of the shadow volume or something.

BTW,

Quote:
level design with BSP


AFAIK there's no such thing; did you mean brush-based (CSG) level design? The output of the CSG process is a poly mesh that can be fed into any data structure, not just a BSP tree.

Share this post


Link to post
Share on other sites
superpig>
Quote:
would agree that classical BSPs are antiquated when it comes to storing your entire level.

However, that doesn't mean they're to be thrown out entirely.

I agree, ABTs/binary sphere trees are a form of BSP anyway :)

Share this post


Link to post
Share on other sites
Quote:
Original post by sBibi
I agree, ABTs/binary sphere trees are a form of BSP anyway :)
I meant classical BSP trees :P

Are ABTs a form of binary tree? I was under the impression they were simply AABB-trees.

Share this post


Link to post
Share on other sites
Quote:
I meant classical BSP trees :P

ok ^^

Quote:
Are ABTs a form of binary tree? I was under the impression they were simply AABB-trees.

ABT like Adaptive Binary Tree, so yes, I guess they can be seen as a form of binary AABB trees :D (except that "standard" AABB trees would be static, and that each AABB tree node doesn't necessarily have two childs...)

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
Quote:
level design with BSP

AFAIK there's no such thing; did you mean brush-based (CSG) level design? The output of the CSG process is a poly mesh that can be fed into any data structure, not just a BSP tree.


Yes I did, we often refer to brush based geometry as BSP, incorrectly, and I've picked up the bad habit. Thanks for the responses everyone, this answers my main questions but only leaves me with more new ones. :)

Share this post


Link to post
Share on other sites
the problem is, people there interpret "BSP is outdated" as that there's no need to do any partitioning because cards is fast. And imho it's wrong. Yes, you can do good things now w/o partitioning, but with partitioning you can have more detail at same speed, and it's good. w/o partitioning you can't do collision detection for more-or-less detailed meshes.
And, yes, partitioning for rendering down to single triangles is obsolete.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dmytry
the problem is, people there interpret "BSP is outdated" as that there's no need to do any partitioning because cards is fast. And imho it's wrong. Yes, you can do good things now w/o partitioning, but with partitioning you can have more detail at same speed, and it's good. w/o partitioning you can't do collision detection for more-or-less detailed meshes.
And, yes, partitioning for rendering down to single triangles is obsolete.


Personally, the reason I don't ever plan to use BSP for storing my level data in the future is that it seems inefficient compared to something like an octree. With each step down through the BSP you eliminate half of your data set; with the octree, though, you eliminate seven eighths. Granted, you don't get quite the same plane-testing, but given the rapidly increasing detail of today's environment meshes, generating a tree of planes for every poly in the mesh seems like it'd be horribly demanding on system resources.

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
Quote:
Original post by Dmytry
the problem is, people there interpret "BSP is outdated" as that there's no need to do any partitioning because cards is fast. And imho it's wrong. Yes, you can do good things now w/o partitioning, but with partitioning you can have more detail at same speed, and it's good. w/o partitioning you can't do collision detection for more-or-less detailed meshes.
And, yes, partitioning for rendering down to single triangles is obsolete.


Personally, the reason I don't ever plan to use BSP for storing my level data in the future is that it seems inefficient compared to something like an octree. With each step down through the BSP you eliminate half of your data set; with the octree, though, you eliminate seven eighths. Granted, you don't get quite the same plane-testing, but given the rapidly increasing detail of today's environment meshes, generating a tree of planes for every poly in the mesh seems like it'd be horribly demanding on system resources.

Yes, i agree, octtree/sphere tree and other more-regular trees is probably better - don't need to make decisions how to subdivide. It's just confusing that BSP stands for binary space partitioning, and for some readers, BSP stands for anything that makes decision what-to-render on CPU, and for many programmers only "unaligned" partitioning is BSP...

Share this post


Link to post
Share on other sites
ABT isn't a BSP-tree. It doesn't even partition space, it is a loose binary AABB-tree with a certain set of heuristics for determining splits. Bounding volume hierarchy != spatial partitioning scheme if you wan't to be picky about it. That doesn't mean spatial partitioning trees like a Kd-tree (which IS a BSP-tree, an axis aligned one to be exact) aren't useful.

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
Quote:
Original post by Dmytry
the problem is, people there interpret "BSP is outdated" as that there's no need to do any partitioning because cards is fast. And imho it's wrong. Yes, you can do good things now w/o partitioning, but with partitioning you can have more detail at same speed, and it's good. w/o partitioning you can't do collision detection for more-or-less detailed meshes.
And, yes, partitioning for rendering down to single triangles is obsolete.


Personally, the reason I don't ever plan to use BSP for storing my level data in the future is that it seems inefficient compared to something like an octree. With each step down through the BSP you eliminate half of your data set; with the octree, though, you eliminate seven eighths. Granted, you don't get quite the same plane-testing, but given the rapidly increasing detail of today's environment meshes, generating a tree of planes for every poly in the mesh seems like it'd be horribly demanding on system resources.

i disagree. a BSP or KD tree gets (roughly) the same performance as a BSP one. you need three plane checks to determine what leaf of an octree node you are. in 2^3 BSP/KD levels, you get the same number of spatial partitions. this check might be easier for an octree, but its also less flexible.

hierarchical datastructures will never be obsolete. the only fundamental difference between now and back then is the content of a leaf. back then it made sense to put just one tri in it, since every tri culled was important, now it makes more sense to put a whole bunch of tris in it, and save yourself half of the tree traversal.

Share this post


Link to post
Share on other sites
Quote:
ABT isn't a BSP-tree. It doesn't even partition space, it is a loose binary AABB-tree with a certain set of heuristics for determining splits. Bounding volume hierarchy != spatial partitioning scheme if you wan't to be picky about it.


mmh, seems like I don't have the right terminology. I thought a space partitionning structure just meant anything that partitionned space in a way or another, and any bounding volume hierarchy does in some way, each bounding volume contains a region of space, even if they overlap and a subregion of space is shared between multiple volumes, I still saw that as a space partition, but OK then, if space partitionning means a strict, static partition without overlaps, then ABTs are not BSPs. just.. mmh a binary bounding volume hierarchy ;)

thanks for clearing up that terminology thing...

Share this post


Link to post
Share on other sites
Don't sweat it, lots of people aren't as picky as I am. Anyway, I'd say that the main difference is that with something like a bsp the (union of cildren)=parent which doesn't have to hold in a bounding volume hierarchy. So you waste less energy on representing empty space.

Share this post


Link to post
Share on other sites
I don't know if this was already mentioned, but there is a new engine out there (can't remeber which one) that has some pretty wicked effects and uses all of the newer graphics hardware functionality, with very complex indoor and outdoor scenes... it doesn't use any sorta standard space partioning, but instead uses only occlusion maps. Im not exactly sure what the frame rates are and or system specs, but they stated it was a real time engine that would run on all modern hardware. Anyway, I personally think that with the proper tools and such, OC can eliminate the need for bsp's.

Share this post


Link to post
Share on other sites
Methods that bring complexity from O(n) to O(log n) (at least approximately) won't die, at least before n becomes constant (doesn't seem realistic...) and hardware (ie. algorithm's constant) becomes *very* fast.

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