Most standard texture compression formats, such as BCn, ETC/EAC, and ASTC, use algorithmic vector quantization to determine codebook entries based on the encoded block. The contents of the encoded blocks are divided into three categories: header/mode bits, endpoints that represent colors in the block, and indices for selecting colors from a palette. The encoding process involves linear interpolation and a squared error error metric. Contrary to popular belief, encoding textures is not a computationally complex task. The full image can be encoded in linear time as long as each block is encoded independently and in a bounded amount of time. Exhaustive search can be used for simpler formats like BC1-5 and ETC/EAC, but it is not feasible for more complex formats like BC6-7 and ASTC. Despite its practicality, exhaustive encoding is not recommended for practical use. The author also emphasizes that assumptions about computational complexity should not be made solely based on similarities to known hard problems and that exploiting symmetries can simplify combinatorial optimization problems. Furthermore, computers are fast, and trying a large number of possibilities is feasible as long as trials are quick and multiple cores are available. The author has personally tested numerous functions exhaustively for the
https://fgiesen.wordpress.com/2023/07/21/computational-complexity-of-texture-encoding/