Culling

This information was provided to the SLDev mailing list by Dave Parks, Jake Simpson, and Douglas Soo of Linden Lab. This information should not be construed as official Linden Lab policy, and is rather documentation derived from informal discussions.

Related Bugs/Improvements

http://jira.secondlife.com/browse/SVC-1926

Overview

The client sends camera frustum information to the server, and the server sends the client information about objects that are "interesting" based on that information. Internally, we refer to this logic as the "interest list," and it's unfortunately implemented entirely server side. The gist of our streaming is "stream objects, ask for textures." Since the network load of a prim is much less than a texture, occlusion culling saves bandwidth by never requesting texture data for occluded objects. Unfortunately, since the interest list is based solely on size vs. distance for sending prims, occluders are often not sent first, so every texture is visible for at least one frame. It's usually OK, because the requested amount of a texture to download atrophies quickly when the texture is not being rendered, lowering its priority as soon as it is occluded. There may be optimization opportunities in the texture download prioritizing code.

Priority

Textures are prioritized based on how many pixels they cover on the screen, and the priority is "boosted" based on different flags defined in this enum (from llviewerimage.h):

  enum
  {
      BOOST_NONE              = 0,
      BOOST_AVATAR_BAKED      = 1,
      BOOST_AVATAR            = 2,
      BOOST_CLOUDS            = 3,
      BOOST_SCULPTED          = 4,
      BOOST_HIGH              = 10,
      BOOST_TERRAIN           = 11, // has to be high priority for minimap / low detail
      BOOST_SELECTED          = 12,
      BOOST_HUD               = 13,
      BOOST_AVATAR_BAKED_SELF = 14,
      BOOST_UI                = 15,
      BOOST_PREVIEW           = 16,
      BOOST_MAP               = 17,
      BOOST_MAP_LAYER         = 18,
      BOOST_AVATAR_SELF       = 19, // needed for baking avatar
      BOOST_MAX_LEVEL
  };

So, sculpt textures are prioritized before avatar skins, clouds, and all "normal" textures. If you alt-zoom or left click on something, its texture becomes high priority. Right clicking on it (selection) gives it a higher priority than the terrain. You get the idea.

Looking at the code, it looks like the sculpt textures might have a 5 second delay between the texture being available and it actually being applied to the prim, since mSculptChanged is the flag used to determine when a sculpt gets rebuilt, and it only gets set in LLVOVolume::updateTextures, which only gets called every 5 seconds or on LOD switches or on vertex buffer rebuilds, whichever comes first. Room for improvement there.

As far as front-to-back rendering goes to reduce overdraw, work has been done to this end in windlight, but has more to do with changing the order of specific types of geometry rather than reordering prims. In windlight, terrain is rendered after prims, sky is rendered last, etc. Occlusion culling was also rewritten in windlight to use fewer triangles and fewer "guess" queries, getting rid of the "guess" queue and making sure that if something is not visible, it's never rendered.

The client occlusion culling is ignorant of things like prim types since it happens at the OpenGL level working on meshes using GL_ARB_occlusion_query.

Performance

The biggest issue with occlusion culling performance is that very few builds have any significant occluders due to overuse of transparencies and walls that leak (have cracks between prims). I'd encourage any builders to take a good look at how professional level designers layout environments in video games. In "World of Warcraft," for example, there are no windows, and you can never see the complex items inside a building from the outside. In "Call of Duty 4," there are plenty of windows, but you can never see into a window on one side of the building and out the window on the other side, effectively making every building an occluder. Compare this to Second Life, where every building has floor to ceiling windows and no inside walls. Some simple tricks to keep your windows and not kill performance are to make your windows opaque from the outside. This is the perception people have of windows in real life, so doing this will often make a build look "cleaner" or less cluttered.

Some builds that play really well with occlusion culling are the cyberpunk city in Suffugium and the giant cube maze in Q. Let me know if you know of others.

