What is used for visibility determination these days?

Hidden surface removal and visibility determination used to be hot topics years ago. However, gradually, they seem to have faded in the background, so I wonder what people use nowadays. A mix of (old) techniques such octrees/quadtrees, BVHs, and conditional geometry? Am I missing some new killer algorithm / data structure?

I think more and more developers are moving towards occlusion culling in software. it's fast enough, you have no turn around times which is important for development speed, you also don't have setup costs (like e.g. creating portals) and you have all the flexibility you need.

regarding data structures, quite some games seem to use just an array of objects that they process in one go, this seems to be faster than suffering from cache misses by jumping to random places in hierarchical structures.

as krypton mentioned, rendering occluders in software on a small canvas is popular these days and fast too, dice did a nice paper on it.

as far as culling goes, good ol frustum culling (accelerated with caching last result) can blitz though an array of thousands of objects very very easily, and that of course could be combined with some form of bvh to reduce the number of tests down but only really necessary if you have over a few thousand individual objects at any given moment.

What about conditional/predicated geometry? Wouldn't that make software occlusion obsolete?

What about conditional/predicated geometry? Wouldn't that make software occlusion obsolete?

Not at all. Predicated rendering allows GPU to skip work efficiently, but everything involved in CPU processing is still full blown. If this involves complex CPU skinning, texture streaming or stuff like that, the CPU hit can still be significant.
Culling saves both CPU and GPU work.

[font=arial, verdana, tahoma, sans-serif][size=2]What's the benefit of software occlusion queries, as opposed to hardware occlusion queries ?
I mean, if done correctly hardware queries could be fast (no stall) even in DX 9.0, if fetching the results next frame.[/font]
What about using instancing and occlusion culling ? For example, if a forest is rendered using instansing of a single tree, using a single draw call, how this fits with occlusion culling ?

Another simple system that hasn't been mentioned yet are occluder planes. I know of several "AAA" console games from this generation that only used frustum culling and occluder planes for visibility. The level is authored with large 'quads' inside any large walls/etc that occlude a lot of geometry. Each frame, the quads are frustum culled, overlapping quads are merged, and small/usless quads are rejected, which produces the list of occluders to be used that frame.
A list of bounding volume indices is processed by the frustum culling job (easily parallelizable) which produces a new list of indices (culled volumes removed). The second list is passed to another job, which tests each volume against each occluder (also easily parallelizable). If implemented correctly, tens of thousands of volumes can be culled in no time at all, with no precomputation. The final list of visible-volume indices is used to retrieve the visible objects to be rendered that frame.

Am I missing some new killer algorithm / data structure?

The killer technique these days, is simply taking old techniques and applying data-oriented and multi-core/GPGPU programming techniques to them.

[font="arial, verdana, tahoma, sans-serif"]What's the benefit of software occlusion queries, as opposed to hardware occlusion queries? [/font]
[font="arial, verdana, tahoma, sans-serif"]I mean, if done correctly hardware queries could be fast (no stall) even in DX 9.0, if fetching the results next frame.

If you implement with a one frame latency, then this is a huge draw back, not something to just brush over. There's not very many examples where I would put up with huge rendering artefacts simply because they only appeared for one frame at a time.[/font]
In order to have the one-frame latency and have no artefacts, then you need to know the positions of all objects/cameras one frame in advance, which is also possible, but instead introduces an extra frame of input latency (and a lot of system complexity), or alternatively, it requires you to always render objects that you don't have timely results for.

Second, hardware occlusion queries are expensive. For each bounding volume that you want to test, you've got to pay the CPU-side cost of issuing a draw-call (and the associated report-gathering), and on the GPU-side you've got to pay the rasterisation/fill costs. If you've got a large world with tens of thousands of objects, then this simply isn't feasible in practice.
In practice, a game-world can have millions of cullable objects in it -- a naive occlusion query system requires you to submit draw-calls for each one of them, and generally you only want to be issuing between a few-hundred to ten-thousand draw-calls per frame total (including real rendering), depending on your CPU-budgets.
To make this feasible, you've got to implement a complex system such as CHC+, which has it's own list of draw-backs.

Note, there are GPU-side alternatives to hardware occlusion queries, such as the HZB, as implemented in the "rendering with conviction" presentation. This particular technique only requires a single-draw call (instead of tens of thousands) and doesn't require rasterisation of the bounding volumes, which makes it much more scalable (and simpler) than the above techniques.

