Pictures are a part of a large number of applications. A certain class of pictures can be referred to as illustrations. That is, the point of the picture is to illustrate a principle as part of an article or presentation. Good illustrations are visually interesting, but are judged more on their content than on their artistic merit. With respect to picture complexity, illustrations are simple in that there are a moderate number of shapes, clearly bounded by curves and lines. The image is essentially two dimensional, and color is often restricted to flat filled areas; that is, uniform colors and simple textures. Illustrations are important in business and publishing environments today. The advantages to be gained from using a computer to generate these images are similar to the ones for word processing: images are easily modifiable, pictures can be filed and copies easily generated, subimages can be libraried to facilitate the composition of a series of illustrations. However, to be acceptable outside of the experimental environment, the image quality of illustrations must be high. Curves and lines must be smooth, text must be represented in a variety of fonts, objects must be accurately positioned. While each illustration may contain a limited number of colors, a wide range must be available.

Given the type of imagery desired, a raster display will give much better representation of the picture than a line oriented display. The constraint of high image quality, even after scaling and repositioning operations, means that the picture must be stored using a high precision representation. Furthermore, if the data base has sufficient precision, the set of affine transformations can be used as tools for generating images.

The process of designing an image is the mapping of some visualization onto a medium. Therefore, that any effective tool should provide visual feed-back as the image was formed. Furthermore, the image should be built up in a two-dimensional manner, that is, by pointing to positions on a page, which indicates an interactive system. In this paper, such a system will be called an illustrator.

Given a high precision data base, such as endpoints for lines, coefficients for splines, plus information about the resolution of the display, there are many standard techniques for displaying straight lines, curves and areas (5). This process is known as scan conversion. There are a number of problems in using these techniques in an illustrator, specifically:

In an interactive system it is necessary for the user to select objects to be manipulated. A natural way to do that is to point to the object. Therefore, given a point on the display, it is necessary to determine which object has been selected. This is called hit testing. Hit testing is the inverse of the display problem, and is even more speed critical than refresh.

This paper will discribe methods for solving these problems that achieve a reasonable compromise in simplicity of implementation and response time. The solution is based on using display encoding techniques which provide a representation of the image that is compact, structured, and simple to manipulate. These techniques have been implemented in systems which have been used to successfully create illustrations. Examples are included at the end of the paper.

Graphics systems can be categorized by the type of data used to represent the picture. One type of interactive graphics systems uses raster dots or arrays of intensity samples as the unique representation of the image. These systems use a painting model to manipulate the dots directly. These systems are easy to use, and have been shown to produce effective imagery (8, 9). However, the picture is unstructured, which limits the types of manipulations that can be performed without special hardware. The resolution is tied strongly to the display resolution, which can limit image quality. In general, to be effective visually, the images from such systems require large amounts of data, either in resolution or in bits per pixel. We have chosen a more structured approach.

Given a geometric representation, one can consider that geometric elements (lines, curves, areas) are all made of filled contours. This paradigm is quite useful for applications such as the production of rasters for high-resolution printing of graphics and text (1). However, this model is difficult to implement in an interactive application because using the geometric data for display and hit testing can be expensive in terms of computation time. An interactive display file can be used to provide a definition of the picture that is structured, yet can be manipulated fast enough for an interactive system.

It is natural for several representations to coexist in the design of a graphics system, usually according to levels of hierarchy. At the top level may exist a representation that embodies some specific knowledge or meaning relevant to a particular application: architectural drawings, blueprints for mechanical parts, electrical circuit diagrams, etc. Here we will consider that the top level representation that we chose aims only at giving a unambiguous and complete description of high-quality business graphics illustrations.

To implement these ideas, the following systems approach was used: The workbench is a moderate resolution raster display plus pointing device attached to a 16 bit mini-computer. The final output device is a high resolution raster device such as a film recorder, phototypesetter, or raster printer. Shapes are defined by their geometry: trajectories and contours; plus style informations such as line width, colors, and textures. Trajectories can be specified by one of several mathematical schemes such as splines or other knot-based approximations, circles or other conical equations. Text is unformatted, and described in terms of position and string information plus style parameters such as font, color, and orientation. The user builds display objects by pointing at fitting points and indicating fitting methods such as straight lines or curves. All numbers are represented as floating point values to provide sufficient precision. The top level description is converted to an interactive display file, where the interactive processing, refresh and hit testing, will take place. The display file is used to generate a bitmap, that is a one bit per point rectangular array of samples (13), which is used as the refresh buffer for the display. This structure is summarized in figure 1.

The display file representation is used for refresh and hit testing. In designing such a representation, the first consideration is to what precision the objects should be encoded. Clearly, display resolution is sufficient for refresh. Since the user cannot specify a position by pointing which is more precise than the display resolution, it is also sufficient for hit testing. Both hit testing and incremental refresh involve scanning through the display file to determine what objects are in a specified area. Therefore, partitioning the display file to facilitate culling will increase performance. It is important that the display file be reasonably compact, yet not so difficult to generate or decode that it negates the advantages in terms of speed. It is also convenient to be able to encode all objects in a uniform manner.