The other major limiting factor for performance in SL is the small batch size. On average, SL draws about 70 triangles per drawing call. In theory, increasing that number to 200 triangles per drawing call could improve rendering performance by 200%. The primary reason the draw size is so small is because we have to break batches to switch textures and to sort transparent objects to be rendered in depth order. This is why people in the graphics world are making such a fuss over "megatexturing" and similar techniques. These techniques combine all visible textures into a single large texture so all your geometry can be rendered with a single draw call. These techniques require artist intervention from the get go, however, so most are not applicable to SL. The technique that is applicable is good ol' fashioned texture atlasing, which is merely combining several textures into a single texture and modifying object texture coordinates to reference the part of that larger texture that contains the texture the object was originally referencing. Since textures in SL are streaming, though, generating atlases for your builds will result in ugly artifacts as textures load, so the correct solution is probably something between megatexturing and atlasing, where atlases are generated on-the-fly by the viewer and tailored to align texture borders within the atlas along mip borders according to the amount of the texture that's been downloaded so far.

We've (somewhat intentionally) done a very poor job at Linden Lab of educating builders on how to be performance conscious, which I think plays a large part in the overall sluggishness of the viewer. This is part of a philosophy that says it should be possible to build a content authoring system where artists don't need to care about performance implications, as the software should just deal with whatever comes its way appropriately. What we've seen, however, is that people (even technically minded people) consume as many resources as are available to them until performance reaches a level they deem is unacceptable, so the more efficient your renderer becomes, the more ludicrous the demands become. In SL, this usually means the performance becomes that of the lowest common denominator in terms of what is acceptable. That is, if you think performance is important and build a nice house with opaque window exteriors and few textures, you'll still have a bad experience if your neighbor thinks a flexi-prim bamboo forest is the bees knees.

The free market is winning out here (Otherland sims and similar, managed estates do better than private estates with no building standards), but it's slow going, and an initiative to document the best ways to build beautifully and efficiently is probably in order.

Subscribe and Unsubscribe

The ObjectKill message is a message that is sent when your agent on the simulator has decided to unsubscribe to an object on the simulator. The primary reason why it needs to be sent is that once your agent on the simulator isn't paying attention to objects, it won't send further updates to the viewer, which will cause lots of interesting artifacts in the case of objects that change when you aren't subscribed. In particular, moving objects can cause quite a headache (ghosting, etc.) - so the correct behavior is to cull the object from the viewer completely.

The logic that decides to subscribe and unsubscribe to objects is done based on groupings of objects based on type, size, and location in the region. Right now subscription and unsubscription is done based on a circular keyhole layout, with a bit of hysteresis to reduce subscription thrashing. If you turn down your bandwidth and teleport to a new region (or clear your caches), you should see this effect pretty well.

Moving the camera shouldn't generally cause objects to be unsubscribed - camera position and direction is used for determining which objects to subscribe to first, but for the purposes of unsubscription, I believe that only your avatar position is used.

As you move around in a simulator, the sim is constantly sending ObjectUpdate* packets (to subscribe) for objects that become within range or have moved, and it sends ObjectKill packets (to unsubscribe) for things that go outside of your vision. Then when you move back to that area it sends the ObjectUpdate* packets for those objects again. You may wonder why culling is done across the network by sending ObjectKill packets for things that are not actually leaving the simulator.

Suppose the sim didn't do that. In that case, the viewer would never know when the sim decided the object is too far away. So you'd need to have the viewer perform its own culling, or you'd have extra objects hanging around.

If the culling on the viewer and sim didn't match, you'd end up with updates being sent for objects the viewer won't show, or the viewer showing objects for which the sim isn't sending updates.

And since the sim determines which objects are near enough to notify you about their existence, it's only logical that it'd do the kill notification as well. Less error prone, and avoids duplicating code. Sim needs to know which objects are far enough anyway, as it has to decide when to stop sending updates.

In terms of why objects are subscribed and unsubscribed in the first place, there's also the factor of network bandwidth to consider alongside the issue of CPU usage on the Sim. If you don't remove those objects from the stream that are not considered within the clients perview (and not just frustum perview as most FPS games have it - you need to be able to consider objects behind you to ensure you get sounds, particles that overlap your view and so on) then it doesn't take long before your stream is *full* of objects you can't see, don't care about and yet are getting updates for you don't need.

