Printing VLSI images3 in a device-independent manner poses new imaging problems, the most important of which is to render the layout in such a way that enough information is preserved in the hardcopy output. In editors for VLSI design layout, an abstraction of the physical IC layers is commonly represented by using different colors. In conventional imaging, accurate tone rendition is of primary importance while the information contained in a single fragment of the image is less important. In the rendition of a VLSI image, however, individual tones are irrelevant, since they are simply abstract properties of the physical layers in the VLSI image. At the same time, the IC designer must be able to discern all the layers in the VLSI image, including those contained in overlaps. The polygons representing the various features must be transparent [Trimberger, 1987], while, at the same time, the different intersections must yield tones that are easy to tell apart.

This property of being transparent is different within the scope of VLSI DA tools than it is in the real world. For example, in the editor presented in section 6, the second metal layer is represented using the color ``darkish vivid magenta.'' However, when metal-2 occurs over some material other than a well, the user needs it to be printed in a more transparent shade (in this case, ``very dark vivid magenta'') to prevent large power or ground wires from hiding the contents of cells over which they are routed.

As this would indicate, one of the most relevant problems of rendering VLSI images is how intersections are treated, since this determines readability. Therefore, the solution is to treat intersections explicitly, instead of trying to twist an existing imaging model to produce the desired effect. The example in the previous paragraph cannot be solved with conventional algorithms used in computer graphics for rendering realistic scenes.

By treating intersections explicitly, I mean that the intersections should be found and treated as new regions, to yield a partition of the plane. This way, the rendition of intersections can be controlled individually and independently of underlying imaging systems. Figure 2 illustrates some possible imaging models. To image VLSI layout, two problems have to be resolved: all intersections have to be found and a model for coloring the intersections has to be determined. I give a solution to the first problem in section 4 and a solution for the second problem with the method by which it's obtained in section 5.

In DA systems, the data to be imaged can be of different kinds; different abstractions are used in the various stages of a design. Examples of abstraction levels are: layout, transistor schematics, gate-level descriptions, and block diagrams. When a single designer is in charge of an integrated circuit, the process usually begins by specifying a block diagram. Each block is then refined by associating a gate-level description with it, etc. Often higher level descriptions are retained near refined objects to enhance readability, i.e., it has become customary to mix layout with transistor schematics, gate-level descriptions, and block diagrams.

Similarly, cell libraries are often documented using all three levels of abstraction in the same document. Figure 3 shows a block diagram element, a transistor schematic, and the layout of a memory cell. Many modern VLSI editors offer the ability to mix layout with schematics4, hence an imaging model should be able to encompass line drawings (shown on the left in figure 3) and colored representations (shown on the right).

From a graphic point of view, two classes of objects can be distinguished. One class contains sets of colored regions. These regions have simple shapes, but different regions should be easy to discriminate. The other class consists of text, in different fonts and orientations, and lines, such as line segments, circles, and splines.

An appropriate refinement to the imaging model treats the schematics as annotations which are never covered by layout. In this way, signal names in the layout are always readable. First an algorithm renders the layout, then another algorithm superimposes the annotations. This model is illustrated by figure 4.

It is said that one picture is worth a thousand words. However, designers will include in their documents the symbolic descriptions they consider necessary only if they can do so with the same small effort that is required to write plain text.

In pursuit of system integration, a tool that generates IC design documents should use the same user model as the system's text editor. A user model is the user's conceptual model of the information he or she manipulates and of the processes applied to this information [Newman, 1980]. While the first part of this definition has been covered in section 2.2 (annotations overlaid on layout), this section is devoted to the processes applied.

Like many CAD/CAM tools, VLSI design automation tools have a long history of inappropriate user interfaces. Indeed, most of the time, the user's model of VLSI DA systems is rather a brouhaha of commands. There are many interactive commands and variants thereof that the user needs to accomplish design tasks; the tool writers are busy providing the functions of the commands and, in return, the users are willing to make a larger learning investment to ``buy'' more functions.

