Dynamic 2D Imposters: A Simple, Efficient DirectX 9 Implementation

Introduction

The technique of using 2D imposters is becoming more and more popular in the world of computer games. The aim is, without loss of detail, to reduce the geometric complexity of a 3D scene by caching portions of the scene as images. 3D objects in the scene are captured into separate images. When the final scene is generated the cached images, or imposters as they are known, are rendered in place of the 3D objects. In this way an imposter is a simplified representation of a complex 3D object. As modern games grow larger and demand more detail than ever before developers are increasingly looking for new and innovative level-of-detail algorithms. The common place practice of using a progressively lower detail series of hand-authored meshes is not necessarily enough to meet the demands of modern games and more advanced solutions such as 2D imposters are required. As the topic of imposters is gaining acceptance and importance in the industry, numerous good articles and chapters have already been written, however I have not yet seen an article that covers the implementation of an imposter system. This article provides some basic theory, but is mostly concerned with, as the title suggests a simple and efficient system for dynamically generating and rendering 2D imposters.

Imposters can be used in many situations, however they are very well suited for complex and detailed games that have a large amount of distant static background geometry. In these games the users' attention is likely to be in the foreground and they will not notice the imposters in the background. Less time spent processing and rendering geometry leaves the game more time for the things that really make the game: logic and AI.

Imposter generation falls into two categories. Static or offline imposters are those that are generated offline, usually by an artist. Statically-generated imposters have been in use for many years and are more commonly known as sprites, particles or billboards. The classic example in this case is the often seen "billboard tree" constructed from billboards at right-angles. This tree is an example of an imposter that has four viewpoints. This article is about dynamically-generated imposters. They are similar in concept to static imposters and are still implemented as billboards; however they are regenerated at runtime by rendering an image of a 3D object to a texture.

This article is aimed at developers who want a starting point for creating their own imposter system. The code presented in the article is intended to be simple and adaptable to different environments and needs. Development of an imposter system is complicated by numerous issues. It is essentially an R&D task and requires experimentation to solve the mathematical, visual and performance aspects that come with the territory. To read this article I assume that you are experienced with the C/C++ programming language and have an understanding of 3D graphics concepts. You should at least be familiar with the DirectX 9 API and you might want to have the SDK help to hand.

Theory

A 2D imposter is a simplification of a complex 3D object, implemented as a billboard that is textured with a rendered image of the 3D object. The purpose of using imposters is to reduce the time required to render a 3D scene. It works by caching images of 3D objects and using these images in place of the real objects. Using imposters to decrease the amount of work performed each frame results in less time spent rendering. In DirectX this equates to a reduction in polygon and texture upload, draw calls, state changes, and more importantly, less CPU processing of geometry.

Generation of an imposter consists of the following steps:

Imposter billboard vertices are derived from the bounding box of the 3D object. The billboard is such that in screen-space, from the current viewpoint, it fully encompasses the 3D object. The billboard and the current camera position are used to compute the necessary view and projection matrices. The final stage in generating an imposter is to initialize render-state and render the 3D object into the texture. This texture is called the imposter texture throughout this article. The imposter texture must contain an alpha channel. The alpha represents where in the texture the imposter is: opaque (alpha = 1.0) where the imposter is; and transparent (alpha = 0.0) where the imposter is not.

Once the imposter is cached it is used for multiple frames of rendering. Imposters are rendered into the final 3D scene using alpha testing or alpha blending and are placed at the position of the 3D object they are replacing. The key to imposters bringing a performance gain is to reuse cached imposters over as many frames as possible. To this end imposters should only be regenerated when it becomes necessary to maintain the illusion of a cohesive 3D scene. There are certain conditions that will make the imposter illusion become apparent. There are global conditions such as camera viewing angle and light color and direction. There are local conditions such as animation, position, and orientation of the 3D object. When these conditions become so extreme that imposters become noticeably two-dimensional, they must be regenerated. The variation between the appearance of a 2D imposter and the 3D object it represents is what I call "imposter error."

Visual Quality Concerns

For imposters to be useful they need to not only be more efficient than rendering the 3D object, they also need to look as good, or (if a small sacrifice in quality is acceptable) almost as good as the real thing. With practice and experimentation most of the visual quality problems are solvable.

The biggest visual problems are:

