[cairo] Color cube stuff for pseudo-color support

[Bill Spitzak]

Keith Packard wrote:
> On Fri, 2008-02-29 at 20:01 -0800, Bill Spitzak wrote:
> 
>> 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.
> 
> You don't want to fill the default colormap; most other applications
> will fail. But, you don't want to allocate too few colors as your
> application will look terrible. So, you want to pick a 'reasonable'
> number of pixels to use and hope that most applications will end up
> sharing them.

Yes you are right. The color cube should use a good deal less than 256 
colors so you do not fill the server's colormap. The fltk one was 5x8x5 
due to compatibility with Irix but probably even 5x5x5 would work.

> Oh, one other thing is that we'll want to support static color as well.
> Static color turns out to be a lot better than pseudo color as the X
> server will allocate a reasonable color cube and gray ramp, allowing
> everyone to share nicely.

Indeed the fltk scheme also worked for static color. It filled in each 
entry in the desired color cube with the closest color in the static 
map. The advantage is that the code to turn the color in the image into 
the nearest color cube entry could remain hard-coded rather than having 
to vary depending on the server.

>> 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.
> 
> You can't tell which pixels are allocated or free, and you can't tell
> which pixels are read-only or read-write. The only way you can tell is
> to allocate the color in the cell and check which pixel value is
> returned.

I didn't explain that clearly, it does call XAllocColor with the color 
again. Here is what it really does, including my comments about why it 
is doing what it does:

   XColor xcol = my_cube[index];
   if (!XAllocColor(...,&xcol)) {
     call_XFreeColor[index] = true;
     // Failed, read the colormap so we can search it:
     // I only read the colormap once.  Again this is due to the slowness
     // of round-trips to the X server, even though other programs may
     // alter the colormap after this and make decisions here wrong:
     if (i_didnt_read_it_yet) {
       i_didnt_read_it_yet = false;
       XQueryColors(...) // get it into map
     }
     xcol = find_least_squared_match(c,map);
     // It appears to "work" to not call this XAllocColor, which will
     // avoid another round-trip to the server.  But then X does not
     // know that this program "owns" this value, and can (and will)
     // change it when the program that did allocate it exits:
     if (!XAllocColor(..., &xcol)) {
       // However, if that XAllocColor fails, I have to give up and
       // assumme the pixel is ok for the duration of the program.  This
       // is due to bugs (?) in the Solaris X and some X terminals
       // where XAllocColor *always* fails when the colormap is full,
       // even if we ask for a color already in it...
       call_XFreeColor[index] = false;
     }
     // record what color was used:
     actual_cube[index] = color_from(xcol);
   }

> Using error-diffusion produces a good result with simple images, but
> when doing incremental rendering, it's important to use an ordered
> dither so you get reproducible colors. However, its easier (and a lot
> faster) to just pick the nearest available color. For many applications,
> nearest color works better than a dither in any case -- line art and
> other simple graphics isn't great looking with dithers. As we have no
> API for controlling this activity (nor do I suggest we add one), we
> should pick a method which generates the best overall look for simple
> applications using text and plain graphics. Nearest fits this
> requirement well.

Nearest color works pretty badly for antialiasing and gradients, 
however. Maybe having the setcolor api actually act like the nearest 
solid color was chosen, so that those areas are not dithered (provided 
the dithering algorithm is something smarter than what I used, which 
will dither an error on the left right across the solid area as 
alternating colors).

Random dither does produce different patterns depending on the area 
being updated but I have not found this to be a problem (for instance 
the fltk color chooser updates only a tiny square as you drag it around 
in the hue selector area, but the dithering pattern still looks quite 
reasonable and there is no visible "trail").

> And, dithering only works if cairo was doing all rendering locally and
> just using PutImage to transmit the finished result.

I was under the impression that this is the *only* possible way to 
implement Cairo, which is why I saw no problem with using dither.

> The pseudo color code in the Render extension is not this clever, but
> does handle random spacing of colors in the colorspace -- the color cube
> and ramp just select a good set of colors while the RGB->pixel mapping
> chooses the closest pixel to each color.

Yes I was just proposing this as the best method I could figure out for 
speeding this up. Correct RGB->pixel mapping for an unknown set of 
colors would require a search for every pixel, or a 256^3 entry table, 
and would be ridiculously slow.