Jump to content

  • Log In with Google      Sign In   
  • Create Account

Efficient visibility/occlusion testing in software


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 jefferytitan   Crossbones+   -  Reputation: 2242

Like
1Likes
Like

Posted 05 July 2012 - 07:41 PM

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?

Thanks,

JT

Sponsor:

#2 Krypt0n   Crossbones+   -  Reputation: 2656

Like
2Likes
Like

Posted 05 July 2012 - 11:32 PM

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 ;)
http://www.gamedev.net/page/community/iotd/index.html/_/one-billion-polys-r85
(shameless self promotion :) )

#3 MJP   Moderators   -  Reputation: 11737

Like
1Likes
Like

Posted 05 July 2012 - 11:48 PM

Lately the idea of completely dynamic visibility testing via depth buffer generation has become somewhat popular, so you could look into that. Otherwise PVS techniques have been around a long time and still get the job done, provided most of your scene is static.

#4 Hodgman   Moderators   -  Reputation: 31798

Like
1Likes
Like

Posted 05 July 2012 - 11:58 PM

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.

Do you need exact 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 (or n) 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 (assuming you've got sensible data layouts).

Edited by Hodgman, 05 July 2012 - 11:58 PM.


#5 Tordin   Members   -  Reputation: 604

Like
1Likes
Like

Posted 06 July 2012 - 01:48 AM

http://www.guerrilla...m/publications/
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, 06 July 2012 - 02:42 AM.

"There will be major features. none to be thought of yet"

#6 jefferytitan   Crossbones+   -  Reputation: 2242

Like
1Likes
Like

Posted 06 July 2012 - 05:35 AM

@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.

#7 bwhiting   Members   -  Reputation: 814

Like
0Likes
Like

Posted 06 July 2012 - 06:56 AM

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.

CONS:
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

PROS:
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 Posted Image




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS