Starwave is a Web hosting/publishing company that partners with more traditional publishing houses (eg: those that initially have no presence on the Web) to enable any of their publishers to bring their content to the Web from any number of remote sites, at any time, using a variety of publishing mechanisms.

The majority of this content, such as sports scores, highlights, and statistics (ESPN.com) and breaking news stories (ABCNews.com and ESPN.com), needs to be delivered in real time, which is a major advantage of Web publishing over traditional publishing mediums.

The software developers at Starwave have written a number of server side applications which operate to produce this dynamic, near real-time content for the various content sites that Starwave hosts, operates, and supports.

Figure 1: Polling Output

Due to the extremely high volume of traffic on the servers of such Web sites as ESPN.com and ABCNews.com, the requirements on these applications are extremely rigorous, forcing software developers to make the applications as robust and efficient as possible, utilizing as little of the Web servers already-constrained resources [CPU and memory mostly] as possible and still meet their requirements.

One of these applications is the Polling Application, which is composed of a set of Java applications, ASP pages, and ISAPI filters/extensions working together with an MS SQL server back-end to allow users to vote in polls and see near-real time results of the total votes and voting distribution rendered in Compuserve Image format (GIF).

Examples of polling output are shown in Figure 1.

Between all of the Starwave services that use polling, and the near real-time requirements for polling output, the Java applications that produce polling output GIFs will produce anywhere from 30,000 to 60,000 images per day. Since there are between 6 and 10 Starwave services that use polling, that's a volume of between 180,000 and 600,000 images produced per day on a single machine running IIS, MSSQL server, polling services, and all other services required for publishing content.

Rendering images is traditionally a highly CPU intensive that requires a lot of memory. Java provides a number of classes and utilities as part of the AWT (Abstract Windows Toolkit) package that allow images to be rendered. These are extremely effective for producing low volumes of images, but if you're rendering greater than 30,000 images/day, efficiency of your rendering process becomes paramount. How can we maximize the efficiency of the rendering software to handle this volume of images?

To answer this question it is helpful to have a high-level understanding of what might typically be done to generate a GIF image using the AWT. Here is an outline, with a code sample, that shows image processing steps using the AWT to produce a GIF image:

1. Construct off-screen java.awt.image
2. Draw on the off-screen images graphics context
3. "PixelGrab"* the image to get integer values representing each pixels RGB value.
4. Bit shift each integer value to extract the RGB values for each pixel
5. Store these RGB values in 3 2-D arrays for later processing
6. Find the 256 "most important" colors for the image
7. Generate your color look-up table (LUT)
8. Iterate over the 3 2-D RGB arrays, find the LUT index for each RGB triple and LZW compress this set of data to generate GIF.

* PixelGrabber is a class provided with the Java Development Kit (JDK) in package java.awt.image that can be attached to an Image or ImageProducer object to retrieve a subset of the pixels in that image.

The goal of here is to provide a set of server side classes which eliminate steps 1, 3, 4, and 5 above by constructing an off-screen graphics context as a 2-D byte array (CIUGraphicsContext class) and drawing the image directly into the array specifying a LUT index in each element of the array corresponding to each pixel value of the image, and then simply LZW compressing this data to produce a GIF. Note: it is possible to eliminate steps 6 and 7 by assuming only the Netscape color cube colors are available (which I have chosen to do), but it is also possible to construct the LUT during image generation if this is required.

This would change the above outline to the following:

1. Construct off-screen graphics context as a 2-D byte array
2. "Draw" directly into this array using LUT indexes to represent pixel colors
3. LZW compress the array to generate the GIF image

I have written a Java package called "imageutils" which was developed to streamline Starwave's GIF rendering process for polling results. The basic design pattern used is similar to the Composite Pattern from Design Patterns^[1] and is probably quite familiar to anyone who has done some graphics programming (see Figure 2).

Figure 2: Imageutils Primitive Class Hierarchy

Instances of any class that extends CIUPrimitive export enough information (via their inherited methods) such that they can rendered without having to know what type of instance they are.

The classes CIUSquare, CIUEllipse, and CIUCircle contain only constructors that make calls to "super()" and contain no other code because all of their code is in their base classes CIUrectangle and CIUSuperEllipse.

