GameDev.netCompressed Quantized Unit Vectors

Compressed Quantized Unit Vectors
3D vectors can be used to express a position, a direction in 3 space. For some purposes you want 3D vectors that have an arbitrary length, for example when you need to express a position or a velocity. For some purposes you want only unit length vectors, that is a vector with a length of 1. Unit vectors are used for example to express a direction. When they are expressing the direction that some surface is facing they are called normals. The typical representation of a 3D vector is with 3 floating point numbers. If you use 32 bit floats this makes each vector 12 bytes. A 12 byte vector provides a huge amount of precision and versatility. It can point in any direction with very high accuracy and it can express vectors with a huge range of lengths also with very high accuracy. For unit length vectors you don't usually need this kind of high precision and you can save lots of memory using quantized normals. This page descibes my method for mapping 12 byte vectors into 2 byte quantized normals and back. The transformation in each direction can be achieved in constant time with just a few table lookups. First though have a look at what you lose in accuracy. In these two images I have a sphere represented with about 40000 triangles. In the first picture the normals used to light the sphere are quantized 2 byte normals. In the second picture I am using complete 12 byte normals. ( click on the image to enlarge it ) Notice how the second picture is perfect sphericity itself. But the first picture is not too bad. There are two subtle creases along the equator where my quantization method is weakest, and the surface has a very slight wobble to it, unlike the second picture. Now remember that these pictures represent the worst case for using normals to calculate lighting. The sphere is lit obliquely and the surface is a nice smooth continuous curve. In the typical case of a 3d model, or a terrain, this quatization error is absolutely invisible. Go to my terrain rendering page to see what I mean. All of those scenes use quantized normals. I have included the code at the bottom. Here is a quick explanation of how it works. If you know that your vector is unit length then you know that:
Therefore you know that if you have 2 numbers you can compute the magnitude of the third number, but not its sign. So you need to store off the sign of each element. Given that I am going to pack this whole thing into 16 bits, I use 3 bits for the sign of each vector component leaving me 13 bits to represent the magnitude of two of the components. You also know that the magnitude of any component ranges from 0 to 1 so it makes quantization practical. It would be simple to just code one value into 6 bits and another value into the remaining 7 bits and just use those two numbers to look up the third value in a table. However it is possible to express both numbers using seven bits each but using a total of only 13 bits for both. This is because when you select two components of a unit vector, not every pair of numbers less than 1 is possible. For example if X == 1.0 then Y and Z must both be 0. As X becomes smaller more values become possible for Y and Z. If you make your quantization table a 2d table indexed on the square of X and the square of Y, then the cells of the table that can be filled with valid values for Z form a triangle. You can see that we are using only half of the space. Which is great because I am short one bit! So say that I will represent X with 7 bits, and Y with 6 bits and look up Z in my table. To get a 7th bit of resolution for Y I just check to see if my quantized Y would be bigger than the dynamic range of 6 bits. In that case I subtract both numbers from 127. Now the X still fits in the X slot and the Y is guaranteed to fit in the Y slot and the pair of numbers will index into a part of the table that is still not coded with values for Z. There are better ways to quantize unit vectors. I have seen one really good way in a recent SIGGRAPH paper. It takes advantage of the stuff I describe here but also takes advantage of the symetry within a single quadrant to get even more accuracy within 16 bits. The problem is that mapping from 12 byte vectors to 2 byte vectors involves doing some trancendentals. I believe going the other way from 2 to 12 is just as fast as my method. So you might want to look for that paper. I'll put a reference to it here when I find it. Here is the code that implements my quantization method. The c3dVector object is just of structure with 3 floats in it. Your typical 12 byte vector.
© 1999-2011 Gamedev.net. All rights reserved. |