Here's a hard problem that's been addressed only a few times that I know of. I'm looking for known, or new, approaches.

So, that's a scene from Second Life, with high quality settings. Which brings the frame rate down to about 4 FPS! How to improve on that?

Second Life server side is proprietary, but the viewers are open source. So anyone can work on the viewers, and many people do. I'm looking at how to add impostors to the viewer.

In the picture above, far more detail is being rendered than can actually be seen. There are no pre-generated impostors for content. There are only levels of detail. The lower levels of detail tend to be terrible, and often have holes, because the mesh reducer is both not very good and pushed too hard. We're stuck with that content; it's user-created over 15 years. We have to do what we can with what we've got.

The general idea is to generate impostors dynamically in the viewer and cache them for re-use. Maybe put the cache on a server and share it between viewers. The hard part is, what to impostor together to avoid overlap problems? Some constraints.

• Every building in that scene can be entered, and has detailed objects inside.
• Most objects don't move, but, potentially, any object can move.
• There's not much of an object hierarchy. Some root objects have “child objects", but there's only one level of children. A moving object is usually one root object, but a building might be 50 objects.
• Child objects can move relative to the parent object. This is used mostly for doors.

In the picture above, we'd like to impostor everything further than the second ship and the second building on the left. Maybe even start impostoring at the second ship and the second building, if we can get away with it.

The first problem is overlap. When billboard impostors overlap, the illusion breaks down because the depth sort is wrong. (Yes, you can kind of do something about that by having Z info in the billboard, along with a shader to interpret it, but that's a tough retrofit for the existing SL viewer.) There are some easy cases - if the bounding box of B is entirely contained in the bounding box of A, render them into one impostor. If the bounding boxes of A and B are completely disjoint and not enclosed by some other object, render them separately. That's the easy part. What to do about partial overlap of the bounding boxes? Any theory on this?

Nagle said:
What to do about partial overlap of the bounding boxes?

Project them to screen space, use poly clipping to calculate area of union, merge if union area * 2 > smaller box area?
Would be the logical generalization of your idea.

Same could be done for the distance spans the boxes have from camera, and their difference in velocity (which i guess has to be zero in practice).

Nagle said:
(Yes, you can kind of do something about that by having Z info in the billboard, along with a shader to interpret it, but that's a tough retrofit for the existing SL viewer.)

Maybe that's necessary. E.g. if you group two boats but there is some dock / bridge between them that did not made it into the group.
Not sure if such cases could be avoided robustly by disallowing grouping on overlap of any object that is not accepted. I assume this could result in only accepting tiny amounts of groups, making the grouping idea pointless. Seems the hardest problem here…

(blah blah… just typing something because i wonder my comment was not shown on forum site, so there might be no notification either.)

I've been looking at https://developer.nvidia.com/gpugems/gpugems3/part-iv-image-effects/chapter-21-true-impostors​

There are kinds of displacement mapping that can help with impostor occlusion. But they don't scale up to billboard impostors of building size. This needs a picture to explain. Think of a row of buildings along a street. Each has a billboard impostor, centered at the center of the building. You won't get a flat wall of storefronts from that, viewed obliquely as in the photo above. The plane of the impostor is in the wrong place.

Automatic box impostors? What do you do if something sticks out? If you use the bounding box, and make an impostor for each face, the corners won't match up.

What makes this hard is that it has to do something reasonable for totally uncontrolled content.

There are lots of systems for generating impostors. Unity has a nice one. But the demo is kind of a trick. The fly-through part of the demo has the distant stuff so dim, so blurred, and so obscured by trees you can't see the impostors. Not going to be able to walk a city street that way.

JoeJ said:
Project them to screen space, use poly clipping to calculate area of union, merge if union area * 2 > smaller box area?

The trouble with working in screen space is that you have to redo the impostor generation as the viewpoint changes. No performance win over rendering the 3D models.

The trouble with working in screen space is that you have to redo the impostor generation as the viewpoint changes.

Not really, pairs that passed the test in precious frame very likely pass it also for the next, so only new objects coming into view form new groups or add to existing ones mostly.
To avoid SS you could clip the bounding boxes and use 3D volume instead projected area, but that's more expensive, difficult and less accurate.

However, i assumed you aim for one 2D billboard plane per group of objects, which adds per frame work in any case, both for grouping and rendering new billboards.
Metro Exodus did this, afaik, but i don't think they make groupings and do it per object, which is simpler and maybe faster.

turanszkij said:
You said rendering is 4FPS, but you didn't say whether the bottleneck is CPU or GPU. Impostors will help with GPU - more specifically if there is geometry bottleneck - are you sure this is the problem you have?

The viewer performance problem in Second Life is almost always running out of CPU time in the main thread. Even modest GPUs can keep up easily. Every object has its own transform, and objects with multiple parts have more than one. Plus, objects have multiple textures, and there's a lot of texture switching. A standard cube uses 6 different textures. The amount of stuff drawn per draw call is much lower than in most games.

The goal with impostors is to 1) reduce the number of draw calls, and 2) reduce the amount of data that has to be fetched from the servers.

Good point, though. It's not really about impostors. It's about grouping. To the viewer, anything can move, and anything can change texture or color. But in practice, most things don't move. So this is more of a caching and cache invalidation problem.

The real win with impostoring is taking something like a house full of furniture and other objects and doing it in one draw call. Complicating the issue is that Second Life creators love windows. Big windows so people going by can see all the stuff in your store is normal. Just like real life. Maybe all we need to do is impostor all the little stuff that's totally contained in a building, and somehow get the outside to be drawn as one draw call.