The CIUPieChart primitive is not unlike the Tea Pot primitive in the Open Graphics Library (OpenGL), allowing a pie chart to be constructed using generalized algorithms and to be considered a "primitive" for simple rendering.

Before images can be generated, it is important to understand the graphics context, which is where the majority of the efficiency improvements can be found.

In order to construct a graphics context (class CIUGraphicsContext), we need a color look-up table (LUT), which is shown in a Rational Rose diagram ^[2], along with the rest of the imageutils classes, in Figure 3.

Figure 3: Imageutils Support Class Hierarchy

The LUT we use contains the 216 colors of the Netscape Color Cube (thus the classes name: CIUNetscapeColorCube ).

This class supports a couple of simple initialization methods, one of which initializes from a static array of strings and one that reads in a GIF and stores all 216 colors in a hash table.

By initializing from an image, any color cube can be used as a LUT. Individual colors (class CIUIColor) can be constructed from HEX strings, integers, or byte triples.

Index lookups into this LUT can be done using any of six methods:

A graphics context can be constructed knowing it's width, height, background color, and LUT that will be used for rendering. For example:

This can be resized later if any of the children are clipped when they are drawn on the gc.

What is actually constructed upon instantiating a CIUGraphicsContext is a 2-D array of bytes, each byte corresponding to a pixel of your image, each of which will be filled with a LUT index corresponding to the color of the pixel. To construct an image, CIUPrimitives are drawn onto the graphics context very much like the way traditional graphics contexts work, except the imageutils package draws in bytes, not pixels.

CIUPrimitives can be constructed and then subjected to three primitive graphics operations: scale, rotate, and translate. Examples of this include, but are obviously not limited to:

The CIUPrimitive base class provides enough information that an instance of the CIUGraphicsContext class can render it into it's 2-D byte array without having to know the particular type of primitive it is. See code listing 3 for the complete class listing of CIUPrimitive.

Primitives are constructed using the LUT so when they determine what their colors are at various pixel locations within their bounding boxes the "color to LUT index" look-up can occur, which saves a lot of time doing lookups at rendering time. Colors are matched to LUT indexed using minimization of least sum of squares.

Images are composed of any number of any number of CIUPrimitives which are constructed and then drawn on the Graphics Context. The actual draw() method will return an integer which can be examined to see if clipping occurred in either the horizontal or vertical directions. Drawing consists of iterating over all of the pixels of a primitive and asking first if the current pixel is "on" (not hidden), and if so, what the LUT index is corresponding to the pixel of interest.

Images are either textured, or non-textured, which provides a way for the Graphics Context to only have to ask for a primitive's color once if it is non-textured. Invalid pixel requests result in an exception thrown back to the graphics context and the drawing of the current primitive to be skipped.

Once all of the children are drawn onto the Graphics Context, the byte data is ready for compression and writing to any image format supported (currently only GIFs are supported, using LZW compression as their compression algorithm).

• Make the CIUGraphicsContext extend CIUPrimitive, thereby making the design pattern really be a Composite Pattern. This would be achived by making the context a container for primitives that supports all of the primitives fundamental graphics operations.
• Implement run-length encoding (RLE) and Huffmann encoding to produce a wider variety of image formats whose compression algorithms may be more appropriate for the polling application at Starwave.
• Implement more fundamental graphics operations, like shearing, or generalized matrix transformations. It may even be possible to push some of these up into the CIUPrimitive class and allow extended primitives to override them if required.
• Generalize the LUT so it supports all color modes. Then, class CIUNetscapeColorCube can extend a base class and map all color requests to one of the colors in the 216 color Netscape color cube.

• Generate images "on demand". Make the image generation event driven and not time driven, thereby vastly reducing the number of images that must be generated.
• Render the images as HTML tables instead of GIF images.

The recoding of the rendering mechanism for polling results at Starwave has realized significant performance improvements which have caused image generation to be far less of a drain on system resources than previously.

Although the Java AWT methods are powerful and support a wide variety of graphics primitives and operations, the tradeoff for having all of the functionality at your programs fingertips seems to be a penalty of CPU cycles burned and memory allocated to render images. In the case of the polling application at Starwave, where tens of thousands of images are generated daily, it makes a lot of sense to trim out some functionality and implement only what we need in order to realize significant performance gains.

• Adam Fritz: Had the original idea plus some design ideas/decisions.
• David Lavalle: Wrote some code I'm using in the LUT