Sign in to follow this  

Efficient visibility/occlusion testing in software

Recommended Posts

jefferytitan    2523
Hi people,

I'm trying to figure out a way to do efficient visibility testing in realtime. The tool (Unity indie) that I'm using offers raytesting, but (to my knowledge) no occlusion testing or read access to the depth buffer. My problem domain is to detect visibility of a set of boxes (say up to 30) in a scene with hundreds of occluders (boxes, spheres and cylinders). Assume that none of the boxes I'm testing for intersect with an occluder.

I've considered various ways, e.g. recursive subdivision with raytesting, rendering a coarse version of occluders to see what they cover. Feel free to suggest any other approaches. A problem that often comes up is getting a projection of a 3d object into screen space.

My first question is whether anybody knows of an efficient recursive approach to rendering, e.g. all I care about is whether a square is fully covered or not, and if only partially covered recurse at higher detail. If not, what's a good rendering approach if all you care about is the depth at each pixel position and which object it belongs to?



Share this post

Link to post
Share on other sites
Krypt0n    4721
if the scene is static (which is quite a common case), you could pre-calculate the visibility for a grid (for every grid cell), and then just use it for rendering when you're rendering. there are various ways to store it efficiently, I think the Quake engine stores for every 'cell' of their BSP tree an Runlenght compressed bit-buffer. some store a recursive octree (storing per not if "nothing" "everything" or "partially visible, in the last case you go one node down the tree and check again).

if you can integrate a 3rd party tool, I'm still offering my occlusion lib ;)
(shameless self promotion :) )

Share this post

Link to post
Share on other sites
MJP    19753
Lately the idea of completely dynamic visibility testing via depth buffer generation has become somewhat popular, so you could [url=""]look into that[/url]. Otherwise PVS techniques have been around a long time and still get the job done, provided most of your scene is static.

Share this post

Link to post
Share on other sites
Hodgman    51221
[quote name='jefferytitan' timestamp='1341538872' post='4956176']I've considered various ways, e.g. recursive subdivision with raytesting, rendering a coarse version of occluders to see what they cover. Feel free to suggest any other approaches.[/quote]Do you need [i]exact[/i] results, or just good enough to optimise your rendering?

Once approach that I've seen in a few games that I thought was so simple that it's clever is:
*Project the conservative bounds of all your occluders into screen-space.
*Select the 5 ([i]or [font=courier new,courier,monospace]n[/font][/i]) occluders with the largest screen area.
*Create a frustum from each of these occluders to get their occlusion volume.
*Perform a "frustum fully contains" test for each occludee's bounding volume against each occluder frustum.

It's very dumb, coarse, and kind-of brute-force, but it's been used in a few AAA console games and is actually very efficient computation-wise ([i]assuming you've got sensible data layouts[/i]). Edited by Hodgman

Share this post

Link to post
Share on other sites
Tordin    625
there is an practical, occlussion slide that is pretty nice, i implemented my own occlussion test in a very similar way.

for the game i made (tight corridors and lots of rooms) this work realy good.
and for this aproach, there is tons of things to improve to get it realy efficent and good working. Edited by Tordin

Share this post

Link to post
Share on other sites
jefferytitan    2523
@Krypt0n: Wow, impressive work. My guess is that it would be tricky to integrate with Unity sadly, but my hat off to you! Pre-calculation is a possibility, but the question is still how (just without the performance factor).
@MJP: Will read up on that. Thanks.
@Hodgman: Interesting approach. The purpose actually is for dynamic instantiation of game assets including enemies and set pieces, so the approach needs to be conservative enough to avoid screen pop. If it sounds complicated... I'm trying to be tricky. ;)
@Tordin: Thanks, will read up on that.

Share this post

Link to post
Share on other sites
bwhiting    1562
I came up with my own hybrid approach based on what I had read and the limitations of the platform I am on (flash / actionscript 3 - slooooow)

First off:
A proper depth buffer is something that I wanted to avoid, speed saving.
So I came up with the idea of just using the furthest depth of the triangle to determine the colour of it, also encoded in the colour is the id of the occluder - important later.

The system dynamically chooses the nearest N (i.e. 15) number of occluders from a pre defined list, solid shapes only and ideally planes, boxes or simple geometry but anything that contains no holes/gaps will work.

These are then rendered from back to front into the special buffer of awesomeness.
Once done you can run through all your occludees checking only their projected bounding boxes, if any point it is nearer than the same point in the buffer then render the object, otherwise you then store the id of the occluder from the buffer and move through the rest of the points, if any of following ids is different, then render the object. if all the ids match when you get to the last vertex then boom occluded, so only 8 pixel reads and a couple of shifts to occlude one object (or object group for some more power)

The reason for the ids is so that if an object is hidden behind two separate occluders but there is a gap between them it will not get occluded.

Some objects that are fully occluded (by more than one occluder) will still be occluded.
There are also other cases where something that could have been occluded but is not, i.e. due to using the depth from the furthest point on the triangle, so a very big triangle may not occlude things hidden behind it that are very close to it.
You have to provide the occluders, planes and boxes are good enough in most cases

No objects that should not have been occluded will be.
Fast! No need to check every pixel for a an area quad against a depth buffer and no need for a full z-buffer in the first place.
Early outs for the algorithm
(there is also one top secret benefit that I worked out that can be very useful but is more applicable to certain scene types, I will explain this one in a blog post when I finally get round to documenting the process properly.

If anyone wants to know more or if I made no sense just badger me a bit and should motivate me to write it up properly.

Might be a totally flawed system but I got good results so far and that was in flash so in something like c++ this should be fast as lightning.
Either way am proud of my approach [img][/img]

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