dplatt@coherent.com (Dave Platt) (04/09/88)
Howdy. I'm not sure whether this question is going to fall into the
"10 standard beginners' questions that arise every two months" category
that's been getting so much discussion in comp.graphics... but what the
heck, I'll ask it anyhow.
Background
I'm working on a Mac II application that draws on the screen in color.
Currently, the colors are program-specified, but I plan to add a Color
Picker routine to permit the user to choose any of the colors supported
by Color QuickDraw. The underlying color specifications are 48-bit
(R,G,B) triplets, with each value being specified to 16 bits
precision; the actual video card supports only 8 bits of precision per
color plane, I believe.
I'd like to be able to generate reasonably-accurate hardcopy printouts
of the screen, using an ImageWriter II with a color ribbon. The IW II
supports the old-style Macintosh color model (8 specific colors,
including black and white), but the printer driver doesn't know how to
map Color QuickDraw 48-bit color specifications into the 8-color
model.
In the images that I'm generating (Mandelbrot fractal zooms), there are
some fairly large areas of uniform color. I'd like to use a
color-dithering technique in these areas... printing pixels of
different colors (chosen from those available on the ribbon) so that
the overall color of the area matches the color chosen by the user as
closely as is practical. The Mac II's Color QuickDraw supports a
technique like this for drawing within a color window; one supplies an
(R,G,B) color as input, and receives in return a colored "brush" (a
pattern of 8*8 pixels). Within the "brush", each 2*2 square of pixels
can combine up to 4 of the colors available in the window's color
table, with the "average" color falling reasonably close to the (R,G,B)
input color.
Unfortunately, this capability necessitates that one have a window
available whose color table contains only those colors actually
available for drawing. Printing isn't performed via a color window...
it uses an old-style 1-bit-deep GrafPort, and the Color QuickDraw
routines won't work with it. So, I'll need to construct such a colored
brush myself.
The Problem
Given a color palette of N colors, each of whose (R,G,B) values are
known to a reasonable precision, select a group of 4 of those N colors,
such that the average of these 4 colors' (R,G,B) values falls close to
a specified (R',G',B') color.
Techniques
Apple's documentation doesn't go into any great detail about the
algorithm that Color QuickDraw uses to make its choice of colors.
Apple does state that the algorithm was chosen for speed and reasonable
accuracy, and may not always produce the closest match to the desired
color. I've read a report that the algorithm sometimes doesn't even
product an exact match when the desired color is one that happens to be
in the window's color table... the brush-maker constructs a two-color
brush rather than returning a solid brush of the desired color.
I have a vague suspicion that finding the closest/best match may be a
"difficult" problem: similar to the knapsack problem, and thus
NP-complete. I'd rather not put an exponential-time algorithm in the
critical path of my code!
So... what approaches might I use to construct these colored brushes in
a way that will result in a reasonably close match between the desired
color and a mix of those available, and which won't chew up gobs of
processor time?
[Of course, one could make a good case that even an expensive brush-
blending phase will be a relatively small task compared with
generating a full-screen Mandelbrot image]
Thanks in advance for any suggestions, pointers to good references,
etc. that any of you can make! And, apologies if this turns out to be
a "bonehead Graphics-for-Gradeschoolers" problem that has been
discussed aleph-null times before.
--
Dave Platt VOICE: (415) 493-8805
USNAIL: Coherent Thought Inc. 3350 West Bayshore #205 Palo Alto CA 94303
UUCP: ...!{ames,sun,uunet}!coherent!dplatt DOMAIN: dplatt@coherent.com
INTERNET: coherent!dplatt@ames.arpa, ...@sun.com, ...@uunet.uu.netlimes@sun.uucp (Greg Limes) (04/26/88)
In article <3184@coherent.com> dplatt@coherent.com (Dave Platt) writes: > > The Problem > >Given a color palette of N colors, each of whose (R,G,B) values are >known to a reasonable precision, select a group of 4 of those N colors, >such that the average of these 4 colors' (R,G,B) values falls close to >a specified (R',G',B') color. Much of Dave's posting hacked away ... I have been doing some work on an IBM-PC's EGA adaptor that has run me into this same brick wall, with the slight modification that I have a choice of up to 16 colors from a palette of 64 ... yes, pretty weak, but that is the hardware I have to work with; so, if anyone has any references not only on how to select from the N colors, but also how to select WHICH n colors, post (or email) them also ... -- Greg Limes [limes@sun.com] frames to /dev/fb