Sign in to follow this  
Lugerns

Image space occlusion culling

Recommended Posts

I am trying to implement Image space occlusion culling for my master thesis. And I have a few questions, about the speed of the software rasterizer, how many faces it should be able to render ever frame. 1. How many faces do you render to the occlusion map, during the generation of the occlusion map every frame, do you use the original faces or a 3D skin, do you only select some faces to be renderd or do you render the whole leaf(from the spatial division tree)? 2. How many faces do you generally test against the occlusion map every frame to see if they are visible or not, and what kind of BV do you use to test, an AABB, a 2D screen space rectangle calculate by the points of the AABB or a 3D skin? 3. If you have a big outdoor environment and about 256 leafs (leafs from the spatial division tree) visible in my frustum would it not be very expensive to test all these leafs against the occlusion map or, my current rasterizer can not do this white a good frame rate (~30fps). Should it be able to or should I use a different approach (or bigger leafs or something)? 4. My occlusion map size is 256x256, should I use a smaller map? /Luger [Edited by - Lugerns on May 26, 2005 9:38:16 AM]

Share this post


Link to post
Share on other sites
well so far i'm using real scene geometry and dynamic kd-tree, of course it would be better to use simplified geometry for occluders.
there's full source with demos http://sourceforge.net/projects/ooce

Share this post


Link to post
Share on other sites
Quote:
Original post by Lugerns
1. How many faces do you render to the occlusion map, during the generation of the occlusion map every frame, do you use the original faces or a 3D skin, do you only select some faces to be renderd or do you render the whole leaf(from the spatial division tree)?

I use lowpoly 3D occlusion skins. On the average, I render around 2k to 3k faces into the map per frame.

Quote:
Original post by Lugerns
2. How many faces do you generally test against the occlusion map every frame to see if they are visible or not, and what kind of BV do you use to test, an AABB, a 2D screen space rectangle calculate by the points of the AABB or a 3D skin?

The screenspace projection of the geometry AABB or OBB. I test every leaf that passes through all other visibility tests against the HOM. Usually around 1000 leaves per frame, with 700 to 1200 faces per leaf (on the average 800k to 1m faces visible per frame).

Quote:
Original post by Lugerns
3. If you have a big outdoor environment and about 256 leafs (leafs from the spatial division tree) visible in my frustum would it not be very expensive to test all these leafs against the occlusion map or, my current rasterizer can not do this white a good frame rate (~30fps). Should it be able to or should I use a different approach (or bigger leafs or something)?

Well, 256 leaves shouldn't be a problem. Have you optimized your rasterizer ? Did you include all possible ways of early rejection or aggressive culling ? A different option is to increase the number of faces per leaf, and reduce the leaf count respectively. How many faces are in one leaf currently ?

Quote:
Original post by Lugerns
4. My occlusion map size is 256x256, should I use a smaller map?

256 is good. 128 can still be viable in many cases (especially closed environments). More than 256 doesn't increase culling efficiency enough to justify the rendering overhead. Lower than 128 becomes very inefficient at culling.

Share this post


Link to post
Share on other sites
Quote:
Original post by Yann L
I use lowpoly 3D occlusion skins. On the average, I render around 2k to 3k faces into the map per frame.


Ok, so you make a 3D occlusion skin from the geometry you have in the leaf?
If so what if you have a dynamic object in the leaf that changes position, then you have to recalculate the 3D skin, or do you handle dynamic objects different?

Quote:
Original post by Yann L
The screenspace projection of the geometry AABB or OBB. I test every leaf that passes through all other visibility tests against the HOM. Usually around 1000 leaves per frame, with 700 to 1200 faces per leaf (on the average 800k to 1m faces visible per frame).


So you first test the AABB or OBB, and if thats visible,
you "render it"(add it to your render list or something)
or
you test the geometry in the leaf or its 3D skin and the if thats visible you "render it"?

Quote:
Original post by Yann L
Well, 256 leaves shouldn't be a problem. Have you optimized your rasterizer ? Did you include all possible ways of early rejection or aggressive culling ? A different option is to increase the number of faces per leaf, and reduce the leaf count respectively. How many faces are in one leaf currently ?


I have just started to optimize (SIMD instructions) my rasterizer and I am getting better results By early rejection you mean if I use a hierarchy of occlusion maps? I am just using a single occlusion map (256x256), haven't implemented the hierarchy yet. I currently don't have anything in my scene except a bare and bumpy(hills) landscape so I can't do any major aggressive culling, yet, I just reject occluders that have 10 or less pixles visible. I currently have 1500 faces in one leaf.

I have much work left to do, just want to get everything clear before I continue the implementation.

/Luger

Share this post


Link to post
Share on other sites
Quote:
Original post by Lugerns
Ok, so you make a 3D occlusion skin from the geometry you have in the leaf?

A precomputation process (with some good help from the artists) makes a huge occlusion skin for the entire static part of the scene. The occlusion skin gets its own spatial tree, independent of the main tree. This is because the coarse skin doesn't really fit well into the very fine main tree, it would be split thousands of times, and a software renderer doesn't like splits too much (slow).

