[Basic]

OK, I'm a bit late here, but I've been away.

Originally Posted by andypski

Overall it might not be a gain at all - block->block noise (low frequency noise created by colour choice mismatches at block intersections) is one of the key problems that a high quality DXTC compressor needs to deal with, and is very difficult to solve optimally. In addition to this the low-frequency and structured nature of this noise makes it one of the most noticeable artifacts caused by the compression. With a larger block size the errors from block->block are likely to get larger.

If I got it right, DXT1 (I used that name to explicitly say "no alpha on the side") have two different compression blocks; 3-color-block, and 2-color-1-transparent-block. Each block has it's own mini-palette. The type of the block can be chosen indpendently per block.

So palette is chosen per 4x4 texel block, compression type per 4x4 texel block.

In the S3TC-similar compression blocks, FXT1 selects the palette per 4x4 texel block. But the compression type is as always in FXT1 selected per 8x4 block.

Are you saying that:
1) The slightly higher granularity in compression type selection will reduce block>block noice.
And/or
2) None of the extra modes in FXT1 would ever be used. Not even for, say, slow gradients, or multi-bit alpha modes still at 4bpp.

[Simon F]

Originally Posted by Basic

If I got it right, DXT1 (I used that name to explicitly say "no alpha on the side") have two different compression blocks; 3-color-block, and 2-color-1-transparent-block.

A minor correction: The two modes are "4-colours" (2 implied from the 2 stored base colours) and "3-colours + transparent black".

[andypski]

Originally Posted by Basic

Are you saying that:
1) The slightly higher granularity in compression type selection will reduce block>block noice.
And/or
2) None of the extra modes in FXT1 would ever be used. Not even for, say, slow gradients, or multi-bit alpha modes still at 4bpp.

I had a long reply to this typed in but lost it in a crash, so this version is going to be fast and dirty, but I hope clear enough.

My recollection of FXT1 is that it had 4 compression modes -

CC_MIXED. 4x4 block, 2 565 endpoints and 2 interpolant colours. Basically identical to S3TC.

CC_HI. 8x4 block, 2 555 endpoints and 5 interpolants with 1 explicit transparent encoding.

CC_CHROMA. 8x4 block, 4 555 explicit colours

CC_ALPHA. 8x4 block. 3 5555 endpoints, 2 interpolants between endpoint 0 and 1 for the left 4x4 area and 2 between endpoints 1 and 2 for the right 4x4 area.

The CC_MIXED mode could not coexist in an image with the other formats because this created a dependency between the format chosen per block and the texel addressing (how do you find a specific texel on a line that is composed of different block sizes?) You would need to add an index of some kind, which would get messy.

So in mixed-mode images only the 8x4 formats are available. The compression of both S3TC and FXT1 on colour images is 4bpp, so for each 8x4 FXT1 block you have 2 S3TC blocks in a direct apples->apples comparison. Looking at the descriptions above it can be seen that for colour-only data S3TC should always be a superior representation to either the CC_CHROMA and CC_ALPHA formats for any data, and it is questionable whether CC_HI is better for gradients as well (lower endpoint precision with 1 extra interpolant vs. 2 extra explicit colours at higher precision.)

So for colour images FXT1 is pretty much a bust - I would expect that on almost all images the best S3TC compressor would beat the best FXT1 compressor for quality.

For images with alpha the presence of the CC_ALPHA format makes things interesting because it allows 4bpp compression of complex alpha, but the image quality will be lower than the 8bpp S3TC equivalent, so it is questionable if this is a big advantage.

Overall FXT1 seemed like a bit of a 'me too' exercise on the part of 3dfx and didn't really offer anything compelling above what S3TC provided, so it's not surprising that it didn't generate much interest.

- Andy.

[Basic]

Simon:
DOH Are you sure that two bits can represent 4 values?
I'll blame it on my always occuring post-Xmas cold.

andypski:

CC_MIXED has two sub modes (just as S3TC). Both are 8x4 blocks, but they split this 8x4 block into two 4x4 sub blocks.
Sub-modes:
CC_MIXED non-transparent: One 555 endpoint and one 565 endpoint, 2 interpolant colors.
CC_MIXED transparent: One 555 endpoint and one 565 endpoint, 1 interpolant color, 1 transparent "color".

