Color by Numbers
Color by Numbers
Embedded GUIs are growing more elaborate day by day. Developers now have to contend with such arcana as a color palette.
Before I move on to this column's main topic, I would like to point out that I did Borland C++ Builder a disservice in my October column ("User Interface Prototypes," p. 33). I described an awkward and obscure way to compile all files as C++ files, whether the file name extension is .c or .cpp. Version 6 of the Borland tool, which has been out for several months, now has a check box for this option. Its default behavior is to compile .c files as C and .cpp files as C++, but checking the "Force C++ Compile" option causes all files to compile as C++. Thanks to reader Rob Blansett for pointing this out.
Another reader wanted to know how to pick the ideal set of colors in a color map. I'm going to use this column to respond, since its information with which embedded programmers may not be familiar.
A color map, or palette, maps a small set of values to a set of colors chosen from a larger range. In most color graphics controllers, the palette is implemented in hardware.
Say, for example, that a screen can display 24 bits of color information (224 colors), but the frame buffer can only store eight bits for each pixel. When rendering a pixel, the controller uses the 8-bit value to access a table with 256 entries. Each entry contains a 24-bit color value, which is then rendered. This allows the application to use 256 colors out of a set of 224 (16,777,216) at any one time.
Determining the "best" set of colors was something I had never really thought about before. The obvious answer is to pick 256 values that are evenly spread across the 224 possible colors that the controller offers. Taking this approach, you might be tempted to pick every 65,536th value. While this seems numerically reasonable, it ignores the fact that the 24-bit value is divided into red, green, and blue components. The multiples of 65,536 leave the least significant 16 bits as zero for all values. In a distribution like this, all of the available colors lack any blue or green component; they're all shades of red.
A more reasonable approach would be to break down the color value into its red, green, and blue components, compute four evenly spread values from each, and then produce all combinations. Four values for each component uses two bits per component, which is a total of six bits, leaving two bits over. No symmetric way of distributing those bits exists, but you may have more information as to which range of colors you are likely to use more. The spare values could be used to provide more colors in the frequently used areas.
In practice, the technique just described is rare. The set of colors in the color map can be changed at run time, so it's usually built to match the needs of the moment.
So you could treat the graphical user interface (GUI) as if all 24 bits of color were available, adding a new color to the map whenever it's needed and, when a color is found to be unused, marking the corresponding entry in the color map accordingly. The danger is that, at run time, a display of a particular combination of elements could lead to all 256 slots in the map being occupied. On a PC, where you cannot predict in advance what combination of windows or applications will be active, this is a real restriction, but in many embedded devices the interface is limited, allowing you to establish exactly what combinations are possible.
If this restriction is still too much, many controllers give you the option of storing more bits per pixel in the frame buffer, so if we store 24 bits per pixel, we have no map and no restrictions. The downside is that we need three times as much RAM for the frame buffer that represents the display.
So what do we need all of those colors for anyway? We'd need them to reproduce photographs, or play DVDs, but lots of embedded systems use a GUI that does not require pictures, and instead displays text, buttons, and menus that the user can manipulate.
My own work involves medical devices that display graphs to represent aspects of a patient's condition. While the graphs scroll from right to left, the rest of the display only changes in response to a user action or a patient-triggered event such as an alarm. This kind of interface can be implemented in sixteen colors, so why bother with sixteen million?
Sometimes you need to know a particular color will be available when you need it. Sloped lines often appear jagged when you create them on the display. The jaggedness is usually most noticeable when the line is almost but not quite vertical or horizontal. If you rotate a line slowly through 360 degrees, the jagged edges ripple up and down its sides.
Similar effects occur with circles and with characters generated from a font. To soften those jagged edges, you can use colors in between the foreground color and the background color. This technique, which is called antialiasing, is only effective with a sufficient range of colors between the foreground and background.
The basic approach of antialiasing is to generate the image to be rendered at double the resolution of the final display, as shown in the first square in Figure 1. If the height and width have both been doubled, each pixel of the final display will be represented by four locations in the double resolution version. The second image in Figure 1 shows the double resolution drawing grouped into blocks of four locations. To distill a single value for the final pixel, we average the values of the four locations. The third image in Figure 1 shows the line segment drawn at the final resolution of the display. When magnified to this extent, the softening of the edges is not apparent, but on a real display the effect can be quite impressive.
Figure 1: Antialiasing
The averaging process leads to a color that may not have appeared anywhere else on the display, so we simply use the closest match. The closer the match, the better the antialiasing effect. This is why a display supporting 24-bit color can look better than a display with 256 colors, even if the screen design only requires a small set of colors.
If we don't have enough RAM to draw the image at double resolution, an algorithm based on the same principle can antialias small sections so that the entire image does not have to be rendered at the higher resolution. You can also make use of specialized algorithms for drawing antialiased lines or ellipses.[1,2] These algorithms read the background color of all parts of the line because the shape may cross backgrounds of a different color.
You might think that embedded systems don't often encounter these subtle issues. Users moving from a low-resolution monochrome display might consider any color at all a big step forward. In some applications, however, an embedded GUI has to compete with mechanical controls. In luxury cars, for example, graphical displays are starting to replace mechanical speedometers and tachometers. Because users expect a display that looks like the original dial, not some crude pixilated imitation, smoothing the edge of the needle, along with shadowing and shading, is a vital aspect of the design.
Colors in the Palm of your hand
If you let your marketing department boast about the color capabilities of the device you're selling, be sure not to let them get carried away. Palm was threatened with a class action lawsuit for advertising and selling the M130 as a device capable of over 65,000 colors. Palm now claims that it has 58,621, a reduction of 11%.
When I first saw the complaints against Palm, I thought they were fairly weak, but when you look a bit closer, their real crime is that 58,621 colors figure is not accurate either. Some of the M130's competitors have 16-bit screens. The M130 features a cheaper 12-bit screen and then uses a combination of techniques to get more colors from the display.
One trick is to vary the frame rate to alter the intensity of a color. However this affects the entire screen, so its effect on the number of useful colors is minimal.
The second technique is dithering, which involves using two similar colors to produce an intermediate color. A different color is used on every second pixel. From a distance, the eye will average the two colors used. This technique effectively reduces the resolution of the screen. Dithering was Palm's biggest sin. Since it can be performed from software alone, nothing is stopping someone from applying the technique to a screen that has genuine 16-bit color, thereby achieving even more colors. If we allow dithering to be part of the metric for color depth, all currently advertised color devices or PCs would be able to multiply the number of colors that they claim they can display.
Another problem is that I can download JPEGs to my Palm device from a PC. Some of those pictures may already have been dithered, and double-dithering doesn't work. Dithering is a useful technique, but it must be implemented with an understanding of the capabilities of the final display.
Cheap eval boards?
So why do I care so much about the Palm display? Well, I had a plan to use the Palm as a cheap prototyping platform for an embedded GUI. It has a Motorola Dragonball processor with a built-in LCD controller. The Palm is far cheaper than any of the Motorola evaluation kits, and you get a screen thrown in. My application would not use the Palm OS, but I figured that bypassing it wouldn't be a big deal. It was a nice plan. Unfortunately, the M130 is not flashable, so you can't remove the OS. I could have run my software from RAM, but the timed interrupts would still be fixed in ROM. Since I didn't want any interference from the OS, those interrupts could have been problematic.
I did get the GNU cross compiler and debugger to work for the Palm. The debugger uses the serial link to the Palm's cradle for download and debugging. However, the Palm version of the GNU tools depends on a Palm application for the communications that allow download and debug to work. This application is a replacement for the more common GDB stubs that are used on targets with no OS. Without this debug application, it isn't possible to gain control of the serial port without some involvement from the OS.
Had I managed to get over that hurdle, the next step would have been to derive enough information about how the screen was wired to enable me to configure the LCD controller appropriately. In any case, the fact that the M130 had a 12-bit screen, when I thought it had a 16-bit screen would no doubt have created numerous additional headaches.
Another handheld with flash instead of ROM and a genuine 16-bit screen might have allowed some further progress, but it had become clear that the effort to get the device to work as a GUI development environment outweighed the price difference between a mass produced consumer handheld device and a dedicated evaluation board. I still hope to find a good candidate for a cheap platform for embedded graphics work. If I ever do, I'll let you know. And if you try it with more luck than I had, I expect you to reciprocate.
Niall Murphy has been writing software for user interfaces and medical systems for 10 years. He is the author of Front Panel: Designing Software for Embedded User Interfaces. Murphy's training and consulting business is based in Galway, Ireland. He welcomes feedback and can be reached at firstname.lastname@example.org. Reader feedback to this column can be found at www.panelsoft.com/murphyslaw.
1. Abrash, Michael. Zen of Graphics Programming, Scottsdale, AZ: The Coriolis Group, 1996.
2. Foley, James, Andries van Dam, Steven Feiner, and John Hughes. Computer Graphics: Principles and Practice, Second Edition in C. Reading, MA: Addison-Wesley, 1996.
3. PRC tools is an extension to GCC for the Palm Pilot. www.palmos.com/dev/tools/gcc/