# Most efficient mapping of pixel to colors with colormaps

I'm working on a module that handles colormaps and I want to make the mapping of pixel to colors as efficient as possible. It is a performance critical section of our app. Our current solution works like this:

I have a normalized double value x (range [0, 1]) per pixel that denotes the position inside the colormap. The colormap itself is layed out as a vector of arbitrary size of RGBA elements. Now I basically scale my double x*(colormap.size()-1) and access the color like so:

RGBA a = colormap[static_cast<int>(x*(colormap.size()-1))]

This methods has some drawbacks:

• With increasing resolution of the colormap, the vector storage is growing unnecessarily large causing a lot of cache misses as pixel indexes jump seemingly random inside the vector.
• I need to static_cast to integer which again costs me some muops. I guess it doesn't matter in the large scale that much but I question if this can be skipped with a more efficient algorithm

I bet that someone has come up with such a solution over time. I could for example imagine something like a parametric curve through a color cube. However: Fragmented colormaps should also be included (e.g. hard borders between different color areas) should be possible, which would be difficult with this approach.

Is there a more efficient approach?

EDIT: The colormap can either be fragmented or linear but not both. Maybe some optimization could be based on that.

• Are you using a true colormap (as in, when you know the RGBA value of a particular element and the size of the map, you cannot know the RGBA values of adjacent elements), or is there actually an underlying algorithm for determining the progression of colors in your colormap? Oct 25, 2023 at 8:18
• @BartvanIngenSchenau Yes it's a true colormap. It can be arbitrary, it is not assumed to be generated (or it can be in some cases). Oct 25, 2023 at 12:10

Is this on the CPU or GPU?

On a GPU this is a "one dimensional texture", which is a highly optimized lookup. By default it will linear-interpolate between values, which may cause problems for your "hard border". If the number of hard borders is small (one or two) it may be more efficient to just split at that and then do a parametric function.

increasing resolution of the colormap

.. How large is this colourmap anyway?

• It should run on the cpu. The colormap size is differnt, if you mean like we do it in our company it can be about 4000 elements sometimes, which equates to 4000*4 bytes = 16kB to hold in memory. Most of them will point to the same color which means it's really not optimized. Oct 25, 2023 at 12:11

In a comment, you wrote

which equates to 4000*4 bytes = 16kB to hold in memory. Most of them will point to the same color which means it's really not optimized

If entire ranges of the colormap are the same color, you can use a jagged array, like this:

int i = static_cast<int>(x*(colormap.size()-1))
RGBA a = colormap[i >> 5][i & 31]

The first lookup gives you a pointer to the sub-colormap. Multiple pointers may point to the same submap, which reduces the overall memory footprint and keeps the entire thing in L1 cache. Of course, this optimization only works if many submaps are the same and can be replaced by a single instance.

Here is a tiny example where the benefits are marginal to non-existent.

// flat map
int[] colormap = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }
// jagged array with partial re-use
int[][] maps = {{ 1, 1, 1, 1 }, { 1, 1, 2, 3 }, { 4, 5, 5, 5 }, { 5, 5, 5, 5 }}
int[][] colormap = { &maps[0], &maps[0], &maps[0], &maps[1], &maps[2], &maps[3], &maps[3] }
• I also thought about submaps... in that case we could also opt for fragmented and interpolated submaps in an interchangeable way. However, the submaps are usually not the same size. Oct 25, 2023 at 14:48