And it certainly is possible to mix CC_MIXED freely with the other modes in the same texture. The only limitation is that both S3TC-like blocks in a CC_MIXED block must use the same mode (transparent/non-transparent).

Enhancements possible by small changes in the standard (not using any more memory):
CC_MIXED: All endpoints 565
CC_HI: One endpoint 565
CC_CHROMA: All endpoints 565
CC_ALPHA: One extra bit in one of the endpoints, not realy worth it.
There is coding space left for other compression modes, if someone see a new usefull mode.

[andypski]

Originally Posted by Basic

CC_MIXED has two sub modes (just as S3TC). Both are 8x4 blocks, but they split this 8x4 block into two 4x4 sub blocks.
Sub-modes:
CC_MIXED non-transparent: One 555 endpoint and one 565 endpoint, 2 interpolant colors.
CC_MIXED transparent: One 555 endpoint and one 565 endpoint, 1 interpolant color, 1 transparent "color".

And it certainly is possible to mix CC_MIXED freely with the other modes in the same texture. The only limitation is that both S3TC-like blocks in a CC_MIXED block must use the same mode (transparent/non-transparent).

Aha! My (somewhat old) memory of FXT1 must be playing tricks on me.

Being able to include CC_MIXED blocks does make it a bit more interesting, but the other block modes still seem to be fairly uninteresting in general. The CC_ALPHA mode is still the only really interesting extension as explained above. In addition, reducing the precision of one of the endpoints can cause some problems due to increased quantisation noise, and the ability to freely mix 3 and 4 colour blocks in DXTC (without restrictions) can also marginally improve compression quality in some cases with smart compressors.

Changing the encoding to keep higher resolution endpoints at all times would make the spec much more interesting as it should then beat S3TC in all cases (although perhaps only marginally) - can you outline this suggestion and the new encoding?

- Andy.

[Basic]

The redundancy in FXT1 is in the placement of base colors. It's possible to switch places on the base colors, and then do the corresponding changes in the index field.

This can be used in different ways:
You could see the colors as 15 bit integers (removing the last green bit), and do compares between them.
So ie for (one half of) CC_MIXED:

if(color0<color1) {
  color0.greenlsb=0;
  color1.greenlsb=the_other_bit_stored_explicitly;
}
else {
  color0.greenlsb=the_other_bit_stored_explicitly;
  color1.greenlsb=1;
}

This scheme would btw be "compatible" with FXT1 in the sense that if you compress with FXT1 and decompress with this "FXT2" (or the other way around), the output will still be correct except for the green lsb.

Another way is to lock certain texels to certain (groups of) colors:
For CC_ CHROMA:
Texel0 always use color0 => 2 bit freed in the index array
Texel1 always use color0/1 => 1 bit freed in the index array
And then do a comparison as above between color2/3 for the fourth bit.
There's the four needed green lsb bits.
There is actually one bit that isn't used at all in this mode, so that one could be used as the fourth bit. But then you'd waste easy coding space for future enhancements with new compression modes.

[andypski]

So in your encoding I have 1 explicit bit that I specify per (4x4) CC_MIXED block as 0 or 1, and an implicit encoding from the ordering of the endpoint values that manipulates the effective LSB that is then substituted back into the green channel of each endpoint? I worked your example through, but couldn't generate the case where I could have colour 0's LSB as 1 and colour 1's LSB as 0 - have I misunderstood the encoding?

[Basic]

You're right that color0.glsb=0 and color1.glsb=1 together isn't possible. But you don't need that!
Think of it like this; the color order determines the green lsb of the "smallest" color, while the explicit bit is the green lsb of the "largest" color. With that in mind, you can easily see that you can set the green lsb of both colors to anything you want.
You just never need to set color0.glsb=0 and color1.glsb=1, the colors would be swaped instead.

There is just one "problem", if the colors are equal when the green lsb is stripped off. But otoh, the solution is quite simple. If the colors are equal, then color1.greenlsb=1 according to the rules above. So set the explicit bit to 0, and you've got all cases covered.