What about using instancing and occlusion culling ? For example, if a forest is rendered using instansing of a single tree, using a single draw call, how this fits with occlusion culling ?[/quote]Your culling system should not be directly tied to your renderable-object system (no dependency between them). Usually a 3rd system will use the results of the culling system when preparing renderable objects.

Two options would be to link all instances of that tree to a single cullable (either draw the whole forest or don't), or link each tree to it's own cullable, and have the instancing system adjust it's per-instance data buffers appropriately upon recieving the culling results (i.e. only include data for visible trees and adjust the instance-count), but this highly depends on your instancing system and your circumstances.

What about conditional/predicated geometry? Wouldn't that make software occlusion obsolete?

Only if you can afford to pay the CPU-side costs of rendering every item in your world every frame, and the GPU-side cost of rendering every bounding-volume every frame. In some games, this might be feasible. In any kind of game with complex visibility requirements (i.e. more than simply frustum culling), it probably isn't feasible.

What about 3rd party libraries? I don't see much talk about them.

Generally because there isn't any.

The main people doing software occulsion are big studios who do their own bespoke version for their specific needs. The other group are hobbiest, many of whom will do it 'just because' or as part of an engine.

There isn't really a 'general solution' to the problem as the way of solving it is somewhat scene/data/engine/pipeline dependant.

What about 3rd party libraries? I don't see much talk about them.

There is Umbra which has been used in a large number of well-known games.

[quote name='Amr0' timestamp='1318417214' post='4871795']
What about 3rd party libraries? I don't see much talk about them.

There is Umbra which has been used in a large number of well-known games.
[/quote]

Yes, it seems to be "the industry standard" and used by Unity. No love for the poor man though it seems.

Another simple system that hasn't been mentioned yet are occluder planes.

Are those also called antiportals? I googled them and I found a paper which seems pretty similar to antiportals in concept.

Are those also called antiportals? I googled them and I found a paper which seems pretty similar to antiportals in concept.

Yeah I'd probably use the terms 'occluder plane' and 'antiportal' interchangeably.

Your culling system should not be directly tied to your renderable-object system (no dependency between them). Usually a 3rd system will use the results of the culling system when preparing renderable objects.

Two options would be to link all instances of that tree to a single cullable (either draw the whole forest or don't), or link each tree to it's own cullable, and have the instancing system adjust it's per-instance data buffers appropriately upon recieving the culling results (i.e. only include data for visible trees and adjust the instance-count), but this highly depends on your instancing system and your circumstances.

Thanks.
Well, I was asking, because I'm using hardware occlusion culling with DX 9.0 queries. I needed to implement a big forest, had the frustum culling of the trees tied with terrain quadtree culling, but for the occlusion culling I was facing a dilema :
In order to make my occlsusion culling to work, I needed to render the trees individually and fetch the result to see which tree acts as occluder and which as occludee, issuing a draw call per tree, but in order to make my instancing actually be helpful, I needed to draw many trees with one draw call. As my forest is actually culled with visible terrain chunks, using the results of a quadtree culling, maybe I should treat my terrain chunks as a whole, render instanced trees per chunk and occlude next chunks with trees, mixing the occlusion and instancing that way.


Can you guys point me to a nice article/sample code about software occlusion culling.

Hodgeman - Why would the artefacts be so bad for a one frame delay? Most objects wouldn't move that much in a single frame, and those that do could maybe be removed from the occlusion system.

dice slideshow

Why would the artefacts be so bad for a one frame delay? Most objects wouldn't move that much in a single frame, and those that do could maybe be removed from the occlusion system.

It depends on the game... but in general the camera can move a lot each frame, which means that every object can move a lot (in camera-space) ...which means you're going to have to remove every object from the occlusion system? ;)
e.g. In a first-person shooter, the camera can rotate by an arbitrary amount each frame -- if one frame a doorway is off-screen, and then next frame the doorway is visible, then an entire room (or an entire landscape view out of a window) could fail to render for that frame. That's pretty awful.
As I mentioned though, you can work around this particular issue if you know next frame's camera position in advance, which is pretty simple (although it increases input latency), and then only leaves the movement of objects as a source of artefacts.