REGISTER  |  SIGN IN
United States Patent5097411
Doyle , ; et al.March 17, 1992
Title
Graphics workstation for creating graphics data structure which are stored retrieved and displayed by a graphics subsystem for competing programs
Abstract
A method for operating a computer graphics system to build custom nodes containing commands and data information that is stored in a data structure in the graphics subsystem. A host processor calls routines which build the custome nodes. A structure walker traverses the data structure and extracts the information from the data structure to pass it to the graphics subsystem for display. The use of custom nodes increases the flexibility of advanced graphics data structures bny allowing the creation of other data structures during execution of a first data structure.
Inventors:Doyle; Peter L. (Northboro, MA), Ellenberger; John P.  (Groton, MA), Jones; Ellis O.  (Andover, MA), Carver; David C.  (Medway, MA), Dipirro; Steven D.  (Holliston, MA), Gerovac; Branko J.  (Marlboro, MA), Armstrong; William P.  (Salt Lake City, UT), Gibson; Ellen S.  (Salt Lake City, UT), Shapiro; Raymond E.  (Marlboro, MA), Rushforth; Kevin C.  (West Valley City, UT), Roach; William C.  (Salt Lake City, UT)
Assignee:Digital Equipment Corporation (Maynard, MA)
Appl. No.:258398
Filed:October 17, 1988
Current U.S. Class:345/522 345/501 
Current International Class:G06T 17/00 (20060101)
Field of Search:340/724,747,748,725 364/518,2MSFile,9MSFile
U.S. Patent Documents
3916387October 1975Woodrum
4010451March 1977Kibble et al.
4149240April 1979Misunas et al.
4236206November 1980Strecker et al.
4240139December 1980Fukuda et al.
4303986December 1981Lans
4315310February 1982Bayliss et al.
4318184March 1982Millett et al.
4373182February 1983Schultz et al.
4395758July 1983Helenius et al.
4413315November 1983Kurakake
4428065January 1984Duvall et al.
4432053February 1984Gaither et al.
4466060August 1984Riddle
4471463September 1984Mayer
4509115April 1985Manton et al.
4541045September 1985Kromer, III
4555700November 1985Conu is et al.
4555775November 1985Pike
4591845May 1986Komatsu et al.
4613852September 1986Maruko
4618859October 1986Ikeda
4631690December 1986Corthout et al.
4653020March 1987Cheselka et al.
4677550June 1987Ferguson
4688032August 1987Saito et al.
4694404September 1987Meagher
4700181October 1987Maine et al.
4700320October 1987Kapur
4710761December 1987Kapur et al.
4710763December 1987Franke et al.
4731606March 1988Bantz et al.
4737921April 1988Goldwasser
4742451May 1988Bruckert et al.
4757470July 1988Bruce et al.
4760390July 1988Maine et al.
4803477February 1989Miyatake
4805134February 1989Calo et al.
4807142February 1989Agarwal
4809170February 1989Leblang
4811240March 1989Ballou
4813013March 1989Dunn
4868766September 1989Oostorholt
4870561September 1989Love
4897636January 1990Nishi
4928247May 1990Doyle
4935730June 1990Kosuka
4947257August 1990Fernandez
4949180August 1990Miles
Primary Examiner: Lee; Thomas C.
Assistant Examiner: Coleman; Eric
Attorney, Agent or Firm:Kenyon & Kenyon
Parent Case Text


This is a division of application Ser. No. 184,406 filed Apr. 20, 1988, which is a continuation of application Ser. No. 085,081 filed Aug. 13, 1987.
Claims

What is claimed is:
1. A computer implemented method of displaying graphic information by a plurality of competing application programs via advanced graphic data structures comprising the steps of:
(a) calling and executing routines by a host processor to build at least one custom node containing commands and data information with said data information being stored i a first data structure existing in a graphics subsystem and said custom node being stored in said graphics subsystem, said data information being used for creating a display at a particular time, the custom node being used by the host processor to build a second data structure for creating a second display at another particular time;
(b) scheduling with the host processor asynchronous traversal of the custom node by completing application programs being run by the host so each said completing application program views the graphics subsystem as its own absent the other completing programs;
(c) extracting, during asynchronous traversal of the custom node based upon the scheduling at step (b) the data information from first and second data structures and passing the data information to the graphics subsystem for display.

2. The method according to claim 1 wherein the step of passing the information is carried out by a structure walker which controls the flow of the information passed to the graphics subsystem for display.

3. A method according to claim 1 wherein the custom node includes a generic node which sends the commands and data to the graphics subsystem without effecting the state of the data structure.
Description


BACKGROUND OF THE INVENTION

A. Field of the Invention

This invention relates to a computer graphics workstation and, more particularly, to a high performance, stand-along 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 pixels for a two-dimensional, black and white display 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 work 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 of 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 i 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.

Hierarchical graphics data structure are built using reference nodes. A reference node instructs the structure walker to traverse another substructure of the calling structure before continuing with the traversal of the structure containing the reference node. Reference nodes can be either conditional or unconditional. Conditional nodes select one among two or more alternate traversal paths depending on the value of one or two operands.

Hierarchical graphics data structure are built using reference nodes. A reference node instructs the structure walker to traverse another substructure of the calling structure before continuing with the traversal of the structure containing the reference node. Reference nodes can be either conditional or unconditional. Conditional nodes select one among two or more alternate traversal paths depending on the value of one or two operands.

Other nodes used to create advanced graphics data structures include assignment nodes and special purpose nodes. Assignment nodes set up and manipulate the values that are tested by conditional reference nodes thus permitting dynamic control of how a given conditional reference nodes select the path traversal. Special purpose nodes allow the building of custom nodes which use the same data at different places i the structure and store unused data. Special purpose nodes provide increase flexibility by allowing the application to tailor a data structure for its own needs.

The conditional reference nodes used to create advanced graphics data structures redirect the traversal path of the structure walker based upon either true/false test or a value comparison. The test performed by the conditional reference nodes uses values stored in one or two operands in the node. The value of the operands are set by the manipulations of the assignment nodes. The operands are retrieved by using one of four access modes.

The access modes are specified by constants set in the mode parameters of the routine that creates the node. The access modes tell the system how to interpret the operational specifier parameter argument of the routine. The test performed by the conditional reference node uses the value of the operand at the time of traversal.

Operand access modes are important in the use of assignment and reference nodes. By using the access modes, assignment nodes create additional data or general data in the structure memory. The reference nodes can then branch according to their data created. The use of special purpose nodes allows the data to be sent to the graphics subsystem. In this way, the data structure in effect writes a "subprogram" and executes it during the traversal of the structure. This provides a more general functionality as well as a more efficient use of memory resources.

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 subsystem 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 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 interface with one another by means of a 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 RXb 50 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 bus as the bus 15. The Scorpio processor in 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
15. The control processor 13 also performs input and output pre-processing for interactive peripheral 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 repeater 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 repeater box 23, reference should be made to co-pending Application Ser. No. 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. 084,930, now U.S. Pat. No. 4,903,218 entitled Console Emulation for Graphics Workstation, filed on even date herewith.

Pursuant to the preferred embodiment of the invention, the graphics subsystem 17 comprises 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 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 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 below, the rendering processor 36 is used in the three-dimensional graphics processor 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, rastar-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 VR2900DA/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 control processor 13 (See FIG. 1). The control processor's local bus is the II32 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 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 220000000 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.0.). This step is required because host software is incapable of specifying physical addressed 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.

This last step that the host device driver performs is to unprotect S.0. 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.0. pages contain operating system software and data that not every process can access. If an S.0. 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.0. 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 had 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)L

SGRSBEGIN--STRUCTURE (context):

and then calling the routines that create the node, and ending the sequence with the routine SGRSEND--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 instructures 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 least two situation: 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 lever 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 reference 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-lever structure when the structure walker 27 finishes traversing the referenced structured. 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 node 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 267
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 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, bu 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, reference.sub.-- handle, handle 4. SGR$TEST context, reference.sub.-- mode, mode, opspec, true.sub.-- handle, false handle, handle 5. SGR$TEST.sub.-- AND.sub.-- CLEAR context, reference.sub.-- mode, mode, opspec, true.sub.-- handle, false handle, handle 6. SGR$COMPARE context, reference.sub.-- mode, mode1, mode2, opspec2, less.sub.-- handle, equal.sub.-- handle, greater.sub.-- handle, handle 7. SGR$CASE context, reference.sub.-- mode, mode, opspec, count, otherwise handle, case.sub.-- handles, handle 8. SGR$TEST.sub.-- SET context, reference.sub.-- mode, mode1, opspec1, mode2, opspec2, true handle, false.sub.-- handle, handle 9. SGR$TEST.sub.-- CLEAR context, reference.sub.-- mode, mode1 opspec1, mode2 opspec2, true HANDLE, FALSE.sub.-- handle, handle 10. SGR$MOVE context, mode1, opspec1, mode2, opspec2, handle SGR$MOVE.sub.-- BLOCK context, size, mode1 , opspec1, mode2, opspec2, handle SGR$MOVE.sub.-- MASK context, mask, mode1, opspec1, mode2, opspec2, handle SGR$SET.sub.-- BITS context, mode1, opspec1, mode2, opspec2, handle SGR$CLEAR.sub.-- BITS context, mode1, opspec1, mode2, opspec2, handle SGR$ADD context, mode1, cpspec1, mode2, opspec2, handle SGR$SUB context, mode1, cospec1, mode2, opspec2, handle SGR$XOR context, mode1, opspec1, mode2, opspec2, handle SGR$GENERIC context, size, data, handle SGR$INDIRECT context, to.sub.-- handle, handle 20. SGR$INDIRECT context, to.sub.-- handle, handle SGR$DATA context, size, data, handle __________________________________________________________________________