A problem arises when a new user wants to learn the system. Although the complexity of the job justifies long training, an inconsistent user model forms unwanted behavior habits. The habits formed out of this absence of a consistent user model leads to avoiding some commands and replacing them by other complex command sequences that seem necessary according to the user's conception. Thus, the user can take advantage of only a subset of the system. Other researchers have given examples of common errors in user interface design [Nievergelt, 1982] and presented a detailed analysis of a VLSI editor's user interface [Card et al., 1983, chpt, 10].

In summary, there are two main requirements for the design of a user interface for a tool that integrates design automation with a document processing system:

As is suggested by figure 1, both the task of coalescing a VLSI image with a text document and of printing a VLSI image can be conceived of as a sequence of copy commands. In the first case, each invocation of the command would take a specified portion of the VLSI image and insert an equivalent illustration at a selected position in the text. In the second case, all operations required to submit the specified portion of the VLSI image to a print server5 would be performed.

Independent of the complexity of the implementation of a task, such as submitting an arbitrary VLSI image to a print server of any technology, the user's model is kept simple, because conceptually the task is simple.

Having defined what the user's model of the tool should be, the abstract concepts around which the tool is organized have been specified. This is known as the representation of the tool at the conceptual level [Moran, 1980]. In section 3.2, the details of the user interface are specified. If integration is to be achieved, the actual realization of such a user interface must depend on the paradigms in its underlying system; a functioning implementation is presented in section 6.

Two concepts mentioned above have to be refined. The first is to define ``a specified portion of the VLSI image to be acted upon.'' The second is to specify how the choices and variants in ways of moving a specified portion of the VLSI image are presented to the user. From an implementation point of view, this means that some parameters have to be introduced. In pursuit of clarity and orthogonality, the parameters themselves have to be chosen carefully and, futhermore, their possible values must also be taken into consideration.

Three orthogonal questions are identified: What? Where? and How many? These questions are sufficient to describe the input, the output medium, and the number of copies for a printer.

Several users have been observed and interviewed. It has been observed that the user's answers to these questions generally remain constant over a session, hence the user considers it a nuisance to set these parameters every time the command is issued. Therefore, the parameter's values should be retained for repeated invocations of the command. In the following, the possible values of the parameters are described.

``What'' circumscribes the input. Three values are sufficient to do all the required tasks: design, selection, and WYSIWYG. The design value indicates the entire content of the VLSI image. Therefore, this value is employed to draw everything. The selection value is used to show details in a large scale and is based on the selection concept of the VLSI editor.

The third option, WYSIWYG (what you see is what you get), is more subtle. Prior to the availability of the tool described here, coalescing VLSI images with text documents required the use of an additional tool and the specification of a set of parameters, including a cropping window, a translation of the origin, a scale factor, and eventually, for layout, a rotation to change the aspect ratio. However, as often is the case, a simpler method can be more powerful. The user adjusts the window of the VLSI editor so that it displays exactly what should go into the text document. When the command is executed, the tool computes the transformation and fits the image to the text layout. Use of this feature maintained, for instance, the same font size in the diagram above and the diagram below.

While the first parameter thus circumscribes the input, the second parameter controls the output. Since the destination is not necessarily a printer, the second parameter sets goals rather than devices. Goals can be classified into three sub-groups: electronic documents, print servers, and compute servers.

The diagram above contains the item ``master in page description language.'' For the user, this is an implementation detail, and therefore not part of the user interface per se. Nevertheless, it is intentionally revealed to the user, thus it becomes part of the user model [Moran, 1980]. One reason to make the user aware of this extra step is that most systems have a Redo or Repeat command which reexecutes the last command. To support such a command efficiently, an intermediate data structure called a master (a program in this case) is maintained to capture the last imaged input. In this master, the illustration is stored in a normalized size, so the task can easily be redirected to a different goal.

The text editor is the most prominent member of the electronic document sub-group. For the user, the typical operation is trivial; executing the command will cause the selection in the window of the VLSI editor to be copied and fitted at the caret position in the text document. Repeating this operation allows the user to coalesce a VLSI database with a text document performing only a simple sequence of the cycle select input, select output position, and copy. The implementation details are summarized in section 6.

