Method and apparatus for the continuous and asynchronous traversal and processing of graphics data structures

• US 4,928,247 A
• Filed: 04/20/1988
• Issued: 05/22/1990
• Est. Priority Date: 08/13/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Gerovac, Branko J., Rushforth, Kevin C., Carver, David C., Doyle, Peter L., Shapiro, Raymond E., Armstrong, William P., DiPirro, Steven D., Ellenberger, John P., Roach, William C., Jones, Ellis O., Gibson, Ellen S.
• Primary Examiner(s): Clark, David L.
• Application Number:
  US07/184,108
• Time in Patent Office: 762 Days
• Field of Search: 364/518, 364/521
• US Class Current: 715/853
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A host system executes one or more application programs which results in graphic data structures. These graphic data structures are then continuously and asynchronously traversed. Traversal requests by competing application programs are scheduled and performed so that each application views the graphics processing as its own. The traversal and ordering of traversal requests provide efficient use of resources for multiple application programs.

Claims

1. A method of operating a computer graphics system comprising the steps of:

(a) providing a plurality of application processes in a host central processing unit;

(b) operating said host central processing unit to execute said application processes to thereby generate individual graphics data structures relating to said application processes, each of said individual graphics data structures containing graphics data and commands representative of an object to be displayed by said computer graphics system;

(c) further operating said host central processing unit to store said individual graphics data structures in a memory device;

(d) operating a graphics device to continuously and asynchronously traverse said memory device through at least a portion of each of said individual graphics data structures to identify a sequence of certain ones of said individual graphics data structures and to asynchronously read and transmit said graphics data and commands of said certain ones of said individual graphics data structures, in accordance with said sequence, to a graphics subsystem for processing, manipulation and display; and

(e) identifying, ordering and setting said sequence of said certain ones of said individual graphics data structures by cooperatively operating said graphics device and said host central processing unit through further execution of said application processes to;

(i) selectively generate and control separate traversal requests, each of said separate traversal requests containing information on the mode and type of traversal of a preselected one of said certain ones of said individual graphics data structures;

(ii) attach each of said generated traversal requests to the respective preselected one of said certain ones of said individual graphics data structures; and

(iii) read and execute each of said traversal requests during the continuous and asynchronous traversal of said memory device to provide graphics processing of a multiple of application processes.

2. The method of claim 1 and further including the steps of

(a) operating said host central processing unit to generate graphics contexts, each of said graphics contexts containing graphics attribute and control information required to perform a read and execute of a traversal of at least a preselected one of said graphics data structures;

(b) said traversal requests comprising flags in said graphics contexts; and

(c) further operating said host central processing unit to attach each of said graphics contexts to said at least a preselected one of said graphics data structures.

3. The method of claim 2 and further including the steps of:

(a) operating said host central processing unit to generate windows;

(b) operating said host central processing unit to generate display contexts, each of said display contexts containing information on a description of a preselected one of said windows; and

(c) further operating said host central processing unit to attach each of said display contexts to at least a preselected one of said graphics contexts.

4. The method of either claims 1, 2 or 3 and further including the step of storing said graphics data structures in said memory device as hierarchical node memory structures.

5. The method of either claims 2 or 3 and further including the steps of:

(a) operating said graphics device to traverse said memory device in a request process to ascertain the existence of traversal requests in said graphics contexts; and

(b) thereafter operating said graphics device to traverse said memory device in a traverse process to traverse said graphics data structures in accordance with the traversal request ascertained pursuant to the request process of step (a).

6. The method of claim 2 and further including the steps of:

(a) compiling a list in said memory device of a single instance from each of said graphics contexts, each of said instances including a pointer to the corresponding graphics context; and

(b) utilizing said list to traverse said memory device.

7. The method of claim 6 and further including the steps of:

(a) compiling a list in said memory device of a single instance from each of said display contexts;

each of said instances including a pointer to the corresponding display context; and

(b) utilizing said list to traverse said memory device.

8. A computer graphics system, which comprises

(a) a host central processing unit including a plurality of application processes;

(b) said host central processing unit executes said application processes to generate individual graphics data structures, each of said individual graphics data structures containing graphics data and commands representative of an object to be displayed by said computer graphics system;

(c) a memory device, said memory device coupled to said host central processing unit;

(d) said host central processing unit stores said individual graphics data structures in said memory device;

(e) a graphics subsystem, said graphics subsystem coupled to said host central processing unit, said graphics subsystem operates to process and display graphics data;

(f) said graphics subsystem having a graphics device, said graphics device coupled to said memory device, said graphics device continuously and asynchronously traverses said memory device through at least a portion of each of said individual graphics data structures to identify a sequence of certain ones of said individual graphics data structures and to asynchronously read and transmit said graphics data and commands of said certain ones of said individual graphics data structures, in accordance with said sequence, to said graphics subsystem; and

(g) said graphics device and said host central processing unit cooperatively operate to identify, order and set said sequence of said certain ones of said individual graphics data structures by generating separate traversal requests through further execution of said application processes, each of said separate traversal requests containing information on the mode and type of traversal of a preselected one of said graphics data structures, attaching each of said separate traversal requests to the at least a portion of the preselected one of said graphics data structures and reading and executing each of said traversal requests during the continuous and asynchronous traversal of said memory device to provide graphics processing of a multiple of application processes.

9. The computer graphics system of claim 8, wherein said central processing unit operates to generate graphics contexts, each of said graphics contexts containing graphics attribute and control information required to perform a read and execute of at least a preselected one of said graphics data structures, and to attach each of said graphics contexts to said at least a preselected one of said graphics data structures.

10. The computer graphics system of claim 9, wherein said traversal requests comprise flags in said graphics contexts.

11. The computer graphics system of either claims 9 or 10 wherein said central processing unit operates to generate windows and display contexts, each of said display contexts containing information on a description of a preselected one of said windows, and to attach each of said display contexts to at least a preselected one of said graphics contexts.

12. The computer system of claim 8, wherein said central processing unit stores said graphics data structures in said memory device as hierarchical node memory structures.