Abstract
The purpose of this paper is to review and organize the basic concepts involved in naming and modifying images presented on a display, and to indicate the advantages and disadvantages of the various techniques currently used by graphic languages. We will not consider the syntactic questions of how the semantic capabilities are presented to the language users. A number of extant graphics programming languages are categorized according to their naming and modification capabilities.
Most graphics languages allow names to be associated with various parts of an object as it is being described by the application program. For example, languages which provide a segmented, transformed display file (1) allow each segment to have a unique name. A segment might contain a single line, or a text string representing a light button, or the lines to draw a resistor, etc.
Such names can be used in several ways. They are used with pick devices (2), such as the light pen, for reporting to the application program the identity of a selected entity. In some languages, this is in fact their sole use. Most languages, however, use names to provide a selective modification capability. The simplest such capability is mere deletion of a named entity, although nearly all languages allow named entities to be extended, to have additional items added at any time after the entity was initially created. Some languages allow modification to the attributes of named entities, such as intensity, blink status, size, position, or orientation. A final use of naming is so the application program can later refer to a previously defined entity, to copy it {as a macro-definition) or reference it (as a subpicture).
The simplest sort of naming capability associates a single (usually integer) name with a collection of one or more graphics primitives. We call this single-level naming. A more sophisticated capability is that of multiple-level naming, wherein the picture is viewed as a tree, with leaf nodes corresponding to collections of graphics primitives, and internal nodes corresponding to collections of collections. Figure 1 shows a circuit diagram, and the tree structure corresponding to a convenient way to name the parts of the circuit.
The leaves of the tree symbolically depict the graphics primitives belonging to each leaf, while the numbers by the nodes are node names. These names are normally assigned by the application program in some meaningful, systematic way. If the application's data structure can reside in main memory, the names often correspond to indexes into arrays or addresses of data in a linked list. If the data structure is disk-resident, the names are often record identifications. Notice that although node names are not unique, the sequence of node names on the path from the tree root to any node is unique. Thus the multi-level name of the capacitor in filter 1 is (23,10,1), while the name of the capacitor in filter 2 is (23,11,1). The name of filter 1 is (23,10), while the name of filter 2 is (23,11). While in the example the root node has a name (23), it is more customary to eliminate root names, and to refer to the entire picture by some means other than the name, since there is by definition only one root node. Thus most graphics languages have a command such as CLEAR which erases the displayed picture. Systems which provide archival storage of pictures typically provide a root name only when the picture is to be saved. If later retrieved, the picture becomes the current nameless picture, unless incorporated by copy or reference as part of the existing current picture.
Multi-level names are also called nested names, or qualified names. This derives from their similarity to naming in block-structured programming language and in the data structures of PL/I, COBOL, and other languages.
The advantage of multi-level names is that they can be used to uniquely refer either to a collection of primitives, such as (23,10,4), or to a collection of collections, such as (23,11). This is desirable because in many applications we indeed want to refer to higher-level groupings. In a circuit design application, we might have both a "delete filter" command and a "delete element" command. If only elements (resistor, capacitor, inductor) have names, as would be the case with single-level naming, the application program is given the job of deciding what filter (if any) an element belongs to, given an element name. With multi-level naming, the filter name is explicitly given in the qualified name of an element: element (23,11,4) belongs to filter (23,11).
Application programmers sometimes try to encode qualified names in a single integer name, perhaps by using individual bytes from the integer to represent level names. This can be awkward for the application programmer. The range of available names may be too limited, so names may not be able to be assigned in a useful way. Then artificial (in the example, 1-byte) names must be used, and correlated to useful names via a table-lookup.
Not all interactive graphics applications have an inherent use for qualified names, of course, but graphics languages meant to serve a variety of applications should make available a multi-level naming capability. Some languages allow essentially infinite-level naming, while other languages allow a fixed (usually 1 or 2) number of naming levels. Languages with a fixed number of levels may require all collections of primitives to be named with the fixed number of levels. This restriction can introduce a degree of artificiality in hierarchical naming if not all collections of primitives inherently have the same number of naming levels. This is only a minor inconvenience if the language requires more naming levels than are truly needed, but can be awkward if not enough levels are provided, as discussed with single-level names. It does seem possible to naturally accommodate most interactive applications with 2 or 3 levels of naming.
In the early days of graphics languages, names were sometimes assigned by the graphics language rather than by the application programmer. We have come to recognize this as a serious handicap for the application programmer, who is consequently forced to maintain tables correlating his names with the language-provided names.
Just as multiple-level naming can be more convenient than single-level naming, so too with modification. This is so because we often have applications in which sometimes collections of primitives are to be modified, while other times collections of collections are to be modified. In the example of Figure 1, the application programmer would prefer to delete filter 1 with a single command. At the same time, though, the application programmer would also like to be able to delete just the resistor, capacitor, or line. This is easily done with a 2-level (or greater) modification capability. With 0-level modification, the application program would erase the entire picture, and then re-describe it, minus the deleted portion. With 1-level modification (such as that provided by segmented, transformed display files), the application program has two choices. Each filter can be considered as a segment. To delete the resistor in filter 1, we first delete the segment containing filter 1, then recreate the segment, putting in it only the capacitor and line. The alternative choice is to let each basic circuit element be a segment, so deleting the resistor of filter 1 corresponds to deleting a segment. But then deleting filter 1 requires deleting 3 segments, whose names must first be found from the application data structure. Neither of these alternatives is really satisfactory: an application which performs picture modification at two different hierarchical levels is best served by a graphics language which provides for two levels of modification!
Languages designed to deal with an arbitrary number of hierarchical levels in a picture by means of a subpicture and instance mechanism also allow an arbitrary number of modification levels by subpicture modification. However, multilevel modification need not imply sub-picturing.
The number of modification levels provided by a language cannot exceed the number of naming levels, since the name forms the basis for a modification request. Some languages provide the same number of levels of naming and modification. There are/ however, occasions on which more naming than modification levels are useful. For instance, individual items in a menu may never be modified, yet they surely need to be named. The entire menu, and perhaps parts thereof as well, need to be named so they can be turned on and off. In this case, then, a naming level below the lowest modification level can be used. One might also find examples where a naming level above the lowest (or highest) modification level might be useful. In general, then a language with a limited number of modification levels should allow additional levels of naming below, above, and between modification levels.
It is desirable to organize the naming and structuring capabilities so their use is completely optional: the application programmer should need to understand and use the capabilities only if he truly needs them. Otherwise the language becomes a burden, rather than an aid, to its user.
These notions can be made more concrete by considering Figure 2, which shows the inherent hierarchical organization of some application's picture. Modification is required at those nodes marked with a circle, while only naming is needed at nodes marked with a triangle. Unmarked nodes need neither naming nor modification.
With a flexible graphics language, the inherent hierarchical structure can be directly mapped into appropriate multilevel names, with the required interspersing of naming levels at which modifications are possible. Otherwise, the application programmer is left the choice or mapping from the name space of the graphics language to the name space of the application.
In this section we survey and tabulate the naming and modification capabilities of several existing or proposed graphics programming languages. The languages are treated in (approximately) chronological order of their development. Each subsection gives a very short summary of the packages' background. While Figure 3 summarizes salient information, Figure 4 formally describes the names used with each language.
This display-independent language was developed in The Netherlands, at the Universities in Delft and Nijmegen. Implementations exist on the PDP-11/45 and IBM 360 and 370, for devices such as storage tube displays, Vector General displays, and various plotters. The latter version is written mostly in FORTRAN, and is thus relatively portable. From an overall viewpoint, it is the best of the languages described. However, it has but one level of picture modification, the picture segment. Naming is multi-level, and names can be specified in four ways. At the lowest level, individual graphics primitives can be named; the picture segment is of course named; groups of primitives can be named, with groups being nested; picture segments copied into another segment can be named, again providing a nested name. The latter two naming mechanisms can be arbitrarily intermixed in the naming hierarchy. Many segment attributes can be modified.
Omnigraph was implemented at the National Institutes of Health, on a PDP-10. It can be used with plotters, storage displays, and DEC and ADAGE refresh displays. Segments are used to provide single-level naming and modification. Segments can not be extended. An existing segment can be replaced by a new segment with the same name. The replacement occurs when definition of the new segment has been completed, thus allowing doublebuffering of segments.
This display-independent language was developed at Cambridge University and at the Computer-Aided Design Centre, Cambridge, England. Written in FORTRAN, it has been used with simple refresh displays, storage tube displays, and plotters. The modification capability deals with segments which can be created and deleted, but not extended. A few segment attributes can be modified. Within a segment, groups of picture primitives can be named, but nesting is not allowed.
Developed at the United States Military Academy and written (largely) in FORTRAN, GCS can be used with the IMLAC PDS-1, storage tube displays, and plotters. GCS has frames, which are the equivalent of segments. The frames are treated identically to Omnigraph's. GCS also has structures which are template (symbol) definitions. Three levels of nesting are allowed. However, since pick devices are not supported, the qualified names of picture parts are never used. Structure names are used only for defining and referencing structures. All names are character strings of maximum length 8. This might be a programmer inconvenience if names are used in the fashion described in section 1.
DIGS was designed at the University of North Carolina. A PDP-11/45 and Vector General implementation is underway. The system is meant to be used with devices ranging from plotters to refresh displays having a dynamic display space {image space) transformation capability. Two modification levels are provided. The segment is a collection of graphics primitives. The viewport is a collection of segments. Both can be created, deleted, and extended. A number of segment and viewport attributes can be modified. Additional naming is done with nested blocks. Blocks, segments, and viewports must be properly nested, but can be arbitrarily interspersed, constrained only by the relation between viewports and segments. A special lowest-level block can be used at the bottom of a naming hierarchy to allow space savings in the correlation table and/or display processor code. This becomes critical if there are hundreds or even a thousand separately named entities being displayed, as occurs with large molecules, for example. These lowest-level blocks do not have arbitrary application names assigned by the application programs. Rather, a collection of such blocks have (integer) names n, n+1, n+2, n+3, etc., where only n is determined by the application program. A picture might have several different collections of these blocks.
| Language Comparisons | |||||
|---|---|---|---|---|---|
| Language | Naming Levels |
Modification Levels |
Modification Operations |
Attributes which can be modified after picture is created |
Pick device supported |
| GPGS | Many: Block Picture Segment Primitive Copy |
One: Picture Segment |
Delete Extend Modify attributes |
Blink Color Depth cueing Image-Space Transformations Intensity Pen Detectability Visibility |
Yes, if available |
| Omnigraph | One: Segment |
One: Segment |
Delete Replace Modify attributes |
Visibility | No |
| GINO-F | Two: Segment Group |
One: Segment |
Delete Extent? Modify attribute |
Visibility | No |
| GCS | One: Frame |
One: Frame |
Delete Replace Modify attributes |
Visibility | No |
| DIGS | Many: Block Viewport Segment |
Two: Viewport Segment |
Delete Extent Modify attributes |
Blink Color Depth cueing Image-Space Transformations Intensity Pen Detectability Visibility |
Yes, if available |
GPGS
<gpgs name> ::= <block sequence><segment><block & copy sequence><primitive>
<block sequence> ::= <block><block sequence> / <block>
<block & copy sequence> ::= <block><block & copy sequence> / <copy> <block & copy sequence> / <block> / <copy>
<primitive> ::= INTEGER NAME / NULL
<segment> ::= INTEGER NAME / NULL
<block> ::= INTEGER NAME / NULL
<copy> ::= INTEGER NAME / NULL
OMNIGRAPH
<omnigraph name> ::= INTEGER NAME
GINO-F
<gino name> ::= <segment><group>
<segment> ::= INTEGER NAME / NULL
<group> ::= INTEGER NAME / NULL
GCS
<gcs name> ::= CHARACTER STRING (max.length 8)
DIGS
<digs name> ::= <block sequence><viewport><block sequence><segment><block sequence><lowest block>
<block sequence> ::= <block><block sequence> / <block>
<viewport> ::= INTEGER NAME / NULL
<segment> ::= INTEGER NAME / NULL
<block> ::= INTEGER NAME / NULL
<lowest block> ::= INTEGER NAME / NULL
The designer of a graphics programming language must make several important decisions concerning the semantics of picture naming and structuring. They are:
In the final analysis, the designer's decisions must take into account both ease of implementation questions, which have not been discussed here, and ease of use questions, which have been discussed.
1. Newman, W., & Sproull. R. "An Approach to Graphics System Design". Proc. IEEE 62 (4), {Special Issue on Computer Graphics): 471-483. April 1974.
2. Foley, J. & Wallace, V. "The Art of Natural Graphic Man-Machine Conversation". Proc. IEEE 62 (4), (Special Issue on Computer Graphics): 462-470. April 1974.
3. Caruthers, L., and van Dam, A. General Purpose Graphic Systems User's Tutorial, Katholieke Universiteit, Nijmegen, The Netherlands. July 1975.
4. Caruthers, L, Groot, D, Hermans, E., and Patberg, J. GPGS Reference Manual, Revision 1, February 1975. Technische Hoges-chool, Delft, and Katholieke Universiteit, Nijmegen, The Netherlands. Originally issued 1972.
5. Sproull, R. Omnigraph: Simple Terminal-Independent Graphics Software. Xerox Palo Alto Research Center, California. December 1973.
6. GINO-F, Computer Aided Design Centre, Cambridge, England.
7. GCS Graphics Programmers Manual. United States Military Academy, West Point, New York.
8. Primer on Computer Graphics Programming, United States Military Academy, West Point, New York. July 1973.
9. Foley, J., Hogan, R., & Dunham, C. DIGS - Display Independent Graphics System. Department of Computer Science, University of North Carolina, Chapel Hill, N.C. September 1975.