A disk file is the other choice available in the electronic document sub-group. If the master is represented in a standardized page description language (as discussed at the end of the introduction), writing it to a disk file is obviously valuable. Such masters are useful in electronic document exchange beyond the user's world and for archival storage, since it will always be possible to print a document in a standardized page description language. An additional application is reading the master into a general purpose graphic illustrator for further processing. This is required when illustrations for books must be improved by graphic artists.

The print servers comprise the second sub-group of output goals. The use of a standardized page description language makes available a large amount of software to drive a variety of different printers. For the purposes of printing VLSI schematics and layout, four printer technologies are particularly valuable.

Electrostatic plotters combine a reasonable resolution of 200 or 400 dpi (dots per inch) with a large paper width. This makes them the preferred output medium for complex schematics involving a large number of symbols and for layout. Thermal transfer printers have the advantage of being able to print on paper that is larger than 8.5 by 11 inches and at medium resolution. This makes them suitable for medium sized schematics.

Laser printers are well-known devices that print on 8.5 by 11 inch sheets of paper, while high resolution printers are experimental laser printers with a resolution of 1200 dpi [Starkweather, 1985]. The latter prints on photographic film or paper; a page is produced for each color separation unless the printer is in black-and-white mode.

The distinction between black-and-white and color printers is made because many color print servers offer a logical black-and-white interface which translates colors to black-and-white patterns and skips the color passes. Since publishers often require black-and-white illustrations, a good tool should support this by presenting a different logical printer for the two possibilities; this is the most natural place to implement it.

Compute servers form the third and last sub-group of output goals [Hagmann, 1986]. Their purpose is to off-load the creation of complex bitmaps from the print server to more powerful or dedicated machines. When this value is selected, the master is sent to a server that performs the raster scan-conversion, producing a (possibly compressed) bitmap. After being notified by the compute server that the bitmap is completed, the tool automatically submits it to the appropriate print server.

In contrast to the first two parameters, what and where, the third parameter, how many, is trivial. It is needed to specify the number of copies to be printed when the goal specified in the where parameter is a print or compute server.

Although this user interface covers most needs, in real life the need arises to execute more complex tasks. It is important that such requirements be satisfied by the same tool, since a special tool would result in an overly complex user model. If you add tools, you add their user models, and what you get is not a series of simple user models but a single user model that is a collection of all the previous user models and hence cumbersome and unwieldly.

On the other hand, the user interface of the initial tool should be retained as closely as possible to keep the execution of simple tasks simple. A possible stratagem is to designate the seldom used functions ``advanced'' and hide them from the casual user. The way this is realized depends on the paradigm of the system underlying the tool. For example, if the paradigm includes pop-up or pull-down menus, a nested menu can be presented to the user.

The advanced functions presented below cover all the electronic publishing needs of the VLSI designers currently using this tool.

Corner stitching, [Ousterhout, 1984] and [Shand, 1985], is a data-structuring technique that is efficient for performing local operations on large numbers of small rectangles aligned to the axes. In corner stitching, space is stored explicitly. Because of this, the data structure represents a decomposition of the plane generated by the input rectangles; this is called a tesselation. The elements of a tesselation are called tiles. The geometrical axioms for a decomposition are satisfied by defining a tile to be a set that is closed at the South and West sides, and is open at the North and East sides.

The tiles are linked with four pointers, called stitches. Only two corners need to be stitched to accomplish all local operations. The stitches in the lower left corner of a tile are called South-West and West-South, while those on the upper right corner are called North-East and East-North (see figure 5).

Each tile has a value, which is application-dependent. Space tiles, i.e., tiles that do not correspond to any input rectangle, have the special value L. A tesselation is kept unique and minimal by requiring maximal horizontal strips. When a non-space tile is inserted into a space, horizontally adjacent space tiles are split into thinner tiles and then joined into maximal strips. When a new non-space tile collides with an existing non-space tile, a client's procedure must supply a new value for the new tile inserted into the tesselation to represent the intersection. Only then are the maximal horizontal strips formed which restore the consistency of the tesselation.

