Nature of the Beast: Occlusion Culling Discussion

They should. Clouds are special particles, they don't seem to be emitted from anywhere. You can turn off clouds, or you can place invisiprims around your house (or wear one on your HUD that obscures your window), but that would remove all clouds inside and out. And in the case of invisiprims it'd make your avatar disappear too.

Oh, going back to one of the things I was thinking about with occlussion culling; does it affect the order in which textures are downloaded?
After moving to a much more 'packed' sim (or rather a sim with lots of stuff around it) I've been noticing that my home seems to download last out of everything around me. ie I can see through my house (it isn't even grey squared yet) and see all the buildings outside loading first, even though I'm inside my house.

Is this feature being used to change the order in which textures are loaded to visible first? Because my house is now tweaked to hopefully take full advantage of culling (my tinted windows now go opaque rather than just darker), to make it much more responsive for having people over. But it'd still suck a bit if it takes forever to load because SL is downloading everything else first.

I did some testing with the invisiprim box idea in the presense of a Linden (name withheld, he'll reveal himself if need be) and noticed a few oddities in the OC system while looking out of the box:

1. Distant points (I guess beyond 160m, though it could be further) are culled, with the ground and prims removed
   
2. Nearby single prims, even as far as 90 meters or so, would not cull dispite us being fully enclosed in a box
   
3. Octree cubes containing large numbers of prims nearer than those single prims WOULD be culled, ground included
   
4. 
   

If you head out to the East edge of Brilliant with the Octree view turned on, you'll notice a floating, invisible cube with a wooden cube inside of it. Sitting on that inner cube will get you inside. If you look South you'll see a building which has a great deal of complex prims hidden within it. From within the invisible box though the closest wall and all those complex prims are culled, as well as a chunk of the ground. Looking West, outside of the box, you'll notice a gas station kind of thing. Looking from inside the box, much of said station is culled.

My observations lead me to believe that the OC system isn't actually culling everything you can't see, but is in actuality culling only dense regions that you can't see. That's a good rendering increase, sure, but not what we were expecting when we were told "what you can't see isn't being rendered."

Also, while I could excuse it for lack of attachment complexity or possibly me standing slightly outside of the octree cube, when I swung my camera outside and resized the invisi-box so that it slightly encompassed the culling cube, my attachments (and that lone wooden cube mentioned earlier) still showed through and the culling cube inside the box was not being culled. If I can't see me, I shouldn't render, and likewise with the lone wooden cube.


The accompanying Linden confirmed these observations himself and said he'd talk to the OC devs about it, and happily bought a copy of my box for testing. I hope the system gets to the point of total culling of what you can't see soon.

Right with one exception. The assumption people are making when they complain about "inefficiency" in the occlusion culling is that inaccuracy (not culling everything that is occluded) equals inefficiency. This is not true.

If you're thinking is thus:

1) A = object is occluded
2) B = don't draw object
3) C = draw object
4) A implies B and not A implies C results in maximum efficiency (highest framerate)

Then you're assuming that determining A is less expensive than performing C. This is far from true. In many cases (the vast majority of cases, actually), determining whether or not an object is occluded is more expensive than actually drawing the object. Indeed, the system detects cases where determining A is slower than performing C and does not perform occlusion culling for those cases.

I actually placed an invisi-prim cube in the Morris test area here, has a phantom top and four sides, invisible on the inside faces.

My obersations were:
- flexi-prims take ages to cull, I'm sure that one must definitely be a bug
- close objects don't cull, though I suspect that's just because they are in the same cubic area as the box
- Some areas of land disappear while other areas, the same distance away don't seem to disappear at all.

It's worth a look, just hop inside and look out across the morris test area, not only will you get a really good fps, but you can see it all going on. It's just that the land one seems like a possible bug, as you can see some chunks being culled, but others that should be culled remain in place (though a number of their objects do disappear).

It is looking good though, if you turn and look at the adjoining sims you get better results from the culling and great fps.

Best done in mouselook mind, as the 3rd person camera can bleed out of the box.

My thought is that inside a box that blocks LoS to everything outside, all OC cubes not at least partially visible should be culled. Surely it's efficient to scan whether or not the cubes around you are visible, not just whether the contents of those cubes are visible. I say this because when I stand 30m from the corner of a sim that has no adjoining sims and look out into the abyss, I do not see it staring back. I see my frame rate jump to 30 fps.

From the view port it should be easy enough to do a quick ray cast test for the four closest corners of the culling cube. Should you intersect with any object at all four points, and the intervening object is not hollow parallel to the viewer, and not transparent on the facing towards the viewer, cull the cube. If the object is hollowed though, scanning within the hollow area would be required to ensure that another object doesn't fill that void (hollowed walls for bay windows, the windows themselves being opaque glass with painted window dressings so they block LoS). The OC system doesn't need to be instant speed either. We're all use to teleport rez lag, so having portions take a second or two to repopulate wouldn't be a terrible shock.

