On DXTn Compression

Moderator: Halo Moderators

Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

On DXTn Compression

Post by Altimit01 » Fri Jun 06, 2008 3:25 pm

DXTn compression is the more common name for what is known as S3 Texture Compression (S3TC). It was developed by S3 Graphics Ltd. but has since become the de-facto standard for computer game bitmaps with its inclusion in Microsoft’s DirectX. DXTn compressed images are almost exclusively seen in Microsoft’s DirectDraw Surface files (.dds). All of the formats follow a similar algorithm so for the purposes of this article we’ll only cover DXT1. DXT1 compresses an image by using texels, a 2 color palette and a 2 bit/pixel lookup table.

Texels: A texel is a 4x4 pixel (16 total) block in the larger image that is the principle building block of DXTn compression. The DXT1 texel is represented in code as 64-bit block of data. For comparison a 16 pixel uncompressed image using R5G6B5 would be 256 bits. The DXT1 code is broken up into 2 sections. The first is 32 bits long and consists of 2 16-bit colors (R5G6B5). The second is a 32 bit long lookup table where every 2 bits represents a pixel color of value 0 through 3 for each of the 16 pixels. The pixel location in the texel is implicitly defined by the structure so that the first four 2-bit values are the four pixels left to right of the top row, the next four are the next row from left to right and so on. The 2-bit values in the look-up table indicate which of 4 possible colors the pixel can be. Those 4 colors consist of the 2 colors stored in the first 32 bits and 2 colors spaced evenly between the first two.

For example, say that color1 (the first defined color) is R:10, G:50, B:75 (a dark blue) and that color4 (the second defined color) is R:200, G:200, B:200 (a very light grey). Color2 would be R:73, G: 100, B: 142 (a light blueish grey color) and color3 would be R:135, G:150, B:158 (a light grey). Color2’s red channel was calculated using 2/3 the value of color1’s red and 1/3 the value of color4 (10*2/3 + 200*1/3 ≈ 73). Color3 did the same thing in reverse using 2/3 of color4’s values and 1/3 of color1’s values. In special cases, DXT1 may only use 3 colors with the fourth “color” representing transparency.

As can be seen, this compresses 16 possible colors into 4, but those 4 colors all line along the same gradient which is chosen to best fit those 16 colors. With what’s already been shown it’s quite possible to render a DXT1 compressed image, but compressing an image into DXT1 requires determining the best possible gradient. The most common technique used is Principle Component Analysis (PCA). PCA in its most general form is a way of rotating a coordinate system such that along the principle axis there is the greatest amount of variation in value with each subsequent axis having less. In most cases only the principle axis is used to transform a higher order data system to a one dimensional system. Since along the principle axis the data varies the most, it also represents the best possible straight line that fits the data. This makes PCA perfect for determining the color gradient in DXTn compression.

By treating all 16 colors as coordinates in 3-space using red, green and blue as the original axis we can use PCA to find one of the best possible gradients for compression. The first step for PCA is to create a covariant matrix of the system (3x3 for 3 dimensions). A covariant is a value which represents how much one dimensions value varies with respect to the variation of another variation. The covariant of X and Y aka cov(X,Y) is expressed by this equation:

Image

A variance is simply the measure of how much a single dimension varies and is equal to cov(X,X) for whatever dimension the variance relates to. The square root of a variance is the standard deviation of that dimension which is often used during statistical analysis. The covariance matrix that we will use for image compression looks like this:

Image

It is important to note that the covariance must be constructed from a data set that has a mean value of 0 for all dimensions. So before finding the covariance, we will need to subtract the mean value of each color channel. So now that we have our matrix that contains information about all possible changes in any dimension, we can use matrix math to find the axis along which there is the most variation. First we need to find the eigenvalues of the matrix. Since this a 3x3 real symmetrical matrix we know that there are 3 real eigenvalues and that the eigenvectors are real and orthogonal (which is important since we’ll be using the eigenvectors as our new axes). The eigenvector corresponding to highest eigenvalue is the principle axis with each successively lower eigenvalue corresponding to the next most significant axis.

Notes on matrix math:
Eigenvalues and eigenvectors are special properties of square matrices. An eigenvalue is any value that satisfies the following equation:
Image
That is to say, for every invertible square matrix there exists a value that can represent the matrix when multiplied by a vector. The number of these eigenvalues is equal to the order of the matrix although they may be repeated or complex. An eigenvector is the vector that satisfies the above equation for a given eigenvalue (which may be complex). The eigenvectors do not have fixed values, but each element of the vector is directly proportional to the others.

So by finding the eigenvector of the highest eigenvalue we have a vector that represents the best fit gradient we will use for our compression. By finding the dot-product of each pixel color and the unit-length gradient (subtracting the mean value of each channel for those colors), we can determine each colors projection along the principle axis. The next important step in PCA/DXTn compression is to determine the endpoints of the gradient.

A simple process is to find the maximum and minimum projections along the principle axis and pick the points at 1/8 along that line and 7/8 along that line (with the two calculated points being 3/8 and 5/8). Then it is a simple matter of determining which projection value correlates to which of the four points on the line. We have now simplified the 16 possible colors into 4 points along a 0-mean gradient in color-space. All that remains is to convert the two endpoint colors into actual colors (by re-adding the channel mean values) and we have the two colors that will be stored in the texel data. With all of this it is now possible to compress an image into DXT1.

For more information:
DXTn, S3TC compression - Wikipedia
PCA - Wikipedia
PCA - squish library
Covariance - Wikipedia
Eigenvalues and eigenvectors in general - Wikipedia
PCA, covariance, eigenvalues and eigenvectors - mediafire:PDF
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