Thus each tile contains the following information:

In his paper on corner stitching, Ousterhout has shown that, in a tesselation with n non-space tiles, there are at most 3n+1 space tiles. He claims that, on the average, only one space tile is needed in layout for every non-space tile. Despite this claim, the number of tiles in a tesselation is much larger than the number of rectangles in the input. This is because the intersections are decomposed to compute their color. The input for a straight transistor surrounded by white space, for instance, consists of two crossing rectangles (the example used in figure 2 is a representation of a transistor), while it generates five non-space tiles in the tesselation.

It might be argued that it would be better to defer finding the intersections to the moment when the bitmap is produced. A color map would be used to XOR the rectangles into the bitmap. This is a time/space trade-off. Although the number of rectangles is much larger by explicitly representing the intersections, every intersection is handled only once at the high level of rectangles to determine the color
. When the intersections are resolved at the bitmap level, the operation of XOR-ing bit patterns is performed for every bit for every rectangle intersecting on that bit. Even if the BITBLT function is implemented efficiently, doing operations on a word basis as far as possible, this low level method is significantly slower owing to the large number of rectangles in a VLSI layout.

To avoid the creation of unnecessary rectangles in the intermediate master (see section 3.2), rectangles that entirely share a common edge and are the same color are merged, using the maximal horizontal strip method introduced above. The basic idea is to assign every color a number which is stored as the value of a tile as illustrated in figure 6. If two tiles with a common edge bear the same number, they are merged into a single tile with that number.

It is preferable not to make assumptions about the possible colors to retain independence from VLSI technologies. Therefore, a separate data structure, called color table, organizes the colors. Each entry in the color table consist of a set of layer colors and a specification of a blend color. The set of layer colors contains all layers that intersect in a given tile and is the search key into the color table. The blend color specification is the resulting color-blend for the intersecting color.

The value of a tile stored in the tesselation is a reference to an entry into the color table. The algorithm for inserting a rectangle into a tesselation is as follows:

After all rectangles have been inserted into the tesselation, and after the colors for the intersections have been blended as described in the next section, they are painted into the master using a page description language as described in Section 3.2. Since, in the geometrical sense, the tesselation is a decomposition of the plane, a simple and fast intermediate encoding can be produced.

Since in VLSI layout the exact visual perception of a color of a given swatch is not as important as the fact that the swatches are easily discernible, it is possible to ``spread'' the clusters and to eliminate the greys. A simple heuristic approach is enough to obtain an acceptable result.

Using this simple method, the colors written in the master have a more uniform distribution over the entire color spectrum than the layer colors used by the VLSI editor, achieving more robustness regarding the mismatch of the gamut of the color monitor and of the various color printers. Designers have printed images produced with the tool described in this report on such diverse devices as high-resolution color laser printers, thermal transfer printers, and Versatec color plotters.

The difficulty of making a judgment of the relative magnitude of two color differences is reduced if the colors involved are closely similar in at least one of the three basic attributes of color perception, such as hue, saturation and lightness8. An adequate color model common in computer graphics is the HSL (hue, saturation, lightness) color model, although this model is used much more informally than in color science [Schwarz et al., 1987]. As shown by Foley and Van Dam [1982], it is easy to convert a color from the RGB model to the HSL model and vice versa.

In a simple implementation, the colors for the various layers present in the VLSI image are converted to HSL values. The hues for the layers are then distributed more uniformly across the spectrum and the resulting values are re-converted to the RGB model.

For the intersections, the RGB color model is used to construct a simple blending algorithm. Each layer is given a weight and the weighted mean of the RGB values of the colors for the intersecting layers is calculated, yielding the color for the intersection. The weight is not fixed, but depends up the context, i.e., the other intersecting layers. Given the small number of layers in a VLSI design, the implementation is a straightforward application of dynamic programming.

