Nature of the Beast: Occlusion Culling Discussion

First off, I'd like to please ask any Lindens out there to correct me if I'm wrong on my assumptions. Please, do feel free to get technical on us. Someone out here may surprise you with some tidbit of knowledge that helps your efforts.

Secondly, my findings are based on empirical testing and observations, and while possibly correct should not be taken as truth until confirmed by the people who wrote the system.


The occlusion culling system seems to be based off of a "box within a box" routine. A sim appears to be cut into 64m^3 boxes at all times. The system then subdivides which ever box you're in into smaller 32m^3 boxes (8 of the in total), and again subdivides the box that you're in into yet smaller 16m^3 boxes, followed by subdividing the box you're located in into the final and smallest size of 8m^3. Culling appears to occur on any box you cannot see at all, which means all prims within those boxes are not rendered. If you can see any part of those boxes, all the contained objects are rendered.


The test:

Find a nice open sim. I sat out on the beach of Ahern for my experiment (48, 154, 22). Look about you with Debug->Rendering->Info Displays->Octree active. You should see a few red blocks and lots of lines forming cubes from monsterous sizes off in the distance to smaller and smaller ones around you. To begin testing the culling of the smallest blocks from you, errect a 20m x 30m wall (width doesn't matter) and position it in the same cube that you are so that the wall is not even touching the other smallest cubes you wish to cull. Reset your camera (esc) and turn to look at the wall. Zoom out a little, but only enough to make the background blocks being culled visible. You should notice that there are one or two 8m tall and wide (or rather in the case of two, an 8x16) red box.

To continue the test, zoom in closer to the wall. More blocks appear as they vanish behind your wall because you can no longer see any part of them. Those areas are being culled as well. As a final test, fully enclose yourself in a 20x20x20 box and make sure your camera is inside of it. You'll see red everywhere except in the boxes your 20m^3 box intersects.


Pros and Cons:

The upside of this system is very obvious, as a programmer. Subdividing numbers in powers of 2 (64, 32, 16, and 8 are all powers of 2) is memory efficient if you program it right (which it seems like it has been) and faster to compute. No fancy code to jump through hoops, just shift a bit left or right and you've got a larger or smaller power of 2. Bit shifting is faster than dividing or multiplying by the way. This means the scanning routine for figuring out which blocks are visible or not can more easily be calculated and the correct blocks are culled in short order. Since you're only doing bit shifting on the boxes you're residing in, no unnecessary computing power is being used to scan an unnecessary amount of boxes. Just the minimum required to do the job. Result, I get 20 fps at ground level for possibly the first time in my time on SL (prior to constructing the aforementioned box, my fps was 5!). In conclusion, this system works very well indoors.

The downside of the system is equally obvious. At long camera shot (views where you can see your avatar from a distance) the culling system is defeated because you can see more of your surroundings. Also highly primmy structures that fit within the larger blocks that you see remain rendered, even if you're only catching a corner of the cube they reside in. So in certain circumstances, like outside (which much of SL is made up of, outside areas) this culling routine doesn't work at all or does a very poor job.


Possible Solution to the problem:

I stated in another thread that the culling is not aggressive enough, but at the time I didn't know how the system worked and was basically impotently shaking my big stick saying, "make it work better!" One of the throng of previewers who were sad, confused, and uninformed. Having done these tests I've come to a conclusion that might solve part of the culling problem:

Reduce the largest cube size from 64m^3 to 32m^3.

The smaller the scale of cubes, the better the culling system works. However there is a balancing issue in play here. The smaller the scale of the culling cubes, the more of them there needs to be to fill the sim, and the more overhead goes into the scanning routine. At a certain point the refinement becomes too intense and you waste more processing power figuring out what not to render than if you were to render it. However, it is my belief that a reduction of sizes from 64 to 32m^3 would not impose such a processing strain and would in the end benefit the rendering system in the long run.


Further Recommendations:

If the solution above is accepted, I feel the subdivisions should be kept at the same depth so that the smallest set of cubes becomes a 4m^3 set. This will enhance the culling of nearby objects for home owners on the mainland who's houses may broach the edges of their plot and come uncomfortably close to their neighbours with their bright neon lights and spinning animated prims.

Addendum:
In parting thoughts as my brain shuts down for the "evening" (<checks his watch and sees it is indeed approaching 8am EST, though no sleep has been had yet>, offering the end user a slider ranging from 4m to 64m in powers of 2 to choose how many major subdivisions there are for the renderer would allow individual users to adjust the culling system for their own computers, allowing people with SotA rigs to play with lower divisions to see if there's any improvement for them, and people with normal rigs to hover between the higher values to tweak as needed. If this IS implemented, I recommend the smallest culling box be 4m^3. If you need occlusion culling to clean up the space within an 8m radius of you and can manage to get a significant frame rate increase, there are too many prims being used. x.x

First off, observation #2 is wrong. Culling is done from the camera's POV, and has to be so because it's using the rendered scene for the hardware occlusion query.

Secondly, the quads are not only divided in the region around your avatar, but wherever a certain threshold of object count is exceeded. There is a minimum size, but probably more harm than benefit would result from user tweaking of it.

And yes, when you're flying up above everything there's only so much that can be culled. At that point the algorithm just needs to spend as little time checking occlusion as possible, so smaller quads are a liability.

Sorry, I think observation 2 might be worded a little ambiguously. What I meant was that my observations saw the smallest cubes still around my avatar when I zoomed out and that those cubes would not recalculate unless I moved my avatar. What it really should be doing is recalculating the smallest cube set based on your camera position, because that's where you're looking from. In mouselook mode, basing the calculations on the avatar makes perfect sense though.

At any rate, could we at least try to have the cubes 32m across for a day, or hack together a command we can enter somewhere to adjust it just to test?

Question; What about avatars? I won't have time to properly test 1.9.1, but does occlussion culling include avatars and the attachments they are holding?
Also, what about linked sets and large/otherwise-obscured avatars? Are the prims you can't see culled and the remaining ones left, or does it leave linked-sets either visible or not visible?

Lastly; does this include textures? ie if I TP into a sim inside a building where I can only see a handful of textures, does SL load those textures first before dealing with other textures (if at all)?

Texture loading (for me at least) always seemed to radiate outwards from your avatar, with things closest to you loading faster than those farther from you. Sometimes that's a bad thing, especially when you jump into TeaZers with a two story mall in your face, but they're all farther away than the platform and its three or four textures. o.o;

I would theorize that avatars in culled cubes would cease to be drawn as well, but I'd need to find someone with an excessively laggy set of attachments to test the OC on. The obvious problem though, is that the culling is almost nonexistant in an open area and so all avatars would still be rendered. You'd have to be inside a room of some sort before it would cull effectively.

Sounds like something to put in "Debug -> Rendering > Occlusion scale" allowing people to select 128, 64, 32, 16. Why 128? because on my older computer I seem to lose a couple of FPS when I turn occlusion on outside, so for some people even 64m is too small...

Except 64m^3 is huge, and if you even see a portion of one of the cubes it doesn't get culled. You'd have to be zoomed in to like... a 30 degree field of view or smaller to not see all the 128m^3 cubes around you. x.x

According to Steve Linden, occlusion culling doesn't affect avs, particles (unless the emitter prim they're coming from is culled, of course), or LOD recalculation.

/290/c5/100140/1.html

Ah, I was just wondering the occlussion culling would effect this though. As you could TP into a room (sticking with mall here) where there are LOADS of textures close to you, but you can't see many of them because they are behind walls. If the objects they are on (or even the prim face if it could do that) were in a culled cube, then it wouldn't need to load that texture, at least not immediately (it would be fine to do so after you've loaded the immediate objects for example).

As for it not culling avs, that really sucks IMO. As a lot of the time the environments don't cause lag for me, it's having a large number of nearby avs, although maybe more importanlty their attachments? So, if an av isn't culled, are their attachments?
For example; if an av is standing so that they are half in a culled cube, and half outside it, would the attachments on the culled half be removed just like 'normal' (non-attached) objects? If so then this would help immensely in many areas, as the furry crowd seems to have an abundance of prim-heavy avs, many with things like particle wings. If I were to go upstairs in a building with loads of them downstairs, then it'd be nice to have no lag from them/their attachments as a result of being upstairs

That would seem like a Very Good Idea (tm) to me. Any words to share on this Yedwab?

Still haven't had time to try this myself, but how does occlussion culling behave with transparent objects? e.g if I have a window, will it still render everything outside it as normal? What if it's 1% transparent?
Was just wondering about this, I recently moved my house which has a nice glass roof, but I'm trying to optimise it thinking in terms of occlussion culling, as there are skyboxes in the air above my house that I don't really want to see.
The windows in my house are tint on touch, if I click them they go opaque, touch them again and I can see out, will this be taken into account by occlussion culling?

The preview release notes answers this:

If a face has any form of alpha (either non-100% alpha on the face, or alpha in the texture itself), then it will (of course) no longer cause occlusion. Any other behaviour is a bug.

I suspect that textures which were uploaded with alpha channels will also fail to cause occlusion even if that alpha channel is entirely opaque (since IIRC these are still put into the alpha pass, as verifiable by whether affected by invisiprims; fairly sure this is the case on the main client but I haven't checked with the preview client).

It's technically pretty straightforward to allow occlusion by the utterly-opaque parts of textures-with-alpha-channels, but it's hard to say whether the additional fillrate hit could be worth it.

All this does is extend the slicing model up to the whole sim. That is, right now, the first slice takes the sim and chops it up on a 4x4x"4" (because the sim isn't a cube, the last coordinate's more than 4) grid. Now, if you're standing on a platform at 300, the whole sim below 128 (and in fact most of the sim belowe 256) is going to be invisible to you. Why bother chopping it up smaller than 128 for the first pass?

BTW, in 1.9.1.10 occlusion culling actually started to make a big improvement even in relatively open places like the Lusk platform. In the first preview release it didn't seem to do much if anything for me. Wonder why?

Sorry if I repeat points that have been made, let me just give an overview of how the system works:

The occlusion culling works off an octree space partition, which is cubes inside cubes, as mentioned earlier. The maximum box size is actually infinite (to the limits of 32 bit floating point), but the maximum box size of a leaf box (that is, a box that actually contains objects instead of more boxes) is 256x256x256. The minimum leaf size is 8x8x8.

What determines the level of subdivision (smaller boxes being a higher level of subdivision) is the object density. A box will subdivide itself as soon as the number of objects in it exceeds 128. The binning up of objects has absolutely nothing to do with the camera, it's just that more objects tend to be loaded near the camera.

The actual occlusion calculation uses an OpenGL extension called GL_ARB_occlusion_query, which allows a programmer to query the number of samples that passed the depth and stencil tests for a given set of drawing calls. So, if no samples passed when drawing an octree node (bin box), it can't be seen, so don't draw anything inside that box.

Checking every box every frame is very expensive, so the occlusion culling algorithm will only check a few boxes every frame to see if they're occluded, and remember boxes that were occluded last frame to check the next frame. It will also ignore boxes that are mostly off the screen or that have less than 64 objects in them, or are too close to the camera. That way, an occlusion query is only performed if the cost of doing the query is less expensive than actually drawing the contents of the box. Also, occlusion queries pad the boxes by 5 meters to avoid situations where a box might be occluded by objects within itself.

The hierarchy of the octree comes into play by allowing the discovery that a box is occluded to indicate that all the boxes within it are also occluded. In this way, the maximum area possible can be culled in a single query. Since the maximum box size is infinite, theoretically the entire grid could be knocked out by checking a single box.

The efficiency of the algorithm is difficult to observe visually, since its affects largely remain unseen. Indeed, the only change in actual experience should just be an increase in framerate. Also, the existing object management system tends to unload objects inside buildings when you are outside simply because objects inside tend to be small and far away when you are outside. This greatly reduces the object density within those buildings, making occlusion queries there counter-productive.

The goal of the system is to detect cases where queries would increase framerate and avoid doing queries in places where they would only hurt. To test this, toggle occlusion queries on and off while keeping your camera still and see if your framerate goes up or down. If you find a situation where turning occlusion queries on makes your framerate go down, pease report it as a bug and include a screenshot.

Thanks much.

Thanks for the details!

That's cute, but... if an object extends outside of an octree node then shouldn't it be in the parent of that node instead? Otherwise... it sounds like you're inserting objects based on their origins rather than bounding box/sphere/whatever, then adding some slop to make up for possibly homing the object too deep in the hierarchy. How about, at worst, making a blanket 10x10x10 guess for a bounding box if you really don't have access to a more accurate guess and then add the object to the right node in the first place so no padding (and commensurate fill rate inflation) is needed? Perhaps your octree implementation only adds objects to tree leafs?

Sorry for teaching granny to suck eggs etc etc - trying to get a handle on this octree-alike, and I've implemented similar hierarchies for lighting, collision and culling in the past.

That's right, objects are tracked by their origin only and are only stored in the leaf nodes. Since Second Life doesn't allow a single object to be larger than 10x10x10, the slop used in occlusion and frustum culling makes up for it. General purpose implementations don't allow for the object size limit assumption. Leveraging that assumption turns out to be a huge win. Storing a tight bounding box per leaf that wraps its contents would probably be better. It's on my todo list.

Doing a staggered octree would make storing objects in the parent node work without the risk of "trickling up" too far, but our implementation is not staggered, so trickling up has a significant chance of landing a huge number of objects in the root node, which is very very bad and does not scale. Since objects are occluded with their node and parent nodes are always larger than leaf nodes (and therefore less likely to be occluded), I'm not convinced that using a staggered tree is a good idea when hardware occlusion queries are in play.

Feel free to prove me wrong.

Thanks for getting technical, it helps my understanding of how and why the thing works. I was curious, is the 128 object limit changable? There are some instances (like the very large tower mentioned in other posts, or the ones I can readily remember off the top of my head being in Nexus Prime) where there are a lot of objects in a very large space, but perhaps too few to trigger the subdivision within a given area (very wide areas with very large and complex machinery for instance).

Also I was wondering if this subdivision thing was the reason why I would always notice an 8m^3 box set around my avatar. I'm pretty sure I've got about 130 prims total on my avatar in various locations. If that's the case, I can see why the subdivisions aren't moving with the camera as I had suggested it should be in another post. Actually my thoughts in that post were that subdividing the cube which the camera is in would make rendering the scenery around the camera more efficient because you remove the stuff "close" to the camera but possibly on the other side of a wall near said camera.

Having a tight fit bounding box per octree node would do a better job of fixing those situations than any additional subdivision of the tree itself, I think. I'll try both just to be sure.

I noticed the bounding boxes earlier when I turned on octree rendering, fast work on that. >
Here's hoping a combination of both techniques will help with rendering spacious objects too.

Oh, one other thing. I posted in Land Management about clouds that are intersecting my build, but I'm wondering, would occlussion culling get rid of those? Would be handy for such occassions, or if you want to build a skybox directly in the clouds without them coming inside?

Occlusion culling doesn't affect what you can or can't see in the slightest - if it does then it's a bug. The inside-outside clouds sorta thing is a different issue.

Ah k.

[edit]Although actually, iirc this occludes a particle emmitter if it isn't visible, even if it's particles would be? Aren't clouds a type of particle emmitter? I suppose it would depend on where the source is in relation to my home though.[/edit]

I just managed to get in the preview now though, occlussion culling rules! I can get upwards of 25fps in mostly closed off areas! It's awesome, this hopefully means my home (with windows tinted to opaque) will now be smooth as silk instead of giving me the same 5 to 8 fps as before!