Editing S3 Texture Compression

{{Short description|Texture compression algorithm}}
{{Infobox software
| name                   = S3 Texture Compression (S3TC)
| logo                   = 
| logo_size              = 
| developer              = [[S3 Graphics]]
| released               = {{Start date and age|1998|}}
| latest_release_version = 
| latest_release_date    = 
| operating system       = [[Microsoft Windows]]
| genre                  = [[texture compression]]
}}
'''S3 Texture Compression''' ('''S3TC''') (sometimes also called '''DXTn''', '''DXTC''', or '''BCn''') is a group of related [[lossy compression|lossy]] [[texture compression]] [[algorithm]]s originally developed by Iourcha et al. of [[S3 Graphics|S3 Graphics, Ltd.]]<ref>{{patent|US|5956431|"Fixed-rate block-based image compression with inferred pixel values"}}</ref><ref>{{cite patent|title=System and method for fixed-rate block-based image compression with inferred pixel values|pubdate=Sep 21, 1999|inventor-last=Iourcha|inventor2-last=Nayak|inventor3-last=Hong|inventor-first=Konstantine I.|inventor2-first=Krishna S.|inventor3-first=Zhou|country=US|number=5956431}}</ref> for use in their [[Savage 3D]] [[computer graphics accelerator]]. The method of compression is strikingly similar to the previously published [[Color Cell Compression]],<ref>{{cite journal|title=1990 IEEE Color Cell Compression Paper|last=|first=|date=|publisher=[[IEEE]]|doi=10.1109/TENCON.1990.152671|s2cid=62015990}}</ref> which is in turn an adaptation of [[Block Truncation Coding]] published in the late 1970s. Unlike some image compression algorithms (e.g. [[JPEG]]), S3TC's fixed-rate data compression coupled with the single memory access (cf. Color Cell Compression and some [[Vector quantization|VQ]]-based schemes) made it well-suited for use in compressing [[texture mapping|textures]] in hardware-accelerated [[3D computer graphics]]. Its subsequent inclusion in [[Microsoft]]'s [[DirectX]] 6.0 and [[OpenGL]] 1.3 (via the GL_EXT_texture_compression_s3tc [[OpenGL#Development|extension]]) led to widespread adoption of the technology among hardware and software makers. While S3 Graphics is no longer a competitor in the graphics accelerator market, license fees have been levied and collected for the use of S3TC technology until October 2017, for example in [[game console]]s and graphics cards. The wide use of S3TC has led to a [[de facto]] requirement for OpenGL drivers to support it, but the patent-encumbered status of S3TC presented a major obstacle to [[Open-source software|open source]] implementations,<ref>{{cite web |url=http://dri.freedesktop.org/wiki/S3TC |title=S3TC situation on official DRI information page |publisher=Dri.freedesktop.org |date= |access-date=2012-01-25 |archive-date=2012-01-19 |archive-url=https://web.archive.org/web/20120119112130/http://dri.freedesktop.org/wiki/S3TC |url-status=live }}</ref> while implementation approaches which tried to avoid the patented parts existed.<ref>[https://www.phoronix.com/scan.php?page=article&item=s2tc_s3tc_fix S2TC: A Possible Workaround For The S3TC Patent Situation] {{Webarchive|url=https://web.archive.org/web/20160513050935/http://www.phoronix.com/scan.php?page=article&item=s2tc_s3tc_fix |date=2016-05-13 }} on [[phoronix]]</ref>

== Patent ==
Some (e.g. US 5956431 A) of the multiple USPTO patents on S3 Texture Compression expired on October 2, 2017.<ref name="lwn-714524">{{Cite magazine |last=Yates |first=Tom |date=2017-02-15 |title=This is why I drink: a discussion of Fedora's legal state |url=https://lwn.net/Articles/714524/ |magazine=[[LWN.net]] |access-date=2017-02-16 |quote=...&nbsp;The patent on S3 texture compression expires on October 2, 2017, so Steam games might work better on Fedora after that date.&nbsp;... |archive-date=2017-03-01 |archive-url=https://web.archive.org/web/20170301064408/https://lwn.net/Articles/714524/ |url-status=live }}</ref> At least one continuation patent, [https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US6775417.pdf US6,775,417], however had a 165-day extension. This continuation patent expired on March 16, 2018.

== Codecs ==
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 [[Pixel|pixels]] to a 64-[[bit]] or 128-bit quantity, resulting in compression ratios of 6:1 with 24-bit [[RGB color space|RGB]] input data or 4:1 with 32-bit [[RGBA color space|RGBA]] input data. S3TC is a [[lossy data compression|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 mapping|normal map]] data, both of which usually generate [[Compression artifacts|artifacts]]. [[ATI Technologies|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]].<ref>{{cite web|url=http://www.gamershell.com/news/14362.html|title=DOOM 3 Video Requirements|last=Duffy|first=Robert|date=July 27, 2004|website=|publisher=Gamershell.com|url-status=dead|archive-url=https://web.archive.org/web/20080103155922/http://www.gamershell.com/news/14362.html|archive-date=January 3, 2008|access-date=2012-01-25}}</ref>

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|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 ==
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 <math>c_0</math> and <math>c_1</math>, and a 4×4 two-bit lookup table.

If <math>c_0 > c_1</math>(compare these colors by interpreting them as two 16-bit unsigned numbers), then two other colors are calculated, such that for each component, <math display="inline">c_2 = {2 \over 3} c_0 + {1 \over 3} c_1</math> and <math display="inline">c_3 = {1 \over 3} c_0 + {2 \over 3} c_1</math>.
This mode operates similarly to mode 0xC0 of the [[Apple Video|original Apple Video codec]].<ref>Togni, Roberto, et al. "[http://wiki.multimedia.cx/index.php?title=Apple_RPZA Apple RPZA] {{Webarchive|url=https://web.archive.org/web/20170704235213/https://wiki.multimedia.cx/index.php?title=Apple_RPZA |date=2017-07-04 }}". MultimediaWiki.</ref>

Otherwise, if <math>c_0 \le c_1</math>, then <math display="inline">c_2 = {1 \over 2} c_0 + {1 \over 2} c_1</math> and <math>c_3</math> is transparent black corresponding to a [[Alpha compositing|premultiplied alpha format]]. This color sometimes causes a black border surrounding the transparent area when linear texture filtering and alpha test is used, due to colors being interpolated between the color of opaque texel and neighbouring black transparent texel.

The lookup table is then consulted to determine the color value for each pixel, with a value of 0 corresponding to <math>c_0</math> and a value of 3 corresponding to <math>c_3</math>.

== DXT2 and DXT3 ==
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 <math>c_0</math> and <math>c_1</math>).

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 ==
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 4×4 3-bit lookup table) followed by 64 bits of color data (encoded the same way as DXT1).

If <math>\alpha_0 > \alpha_1</math>, then six other alpha values are calculated, such that <math display="inline">\alpha_2 = {{6\alpha_0 + 1\alpha_1} \over 7}</math>, <math display="inline">\alpha_3 = {{5\alpha_0 + 2\alpha_1} \over 7}</math>, <math display="inline">\alpha_4 = {{4\alpha_0 + 3\alpha_1} \over 7}</math>, <math display="inline">\alpha_5 = {{3\alpha_0 + 4\alpha_1} \over 7}</math>, <math display="inline">\alpha_6 = {{2\alpha_0 + 5\alpha_1} \over 7}</math>, and <math display="inline">\alpha_7 = {{1\alpha_0 + 6\alpha_1} \over 7}</math>.

Otherwise, if <math display="inline">\alpha_0 \le \alpha_1</math>, four other alpha values are calculated such that <math display="inline">\alpha_2 = {{4\alpha_0 + 1\alpha_1} \over 5}</math>, <math display="inline">\alpha_3 = {{3\alpha_0 + 2\alpha_1} \over 5}</math>, <math display="inline">\alpha_4 = {{2\alpha_0 + 3\alpha_1} \over 5}</math>, and <math display="inline">\alpha_5 = {{1\alpha_0 + 4\alpha_1} \over 5}</math> with <math>\alpha_6 = 0</math> and <math>\alpha_7 = 255</math>.

The lookup table is then consulted to determine the alpha value for each pixel, with a value of 0 corresponding to <math>\alpha_0</math> and a value of 7 corresponding to <math>\alpha_7</math>. 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.

== Further variants ==

=== BC4 and BC5 ===
{{main|3Dc}}
BC4 and BC5 (Block Compression 4 and 5) are added in Direct3D 10. They reuse the alpha channel encoding found in DXT4/5 (BC3).<ref name="reed">{{cite web |last1=Reed |first1=Nathan |title=Understanding BCn Texture Compression Formats |url=http://www.reedbeta.com/blog/understanding-bcn-texture-compression-formats/ |website=Nathan Reed’s coding blog |access-date=2020-09-01 |archive-date=2020-11-09 |archive-url=https://web.archive.org/web/20201109040712/http://www.reedbeta.com/blog/understanding-bcn-texture-compression-formats/ |url-status=live }}</ref>
* BC4 stores 16 input single-channel (e.g. greyscale) pixels into 64 bits of output, encoded in nearly<ref name=ryg/> the same way as BC3 alphas. The expanded palette provides higher quality.
* BC5 stores 16 input double-channel (e.g. tangent space normal map) pixels into 128 bits of output, consisting of two halves each encoded like BC4.

=== BC6H and BC7 ===
BC6H (sometimes BC6) and BC7 (Block Compression 6H and 7) are added in Direct3D 11.<ref name="reed"/>
* BC6H encodes 16 input RGB HDR (float16) pixels into 128 bits of output. It essentially treats float16 as 16 sign-magnitude integer value and interpolates such integers linearly. It works well for blocks without sign changes. A total of 14 modes are defined, though most differ minimally: only two prediction modes are really used.<ref name=ryg>{{cite web |last1=Giesen |first1=Fabian “ryg” |title=GPU BCn decoding |url=https://fgiesen.wordpress.com/2021/10/04/gpu-bcn-decoding/ |website=The ryg blog |access-date=24 July 2023 |language=en |date=4 October 2021 |archive-date=24 July 2023 |archive-url=https://web.archive.org/web/20230724085332/https://fgiesen.wordpress.com/2021/10/04/gpu-bcn-decoding/ |url-status=live }}</ref>
* BC7 encodes 16 input RGB8/RGBA8 pixels into 128 bits of output. It can be understood as a much-enhanced BC3.<ref name=ryg/>

BC6H and BC7 have a much more complex algorithm with a selection of encoding modes. The quality is much better as a result.<ref name="reed"/> These two modes are also specified much more exactly, with ranges of accepted deviation. Earlier BCn modes decode slightly differently among GPU vendors.<ref name=ryg/>

== S3TC format comparison ==
{| class="wikitable" style="text-align:center;"
|-
! FOURCC
! DX 10/11 name
! Description
! Alpha premultiplied?
! Compression ratio
! Texture type
|-
| DXT1    || BC1 || 1-bit alpha / opaque || Yes || 6:1 (for 24-bit source image) || Simple non-alpha
|-
| DXT2    || BC2 || Explicit alpha || Yes || 4:1 || Sharp alpha
|-
| DXT3    || BC2 || Explicit alpha || No || 4:1 || Sharp alpha
|-
| DXT4    || BC3 || Interpolated alpha || Yes || 4:1 || Gradient alpha
|-
| DXT5    || BC3 || Interpolated alpha || No || 4:1 || Gradient alpha
|-
| {{N/A}} || BC4 || Interpolated greyscale || {{N/A}} || 2:1 || Gradient
|-
| {{N/A}} || BC5 || Interpolated two-channel || {{N/A}} || 2:1 || Gradient
|-
| {{N/A}} || BC6H|| Interpolated HDR (no alpha) || {{N/A}} || 6:1 || Gradient
|-
| {{N/A}} || BC7 || Interpolated alpha || ? || 4:1<!-- 3:1 if no alpha --> || Gradient
|}

== Data preconditioning ==
BCn textures can be further compressed for on-disk storage and distribution ([[texture supercompression]]). An application would decompress this extra layer and send the BCn data to the GPU as usual.

BCn can be combined with Oodle Texture, a lossy preprocessor that modifies the input texture so that the BCn output is more easily compressed by a [[LZ77]] compressor ([[rate-distortion optimization]]). BC7 specifically can also use "bc7prep", a lossless pass to re-encode the texture in a more compressible form (requiring its inverse at decompression).<ref>{{cite web |title=Oodle Texture Compression |url=http://www.radgametools.com/oodletexture.htm |website=www.radgametools.com |access-date=2023-04-03 |archive-date=2023-03-18 |archive-url=https://web.archive.org/web/20230318033018/http://www.radgametools.com/oodletexture.htm |url-status=live }} Open source part mentioned: [https://github.com/richgel999/bc7enc_rdo bc7enc_rdo] {{Webarchive|url=https://web.archive.org/web/20210202215707/https://github.com/richgel999/bc7enc_rdo |date=2021-02-02 }}</ref>

crunch is another tool that performs RDO and optionally further re-encoding.<ref>{{Cite web|url=https://github.com/BinomialLLC/crunch|title=crunch open source texture compression library|website=GitHub|access-date=2016-09-13|archive-date=2016-09-09|archive-url=https://web.archive.org/web/20160909164533/https://github.com/BinomialLLC/crunch|url-status=live}}</ref>

In 2021, Microsoft produced a "BCPack" compression algorithm specifically for BCn-compressed textures. Xbox series X and S have hardware support for decompressing BCPack streams.<ref>{{cite web | url=https://learn.microsoft.com/en-us/gaming/gdk/_content/gc/system/overviews/directstorage/directstorage-overview | title=DirectStorage Overview - Microsoft Game Development Kit | date=16 March 2023 | access-date=3 August 2023 | archive-date=3 August 2023 | archive-url=https://web.archive.org/web/20230803135559/https://learn.microsoft.com/en-us/gaming/gdk/_content/gc/system/overviews/directstorage/directstorage-overview | url-status=live }}</ref>

== See also ==
* [[S2TC]], patentless workaround
* [[FXT1]]
* [[DirectDraw Surface]]
* [[PVRTC]]
* [[Adaptive Scalable Texture Compression]] (ASTC)
* [[Ericsson Texture Compression]] (ETC1 & ETC2)
* [[Color Cell Compression]]

== References ==
{{reflist|30em}}

== External links ==
* [http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/5956431 US Patent & Trademark Office, Patent Full Text and Image Database, result for US 5956431 A]
*[https://assignment.uspto.gov/patent/index.html#/patent/search/resultAbstract?id=5956431&type=patNum USPTO Patent Assignment Search for US 5956431 A]

[[Category:3D computer graphics]]
[[Category:Lossy compression algorithms]]
[[Category:Texture compression]]