S3 Texture Compression

Some (e.g. US 5956431 A) of the multiple USPTO patents on S3 Texture Compression expired on October 2, 2017.[6] At least one continuation patent, US6,775,417, however had a 165-day extension. This continuation patent expired on March 16, 2018.

There are five variations of the S3TC algorithm (named DXT1 through DXT5, referring to the FourCC code assigned by Microsoft to each format), each designed for specific types of image data. All convert a 4×4 block of pixels to a 64-bit or 128-bit quantity, resulting in compression ratios of 6:1 with 24-bit RGB input data or 4:1 with 32-bit RGBA input data. S3TC is a lossy compression algorithm, resulting in image quality degradation, an effect which is minimized by the ability to increase texture resolutions while maintaining the same memory requirements. Hand-drawn cartoon-like images do not compress well, nor do normal map data, both of which usually generate artifacts. ATI's 3Dc compression algorithm is a modification of DXT5 designed to overcome S3TC's shortcomings with regard to normal maps. id Software worked around the normalmap compression issues in Doom 3 by moving the red component into the alpha channel before compression and moving it back during rendering in the pixel shader.[7]

Like many modern image compression algorithms, S3TC only specifies the method used to decompress images, allowing implementers to design the compression algorithm to suit their specific needs, although the patent still covers compression algorithms. The nVidia GeForce 256 through to GeForce 4 cards also used 16-bit interpolation to render DXT1 textures, which resulted in banding when unpacking textures with color gradients. Again, this created an unfavorable impression of texture compression, not related to the fundamentals of the codec itself.

DXT1 (also known as Block Compression 1 or BC1) is the smallest variation of S3TC, storing 16 input pixels in 64 bits of output, consisting of two 16-bit RGB 5:6:5 color values ${\displaystyle c_{0}}$ and ${\displaystyle c_{1}}$, and a 4x4 two-bit lookup table.

If ${\displaystyle c_{0}>c_{1}}$(compare these colors by interpreting them as two 16-bit unsigned numbers), then two other colors are calculated, such that for each component, ${\displaystyle c_{2}={2 \over 3}c_{0}+{1 \over 3}c_{1}}$ and ${\displaystyle c_{3}={1 \over 3}c_{0}+{2 \over 3}c_{1}}$. This mode operates similarly to mode 0xC0 of the original Apple Video codec.[8]

Otherwise, if ${\displaystyle c_{0}\leq c_{1}}$, then ${\displaystyle c_{2}={1 \over 2}c_{0}+{1 \over 2}c_{1}}$ and ${\displaystyle c_{3}}$ is transparent black corresponding to a premultiplied alpha format.

The lookup table is then consulted to determine the color value for each pixel, with a value of 0 corresponding to ${\displaystyle c_{0}}$ and a value of 3 corresponding to ${\displaystyle c_{3}}$.

DXT2 and DXT3 (collectively also known as Block Compression 2 or BC2) converts 16 input pixels (corresponding to a 4x4 pixel block) into 128 bits of output, consisting of 64 bits of alpha channel data (4 bits for each pixel) followed by 64 bits of color data, encoded the same way as DXT1 (with the exception that the 4-color version of the DXT1 algorithm is always used instead of deciding which version to use based on the relative values of ${\displaystyle c_{0}}$ and ${\displaystyle c_{1}}$).

In DXT2, the color data is interpreted as being premultiplied by alpha, in DXT3 it is interpreted as not having been premultiplied by alpha. Typically DXT2/3 are well suited to images with sharp alpha transitions, between translucent and opaque areas.

DXT4 and DXT5 (collectively also known as Block Compression 3 or BC3) converts 16 input pixels into 128 bits of output, consisting of 64 bits of alpha channel data (two 8-bit alpha values and a 4x4 3-bit lookup table) followed by 64 bits of color data (encoded the same way as DXT1).

If ${\displaystyle \alpha _{0}>\alpha _{1}}$, then six other alpha values are calculated, such that ${\displaystyle \alpha _{2}={{6\alpha _{0}+1\alpha _{1}} \over 7}}$, ${\displaystyle \alpha _{3}={{5\alpha _{0}+2\alpha _{1}} \over 7}}$, ${\displaystyle \alpha _{4}={{4\alpha _{0}+3\alpha _{1}} \over 7}}$, ${\displaystyle \alpha _{5}={{3\alpha _{0}+4\alpha _{1}} \over 7}}$, ${\displaystyle \alpha _{6}={{2\alpha _{0}+5\alpha _{1}} \over 7}}$, and ${\displaystyle \alpha _{7}={{1\alpha _{0}+6\alpha _{1}} \over 7}}$.

Otherwise, if ${\displaystyle \alpha _{0}\leq \alpha _{1}}$, four other alpha values are calculated such that ${\displaystyle \alpha _{2}={{4\alpha _{0}+1\alpha _{1}} \over 5}}$, ${\displaystyle \alpha _{3}={{3\alpha _{0}+2\alpha _{1}} \over 5}}$, ${\displaystyle \alpha _{4}={{2\alpha _{0}+3\alpha _{1}} \over 5}}$, and ${\displaystyle \alpha _{5}={{1\alpha _{0}+4\alpha _{1}} \over 5}}$ with ${\displaystyle \alpha _{6}=0}$ and ${\displaystyle \alpha _{7}=255}$.

The lookup table is then consulted to determine the alpha value for each pixel, with a value of 0 corresponding to ${\displaystyle \alpha _{0}}$ and a value of 7 corresponding to ${\displaystyle \alpha _{7}}$. DXT4's color data is premultiplied by alpha, whereas DXT5's is not. Because DXT4/5 use an interpolated alpha scheme, they generally produce superior results for alpha (transparency) gradients than DXT2/3.

• S2TC, patentless workaround
• FXT1
• DirectDraw Surface
• PVRTC
• Adaptive Scalable Texture Compression (ASTC)
• Ericsson Texture Compression (ETC1 & ETC2)
• Color Cell Compression

• US Patent & Trademark Office, Patent Full Text and Image Database, result for US 5956431 A
• USPTO Patent Assignment Search for US 5956431 A
• Microsoft Developer Network article on Block Compression in Direct3D 10
• squish, an MIT-licensed S3TC compressor. The site also contains an article giving an introduction to compression algorithms.
• Comparison between S3TC and FXT1 texture compression
• The Truth about S3TC Note: This article used an early S3TC compression engine, not nVidia's or ATI's updated codecs.

(Wayback Machine copy)

• Texture compression survey
• A fast, SSE2-enabled DXT1/5 compressor by Intel
• Betsy, a GPU-accelerated compressor.
• Modern open source BC1-7 encoders supporting Rate–distortion optimization (RDO)