$17[Introduction]
$p1
The idea of structuring 
$p
Several similar approaches have been suggested e.g. in [Foley 82] and 
[Lantz 84] but with a limited number of practical implementation
examples and less emphasis on their application to general interactive
computing environment. Recently work has been started on defining a standard
for a similar type of interface: Programmer's Hierarchical Interactive Graphics
Standard (PHIGS). A number of manufacturers .......
$p1
This document describes a simple structured interface
between the applications programs, system utilities and user interface
modules on one side and the graphics support component of the system
on the other. The interface fits easily into a 
variety of applications through supporting structured hierarchical dependencies
of objects both between and within the applications. 
It provides flexible workspaces for the
individual applications while presenting a manageable and uniform
front to the graphics support subsystem. 
$p1
The interface is a directed graph, residing in the main system memory
where client processes in the system can manipulate their own allocated
sections on one side and a separate evaluation process caters
for the creation of the resulting images on the other as shown in a
paraphrase of a windowing system below. 
The evaluation process
can be viewed as a function taking the graph as an argument and producing
the image as a value with the "propagation time" through the function
dependent on the performance of the graphics subsystem. 
The interface was implemented in two ...... (year?).
$figure'A paraphrase of nested windows'
$p1
The top part of the graph is usually under the supervision of the system window
manager, while its exit edges provide linkage to applications subgraphs
running within their allocated subwindows. Such hierarchy may reoccur 
recursively
where an application may have its own subwindow manager maintaining its
menu, workspace and other areas of activity.
$p1
The image is computed through a depth-first scan of the descriptor structure,
where for each of the nodes, its local evaluation environment is saved,
prior to following any of the downwards edges and subsequently restored 
on return. The ordering of the exit edges defines the eventual overlap of
the graphical objects created by their execution.
Evaluation is terminated after the execution along the last vertical
edge of the node, at which it was invoked, thus allowing nested invokation
of selected substructures.
$p1
The speed of generating new images is strongly
dependent on the complexity of the graph and
on whether the evaluation process has to share the processor with other
processes, or it can have its own customised evaluation engine.
Depending on certain properties of the graph, like being acyclic or even
a tree, various optimisation techniques allow for only parts of the
graph to be scanned, still yielding a valid picture.
$b2
$17[Graph construction]
$p1
The graph is constructed out of fixed-format nodes with two exit edges:
a $I[vertical] and a $I[horizontal] one. The vertical
edge is used to represent image hierarchy and the horizontal edge
supports linkage of multiple image components at the same level of
hierarchy.
$p1
Leaf nodes in such a directed binary graph i.e. those with no vertical 
exit edges are generally
responsible for the final drawing operations, and they can invoke 
operations like filling a polygon, drawing a stright line, drawing a
string of characters etc. These are executed with the necessary current
environmental attributes like: colour, font, scaling, clip boundaries etc. 
Some of the drawing
operations can have impact on the environment, like deposition of
character strings moves the working coordinates along the string baseline.
Non-leaf nodes are generally responsible for the composition of the picture
out of subordinate ones as well as for the necessary modifications of the
environment, like coordinate manipulations, colour and font selection etc.
Some of these operations, like moving or scaling are cummulative
along the vertical paths in the graph; others like font or colour selection
are nested.
There are also some general control nodes, which allow the user
to exercise control over the evaluation process.
$figure'Format of the node'
$14[Format of the node]
$p1
Each binary node consists of 11 consecutive 16-bit half-words, where
the first two bytes contain the instruction code and the execution flags
of the node. They are followed by a long-word of argument field, and
then two long-words, where on exit, the evaluation process deposits the 
relative
dimensions of the bounding box for the image subordinate to the node.
These dimensions are relative to the environmental working
$I[(workX,workY)] coordinates on the entry to the node. 
The argument field can contain
a 32-bit pointer, two 16-bit geometrical or indexing arguments, or
for some single-argument operations only the first half-word is taken into
account.
The last two long-words contain downwards and rightwards pointers of
the exit edges, with execution flags $I[Down] and $I[Right] indicating their
validity. Flag $I[Pointer] when 1 represents indirection in fetching
of arguments.
$p1
We will describe further details of the nodes while presenting a number of
example applications. 
In all illustrations, nodes will be denoted with their associated opcodes
and those of the flags, which are set to 1. Values of 1 for the
$I[Down] and $I[Right] flags are indicated by the presence of the 
corresponding exit edges.