Lightning Engine

We’ve recently started searching for ways to optimize our terrain renderer. Our current implementation uses material splatting with user specified weights per material, as well as decals for extra details (e.g. roads, foot steps, etc.). For distant terrain we use a base layer, in order to minimize the amount of work required to render the terrain. Here I’ll talk about our attempt on virtual textures, the difficulties we’ve encountered and how we are planning on integrating the technique into the engine.

Virtual textures, megatextures, clipmaps, etc.

Independently of the name you pick, the fundamental concept is the same: The ability to render a scene using textures larger than the limit (in dimensions or memory) imposed by the graphics API and/or the GPU used, by keeping in memory only the parts required to render each frame. The different names correspond to different algorithms based on this idea. Some are designed for terrain rendering only, others for arbitrary geometry. Here are some links on the subject (in no particular order):

1. SGI’s paper on clipmaps
2. The Clipmap: A Virtual Mipmap
3. Virtual Texture: A Large Area Raster Resource for the GPU
4. Hardware-Independent Clipmapping
5. Unified Texture Management for Arbitrary Meshes
6. Sparse Virtual Textures
7. nVidia’s white paper on clipmaps for DX10
8. Clipmapping on the GPU
9. Advanced virtual texture topics (Chapter 2 from here)

Our implementation is based on Sean Barrett’s GDC presentation and demo, with some modifications and additions. Other than Sean’s presentation video, you can read papers no. 5 and 9 for more informations on this particular algorithm. The major steps of the algorithm are:

1. Find which tiles are required for the current frame
2. Update the tile cache by uploading newly introduced tiles
3. Update the indirection table
4. Render the geometry with a special fragment shader using the tile cache instead of a regural texture

Step 1: Find required tiles
There are several different ways to find which tiles are required for each frame. For a comprehensive list of available options read paragraph 2.3.6 from paper 9. Our current implementation uses Barrett’s original idea of rendering the scene to a texture with a special shader (or a special texture) and reading back the result on CPU for further processing. Unfortunately, this approach doesn’t allow any prediction and suffers from temporal blurriness, as mentioned in Crytek’s paper. In our little demo, this isn’t actually a big problem, so we settled with this solution for now.
The only problem of this method is that the required readback may slow things down a lot, especially if exact levels of details are required (i.e. when rendering the special buffer at full screen resolution). In order to speed things up we used two different PBOs (GL_ARB_pixel_buffer_object) for the readback with one frame delay between rendering and actual processing. Rendering of this special buffer is performed at half the screen resolution, with an appropriate bias to the selected level of detail. This way we can get almost the same output in one forth of the required time.
After the buffer is processed, we have collected all the required tiles for rendering the scene. There might be a problem though which isn’t mentioned in the above pseudocode. The number of required tiles may be more than the number of tiles the cache can support. In order to prevent this from happening, after finding which tiles are required and marking them in a separate buffer, we also request all their parents.

Step 2: Update the tile cache
Starting from the mipmap at the lowest detail level, we request all visible tiles from that mipmap, one by one. When all tiles from a mipmap level have been considered, we move on to the next mipmap level. If the cache is full, we stop asking for higher detail tiles and we continue with the next step. This works because we already have their parents in the cache, and we can use them instead. Of course the quality won’t be optimal but we can continue rendering without worrying about invalid data.
Every time a tile is inserted in the cache texture, we inform the indirection table about its location in the cache and its mipmap level.
Tiles are requested asynchrounsly from a separate thread. This thread is responsible for “generating” the requested tile data and sending them back to the main thread. We say “generate” because the data can be either proceduraly generated or read from a file. When the main thread requests a tile which isn’t available in the cache (a second level cache in system RAM; not to be confused with the tile cache texture which resides in VRAM), the corresponding pixel in the indirection table is unmarked, and its parent is used.

Step 3: Update the indirection table
The next step is to update all tiles in the indirection table, not touched during step 2. During step 1, every tile which should be requested during step 2, has been marked. In this step we check all the tiles which haven’t been marked, and we assign them the same cache page as their parents. This procedure is peformed without using recursion, by looping through each mipmap level of the indirection table, assigning parent page information to each unmarked child.
When each tile in the indirection table have a corresponding cache page assigned, we must update the indirection texture. In contrast to what Crytek suggests in their paper, we used an RGBA8 indirection texture. The main reason for this, is to avoid the extra CPU time required for converting the indirection data to FP16 format, and the required bandwidth for uploading the data, especially when the indirection texture is big. As in Barrett’s demo, we use the floor() trick to convert a fixed point value in the [0, 1] range to an integer value in the shader. We haven’t seen any problems yet, so the extra gain in performance is worth it.