The color values for the CMYK model used in printers are obtained with a simple approximative calculation. First cyan, magenta, and yellow values are calculated by subtracting red, green, and blue from one [Foley and Van Dam, 1982]. Finally grey, i.e., the minimum value of cyan, magenta, and yellow, is subtracted from these three colors and used as the black value. The technique of removing grey and placing it into the black separation is known as undercolor removal or UCR. The proposed radical degree of UCR is unusual, but it allows to reduce the size of the print files by 25%, which in the case of VLSI layout is a large number of megabytes.

As a starting value, if there are n layers in an intersection, each is given weight 1/n. The value is then looked up in a table, which for every layer returns a factor in function of the other layers present. The weights are then renormalized so that their sum is 1 and the weighted mean is calculated. Cuts and vias are exceptions because their factor is always infinite to give them weight 1.

This allows one to fine-tune the rendition of such delicate layers as wells. Physically, a well is an implant in the substrate, which means that it is below all other features on the chip. An accurate representation would be to treat it as a background color. In a straightforward implementation using a blending algorithm based on mean values, the rendering of the wells looks like a veil over the area it covers. Subjectively, for the designer it is disturbing to perceive wells to be on top of the other layers when he knows that the wells are underneath. Using context dependent weights easily solves this problem, as it does for the metal-2 problem described in section 2.1.

Some experiments with different weight strategies has been carried out. Designers have been asked to read layout produced by somebody else, and the blending that permits the maximum readability has been chosen for the final implementation. Figure 9 shows an inverter imaged these colors.

Typically, in VLSI layout there are millions of rectangles, while there are only around 100 possible intersection combinations. Therefore, the color table introduced in section 4 is used to cache the blended colors, to avoid the calculation for every tile in the corner-stitched plane. When all rectangles have been inserted in the tesselation, the color table contains all intersection combinations appearing in the input. The color table is traversed only once and a color is blended for every entry. As the last step of imaging IC layout, the tesselation is enumerated into the intermediate master using the information in the color table.

Although the simple method just descibed produces usable layout prints, a significant improvement can be obtained by applying the colorimetric methods developed in color science. These methods allow to achieve significantly improved readability and to use a smaller color palette than the physical model combined with transparent colors described in the literature [Trimberger, 1987].

Whilst applications like avionics have triggered the development of such methods for color monitors since long [Merrifield, 1987], [Silverstein, 1987], this methods have not been applied for computer generated hardcopies. The material in this section is based on the book by Wyszecki and Stiles, to which the reader is referred for further details. This section is limited to the presentation of the material necessary for the task at hand.

Due to lateral interactions in the neural network of the visual system, Mach bands are perceived near the border of two juxtaposed fields of different luminance [Wyszecki and Stiles, 1982]. On the dark field a darker band is perceived and on the light field a lighter band is perceived.

In the printing industry, a mask is used to exagerate the edges between fields of different luminance, a technique known as detail enhancement (or peaking in the case of electronic color scanners) [Southworth, 1979].

In animated cartoons and comic strips, regions are outlined in black. Some tools to create checkplots attempt to use this stratagem by outlining all geometric figures in the layout, especially when they use cross-hatching to fill the regions. Although this works to some extent if the underlying VLSI editor is based on polygons, it fails if the VLSI editor is based on rectangles, as is shown by figure 19. The regions of a given color are not rectangular, so outlines clutter the interior of regions.

Since the data is already stored in a corner stitched plane, it is easy to devise a region-finding algorithm. As the tesselation is enumerated and each tile is painted into the master, the neighborhood of the tile is explored. If a neighboring tile's index into the color table is different than the tile's index, a black outline is painted along their boundary. The result is shown in figure 20.

Cedar is a programming environment whose primary purpose is to increase the productivity of programmers whose activities include experimental programming and the development of prototype software systems for a high-performance personal computer [Swinehart et al., 1986].

Nectarine processes images produced with the VLSI editor ChipNDale [ibid., page 458], which can contain both schematics and layout. For the intermediate master, the Interpress [Xerox, 1984] page description language has been chosen. The use of the Interpress Electronic Printing Standard [Xerox, 1986] (for a summary, refer to Bhushan and Plass [1986]) allows Nectarine to take advantage of all the Cedar imaging tools available for Interpress.