The common DirectX alpha blending mode “source alpha-inverse source alpha” cannot be used in models that are going to be impostered. This is easily solved by using low-detail non-alpha versions of models when rendering them as imposters. Note that alpha-testing can be used with imposters to implement transparency. Pre-multiplied alpha can also be used as discussed in Game Programming Gems 2.

Visual popping is almost unnoticeable with good use of time-based alpha blending. You can even alpha-fade between imposter viewing angles so that imposter regeneration is barely noticeable, however that is not implemented in this article as it requires a larger render-texture budget. It should be noted that when alpha blending is used, imposters need to be depth-sorted and rendered back-to-front for the transparencies to work correctly. If alpha-fading is not required, it is possible to use alpha-testing instead which makes the depth sort unnecessary. There are many high-performance sort algorithms available.

Selecting the right texture resolution is important. A texture resolution that is too low will mean that imposters look pixelated. Additionally if the camera gets too close to an imposter or the imposter is too large then a low resolution texture becomes very obvious. For this article I have empirically selected the texture resolution of 64-by-64 for each imposter. The problem with hard coding a texture resolution is that it doesn't work very well with different sized objects or object distance. For example, larger and closer imposters will require a higher resolution than smaller and more distant imposters. For simplicity in this article, I will stick with the hard-code resolution; however the section Taking Imposters Further discusses extensions to the imposter system to efficiently handle run-time selection of different texture resolutions.

When imposter error becomes too extreme, imposters need to be regenerated before the problem becomes noticeable by the user. The conditions that cause imposter error will have more or less impact depending on the type of game, but typically they are based on camera viewing angle changes, object animation, movement and rotation, and lighting changes.

In this article the conditions are dealt with in the following ways:

Note that changes to object orientation are not tested for in the sample code. However, it is a simple condition to support. The test of the angle between camera vectors needs to be performed in model-space rather than world-space so that it will account for changes in object orientation.

It should be noted at this point that use of hardware fogging can help hide the visual problems associated with imposters. Fog is your friend, just remember that you only need to fog the imposter billboard and not the 3D object, otherwise you may end up with double fog!

Runtime Efficiency Concerns

Aren't imposters meant to make rendering more efficient? The answer is yes, however if an imposter system is implemented naïvely you may find that it doesn't quite solve your efficiency problems.

The naïve implementation is the simplistic approach of using one render texture for each imposter. This approach should only ever be used during prototyping (when solving visual issues) as it has a detrimental impact on performance. The naïve implementation requires a render target change for each imposter that is generated and requires a DirectX draw call for each imposter that is rendered. Changing render targets is an expensive operation. Executing a draw call for a small amount of geometry is also an expensive operation. To get the most out of imposters, multiple imposter textures need to be packed onto each render texture. The bigger the render texture and the smaller the imposter texture, the better, as we can fit more imposters in the same render texture. Packing texture in this way means that only one render target change is needed to generate multiple imposters and only a single draw call is required to render multiple imposters. Therefore, the more imposters that can be squeezed into a render texture, the more efficient the system becomes.

Regenerating imposters, although more efficient when using texture packing, is still the most expensive part of this system. Therefore we want to regenerate imposters as little as possible. It is important to tweak threshold values so that imposters are only regenerated when imposter error becomes obviously noticeable by the user.

As imposters are regularly regenerated, a dynamic DirectX vertex buffer is used to pack imposter vertices for draw calls. A dynamic vertex buffer is a vertex buffer that is created with flags that specify that DirectX should optimize the vertex buffer for usage where the vertex buffer is updated each frame.

Finally, it should be mentioned that the imposter render texture should never be locked. Locking a render texture can cause the graphics system to flush and stall which will really kill performance.

Step-by-step Implementation

The following section describes the code necessary for efficient imposter generation and rendering. The code listings that are included are from the sample application that comes with the article. The sample code has been compiled with the DirectX 9 October 2005 SDK and it makes heavy use of the DirectX Extensions library (D3DX).

The code listings are presented in a step-by-step fashion and introduced in order of the most important techniques in the imposter system. The first steps involve usage of the render textures. Then we look at the techniques for building imposter billboards and the matrices required for render to texture. Next, for the purposes of demonstration and example, the naïve inefficient imposter implementation is presented. Subsequently, the efficient approach using texture packing is discussed. Finally, there is a section that demonstrates how to determine when an imposter requires regeneration.

