Jump to content
  • Advertisement
KarimIO

3D Do models go inside a BSP?

Recommended Posts

Hey guys,

So I'm starting to think about BSP for my engine, which so far only supports models. And I've got a couple stupid questions. How are static and dynamic models usually used with the BSP visibility side of things? As far as I'm aware, dynamic models only use the BSP tree as a way to cull before visibility culling, so i guess I can compare an OOBB to the BSP tree leaves - is this correct? How do static meshes affect the BSP tree in terms of blocking visibility?

Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement

BSP gained popularity in 3D games because it meant that you could draw your world without a z-buffer. You use the BSP to sort the world polygons into perfect depth order, which is possible because whenever a triangle crossed a BSP splitting plane, you'd slice it into two parts. Since we're no longer writing software rasterizers, BSP has fallen out of favor - there's plenty of other spatial partitions to choose from ;)

In my experience with old BSP engines though -- models can be in multiple leafs (unlike world triangles, which are split to ensure they're only ever in one leaf). When traversing the tree you take care to ensure you only visit each model once even though it can be reached multiple times in the traversal, and build a list of visible models (yeah - a culling technique). Static meshes typically didn't block visibility because it was all pre-computed as PVS.

Share this post


Link to post
Share on other sites

Thanks for responding quickly and helpfully as usual, Hodgman!

2 minutes ago, Hodgman said:

BSP gained popularity in 3D games because it meant that you could draw your world without a z-buffer. You use the BSP to sort the world polygons into perfect depth order, which is possible because whenever a triangle crossed a BSP splitting plane, you'd slice it into two parts. Since we're no longer writing software rasterizers, BSP has fallen out of favor - there's plenty of other spatial partitions to choose from

Doesn't Source use BSP for practically for everything under the sun and Unreal use it for blocking? It's not just partitioning and visibility I'd like it for, but also that blocking.

5 minutes ago, Hodgman said:

In my experience with old BSP engines though -- models can be in multiple leafs (unlike world triangles, which are split to ensure they're only ever in one leaf). When traversing the tree you take care to ensure you only visit each model once even though it can be reached multiple times in the traversal, and build a list of visible models (yeah - a culling technique).

Yeah that makes sense, but it shouldn't be difficult to overcome.

5 minutes ago, Hodgman said:

Static meshes typically didn't block visibility because it was all pre-computed as PVS.

How is this done though? The only thing that comes to mind is having an interior and exterior collision mesh, so anything including the interior mesh would block other BSP elements and anything in the exterior would represent what leaf the actual model is in.

Share this post


Link to post
Share on other sites
4 minutes ago, KarimIO said:

Doesn't Source use BSP for practically for everything under the sun and Unreal use it for blocking? It's not just partitioning and visibility I'd like it for, but also that blocking.

Source is a highly modded Quake 1 fork, so that would make sense :D 

Unreal has brush-based CSG support in the editor, but I don't know if, after the CSG step where brushes are converted to triangles, they actually construct a BSP or not.

Unity has a bunch of CSG plugins for their editor, where you can quickly block out maps like you would in Unreal or Hammer/Source... but they definitely don't construct a BSP afterwards.

7 minutes ago, KarimIO said:

How is this done though? The only thing that comes to mind is having an interior and exterior collision mesh, so anything including the interior mesh would block other BSP elements and anything in the exterior would represent what leaf the actual model is in.

How was PVS computed? You had to block out the whole level and make sure it was sealed/water-tight. If any parts of the level were going to be built with static-meshes, you still had to put brushes behind them (with an invisible material, typically) to satisfy this. The BSP compiler then broke the world up into sectors and portals. The visibility (PVS) compiler then shot a bunch of rays from sector to sector (through the portals) to guess whether they were occluded or not. There's also an exact analytical solution to this problem instead of the brute-force ray-casting method.

Then once you know which leaf node (sector) the camera is in, the PVS data gives you a list of all the other leaf nodes that are potentially-visible. Any static/dynamic meshes in those leaves are also potentially-visible.

Share this post


Link to post
Share on other sites
6 minutes ago, Hodgman said:

There's also an exact analytical solution to this problem instead of the brute-force ray-casting method.

There is an analytical solution, but very difficult and unpractical for detailed worlds: http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm

(Additionally to the fact that BSP itself is unpractical for detailed worlds and especially outdoors - very unlikely it is what you want.)

Share this post


Link to post
Share on other sites

Alrighty so basically I should use CSG geometry without the BSP partitioning. PVS is an all-encompassing thing, right, not just an individual technology? But in regard to partitioning and visibility, I remember Frostbite used sphere-based partitioning. Is that still used today, or can you suggest another partition method.

Share this post


Link to post
Share on other sites
5 minutes ago, KarimIO said:

Alrighty so basically I should use CSG geometry without the BSP partitioning.

CSG geometry? Does that mean you have low poly levels similar to Quake? If so BSP is a good option.

Visibility determination is still an open problem - any solution is complicated and has draw backs. Sphere-based partitioning probably means a tree of bounding spheres, but partitioning alone does not tell anything about occlusion, it only helps to render front to back and to cull whole branches of a tree if the parent is occluded.

Most dynamic approaches work somehow like this: Select a set of potential good occluders (nice to have low poly representations), render them front to back (software or GPU), test bounding tree for occlusion and append to visible list. There are many variations of how to do this. Doing the tasks in order per node and using a common tree allows to cull occluders by occluders, so zuro work behind a solid wall. Doing the tasks for larger sets or whole scene allows parallelization but processes useless work.

Static approaches allow to build a PVS and also to work with portals instead occluders. (rastering portals at low resultion is stable against false negatives, but generating portals in realtime seems impossible).

Probably the most effective is coarse CPU culling and fine grained GPU culling. 

Many games utilize GPU occlusion queries with Hi-Z pyramid. That's easy to implement in comparission to a CPU approach which requires a software rasterizer. I'd try this first and see if it's good enough (There are some frames of latency until you get the results which results in popping we often see e.g. in UE games.)

 

 

 

Share this post


Link to post
Share on other sites
6 minutes ago, JoeJ said:

CSG geometry? Does that mean you have low poly levels similar to Quake? If so BSP is a good option.

As I said, I currently use only models for geometry. I wanted to add CSG-geometry for blocking things out, as well as for people who come from the Source Engine that might find it useful.

12 minutes ago, JoeJ said:

Most dynamic approaches work somehow like this: Select a set of potential good occluders (nice to have low poly representations), render them front to back (software or GPU), test bounding tree for occlusion and append to visible list. There are many variations of how to do this. Doing the tasks in order per node and using a common tree allows to cull occluders by occluders, so zuro work behind a solid wall. Doing the tasks for larger sets or whole scene allows parallelization but processes useless work.

This is pretty much what I planned to do before wanting to look for more effective methods. Quick question though, should frustum culling be done before or after occlusion culling?

13 minutes ago, JoeJ said:

Static approaches allow to build a PVS and also to work with portals instead occluders. (rastering portals at low resultion is stable against false negatives, but generating portals in realtime seems impossible).

So an optimal approach would be using the PVS for static objects and occlusion queries for dynamic ones, while checking the partitioning tree for where the dynamic objects are to reduce the amount of occlusions, correct?

14 minutes ago, JoeJ said:

Many games utilize GPU occlusion queries with Hi-Z pyramid. That's easy to implement in comparission to a CPU approach which requires a software rasterizer. I'd try this first and see if it's good enough (There are some frames of latency until you get the results which results in popping we often see e.g. in UE games.)

I know nothing of Hi-Z Pyramids, but I'll check them out!

Share this post


Link to post
Share on other sites
20 minutes ago, KarimIO said:

This is pretty much what I planned to do before wanting to look for more effective methods. Quick question though, should frustum culling be done before or after occlusion culling?

Frustum culling might happen automatically: Checking a offscreen bounding box against a software framebuffer rejects it including it's subtree, so you get accurate frustum culling for free. (Note that the software framebuffer can be made of spans instead individual pixels, which is much nicer than pixel based GPU hardware queries.)

29 minutes ago, KarimIO said:

So an optimal approach would be using the PVS for static objects and occlusion queries for dynamic ones, while checking the partitioning tree for where the dynamic objects are to reduce the amount of occlusion (QUERIES,) correct?

Makes sense. For GPU queries typically multiple objects get batched (no experience on GPU queries myself). How optimal this is depends on the game but sounds very practical. 

34 minutes ago, KarimIO said:

I know nothing of Hi-Z Pyramids, but I'll check them out!

Something here, seems very basic but with good effort / result ratio ;) I don't know if UE has a software system in front of this:

https://interplayoflight.wordpress.com/2017/10/25/how-unreal-renders-a-frame/

 

Share this post


Link to post
Share on other sites
3 minutes ago, JoeJ said:

Frustum culling might happen automatically: Checking a offscreen bounding box against a software framebuffer rejects it including it's subtree, so you get accurate frustum culling for free. (Note that the software framebuffer can be made of spans instead individual pixels, which is much nicer than pixel based GPU hardware queries.)

I didn't mean frustum culling of pixels, I'm aware that happens automatically, I meant of subtrees and entire objects or areas.

5 minutes ago, JoeJ said:

Makes sense. For GPU queries typically multiple objects get batched (no experience on GPU queries myself). How optimal this is depends on the game but sounds very practical. 

Awesome!

5 minutes ago, JoeJ said:

Something here, seems very basic but with good effort / result ratio ;) I don't know if UE has a software system in front of this:

https://interplayoflight.wordpress.com/2017/10/25/how-unreal-renders-a-frame/

Thanks! I'll check it out soon. And is this used in addition to the previously mentioned techniques, or instead of it?

 

Thanks again, JoeJ and Hodgman!

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!