Interpress is a standardized page description language. More precisely, it is an interchange standard which specifies a set of instructions for print software to generate an image of a document page. ``Interchange standard'' refers to the property Interpress has of being independent of a particular environment or characteristics of computers or printers. An Interpress master is a program that can be executed on any machine for which an Interpress interpreter—called a decomposer—is available. The method of specifying how to generate images instead of specifying the images themselves—e.g., specifying a rectangle as an instruction to print a rectangle of a given dimension to be printed at a given position, instead of a bitmap and some printer control commands—leaves an Interpress master independent of such idiosyncrasies as resolution and control commands.

The program is structured in three modules: the user interface, the color blending implementation, and the main module which calls the corner stitching package to tesselate the layout and subsequently calls the Interpress package to produce masters that are submitted to the various print servers. Nectarine makes five passes over the data.

In the first pass, the VLSI image is traversed to identify all fonts used and to determine the print fonts corresponding to the screen fonts. This information is employed to construct the preamble of the Interpress master.

In the second pass, all intersections are found and the image plane is decomposed into a tesselation using the corner stitching algorithm. The rectangles are assigned numbers according to the layers intersecting in them. The color table, in which the intersections are classified by their resulting color, is created.

In the third pass, the color table is traversed and a color (one that represents the particular intersections occurring in the rectangle class to which the entry in the color table refers) is blended for each entry. It is in this pass that color corrections to improve ``printability'' are performed.

In the fourth pass, the tesselation is traversed. Each rectangle's color is looked up in the color table and a corresponding colored rectangle is painted into the Interpress master.

In the fifth and last pass, the annotations are handled. As shown in figure 3, painting them into the Interpress master in a separate last pass makes them appear superimposed on the marked paper. This is because the Interpress standard allows one to set a so-called priority toggle which enforces the model shown in the first example of figure 2, as described in [Xerox, 1986], section 4.1, and in [Warnock and Wyatt, 1982].

Where appropriate, caches are maintained to avoid recomputations of the same data in successive invocations of the Nectarine command.

In concept, including a specific symbol from a VLSI image into a specific location of a text document is the same operation as copying a portion of text from one document to another. In Cedar's text editor Tioga [Swinehart et al., 1986], page 451, text is copied by selecting the source text and the destination position (called caret), and applying the copy command.

One of the paradigms used in Cedar user interfaces is based on so called control panels. These are windows that contain menu buttons. The user executes a command by clicking a mouse button when the cursor is on the menu button of the desired command. Figure 21 shows the control panel ChipNDale associates with each VLSI image.

Nectarine uses the last line in the ChipNDale control panel. The three buttons labelled What, Where, and Copies correspond to the three parameters discussed in section 3.2. Since the set of values that the parameters can assume is known in advance, a new class of menu buttons has been implemented. This class is called flip button, because when the user clicks a mouse button over one of them, the answer flips through the set of possible values. The values of the parameters are retained until they are changed explicitly, because such a change is required only rarely.

Once the parameters are specified, the copy command can be triggered. In figure 21, the highlighted menu button labelled Nectarine, and outlined with a box, is the menu button that actually triggers action. This button is referred to as the action menu button.

In section 3.3 the need of so called ``advanced'' functions hidden to the casual user had been postulated. They have been implemented as additional parameters, which have well-behaving defaults. The fields for these parameters are in a second line in the ChipNDale control panel, which becomes visible only when the panel is scrolled up. Casual users do not even suspect that the control panel is a scrollable window, hence the user interface is not complicated by these advanced features.

As shown in figure 1, it should be possible to coalece a ChipNDale image with a Tioga document by repeatitively copying portions of the image at given text positions, whereby the image should be scaled to fit the text document.

Tioga documents are tree-structured, with each node corresponding approximately to a paragraph or statement. Tioga allows one to define special node classes, such as to display Interpress masters on the screen.

