Basis Universal - tree structure vector quantization?

Super happy that Binomial has provided basis_universal - Khronos Group are looking at standardizing it.

I'm working on an OpenCL implementation here. Made some good progress - a series of nested loops to compute the best ETC1S fit. ETC1S starts from a 5 bit color (ETC1 supports other colorspaces, but basis_universal uses 5 bit colors.) Then certain carefully chosen deltas are added to get the color of each pixel.

Here's the evaluate_solution function. Parallelizing that in OpenCL is pretty simple - one dispatched work item for each ETC1S block in the image.

What I'm working on is endpoint and selector optimization.

Endpoints start with the 5 bit "base color" of an ETC1S block. That "base color" describes a range of colors using selectors, which are 2-bits-per-texel values that choose a delta to add to the base color.

Optimizing is done by creating a codebook, which is all the blocks that use the same 5 bit color as the base color.

At first, many blocks will not use exactly the same color. This results in a more accurate output but a larger compressed .basis file. The first step is to find small changes that will have more blocks reusing the same base color (called "endpoint clusters" in the code). This is where the codebook is useful.

The codebook can use a tree structure to find similar blocks.

All of that is endpoint optimization. The step after that is selector optimization. Another codebook is created to find similar selectors (called "selector clusters" in the code).

Again, there's that same optimization process to find similar selectors and group them together. The goal is to stay close to the original image while making the ETC1S blocks have a lot in common so the final .basis file will have a small compressed size.

(It may be helpful to note the .basis file is uncompressed first into ETC1S blocks on the CPU. The GPU can then transcodes from ETC1S into whatever compressed texel format it actually supports using a compute shader.)

Similar values being pushed together - whether endpoints or selectors - is what the code means by "quantized."

Here's where I'm at. Does anyone want to look over this and review it?