[cairo] Color cube stuff for pseudo-color support

[Bill Spitzak]

What FLTK did that worked pretty well:

1. Pick a color cube that your code will (mostly) assume exists. This 
allows conversions from actual colors to cube entries to be hard-coded 
and very fast. Make an array to hold the color indexes for each entry in 
the cube, and another array to hold the *actual* color for each entry in 
the cube.

2. Try to allocate all the colors in the cube. If you get a color, put 
it into the array at that location. Allocate the corners of the cube 
first, then widely spaced values through it.

3. If a color fails, then read the colormap from the server, and find 
the nearest color to the color you want. Pretend you allocated that 
color and write it into the array. Don't bother allocating any more 
colors, just keep finding them in this colormap, as the roundtrip to 
read the map each time is slow.

The result is that you end up with something that sort-of resembles your 
desired color cube, but all the colors are allocated.

4. To dither an image to put onto the display, find in your *planned* 
color cube the nearest color (this should be simple). This is the color 
you will draw on the screen, it may not be exactly the desired color (it 
may not even be the nearest color), but it will be close. You then 
subtract the *actual* color from the color you wanted to draw. This is 
the error value, which you then distribute around as an error-diffusion 
value (fltk just dumped all the error on the pixel to the right but this 
should work with any error diffusion method).

This worked when run at the same time with a number of other programs 
that purposely allocated different sizes of cubes, or filling the 
colormap with random colors. It also worked on less than 8-bit visuals 
despite the color map seeming to require more colors than would fit.

Keith Packard wrote:
> So, you want to allocate a color cube. And you want to share it among
> multiple applications.
> 
> Sharing is only possible if everyone allocates exactly the same colors
> using read-only pixels. But, you can only allocate one read-only pixel
> at a time. So, you don't get to know up-front how many colors you can
> allocate. Yay!
> 
> What you can do is allocate a pile of pixels read-write, then free them
> when you know how many pixels are available. Yuck, but it will work. The
> code for doing this work is available in the xstdcmap client. 
> 
> The second trick here is figuring out whether some other cairo
> application has already allocated a suitable color ramp. You can't use
> the read-write trick as you won't align with other cairo applications.
> And, allocating colors read-only will make fail-over to smaller cube
> very expensive.
> 
> Here's my suggestion (untested). Use a root window property to indicate
> what kind of color cube has been allocated. If that property is present,
> just allocate the indicated colors one at a time (read-only). If that
> fails, free the allocated colors, then use the read-write trick to
> figure out how much space is free in the colormap and reset the property
> to indicate what color cube was successfully allocated.
> 
> As to the precise colors to use, Render uses a fairly small cube, and a
> gray ramp. The ramp helps provide extra resolution when drawing text;
> the cube provides fairly minimal color coverage. The allocation code has
> a 'size' parameter which limits how many colors will be allocated.
> 
> I'd say that the colormap stuff should probably be done with the server
> grabbed or you'll probably have terrible race problems.
> 
> The X server has a fairly inefficient mechanism for translating from RGB
> value back to pixel value. It constructs, in the most obvious way
> possible, a 3-dimensional array that maps a sub-set of the bits in each
> component back to the closest pixel value allocated. While the mapping
> is obviously fast, the construction of the array is not. A non-quadratic
> mechanism is clearly necessary when it will be executed at each
> application startup.
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://lists.cairographics.org/mailman/listinfo/cairo