[andypski]

Gotcha.

[Basic]

I'll read that as "I see what you're saying". (Normally I would interpret "Gotcha" as "I nailed you down there".)

Btw, you didn't seem too impressed about the CC_CHROMA mode at all. I know that it doesn't have the fine gradients in it, so it's just 4 colors total over the whole 8x4 block. But remember that it's the only mode that breaks the "one-dimentional" color limit. A block where three different colors meet will get big errors in all other modes. Try to get red, green and blue into the other modes.


Now back to a different place where compression might be interesting.
What if a GPU has a virtualized memory (like P10). Textures are split into blocks. (I don't remember the exact size for P10, was it 4KB? => 32x32texel@32bit.) If each of those 32x32 blocks were ~jpg compressed, and decompressed by the GPU as they were loaded into gfx card mem, then AGP memory could suddenly become a lot more useful.

AGP bandwith would be virtually multiplied by the jpg compression ratio. The jpg decompression wouldn't need to work in random order (as normal texture decompression schemes need). The possibly variable block size wouldn't be such a big problem here, since we could use a table to see where the blocks are stored. The table would be just 1/1024 of the (uncompressed) texture size, and the cost of the indirection isn't that bad since it's only going to be used when loading new textures over AGP, and it will be used in pair with a transfer of a rather large block of data.

It should be noted though, that the working set of textures still should fit into gfx card mem. The "working set" of textures being those needed to render one entire frame, and that probably will be there next frame too. Or in other words, textures should still only be loaded over AGP when getting into new areas/revealing new textures.

[andypski]

Originally Posted by Basic

I'll read that as "I see what you're saying". (Normally I would interpret "Gotcha" as "I nailed you down there".)

I see what you're saying

Btw, you didn't seem too impressed about the CC_CHROMA mode at all. I know that it doesn't have the fine gradients in it, so it's just 4 colors total over the whole 8x4 block. But remember that it's the only mode that breaks the "one-dimentional" color limit. A block where three different colors meet will get big errors in all other modes. Try to get red, green and blue into the other modes.

It may have some uses, but I suspect the number of instances where it would be selected over standard S3TC blocks is fairly rare interms of overall error - it might reduce blocking slightly in some circumstances, but in real-world images/textures you can usually trade off some chroma accuracy in small areas without much visual blocking, particularly if there is any high frequency noise structure in the area - this would tend to mask the chroma inaccuracy. I suspect CC_CHROMA would come into play if you were trying to compress images such as HUD displays (which might have widely different primary colours in a single block)

With alterations in encoding FXT(2!) becomes interesting, but still not much of an advance over S3TC on the kinds of images it's designed to represent. It would be interesting to write a good encoder for this new format to see how it performs. 3DFX's original FXT1 encoder was really not very good at all (and it was so slow...)

[Basic]

You're probably right that the places were CC_CHROMA would be at most use would be at HUDs, or displays/signs/maps/diagrams, which often can be colorful. But I guess I can't be sure unless I have some example pictures. Maybe it's OK with rather large chroma errors, if it's on just a small area. (But since it's for textures, you'd never know how large area they will be expanded to.)

3DFX's original FXT1 encoder was really not very good at all (and it was so slow...)

Well, that's one thing that we agreed on all the time. If you have the encoder, then try anything with small black and white details. (So that there's black and white in every block.) Then try to compress it over a weekend or so... In some modes they actualy made exhaustive searches, but used an incorrect measure for what was optimal. I think I have the FXT1 source laying around somewhere.

I actually started to write a FXT1/2 en-/de-coder, but kinda' lost the interest when no one seemed to be interested in the format, and then 3dfx disapeared.

Btw, I know that 3dfxs' FXT1 encoder didn't attempt to do any dithering, did S3s' compressor do that?

[andypski]

Originally Posted by Basic

Btw, I know that 3dfxs' FXT1 encoder didn't attempt to do any dithering, did S3s' compressor do that?

Of course the source code for S3's encoder was never made public.