Quote:
Original post by Lugerns
If so what if you have a dynamic object in the leaf that changes position, then you have to recalculate the 3D skin, or do you handle dynamic objects different?

Each dynamic object gets its own private occlusion skin at built time. The skin undergoes the exact same transformations as the parent object, and is attached to the same leaf in the dynamic tree. For non-deforming objects, this is very straightforward, and very efficient. For things like skinning, updating the occlusion skin can get a little tricky at times - depends on the character.

Quote:
Original post by Lugerns
So you first test the AABB or OBB, and if thats visible, you "render it"(add it to your render list or something)

Yep.

Quote:
Original post by Lugerns
I have just started to optimize (SIMD instructions) my rasterizer and I am getting better results By early rejection you mean if I use a hierarchy of occlusion maps?

Yes. You can reject an AABB/OBB as visible, as soon as the number of pixels classified as "guaranteed visibility" goes over your aggressive culling threshold. With a hierarchy, this can usually be done at very early levels, so in practice, you'll test only a few pixels before rejection. Totally occluded leaves can also be rejected very easily as invisible, if their entire projection is classified "guaranteed invisibility" within the first couple of hierachical levels. This accelerates the process tremendeously. Only partially occluded leaves will need to recurse deeper into the map.

Share this post


Link to post
Share on other sites
Your occlsion skins are just used to speed up the generation of the occlusion map, and not anything else?

Quote:
Original post by Yann L
The occlusion skin gets its own spatial tree, independent of the main tree. This is because the coarse skin doesn't really fit well into the very fine main tree, it would be split thousands of times, and a software renderer doesn't like splits too much (slow).


Who do you build your occlusion skin tree, do you do any splitting or you just place the face in n number leafs that it intersects, and my by just split the really big faces?

/Luger

Share this post


Link to post
Share on other sites
Update: I read some of your other posts, I've realized that you *are* using pure software rendering to generate the occlusion maps. Interesting. Has anybody ever tried using an s-buffer-like algorithm for this sort of thing?

One thing that's never been clear to me is this: since you render these occlusion maps at lowish resolution (256x256), that's less accurate than a normal Z buffer. How do you handle the inaccuracy this creates? It seems to me that it would theoretically be possible for an object to be seen as "occluded" when in reality, it's sticking out from behind another object by a little bit.



[Edited by - Josh Yelon on May 27, 2005 3:32:13 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Josh Yelon
...
How do you handle the inaccuracy this creates? It seems to me that it would theoretically be possible for an object to be seen as "occluded" when in reality, it's sticking out from behind another object by a little bit.


Simple answer : you don't care.
The object contribution to the final image is too small to care. (ie you won't notice.)
That's also sometimes referred as "Agressive Culling", basically under a given treshold it's better to skip than to draw. (less expensive)

Share this post


Link to post
Share on other sites
Quote:

Your occlsion skins are just used to speed up the generation of the occlusion map, and not anything else?

Yes. They're conservative and not volume preserving, so they can unfortunately not be used for collision detection and similar. They only reproduce the depth silhouette of the object. A cylinder, for example, can be accurately represented by a 2 quad cross as occlusion skin.

Quote:

Who do you build your occlusion skin tree, do you do any splitting or you just place the face in n number leafs that it intersects, and my by just split the really big faces?

I built it just the same way I built the tree for the main geometry (I use an ABT), only on a coarser level. Means, the leaves have larger volume, and thus only really large polygons are split.

And btw, I render entire planar polygons (including concave and with holes), rather than individual triangles. This speeds up the interpolation gradient computation.

Quote:
Original post by Josh Yelon
Update: I read some of your other posts, I've realized that you *are* using pure software rendering to generate the occlusion maps. Interesting. Has anybody ever tried using an s-buffer-like algorithm for this sort of thing?

Isn't worth the trouble, and will probably slow you down. S-buffers were originally developped to get zero overdraw, because CPUs at the time had great difficulties keeping up with the pixel math, ie. the fillrate. Especially if you wanted things like perspective correct texture mapping (ie. one divide per pixel), minimizing per pixel computations by culling out parts of the span were essential.

Using a z-buffer with early rejection fixed that a few years later. Today, where SIMD can draw several floating point pixels simultaneously, the inner loops are so fast that the whole span linked list stuff will just be slower than brute forcing everything through the zbuffer. Especially since depth is the only interpolated attribute - no colour, no texture coords, just 1/z (or 1/w).

Quote:
Original post by Josh Yelon
One thing that's never been clear to me is this: since you render these occlusion maps at lowish resolution (256x256), that's less accurate than a normal Z buffer. How do you handle the inaccuracy this creates? It seems to me that it would theoretically be possible for an object to be seen as "occluded" when in reality, it's sticking out from behind another object by a little bit.

As Ingenu mentioned, that can happen, but will usually not be visible. A really good software renderer can minimize these effects by carefully adjusting subtexel rendering vs. subtexel testing policies. In principle, you make the subpixel testing conservative to the rendering. This removes pretty much all artifacts at the cost of a little culling efficiency.

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