Another thing I discovered during my experimentation is that culled areas would sometimes flicker back into existance for a moment. Particularily when moving, but occasionally while stationary and not moving my camera. I'm not sure how the OC system works at the moment, but it seems to me that every pass an area is calculated to be visible or not visible and the previous state is not remembered. I think it would be best to store that information from a previous pass so you know which areas were culled and have them be "missed" on the next run or two to determine whether they're culled or not. Reducing the amount of scanning you have to do will speed up the whole process.

Close objects will get culled if the camera is closer to the prim, with the camera RIGHT next to the prim culling most, if not all, objects (red block gets larger the closer the camera is to a prim). Just seems like this needs to be tweaked to cull more when the camera is FURTHER away from a prim.

Every time you move your camera? o_O!?

No, if the OC system had a flag to decide wheter to render and not render regions, and assumed the region was in that state on its next pass, you could skip two passes (possibly a second or two) without rendering the "not render" areas before scanning them again to figure out that yes indeed they ARE suppose to be rendered. As a sort of code snippet:

for (int x = 0; x < ocCubes; x++) {  // Go through all the OCtree cubes
   if (!render[x] || getUnixTime() - render[x] > 2000) {  // If render[x] (our flag) is == 0, or its difference from now is larger than 2000 (2 seconds)
      if (isVisible(x)) {  // Check to see if it's visible
         render[x] = 0;  // We can see it, so ensure it gets scanned next pass
         drawRegion(x);  // Do the rendering call for that cube
      } else {
         render[x] = getUnixTime();  // We can't see this region, so set its flag to now so it won't be checked again for 2 seconds
      }
   }
}

So I stand next to a 20 x 0.01 x 32m wall, right near its center, in a 32m rendering zone. I can see 16 x 32 x 32m clearly on my side, but only a portion of the other side is visible. The areas I cannot see because of the wall get their rendering flag set to "not render" for 2 seconds (could be extended when you aren't moving your camera around, and reduced for when you are), and that portion of the cube would not draw and be skipped for 2 seconds worth of future scanning.

However for the above example to succeed, the isVisible() function needs to intelligently figure out whether a certain area should be split into smaller cubes. Partially occluded cubes could be cut down into smaller blocks. In the above example, if no intelligent splitting occurs, you'll still be able to partly see the 16m^3 culling boxes on the other side of the wall because they peek around either side of the wall (it's not completely blocking off the other side). If the isVisible() check decides that part of the wall is occluded (say, 1/2 of the corner vectors are NOT visible), it would then reduce the rendering blocks to a smaller size. So instead of four 16m^3 cubes we can partly see, we get thirty two (32) 8m^3 blocks which we either can mostly see or completely not see, and thus won't render. And since at least half of those cubes are not visible, we're simply "passing them over" when it comes to the OC scanning. It's like they don't exist. This should mean that no significant system load is added, and the benefit is that you can then TOTALLY omit those none-visible cubes from rendering, ground included.

I'd be happy to demonstrate my thoughts in game visually if anyone requests it.


Addendum:
The result of the "not render" flag would mean that if you were moving, a portion of the landscape that was previously hidden might not render immediately (two seconds at most). This is no different from teleport rez lag when everything is getting set up, except this time you've already got all the textures and prim information locally so it should just pop into place rather than slowly coming back over several seconds. And as I mentioned, moving could set the rescan delay lower (to 1 second) and you'd probably never notice things disappear and reappear unless you were going at abnormal flight speeds.

In retrospect though, abnormal flight speeds (across the sim in 3 seconds or so) would make the isVisible()'s adjustment I suggested above go nuts on your computer, so perhaps it should be limited to only doing that optimization if the camera is moving at running speeds or slower.

Hmm, it's an interesting idea, but I'm not sure I particularly see the usefulness. I suspect that areas that aren't rendered remain un-checked unless you move your camera, or an object affecting it (ie the wall you are standing near) changes in some way, such as a texture change, or the shape changed or something. I suspect the client is already able to detect when an object is updated (judging by the "Show updates" option in Debug, though I haven't used it much), so if a prim marked as affecting occlussion has updated, then it can re-scan.

That way if you are idle you don't lose performance once the initial scan is done, and if you are moving you don't get 'occlussion lag'.

Which means that you could have up to 2 seconds lag before you could see stuff as you moved your camera around... even if you were looking at it 5 seconds ago! It's bad enough having textures reloading when you turn 180 degrees, but watching stuff pop in and out as I spun my camera around a focus would drive me crazy. You're thinking about the movement of the avatar, but the camera can move much much faster than the av... just flicking the mousewheel or alt-grabbing something in the distance and slewing your view around that can move the camera a hundred meters a second.