(But no, it didn't... )

You can check that out on example images easily enough.

[Basic]

But you know because you were involved writing it?

I just have a feeling you're already closer to a FXT* compressor than I ever was, because you already have some nifty optimization source laying around.

[andypski]

Originally Posted by Basic

But you know because you were involved writing it?

I just have a feeling you're already closer to a FXT* compressor than I ever was, because you already have some nifty optimization source laying around.

I can't lay claim to writing the original S3 compressor, although I do work extensively with the guy who did write it. (On compression, amongst other things...)

Since I no longer work for S3 I'm afraid I don't have access to the original compressor any more (it was a very clever one in many ways)

It should be possible to write an even better version than the original S3 version, but I think it would take significant time and research to beat it by any significant margin. I know that Simon F. thought that his own S3TC compressor gave better results on some images at least - he commented on this on his home page, although we would respectfully disagree (on the limited basis we have for comparison).

[Dio]

Originally Posted by Basic

Btw, I know that 3dfxs' FXT1 encoder didn't attempt to do any dithering, did S3s' compressor do that?

I would say that targetting things like dithering and error diffusion is barking up the wrong tree a bit. The errors introduced by the compression process don't really lend themselves to an error-diffusion type model as far as I can see.

Concentrate on a really good block compressor and you'll see much better results. (Any kind of extensive search, by the way, will never be fast). After that look at advanced stuff!

Of course, that's not easy

[Simon F]

Originally Posted by andypski

It should be possible to write an even better version than the original S3 version, but I think it would take significant time and research to beat it by any significant margin. I know that Simon F. thought that his own S3TC compressor gave better results on some images at least - he commented on this on his home page, although we would respectfully disagree (on the limited basis we have for comparison).

In my defense, it was only on "some images" and it was a long time ago .

I think the problem I found with the S3 compressor was that it had some default weights that emphasised the green channel over the red and blue. (IIRC, according to Poynton's colour FAQ, although the eye is less spatially sensitive to blue than the other primaries, it is still quite sensitive to overall blue levels.) On one or of the two test images I tried, the S3 compressor produced an almost monochromatic green result, although I suspect that in general the S3 compressor would be superior.

FWIW, having looked at the description of the compression process in the S3 patent, I noticed some of the techniques described (e.g. principal vector analysis) are probably similar to those I used in the VQ tool (which I'd based on the work by Wu).

I suppose I could update my compression comparison page to use the S3 compression tool but I'm a bit busy (or lazy). Besides, the old version I have has the feature that makes it crash immediately after you output a decompressed .bmp file from a .s3tc input file! It's a bit tedious.

[andypski]

Originally Posted by Simon F

I think the problem I found with the S3 compressor was that it had some default weights that emphasised the green channel over the red and blue. (IIRC, according to Poynton's colour FAQ, although the eye is less spatially sensitive to blue than the other primaries, it is still quite sensitive to overall blue levels.) On one or of the two test images I tried, the S3 compressor produced an almost monochromatic green result, although I suspect that in general the S3 compressor would be superior.

As I recall I think your analysis is pretty correct here - there can be some rare instances where it doesn't do so well (although we had a large test suite for the compressor to try to avoid this). Certainly I believe that on regions of completely random colour noise (essentially uncompressible) it would tend to bias heavily towards green (so blocks that had an overall 'neutral' character in the original would end up greenish), but on real world images this effect didn't show up.

Actually there was a bug/feature that could cause a very slight (1 lsb) green shift in some circumstances, but I don't think this was ever tracked down and fixed (it can sometimes be seen when compressing greyscales)

Where the S3 compressor was pretty good was manipulating the endpoints and clustering to squeeze out more signal->noise.

[Simon F]

Originally Posted by andypski

Actually there was a bug/feature that could cause a very slight (1 lsb) green shift in some circumstances, but I don't think this was ever tracked down and fixed (it can sometimes be seen when compressing greyscales)

Isn't that almost an inevitable side-effect of using 565 base colours? (Though, frankly, I don't think it's at all important)

Where the S3 compressor was pretty good was manipulating the endpoints and clustering to squeeze out more signal->noise.

I tried something along those lines as well. It's annoying how you can't analytically compute the optimum end points.

[andypski]

Originally Posted by Simon F

Isn't that almost an inevitable side-effect of using 565 base colours? (Though, frankly, I don't think it's at all important)

I think it may be pretty much inevitable in a compressor that is trying to make the best use of the available colour precision. I have seen compressors that didn't exhibit this overall shift, but they weren't as good at representing the shallow gradients.

I tried something along those lines as well. It's annoying how you can't analytically compute the optimum end points.

Yes - this is an irritating problem with getting an optimal compression solution - balancing error by manipulation of the endpoints, and finding the global minima rather than a local one.

[Dio]

Originally Posted by Simon F

It's annoying how you can't analytically compute the optimum end points.

Actually, I did find an analytical solution to most of the problem (everything except the rounding to 565). But I never managed to make it work - which means it is possible (likely?) it wasn't actually a solution

[Simon F]

Originally Posted by Dio

Actually, I did find an analytical solution to most of the problem (everything except the rounding to 565). But I never managed to make it work - which means it is possible (likely?) it wasn't actually a solution

You've got me very intrigued :?. I don't understand at all how you can do it analytically with all the discontinuities.

For example, with the DC VQ compressor, given a set of image vectors and a chosen partition of that set into two subsets (on either side of a plane perpendicular to the principal axis), you can easily compute two representative vectors for those subsets that gives a local minimum in the error. The problem is that you might be able to move the plane (and suddenly the sets change (i.e. the error function is discontinous)) and you might get a lower error.

I just chose to sweep the partition plane through the entire set to find all possible minima (which, luckily, is linear operation in the number of vectors).
Although it'd be more complicated, I suppose you could do the same with the S3TC encoding whereby you have "4" subsets.

[Dio]

I suppose I still had to check a bunch of cases and pick the best, but it was reduced to a maximum of 16, and it was guaranteed to give me the minimum error, so I call it analytical

I also had to make a pretty big bunch of assumptions but most of them I was making anyway in the progressive refinement version I was trying to replace - reduction to a 1D problem, midpoint is centre of extremities, etc.

Anyway, it never worked, and the progressive refinement was both faster (it rarely executed more than a couple of iterations) and great quality, so I dumped it.

[Brimstone]

Originally Posted by andypski

You can get about twice the compression ratio of DXTC (for colour-only images), but the difference between 2bpp and 4bpp is not really of much interest in the video card market. Smaller than 4bpp is of interest mainly in areas where memory is at a huge premium (handheld devices etc). As far as video cards go if VQ's higher compression ratio couldn't win the day back when it was first introduced (when devices might typically have only about 8-16 MB of onboard RAM) then it is hardly likely to be a convincing argument now.

In the consumer 3D space the most interesting aspect of compression is increasing the efficiency of texturing, and DXTC solves that problem just fine - the added benefits of dropping to 2bpp vs. 4bpp in overall texturing efficiency are generally pretty marginal (considering you've already dropped from 24bpp->4bpp, and effectively from 32bpp->4 bpp, since most 3D hardware does not use packed texel formats).

Whether the image quality of VQ at 2bpp is equivalent to DXTC at 4bpp is a long and involved discussion in and of itself, but in most typical cases I believe it to be somewhat lower quality overall (although in the same ballpark). Of course each compression method has different strong and weak points in terms of IQ, and therefore the exact situation varies from image to image. I know that Simon had a comparison of some aspects of this on his homepage where he made some interesting observations on quality/bit.

VQ compression is also not great for hardware, as Simon has touched upon, since you need to hide an additional indirection. Also, for properly orthogonal support you have to be able to use N different sets of VQ palettes, where N is the number of simultaneous textures you support.

What about Light Field mapping which gains from both VQ and Texture Compression? Any merit in going this direction?









Light Field Mapping analysis


Intel Research on Light Field Mapping

[gkar1]

Originally Posted by Humus

S3TC has served us well for a while now, but I feel the time for retirement of texture compression is closing in. In the future with long shaders etc. I think texture compression will be more and less of a forgotten feature as shader execution will be the performance determining factor and not the memory bandwidth.

I agree, with the increasing flexibility and performance of pixel shaders, procedural textures are the way to go IMO.