When a node is to be painted on the screen—or more in general, formatted—the paint procedure from the node's class is called by Tioga. Using this classing mechanism, it would have been possible to insert ChipNDale data structures directly into the Tioga document, thus allowing the figures to be edited. However, this would require the VLSI editor to be loaded each time a document containing such figures is examined. Since many people reading documents with illustrations from ChipNDale are not designers and, therefore, are not running DA tools, this was considered to be a undesirable solution.

Instead, the existing Interpress artwork class has been improved. The adopted implementation allows the examination of a document with ChipNDale illustrations on any machine for which an Interpress implementation exists. This method has been accepted favorably by the VLSI designers. Due to Nectarine's powerful user interface, the designers have accepted to keep figures also in a separate ChipNDale document and to copy a figure again into a Tioga document every time the figure is amended.

The required improvement to the Interpress artwork class is because the coordinates in an Interpress master are fixed values expressed in meters, so that a master is always printed in the same size. The difficulty is that the field of the page into which a Tioga document is rendered is not static, but is determined from a style sheet and from local properties of the document at the time of formatting. In order to reflect this flexibility in an illustration copied with the aid of Nectarine, instead of associating static formatting information (such as a bounding box) as a property of the figure, Nectarine places instructions in the information for the formatter.

These instructions access the formatter's state information to determine the current margins. The known size information of the illustration is employed to compute a scaling factor such that the illustration is flush to the local margins of the document. This scaling factor is in turn used to modify the formatter's state information to achieve the desired effect. In particular, if a document is printed with a different number of columns per page, the illustrations do not have to be regenerated.

This mechanism has required only a minor change in the Interpress artwork class, yet producing active documents in this way is a major time-saver for authors. The reason the implementation of this improvement required only a minor programming effort is that Cedar makes available an interpretative language that can be used to implement formatting procedures in artwork classes. This simple stack-oriented language is called JaM [Warnock and Newell, 1980], uses a postfix notation, and is similar to Interpress.

JaM interprets a stream of tokens by placing those which are data on a stack; the tokens that are instructions are executed operating on the data in this stack. Since a Tioga document as seen by a formatter is such a stream, all that needs to be done is to insert appropriate JaM instructions in this stream.

In the applications described in this report, the size of each printed rectangle is more important than its absolute position. For instance, in schematics, a bus is represented by a family of parallel straight-line segments. For the designer it is important that the width of each segment of the family is represented with the same number of pixels. This is achieved by translating the origin in the Interpress master to the lower left corner of the tile before painting it, because the Interpress coordinate system always has its origin on a grid point (see Xerox [1986], section 4.3.4. for more details). The procedure PrintTile, which is called for every tile when the tesselation is enumerated to paint the tiles into the master, has the following simple structure for a rectangle of widthw, and heighth, with its lower left vertex at (x1,y1):

In section 5, the values of the cyan, magenta, yellow, and black components of a colors were considered to be real values in the interval [0, 1]. It is clear how to produce the binary values 1 and 0: ink and no ink. How are the intermediate grey values generated?

It might be of interest to learn first how the RGB signals fed into the color monitor are generated in most of today's workstations, since this is relevant for continuous tone printing. From an electrical point of view, the different voltage values that can be applied to an electron gun and are above the noise level can be expressed with 8 bits of information. For an RGB image, this would require 24 bits. However, on a color monitor, only 7000 colors can be discriminated when displayed in non-adjacent fields [Murch, 1987].

To avoid the waste in memory space and bandwidth, the digital-to-analog converter-chips comprise a look-up table loaded by software that allows to index a pre-declared 24 bit RGB triplet with an 8 bit index. These chips also perform the g-correction. The luminance of the phosphors is not proportional to the voltage applied to an electron gun. Proportionality is achieved by taking the g-th root from the tristimulus values, where g  [2.5, 3.0] [Meyer and Greenberg, 1987]. A better model is to consider the logarithms of luminance and voltage, so that g becomes the slope of a curve related to the tone reproduction curve. Images displayed with a low g are perceived to have pastel colors, while those displayed with a high g are perceived to have highly saturated colors.