1. Render Texture Allocation

The first thing needed in an imposter system is a render texture. The code in Listing 1 creates the render texture using D3DXCreateTexture and D3DXCreateRenderToSurface. The DirectX code is encapsulated in the function RenderTexture::Init which is called to initialize the render texture. For runtime efficiency this function should only be called when the game starts up. Parameters to Init specify the resolution of the texture. The texture is created with the format D3DFMT_A8R8G8B8 which has 8-bits each for red, green, blue, and alpha channels. The alpha channel is required as it is the alpha mask that defines the area of the texture that contains the imposter. To create a render texture rather than a normal texture, D3DUSAGE_RENDERTARGET is specified as the Usage parameter. For the Pool parameter, D3DPOOL_DEFAULT is used and this places the texture in the memory pool that is most efficient for its use: video memory.

2. Render to Texture

Rendering to a texture is similar to rendering a normal scene. When rendering a DirectX scene, the rendering needs to be executed between calls to the IDirect3DDevice9 functions, BeginScene and EndScene. BeginScene is called first. Rendering is then performed using DirectX API functions. EndScene is called when rendering is complete. When rendering to texture, the ID3DXRenderToSurface functions BeginScene and EndScene are called instead of those in IDirect3DDevice9. In Listing 2, BeginScene and EndScene functions are added to the RenderTexture class to encapsulate the DirectX versions of these functions.

We have now covered the basics of render texture usage and created the RenderTexture class that simplifies the use of render textures. Listing 3 presents a simple example of using the RenderTexture class.

3. Generating Imposter Billboards

The first stage of imposter generation is to generate geometry for the imposter billboard. The billboard that is required is that which in screen-space fully covers the 3D object from the current viewpoint.

The billboard geometry is derived from the bounding box of the 3D object. First, the bounding box is projected into screen-space. Then, working in screen-space, a 2D bounding box is generated that encloses the points of the 3D bounding box. This 2D bounding box is the imposter billboard in screen-space. While determining the 2D bounding box, the depth values of each point are compared to determine the minimum depth value of all points. Finally the screen-space points and the minimum depth value are unprojected into world-space and are used as the positions of the imposter billboard.

Listing 4 presents the ImposterVertex and Imposter structures. These store the data required by a 2D imposter. ImposterVertex represents each vertex of the imposter billboard. Imposter vertices have position, color, and texture-coordinates. The color is used for alpha-fade transitions from 3D object to imposter. The Imposter structure represents an individual imposter billboard. In addition to other useful data, it contains the vertices that make up the billboard.

Listing 5 contains the CreateBillboard function that enscapsulates the code to compute an imposter billboard. D3DXVec3ProjectArray is called to perform the projection into screen-space. Subsequently D3DXVec3UnprojectArray is called to unproject from screen-space into world-space. Also computed are the center point of the billboard and the distances to the nearest and furthest points on the bounding box. This data is used in the next section for computing the matrices required for rendering to the texture. Calculated from the imposter center is the direction vector to the camera position. The imposter center and camera direction are used to help determine when an imposter requires regeneration.

4. Generation View and Projection Matrices

View and projection matrices are required in order to render to the texture. The matrices are computed for a particular imposter in CreateMatrices in Listing 6. The matrices are generated using the functions D3DXMatrixLookAtLH and D3DXMatrixPerspectiveLH. The view matrix is computed with the current camera position and the camera is reorientated to look directly at the center of the imposter billboard. The projection matrix is computed using the billboard as the projection plane and the near and far plane distances that were calculated in Listing 5.

5. Rendering a Mesh to the Imposter Texture

With an imposter billboard and the right matrices we can now take a look at how to render an imposter to a texture. This section presents the naïve approach to imposter generation. The approach presented here is sufficient for prototyping an imposter system, however it is inefficient as it changes render target for each imposter that is generated.