The use of conditional nodes provide the user with greater flexibility in the creation of advanced data structures. Referring to Table 2 above, conditional nodes are created by calling routines 4-9 assignment nodes by the routines 10-17 and special purpose nodes by the routines 18-21.

Conditional Reference Nodes

Conditional reference nodes redirect the traversal path of the structure walker 27 based upon either a true/false test or a value comparison. Based on the outcome of the test, the conditional reference node instructs the structure walker 27 to follow a predetermined traversal path associated with the test result.

The test performed by the conditional reference nodes use values stored in one or two operands (depending on the node type) in the node. The value of these operands are set by the manipulations of the assignment nodes thus permitting dynamic control of how a given conditional reference node selects the path of traversal. These operands are retrieved by use of the four access modes described in Table 2 and are the subject of the present invention.

The access modes are specified by constants set in the mode, model or mode2 parameters (depending on the node type) of the routine that creates the node. The access modes tell the system how to interpret the operational specifier (opspec) parameter argument of the routine. The model parameter specifies the access of opspec1, and mode2 specifies the access of opspec2.

TABLE 2 ______________________________________ Operand Access Modes Constant Mode Description ______________________________________ SGR$K.sub.-- IMMEDIATE The operand is the current value stored as the operand specifier (opspec) a command parameter in the node. SGR$K.sub.-- ABSOLUTE The operand is contained in the structure memory virtual address stored as the operand specifier in the node. SGR$K.sub.-- REGISTER The operand is contained in one of three registers numbered (0-2). These registers are special locations in structure memory which can be saved and restored as part of the hierarchical graphics state. All three registers can be used to store an operand, but register 0 must be reserved for use as a base-address register when displacement mode is used. SGR$K.sub.-- DISPLACEMENT The operand is located in the structure memory virtual address obtained by adding the value stored in the operand specifier to the contents of register 0. ______________________________________

The test performed by the conditional reference node uses the value of the operand at the time of traversal; this may be the operand passed to the node-building routine when it was called, or an assignment node may have changed the value of the operand as detailed below.

The Operand access modes are important in the use of assignment and reference nodes. By use of the access modes, assignment nodes can create additional data or general data in the structure memory. The reference nodes can then be made to branch according to the data created. The use of special purpose nodes allows the data to be sent to the graphics subsystem 17. In this way, the data structure can in effect write a "subprogram" and execute it during the traversal of the structure. This provides for a more general functionality as well as a more efficient use of memory resources than present methods whereby conditional branching takes place of a fixed location such as a condition register.

Examples of conditional reference and assignment nodes are as follows:

TEST

TEST.sub.-- AND--CLEAR

COMPARE

CASE

TEST.sub.13 SET

TEST.sub.13 CLEAR

The test node is created by the routine:

SGRSTEST (context, reference.sub.-- mode, mode, opspec, true handle, false.sub.13 handle, handle)

This node performs a simple true/false test on an operand and directs the structure walker to traverse one of two substructures depending on whether the results of the test is true (nonzero) or false (zero). the value of the operand remains unchanged.

The test.sub.-- and.sub.-- clear Node is created by the routine: SGRSTEST.sub.13 AND CLEAR (context, reference.sub.-- mode, mode, opspec, true.sub.-- handle, false.sub.-- handle, handle).

This node performs a true-false test similar to the test node. It first tests the value of an operand, then sets the value of the operand to zero (false). Because it clears the operand (that is, sets it to a false condition), on subsequent traversal this node would direct the structure walker 27 down the path associated with a true condition only if the operand were reset to true once again.

The compare node is created by routine:

SGRSCOMPARE (context, reference.sub.-- mode, model, opspec1, mode2, opspec2, less.sub.-- handle, equal.sub.-- handle, greater handle, handle)

This node performs a test on two operands to determine which, if either, is greater, and directs the structure walker to traverse one of three substructures, depending on whether the first operand is less than, equal to, or greater than the second operand. The operands remain unchanged.

The case node is created by the routine:

SGRSCASE (context, reference.sub.-- mode, mode opspec, count, otherwise.sub.-- handle, case.sub.-- handles, handle

This node tests the value of an operand and directs the structure walker to traverse a substructure assigned to that value; if the value of the operand is not associated with substructure, then a default substructure is traversed. The operand remains unchanged. This node allows the selection of a number of traversal paths, depending on the value of the operand in the node. The test.sub.-- set and test.sub.-- clear Nodes are created with the routines:

SGRSTEST.sub.-- SET (context, reference.sub.-- mode, model, opspec1, mode2, opspec2, true.sub.-- handle, false.sub.-- handle, handle)

SGRSTEST.sub.-- CLEAR (context, reference.sub.-- mode, model, opspec1, mode2, opspec2, true.sub.-- handle, false.sub.-- handle, handle)

These nodes allow the performance of mask-like tests to determine which parts of the graphics data structure will be traversed. The test.sub.-- set determines if the bits which are set in the first operand are also set in the second operand. If the test result is true (that is, if the logical AND of the two operands is equal to the first (operand), then the first substructure is traversed; if false, the second substructure is traversed.

The test.sub.-- clear determines if the bits which are clear in the first operand are also clear in the second operand. If the test result is true (that is, if the logical AND of the two operands is equal to 0), then the first substructure is traversed; if false, the second structure is traversed.

For instance, a mask could be stored in register 1 which represents whether certain features are "enabled" or "disabled. " A test.sub.-- set node could be used to test whether a feature was enabled and, if so, direct the structure walker to traverse the appropriate substructure.

Assignment Nodes

Assignment nodes provide additional flexibility in the use of conditional reference nodes by modifying their operands as a result of data structure traversal. In other words, the condition to be tested by the conditional reference nodes can be different at each traversal, depending on how assignment nodes are used to modify their operands.

Assignment nodes perform arithmetic or bit operations on the operands used by conditional reference nodes. The following are assignment nodes:

MODE

MOVE.sub.-- BLOCK

MOVE.sub.-- MASK

SET.sub.-- BITS

CLEAR.sub.-- BITS

ADD

SUB

XOR

The move node is created by the routine:

SGRSMOVE (context, mode1, opspec1, mode2, opspec2 handle)

This node performs a longword move operation, from the location described by onspec1 to the location described by opspec2.

The move.sub.-- block node is created with routine:

SGRSMOVE.sub.-- BLOCK (context, size, model, opspec1, mode2, opspec2, handle)

This node performs a move operation on a block of longwords indicated by the size parameter, from the location described by opspec1 to the location described by opspec2. The move.sub.-- mask node is created with routine:

SGRSMOVE.sub.-- MASK (context, mask, mode2, opspec2, handle)

The node sets the bits specified by the mask parameter to the same values in the second operand as their corresponding values in the first operand.

The set.sub.-- bits node is created with the routine:

SGRSSET.sub.-- BITS (context, model, opspec1, mode2, opspec2, handle)

This node performs a logical OR operation, setting all the bits in the second operand which are set in the first.

The clear.sub.-- bits node is created with the routine:

SGRSCLEAR.sub.-- BITS (context, model, opspec1, mode2 opspec2, handle)

This node performs a logical AND NOT operation, clearing all the bits i the second operand which are set in the first.

The add node is created with the routine;

SGRSADD (context, model, opspec1, mode2, opspec2, handle)

this node performs a signed longword addition of operand 1 and operand 2. The result of the addition is stored in the second operand.

The sub node is created with the routine: SGRSSUB (context, model, opspec1, mode2, opspec2, handle)

This node performs a signed longword subtraction, subtracting operand 1 from operand 2 and storing the result in the second operand.

The xor node is created with the routine:

SGRSXOR (context, model, opspec1, mode2, opspec2, handle)

This node performs a logical XOR operation using the two operands and storing the result in the second operand, Note that if all the bits in the second operand are set, a logical NOT is performed.

Examples of special purpose nodes are given below.

The routines that build special-purpose nodes increase the flexibility and efficiency of the graphics data structure. There are three nodes as follows:

Generic

Indirect

Data

The generic node is created by the routine:

SGRSGENERIC (context, size, data, handle)

The generic node provides the means of sending commands or data, or both, through the graphics pipeline; in effect, creating a custom node. The commands that are used should not affect the hierarchical graphics state.

The indirect Node is created by the routine:

SGRSINDIRECT (context, to.sub.-- handle, handle)

The indirect node references data in another node. An application may insert indirect nodes that reference predefined data. The routine inserts the node type of the referenced node into the indirect node being created, as well as a pointer directing the structure walker to traverse the data contained in that node. This creates a node identical to the referenced node, but located in a different part of the graphics data structure. This routine is useful in building attribute tables. This saves memory, and limits the number of changes when editing.

The data Node is built by the routine:

SGRSDATA (context, size data, handle)

The data node is used for storage, or to hold data to be used by the application program. During structure traversal, the structure walker 27 passes over data in this node, but follows the next pointer.

The primary function of the structure walker 27 is to accurately traverse the nodes of the data structures in the proper sequential order and to provides each node type correctly. The processing function of the structure walker 27 involves execution of node commands relating to further traversal of the nodes of the structure or conditional branching to alternative node branches in the node structure and the sending of the data and command information contained in the traversed nodes to the graphics pipeline processor 29 for processing, as described above.

Software Organization

Referring now to FIG. 3, there is illustrated a block diagram of the software organization of the graphics system of the invention. An application 100 contains requests relating to the building of graphics data structures. Many applications 100
are present in the host central processing unit 10 to build multiple graphics data structures for manipulation and display by the graphic subsystem 17. In the preferred embodiment, the X Window System is implemented to perform the windowing and bit map graphics requests contained in the application program 100. The X window system is fully described in publications published by the Massachusetts Institute of Technology such as Xlib--C Language X Interface Protocol Version 11 by Jim Gettys, Ron Newman and Robert W. Scheifler and X Window System Protocol, Version 11 Beta Test by Robert W. Scheifler. These publications are available to use copy, modify and distribute for any purpose without fee. Information on the X Window System may be obtained from the Massachusetts Institute of Technology Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts 02139.

The X Window System is based upon a client - server model. The application 100 is the client which accomplishes its work by communicating its requests to a server process 101. The server 101 performs the requested function and returns a status to the client application 100. The major components of the X window System are an X protocol 102, the server 101 and an XLib 103.

The X protocol 102 defines a model for communication between a server 101 and a client 100, and also defines the model for the graphics subsystem 17. The model consists of several objects which interact in specified ways. The most fundamental object is the window, a rectangular array of pixels which may or may not be (partially) visible on the monitor 38 at a given time. Windows are in a hierarchy: in other words, windows may have sub-windows. When a sub-window is displayed, it will be clipped against its parent. The monitor is the root of the hierarchy. Each window has a unique ID, an optional property list, and may be manipulated by a process 100 other than the creating process 100. The X protocol 102 neither imposes nor encourages limits on the number of windows in existence (i.e. windows are "cheap"). Other objects defined by the X protocol 102 include

Color Maps: associations between pixel value and colors

pixmaps: a rectangular array of pixels

tiles: a special kind of pixmap used to fill regions and define cursors

polylines: a set of related points which are displayed in a window according to specified criteria

(glyph) fonts: a set of bitmaps which correspond to alphanumeric characters (includes proportional fonts)

The X protocol 102 also defines a number of events. The events are detected by the server 101 as, e.g., inputs received from peripheral devices via the control processor 13 and peripheral repeater box 23 (see FIG. 3) and are passed on to clients
100. Examples of events are

Exposure events: part of a displayed window which was previously occluded has now been uncovered

Keyboard events: a key on the display has been pressed

Button Events: a button on a pointing device (e.g. mouse 20) has been depressed.

Clients 100 only receive notification of events in which they have explicitly expressed interest. Events are maintained in a time-ordered queue, and can be received by clients 100 either synchronously or asynchronously.

The X Server 101 mediates communication between client applications 100 and the graphic subsystem 17. Each client 100 establishes a connection to the server 101 via a communications protocol. A client 100 will send commands to a server 101 to perform functions such as drawing into a window, loading fonts, manipulating the color map, expressing interest in certain events, etc. The X Server 101 will then perform the requested functions, by, e.g., sending commands to the graphics subsystem 17
via a node in the structure memory 26.

A server 101 is always located on the same machine as the monitor 38. It is possible for there to be more than one server per machine, and for a server to control more than one monitor 38. Each monitor 38, however, may be controlled by at most one server.

The server 101 provides a device independent (DDI) program which interfaces with a device dependant (DDX) program for communication from the X Window system to the specific system of the invention upon which the windowing system is operating. With respect tot he present invention, the most significant feature of the DDX is the three dimensional display context functions of the traversal control implemented through a display manager 106 in the windowing server 101 to connect a window defined by a client application 100 to the three dimensional graphics structure built by the client application 100 in the structure memory 26, as will appear. In this manner, a three dimensional functionality is merged into the X Window System.

Xlib 103 is the Client's interface to an X Server. It is a procedural interface which corresponds to the functions provided by the underlying X protocol 102. Thus, there are calls to create windows, draw into them, etc. Since Xlib is a procedural interface, it is designed to be called from higher-level languages.

A window manager 104 is an application which implements a human-workstation interface. It typically provides a user with the ability to create, move, resize, iconify, and destroy windows. These actions are indicated by using the mouse 20 as a pointing device, in conjunction with button clicks and keyboard hits. Although the X protocol 102 does not specify any one window manager, there are currently several from which to choose. X provides the necessary features for a customized window manager implementation. This means that a window manager is not necessary for X applications to run and it is possible to have multiple window managers (not at the same time on the same display, however).

A graphic package may be layered on top of the X Window System, as, for example, a GKS o/b package. In the present invention a graphics package is used for two dimensional displays through bit map graphics. Indeed, the X Window System was developed for use in connection with bit map graphics systems. The bit map graphics contexts and command queues are processed by the rendering processor 36, as will appear.

Pursuant to the invention, three dimensional graphics data structures are built by the application clients 100 directly through structured graphics routines 105 (SGR) which are provided in the host subsystem. The applications 100 utilize the various structured graphics routines 105 as required to build specific graphics data structures. The structured graphics routines execute routine requests made by the application 100 and build appropriate linked nodes in the structure memory 26.

The following are several examples of structured graphics routines which may be provided in the host subsystem for implementations of graphics data structures.

EXAMPLE 1

SGRSBEGIN.sub.-- STRUCTURE

FORMAT

SGRSBEGIN.sub.-- STRUCTURE(context)

ARGUMENTS

context

The identifier of the graphics context for this subroutine call. The context argument is the address of an unsigned integer that contains the identifier of the graphics context block.

PURPOSE

To begin a structure.

DESCRIPTION

A structure is a group of nodes linked together. After calling SGRSBEGIN.sub.-- STRUCTURE, all nodes created with the same context are added to the end of the structure. No nodes are created by SGRSBEGIN.sub.-- STRUCTURE. A structure is terminated by SGRSEND.sub.-- STRUCTURE.

The information for linking nodes is stored in the graphics context referenced by the context argument, so it is possible to build multiple structures at the same time using multiple contexts.

Calling SGRSBEGIN.sub.-- STRUCTURE for a context which is not building a structure is an error.

It may be desirable to begin each structure with a node that does nothing, such as a data node or a disabled node. This permits the structure to be referenced by multiple nodes are still permits replacement of the first true node in the structure.

EXAMPLE 2

SGRSCOLOR

FORMAT

SGRSCOLOR(context, red, green, blue, color) ARGUMENTS

context

The identifier of the graphics context for this subroutine call. The context argument is the address of an unsigned integer that contains the identifier of the graphics context block.

red

The red intensity of the color. The red argument is the address of an unsigned longword in F.sub.-- floating format that contains the value for red intensity. This value is in the range 0.0 no (intensity) to 1.0 (full intensity).

green

The green intensity of the color. The green argument is the address of an unsigned longword in F.sub.-- floating format that contains the value for the green intensity. This value is in the range 0.0 (no intensity) to 1.0 (full intensity).

blue

The blue intensity of the color. The blue argument is the address of an unsigned longword in F.sub.-- floating format that contains the value for the blue intensity. This value is in the range 0.0 (no intensity) to 1.0 (full intensity).

color

The color longword returned by the routine. The color argument returns the address of an unsigned longword that returns the value for color.

PURPOSE

To create a color word.

DESCRIPTION

This routine creates a color composed of red, green, and blue intensities. The format of a color word is shown in following scale.

Color is passed as an argument to SGRSSET.sub.-- BACKGROUND, SGRSSET.sub.-- LINE.sub.-- COLOR, and SGRSSTATUS.

RELATED ROUTINES

SGRSSET.sub.-- BACKGROUND

SGRSSET.sub.-- LINE.sub.-- COLOR

SGRSSET.sub.-- SURFACE.sub.-- COLOR

SGRSSTATUS.

EXAMPLE 3

SGRSVECTOR

FORMAT

SGRSVECTOR (context, vertex.sub.-- format, edit.sub.-- flags, count, vertex.sub.-- array, handle)

ARGUMENTS

context

The identifier of the graphics context for this subroutine call. The context argument is the address of an unsigned integer that contains the identifier of the graphics context block. vertex.sub.-- format

Flags declaring the format of the vertices passed by the vertex.sub.-- array argument. The vertex.sub.-- format argument is an unsigned longword that contains the following flags:

______________________________________ Flag Description ______________________________________ SGR$M.sub.-- STATUS When set, each vertex in the array contains a status word. SGR$M.sub.-- X.sub.-- When set, each vertex in the array contains a coordinate for x. SGR$M.sub.-- Y When set, each vertex in the array contains a coordinate for y. SGR$M.sub.-- Z When set, each vertex in the array contains a coordinate for Z. SGR$M.sub.-- W When set, each vertex in the array contains a coordinate for w. ______________________________________

edit.sub.-- flags

Flags specifying how the routine will format the status words of itemized vertices as it stores them i the node. The edit.sub.-- flags argument is the address of an unsigned longword that contains the following flags:

______________________________________ Flag Description ______________________________________ SGR$M.sub.-- EDIT.sub.-- POLYLINE When set, creates default status words for itemized vertices with separate draw mode. SGR$M.sub.-- EDIT.sub.-- SEPARATE When set, creates default status words for itemized vertices with polyline draw mode. ______________________________________

If neither DGRSM.sub.-- EDIT.sub.-- POLYLINE nor SGRSM.sub.-- EDIT.sub.-- SEPARATE is set in the edit.sub.-- flags argument, the status words of itemized vertices are not changed and the status word must be filled in the properly for each vertex. The edit.sub.-- flag argument does not affect vertices without status words.

count

The number of vertices passed by the vertex.sub.-- array argument. The count argument is the address of an unsigned longword.

vertex.sub.-- array

The array of vertices defining the vectors to be drawn. The vertex.sub.-- array argument is the address of an array of longwords; this array must contain the number of longwords equal to the value passed by the count argument multiplied by the number of vertex components indicated by the number of flags set in vertex.sub.-- format. For example, if vertex.sub.-- format declares a 3D-with-status vertex format (by setting SGRSM.sub.-- STATUS, SGRSM.sub.-- X, SGRSM.sub.-- Y, and SGRSM.sub.-- Z in the vertex.sub.-- format argument) and the count argument declares that the number of vertices is 10, then the vertex array must contain 40 longwords. Vertex components must be int he order status, x, y, z, w. All coordinates must be of the default floating-point format set i the graphics context.

handle

The identifier of the node created by this routine. The handle argument returns the address of an unsigned longword that contains the identifier.

PURPOSE

To create a vector node.

DESCRIPTION

This routine creates a vector node. When this node is traversed by the structure walker 27, data is forwarded to the graphics subsystem 17 to draw the vectors to be displayed, as described above. In order to be visible the vectors must be properly transformed (for example, they must be within the clipping planes), have correct attributes (such as a color different from the background color), and must not be obscured by polygons.

Each vertex can have a status word and x, y, z, and w coordinates. The status word sets the draw mode and/or itemized vector color is enabled.

EXAMPLE 4

SGRSX.sub.-- ROTATE.sub.-- MATRIX

FORMAT

SGRSX.sub.-- ROTATE.sub.-- MATRIX(context, multiply.sub.-- control, angle, matrix)

ARGUMENTS

context

The identifier of the graphics context for this subroutine call. The context argument is the address of an unsigned integer that contains the identifier of the graphics context block.

Multiply.sub.-- control

Specifies how the matrix argument is to be interpreted. The multiply.sub.-- control argument is the address of an unsigned longword. Acceptable values are:

______________________________________ Constant Function ______________________________________ SGR$K.sub.-- REPLACE The matrix argument returns the new matrix produced by this routine: Matrix new.sub.-- matrix SGR$ K-PREMULTIPLY The matrix argument supplies a matrix to which the new matrix produced by this routine is premultiplied. The matrix argument then returns the resulting matrix: Matrix New.sub.-- matrix x matrix SGR$ K-POSTMULTIPLY The matrix argument supplies a matrix to which the new matrix produced by this routine is postmultiplied. The matrix argument then returns the resulting matrix: matrix matrix x new.sub.-- matrix angle ______________________________________

The angle of rotation in radians. The angle argument is the address of a longword in F.sub.-- floating format.

matrix

The x-rotation matrix created by this routine. The matrix argument returns the address of a 4.times.4 array of longwords in F.sub.-- floating format containing the result matrix. The matrix is in row major order.

PURPOSE

To create an x-rotation matrix.

DESCRIPTION

This routine computes a rotation matrix to rotate about the x axis. The resulting rotation is angle radians clockwise as viewed from the +x axis. The rotation matrix is returned in the matrix argument.

Any number of additional routines may be stored in the host subsystem to enable an application process 100 to build a graphics data linked node structure representative of a three dimensional image in color for storage in the structure memory 26
and eventual traversal by the structure walker 27. The following is an example of a complete structured graphics routine library with the routines listed by function:

TABLE 1 ______________________________________ SGR Primitive Routines Arguments ______________________________________ Primitive SGRs SGR$POLYGON context, vertex.sub.-- format, flags, plane.sub.-- equation, count, vertex.sub.-- array, handle SGR$STRING context, vertex.sub.-- format, vertex, flags, count, string, handle SGR$VECTOR context, vertex.sub.-- format, edit.sub.-- flags, count, vertex.sub.-- array handle Primitive Utility SGRs SGR$PLANE.sub.-- EQUATION context, vertex.sub.-- format, negate, count, vertex.sub.-- array, plane.sub.-- equation SGR$STATUS context, flags, color, status ______________________________________

TABLE 2 ______________________________________ SGR Attribute Routines Arguments ______________________________________ General Attribute SGRs SGR$SET.sub.-- BACKGROUND context, color, handle SGR$SET.sub.-- GEOMETRY.sub.-- MASK context, enable.sub.-- mask, disable.sub.-- mask, handle SGR$SET.sub.-- INTENSITY.sub.-- RANGE context, minimum, maximum, handle SGR$SET.sub.-- LINE.sub.-- COLOR context, color, handle SGR$SET.sub.-- LINE.sub.-- FILTER context, filter, handle SGR$SET.sub.-- LINE.sub.-- PATTERN context, flags, dash.sub.-- mask, dot.sub.-- mask, mask.sub.-- bits, pattern.sub.-- length, fill.sub.-- color, handle SGR$SET.sub.-- RENDERING.sub.-- MASK context, enable.sub.-- mask, disable.sub.-- mask, handle Vector Attribute SGRs SGR$SET.sub.-- MARKER.sub.-- TYPE context, glyph, handle SGR$SET.sub.-- VECTOR.sub.-- DRAW.sub.-- MODE context, draw.sub.-- mode, handle Polygon Attribute SGRs SGR$SET.sub.-- LIGHT context, light.sub.-- id, light, handle SGR$SET.sub.-- LIGHTING.sub.-- STYLE context, style, handle SGR$SET.sub.-- LIGHT.sub.-- MASK context, enable.sub.-- mask, disable.sub.-- mask, handle SGR$SET.sub.-- SHADING.sub.-- STYLE context, style, handle SGR$SET.sub.-- SURFACE.sub.-- COLOR context, side, color, handle SGR$SET.sub.-- SURFACE.sub.-- PROPERTIES context, side, pro- perties, handle String Attribute SGRs SGR$DO.sub.-- STRING.sub.-- CHARACTERS context, handle SGR$DO.sub.-- STRING.sub.-- MATRIX context, handle SGR$DO.sub.-- STRING.sub.-- POSITION context, handle SGR$SET.sub.-- STRING.sub.-- FONT context, flags, spacing.sub.-- handle, process.sub.-- handle, glyph.sub.-- handles, handle SGR$SET.sub.-- STRING.sub.-- SPACING context, spacing.sub.-- vector, handle Attribute Utility SGR SGR$COLOR context, flags, red, green, blue, color ______________________________________

TABLE 3 ______________________________________ SGR Rendering Routines Arguments ______________________________________ Rendering SGRs SGR$BEGIN RENDERING context, style, handle SGR$END.sub.-- RENDERING context, handle ______________________________________

TABLE 4 __________________________________________________________________________ SGR Transformation Routines Arguments __________________________________________________________________________ Matrix Composition SGRs SGR$CONCAT.sub.-- MATRIX context, flags, matrix, normal.sub.-- matrix, handle SGR$LOAD.sub.-- MATRIX context, flags, matrix, normal.sub.-- matrix, handle SGR$SUBSTITUEE.sub.-- MATRIX context, flags, matrix, normal.sub.-- matrix, handle Modeling SGRs SGR$A.sub.-- ROTATE.sub.-- MATRIX context, multiply.sub.-- control, angle, point1, point2, matrix SGR$SCALE.sub.-- MATRIX context, multiply.sub.-- control, vector, matrix SGR$TRANSLATE.sub.-- MATRIX context, multiply.sub.-- control, vector, matrix SGR$ROTATE.sub.-- MATRIX context, multiply.sub.-- control, angle, matrix SGR$Y.sub.-- ROTATE.sub.-- MATRIX context, multiply.sub.-- control, angle, matrix SGR$Z.sub.-- ROTATE.sub.-- MATRIX context, multiply.sub.-- control, angle, matrix Viewing SGRs SGR$LOOK.sub.-- AT.sub.-- VIEW.sub.-- MATRIX context, multiply.sub.-- control, from, to, up, matrix SGR$POLAR.sub.-- VIEW.sub.-- MATRIX context, multiply.sub.-- control, view.sub.-- flag, point, distance, azimuth, incidence, twist, matrix Projection SGRs SGR$ORTHOGRAPHIC.sub.-- PROJ.sub.-- MATRIX context, multiply.sub.-- control, height, aspect, front, back, matrix SGR$PERSPECTIVE.sub.-- PROJ.sub.-- MATRIX context, multiply.sub.-- control, angle, height, aspect, front, back, matrix String Matrix SGRs SGR$SET.sub.-- STRING.sub.-- MATRIX context, matrix, handle General Matrix Utility SGRs SGR$COPY.sub.-- MATRIX context, from.sub.-- matrix, to.sub.-- matrix SGR$IDENTITY.sub.-- MATRIX context, matrix SGR$INVERSE.sub.-- MATRIX context, matrix, inverse.sub.-- matrix SGR$MULTIPLY.sub.-- MATRICES context, prematrix, postmatrix, result.sub.-- matrix SGR$NORMAL.sub.-- MATRIX context, matrix, normal.sub.-- matrix __________________________________________________________________________

TABLE 5 ______________________________________ SGR Viewport Routines Arguments ______________________________________ Viewport SGRs SGR$CONCAT.sub.-- VIEWPORT context, left.sub.-- bottom, right.sub.-- top, handle SGR$LOAD.sub.-- VIEWPORT context, left.sub.-- bottom, right.sub.-- top, handle SGR$SUBSTITUTE.sub.-- VIEWPORT context, left.sub.-- bottom, right.sub.-- top, handle ______________________________________

TABLE 6 ______________________________________ SGR Structure Building Routines Arguments ______________________________________ Structure Building SGRs SGR$BEGIN.sub.-- STRUCTURE context SGR$END.sub.-- STRUCTURE context, handle ______________________________________

TABLE 7 ______________________________________ SGR Reference Routines Arguments ______________________________________ Unconditional Reference SGR SGR$CALL context, reference.sub.-- mode, reference.sub.-- handle, handle Conditional Reference SGRs SGR$CASE context, reference.sub.-- mode, mode, opspec, count, otherwise.sub.-- handle, case.sub.-- handles, handle SGR$COMPARE context, reference.sub.-- mode, mode1, opspec1, mode2, opspec2, less.sub.-- handle, equal.sub.-- handle, greater.sub.-- handle, handle SGR$TEST context, reference.sub.-- mode, mode, opspec, true.sub.-- handle, false.sub.-- handle, handle SGR$$EST.sub.-- AND.sub.-- CLEAR context, reference.sub.-- mode, mode, opspec, true-handle, false.sub.-- handle, handle SGR$TEST.sub.-- CLEAR context, reference.sub.-- mode, mode1, opspec1, mode2, opspec2, true.sub.-- handle, false.sub.-- handle, handle SGR$TEST.sub.-- SET context, reference.sub.-- mode, mode1, opspec1, mode2, opspec2, true-handle, false.sub.-- handle, handle Arithmetic and Assignment SGRs SGR$ADD context, mode1, opspec1, mode2, opspec2, handle SGR$CLEAR.sub.-- BITS context, mode1, opspec1, mode2, opspec2, handle SGR$MOVE context, mode1, opspec1, mode2, opspec2, handle SGR$MOVE.sub.-- BLOCK context, size, mode1, opspec1, mode2, opspec2, handle SGR$MOVE.sub.-- MASK context, mask, mode1, opspec1, mode2, opspec2, handle SGR$SET.sub.-- BITS context, mode1, opspec1, mode2, opspec2, handle SGR$SUB context, mode1, opspec1, mode2, opspec2, handle SGR$XOR context, mode1, opspec1, mode2, opspec2, handle ______________________________________

TABLE 8 __________________________________________________________________________ SGR Graphics Context Routines Arguments __________________________________________________________________________ Graphics Context SGRs SGR$COPY.sub.-- CONTEXT from.sub.-- context, to.sub.-- context SGR$CREATE.sub.-- CONTEXT display, context Graphics Context Editing SGRs- Inquiry SGR$INQ.sub.-- DEF.sub.-- BASE.sub.-- GEOMETRY context, geometry SGR$INQ.sub.-- DEF.sub.-- BLINK.sub.-- PERIODS context, on, off SGR$INQ.sub.-- DEF.sub.-- BUFFERING.sub.-- MODE context, mode SGR$INQ.sub.-- DEF.sub.-- DRAWABLE context, drawable SGR$INQ.sub.-- DEF.sub.-- FIRST.sub.-- PICK context, pick-number SGR$INQ.sub.-- DEF.sub.-- FP.sub.-- FORMAT context, fp.sub.-- format, fp.sub.-- block.sub.-- exponent SGR$INQ.sub.-- DEF.sub.-- HIT.sub.-- BOX.sub.-- LOCATION context, hit.sub.-- box.sub.-- location SGR$INQ.sub.-- DEF.sub.-- HIT.sub.-- BOX.sub.-- SIZE context, hit.sub.-- box.sub.-- size SGR$INQ.sub.-- DEF.sub.-- LINE.sub.-- FILTER context, filter.sub.-- number, filter.sub.-- values SGR$INQ.sub.-- DEF.sub.-- PATH.sub.-- STACK context, path.sub.-- size SGR$INQ.sub.-- DEF.sub.-- PICK.sub.-- ID.sub.-- STACK context, pick.sub.-- id.sub.-- size SGR$INQ.sub.-- DEF.sub.-- PICK.sub.-- LIMIT context, pick.sub.-- limit SGR$INQ.sub.-- DEF.sub.-- PICK.sub.-- QUEUE context, pick.sub.-- size, path.sub.-- size, pick.sub.-- id.sub.-- size SGR$INQ.sub.-- DEF.sub.-- REPEAT.sub.-- PERIOD context, period SGR$INQ.sub.-- DEF.sub.-- TRAVERSAL.sub.-- ID context, traversal.sub.-- id SGR$INQ.sub.-- DEF.sub.-- TRAVERSAL.sub.-- MODE context, modeflags SGR$INQ.sub.-- DEF.sub.-- UPDATE.sub.-- MODE context, update.sub.-- mode SGR$INQ.sub.-- DEF.sub.-- VERTEX context, vertex.sub.-- 4d SGR$INQ.sub.-- DEF.sub.-- VIRTUAL.sub.-- ROOT context, handle Graphics Context Editing SGRs- Setting SGR$SET.sub.-- DEF.sub.-- BASE.sub.-- GEOMETRY context, geometry SGR$SET.sub.-- DEF.sub.-- BLINK.sub.-- PERIODS context, on, off SGR$SET.sub.-- DEF.sub.-- BUFFERING.sub.-- MODE context, mode SGR$SET.sub.-- DEF.sub.-- DRAWABLE context, drawable, attach.sub.-- detach SGR$SET.sub. -- DEF.sub.-- FIRST.sub.-- PICK context, pick.sub.-- number SGR$SET.sub.-- DEF.sub.-- FP.sub.-- FORMAT context, fp.sub.-- format, fp.sub.-- block.sub.-- exponent SGR$SET.sub.-- DEF.sub.-- HIT.sub.-- BOX.sub.-- LOCATION context, hit.sub.-- box.sub.-- location SGR$SET.sub.-- DEF.sub.-- HIT.sub.-- BOX.sub.-- SIZE context, hit.sub.-- box.sub.-- size SGR$SET.sub.-- DEF.sub.-- LINE.sub.-- FILTER drawable, filter.sub.-- number, filter.sub.-- values SGR$SET.sub.-- DEF.sub.-- PATH.sub.-- STACK context, path.sub.-- size SGR$SET.sub.-- DEF.sub.-- PICK.sub.-- ID.sub.-- STACK context, pick.sub.-- id.sub.-- size SGR$SET.sub.-- DEF.sub.-- PICK.sub.-- LIMIT context, pick.sub.-- limit SGR$SET.sub.-- DEF.sub.-- PICK.sub.-- QUEUE context, pick.sub.-- size, path.sub.-- size, pick.sub.-- id.sub.-- size SGR$SET.sub.-- DEF.sub.-- REPEAT.sub.-- PERIOD context, period SGR$SET.sub.-- DEF.sub.-- TRAVERSAL.sub.-- ID context, traversal.sub.-- id SGR$SET.sub.-- DEF.sub.-- TRAVERSAL.sub.-- MODE context, modelflags SGR$SET.sub.-- DEF.sub.-- UPDATE.sub.-- MODE context, update.sub.-- mode SGR$SET.sub.-- DEF.sub.-- VERTEX context, vertex.sub.-- 4d SGR$SET.sub.-- DEF.sub.-- VIRTUAL.sub.-- ROOT context, handle __________________________________________________________________________

TABLE 9 __________________________________________________________________________ SGR Traversal Control Routines Traversal Control SGRs Arguments __________________________________________________________________________ SGR$$ADD.sub.-- TO.sub.-- QUEUE context, queue.sub.-- handle, first.sub.-- handle, last.sub.-- handle SGR$$QUEUE context, reference.sub.-- mode, first.sub.-- handle, current.sub.-- handle, last.sub.-- handle, handle SGR$$REMOVE.sub.-- FROM.sub.-- QUEUE context, queue.sub.-- handle, first.sub.-- handle, last.sub.-- handle SGR$INQ.sub.-- TRAVERSAL.sub.-- STATE context, traversal.sub.-- type, waitflag, state SGR$RELEASE.sub.-- UPDATES context SGR$REQUEST.sub.-- TRAVERSAL context, traversal.sub.-- type __________________________________________________________________________

TABLE 10 __________________________________________________________________________ SGR Picking Routines Picking SGRs Arguments __________________________________________________________________________ SGR$COMPUTE.sub.-- PICK.sub.-- POINT context, node.sub.-- picked, type, pick.sub.-- vector, vert- geom.sub.-- mat, user.sub.-- vector SGR$CONCAT.sub.-- PICK.sub.-- ID context, identifier, handle SGR$GET.sub.-- PICK context, max.sub.-- path.sub.-- pairs, max.sub.-- pick.sub.-- ids, status, node.sub.-- picked, type, index, pick.sub.-- vector, vert.sub.-- geom.sub.-- mat, num.sub.-- pairs.sub.-- ret, path, num.sub.-- ids.sub.-- ret, pick.sub.-- ids SGR$LOAD.sub.-- PICK.sub.-- ID context, identifier, handle SGR$PRINT.sub.-- PICK context, max.sub.-- pathpairs, max.sub.-- pick.sub.-- ids, status, node.sub.-- picked, type, index, pick.sub.-- vector, vert.sub.-- geom.sub.-- mat, num.sub.-- pairs.sub.-- ret, path, num.sub.-- ids.sub.-- ret, pick.sub.-- ids SGR$SUBSTITUTE.sub.-- PICK.sub.-- ID context, identifier, handle __________________________________________________________________________

TABLE 11 __________________________________________________________________________ SGR Input Handling Routines Input Handling SGRs Arguments __________________________________________________________________________ SGR$ALLOCATE.sub.-- DEVICE context, device SGR$CONNECT.sub.-- DEVICE.sub.-- TO.sub.-- MAT context, device, handle, geometric.sub.-- operation, axis, matrix.sub.-- operation, value- usage.sub.-- flag SGR$DISCONNECT.sub.-- DEVICE.sub.-- context, device, FROM.sub.-- MAT handle SGR$SISPATCH.sub.-- DEVICE.sub.-- EVENT context, event SGR$FIND.sub.-- DEVICE context, display, device- type, unit, device.sub.-- id[, nBins[, nDims]] SGR$FREE.sub.-- DEVICE context, device SGR$GET.sub.-- DEVICE.sub.-- ATTR context, device, attrBlock SGRGET.sub.-- DEVICE.sub.-- CHARS context, device, nBins nDims, ndevice, nextdevice SGR$GET.sub.-- DEVICE.sub.-- VALUE context, device, valueBlock SGR$SET.sub.-- DEVICE.sub.-- AST context, device, valueBlock, eventcode, action, parameter SGR$SET.sub.-- DEVICE.sub.-- ATTR context, device, attrBlock SGR$SET.sub.-- DEVICE.sub.-- LABEL context, device, label, count SGR$SET.sub.-- DEVICE.sub.-- VALUE context, device, valueBlock __________________________________________________________________________

TABLE 12 __________________________________________________________________________ SGR Structure Editing Routines Arguments __________________________________________________________________________ Structure Topology SGRs SGR$INQUIRE.sub.-- LINKS context, handle, prev.sub.-- handle, next.sub.-- handle SGR$INQUIRE.sub.-- REFERENCE context, handle, index, reference.sub.-- handle SGR$POSTFIX.sub.-- NODE context, handle, new.sub.-- handle SGR$PREFIX.sub.-- NODE context, handle, new.sub.-- handle SGR$REPLACE.sub.-- INDIRECT context, handle, indirect.sub.-- handle SGR$REPLACE.sub.-- NEXT context, handle, new.sub.-- next.sub.-- handle SGR$REPLACE.sub.-- NODE context, handle, new.sub.-- handle SGR$REPLACE.sub.-- REFERENCE context, handle, index, reference.sub.-- handle Node Editing SGRs-Inquiry SGR$INQUIRE.sub.-- BITMASKS context, handle, enable.sub.-- bits, disable.sub.-- bits SGR$INQUIRE.sub.-- CHARACTERS context.sub.-- handle, first.sub.-- position, last.sub.-- position string.sub.-- size, result.sub.-- count, result.sub.-- string SGR$INQUIRE.sub.-- COLOR context, handle, color SGR$INQUIRE.sub.-- DEFAULT.sub.-- VERTEX context, handle, vertex.sub.-- 4d SGR$INQUIRE.sub.-- FP.sub.-- BLOCK.sub.-- EXPONENT context, handle, fp.sub.-- block.sub.-- exponent SGR$INQUIRE.sub.-- INDIRECT context, handle, indirect.sub.-- handle SGR$INQUIRE.sub.-- INTENSITY.sub.-- RANGE context, handle, minimum, maximum SGR$INQUIRE.sub.-- LINE.sub.-- FILTER context, handle, filter SGR$INQUIRE.sub.-- MATRIX context, handle, flags, matrix, normal.sub.-- matrix SGR$INQUIRE.sub.-- NODE.sub.-- ENABLE context, handle, onoff SGR$INQUIRE.sub.-- NODE.sub.-- TYPE context, handle, node.sub.-- type SGR$INQUIRE.sub.-- OPSPEC context, handle, opspec.sub.-- id, opspec SGR$INQUIRE.sub.-- PICK.sub.-- ID context, handle, identifier SGR$INQUIRE.sub.-- PLANE.sub.-- EQUATION context, handle, plane.sub.-- equation SGR$INQUIRE.sub.-- REF.sub.-- COUNT context, handle, result.sub.-- system.sub.-- count, result.sub.-- user.sub.-- count SGR$INQUIRE.sub.-- STRING.sub.-- SPACING context, handle, spacing.sub.-- vertex SGR$INQUIRE.sub.-- USER.sub.-- DATA context, handle, user.sub.-- data SGR$INQUIRE.sub.-- USER.sub.-- TYPE context, handle, user.sub.-- type SGR$INQUIRE.sub.-- USER.sub.-- TYPE context, handle, user.sub.-- type SGR$INQUIRE.sub.-- VERTICES context, handle, first.sub.-- position, last.sub.-- position, array.sub.-- size, result.sub.-- count, result.sub.-- vertex.sub.-- array SGR$INQUIRE.sub.-- VIEWPORT context, handle, left.sub.-- bottom, right.sub.-- top Node Editing SGRs-Replacement SGR$REPLACE.sub.-- BITMASKS context, handle, enable.sub.-- bits, disable.sub.-- bits SGR$REPLACE.sub.-- CHARACTERS context, handle, position, delete.sub.-- count, insert.sub.-- count, insert.sub.-- string, result.sub.-- handle SGR$REPLACE.sub.-- COLOR context, handle, color SGR$REPLACE.sub.-- DEFAULT.sub.-- VERTEX context, handle, vertex.sub.-- 4d SGR$REPLACE.sub.-- FP.sub.-- BLOCK.sub.-- EXPONENT context, handle, fp.sub.-- block.sub.-- exponent SGR$REPLACE.sub.-- INTENSITY.sub.-- RANGE context, handle, minimum, maximum SGR$REPLACE.sub.-- LINE.sub.-- FILTER context, handle, filter SGR$REPLACE.sub.-- MATRIX context, handle, flags, matrix, normal.sub.-- matrix SGR$REPLACE.sub.-- NODE.sub.-- ENABLE context, handle, onoff SGR$REPLACE.sub.-- OPSPEC context, handle, opspec.sub.-- id, opspec SGR$REPLACE.sub.-- PICK.sub.-- ID context, handle, identifier SGR$REPLACE.sub.-- PLANE.sub.-- EQUATION context, handle, plane.sub.-- equation SGR$REPLACE.sub.-- STRING.sub.-- SPACING context, handle, spacing.sub.-- vertex SGR$REPLACE.sub.-- USER.sub.-- DATA context, handle, user.sub.-- data SGR$REPLACE.sub.-- USER.sub.-- TYPE context, handle, user.sub.-- type SGR$REPLACE.sub.-- VERTICES context, handle, position, delete.sub.-- count, insert.sub.-- count, insert.sub.-- vertices, result.sub.-- handle SGR$REPLACE.sub.-- VIEWPORT context, handle, left.sub.-- bottom, right.sub.-- top __________________________________________________________________________

TABLE 14 __________________________________________________________________________ SGR General Purpose Routines General Purpose SGRs Argument __________________________________________________________________________ SGR$DATA context, size, data, handle SGR$GENERIC context, size, data, handle SGR$INDIRECT context, to.sub.-- handle, handle __________________________________________________________________________

TABLE 13 __________________________________________________________________________ SGR Structure Memory Management Routines Structure Memory Management SGRs Arguments __________________________________________________________________________ SGR$DECREMENT.sub.-- REF.sub.-- COUNT context, handle SGR$INCREMENT.sub.-- REF.sub.-- COUNT context, handle __________________________________________________________________________

Referring now to FIG. 4, the structure memory 26 is illustrated in block diagram form. The structure memory's main function is to store the "working copy" of the graphics data structures built by the application programs 100 residing in the host central processing unit 10 either through the structured graphics routines or the bit map graphics package layered on the X Window System. The memory is made up of an array of memory devices 200 which are implemented as 256 K CMOS DRAMS, each with a minimum memory size of one megabyte. The array of memory devices 200 is arranged for a total of four megabytes of memory. A random access taken 200 ns and a static column mode is used to achieve sequential access of 100 ns per word.

A structure memory bus 201 interfaces the memory devices with an II32 Bus interface 202, a structure walker interface 203 and a rendering processor interface 204 to provide data flow between the memory devices 200 and the host central processing unit 10 via the control processor 13, the rendering processor 36 and the structure walker 27, respectively. The structure walker 27 is a special purpose, 32 bit bit-slice processor programmed to traverse the three dimensional graphics data structure nodes, as described above. For a more detailed description of the structure memory 26 and structure walker 27 components of the graphics subsystem 17 reference should be made to the Shadowfax Technical Manual published by the Evans & Sutherland Computer Corporation.

Traversal Control

In accordance with a significant teaching of the invention, a traversal control function is partitioned among the components of the host and graphics subsystems to accept requests for graphics structure traversals made by the several, competing application programs 100 residing in the host control processing unit 10 and to subsequently schedule and dispatch such traversal requests.

The traversal control functions are embodied in node control structures built in the structure memory 26 which, when traversed, provide a traversal request mechanism and handle traversal scheduling, traversal monitoring and application synchronization. The control structures function to place the graphics subsystem 17 at the disposal of all the several applications programs 100 residing in the central processing unit 10 such that each program views the graphics subsystem 17 as its own. The traversal control structures therefor coordinate traversal requests from the competing application programs 100 with the asynchronous operation of the structure walker 27 to maximize the processing capability of the graphics subsystem 17 and enable a multiple of application programs to be processed.

Pursuant to the invention there are three basic traversal structures: a system control structure (SCS), three dimensional display contexts (3DDCs) and three dimensional graphics contexts (3DGCs). The system control structure is the top-level control for the structure walker 27 and acts as the structure walker 27 operating system. The display contexts define the mapping of three dimensional images within viewports on the monitor screen defined by windows. The graphics contexts provide all the graphics attributes and control information required to perform the traversal of graphics data structures including a connection to a complementary display context.

The control structures are interconnected by attaching a doubly - linked list of graphics contexts created by applications to the system control structure. Each of the graphics contexts in the list contains one display context root node used to link the graphic context to a display context and one virtual root node used as a link to a graphics data structure. (See FIG. 5) Display contexts may be shared among multiple graphics contexts allowing several graphics contexts to operate within a single window. Moreover, all or part of a graphics data structure may be shared among a number of graphics contexts.

SYSTEM CONTROL STRUCTURE

The System control Structure (SCS) serves as the executive program of the structure walker 27 in that it performs the following functions:

Detects and accepts requests for 3DGC traversals.

Schedules and dispatches all 3DGC traversals.

Effects updates to 3DDCs.

Deactivates 3DGSs and 3DDCs as requested by the traversal control function in the server 101.

SCS CREATION AND CONTROL

As a part of the DDx startup procedure, the windowing server 101 will invoke a traversal control function to allocate and generate the graphics data structure nodes required for the SCS structure and to initiate its traversal.

Once started, the SCS continues running (i.e., being traversed) until all traversal requests have been satisfied. Once all requests have been serviced, the SCS will suspend itself by requesting the control processor 13 to resume its traversal at the next vertical retrace event, thus preventing excessive SCS request processing. Only under the following exceptional circumstances will SCS traversal be terminated, requiring restart by the server 101:

(a) The server 101 detects a traversal-timeout condition.

(b) An SCS-detected error condition is detected.

(c) The server 101 has terminated SCS traversal by issuing a "Server Rundown" request, as part of the server rundown procedure.

(d) The structure walker 27 encounters an error condition, at which time it will halt after notifying the control processor 13.

SCS DATA BLOCK

In order to perform its function, the SCS structure maintains a group of control variables in the structure memory 26 known collectively as the "SCS data block". The contents of this data block are described below.

SCS.State

This longword indicates the current state of SCS execution by taking on one of the following values:

SGRSSK.sub.-- STATE.sub.-- INITIAL--SCS has yet to complete its initial processing.

SGRSSK.sub.-- STATE.sub.-- UPDATE--SCS is performing SCS update processing.

SGRSSK.sub.-- STATE.sub.-- IDLE--SCS has suspended itself after finding not traversal requests pending and expects to be resumed by the control processor 13 at the next vertical retrace event.

SGRSSK.sub.-- STATE.sub.-- PHASE--SCS is performing request processing.

SGRSSK.sub.-- STATE.sub.-- EVENT--SCS has presented an event to the control processor 13 and expects to be resumed immediately.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- PHASE--SCS is performing traversal processing.

SGRSSK.sub.-- STATE.sub.-- RANDOWN--SCS has processed a "Server Rundown" request.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- UPDATE--SCS is performing SCS-deferred updates on the client's graphics display structure.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- CXT.sub.-- SETUP--SCS is performing 3DGC-setup processing.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- CXT.sub.-- CLEANUP--SCS is performing 3DCG- cleanup processing.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- 3DDC--The 3DDc structure is being traversed.

SGRSSK.sub.-- STATE.sub.-- TRAV.sub.-- CLIENT--The client's 100 graphics display structure is being traversed.

SGRSSK.sub.-- STATE.sub.-- INT.sub.-- ERROR--SCS has suspended itself after detecting an internal error.

The structure walker 27 requires exclusive write access to this longword.

SCS.Frame.sub.--Bank

This is a system-wide longword flag indicating which frame buffer bank is being displayed.

SGRSSK.sub.-- BANK.sub.-- A--Frame Buffer Bank "A" is currently being displayed.

SGRSSK.sub.-- BANK.sub.-- B--Frame Buffer Bank "B" is currently being displayed.

The structure walker 27 requires exclusive write access to this longword.

SCS.WLUT.sub.-- Bank

This is a system-side longword flag indicating which image bank of the window look up table (WLUT) is active.

SGRSSK.sub.-- SIDE.sub.-- A--Window Image Bank "A" is currently active.

SGRSSK.sub.-- SIDE.sub.-- B--Window Image Bank "B" is currently active.

The structure walker 27 requires exclusive write access to this longword.

SCS.Perform.sub.-- Traversal

This longword flag is used internally by the SCS to detect the absence of traversal requests at the end of request processing. The structure walker 27 requires exclusive write access to this longword.

SCS.Swap.sub.-- Bank.sub.-- Request

This longword flag is used internally by the SCS to remember that the frame buffer bank must be swapped at the end of traversal processing. It is set by 3DDCs of frame-bank double-buffered windows. The structure walker 27 requires exclusive write access to this longword.

SCS.Swap.sub.-- WLUT.sub.-- Request

This longword flag is used internally by the SCS to remember that the window image bank of the WLUT must be swapped at the end of traversal processing. It is set by 3DDCs of WLUT-bank double-buffered windows. The structure walker 27 requires exclusive write access to this longword.

SCS.Server.sub.-- Rundown

The windowing server 101 can set this flag non-zero to cause the structure walker 27 to terminate traversal of the SCS gracefully (at the completion of traversal phase processing). The structure walker 27 will clear it as its final action before suspending SCS traversal.

SCS.Num.sub.-- Passes

This longword contains a count of the passes made through the SCS main loop. The structure walker 27 requires exclusive write access to this longword.

SCS.Num.sub.-- Frames

This longword contains a count of times SCS traversal processing has been performed. The structure walker 27 requires exclusive write access to this longword.

SCS.Previous.sub.-- Time

At the start of each request/traversal loop of the SCS, this longword is loaded with a 60 Hz, control processor 13 maintained system time value. It is used to determined the SCS.Elapsed Time.

SCS.Elapsed.sub.-- Time

This longword is used to hold the interval of 60 Hz system time which elapses between request/traversal loops of the SCS. This value is used in blink and repeated traversal scheduling algorithms.

SCS.Watchdog.sub.-- Timer

The SCS will load this longword with a maximum processing interval at certain points in its execution. The traversal control function within the server 101 will periodically decrement this timer and perform timeout processing if the timer reaches zero.

SCS.Event.sub.-- Pointer

This longword contains the virtual address of a block of data attached to an event. The structure walker 27 requires exclusive write access to this longword.

SCS.Queue.sub.-- Node

This longword contains the handle of a queue node within the SCS.sub.-- Update.sub.-- Processing substructure.

SCS.Pick.sub.-- Id.sub.-- Stack

This longword contains the handle of a system-default Pick ID Stack node.

SCS.Pick.sub.-- Path.sub.-- Stack

This longword contains the handle of a system-default Pick Path Stack node.

SCS.Call.sub.-- Update.sub.-- Node

This longword contains the virtual address of the call node in SCS update processing. This node is required by the update mechanism to perform deferred updates to the SCS. The structure walker 27 requires exclusive write access to this longword.

SCS.Num.sub.-- GCs

This longword reflects the number of 3DGCs in the 3DGC list attached to the SCS. The structure walker 27 requires exclusive write access to this longword.

SCS.GC.sub.-- List.sub.-- Head

SCS.GC.sub.-- List.sub.-- Tail

These longwords describe the doubly-link list of 3DGCs attached to the SCS. They are pointers which contain the structure memory addresses of 3DGC data blocks, or are both "null", indicating the absence of 3DGCs. The structure walker 27
requires exclusive write access to these longwords.

SCS.DC.sub.-- List.sub.-- Head

SCS.DC.sub.-- List.sub.-- Tail

These longwords describe the doubly-link list of 3DDCs attached to the SCS. They are pointers which contain the structure memory 26 addresses of 3DDCs. The structure walker 27 requires exclusive write access to these longwords.

SCS.Current.sub.-- GC.sub.-- Pointer

This longword is loaded with the structure memory 26 address of the 3DGC data block currently being processed by SCS traversal processing. The structure walker 27 requires exclusive write access to this longword.

SCS.Current.sub.-- DC.sub.-- Pointer

This longword is loaded with the structure memory 26 address of the 3DDC data block attached to the 3DGC currently being processed by SCS traversal processing. The structure walker 27 requires exclusive write access to this longword.

SCS.Current.sub.-- Client.sub.-- Pointer

This longword is loaded with the structure memory 26 address of the root of the client 100 graphics data structure attached to the 3DGC currently being processed by SCS traversal processing. The structure walker 27 requires exclusive write access to this longword.

SCS.Current.sub.-- GC.sub.-- ID

This longword is loaded with the graphics context identification "GC ID" of the 3DGC being processed by SCS traversal processing. The client processes 100 may inspect this longword to determine which of the possibly several 3DGCs has requested its traversal

SCS.Current.sub.--GC.sub.-- Start.sub.-- Time

SCS.Current.sub.-- GC.sub.-- End.sub.-- Time

These longwords are loaded with the control processor 13 maintained system time at which traversal of the 3DGC commenced and completed, respectively. The structure walker 27 requires exclusive write access to these longwords.

SCS.Current.sub.-- Traversal.sub.-- Type

The contents of this longword reflect the type of traversal currently being performed. The structure walker 27 requires exclusive write access to this longword.

SGRSSK.sub.-- DRAW.sub.-- TRAVERSAL

SGRSSK.sub.-- HITTEST.sub.-- TRAVERSAL

SCS ORGANIZATION

The organization of the SCS structure is illustrated below.

The SCS structure alternates between request and traversal processing modes. During the request mode, each 3DGC on 3DGC list attached tot he SCS will be visited in sequence. If requests for traversals are outstanding and the current state of the 3DGC permits, flags in the 3DGC data block will be updated to cause the appropriate traversals in traversal processing. IN addition, draw traversal will be performed on all those 3DGCs sensitive to either the frame buffer bank or window loop-up table image bank if at least one draw traversal request has been made to 3DGC of that particular class.

Given that at least one valid traversal request was detected in request processing, the traversal processing mode will proceed to satisfy all requests accepted. This is done by visiting each 3DGC on the 3DGC list sequentially, and there performing hit-test and draw traversal (in that order), as required. Any grouping of the two types of traversals may be performed on a 3DGC each in a given traversal pass, provided that the corresponding requests were issued. If no traversal requests are outstanding, the SCS will be held suspended until the next vertical retrace event, at which point request processing will once again be performed. This is done to avoid an unnecessary load on the structure memory 26.

______________________________________ BEGIN SCS Define state and matrix stack overflow areas; IF (SCS State = "Initial") THEN 3D.sub.-- Graphics .sub.-- Initialization; ENDIF Clear SCS.Perform.sub.-- Traversal; WHILE (NOT SCS.Server.sub.-- Rundown) DO Set SCS.Watchdog.sub.-- Timer; SCS.sub.-- Update.sub.-- Processing; Request.sub.-- Processing; Traversal.sub.-- Processing; END DO Clear SCS.Server.sub.-- Rundown; SCS.State = "Randown"; END SCS BEGIN 3D.sub.-- Graphics.sub.-- Initialization Initialize the SCS.Frame.sub.-- Bank to Bank "A ' ' [being displayed] Initialize the SCS.WLUT.sub.-- Bank to Bank "A ' ' [active]' Clear both valid planes; Initialize.sub.-- Hierarchical.sub.-- State' END 3D.sub.-- Graphics.sub.-- Initialization ______________________________________

When SCS traversal commences, the SCS will immediately define the state and matrix stack overflow areas, initialize some internal flags, and proceed to enter its main processing loop.

SCS.sub.-- Update.sub.-- Processing

The first part of SCS loop is SCS Update Processing. This section performs deferred updates to the SCS through the use of the Update Mechanism

______________________________________ BEGIN SCS.sub.-- Update.sub.-- Processing SCS.State = "Update.sub.-- Phase"; Perform updates to SCS via call to SCS.Call.sub.-- Update.sub.-- Node; END SCS.sub.-- Update.sub.-- Processing ______________________________________

REQUEST PROCESSING

The request processing portion of mode of the SCS loop performs two functions. The first function is to effect modifications to the 3DDC data blocks. To do this, request processing will examine all 3DDCs known to the system and toggle the "active half" of those which have swap requests pending. This processing is performed here to assure consistent 3DDC data during request and traversal processing.

Secondly, request processing gathers traversals requests from 3D clients 100 and the display manager (from information contained in 3DDC data blocks). This processing is performed by traversing the 3DGC structures contained in the 3DGC list. Each 3DGC, after detecting the "Request Phase" SCS State, will respond to all outstanding traversal requests directed towards it. Results of this request processing are retained within the 3DGC.

In addition, if double-buffered 3DGCs are visited (those with 3DDCs sensitive to either the frame buffer bank or window look-up table image bank), a request to swap the particular bank will be recorded. This will be used to force draw traversal of all such 3DGCs, and cause the actual swapping commands to be delivered at the end of traversal processing.

If no traversal requests are detected after visiting each 3DGC, the SCS will put itself to sleep. The control processor 13 (ACP) will resume SCS traversal at the next vertical retrace event.

______________________________________ BEGIN Request.sub.-- Processing SCS.State = "Request.sub.-- Phase"; Clear SCS.Swap.sub.-- Bank.sub.-- Request; Clear SCS.Swap.sub.-- WLUT.sub.-- Request; DO Increment SCS.Num.sub.-- Passes; SCS Elapse.sub.-- Time = System VR Count SCS Previous.sub.-- Time; SCS Previous .sub.-- Time = System VR Count; Traverse.sub.-- DC.sub.-- List Traverse.sub.-- GC-List IF (NOT SCS.Perform.sub.-- Traversal) THEN SCS.State = "Idle"; Request ACP to resume SCS at next VR event; Suspend traversal; SCS.State = "Request.sub.-- Phase"; ENDIF UNTIL (SCS.Perform.sub.-- Traversal OR SCS.Server.sub.-- Rundown) END Requst.sub.-- Processing BEGIN Traverse.sub.-- GC.sub.-- List RO = SCS.GC.sub.-- List.sub.-- Head; WHILE (RO [GC handle] NOT NULL) DO Save physical addr of 3DGC data block in SCS.Current.sub.-- GC.sub.-- Ptr; Generic.sub.-- 3DGC; RO = GC.Flink; ENDDO END Traversal.sub.-- GC.sub.-- List BEGIN Traverse.sub.-- DC.sub.-- List RO = SCS.DC.sub.-- List.sub.-- Head; WHILE (RO [DC handle] NOT NULL) DO IF (3DDC.System.sub.-- Enabled) THEN IF (3DDC.Kill) THEN Clear 3DDC.Kill; Clear 3DDC.System.sub.-- Enabled; Remove.sub.-- DC.sub.-- Links Set 3DDC.Dead; ELSE IGNORE.sub.-- ATTENTION.sub.-- INTERRUPTS: IF (3DDC.Clear.sub.-- Request) THEN Clear 3DDC.Clear.sub.-- request; Send 3DDC.Clear Window generic node to clear window; IF (3DDC.Swap.sub.-- Request) THEN Toggle 3DDC.Active.sub.-- Half; Clear 3DDC.Swap.sub.-- Request; ENDIF ALLOW.sub.-- ATTENTION.sub.-- INTERRUPTS: IF (3DDC.Clear.sub.-- Request) THEN Clear 3DDC.Clear.sub.-- Request; Send 3DDC.Clear Window generic node to clear window; ENDIF ENDIF RO = 3DDC.Flink; ENDDO E