Wavelets in 3D Graphics

Wavelets have become a hot topic in mathematics in general and computer graphics in particular. They are a useful tool for multiresolution analysis of a data set and for data compression. There are several popular wavelet basis and scaling functions. Herein I will focus on the Haar wavelet basis and its application to compression of low contrast textures in a 3d polygonal game engine that I am developing. In this application, I exploit both of these characteristics of the Haar basis. Terminology For the purposes of this article, a texture consists of a 32 bit image, 2n texels wide, 2n texels tall. A texel is an industry buzzword for a pixel of the texture before it is projected onto the screen. Mipmaps are also stored for each image. Each mipmap is a power of two smaller than the last and is generated by antialiasing from the previous image. So the mipmap set for a 128x128 texture would be 64x64, 32x32, 16x16,8x8,4x4,2x2 and 1x1. Typically, the lowest 3 or 4 mipmap levels are more hassle to maintain than they are worth and are often omitted since for a game one can often constrain the scene to keep polygons that are that far away from being visible. Also, if they are visible, you probably have bigger problems with the sheer number of small polygons you need to project and display than worrying about a little aliasing problem in the distance. Storing the mipmaps drives up texture storage requirements by 1/3rd. The Problem A typical texture size is 256x256. At 4 bytes per texel this single image consumes 256Kb of RAM per texture. A practical scene has approximately a dozen textures visible at a time, and up to a hundred distributed around the map in places where they are not immediately visible. To keep everything loaded at all times would require approximately 200Mb of memory just for the texture and mipmap data, let alone any game logic, lightmapping or geometry. Needless to say, at this time expecting that much memory from a typical end user's i computer is unreasonable. Possible Solutions One solution is to reduce the images to 8 bit palettized representations. This reduces memory requirements to about 50Mb, which can be reasonably swapped to and from disk if you can exploit coherence in the way textures are distributed around the map. However, if you cannot take advantage of any spatial coherence or caching then you will experience a stutter caused by the sudden hit of having to go look up the texture to continue rendering the display. This stutter has a very negative psychological effect; As a player, you are suddenly reminded that you are playing a game and the sense of immersion goes out the window. Frame rate consistency is more important over all than the best case performance, so a performance leveling factor is required. The stutter is aggravated by the fact that in order to swap textures the engine has to look to disk, which is several orders of magnitude slower than accessing the texture directly from memory. Also, a paletted representation of textures requires you to use a smaller subset of colorspace to store the image, you tend to lose a lot of quality in the conversion, and even reconstructed, if you are using a standard palette with six bit color components, the reconstructed texel is at best 18 bits upon reconstruction. Other complications arise when you want to store an alpha (translucency) channel in a paletted representation. Another option is to store a compressed representation of the texture in memory and to derive the mipmaps from that. The problem with this approach is that you are stuck decompressing the entire texture and then extracting all mipmap levels even if you only needed the 32x32 mipmap from a 256x256 texture. Typically, you will need the lower mipmaps before the larger mipmaps for a given texture. This is intuitive since as you walk through a scene, surfaces will come into view in the distance and get closer. As they approach, they will gradually need more detail (higher mipmap levels). With this approach you have to take the full hit all at once. This introduces stutter. JPEG style compression can be used to good effect, you can typically obtain a higher compression ratio than by using the approach I took below. Unfortunately, its all or nothing nature makes it ill suited to my needs. Also, the better compression comes at the cost of having to perform the inverse DCT on each 8x8 block of the image. This process takes 54 multiplications, 462 additions and 6 shifts per channel using Feig's method, which is presently the most efficient published method on Intel processors. In comparison the same 8x8 block decompresses with 256 additions per channel using Haar. An overview of the Haar Basis This is intended to supply an intuitive understanding of how the Haar basis works. What follows is not intended as a rigorous mathematical proof or examination of the subject. Given 2^n samples such as: { 11, 1, 1, 7 } Pair samples and average them giving: { (11+1)/2, (1+7)/2 } = { 6, 4 } Repeat until you have 1 value: { (6+4)/2 } = { 5 } Figure 1. Pairwise averages and the scaling value. This value at the top of this tree (Figure 1) is your scaling value. Now, you recurse down the hierarchy that you paired. At each level you subtract value in the right hand child of the current node from the value in the current node. Do not recurse into the leaf nodes on the tree. Figure 2. Wavelet coefficients by level. There are 2n values in a given level of the tree. These values are your wavelet coefficients. With these values you can reconstruct the original sample set since this operation is invertible. There are 2m coefficients at the mth level of the hierarchy. Adding the scaling value to this set, provides the sample number of values as the original data set, however when converted into Haar form, the numbers are now indicative of the changes from the smaller level. Reconstruction is straightforward. Start with the scaling value and the coefficient for level 0. Add the coefficient to the scaling value to generate the left hand child, subtract it from the scaling value to generate the right hand child. Take those nodes and repeat down the tree: =Figure 3. Reconstruction: add on the left, subtract on the right. Next you weight the coefficients by their level in the tree. This is don't to normalize the coefficients. There are several weighting mechanisms that are popular. Each of them is valid for a different uses. I prefer normalization by multiplying each value by 1/sqrt(2^j) where j is the coefficient's level in the tree. Your data now to consists of: The scaling value { 6 } The wavelet coefficients { 1, 5, -3} The weighted wavelet coefficients { 1, 5/sqrt(2), -3/sqrt(2) } So far, no compression has resulted from this process. The entire transformation merely converted four values into four other values and some weighted values which are derived from them. Applying Haar The next step is to figure out how to apply this to image compression. An image is a two dimensional grid of samples, not a one dimensional set as mentioned above. There are two common approaches: The standard decomposition of the image would perform the Haar transform on each row and then goes through column by column and transforms each in turn. This unfortunately is not very useful for reconstructing mipmaps, since in order to extract a 2x2 mipmap, I would need to reconstruct the entire image, and then anti-alias my way back down to 2x2. If I were to do this, there would be no advantage in reconstructing the lower mipmaps. The nonstandard decomposition transforms one level down each row, and then transforms one level down each column, and repeats until you are left with the scaling function. Thus intuitively, you can extract a 2x2 mipmap from the 1x1 mipmap (aka your scaling coefficient) and the set of coefficients for level 0 (one row coefficient and two column coefficients) and then extract the 4x4 mipmap from the 2x2 using the mipmap and the coefficients for level 1 ( 2 row coefficients, 4 column coefficients), etc. This allows you to reconstruct the image incrementally as you get closer to the surface in the game. Since you manage to avoid any sudden requirements of massive amounts of data, you can avoid stutter. If you are forced to wait on a higher mipmap in one frame of animation because you didn’t have the processing time to decompress it then you can use the lower mipmap level as a stand in for it until you can. In practice I have found it to be better to maintain a constant 25 frame per second refresh rate rather than dip at times down to 5 because I didn’t have a texture ready. I chose to work with the nonstandard decomposition of my texture. This is all well and good, but again so far all we have managed to do is swap one set of numbers for another. No compression has occurred, unless you count the fact that we do not have to store the extra memory for the mipmap levels since they can be derived as we reconstruct the image from the coefficient set. The next step is to compress the coefficient set. One advantage that wavelets have is that a small change to the coefficient set creates a similarly small change in the restored sample set, and it nicely distributes such error around the image, thus avoiding visible discontinuities as a result of this error.