The code for rendering a mesh to the imposter texture is presented in Listing 7. BeginScene is called to begin rendering to render texture. The imposter is then rendered into the texture and EndScene is called. It is important to note that this is inefficient as it is changing render target for each imposter that is generated. When rendering the imposter to the texture, the billboard is first constructed by calling CreateImposterBillboard. Next CreateMatrices is called to compute view and projection matrices. These matrices are plugged into DirectX by calling SetTransform. Before rendering, the mesh render state is initialized and the background is cleared. It is important to note that fog is disabled as it is the imposter billboard that will be fogged and not the mesh that is rendered into the imposter texture. Also, alpha-blending is disabled as this is a feature cannot be used when rendering imposters (see Visual Quality Concerns).

In later sections, a more efficient implementation using texture packing is developed.

6. Rendering an Imposter Billboard

Continuing on with the naïve imposter implementation, Listing 8 presents code that renders a single billboard. SetTexture is called to bind the render texture and DrawPrimitiveUP is called to render the billboard.

Before calling DrawPrimitveUP render-state is initialized. It should be noted that fog is enabled here. The mesh that was rendered to the texture was not fogged, so fog needs to be enabled when the imposter is rendered. Note also the use of alpha-testing so that only the area of the render texture where the imposter exists (where alpha is equal to 1.0) will be blended into the scene. Alpha-blending is enabled here for the alpha-fade transitions that smoothly blend from 3D object to 2D imposter.

Again, this approach is very inefficient but is useful for demonstration and prototyping. It is inefficient not only due to the call to DrawPrimitiveUP, but because the biggest expense is that there is one draw call required for each imposter.

7. Using Texture Packing for Efficient Imposter Generation and Rendering

So far we have developed several useful functions for generation and rendering of 2D imposters. In the previous two sections, a simplistic and naïve technique for imposter generation and rendering was presented. Using a single render texture for each imposter is very expensive. When generating and rendering multiple imposters per frame, the performance costs quickly add up. This section presents an efficient implementation that packs multiple imposters into a single texture. Texture packing has the dual effect of reducing render target changes and reducing draw calls required to generate and render imposters.

The render texture is divided up into regions each of which is used as an imposter texture. When regenerating multiple imposters that are in the same texture only one render target change is required. When rendering imposter billboards we can copy all billboard vertices to a single dynamic DirectX vertex buffer. Imposter billboards that are contained in the same texture are all rendered with a single draw call.

The first step is to divide up the render texture and generate texture coordinates for each imposter. The texture coordinates map the imposter to the region of the render texture that it occupies. Listing 9 presents the AllocImposters function. Parameters to the function specify the number of imposters that are required in the U and V axis of the render texture. The imposter texture is divided up and texture coordinates are assigned to each imposter. Note that the Imposter objects are pre-allocated as a array. It makes sense to allocate in this way as computer games are typically limited in the amount of memory they can consume, so it is better to pre-allocate memory when possible.

The texture coordinates generated in Listing 9 are used both when generating and rendering imposters. When generating imposters, we need to call the IDirect3DDevice9 function SetViewport to set the renderable area of the render texture. The function InitImposterViewport in Listing 10 demonstrates how the texture coordinates are used to set the viewport. After calling SetViewport subsequent rendering will only be output to the specified region of the render texture.

With the ability to render to regions of the render texture, we are now able to pack multiple imposters into a single texture. To do this we take the GenerateImposter function presented in Listing 7 and modifiy it to handle multiple imposters. The modified version of the function presented in Listing 11 is now called GenerateImposters. The important thing to note is that there is only a single call to BeginScene after which a loop is executed that generates multiple imposters. Note that before rendering the 3D object to the texture InitImposterViewport is called to render to the correct region of the texture.

With multiple imposter packed into a single texture, we now look at a more efficient method of rendering imposter billboards. First, a dynamic DirectX vertex buffer is created. A dynamic vertex buffer is the right choice for imposter rendering. As we are going to be depth-sorting imposters, they are potentially rendered in a different order each frame. Therefore, we need to copy vertices to a dynamic vertex buffer each frame. It is worth noting that if you don't use depth-sorting, you could experiment with using a static vertex buffer that is only updated as imposters are periodically regenerated, however the caching code required is beyond the scope of this article. Example code for creating a dynamic vertex buffer is presented in Listing 12.

The RenderImposterBillboards function is presented in Listing 13. This functions renders all imposters that are packed in a texture. For alpha-blending to work, the imposters are first sorted so that they are rendered in back-to-front order. The vertices of the sorted billboards are then coped into the dynamic vertex buffer. Last, the render state is initialized and a single call to DrawPrimitive is executed to render the billboards.

