Sign in to follow this  
RobMaddison

Efficient indoor and outdoor rendering - BSP & PVS?

Recommended Posts

Does anyone know what the latest engines are using for potential visibility with regard to combined indoor and outdoor environments? The last time I looked into this it was BSP trees and potential visibility sets, which had 'superceded' portal-based rendering. I intend my maps to be similar in size and complexity to that of a typical COD mutliplayer map, so mostly a relatively small terrain (which won't require anything more complicated than a small quad tree) and a few largeish buildings and interior areas. My initial thoughts were to model the exteriors of the buildings and chop them up into segments in order that they fit nicely into an oct tree. I was then going to model the static interiors of all the buildings and from those polygons, create a BSP tree from which I can build a potential visibility set (and do some interior collision detection, line of sight, etc). Unfortunately, line of sight will be required all over the map, inside and out so I was wondering whether it might be better to perhaps just create a BSP tree from the entire static scene map geometry, i.e. interior and exterior, and create a PVS from that. Does this sound like an efficient and elegant approach?

Share this post


Link to post
Share on other sites
Apologies for bumping, but I've been doing some more research into this and it appears that with today's graphics hardware, bsp trees, if used, are mainly only used for collision detection. If they're not generally used for rendering indoor environments any more, does anyone know what is?

The only thing I can think of is to split the entire indoor environment up into an oct tree and frustum cull the nodes but that doesn't really allow for any occlusion where nodes completely obscure nodes further away in the frustum. I don't really want to be drawing an entire frustum worth of oct tree nodes if I'm in a room looking at a brick wall.

I'd really appeciate any pointers or thoughts, thanks.

Share this post


Link to post
Share on other sites
I would also be very interested to hear anything anyone has to say on the matter. These days, doing visibility mostly or entirely in realtime, without precomputed visibility data, seems to be the popular thing to do. I've tried to find in-depth technical information about Unreal Engine 3's visibility tech, but that search has been largely fruitless. Epic created a page that shows ways to be a good visibility citizen when constructing UE3 levels, and it describes the main tech very briefly. It "conservatively" culls primitives that "are classified as entirely invisible by convex zone frustum tests." I didn't find that description terribly helpful, but there you go.

The page goes into more depth describing the things level designers can do manually to improve visibility logic. They can make primitives cease rendering after a certain distance, and also use a level of detail system to collapse multiple primitives into one.

http://udn.epicgames.com/Three/VisibilityCulling.html

http://udn.epicgames.com/Three/MassiveLOD.html

Share this post


Link to post
Share on other sites
The way I understand it, it is the other way around, Portal systems superseded BSPs for rendering.

The following is just my perception, I could be entirely wrong [smile]:

As hardware took over software rendering, a lot of optimization was moved to the hardware pipeline, making most software optimizations unnecessary, so most of the time you want to limit what you send down the 3d pipeline in some way, but you need not be 100% precise as to what, some scene partitioning (personally I like portals for indoors and octrees for outdoors) and frustum culling should be enough these days (maybe some back face culling too).

Share this post


Link to post
Share on other sites
Quote:
personally I like portals for indoors and octrees for outdoors

Doesn't portal-based rendering go hand in hand with BSP rendering? Or maybe you could use an oct-tree for the interior rendering combined with portals?

Share this post


Link to post
Share on other sites
Typically, in a portal engine you still use a BSP to find the area or zone a given point (camera, spotlight) resides in. From there you traverse the portal graph.

The BSP can be generated from some lowres structure of the level that doesn't necessarily have to be visible in-game, but it can be.

A more dynamic method might be some sort of hierarchical occlusion culling, but I haven't looked into that. Often hardware occlusion queries perform bad (3+ frames latency etc) so you might need a software renderer for this (Frostbite and others) or a geometric approach (planes and solids). The geometric approach works well for cities but really bad for trees and vegetation.

I think that Unreal uses BSP + heavy occlusion culling. The BSP is often really simplistic and might also be nonexistent on some level.

Share this post


Link to post
Share on other sites
Quote:
Original post by RobMaddison
Doesn't portal-based rendering go hand in hand with BSP rendering? Or maybe you could use an oct-tree for the interior rendering combined with portals?


Not necessarily, you can take advantage of BSPs to automatically place portals, but you can also place portals manually or using a different algorithm to do the automation.

BSPs help a lot in determining which portal area an arbitrary point in space is located at, but you can certainly use a different approach to do this, oct-trees or a similar AABB based structure can be used as well.

I use BSPs, but mostly for collision detection, and determining which portal area to render, which is the only role they have in rendering.

Share this post


Link to post
Share on other sites
PVS can be still used for large levels, but instead of tesselating space with BSPs, you can simply use regular tesselation (grid, octree etc). The result does not have to be perfect, but should cull the obvious cases. You'd also rather not save the PVS the quake way, but rather using an oct-tree (8bit fit quit nicely).

Hardware Occlusion culling can be used to cull the near scene, but you must be careful, it's not as fancy for framerate as it sounds.
1. if you're drawcall limited and you submit occlusion queries for objects you dont see, you still submit drawcalls
- you can use hierarchycally tests, but you'll increase the latency quite a lot if something gets visible and due to the hierarchy you might submit even more drawcalls in worst case (and that's what you're optimizing for)
2. what you save is vertex transforms (and maybe some setup cost), not visible pixels are anyway culled (if you render front2back) by the hardware. and Vertex transforms are kind of cheap (crysis 1 is submitting some million triangle/s on G80 hardware).
3. occlusion queries can result in very unstable rendering, you might see the bounding box of something you test, but not the object itself. The result would be back and forth switching between that object. in some cases, e.g. forest, there might be a lot of those objects and you get a very jittery framerates.


If you really dont want to have long precomputing times for PVS, use portals and anti-portals. They can be evaluated quite easily on cpu, they are conservative and can be quite handy in other areas like AI (visibility testing) or sound (occlusion, reflection).
By portals I mean artist set (anti-)portals, it's not much work and more error-prone than automatic setting, especially with nowadays complex scenes.
Beside just rendering an object, culling also servs the sake of streaming. Making tests more convervative gives you some time to stream in objects before they get really visible, cause your culling will mark them visible quite some time ahead. In some cases, artist can put some occluding wall right after a door, not showing the room behind it at all, but the rendering side might not have to cull those objects and therefor stream them in. That's bad culling on purpose.

Share this post


Link to post
Share on other sites
perhaps you should checkout the occlusion lib Umbra? they are using tons of modern day techniques and an sdk is available on trial basis, for non-commercial use. perhaps it can be a source of inspiration for you?

Also, the torque game engine has support for both bsp and octree spatial partitioning. what happened with the latest version of the engine is that octree partitioning was faster than bsp partitioning. i dont know if thats always the case, but yeah.

hope this helps a bit in deciding!

Share this post


Link to post
Share on other sites
Some great info to work with there guys, thanks.

One thing that's always got my wires crossed is the concept of using a PVS with portals. Why would you need a full PVS if you have portals. Would you not just put a portal polygon in place between two 'zones' (be they octree nodes, BSP convex hull leaves, etc) and store the id of the leaf that can be seen the other side of the portal (and vice versa for the opposite side)? Then if that portal polygon is in the viewing frustrum, draw the leaf on the other side, rinse and repeat. I guess that this is a PVS of some fashion, but sounds a bit easier to implement and maintain than the regular bitwise method.

Perhaps I've misunderstood and portals and PVS are mutually exclusive…?

Share this post


Link to post
Share on other sites
Portals and PVS's can be used together to good effect, or be used completely separately.

Let's go through the combinations:

Portals (only):

- Visibility is computed from the camera /point/, tending to improve accuracy.
- Visibility is computed on the fly, removing the need for preprocessing and additional data structures.
- Can (with difficulty) handle the dynamic object occluding static object case.

PVS (only):

- Does not in general need a portal/cell subdivision of the scene, making it useful for outdoor scenes, forests, indoor scenes with a gazillion visible portals (this kills the efficiency of portal based algorithms), etc.
- Can process offline, so it can spend minutes to hours chugging away at generating optimal (for a view cell) visibility.
- Does not in general handle dynamic occludiing static object cases (but does handle static covers static, and static covers dynamic).

PVS + Portals:

- Uses portals to compute the PVS for each room.
- It can preprocess the anti-penumbra of the portals so that only the visible PARTS of the cells are rendered (usually to expensive to do at runtime).
- The set of visible cells are predetermined, so little run-time clipping is needed.
- Portals can be combined with PVS so that the PVS is cut down to the camera POINT subset of the PVS, but still only considering the PARTS of the cell that are potentially visible from the camera view cell. The net result is higher accuracy that normal portal rendering, at the cost of preprocessing the scene.
- Using portals to generate the PVS is typically much easier/more-accurate/faster than computing the PVS for generic triangle based scenes.

Realtime portals paper


Portals+PVS papers/thesis (go to 1992)

Non-portal PVS papers/thesis

Share this post


Link to post
Share on other sites
I'm using a sort of hierarchical z-buffer visibility.

Using an octree, I draw only what is inside the frustum, in a "partial" front-to-back order (because only nodes are ordered, not triangles). At the beginning, I render a number of nodes to be sure to almost entirely fill the screen-space area. Then I make a z-pyramid (where the first level is the zbuffer itself and the last the farthest visible pixel) using hardware but finally downloading it (only the last levels) into system memory. From now on for each node I check it agains this z-pyramid without using any hardware occlusion query, culling it if not visible.
I use also the z-pyramid to fast cull actor/general objects meshes that are hidden by something.

Share this post


Link to post
Share on other sites
Some more great info guys, thanks.

I've been thinking though, possibly portals and an octree is enough for indoor environments with today's hardware. Like this:

1) Keep the static interior geometry very simple, i.e. just walls, any more complicated areas will be created as static objects.
2) Add the necessary portals to each node
3) At runtime, check which zone the camera is in and retrieve the list of portals that are within the camera frustum
4) Using each visible portal:
4a) Create a new frustum using the portal and draw the simple static interior geometry of the neighbouring zone it has a view into
4b) Cull the neighbouring zone's detailed static (e.g. radiators, window frames, etc) and dynamic geometry against this new frustum
4c) Retrieve a list of the portals which belong to the neighbouring zone and that are within the new frustum and repeat step 4 recursively until no more portals are found

