Imposters

We can achieve a lot of performance gains by using texture atlases and instancing, but it won't be enough for dense environments like forests and jungles. For these, we need imposters!

What are imposters?

Imposters are an extreme form of LOD (level of detail) optimization, replacing entire models with simple, flat pictures of themselves. They are much like the flat facades used in old Hollywood films, or the cardboard character cutouts used to promote books and movies. Here is an Overgrowth scene that has 3D trees interspersed with imposter trees: first you can see flat checkerboard imposters, then cutout checkerboard imposters, and finally the actual colored and shaded imposters.

So now it should be clear what imposters are, in general, which brings us to the next question:

Why use imposters?

We use imposters because they are much, much faster. A high-detail tree could require a thousand triangles, and an imposter is just two (because there are two triangles in a square). Similarly, a tree might draw each pixel multiple times because of its layers of leaves, but an imposter only draws each pixel once. Here's a framerate comparison between a scene with trees, and the same scene with some of the trees replaced:

It looks almost exactly the same, but it draws more than twice as fast!

How do imposters work?

To draw imposters, we need two main components: a surface to draw the imposter image on, and we need the imposter images themselves. Let's start with the surface:

In Overgrowth, the imposter surface geometry is sent to the graphics card as simple triangles around the origin, along with extra information about their transformation matrices and the position of the camera. The vertex shader then transforms the imposter and rotates it to face the camera, using techniques like those discussed in my linear algebra posts. Here is a picture showing how they rotate to face the camera:

This has to be done in the vertex shader because the camera position can change every frame, and it would be quite costly to update the imposter orientation on the CPU every frame, and to send the new coordinates to the GPU. If we do it on the vertex shader, then the imposter vertices can live on the GPU in vertex buffer objects, which are very fast.

Now that we have our imposter surfaces to draw on, we need the imposter images themselves. To match the shading of the 3D object, we will need to draw them in the same way that the object is drawn, combining a color map, normal map, and shadow map. To match the orientation of the 3D object, we will also need several different angles of the object. For now, I chose to use eight different angles, inspired by the old 2.5d shooters like Marathon and Doom. Here is a picture of the eight different angles and three different textures:

From top to bottom: color map, normal map, and shadow map

To create them, I draw the eight different angles using shaders to make sure the results in are in the right format (converting tangent-space normals to object-space for example). The results are stored in textures using framebuffer objects, so the pixel information never has to leave the graphics card. These images are all drawn at double resolution and then scaled down, which is a quality-improvement technique known as supersampling.

While all instances of a given tree can share the same color and normal map, each instance has a unique shadow map. For this reason, shadow maps are drawn much smaller, and combined into a texture atlas (which I discussed in an earlier post). Here is an example of an atlas with shadows for all the angles of 32 different imposters:

Now, to draw the imposters, we can just bind the images, and draw the imposters using the same equations used to draw the 3D trees. There is just one more step: we have to be able to transition smoothly between different angles, and between the imposters and the 3D models. For now I am doing this transition using stippling (swapping out individual pixels). This is the same technique that is used in most AAA games for LOD transitions, including Crysis and Killzone 2.

This doesn't look perfect, but it's very fast, and it accomplishes my main goal: spread the transition out over time so there isn't a sudden eye-catching jump. It would take a lot of original research (months, probably) to make the transitions look good while looking at them, but this will at least help keep them from attracting attention! Here is a close up of an imposter fading from one angle to another:

And here is how it looks when the imposter transitions to the 3D model:

Here is how these transitions look in action:

Further work

There is still a lot more work to do to make the imposters look better and run more efficiently, but I am going to save it for later; I don't think the imposters are the bottleneck right now in terms of performance or appearance. However, here are some of my ideas for improvement:

• Cut out unused space in the texture and use rectangular imposters instead of squares
• Double-check color matching -- make sure there are no gamma issues
• Add some vertical angles for view from above or below

These took nearly two weeks to implement, which is longer than I expected. However, I think it will be worth it to have more varied environments; without them we would only be able to have sparsely populated scenes like sand dunes or snowy plains. I will need to make other improvements to the editor to make it practical to actually create and manipulate dense scenes, but this is a good step!

Do you have any thoughts about the impostors, or questions about how they work?