8. Testing for Imposter Regeneration

Finally, we need to determine when imposters require regeneration. It is impractical to regenerate all imposters every frame. This would be more expensive than rendering the 3D objects in the first place. Cached imposters should be reused over as many frames as possible and not regenerated until imposter error becomes noticeable by the user. Listing 14 presents two tests that determine when an imposter requires regeneration. The first test checks the time since the imposter was last regenerated. If this time is greater than the threshold value, then the imposter needs regeneration. The second test examines the angle between the current camera vector and the camera vector that was computed when the imposter was last generated. If this angle is greater than the threshold angle, then the imposter needs regeneration. In either case, when the imposter is to be regenerated the requiresRegenerate member of the Imposter structure is set to true.

Taking Imposters Further

There are numerous ways in which the imposter system presented here can be improved.

Viewing Angle Tests

The sample code does not account for changes in orientation of the 3D object. To provide for this, the viewing angle test should be calculated in model-space rather than world-space. Then the test will take into account not only the camera viewing angle and model position, but also the orientation of the model. An even better test is to compare the angles between the vectors from the camera position to the near and far points on the object's bounding box. This test is more expensive but accounts for not only the camera viewing angle, but also the size, position, orientation, and distance of the object. This test is documented in Real-Time Rendering.

Calculating Texture Resolution at Runtime

For the sample code, I selected the imposter texture resolution offline and hard-coded it into the application. A more general purpose imposter system may want to calculate the texture resolution at runtime based on the size and distance of the 3D object and the resolution of the screen. Smaller and more distance objects will use a smaller texture resolution, larger and closer objects will use a larger texture resolution. Real-Time Rendering presents a useful formula for calculating texture resolution.

Supporting arbitrary imposter texture resolutions will help make imposters have better visual quality; however coding support for arbitrary texture resolutions is complicated and the code difficult to optimise. We don't want to make things harder for ourselves so I suggest a simpler approach. Select a number of discrete texture resolutions, for example 32x32, 64x64 and 128x128. Create a render texture for each discrete resolution. At runtime, compute the desired arbitrary resolution and then map this into one of the pre-defined discrete resolutions.

Load Balancing Imposter Regeneration

What happens when numerous imposters, or even worse all imposters, need to be regenerated in a single frame? The simple answer to this is to apply load balancing so that at most only X imposters are regenerated in a single frame. The value for X can be determined empirically or by some combination of machine specification and the amount of load being placed on it by the rest of the game. It is for this reason that, in the sample code, the code that tests for regeneration and the code that performs the regeneration are decoupled. By separating these phases, it is possible to test all imposters every frame to determine if they need regeneration, then, of those that require regeneration, only process X imposters.

Load balancing in this way introduces a problem. It is possible to have imposters that are marked as needing regeneration but are still waiting to be regenerated. At some point imposter error for the imposters that are awaiting regeneration may become too great and the illusion will break down. These errors can be quite obvious and may prevent users from becoming immersed in the scene. These effects are reduced somewhat by sorting imposters based on camera distance and the amount of time since their last regeneration. This allows the closest and oldest imposters to get first chance at regeneration. This does make the problem less noticeable; however there is still a chance that a user may be able see noticeable imposter error. For imposters where the error has become noticeable, the only option is to throw the imposter out completely and revert to the 3D object. This can be implemented as another viewing angle test. When the viewing angle becomes greater than the threshold the imposter alpha-fades back to the 3D object. The 3D object remains in place until the system catches up and has time to regenerate the imposter.

References and Further Reading

Real-Time Rendering: Real-Time Rendering, Tomas Moller and Eric Hanes

“Imposters: Adding Clutter”, in Game Programming Gems 2, Tom Forsyth

"Billboard Clouds for Extreme Model Simplification," Xavier Decorety, Gernot Schauflerz, François Silliony, and Julie Dorseyz

"Multi-layered impostors for accelerated rendering," Xavier Decorety, Gernot Schauflerz, François Silliony, and Julie Dorseyz

"Let There be Clouds! Fast, Realistic Cloud-Rendering in Microsoft Flight Simulator 2004: A Century of Flight", www.gamasutra.com, Niniane Wang

_____________________________________________________