Fixed-point as compression

Any given fixed-point format can be considered a method of compressing another, higher resolution fixed-point format.

This is part 4 of the onboarding floating point series. This series is intended to be used for onboarding of programmers new to the team to review a basic understanding of fixed-point and floating-point number formats, or for programmers who would like to remove some of the mystery from formats they may use everyday.

We introduced 1:16:15 fixed-point in fixed-point as fractions. Consider the following table of values. Assume they represent distances in meters, as in previous examples.

table_4_1.txt

Lossless compression

Assuming these values are representative of some group (e.g. vertices of models, instance positions, etc), what can we see from the data?

There are a set of bits that are always zero. Values are within +/-32 meter range and 1/4096 meter resolution.

-:00000000000-----:------------000

Mark those bits with ‘x’ for “don’t care”

-:xxxxxxxxxxx-----:------------xxx

Mark bits that are used with letters for reference.

S:xxxxxxxxxxxAAAAA:BBCCDDEEFFGGxxx

Remove the bits we don’t care about.

S:xxxxxxxxxxxxAAAA:BBCCDDEEFFGGxxx -> s:AAAA:BBCCDDEEFFGG

uint32_t compress( uint32_t d )
{
  return ((d&0x80000000)>>11)|((d&0xffff8)>>3);
}

Without losing any information, we can store these same values in 1:5:12 fixed-point format. However, that requires 18 bits of storage, so we might want to consider how we can reduce it to fit into 16 bits.

Lossy compression

1:5:12 fixed-point storage of distance has a resolution of 1/4096 meter, which is approximately 1/4 of a millimeter. In many common cases like game object model vertices or world positions, that resolution is imperceptible. We can often use 1/1024 meter resolution (or less!) without any difference perceivable by anyone other than the original artist. For any game that works with average human scale interactions, a millimeter is pretty small. Alternatively, if you’re making a game about brain surgery, nanometer resolution might be appropriate but anything more than a +/- 1 meter range is probably unnecessary.

If we don’t care about anything more than 1/1024 meter resolution, we can mark two additional bits ‘x’ as don’t care in the source 1:16:15 fixed-point data. By reasoning about what resolution we need, we can store the same values in a 1:5:10 format, which fits neatly into 16 bits.

S:xxxxxxxxxxxAAAAA:BBCCDDEEFFxxxxx -> s:AAAAA:BBCCDDEEFF

uint32_t compress( uint32_t d )
{
  return ((d&0x80000000)>>16)|((d&0xfffd0)>>5);
}

table_4_2.txt

Note that you can’t say whether or not compression is lossless or lossy without knowing concretely what data is being compressed.

Take-away

Consider fixed-point a form of compression. Select the appropriate size and format by considering the range and resolution necessary given the specific input data and how it’s used.

Next: Part 5

Floating-point as compression - A floating-point format can be considered a (generally lossy) approach to compressing a high-resolution fixed-point format.