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.netkaufman@polya.STANFORD.EDU (Marc T. Kaufman) (04/09/88)
In article <3184@coherent.com> dplatt@coherent.com (Dave Platt) writes:
.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.
.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.
. 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.
Try the following: Draw into an offscreen PixMap, using 8 colors (the
imagewriter CLUT) in a 4-bit deep Map. While the offscreen device is
active, let Quickdraw generate the color pixpat, using the CLUT you have
provided. This should yield 4-bit pixels with one bit each of R,G,B (and
one bit unused).
Save this PixMap, and scan it to the Imagewriter driver, doing a SetForeColor
every time the pixel value changes. (grubby, but it probably will work).
[I posted this to mac.programmer only, as the comp.graphics people probably
have a better way :-)]
Marc Kaufman (kaufman@Polya.stanford.edu)limes@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
bayes@hpfcdc.HP.COM (Scott Bayes) (04/27/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 The solution we use in the Series 300 under Pascal Workstation OS is proprietary, so I can give you the method but not the code. (When I say add x to y, I mean add red component of x to red component of y, green of x to green of y, and blue of x to blue of y, storing result in y. Rx is shorthand for "red component of x".) We work only in RGB, not in HSL. Create two color vectors, RGB and rgb. Initialize RGB to R=0,G=0,B=0. Initialize rgb to r=0,g=0,b=0. "Desired color" means the RGB color you wish to approximate. Now do 4 times: Add desired color to RGB find clut entry x such that (Rx+r-R)^2+(Gx+g-G)^2+(Bx+b-B)^2 is minimal remember index of x add x to rgb. rgb is now the closest approximation to RGB available in the clut. It gets a little slow for large cluts (eg 256 entry), but gives very good results, and maps a desired color that's found in the clut to that entry. Scott Bayes bayes@hpfclw