Excend
Commando
Posts: 2791
Joined: Sun May 06, 2007 3:27 am
Location: SiK x Gh0sTs Rehauled.
Contact:

Post by Excend » Fri Jun 06, 2008 3:50 pm

there is no way im gonna read that whole thing, and if i do, i wont understand half of it, but good job, it looks good enough for a sticky
TaxiService wrote:Roses are red
Violets are blue
What a shitty thread
Fuck all of you.

Dirk Gently
Commando
Posts: 2047
Joined: Sun Oct 21, 2007 2:34 pm
Location: 3C0E9056
Contact:

Post by Dirk Gently » Fri Jun 06, 2008 3:57 pm

Very useful Alt.
*light applause*

?Fe?thers?
Ranger
Posts: 866
Joined: Fri Oct 19, 2007 4:11 pm
Location: I'm under there. Under where? AHHAHA Got you to say underwear!!!!

Post by ?Fe?thers? » Fri Jun 06, 2008 4:13 pm

Anyone want to make a summary of that?
I am with ghosts on this one, looks good. But from the first senence it wont help me at all.
?Fe?thers? [Full]
Jhypestype [Demo]
Image
^Credit to G[v]N^
Image
somewhat tasty!

TaxiService
Night Stalker
Posts: 6887
Joined: Thu May 24, 2007 5:52 am
Location: 41.896198, 12.4165945
Contact:

Post by TaxiService » Fri Jun 06, 2008 10:23 pm

uhm... thanks, but... why did you tell us?



oh, i started to read it and... understand a little, but then my father came and started bothering, so now i dont remember where i was. <_>

nice job anyway.
  • TaxiService! Shitposting since 2007!
MGM Sig

Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

Post by Altimit01 » Fri Jun 06, 2008 10:57 pm

Main reason was to share the information I've discovered. So that other people if they're interested can do the same. Short answer: it's the difference between this and this. Although there's still code to do before it's actually operational.
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

TaxiService
Night Stalker
Posts: 6887
Joined: Thu May 24, 2007 5:52 am
Location: 41.896198, 12.4165945
Contact:

Post by TaxiService » Sat Jun 07, 2008 12:24 am

ooooooh.

Okay so.
  • TaxiService! Shitposting since 2007!
MGM Sig

Slapzy
Ranger
Posts: 1806
Joined: Mon May 05, 2008 3:21 pm
Location: ~root@208.113.172.130# sudo rm -f /

Post by Slapzy » Sat Jun 07, 2008 1:16 am

hmm good job, i understand most of it, how much difference is there in gameplay?

and what editor is that?
at first i thought HMT 7.5, but it has a different layout.
~ Teh Slapz
Image
TaxiService wrote:OMG BARREL ROLL ON ACIDS
._. \·. |: /.· .-. ·.\ :| .·/ ._. \·. |: /.· .-. ·.\ :| .·/ ._.
WHOOHHAGHGHHGEHGR

Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

Post by Altimit01 » Sat Jun 07, 2008 1:43 am

It basically speeds up game-play since this form of data compression is fixed-rate meaning that hardware accelerated graphics (video cards) can utilize it to speed up rendering time.
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

Excend
Commando
Posts: 2791
Joined: Sun May 06, 2007 3:27 am
Location: SiK x Gh0sTs Rehauled.
Contact:

Post by Excend » Sat Jun 07, 2008 4:02 am

Altimit01 wrote:Main reason was to share the information I've discovered. So that other people if they're interested can do the same. Short answer: it's the difference between this and this. Although there's still code to do before it's actually operational.

is there a paticular reason that the second one is also shorter but wider than the first one?
TaxiService wrote:Roses are red
Violets are blue
What a shitty thread
Fuck all of you.

Slapzy
Ranger
Posts: 1806
Joined: Mon May 05, 2008 3:21 pm
Location: ~root@208.113.172.130# sudo rm -f /

Post by Slapzy » Sat Jun 07, 2008 5:33 am

an illusion?

EDITS

i overlaid one over the other in Ps, the injected bitmap pic is the same size, the main app window was just resized a bit

Image
~ Teh Slapz
Image
TaxiService wrote:OMG BARREL ROLL ON ACIDS
._. \·. |: /.· .-. ·.\ :| .·/ ._. \·. |: /.· .-. ·.\ :| .·/ ._.
WHOOHHAGHGHHGEHGR

xxxshooter
Veteran
Posts: 279
Joined: Wed Feb 27, 2008 3:38 pm
Contact:

Post by xxxshooter » Sat Jun 07, 2008 6:54 am

so that application was HMT?
Still in progress:
Image

TaxiService
Night Stalker
Posts: 6887
Joined: Thu May 24, 2007 5:52 am
Location: 41.896198, 12.4165945
Contact:

Post by TaxiService » Sat Jun 07, 2008 8:30 am

Slappey wrote:an illusion?

EDITS

i overlaid one over the other in Ps, the injected bitmap pic is the same size, the main app window was just resized a bit
if you notice, the "Import" button is actived in one of the two pics.
  • TaxiService! Shitposting since 2007!
MGM Sig

Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

Post by Altimit01 » Sat Jun 07, 2008 10:54 pm

xxxshooter wrote:so that application was HMT?
Here's a hint.
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

Modzy
Green Beret
Posts: 3058
Joined: Fri Feb 22, 2008 11:06 pm
Location: Portland, OR

Post by Modzy » Sat Jun 07, 2008 10:55 pm

Altimit01 wrote:
xxxshooter wrote:so that application was HMT?
Here's a hint.
Hahahahahahah lol Where can I get that?

EDIT: Not out yet. Sad Face :(
Last edited by Modzy on Sun Jun 08, 2008 1:15 am, edited 1 time in total.

Post Reply

Who is online

Users browsing this forum: No registered users and 17 guests