Bounded Integer Sequence Encoding

luoyanghero

Initially, fractional bits per pixel sounds implausible, or evenimpossible, but it's not quite as strange as it initially sounds.

In principle we can choose our quantization of thetexel weights (and the color components of the endpoint colors) to use anynumber of values.

For the sake of illustration, let us assume that wecan best represent each texel in a particular block using one of five weightvalues - 0.0, 0.25, 0.5, 0.75 and 1.0. We can easily quantize these to theinteger values 0..4. Two bits is insufficient to represent these, as that wouldonly represent four values, so conventionally we would need to allocate 3 bits.We would then either expand the quantization to use all eight possible 3-bitvalues, or leave three of the values unused.

However, a combination of any three of these texelshas one of 53
possible values, or 125. This is very close to thenumber of values that it is possible to encode in 7 bits (27= 128). So if we can group the texels into triplets, and find anappropriate encoding scheme for these base-5 values ("quints"), wecan use just 7 bits, instead of the 9 we would need for storing three bits pervalue. This is a significant saving, and has the somewhat weird property ofassigning a non-integer number of bits - 2.33 - to each value.

Luoy 每个texel 3b，三个texels need 9b; now three texels as a group, have 5^3 possible values, or125, so only need 7b; 7b/3=2.33b/texel

Similar reasoning shows that it is possible to packbase-3 values (trits) in groups of five, each group taking 8 bits (35
= 243, 28= 256), for 1.6 bits per value.

Luoy 0.0, 0.5, 1.0; 8/5 = 1.6

The Bounded Integer Sequence Encoding (BISE)technique used in ASTC always quantizes values to ranges which conform to oneof three patterns: values from 0 up to 2n-1, using n bits; up to 3 x 2n-1, using n bits and a trit; or up to 5 x 2n-1 using n bits and a quint. This allows us to encode any idealquantization range with much less waste than the traditionalwhole-number-of-bits approach.

When the number of values is not a multiple ofthree or five, we need to avoid wastage at the end of the sequence. Thus, wehave another constraint on the chosen encoding. If the last few values in thesequence to encode are zero, the last few bits in the encoded bit string mustalso be zero. Ideally, the number of non-zero bits should be easily calculatedand not depend on the magnitudes of the previous encoded values.

This is a little tricky to arrange, but it ispossible. This means that we do not need to store any padding after the end ofthe bit sequence, as we can happily assume that they are zero bits, safe in theknowledge that they will not affect the decoding of the actual values.

With this constraint in place, and by interleaving the bits, trits andquints appropriately, BISE encodes a sequence of length
S
(i.e.an array of
S
integer values) using a fixed number of bits:

·
For S values in the range 0 up to 2n-1, it uses nS bits.

·
For S values in the range 0 up to 3 x 2n-1, it uses nS + ceiling(8S/5) bits.

·
For S values in the range 0 up to 5 x 2n-1, it uses nS + ceiling(7S/3) bits.

This is the key innovation that allows ASTC to efficiently trade spacebetween color endpoint values and texel weights.