How does hardware texture compression work?

Question

That it compresses the data compared to the pixel array is obvious.

But what makes it different from from normal compression (like png, jpeg)?

Answer 1

As Simon's comment alluded to, one major difference between hardware texture compression and other commonly used image compression is that the former does not use entropy coding. Entropy coding is the use of shorter bit-strings to represent commonly-occurring or repeating patterns in the source data—as seen in container formats like ZIP, many common image formats such as GIF, JPEG, and PNG, and also in many common audio and video formats.

Entropy coding is good at compressing all sorts of data, but it intrinsically produces a variable compression ratio. Some areas of the image may have little detail (or the detail is predicted well by the coding model you're using) and require very few bits, but other areas may have complex detail that requires more bits to encode. This makes it difficult to implement random access, as there is no straightforward way to calculate where in the compressed data you can find the pixel at given (x, y) coordinates. Also, most entropy coding schemes are stateful, so it's not possible to simply start decoding at an arbitrary place in the stream; you have to start from the beginning to build up the correct state. However, random access is necessary for texture sampling, since a shader may sample from any location in a texture at any time.

So, rather than entropy coding, hardware compression uses fixed-ratio, block-based schemes. For example, in DXT / BCn compression, the texture is sliced up into 4×4 pixel blocks, each of which is encoded in either 64 or 128 bits (depending on which format is picked); in ASTC, different formats use block sizes from 4×4 up to 12×12, and all blocks are encoded in 128 bits. The details of how the bits represent the image data vary between formats (and may even vary from one block to the next within the same image), but because the ratio is fixed, it's easy for hardware to calculate where in memory to find the block containing a given (x, y) pixel, and each block is self-contained, so it can be decoded independently of any other blocks.

Another consideration in hardware texture compression is that the decoding should be efficiently implementable in hardware. This means that heavy math operations and complex dataflow are strongly disfavored. The BCn formats, for instance, can be decoded by doing a handful of 8-bit integer math operations per block to populate a small lookup table, then just looking up the appropriate table entry per pixel. This requires very little area on-chip, which is important because you probably want to decode several blocks in parallel, and thus need several copies of the decode hardware.

In contrast, DCT-based formats like JPEG require a nontrivial amount of math per pixel, not to mention a complex dataflow that swaps and broadcasts various intermediate values across pixels within a block. (Look at this article for some of the gory details of DCT decoding.) This would be a lot grosser for hardware implementation, which I'm guessing is why AFAICT, no GPU hardware has ever implemented DCT-based or wavelet-based texture compression.

Answer 2

"How (hardware) texture compression works" is a large topic. Hopefully I can provide some insights without duplicating the content of Nathan's answer.

Requirements

Texture compression typically differs from 'standard' image compression techniques e.g. JPEG/PNG in four main ways, as outlined in Beers et al's Rendering from Compressed Textures:

1. Decoding Speed: You don't want texture compression to be slower (at least not noticeably so) than using uncompressed textures. It should also be relatively simple to decompress since that can help achieve fast decompression without excessive hardware and power costs.

2. Random Access: You can't easily predict which texels will be required during a given render. If some subset, M, of the accessed texels come from, say, the middle of the image, it's essential that you don't have to decode all of the 'previous' lines of the texture in order to determine M; with JPEG and PNG this is necessary as pixel decoding depends on the previously decoded data.
   Note, having said this, just because you have "random" access, doesn't mean you should try to sample completely arbitrarily

3. Compression Rate and Visual Quality: Beers et al argue (convincingly) that losing some quality in the compressed result in order to improve compression rate is a worthwhile trade-off. In 3D rendering, the data is probably going to be manipulated (e.g. filtered & shaded etc) and so some loss of quality may well be masked.

4. Asymmetric encoding/decoding: Though perhaps slightly more contentious, they argue that it is acceptable to have the encoding process much slower than the decoding. Given that the decoding needs to be at HW fill rates, this is generally acceptable. (I will admit that compression of PVRTC, ETC2 and some others at maximum quality could be faster)

Early History & Techniques

It may surprise some to learn that texture compression has been around for over four decades. Flight simulators from the 70s and 80s needed access to relatively large amounts of texture data and given that 1MB of RAM in 1980 was > $6000, reducing the texture footprint was essential. As another example, in the mid 70s, even a small amount of high speed memory and logic, e.g. enough for a modest 512x512 RGB frame buffer) could set you back the price of small house.