Step 4: Render the geometry
Finally, it’s time to use the virtual texture (indirection table + tile cache). The original texture coordinates are used to read the indirection texture. The indirection information are then used to calculate the correct coordinate in the tile cache texture. The real problem with this step is filtering of the tile cache texture. Currently we have only tried bilinear filtering. Bilinear filtering requires one texel border around each tile, but we already use a 4-pixel border for DXT compression, so other, more complicated, filters can be implemented in the shader. Bilinear filtering of the tile cache texture, with a mipmapped indirection table, gives the same output as a regular texture with bilinear filtering on the nearest mipmap level (MagFilter = LINEAR, MinFilter = LINEAR_MIPMAP_NEAREST).

Storing and editing virtual textures

Having described the major steps of the algorithm, the only real problem remaining is how to store and edit virtual textures. Ideally we want the worker thread to be as fast as possible, in order to minimize popping. On the other hand, we need to be able to edit virtual textures, because the ultimate goal is to integrate the algorithm into our terrain editor. There are two options here:
1) Bake a virtual texture with all of its mipmaps on disk and load it directly or
2) Keep the information about layers, weights and decals and bake the requested tiles on demand.

The first option may be faster for run-time use, but the space requirements increase rapidly with texture resolution. The second option requires more work from the worker thread, so there may be a longer delay between the request and the availability of a tile, but the space requirements are the same as the current algorithm. Since baking of tiles must happen in a second thread, render-to-texture isn’t a candidate, so the baking must be done on the CPU.

For our little demo, we decided to go with the prebaked approach. The maximum virtual texture resolution we’ve tried was 65536×65536, with a tile size of 256×256 (without borders). This texture, in uncompressed RGBA8 format, requires approximately 22GB of space (including mipmaps). In order to minimize the required space, JPEG compression was used for each tile individually. The final texture was about 4GB at a quality of 75 (1/6 of the original size), but since we are using JPEG, this has to do with the amount of detail the texture has. For JPEG we used jpeglib, so compression ratios may vary with other libraries.
Generating mipmaps for a 65536×65536 texture can be a little tricky, because usually mipmap generation algorithms require the mipmap level to be present in RAM for the generation of the next mipmap level. In order to overcome this problem we used the method described by Crytek in their paper, as out-of-core mipmap generation. Mipmap level 0 is stored as separate tiles on disk. When you want to generate a tile for mipmap level 1, all you need is the tiles around the same location from the previous mipmap level. We used a 2×2 box filter for mipmap generation, so only 4 tiles from the previous mipmaps are required to be in memory. Note here that mipmap tiles, in this case, can have a different size than the virtual texture tiles.

The main advantage of the second option is the ability to modify the virtual texture at run-time. Whenever something changes, we can just invalidate the corresponding tiles in the cache and let the worker thread regenerate the data. The main problem is the generation of mipmaps. Since we don’t store anything on disk, we have to bake all mipmap levels, in contrast with option 1 where the baking happens only for mipmap 0. We haven’t tried this yet, but as mentioned above the goal is to integrate the algorithm into our terrain renderer and editor, so interactive editing of textures is needed. Another advantage of this approach is that virtual texture size can be a function of available power and not available disk space. Depending on how fast we can bake tiles, we can adjust the size of the indirection table, effectively altering the size of the virtual texture. E.g. with a tile size of 256 pixels, we can get virtual textures with dimensions up to 1M x 1M (assuming the maximum texture size supported by the GPU is 4096).

Things to try

1. Use a second, regular, texture for all mipmap levels below a threshold. E.g. for a virtual texture larger than 4096×4096 we can store mipmap levels below 4096×4096 in a regular texture. This way we can remove the tiles which correspond to those mipmaps from the tile cache, making up more space for higher detail mipmaps. Potential problems include increase in the required texture memory for keeping this extra texture, and an increase in the number of required texture units. Handling of those mipmaps inside the shader should be easy and should require only a TEX and a lerp.
2. Currently the bottlenecks in our demo is step 1 (scanning the PBO data in order to collect required tiles) and step 3 (indirection texture updates). An alternative method for finding the tiles required at each frame is presented in paper 5 from above. This is definetely something we should look into.
3. Real-time DXT compression of tiles. We already have the required border around each tile, so we have to use it in order to save some texture memory.

There may be some things worth mentioning, that i’m forgetting right now. The subject is big and it can’t fit in a single post. In order to keep it at a reasonable size, i’ll stop here. There will be probably at least one more post on the subject once we manage to test more things. Any questions/suggestions/comments are always welcome.

JD

Tags: rendering, virtual_textures

This entry was posted on Thursday, October 2nd, 2008 at 1:44 pm and is filed under rendering. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.