A better algorithm might be to simply deepen and broaden the culling tree over time ... more or less without limit ... as a background computation. You'd have the current coarse foreground cull, and if that changed or the camera moved (or moved 'enough') the detailed cull would be thrown away.

I thought about that actually. The 2 second delay could actually be variable. The more often a region is not rendered the longer the delay could become. But regardless, if the camera moves more than a certain distance in a second (like say, 10-20m, unassisted flight speed) the delay would be ignored and a render check would be forced. Likewise a tight bounding box (like is calculated for all prims at the moment, even dynamically generated around flexiprims) could be established around the enclosed space, and should the camera move outside of the box it would force a render check. This would prevent simply turning within an enclosed space triggering the render check override (unless you really go at it with your camera), but if you just stay inside it would gradually get better with fewer checks. And if you opened the door to your house and walked outside, the camera would pass the bounding box and force a render check.

Or perhaps ray cast to the edges of the bounding box whenever a prim moves within that box to see if it no longer occludes the outside... So many ideas.

If you're concerned with FPS when stationary (which you seem to be, as delays don't benefit a moving camera visually) then I still think that just using the updates notification system to trigger recalculations is the most sensible way. The updates also seem to tell the client what has actually changed, so it can look at an update and so "Oh, the script just added a listen, nothing important" or "Uh oh! Texture changed and now it has an alpha layer, better recalculate!".

As Argent says, the easiest way to improve moving performance is just to do 'coarse culling' using bigger boxes, then sub-divide these later if you stop moving.

You're converging on the "background culling" algorithm.

The cleanest algorithm might be to continuously grow the occlusion tree in the background, but cull the occlusion tree as the camera and "significant" prims (ones responsible for occlusion) move. This could be precise (eg, when you move the camera you only discard the occlusion tree behind significant prims that the camera moved away from or relative to) or coarse (if the camera or any significant prims move you start over) or something in between (trees behind significant prims within 32 meters may be kept, ones further away are always culled).

Well I'm rather certain that LL won't abandon the octree system now in favour of something more total and ultimately harder on your processing power. Individual ray-casting for instance, which would seem the most precise yet least processor friendly method. On the other hand, they could make that information perform double duty and figure out which prims a light source should stop at so it's no longer sunny inside a fully sealed cube with no windows. ^.^;
So my major concern is less with "how does the outside look" and more on "how does being inside improve your rendering?" Obviously if you can't see outside, it shouldn't render any of it regardless of detail. But the current system seems more passive than active in its efforts to cull the landscape. Smaller culling cubes are calculated based on prim complexity within the cube, which doesn't help with large builds that have complex shapes and large textures within a wide open area (those towers of lag for instance).

Passive is good, it doesn't cost as much in CPU cycles. Constantly recalculating the tree to finer and finer degrees (within reason) is certainly more aggressive, and I'd like it, but it might not be too friendly for people running the bare minimum for SL. By excluding certain zones from being drawn with my method, you can afford to get a little more aggressive because you have less scanning to do. Less scanning of useless zones means more room for scanning newer zones.

Perhaps a combination of our techniques. Scan all 8 corners and the center of the largest culling cube. If you can't see one of the corners and/or the center, split the cube and repeat the process in the offending areas. When you finally reach a point where all the corners, or all but one of the corners, is no longer visible you cull that cube and assign it a "do not scan" flag so it gets skipped in following cycles for a period of time. That would certainly solve my "is indoors significantly better than standing outdoors?" problem, and would in all likelihood help with culling things inside and behind large, complex structures when viewing it from outside. And as per my suggestion, if the camera moves too far too fast, cancel the flag's delay and recalculate. The most effiicent means of recalculating in that case would be to go up a node and rescan, rather than start over from the beginning.

For background culling I don't think that processing is a consideration really, after the initial 'coarse cull' it just uses spare cycles to refine it, if the processor is working over-time then it won't bother until the load eases off.
e.g if you're downloading a ton of textures and processing them then it might not be a good point to refine the culling tree into more precise areas, but if your processor is at 50% capacity then that's a spare 50% to use on pumping up the FPS by sub-dividing the sim into smaller and smaller cubes.

It might be an idea to have an "aggressiveness" rating for occlussion culling, so lower-end systems can have less aggressive culling, ie when doing the 'coarse' culls it uses bigger boxes than a more aggressive setting. But the end result is much the same, as the sub-division will go as small as it can unless you are moving or something happens?

Actually I think a contrary approach, culling first and downloading textures for visible prims second would be best. There's a potential for less immediate bandwidth usage, and it would be easier on either high or low end systems because there's less textures to draw right away.