Though, AFAIK, not explicitly referred to as texture compression, in the literature and patents you can find references to techniques including:
a. simple forms of mathematical/procedural texture synthesis,
b. use of a single channel texture (e.g. 4bpp) that is then multiplied by a per-texture RGB value,
c. YUV, and
d. palettes (the literature suggesting use of Heckbert's approach to do the compression)

Modelling Image Data

As noted above, texture compression is nearly always lossy and thus the problem becomes one of trying to represent the important data in a compact way whilst disposing of the less significant information. The various schemes that will be described below all have an implicit 'parameterised' model that approximates the typical behaviour of texture data and of the eye's response.

Further, since texture compression tends to use fixed-rate encoding, the compression process usually includes a search step to find the set of parameters which, when fed in to the model, will generate a good approximation of the original texture. That search step, however, can be time consuming.
(With the possible exception of tools such as optipng, this is another area where typical use of PNG & JPEG differ from texture compression schemes)

Before progressing further, to help with further understanding of TC it's worth taking a look at Principal Component Analysis (PCA) - a very useful mathematical tool for data compression.

Example texture

To compare the various methods, we'll use the following image:

Note that this is a fairly tough image, especially for palette and VQTC methods as it spans much of the RGB colour cube and only 15% of the texels use repeated colours.

PC and (post mid 90s) Console Texture compression

To reduce data costs, some PC games and early games consoles also made use of palette images, which is a form of Vector Quantisation (VQ). Palette-based approaches make the assumption that a given image only uses relatively small portions of the RGB(A) colour cube. A problem with palette textures is that the compression rates for the achieved quality is generally rather modest. The example texture compressed to "4bpp" (using GIMP) produced

Note again that this is a relatively tough image for VQ schemes.

VQ with larger vectors (e.g. 2bpp ARGB)

Inspired by Beers et al, the Dreamcast console used VQ to encode 2x2 or even 2x4 pixel blocks with single bytes. While the "vectors" in the palette textures are 3 or 4 dimensional, the 2x2 pixel blocks can be considered to be 16 dimensional. The compression scheme assumes there is sufficient, approximate repetition of these vectors.

Even though VQ can achieve satisfactory quality with ~2bpp, the problem with these schemes is that it requires dependent memory reads: An initial read from the index map to determine the code for the pixel is followed by a second to actually fetch the pixel data associated with that code. Additional caches can help alleviate some of the incurred latency, but adds complexity to the hardware.

The example image compressed with the 2bpp Dreamcast scheme is . The index map is:

Compression of VQ data can be done in various ways however, IIRC, the above was done using PCA to derive and then partition the 16D vectors along the principal vector into 2 sets such that two representative vectors minimised the mean squared error. The process then recursed until 256 candidate vectors were produced. A global k-means/Lloyd's algorithm approach was then applied to improve the representatives.

Colour Space Transformations

Colour space transformations also make use of PCA noting that the global distribution of colour is often spread along a major axis with far less spread along the other axes. For YUV representations, the assumptions are that a) the major axis is often in the luma direction and that b) the eye is more sensitive to changes in this direction.

The 3dfx Voodoo system provided "YAB", an 8bpp, "Narrow Channel" compression system that split each 8 bit texel into a 422 format, and applied a user selected colour transform to that data to map it into RGB. The main axis thus had 16 levels and the smaller axes, 4 each.

The S3 Virge chip had a slightly simpler, 4bpp, scheme that allowed the user to specify, for the entire texture, two end colours, which should lie on the principal axis, along with a 4bpp monochrome texture. The per-pixel value then blended the end colours with appropriate weights to produce the RGB result.

BTC-based schemes

Rewinding some number of years, Delp and Mitchell designed a simple (monochrome) image compression scheme called Block Truncation Coding, (BTC). This paper also included a compression algorithm but, for our purposes, we are mainly interested in the resulting compressed data and of the decompression process.

In this scheme, images are broken into, typically, 4x4 pixel blocks, which can be compressed independently with, in effect, a localised VQ algorithm. Each block is represented by two "values", a and b, and a 4x4 set of index bits, which identify which of the two values to use for each pixel.

S3TC: 4bpp RGB (+1bit alpha)
Although several colour-variants of BTC for image compression were proposed, of interest to us is Iourcha et al's S3TC, some of which appears to be a rediscovery of the somewhat forgotten work of Hoffert et al that was used in Apple's Quicktime.