Given these considerations, we have applied and modified some well known encoding techniques, chain encoding of trajectories (3, 6) and run-length encoding of areas (2, 4). These techniques are essentially compressed representations of the bitmap. Chain encoding is based on the assumption that edges are continuous. Therefore, the basic representation is the differences between adjacent pixels. Run-length encoding is based on the assumption that flat areas contain most of the information in the outlines. Therefore, the basic representation is the position of the edge on each scan line. While it would be possible to run-length encode all objects, the increased structure in the chain encoding is appealing for lines.

The particular encoding schemes chosen permit the segmentation of each object into pieces that are independent and bounded in display size. It follows from this that the time for display of one piece is bounded too. This makes it possible to run the screen refresh as a background process.

All shapes can be described by one of the two types of encoding. Thus, pointing detection can be done by a single algorithm, independent of the mathematical definition of the elements (lines, circles, conics, splines, etc.).

Chain encoding is a differential encoding scheme which records the screen coordinate increments between successive raster points on a trajectory. That is, from one trajectory point to the next, raster coordinates may differ only by -1, 0 or 1. Thus, a point may have eight possible successors, so each point new position could be represented in four bits. But, since common curve trajectories are monotonic for reasonably long intervals, one can take advantage of the continuity in direction to further reduce the number of bits per point. A number of schemes are possible for encoding coordinate increments. Two interesting and practical ones are described below.

The first scheme uses two-bits to represent the coordinate increments (figure 2). The set of eight possible curve directions is divided into four quadrants. For each direction quadrant, the three possible coordinate increments are assigned code values 1 to 3. Code value 0 is used to indicate a change of quadrant, with the following two bits specifying the new quadrant. Therefore, the trajectory encoding is a stream of two-bit codes, starting with the quadrant number (0 to 3), followed by increment codes (1 to 3), terminated by a 0.

The second scheme requires two streams (figure 3). The set of eight possible curve directions is divided into eight octants. Within each octant there are two possible directions. Therefore, it is possible to indicate each step within an octant with one bit. One stream contains the one-bit increment codes for a given direction octant, and the second stream contains the octant numbers and the number of steps in each octant. Besides being somewhat more efficient, it is possible to get a general idea of the behavior of a curve segment by examining the direction octants alone. An example of where this feature can be used is for defining edges for the scan converter. Using the chain encoding in the scan conversion process will be described further below.

As mentioned above, in order to gain efficiency in the screen updating and pointing detection algorithm, the encoding is fragmented into independent pieces of similar length that we call chunks (figure 4). The bounding box for each chunk can be stored to facilitate culling on refresh and hit testing.

The display file contains the following information for each chunk:

It is interesting to note that if the chunk size is such that each segment contains at most N trajectory points, all these points are enclosed in a square of size 2N centered at the starting point of the segment. So even if the bounding box is not explicitly stored with the chunk, a bounding region can be computed.

The encoding described above works only for convex areas, specifically, it assumes one continuous run of rasters per scan line within the area. For concave shapes, there are two options: break the area into convex pieces, or introduce a flag into the list of runs that defines the number of runs per scan line. We have implemented the second option, choosing a negative starting X as a flag, signaling that the delta X value is the new number of runs per scan line.

Assuming the run-length encoding describes areas at display resolutions, the starting and delta X values need be no larger than the maximum display coordinate. In practice, most runs can be described in fewer bits. Therefore, it is worthwhile to consider using a variable field for X. While maximum compression would be obtained by using a technique such as Huffman coding for field size, for simplicity we have chosen to implement two fixed fields (8 and 16 bits).

The display file contains for each chunk:

The geometry to rasters conversion scan conversion process can be decomposed in two operations: Converting the geometry into the display file representation, and converting the display file to rasters. The conversion from geometry to display file only need be performed when an object is created or the shape is changed. Because this is a relatively infrequent operation, standard techniques for digitizing curves and filling areas provide acceptable speed. The specific algorithm used for areas is given at the end of this section. Objects are displayed in back to front order to give the correct overlap information. All display, refresh, repositioning, and hit testing operations can be implemented by manipulating the display file.

By the term "hit testing" we mean given some target point, usually the display coordinates of a cursor, which is the selected object? In hardware augmented systems, hit testing is done by the clipping and display system. The clipping boundry is set to a small window around the hit point, and the entire picture is refreshed. An object falling inside the window is returned as a possible hit. In a raster system, redisplaying the object list is too slow, and redisplaying the rasters provides no structural information. However, the segmented encoding provides both structural information and a way to quickly determine which objects are candidates.

The frame information on the encoding chunks provides a method for quickly culling out those segments which do not fall near the target point. The remaining chunks can be decoded using the same routines which display the encoding, except that the resulting points are compared to the target point instead of being displayed. Once the objects which lie near the target point are identified, some algorithm must be applied to select one of the objects. Some considerations are: absolute distance from the point, overlap order of the objects, prefered objects, etc.

Several people have contributed significantly to the design and implementation of the systems this paper is based on. The authors would like to thank Rick Tiberi, Geoff Brown, and John Dawson for their help and ideas.