TweetFollow Us on Twitter

June 95 - Custom Color Search Procedures

Custom Color Search Procedures

JIM WINTERMYRE

[IMAGE 066-080_Wintermyre_final1.GIF]

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.)

[IMAGE 066-080_Wintermyre_final2.GIF]

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).

[IMAGE 066-080_Wintermyre_final3.GIF]

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 customcolor search procedures; there can be any number of such procedures installed for a given graphics device. As defined in the Color Manager chapter ofInside 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 TypesrcCopyditherCopySearch Procedure
Macintosh IIci, Apple 8*24 card215783
Macintosh Quadra 800, built-in video82123

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.

[IMAGE 066-080_Wintermyre_final4.GIF]

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

NothingBrute-ForceHash
Machine TypeProcedureProcedureProcedure
Macintosh IIci, Apple 8*24 card832234175
Macintosh Quadra 800, built-in video2369148

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. *

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.1.1 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
CrossOver 14.1.3 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
Little Snitch 3.5.3 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
OmniGraffle Pro 6.2.3 - Create diagrams,...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
OmniFocus 2.2 - GTD task manager with iO...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more
Cocktail 8.4 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
PDFKey Pro 4.3 - Edit and print password...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Kodi 15.0.beta1 - Powerful media center...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more

Moleskine Timepage – Calendar for iCloud...
Moleskine Timepage – Calendar for iCloud, Google & Exchange 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: The most elegant calendar for your pocket and wrist, Timepage is a... | Read more »
QuizUp Gets Social in its New Update
Plain Vanilla Corp has released a new and improved version of their popular trivia game, QuizUp. The app now emphasizes social play so you can challenge friends from all over the world. [Read more] | Read more »
The Deep (Games)
The Deep 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Swipe Controls Delve into the deep in this retro rogue-like! Swipe to move your diver around and keep away from the enemies as you... | Read more »
Battle of Gods: Ascension (Games)
Battle of Gods: Ascension 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: TURN-BASED TACTICAL COMBATFight tactical battles against the forces of Hades! In Battle of Gods: Ascension you play... | Read more »
Shadowmatic's Latest Update Adds a...
Shadowmatic's shadowy shadow-ness is getting a little shadowy-er thanks to a recent update that adds an Arcade Mode. [Read more] | Read more »
Sunrise Calendar and Slack Have Assimila...
Wunderlist is perhaps one of the most populat and beloved productivity apps on the App Store - and now it's gone and incorporated itself into other useful services like Sunrise Calendar and Slack. [Read more] | Read more »
Crossy Road Devs Hipster Whale are Bring...
Hipster Whale, the minds behind the rather popular (and rather great) Crossy Road, have teamed-up with Bandai Namco to create PAC-MAN 256: an absolutely bonkers looking maze runner chaser thing. | Read more »
Meet the New Spotify Music
Spotify Music  has a lot going on. They're introducing 3 new modes to serve all your musical needs, with the "Now" start page  gives you curated playlists based on your particular tastes. As you listen the app will learn more about your tastes and... | Read more »
What the Apple Watch Gets Right, and Wha...
| Read more »
Celebrate PAC-MAN's 35th Birthday W...
BANDAI NAMCO Entertainment America is celebrating PAC-MAN's 35th anniversary by releasing updates for PAC-MAN and PAC-MAN Lite for iOS. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
What Would the ideal Apple Productivity Platf...
For the past four years I’ve kept a foot in both the Mac and iPad camps respectively. my daily computing hours divided about 50/50 between the two devices with remarkable consistency. However, there’... Read more
PageMeUp 1.2.1 Ten Dollar Page Layout Applica...
Paris, France-based Softobe, an OS X software development company, has announced that their PageMeUp v. 1.2.1, is available on the Mac App Store for $9.99. The license can be installed on up to 5... Read more
Eight New Products For USB Type-C Application...
Fresco Logic, specialists in advanced connectivity technologies and ICs, has introduced two new product families targeting the Type-C connector recently introduced across a number of consumer... Read more
Scripps National Spelling Bee Launches Buzzwo...
Scripps National Spelling Bee fans can monitor the action at the 2015 Spelling Bee with the new Buzzworthy app for iOS, Android and Windows mobile devices. The free Buzzworthy app provides friendly... Read more
13-inch 2.5GHz MacBook Pro on sale for $120 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $979 including free shipping plus NY sales tax only. Their price is $120 off MSRP, and it’s the lowest price for this model (except for Apple’... Read more
27-inch 3.3GHz 5K iMac on sale for $1899, $10...
B&H Photo has the new 27″ 3.3GHz 5K iMac on sale for $1899.99 including free shipping plus NY tax only. Their price is $100 off MSRP. Read more
Save up to $50 on iPad Air 2, NY tax only, fr...
B&H Photo has iPad Air 2s on sale for up to $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469 $30 off - 64GB iPad Air 2 WiFi: $549.99 $50 off - 128GB iPad... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
New 13-inch 2.9GHz Retina MacBook Pro on sale...
B&H Photo has the 13″ 2.9GHz/512GB Retina MacBook Pro on sale for $1699.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price for this model from... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Watch SW Application Project Manager...
**Job Summary** The Apple Watch software team is looking for an Application Engineering Project Manager to work on new projects for Apple . The successful candidate Read more
Engineering Manager for *Apple* Maps on the...
…the Maps App Team get to take part in just about any new feature in Apple Maps, often contributing a majority of the feature work. In our day-to-day engineering work, we Read more
Senior Software Engineer - *Apple* SIM - Ap...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Lead *Apple* Solutions Consultant - Retail...
**Job Summary** Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.