The original S3TC, without the DirectX variants, compresses blocks of either RGB or RGB+1bit Alpha to 4bpp. Each 4x4 block in the texture is replaced by two end colours, A and B, from which up to two other colours are derived by fixed-weight, linear blends. Further, each texel in the block has a 2-bit index that determines how to select one of these four colours.

For example the following is a 4x4 pixel section of the test image compressed with the AMD/ATI Compressenator tool. (Technically it's taken from a 512x512 version of the test image but forgive my lack of time to update the examples).

This illustrates the compression process: The average and the principal axis of the colours are calculated. A best fit is then performed to find two end points that 'lie on' the axis which, along with the two derived 1:2 and 2:1 blends (or in some cases a 50:50 blend) of those end points, that minimises the error. Each original pixel is then mapped to one of those colours to produce the result.

If, as in this case, the colours are reasonable approximated by the principal axis, the error will be relatively low. However if, like in the neighbouring 4x4 block shown below, the colours are more diverse, the error will be higher.

The example image, compressed with the AMD Compressonator produces:

Since the colours are determined independently per-block, there can be discontinuities at block boundaries but, as long as the resolution is kept sufficiently high, these block artefacts may go unnoticed:

ETC1: 4bpp RGB
Ericsson Texture Compression also works with 4x4 blocks of texels but makes the assumption that, much like YUV, the principal axis of a local set of texels is often very strongly correlated with "luma". The set of texels can then be represented by just an average colour and a highly quantised, scalar 'length' of the projection of the texels onto that assumed axis.

Since this reduces the data storage costs relative to say, S3TC, it allows ETC to introduce a partitioning scheme, whereby the 4x4 block is subdivided into a pair of horizontal 4x2 or vertical 2x4 sub-blocks. These each have their own average colour. The example image produces:

The area around the beak also illustrates the horizontal and vertical partitioning of the 4x4 blocks.

Global+Local

There are some texture compression systems that are a cross between global and local schemes, such as that of the distributed palettes of Ivanov and Kuzmin or the method of PVRTC.

PVRTC: 4 & 2 bpp RGBA
PVRTC assumes that an (in practice, bilinearly) upscaled image is a good approximation to the full-resolution target and that the difference between the approximation and the target, i.e. the delta image, is locally monochromatic, i.e. has a dominant principal axis. Further, it assumes the local principal axis can be interpolated across the image.

(to do: Add images showing breakdown)

The example texture, compressed with PVRTC1 4bpp produces:

with the area around the beak:

Compared to BTC-schemes, the block artefacts typically are eliminated but there can sometimes be "overshoot" if there are strong discontinuities in the source image, for example around the silhouette of the lorikeet's head.

The 2bpp variant has, naturally, higher error than the 4bpp (note loss of precision around the blue, high frequency areas near the neck) but arguably still of reasonably quality:

A note on decompression costs

Although the compression algorithms for the schemes described above have a moderate to high evaluation cost, the decompression algorithms, especially for hardware implementations, are relatively inexpensive. ETC1, for example, requires little more than a few MUXes and low-precision adders; S3TC effectively slightly more addition units to perform the blending; and PVRTC, slightly more again. In theory, these simple TC schemes could allow a GPU architecture to avoid decompression until just prior to the filtering stage, thus maximising the effectiveness of internal caches.

Other Schemes

Other common TC modes that should be mentioned are:

• ETC2 - is a (4bpp) superset of ETC1 that improves the handling of regions with colour distributions that don't align well with 'luma'. There are also a 4bpp variant that supports 1 bit alpha, and an 8bpp format for RGBA.

• ATC - Is effectively a small variation on S3TC.

• FXT1 (3dfx) was a more ambitious variant of the S3TC theme.

• BC6 & BC7 : An 8bpp, block-based system supporting ARGB. Apart from HDR modes, these use a more complex partitioning system than that of ETC to attempt to better model image colour distribution.

• PVRTC2 : 2&4bpp ARGB. This introduces additional modes including one to overcome limitations with strong boundaries in the images.

• ASTC : This is also a block based system but is somewhat more complicated in that it has a large number of possible block sizes targeting a wide range of bpp. It also includes features such as up to 4 partition regions with a pseudo-random partition generator, and variable resolution for the index data and/or colour precision and colour models.