Most printers do not permit continuous tone printing. An additive model is used to mix the colors of the inks with the white of the paper. This additive model combines with the subtractive model of the ink mixing.

One technique, called halftoning, consists in using ink spots of variable area. For each of the four color separations cyan, magenta, yellow, and black the image is subdivided in a raster of square bins, which is called a halftone screen. For each bin, a spot with area proportional to the lightness of the color is deposed on the paper.

The subsequent printing of the four separations causes the screens to produce interference patterns, known in the printing industry as moire patterns. The solution is to rotate the four halftone screens by different angles, a technique called angling [Strauss, 1967]. The interference patterns depend on the lightness distribution in the image, thus there is no universal set of values for angling. The standard angles are such that moire patterns are minimized for flesh tones [Southworth, 1979].

The colors for VLSI layout are not related to flesh tones, hence the standard angling will always create moire patterns. One solution is to find a set of angles for every printer that is used, a task that is not hard given that the palette of discriminable colors for VLSI layout presented in section 5.3 contains only 27 colors. A different solution is to distribute uniformely the lightnesses of the colors in the palette, so that the additive effect is pronounced and distinct moire patterns are formed. Since VLSI layout is examined with a relatively large angular subtense, the moire patterns can actually impove the readability.

Many digital printers cannot produce ink spots of variable area. On such printers, a number of pixels can be used to approximate a dot. This technique is called halftone approximation [Foley and Van Dam, 1982]. Accurate algorithms have been devised to obtain the same halftoning quality as in traditional methods [Holladay, 1986]. Unfortunately, halftone approximation substantially reduces the resolution of the printer. For instance, if the printer has a resolution of 1200 pixels per inch and 12 pixels are used to approximate a dot, the resulting resolution is 100 dots per inch.

While such a resolution may be sufficient for realistic images, it is often not acceptable for VLSI layout. Wires can be thinner than a spot of such a size, hence the wires become fuzzy and very hard to trace. Distributing uniformely in each color separation the lightnesses of the colors of the palette allows to use smaller numbers of pixels per dot, thus increasing the device resolution.

The fuzziness of the wires can be further reduced by using a halftoning algorithm where, for increasing lightness, the pixels are ``turned on'' from left to right and top to bottom in a regular pattern. If a 3 3 pixel matrix is used for each dot, the following threshold matrices have have been used in conjunction with the discriminable colors of section 5.3:

Such dots, or more appropriately, cells, have the advantage of degrading gracefully in images with elements of sub-dot size when they are observed at a large magnification. The disadvantage is that putting marks of this size on paper is much more difficult than for the traditional halftone dots. For most inks the image will look smeary, because not all pixels will receive the same amount of ink. A careful choice of the the color palette is mandatory. In particular, these cells are not suitable for realistic images.

This technique is still halftoning for full-color printing. This is not to be confused with the so-called stipple technique [Trimberger, 1987], which was developed centuries ago to render coats of arms in black-and-white or reliefs. A stipple pattern represents a given color or VLSI layer, and its tristimulus value cannot be changed. Intersections of stipple patterns are hard to predict and they require a multi-color process to print. While they play an important role for rendering VLSI layout on black-and-white plotters, they are an anachronism in the world of color printing.

For applications in which an even larger resolution is needed, such as illustrating books with images of entire chips, line art can be used. The separations are then printed in multi-color instead of full-color, avoiding halftoning. In conjuction with a high resolution printer [Starkweather, 1985], this allows to print VLSI layout at a resolution of l = 31.75 mm, in which even the layout of a large chip is readable with the use of a good magnifying glass when it is printed in the size of a book page.

When printing in multi-color it is desirable to use only four separations to control the printing costs, because so-called quality inks will probably be required. The following colors have yielded good results:

Cuts and vias can be imaged in three of the separations to appear black. At the scale at which the use of line art becomes interesting, the other layers, such as the wells, can be omitted without hampering the readability for a VLSI designer.