June 95 - Custom Color Search Procedures
Custom Color Search Procedures
JIM WINTERMYRE
Color QuickDraw can be customized for specific tasks in many ways, most commonly
by replacing the "bottleneck" procedures at its heart. But another, often overlooked
way of customizing Color QuickDraw is by writing and installing custom color search
procedures. These procedures are very useful for color separation and other color
processing tasks, and for modifying QuickDraw's default drawing behavior to solve
particular problems. This article reviews some Color QuickDraw basics, explores how
color search procedures work, and presents a sample search procedure.
It's 2 A.M., and you're finally ready to draw your carefully constructed offscreen GWorld to a
window. The GWorld is 32 bits deep and has been set up to contain a color ramp using 100 shades
of red. You've already created a palette containing the 100 shades of red you need and attached it to
your window, so the exact colors will be available on your 256-color screen. You plunk in your call to
CopyBits, recompile, and . . . Ack! Instead of the expected smooth red ramp, you get an image with
16 distinct bands of color (see Figure 1 on the inside back cover of this issue).
What happened? How can you get the results you want? This article attempts to answer both of
these questions, and a few others along the way. What happened has to do with the way Color
QuickDraw converts colors to pixel values, so we'll start with a brief review of how this works. As for
getting the results you want, one way is to use a custom color search procedure, which is the main
subject of this article.
A QUICK REVIEW OF COLOR IN QUICKDRAW
Before delving into custom color search procedures, let's pause for a quick review of how QuickDraw
converts between colors and pixel values. If you're already familiar with this, feel free to skip ahead to
the section "Drawbacks of Inverse Tables."
How QuickDraw converts colors to pixel values and vice versa is discussed in Inside Macintosh: Imaging
With QuickDraw , and in the Color Manager chapter of Inside Macintosh: Advanced Color Imaging
(available on this issue's CD in draft form). Only a brief overview of this complex topic is provided
here.*
DIRECT AND INDEXED COLOR
When an application does any drawing with Color QuickDraw, the ultimate result is to change some
pixel values in a pixel map somewhere. Color QuickDraw in System 7 (and 32-Bit QuickDraw in
earlier systems) supports two distinct types of color pixel maps:direct and indexed .
In direct pixel maps (those with pixel depths of 16 or 32 bits) the pixel values in memory specify RGB
color information for the pixel directly. For example, the 32-bit direct pixel value $00AABBCC
specifies a red component of $AA, a green component of $BB, and a blue component of $CC -- 8
bits of color information each for the red, green, and blue components. (A 16-bit pixel value contains
5 bits of color information for each component.)
Figure 2. Indexed color
In indexed pixel maps (those with pixel depths up to 8 bits) the pixel values in memory don't directly
specify the colors at all; instead they specify positions in a table of the available colors, called thecolor
lookup table or just color table (sometimes called aCLU T ). Figure 2 shows an example; in this case, the
8-bit pixel value $1C in memory actually represents the RGB color $AAAA BBBB CCCC, found at
position $1C in the color table.
Typically, when an application wants to draw in a particular color, it specifies the desired color
directly using an RGBColor record, and never deals with pixel values at all. Color QuickDraw and
the Color Manager convert between RGBColors and pixel values as needed. If the application is
drawing to a direct pixel map, the color information itself is used to build the pixel value, and no
color table is involved. On the other hand, if the application is drawing to an indexed pixel map,
Color QuickDraw uses the index of the closest-matching color in the color table as the pixel value
(this process is calledcolor mapping ). But searching the entire color table for a match every time a
pixel value is needed would be far too time-consuming, so the Color Manager uses something called
an inverse table to speed up the lookup process.
INVERSE TABLES
An inverse table is something like a "reverse" color table: whereas a color table is used to convert an
index to a color, an inverse table is used to convert a given color to an index into a color table. The
conversion operation goes like this: You take some of the most significant bits of each color
component and concatenate them, then use the resulting number as an index into the inverse table.
The entry at that location in the inverse table holds, in turn, the index of the closest-matching
available color in the corresponding color table. Figure 3 illustrates the process. Note that the
closest-matching color returned by this process need not match the original color exactly, since only
a few of the most significant bits were used (the default is 4 bits).
Figure 3. Inverse table with 4-bit resolution
Inverse tables are described in the Color Manager chapter of Inside Macintosh: Advanced Color
Imaging. *
The number of bits each color component contributes to the inverse-table index is called theresolution of the inverse table. Higher resolutions would give you greater accuracy in color mapping,
but also greatly increase the memory needed to hold the inverse table, so a maximum of 5-bit
resolution is allowed. (Since there are three color components, each additional bit of resolution
multiplies the size of the table eightfold.) You can use the Color Manager routine MakeITable to
create inverse tables with resolutions of 3, 4, or 5 bits per component.
As an aside, Listing 1 shows how to temporarily change the resolution of the current graphics
device's inverse table to 5 bits. (To permanently change the inverse table resolution, set the
gdResPref field of the GDevice record, set the iTabSeed field of gdITable to the result of
GetCTabSeed, and call GDeviceChanged.)
Listing 1. Temporarily changing the resolution of the inverse table
VAR
gdh: GDHandle;
oldITabRes: INTEGER;
{ Get current graphics device. }
gdh := GetGDevice;
{ Get resolution of current inverse table. }
oldITabRes := gdh^^.gdITable^^.iTabRes;
{ Create a new inverse table at 5-bit resolution. }
MakeITable(NIL, NIL, 5);
{ Draw into a port on this device. }
...
{ Reconstruct inverse table at original resolution. }
MakeITable(NIL, NIL, oldITabRes);
Note that inverse tables aren't found in pixel maps or color graphics ports. They're instead associated
withgraphics devices (astute readers may have noticed that the color table in Figure 3 was labeled
"Graphics device color table" -- this is why). So when converting RGBColors to indexed pixel
values, the Color Manager uses the inverse table in thecurrent graphics device . The implications of this
are discussed in "The Importance of the Current Graphics Device."
DRAWBACKS OF INVERSE TABLES
The main problem with using inverse tables for color mapping is that because of their limited
resolution, different colors can map to the same inverse table index. Inverse tables actually include
some extra, undocumented information to allow the Color Manager to resolve such "hidden colors"
-- but examining this extra information is time-consuming, so some speed-sensitive QuickDraw
routines don't always use it. One of these routines happens to be CopyBits, which is what accounts
for our "100 shades of red" problem.
Let's look at the problem in more detail. The offscreen GWorld holding our image is 32 bits deep,
allowing the pixel values to specify RGB colors directly, with a precision of 8 bits per component.
When we copy the image to a window on an indexed graphics device, CopyBits uses an inverse table
to convert these pixel values from direct to indexed. If our inverse table has a resolution of 4 bits (the
default), it can only distinguish 24 = 16 shades of red! (For example, all shades of red from RGB
$0000 0000 0000 to $0FFF 0000 0000 will map to the same inverse-table index.) Soeven if all 100
shades are available in the destination device's color table, only 16 of them will actually be found and get
drawn on the screen. This is why the actual result in Figure 1 has 16 bands of red instead of a
continuum of shades.
The various depth conversion cases are discussed in the book Programming QuickDraw (see "Related
Reading" at the end of this article) beginning on page 338. *
One way to deal with this problem would be to increase the resolution of the inverse table to 5 bits,
which would give us 32 bands of red instead 16. Another approach would be to use the ditherCopy
transfer mode in CopyBits. Both of these methods give better results but don't really solve the
problem. After all, since wedo have all the shades of red available, shouldn't there be some way to
match the colors exactly?
INTRODUCING COLOR SEARCH PROCEDURES
Knowing that inverse tables might not be adequate for some applications, the QuickDraw engineers
designed in a "hook" to allow developers to provide their own color-mapping code. Each GDevice
record has its own linked list of custom
color search procedures; there can be any number of such
procedures installed for a given graphics device. As defined in the Color Manager chapter of
Inside
Macintosh: Advanced Color Imaging , a search procedure has the following interface:
FUNCTION SearchProc
(VAR rgb: RGBColor; VAR position: LONGINT): BOOLEAN;
The rgb parameter is now always a VAR parameter. This was not true for direct-color destinations in 32-
Bit QuickDraw prior to System 7. Also, note that Inside Macintosh Volume V incorrectly declared rgb as a
value parameter.*
The Color Manager calls the search procedure with the RGB color it's trying to match, and expects
the search procedure to do one of three things:
- Match the color -- In this case, the search procedure returns thepixel value for the
color in the position parameter, and a result of TRUE. On an indexed graphics
device, the position parameter should contain the index of the appropriate color
in the graphics device's color table. On a direct graphics device, this parameter
should be set to the appropriate direct-color value.
- Modify the color -- In this case, the search procedure modifies the rgb parameter
and returns a result of FALSE. Color QuickDraw ignores the position parameter.
See the next section for examples of using this technique.
- Do nothing -- In this case, the search procedure simply returns a result of
FALSE, leaving its parameters untouched.
The Color Manager runs through the list of search procedures for the current graphics device,
calling each procedure in turn until one of them returns TRUE. If no search procedure returns
TRUE, it uses the default color-mapping method on the original (or possibly modified) color. For
indexed graphics devices, this means using the inverse table. For direct graphics devices, "color
mapping" simply involves truncating the RGBColor components to the appropriate size.
When called with an arithmetic transfer mode, CopyBits calls custom color search procedures before the
arithmetic operation is performed. You can get around this by doing the desired operation first and then
installing the search procedure and using CopyBits with srcCopy mode to display the result. *
The search procedure mechanism provides a solution to our "100 shades of red" problem. If we
know where all the shades are located in the current graphics device's color table, we can write a
search procedure that returns the correct index for any shade of red we pass to it. This will avoid the
bands shown in the actual result in Figure 1 and instead produce the expected result, with the exact
colors intended. Of course, this technique can be applied toany image if we know where to find all
the colors we need in the color table; we'll examine the technique in more detail later.
MODIFYING SEARCH COLORS
The fact that the desired color is passed to the search procedure through a variable parameter is
significant: it means that the procedure can actually modify the color value it receives. In this case,
the search procedure should return FALSE, telling QuickDraw to perform the default color mapping
on themodified color. This technique opens up several possible uses for search procedures.
One such application is color separation for three-color printing. The snippet called SearchProcs &
Color Separation on this issue's CD shows how to do this. To separate all the greens from an image,
for instance, you could install a search procedure that sets the red and blue RGB components to 0.
Listing 2 shows a simple example.
Listing 2. Search procedure to separate green colors
FUNCTION GreenSepProc (VAR rgb: RGBColor; VAR position: LONGINT):
BOOLEAN;
BEGIN
WITH rgb DO
BEGIN
red := 0; { Set red and blue RGB components to 0, }
blue := 0 { keeping only the green component. }
END;
GreenSepProc := FALSE
END;
A similar search procedure could be used to darken or lighten an image. For example, you could use
the code in Listing 3 to darken the blue component of an image by a factor of 2.
Listing 3. Search procedure to darken the blue component
FUNCTION DarkenBluesProc (VAR rgb: RGBColor; VAR position: LONGINT):
BOOLEAN;
BEGIN
rgb.blue := BSR(rgb.blue, 1); { Shift right to divide by 2. }
DarkenBluesProc := FALSE
END;
WHAT'S THE CATCH?
As usual, you do pay a price for all this functionality: search procedures definitely slow down the
drawing process. Just how badly depends on several factors. In the
case of CopyBits, the speed is most directly affected by the depth of the source and destination pixel
maps. If the source pixel map uses indexed color, the search procedure needs to be called only once
for each color in the source map's color table. For direct color, it must be called forevery pixel!
Consider the very simplest search procedure -- one that just returns FALSE without doing anything:
FUNCTION NothingSearchProc (VAR rgb: RGBColor;
VAR position: LONGINT): BOOLEAN;
BEGIN
NothingSearchProc := FALSE
END;
(A search procedure that did nothing but return TRUE would actually be faster, but would be
useless, since the value in the position parameter would be garbage; returning FALSE ensures that at
least normal color mapping will take place.) Table 1 compares the speed of a CopyBits operation
with and without this search procedure, along with the speed of using the ditherCopy transfer mode
in place of srcCopy. The source image is the one shown in Figure 1.
Table 1. Influence of search procedure on CopyBits speed
| | | srcCopy With
|
Machine Type | srcCopy | ditherCopy | Search Procedure
Macintosh IIci, Apple 8*24 card | 21 | 57 | 83
| Macintosh Quadra 800, built-in video | 8 | 21 | 23
| |
Note: Speeds are given in ticks, and are for ten successive calls to CopyBits, copying a
100-by-100-pixel, 32-bit-deep image to an 8-bit screen.
As you can see, CopyBits with an installed search procedure runs just a little slower than a dithered
CopyBits. Note that the figures in the table are very rough. Several other factors contribute
significantly to the speed difference when a search procedure is installed, such as the size of the
source image and the number of colors it contains. You'll also get different results depending on
what drawing routines you call with the search procedure installed. But the "dithered CopyBits" rule
of thumb seems to work quite well as a general guide.
It's up to you to decide whether the speed penalty for using a custom color search procedure is worth
the improved display quality. For image-processing applications, where color accuracy is probably
more important than speed, search procedures can be very useful; for applications such as arcade-
style video games, which depend on real-time graphics, they're probably not the way to go.
SOLVING THE "SHADES OF RED" PROBLEM
It's very common these days for applications to prepare an image offscreen, using a 32-bit GWorld,
before transferring it to the screen for display. Despite the decreasing cost of 24-bit graphics cards,
indexed 8-bit color is still a very common configuration, and even users with direct color capability
spend a lot of time in 8-bit mode, which can lead to anomalies like the "100 shades of red" problem.
As mentioned earlier, we can use a custom color search procedure to draw direct pixel images into
indexed graphics devices with exact color reproduction, provided that all of the colors are actually
available in the destination device's color table.
The way to make the colors available on the device is of course to use the Palette Manager, attaching
a palette of the needed colors to the window you're drawing in. (This works only if other applications
aren't "hogging" too many colors.) Getting the right colors from a picture or pixel map won't be
discussed in any detail here, but the sample code uses the octree method described in the article "In
Search of the Optimal Palette" indevelop Issue 10. It's probably easier to use the built-in popularand
median color-sampling methods, but they truncate colors to 5 bits per component,meaning that they
won't return separate palette entries for colors that differ only in the lower bits, as our shades of red
do. The octree method doesn't truncate the colors, so it can be used to findall the colors in the
image (assuming the image contains fewer than 256 colors). Another approach is demonstrated in the
snippet CollectPictColors on the CD. Once the colors are available, we can write a search procedure that simply searches the graphics
device's color table and returns the index of the requested color. (If the color table doesn't contain all
the needed colors, the search procedure may have to return FALSE; QuickDraw will then use the
inverse table to map these colors, which can lead to unexpected results. See the section "Evaluating
the Results," later in this article, for more on this.)
THE BRUTE-FORCE APPROACH
In true hacker fashion, let's try the brute-force approach first: we can simply scan straight through
the current graphics device's color table and stop when we find a match. Listing 4 shows the code.
Listing 4. Brute-force search procedure
FUNCTION BruteSearchProc (VAR theRGB: RGBColor;
VAR position: LONGINT): BOOLEAN;
VAR
i: INTEGER;
gdh: GDHandle;
colorTab: CTabHandle;
BEGIN
{ Get handle to current device. }
gdh := GetGDevice;
{ Get color lookup table from current device. }
colorTab := gdh^^.gdPMap^^.pmTable;
{ If the color table exists, loop through all its entries until }
{ we find a match. }
IF colorTab <> NIL THEN
WITH colorTab^^ DO
FOR i := 0 TO ctSize DO
WITH ctTable[i] DO
IF (theRGB.red = rgb.red) &
(theRGB.green = rgb.green) &
(theRGB.blue = rgb.blue) THEN
BEGIN
{ We found the color, so pass back its }
{ index and return TRUE. }
position := i;
BruteSearchProc := TRUE;
EXIT(BruteSearchProc)
END;
{ We didn't find the color in the table, so return FALSE to }
{ tell QuickDraw to use the default mapping method. }
BruteSearchProc := FALSE
END;
If we install this search procedure and draw the "100 shades of red" image, it will
find all 100 shades and produce the expected image. Unfortunately, it'svery slow: a CopyBits with
srcCopy mode using this search procedure takes 30 to 40 times as long as a dithered CopyBits.
HASH TABLES: A BETTER WAY
We can speed up our search procedure by using a hash table instead of a brute-force linear search.
(Hash tables are familiar to most of you from basic computer science classes, and are described in any
good book on algorithms, such asAlgorithms by Robert Sedgewick.) In our case, we'll use the RGB
color value as a hash key to find the corresponding color table index. For our hash function, we'll use
the MOD operator to find the remainder of the hash key relative to some suitably chosen prime
number. The bigger we make this prime number, the better the performance of the hash function
will be. Assuming that the target device uses 8-bit indexed colors (for most images, any lower color
depth will yield a color table too small to hold all thecolors we need), we'll be working with a color
table of 256 colors. We'll choose 251, a prime number near 256, as the divisor for our hash function.
The MODoperator can't operate directly on 48-bit RGBColor records, so we'll use the high-order 8
bits of each color component to form a 32-bit integer of the form $00rrggbb (the same as a 32-bit
pixel value) and use that for our key into the hash table.
Figure 4 shows the data structure containing our hash table. RGBHashArray is a zero-based array of
records of type RGBHashNode. Each node holds a 32-bit color value (rgbComp), along with the
index at which that color is stored in the color table. Nodes whose colors map to the same hash value
are chained together in a linked list, with each node'snextfield holding the array index of the next
node in the chain (this collision resolution method is calledseparate chaining ). The first
kPrimeRecords (251) entries in the hash array hold header nodes for all possible hash values; these
point into the rest of the array, which holds the data nodes themselves.
Figure 4. Hash table data structure
The data structure definitions for our hash table are shown in Listing 5. In addition to the array
holding the table's contents, there's a short header containing the index of the next available data
node along with the color table'sseed value at the time the hash table was built. We can use the latter
to keep our hash table synchronized with the color table. Any time QuickDraw changes the contents
of the graphics device's color table, it also changes its seed value. Thus if the seed values in the hash
table and color table don't match (as checked by the routine in Listing 6), we know the color table
has been changed and we need to rebuild our hash table before using it.
Listing 5. Hash table data structures
CONST
kNumRecords = 256; { Number of colors in color table }
kPrimeRecords = 251; { Number of hash entries }
kTableSize = kPrimeRecords + kNumRecords - 1;
{ Total size of (zero-based) hash array }
TYPE
RGBCompressedColor = LONGINT;{ Color in 32-bit form ($00rrggbb) }
{ Data structure for hash table nodes }
RGBHashNode = RECORD
rgbComp: RGBCompressedColor;
{ RGB color in compressed form }
index: INTEGER; { Index of matching color in }
{ color table }
next: INTEGER { Array index of next node in list }
END;
{ Data structure for array to store hash table data }
RGBHashArray = ARRAY[0..kTableSize] OF RGBHashNode;
{ Data structure for hash table itself }
RGBHashTable = RECORD
nextEntry: INTEGER; { Array index of next unused data node }
curCTabSeed: LONGINT; { Value of color table seed when hash }
{ table was created (indicates when }
{ hash table must be updated) }
table: RGBHashArray { Hash table contents }
END;
RGBHashTablePtr = ^RGBHashTable;
VAR
gRGBHash: RGBHashTablePtr; { Global hash table pointer }
Listing 6. Checking the validity of the hash table
FUNCTION HashTableNeedsUpdate (ctab: CTabHandle;
rgbHash: RGBHashTablePtr): BOOLEAN;
BEGIN
HashTableNeedsUpdate := ctab^^.ctSeed <> rgbHash^.curCTabSeed
END;
There are two straightforward procedures, not shown here, for initializing the hash table and for
clearing it out before building or rebuilding its contents (see the code
on the CD for details). RGBHashInit zeroes out the entire hash table, while RGBHashClear clears
only the list headers, making the table appear empty; there's no need to zero the data nodes
themselves.
The procedure for inserting a color into the hash table is shown in Listing 7. It starts by doing some
bit manipulation to convert the RGBColor to 32-bit form. It then uses the result to compute the
hash-table index for the given color by finding its remainder modulo 251. Next, it fills in the fields of
the next available hash node and inserts it at the head of the linked list starting at the computed
index. Finally, it increments the hash table's nextEntry field to point to the next hash node in the
array.
Listing 7. Inserting a color in the hash table
PROCEDURE RGBHashInsert (rgbHash: RGBHashTablePtr; rgb: RGBColor;
cTabIndex: INTEGER);
VAR
compressedRGB: RGBCompressedColor;
hashIndex: INTEGER;
BEGIN
{ Reduce 48-bit RGB value to 32-bit compressed form. }
WITH rgb DO
compressedRGB := BSL(BAND(red, $0000FF00), 8) +
BAND(green, $0000FF00) + BSR(BAND(blue, $0000FF00), 8);
{ Compute hash-table index. }
hashIndex := compressedRGB MOD kPrimeRecords;
WITH rgbHash^ DO
BEGIN
{ Store color data in next available node. }
WITH table[nextEntry] DO
BEGIN
rgbComp := compressedRGB;{ Actual RGB color }
index := cTabIndex; { Index in color table }
{ Insert this node at front of linked list. }
next := table[hashIndex].next;
table[hashIndex].next := nextEntry
END;
{ Update to next available node. }
nextEntry := nextEntry + 1
END
END;
Building a hash table from the current graphics device's color table is relatively straightforward
(Listing 8). First we save the state of the color table handle and lock it in case we do something that
moves memory while the handle is dereferenced. (Our code doesn't currently do anything to move
memory, but if we should change it in the future so that it does, this precaution ensures that it will
still work.) Next we call our RGBHashClear procedure to clear the hash table's list headers to empty,
and save thecolor table's seed value so that we can tell when the hash table needs updating. Finally,
we step through the contents of the color table, inserting each color into the hash table with
RGBHashInsert (Listing 7). Then all that's left is to restore the color tablehandle to its original
state, and the hash table is ready for use by our search procedure.
Finally, we get to the real heart of the hash-table search procedure, RGBHashSearch (Listing 9).
First we pack the 48-bit RGBColor value into 32 bits. Next, we computethe hash-table index for the
given color and retrieve the list header for that hash value. If the list is nonempty, we step through it,
comparing the RGB color stored in each node with the color we're looking for. If the colors match,
we get the index of the corresponding color table entry from the data node and return TRUE. If we
don't find the desired color, we return FALSE to indicate that the color was not in the hash table.
Note that this will happen only if the source image contains colors that didn't fit in the color table
(an example of this is given in the next section).
Listing 8. Building the hash table
PROCEDURE CTab2Hash (ctab: CTabHandle; rgbHash: RGBHashTablePtr);
VAR
state: SignedByte;
i: INTEGER;
BEGIN
{ Save state of color table handle and lock it. }
state := HGetState(Handle(ctab));
HLock(Handle(ctab));
{ Clear hash table to empty. }
RGBHashClear(rgbHash);
WITH ctab^^ DO
BEGIN
{ Save current seed value. }
rgbHash^.curCTabSeed := ctSeed;
{ Step through contents of color table. }
FOR i := 0 TO ctSize DO
{ Insert each color into hash table with its index. }
WITH ctTable[i] DO
RGBHashInsert(rgbHash, rgb, i)
END;
{ Restore original state of color table handle. }
HSetState(Handle(ctab), state)
END;
Listing 9. Searching the hash table
FUNCTION RGBHashSearch (rgbHash: RGBHashTablePtr; rgb: RGBColor;
VAR index: LONGINT): BOOLEAN;
VAR
compressedRGB: RGBCompressedColor;
hashIndex: INTEGER;
chainIndex: INTEGER;
nextIndex: INTEGER;
BEGIN
WITH rgb DO
{ Reduce 48-bit RGB value to compressed form. }
compressedRGB := BSL(BAND(red, $0000FF00), 8) +
BAND(green, $0000FF00) + BSR(BAND(blue, $0000FF00), 8);
{ Compute hash-table index. }
hashIndex := compressedRGB MOD kPrimeRecords;
WITH rgbHash^ DO
BEGIN
{ Get array index of first node in list. }
chainIndex := table[hashIndex].next;
WHILE chainIndex <> 0 DO { Loop till end of list. }
{ Is this the color we want? }
IF table[chainIndex].rgbComp = compressedRGB THEN
BEGIN
{ If so, pass back its CLUT index and return TRUE }
index := table[chainIndex].index;
RGBHashSearch := TRUE;
EXIT(RGBHashSearch)
END
ELSE { Otherwise go to the next node. }
chainIndex := table[chainIndex].next;
{ If we got here, either there were no links at this }
{ hash-table address, or we reached the end of the }
{ list. Both cases indicate that the color is not in the }
{ CLUT, so return FALSE. }
RGBHashSearch := FALSE
END
END;
Listing 10 shows how to install our search procedure for use in a drawing operation
(gSearchProcUPP is a universal procedure pointer that points to our search procedure,which is simply
a wrapper that calls RGBHashSearch). The Color Manager routines AddSearch and DelSearch,
respectively, install and remove a search procedure for the current graphics device. Note that we
install our search procedure just before the drawing operations that use it, and remove it immediately
afterward. This is because the search procedure will be called forany drawing that occurs on the
device it's attached to, and can significantly affect performance. Before installing and using our search
procedure, we call our HashTableNeedsUpdate function (Listing 6) to compare the hash table's seedvalue with that in the current color table. The function returns TRUE if the seed values don't agree;
this tells us torebuild the hash table with CTab2Hash (Listing 8) before using our search procedure.
Astute readers may wonder what happens if the drawing area spans more than one screen in a
multiple-monitor configuration, since search procedures "belong" toparticular devices. Our sample
code deals with multiple devices simply by calling DeviceLoopto do its drawing, installing the search
procedure only on 8-bit color devices; on any other devices, CopyBits is called with ditherCopy
mode.
EVALUATING THE RESULTS
Has all this optimization been worth it? Table 2 compares the speeds of the various search
procedures, again using CopyBits in srcCopy mode to copy the image shown in Figure 1 from a 32-
bit offscreen GWorld to an 8-bit device. For comparison, the speed of a "nothing" search procedure
is also shown. Clearly, the work has paid off -- the hash-table search procedure is over 15 times as
fast as the brute-force approach, and is certainly comparable to a dithered CopyBits. In some cases
(for example, when drawing an image in a zoomed-in state), our hash table technique is actually as
fast as (or faster than) a dithered CopyBits.
Although our hash-table search procedure gives impressive results, there are certainly cases where its
performance is less than optimal. The hash table method assumes that all of the colors in the source
image can be loaded into the current graphics device's color table. If this condition doesn't hold, the
search procedure will still work, but it won't be able to find colors that aren't in the color table, so
QuickDraw will use the default inverse-table mapping method for those colors. This can give
unexpected results. For example, Figure 5 (on the inside back cover of this issue) shows a version of
the "Better Bull's eye" image fromdevelop Issue 1 (from the article "Realistic Color for Real-World
Applications"), drawn using the hash-table search procedure.
Listing 10. Installing and removing a search procedure
{ Get color table from current graphics device. }
gdh := GetGDevice;
ctab := gdh^^.gdPMap^^.pmTable;
{ Update hash table if necessary. }
IF HashTableNeedsUpdate(ctab, gRGBHash) THEN
CTab2Hash(ctab, gRGBHash);
{ Install search procedure right before drawing. }
AddSearch(gSearchProcUPP);
{ Example drawing code }
CopyBits(BitMapPtr(thePixMap^)^, myWindow^.portBits, srcRect,
destRect, srcCopy, NIL);
{ Remove search procedure right after drawing. }
DelSearch(gSearchProcUPP);
Table 2. Comparison of search procedure speeds
| Nothing | Brute-Force | Hash
|
Machine Type | Procedure | Procedure | Procedure
Macintosh IIci, Apple 8*24 card | 83 | 2234 | 175
| Macintosh Quadra 800, built-in video | 23 | 691 | 48
| |
Note: Speeds are given in ticks, and are for ten successive calls to CopyBits, copying a
100-by-100-pixel, 32-bit-deep image to an 8-bit screen.
The image in Figure 5 has more than 256 distinct colors. The results may look all right at first
glance, but if we zoom in on the top right corner of the image (Figure 6, also on the inside back
cover), we can see unwanted bands of gray. Some of the actual grays that were supposed to appear at
these locations were not available in the graphics device's color table. As a result, they were color-
mapped to the closest available gray at a 4-bit resolution, resulting in banding.
A similar problem can result if you have several windows displaying different images at once. The
frontmost window will display correctly, but the others may not have the correct colors available.
Usually this isn't important, since the frontmost window is generally the one you're concerned with.
Typically, you should install the search procedure only when drawing in the frontmost window.
Another, more subtle case where our search procedure can give unexpected results is when the
destination rectangle passed to CopyBits is smaller than the source rectangle. If the source image uses
direct color, CopyBits will average the color values of adjacent pixels to produce the reduced image.
This usually gives more visually appealing results than just dropping whole rows of pixels; but in this
case, since averaging can produce colors that aren't in the color table, we run into the same kind of
problem we've been discussing. (There's no problem when the destination rectangle isbigger than the
source rectangle, since CopyBits will simply replicate existing pixels without introducing any new
colors into the image.)
MAKING IT BETTER
Our hash-table search procedure is certainly much more efficient than the brute-force approach, but
it can be improved still further. The most obvious idea would be to reimplement the code in
assembly language for maximum efficiency, although this hampers portability and may not result in
much of a speed improvement, depending on how good your compiler is. Another area for
improvement might be the hashing algorithm itself: wecould try a different hash function or another
method of collision resolution. However,since the hash table in this application is so small, this may
not be worth the effort.
A useful extension would be to find the closest match for colors that arenot in the color table. This
would alleviate the problems that occur when the image has too many colors to fit in the color table.
Abandoning the hash table in favor of a tree-based algorithm might work, but it would be hard to
make it as fast as the hash table method. Another approach might be to use some color-quantization
algorithm to reduce the total number of colors in the image to 256 -- but of course that would mean
changing the actual image data.
NOW IT'S UP TO YOU
Custom color search procedures are one of the least-used methods for customizing Color
QuickDraw. In this article, we've seen several practical uses for them -- now it's up to your creativity
to find others. (Let us know if you do!)
THE IMPORTANCE OF THE CURRENT GRAPHICS DEVICE
An often misunderstood fact about Color QuickDraw is this: Color QuickDraw uses the current graphics
device's color table when converting colors into indexed pixel values, ignoring the color table of the
destination pixel map.
The inverse table is built from the color table in the graphics device's pixel map, not the one in the
destination pixel map. When you're drawing to the screen, this is not a problem, since the destination pixel
map and the current graphics device's pixel map match (the destination pixel map is the device's pixel map).
However, it can be a problem when you're drawing offscreen (for example, when using CopyBits to copy
one offscreen pixel map to another). If the color table of the destination pixel map doesn't match that of the
current graphics device, you won't get the results you expect. The destination pixel map's color table is used
only when converting the other way, from a pixel value to a color (for example, when the pixel map is
actually displayed on the screen).
One of the nice things about using GWorlds for offscreen graphics is that you don't have to worry about this
-- GWorlds always have a graphics device associated with them, and routines such as SetGWorld ensurethat the GWorld's pixel map and the graphics device's pixel map are synchronized for correct color
mapping.
RELATED READING
- Inside Macintosh: Advanced Color Imaging, on this issue's CD in draft form and forthcoming in print
from Addison-Wesley. See the Color Manager chapter.
This is the most thorough documentation in Inside Macintosh for color search procedures and color mapping
with inverse tables. You'll also find some useful information in the Palette Manager chapter.
- Inside Macintosh: Imaging With QuickDraw (Addison-Wesley, 1994), Chapter 1, "Introduction to
QuickDraw," Chapter 4, "Color QuickDraw," Chapter 5, "Graphics Devices," and Chapter 6, "Offscreen
Graphics Worlds."
- Programming QuickDraw by David Surovell, Frederick Hall, and Konstantin Othmer (Addison-Wesley,
1992). Everything you ever wanted to know about QuickDraw. In particular, see "Graphics Devices" in
Chapter 3, "Drawing in Color," and see "Pixel Processing Traps" and "Depth Conversion and Dithering"
in Chapter 7, "Image Processing with QuickDraw."
- "In Search of the Optimal Palette" by Dave Good and Konstantin Othmer, develop Issue 10. How to use
the Picture Utilities Package to obtain a palette with the best colors for displaying an image on an
indexed device.
- Macintosh Technical Notes "Principia Off-Screen Graphics Environments" (QD 13) and "Of Time and
Space and _CopyBits" (QD 21).
JIM WINTERMYRE (Internet winter@ai.rl.af.mil) is in the Air Force but doesn't get to fly a plane; instead, he gets to fly a
Macintosh (he thinks he still deserves hazard pay, though). Officially, he's a Signals Intelligence Systems Engineer, but he
always seems to find himself doing Macintosh programming in one form or another. When he's not busy solving the
world's problems or coming up with another useless hack (the boundaries between the two have become fuzzy lately), he
likes to engage in sports that let him pretend he really does have wheels on his feet. He was recently spotted playing jazz
guitar in a smoky little bar in upstate New York. *
Thanks to our technical reviewers Joseph Maurer, Don Moccia, Guillermo Ortiz, and Nick Thompson. *