 |
Description  |
|
|
BACKGROUND OF THE INVENTION
A. Field of the Invention
The invention relates to a computer graphics workstation and, more
particularly, to a high performance, stand-alone graphics workstation
including a digital computer host and a graphics processing subsystem. The
invention provides efficient control structures to obtain a maximum
utilization of system resources and to effectively coordinate operation
among essentially data-driven, asynchronous components and thereby enable
both two-dimensional and three-dimensional high resolution graphics
displays.
B. Prior Graphics Systems
In recent years considerable advances have been made in the utilization of
computer systems to generate and visually display character and graphical
output data. The earliest systems were limited to two-dimensional displays
very often realized through the use of alphanumeric characters. The
graphics data generation capability of such early systems was limited and
certain character representations of predetermined size and shape were
stored in a character data memory and were transferrable to a display
memory by the user, when desired, to expand the display capability of the
system. A noteworthy advance in the computer graphics art involved the use
of a so-called "bit mapped" graphics display system to store output data
in a display memory. The "bit mapped" approach visualizes the output data
as a two-dimensional array of pixels, where each pixel corresponds to an
individual picture element in the display device. In a two-dimensional,
black and white graphics display, each pixel need only contain one bit of
information, i.e. either 0 or 1 to represent either black or white,
respectively. Accordingly, all of the pixels for a two-dimensional, black
and white display may be in the form of a two-dimensional map where the
bits of information in the map comprise the output data representing the
display device.
As should be understood, the graphic display of a three-dimensional object
in color, as opposed to a two-dimensional object in black and white
substantially increases the amount of output data required to represent
the display device and the processing capability of the graphics system
required to process the output data for display on a cathode ray tube. For
instance, with respect to color alone, eight bits of information per pixel
may be required to store information on the red, green and blue components
of the color and the intensity of the color for display.
The bit mapped approach was expanded by the prior art to a planar concept
wherein a three-dimensional array is visualized with separate spaced,
parallel planes, each plane corresponding to one attribute of the color
information, i.e., a red plane, a green plane, a blue plane and an
intensity plane. Each pixel comprises bits stored on the separate planes
and data processing requires the graphics system to retrieve the separate
bits of a pixel from among several memory locations.
When other attributes and display characteristics such as a
three-dimensional display, shading, surface reflective qualities, object
rotation, etc. are to be added to the graphics system, the memory
structure and capacity and data processing capability of the system must
be greatly expanded to represent and visually display an object. Such
capacity, structure and processing capability requirements have generally
limited the feasibility of implementing a high performance,
three-dimensional graphics system as a stand-alone, workstation-type
system particularly a graphics system with a multi-user capability. While
technological advances such as a 32 bit word microprocessor provide a
hardware basis for a stand-alone, workstation implementation for a
graphics system, there remain formidable data structure and processing and
system operational control requirements to achieve an effective high
performance graphics workstation system capable of processing multiple
application processes to permit a multi-user implementation. These
requirements have not been adequately addressed by the prior art.
SUMMARY OF THE INVENTION
Accordingly, it is a primary objective of the invention to provide a
stand-alone, graphics workstation that accomplishes the data structure and
processing and system operational control necessary for high performance,
high resolution graphics display with a multi-user capability.
Generally, the system of the invention comprises a host central processing
unit connected by means of an intermediate processing unit and a bus
arrangement to a graphics subsystem. The host subsystem is operable to
execute one or more application programs residing in the host to build
graphics data structures representing two dimensional and/or
three-dimensional objects to be displayed. The graphics data structures
are stored in a structure memory component in the graphics subsystem. The
three-dimensional graphics data structures are each implemented as a
hierarchical graphics data node structure in the structure memory. For a
thorough discussion of the principal concepts of interactive computer
graphics as generally employed by the system of the invention, reference
should be made to Fundamentals of Interactive Computer Graphics by J. D.
Foley and A. Van Dam (Addison-Wesley 1982).
Each node is defined as a fundamental memory unit to contain graphics data
or commands relating to the primitives, transformations, attributes and so
on of the graphics structure being built pursuant to a specific
application program residing in the host through the utilization of
preselected structured graphics routines stored in a memory library, also
in the host. An asynchronously operational structure walker in the
graphics subsystem traverses a special control structure stored in the
structure memory on a continuing basis to read and process requests for
traversal of the nodes of the graphics structures and to send the data and
command information contained in the nodes down a graphics pipeline for
processing, manipulation and display by the graphics processing components
of the graphics subsystem.
Pursuant to an important feature of the invention, a traversal control
function is partitioned among the host and graphics subsystem components
to accept requests for graphics structure traversals made by competing
application programs, and to subsequently schedule and perform such
traversals in a manner such that each of the competing graphics
applications views the graphics processing subsystem as its own and is
able to be executed with a most efficient utilization of the system
components. The hierarchical node memory structure, asynchronous memory
traversal and supervising traversal control functions together facilitate
a high performance three-dimensional display capability within the system
by providing an efficient allocation of system resources to store complex
graphics data structures and to process the graphics data structures in an
ordered and coordinated fashion. The system of the invention effectively
utilizes efficient coordination and control of ongoing, data driven,
asynchronous operation of the graphics subsystem components to place all
of the system resources equally at the disposal of a multiple of
application programs residing in the host to thereby enable a multi-user
functionality.
In accordance with known concepts of interactive computer graphics, the
invention makes use of a windowing system to provide a conversion from the
world coordinate system of the user to appropriate geometric coordinates
suitable for the physical display device of the workstation, i.e. the
cathode ray tube. A window is a rectangular array of pixels which may be
partially or wholly visible on the display device depending upon the size
of the window relative to the physical dimensions of the display screen.
Windows are also in a hierarchy with a "parent" window and sub-windows or
"children". Windows may be resized and sub-windows used for clipping by
the parent when a sub window is sized greater than the parent for detailed
display of portions of a display device defined by a graphics structure.
As will be described in more detail in the following description of a
preferred embodiment of the invention, a highly advantageous windowing
system for use in connection with the display of the graphic structures
generated by the application programs is the X Window System developed
under the auspices of the Massachusetts Institute of Technology as a
royalty free industry standard. Pursuant to the invention, the data
generated by the windowing system to create and define the window
coordinates and attributes is uniquely identified by the traversal control
system for correlation to the hierarchical graphics data node structure of
the object to be displayed within the rectangular array of the window.
Accordingly, the asynchronous traversal by the structure walker is able to
provide correlated graphics structure data and commands and window data to
the graphics processing components. The window data-graphics structure
correlation function of the traversal control further facilitates high
performance three-dimensional graphics display by permitting the
utilization of a highly effective window system such as the X Window
System which was developed primarily for use in two dimensional, bit
mapped graphics systems. The window identification data for correlation to
the three-dimensional node memory structures systematically merges a
three-dimensional functionality into the advantageous X Window System.
Pursuant to another significant feature of the invention, a separate two
dimensional, bitmap graphics system is provided in parallel to the three
dimensional components to process two dimension application programs. The
bit map graphics system has resources suitable for two dimensional
graphics including a bitmap memory and a rendering processor to traverse
bitmap data commands in structure memory. Moreover, the structure memory
is shared by the parallel three dimensional and two dimensional graphics
systems to serve both as the three dimensional graphics structure memory
and the two dimensional bit map memory. The rendering processor is also
shared by the parallel graphics systems to process both bit map graphics
and polygon rendering for three dimensional objects. In this manner, the
system resources having three dimensional capabilities are not
overburdened with processing tasks related to two dimensional displays and
functional capabilities which overlap both the three dimensional and two
dimensional processes are shared to reduce the number of hardware
components in the system.
Further operating efficiency is achieved by mapping address data relating
to the graphics subsystem components into the host system virtual memory.
The application processes residing in the host are thereby able to
communicate directly with the graphics subsystem components, as, e.g. the
structure memory, without the need of a direct memory access hardware
arrangement or device drivers.
Accordingly, the present invention achieves a high performance, three
dimensional graphics capability feasible in a stand-alone workstation
configuration by maximizing the processing capabilities of interactive
components. Hierarchical data structures are built in memory to permit the
definition of complex data structures representative of the primitives,
attributes and geometric transformations of three dimensional objects. The
asynchronous traversal of the data structures built in the memory together
with the traversal control functions coordinate and control the flow of
graphics data and commands to a graphics pipeline for ordered processing
and display in a manner that readily permits efficient processing and
display of a multiple of application processes.
For a better understanding of the above and other features and advantages
of the invention, reference should be made to the following detailed
description of a preferred embodiment of the invention and to the
accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a computer graphics system in accordance with
the present invention.
FIG. 2 is a block diagram of the graphics subsystem of FIG. 1.
FIG. 3 is a block diagram of the software organization for the computer
graphics system of the present invention.
FIG. 4 is a block diagram of the structure memory of the graphics of FIG.
2.
FIG. 5 is a block diagram of the organization of a node memory structure of
a graphics data structure pursuant to the present invention.
FIG. 6 is a block diagram of the BI bus memory map of the invention.
FIG. 7 is an exploded view block diagram of the reserved I/O space of the
block diagram of FIG. 6.
FIG. 8 is a block diagram of the graphics context and traversal model for
bitmap graphics processing.
FIG. 9 is a block diagram of the bitmap root.
FIG. 10 is a block diagram of the bitmap graphics context.
FIG. 11 is a block diagram of the bitmap cell array.
FIG. 12 is a block diagram of the bitmap display context.
FIG. 13 illustrates, in block diagram form, the connection between a
graphics context and the virtual root node of a data structure.
FIGS. 14a,b,c illustrate examples of various reference nodes.
DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION
System Overview
Referring now to the drawings and initially to FIG. 1, there is
illustrated, in block diagram form, the graphics workstation system
according to the invention. A first or host subsystem includes a host
central processing unit 10, a host memory 11, a tape controller 12, a
control processor 13 and a disk controller 14. The host subsystem
components 10, 11, 12, 13 are interfaced with one another by means of a
primary bus 15.
A preferred host subsystem for advantageous implementation of the teachings
of the invention comprises a Scorpio or Digital KA825 host processor
utilized as the host central processing unit 10, a 4-Mbyte MS820-BA memory
module as the host memory 11, a DEBNx Ethernet local area network and TK50
95 Mbyte streaming tape drive as the tape controller 12, an RD54 150-Mbyte
nonremovable-disk drive and an RX50 818-kbyte diskette drive as the disk
controller 14, an Aurora or Digital KA800 control processor to function as
the control processor 13 and a VAX Bus Interconnect or VAX BI synchronous,
time-multiplexed, 32-bit primary bus as the bus 15. The Scorpio processor
is a single board VAX processor which executes the complete VAX
instruction set and runs either the VMS or ULTRIX operating system and
applications. The Scorpio host processor, Aurora control processor, VAX BI
bus and other host subsystem components are marketed by the Digital
Equipment Corporation.
The control processor 13 is provided with a local or II 32 bus 16 to
interface the control processor 13 with a graphics subsystem 17. The
Aurora control processor 13 therefore acts as an interface between the
graphics subsystem 17 and the BI bus (primary bus) 15. The control
processor 13 also performs input and output pre-processing for interactive
perphireal devices such as a keyboard 18, a button box 19, a mouse 20, a
tablet 21 and a dial box 22 which are connected to the control processor
13 by means of a peripheral repeater box 23 through a serial data line 24,
as illustrated in FIG. 1. The peripheral repeator box 23 is utilized to
power the peripheral devices 18, 19, 20, 21, 22 at the monitor site and to
collect peripheral signals from the peripheral devices 18, 19, 20, 21, 22.
The peripheral repeater box organizes the collected peripheral signals by
packetizing the signals and sending the packets to the host central
processing unit 10 via the control processor 13. The peripheral repeater
box 23 also receives packets from the host processing unit 10 via the
control processor 13, unpacks the data and channels the unpacked data to
the appropriate peripheral device 18, 19, 20, 21, 22. For a more detailed
description of the input and output pre-processing functions of the
control processor 13 and the peripheral repeator box 23, reference should
be made to co-pending application Ser. No. 07/085,097, now U.S. Pat. No.
4,905,232, entitled Peripheral Repeater Box, filed on even date herewith.
Moreover, the Aurora control processor 13 is advantageously operable to
emulate a console for the Scorpio host central processing unit 10. The
console emulation is accomplished through the use of a serial data line 25
between the control processor 13 and the host central processing unit 10.
The Aurora control processor 13 may therefore be used to run diagnostics
and to debug the host subsystem without the need of additional equipment.
For a more detailed description of the console emulation function of the
control processor 13, reference should be made to copending application
Ser. No. 07/084,930, now U.S. Pat. No. 4,903,218 entitle Console Emulation
for Graphics Workstation, filed on even date herewith.
Pursuant to the preferred embodiment of the invention, the graphics
subsystem 17 comprise a Shadowfox graphics card set marketed by the Evans
& Sutherland Computer Corporation. The primary function of the graphics
subsystem 17 is to store graphics data structures built by a plurality of
application programs residing in the central processing unit 10 and to
process, manipulate and display the graphics data structures, as will
appear. Referring to FIG. 2, the Shadowfax graphics card set includes a
structure memory 26 interfaced with the control processor 13 by the local
II 32 bus 16. As will be described in more detail below, the structure
memory 26 comprises a 4-Mbyte memory to store the graphics data structures
built by application programs in the host central processing unit 10.
An asynchronously operational structure walker 27 is interfaced with the
control processor 13 by the II32 bus 16 and with the structure memory 26
by a structure memory bus 28. The structure walker 27 is a
special-purpose, 32 bit, bit-slice microprocessor that traverses the
graphics data structures stored in the structure memory 26 on a continuous
basis and sends the graphics data to the graphics pipeline processor 29
through line 30.
In accordance with the design and mode of operation of the Shadowfax
graphics subsystem, the graphics pipeline processor 29 organizes the data
received from the structure walker 27 into packets and performs graphics
transformations, matrix multiplication, clipping, perspective division and
viewport mapping. Accordingly, the graphics data structures, as processed
by the graphics pipeline processor 29, are transformed from the data
structure world space data as implemented by a user through an application
program in the host central processing unit 10 into displayable screen
space data relative to the physical dimensions of the screen upon which
the object is to be displayed.
A pair of data taps 31,32 examines each command and data packet received
from the output of the graphics pipeline processor 29 to determine whether
to send the packets further down the pipeline or to send the packets into
a graphics data manager 33, which forwards the packets to the appropriate
destinations. For example, X, Y, Z and color data packets are sent
directly to a delta/depth cue calculator 34 for calculation of line slope,
adjusted end points and status flags which describe the orientation of a
line. Color data and Z data are mixed with background colors to determine
relative red, green and blue values. The delta/depth cue calculator output
is sent to a pixel processor 35 for calculations in line drawing
algorithms. The graphics data manager 33 is used to load all valid draw
commands for loading into the pixel processor 35 and further operates to
buffer pipeline commands to a rendering processor 36 and to buffer data
from the rendering processor 36 to the pixel processor 35. As will be
described in more detail below, the rendering processor 36 is used in the
three-dimensional graphics process to render polygons.
The pixel processor 35 comprises sixteen identical processors which draw
antialiased and depth-cued lines using the endpoint and slope data
produced by the delta/depth cue calculator 34 as well as the polygon
rendering data provided by the rendering processor 36. The data from the
pixel processor 35 is sent to a frame buffer 37 which comprises a
1024.times.1024 pixel memory to contain the pixel image generated for the
system monitor 38. The frame buffer 37 provides a 1024.times.864, 60 hz
noninterlaced, raster-scan display format.
A video controller 39 receives the output from the frame buffer 37 and
converts the digital data to an analog signal to drive the monitor 38. In
the preferred embodiment, the monitor 38 comprises a Digital
VR290-DA/D3/D4 nineteen inch color monitor having a 1024.times.864 pixel
image area. The video controller 30 also contains a window look up table
to determine the video format for the display and a color look up table of
color values to define the red, green and blue components of the pixels. A
graphics data bus 40 is provided to interface the video controller 30 and
the various other components of the graphics subsystem 17, as illustrated
in FIG. 2.
Subsystem Mapping
Subsystem mapping refers to a technique utilized in the present invention
to allow the host processor 10 to directly access local RAM in the control
processor 13, structure memory 26 and various registers in the graphics
subsystem 17. These components are directly mapped into host system
virtual memory. Subsystem mapping is highly advantageous in the operation
of the system of the present invention, which is a "data-driven" machine,
as will appear.
In a conventional system, the method that is used to access hardware
external to a CPU is through the use of a device driver. A device driver
is a program which is specifically tailored to handle communications
between a host CPU and a specific device, i.e., memory, disk unit, tape
unit, etc. Thus, when the CPU wishes to access external device memory, it
invokes a device driver which either loads device memory directly through
the use of registers or sets up a direct memory access (DMA) operation.
For DMA, the driver locks down the user's data into physical memory (DMA
hardware requires that the data be locked into physical memory), sets up
source and destination addresses, and then invokes DMA hardware to get the
information transferred from source to destination.
Generally, this DMA approach is very acceptable. However, in a data-driven
machine such as the present invention, the cost of such approach would be
prohibitive. In the present graphics system, the host central processing
unit's main function is to send commands to the graphics subsystem 17.
This would require the host central processing unit 10 to utilize DMA
hardware for almost every operation it performed. Thus, it was with this
problem in mind that subsystem mapping scheme was devised.
The host central processing unit 10 shares the BI bus 15 with system memory
11 and the control processor 13 (See FIG. 1). The control processor's
local bus is the II32 local bus 16. On bus 16 are the local control
processor RAM (1 Mbyte), local registers, and components of the graphics
subsystem 17 including structure memory 26, structure walker 27, graphics
pipeline 29, graphics data manager 33 and rendering processor 36, pixel
processors 35 and the frame buffer 37. Note that not all the above
components are physically connected to the II32 bus (See FIG. 2). The
subsystem mapping scheme permits the host central processing unit 10 to
directly access II32 bus components.
To accomplish the direct access, the II32 bus 16 components are mapped into
the reserved I/O space of the BI bus (primary bus) memory map. FIG. 6
illustrates the BI memory map and FIG. 7 sets forth the details of the
reserved I/O space of the memory map of FIG. 6 where the components are
mapped. Upon system initialization, a device driver of the host central
processing unit 10 is invoked to perform the mapping. The first step it
performs is to set up two mapping registers in the control processor 13.
The mapping registers themselves are mapped into the host virtual address
space by the operating system. The first register, SADR, reflects the
starting address of the reserved I/O space in the BI memory map which is
20800000 HEX. The second register, EADR, reflects the ending address of
the reserved I/O space in the BI memory map which is 22000000 HEX. This is
accomplished by the device driver simply writing the start and end address
into the respective registers. The control processor 13 microcode
relocates its own local RAM to be within this address range. Once this
step is performed the physical mapping has been accomplished.
The next step that the host device driver performs is to map each II32
component (control processor RAM, structure memory 26 and graphics
subsystem 17 registers) into the host's system virtual address space
(S.phi.). This step is required because host software is incapable of
specifying physical addresses due to the inclusion of memory management
(MM) hardware on the host central processing unit 10. This hardware is
always running and screening addresses output by the host central
processing unit 10. Each address is assumed to be a virtual address,
therefore, the memory management hardware will always try to perform a
level of translation with that address to create a physical address. The
level of translation depends on whether the address is a system virtual
address or a process virtual address. This distinction is important
because each goes through a different translation table and translation
mechanism. Process virtual addresses are process specific and, if used for
purpose of present invention, every process would have to map to the
memory itself. This would give every process 4 MBytes of virtual address
space added to its own address space. Thus, in accordance with the present
invention, by selecting the II32 bus mapping to be system virtual
addresses, every process on the system can have access to this bus without
wasting memory resources. This also reduces the complexity of computations
used to determine physical addresses referenced by the graphics subsystem.
The last step that the host device driver performs is to unprotect S.phi.
pages that contain the II32 bus component's virtual addresses. By
unlocking these pages, any process on the system can access this system
virtual address space. Generally, S.phi. pages contain operating system
software and data that not every process can access. If an S.phi. page is
locked, the only way to access these virtual addresses is through the use
of system calls. This would add more complexity to the system and increase
the overhead. Thus by unlocking the S.phi. pages, the use of system calls
are eliminated.
After the host device driver has performed the steps described above, the
mapping is complete. Now each process has direct read/write access to any
of the mapped II32 bus components because these components are directly
mapped into the host's virtual memory. Each process can treat these
components as its own local memory. Therefore, the need for the use of
direct memory access hardware, device drivers or operating system calls is
eliminated.
Memory and Software Organization
From the above description, it should be understood that the graphics
subsystem 17 operates essentially in an asynchronous mode determined by
the asynchronous operation of the structure walker 27 which, as described
above, controls the flow of data from the structure memory 26 to the other
components of the graphic subsystem 17 through the continuous, sequential
traversal of the graphics data structures. The entire data flow through
the graphics pipeline is a function of the structure walker operation. As
will be described in more detail below, the host central processing unit
10 executes application programs to build graphics data structures in
hierarchical node structures representative of the three dimensional
objects to be displayed The node structures are stored in the structure
memory 26.
Conditional Nodes of a Graphics Data Structure
A graphics data structure consists of all the data which describes an
object and how it is displayed. A graphics data structure is a
hierarchical collection of nodes and the paths that connect them.
A node is a set of executable commands and data. The structure walker 27
traverses each node in order, following one or more pointers in each node
which link the node to the rest of the data structure. As it traverses the
node, the structure walker 27 extracts the commands and data and sends
them down the graphics pipeline, where they eventually result in the
display of the object defined by the data structure.
The data structure exists in a graphics environment defined by a graphics
context which will be described in more detail below. The graphics context
is connected to the system data structure through a virtual root node. A
virtual root node is simply the top-most node created by the user stemming
from the graphics context that was created by the system as shown in FIG.
13.
While building a data structure, the nodes that form the data structure
offer a wide range of functions i.e. from describing graphics primitives
to controlling traversal flow. Nodes are linked together in groups or
structures, by first calling the structure graphics routine (SGR):
SGR$BEGIN.sub.-- STRUCTURE (context);
and then calling the routines that create the node, and ending the sequence
with the routine SGR$END.sub.-- STRUCTURE (context, handle). The result is
that the pointers link the nodes together thus permitting the structure
walker 27 to traverse the nodes in their correct order as described below.
There are six node classifications for creating data structures. The first
three being:
Primitive nodes--Contain graphics data for vectors, polygons and strings.
Attribute nodes--Control the appearance of graphics primitives such as line
color, line pattern, shading and lighting
Transformation nodes--Describe how data is viewed on the screen.
Transformation nodes control the composition of matrices for graphics
transformation and normal transformation, and for the viewport. For
example, if a primitive node builds a cube, a transformation node can
scale and rotate it to make a brick.
The next three nodes are used to create advanced graphics data structures.
REFERENCE NODES
Hierarchical structures are built with reference nodes. A reference node
instructs the structure walker 27 to traverse another structure (referred
to as a "substructure" of the calling structure) before continuing with
the traversal of the structure containing the reference node. Reference
nodes operate in three modes: restore, no restore and branch. The
ref.sub.-- mode parameter of the routine that creates the node defines the
mode. These modes control the manner in which changes to the hierarchical
graphics state affect the traversal of other parts of the graphics data
structure.
Restore Mode
A reference node set to restore mode instructs the structure walker 27 to
save the current graphics state such as the current transformation matrix,
current attribute settings, etc. on a stack before traversing the
referenced substructure, then to restore that state when it has finished
traversing the substructure. As a result, changes in the hierarchical
graphics state made in a substructure do not affect the graphics state of
higher structures.
No-Restore Mode
A reference node set to no-restore mode redirects the structure walker 27
but does not instruct the structure walker to save the hierarchical
graphics-state and restore it upon returning to the reference node. This
mode is useful in at leaset two situations: When you are sure that a
referenced substructure will not change the graphics state and you want to
optimize traversal performance, and when you want changes in graphics
state at a lower hierarchical level to affect the traversal of an equal or
higher level of the data structure.
Branch Mode
As with the restore and no-restore modes, a reference node set to branch
mode redirects the structure walker traversal. However, when the structure
walker 27 finishes traversing the referenced substructure, it does not
return to the reference node; as a result, there is no need to save or
restore the graphics state. Branch reference mode is usually used with
conditional refercnce nodes which select among two or more substructures.
It is similar to the "GOTO" statement in a programming language.
Reference nodes are of two types: conditional and unconditional. Both node
types can perform restore, no-restore, and branch references. Conditional
nodes select one among two or more alternate traversal paths depending on
the value of one or two operands. For example, one type of conditional
node compares whether operands are equal to, greater than, or less than
each other. Unconditional nodes reference a single substructure with the
option of returning to the higher-level structure when the structure
walker 27 finishes traversing the referenced structure. FIGS. 14a-c give
examples of various kinds of references. Note that an "R", "NR", or "B" in
the right side of a reference node in FIGS. 14a-c indicates whether the
reference is of the restore, no-restore, or branch variety; in addition, a
circle is placed on the main reference pointer for no restore references
as an additional visual clue, and nodes following a branch reference are
shaded gray to show that the structure walker 27 never traverses these
nodes.
FIG. 14a shows a data structure featuring a Call/Restore node which
displays a red circle with a blue square. Because the reference node
restores state, the red line-color attribute does not affect the
line-color attribute set in the calling structure.
FIG. 14b shows a data structure featuring a conditional Test/No Restore
node which displays either a blue or a red square, depending upon whether
the operand tested by the Test/No Restore node is true or false. Because
the reference node does not restore state, the line-color attribute set in
the referenced structure does affect the color displayed by the calling
structure.
FIG. 14c shows a data structure featuring a conditional Compare/Branch node
which will display one of the three referenced substructures, depending on
the values of the operands compared by the Compare/Branch node. Note that
diagrams of substructures that cannot fit on the page are represented by
labeled frames.
Assignment Nodes
The assignment nodes set up and manipulate the values (operands) that are
tested by conditional reference nodes, permitting dynamic control of how a
given conditional reference node selects the path of traversal. The nodes
perform operations on data contained in structure memory locations. The
operations include move, logical OR (set bits), logical AND NOT (clear
bits) add, subtract, logical XOR.
Special Purpose Nodes
The special purpose nodes allow you to build custom nodes, use the same
data at different places in the structure, and store unused data. This
saves both structure memory space and editing time. Three special purpose
nodes are provided; a data node, a generic node, and an indirect node.
These nodes can provide increased flexibility by allowing the application
to tailor a data structure for its own needs.
Data nodes are provided to contain application data in fields which are
reserved for the application. The structure walker ignores data in the
data node, and follows the next pointer.
The generic node contains commands and data that go to the pipeline. The
structure walker 27 does not process information in a generic node, but
passes this node to the graphics subsystem 27 without recording changes in
the subsystem state. Generic nodes can change the state of the graphics
subsystem, but the structure walker does not restore changes made this
way.
The indirect node provides the ability to reference data in one node from
another node in the data structure. For example, an application can define
a node containing line color data and use indirect nodes to reference the
information in the indirect node. This saves memory and allows changes to
the color definitions without editing many nodes throughout the structure.
Any primitive, attribute, and transformation operations can be done using
indirect nodes.
Advanced graphic data structures are created by the routines shown in Table
1.
TABLE 1
__________________________________________________________________________
Advanced Graphic Data Structure Routines
SGR
Parameter
__________________________________________________________________________
1.
SGR$BEGIN.sub.-- STRUCTURE
context
2.
SGR$END.sub.-- STRUCTURE
context, handle
3.
SGR$CALL context, reference.sub.-- mode,
refere | | |
