Crossbones+ - Reputation: 2455
Posted 05 July 2012 - 07:41 PM
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?
Crossbones+ - Reputation: 3930
Posted 05 July 2012 - 11:32 PM
if you can integrate a 3rd party tool, I'm still offering my occlusion lib ;)
(shameless self promotion )
Moderators - Reputation: 15554
Posted 05 July 2012 - 11:48 PM
Moderators - Reputation: 45751
Posted 05 July 2012 - 11:58 PM
Do you need exact results, or just good enough to optimise your rendering?
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.
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.
Members - Reputation: 604
Posted 06 July 2012 - 01:48 AM
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.
Crossbones+ - Reputation: 2455
Posted 06 July 2012 - 05:35 AM
@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.
Members - Reputation: 1181
Posted 06 July 2012 - 06:56 AM
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