Moving some of this to the client is a definite possibility - however there are implications to that. It enables people to ask the sim for information about objects they can't see in an attempt to cheat at games, and generally see stuff they don't have the permissions to see, plus timing suddenly becomes that much more important.

Realistically the Sim has to be the final arbiter of what it sends for several reasons - network bandwidth (you may have extra bandwidth to receive more data, but the sim doesn't necessarily have the bandwidth to be sending it out, given it's sending out these streams of updates to gobs of clients, not just yours), clients seeing what they need to see and no more, and the sim owning what you can see.

Possible future improvements

Note - this isn't necessarily how SL works right now, just an ideal of what it might be nice to get to.

The subscribe / unsubscribe code in SL needs some attention. What's there works, but not in the most optimal fashion.

Right now unsubscribe / subscribe is UDP and will probably need to remain that way since UDP is asynchronous and TCP is not - if object updates are coming via UDP (and they need to, trust me on this. Go dig out the TCP version of Doom and see what that does :) ) then the "Client, you need to know about this object" needs to be UDP to be sure it gets there first - at least attempting to, since UDP isn't guaranteed delivery.

Generally there are approaches that will work for this kind of thing - if the client receives an update for an object it doesn't know about yet, it can just ignore that update, unless it's enough to actually construct a complete object on the client side in which case it should do that. Generally though you don't get enough in an update packet since it's mostly deltas from an known state, not a complete state for an object, so construction is less likely an option.

There are mechanisms we can put into place whereby the sim sends a 'subscribe' notice to the client, indicating a new object of interest has entered the list of objects for this particular client, and can do that via UDP. And it will continue to do that, sending down a complete state until such time as the client acks this and says "Yes, I know there's a new object here, thanks" which it can do simply by acking the packet it received with that new objects information with in it. Then the sim 'knows' the client has that object and it can start sending just updates instead. You do the same thing for unsubscribing - the sim continues to send updates for a given object, as well as a "you are done with this object" message, until the client acknowledges it got it, in which case the object is just removed on the sim side and not considered again until it comes back into view.

There are some other things we can do as well in terms of the object update packets - Object Update packets should be mostly just deltas from a known state that the sim and client agree on - e.g. the initial state that the sim sent down to the client, which the client acked. The sim now knows what the client has and will only send down information that has deviated from that state. If, every now and then, when you get a smaller packet constructed for sending down, you can insert a new 'complete state' for an object to pad it out, which once acked brings the client and sim states up to one that hopefully should have less deviation between them because it's 'newer'.

Further to this there are other things to be tried, like not sending positional updates at all, but only sending velocity changes. If you send down a known state the client and sim have agreed on, then you don't need to send positional updates any more because the client and sim _should_ be in sync - all you need to do is send down velocity changes and the client and sim should remain in sync. Of course if packets are dropped, even though the velocity change is still being sent (and will be until the client acks it and the server says "Right, we are in sync right now") then this breaks some stuff since the client got the velocity change later than the sim started it, which means the dead reckoning position of the object is now wrong, but that's alleviated by the peridoric complete states being sent down. You can also send times on these packets and have the client re-interpret what the position should be given that the velocity change occured at time X (although this starts to involve some somewhat hairy code on the client side to make things match up). Simpler indeed, to just including a position when sending down a velocity change. You'd be surprised how effective that actually is - if you get to the point where so many packets are dropped that this become very apparent, then you are pretty much teetering on getting dumped anyway.

Most of the time good enough is surprisingly low in terms of real time correction and so on, because nothing particularly heavy is done client side that relies on this - it's all just visualization, rather than collision requirements and so on. The moment you start doing physics on a client, all this suddenly becomes far more important. But for now, it's less so.

Most of this is a known and solved problem; it's just time and resources that prevent us from looking at this immediately - that and the fact that while we see some artifacting now and again, it's not really something that destroys residents experience.