I know this is generally how a portal engine works, but with this method, I don't really see the need to have a pre-computed PVS (as in Crowley9's "Portals (only)" description). If the static interior geometry is kept simple enough, i.e. as square as possible, the GPU should be able to easy handle any overdraw - there won't be that many wasted vertex transforms. Rooms where there are more complicated areas, like for instance, a curved wall, alcoves or broken areas, can be stored as rectangular but have these more complicated pieces stored as additional static geometry pieces that can be culled away by the frustums.

I haven't had a chance to try this out yet but does it sound okay?

Share this post


Link to post
Share on other sites
few years ago i've invented a little trick that seems to nicely combine portals with hardware occlusion query, basically i subdivide scene using kd-tree that also keeps information about portals between cells faces then every frame i locate camera and render traditionally like i would classic portals, except instead of using explicit recursion i use queue that also keeps occlusion queries. that way every time i pop portal to visit from queue it usually has occlusion query completed and can be decided if i should drop it or visit destination cell, render its contents and add its portals to queue initialising queries

Share this post


Link to post
Share on other sites
How clever must your code be? Serious question, is this about settling things in your mind or getting the job done?

Reason I'm asking is that I tried many systems to get this working on a polygon soup mesh and there really isn't a good way to do it. You need the CSG information from apps like worldcraft to make a good fist of it without spending years at.

So I made a little program which showed me a level with a top down isometric camera. I drag squares over various zones, and a right click allows me to link them up. When you're in one of these zones, you draw the ones that are linked also.

Works like a charm, takes about 10 man minutes per level to make the data. Job done.

Short version: Not everything has to be automated.

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