Multiple-level graphics processing system and method Number:7,161,599 from the United States Patent and Trademark Office (PTO) owispatent

Title: Multiple-level graphics processing system and method

Abstract: A multiple-level graphics processing system and method (e.g., of an operating system) for providing improved graphics output including, for example, smooth animation. One such multiple-level graphics processing system comprises two components, including a tick-on-demand or slow-tick high-level component, and a fast-tick (e.g., at the graphics hardware frame refresh rate) low-level component. In general, the high-level, less frequent component performs computationally intensive aspects of updating animation parameters and traversing scene data structures, in order to pass simplified data structures to the low-level component. The low-level component operates at a higher frequency, such as the frame refresh rate of the graphics subsystem, to process the data structures into constant output data for the graphics subsystem. The low-level processing includes interpolating any parameter intervals as necessary to obtain instantaneous values to render the scene for each frame of animation.

Patent Number: 7,161,599 Issued on 01/09/2007 to Beda,   et al.

---

Inventors:	Beda; Joseph S. (Seattle, WA), Swedberg; Gregory D. (Bellevue, WA), Ungureanu; Oreste Dorin (Duvall, WA), Gallo; Kevin T. (Woodinville, WA), David; Paul C. (Kirkland, WA), Calkins; Matthew W. (Seattle, WA)
Assignee:	Microsoft Corporation (Redmond, WA)
Appl. No.:	10/184,795
Filed:	June 27, 2002

---

Current U.S. Class:	345/473 ; 345/419; 345/506
Current International Class:	G06T 13/00 (20060101)
Field of Search:	345/419,473,506

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5487172		January 1996		Hyatt
	5852449		December 1998		Esslinger et al.
	6154215		November 2000		Hopcroft et al.
	6215495		April 2001		Grantham et al.
	6259451		July 2001		Tesler
	6266053		July 2001		French et al.
	6266253		July 2001		Kurrer et al.
	6487565		November 2002		Schechter et al.
	6538656		March 2003		Cheung et al.
	6751655		June 2004		Deutsch et al.
	2004/0130550		July 2004		Blanco et al.

Foreign Patent Documents

	WO99/00725		Jan., 1999		WO
	WO99/52080		Oct., 1999		WO

Other References

Rikk Cary, Gavin Bell, Chris Marrin: "International Standard isl.iec 14772-1: 1997 Virtual Reality Modeling Language (vrml97)" VRML 97, 1997, pages 1-236, XP002133320 page 7, paragraph 3.18: pp. 89-99 section 6.20; p. 149, paragraph B.2. cited by other . European Search Report in EP 02 02 3604 of Jan. 11, 2006 listing documents considered to be relevant. cited by other . Hyun Suk Kim et al: "Scene Graph for Dynamic Virtual Environment: Spangraph" International Journal of Virtual Reality, IPI Press, Colorado Springs, CO, US, vol. 4, No. 2, 2000, p. 12-18, OP001039706 ISSN: 1081-1451 .star-solid. page 16, col. 2.star-solid.. cited by other . Partial European Search Report in EP 02 02 3604 listing documents considered to be relevant. cited by other . Java 3D API Specification: Scene Graph Basics. Sun Microsystems, Inc. 1999. http://java.sun.com/products/java-media/3D/forDevelopers/j3dguide/S- ceneGraphOverview.doc.html. cited by examiner.

Primary Examiner: Chauhan; Ulka
Assistant Examiner: Pappas; Peter Anthony
Attorney, Agent or Firm: Workman Nydegger

---

Parent Case Text

---

CROSS-REFERENCE TO RELATED APPLICATIONS

The present invention claims priority to U.S. Provisional Patent Application Ser. No. 60/330,244, filed Oct. 18, 2001. The present invention is related to U.S. patent application Ser. No. 10/184,796 entitled "Generic Parameterization for a Scene Graph" and U.S. patent application Ser. No. 10/185,775 entitled "Intelligent Caching Data Structure for Immediate Mode Graphics," both assigned to the assignee of the present application, filed concurrently herewith, and hereby incorporated by reference in their entireties.

---

Claims

---

What is claimed is:

1. In a computing environment, a system comprising, a graphics subsystem for outputting frames of display information including graphics; a first component that provides graphics data at a first rate to the graphics subsystem to output the frames of display information; a second component that interfaces with program code to produce scene data for the program code, the second component configured to process the scene data into graphics information by maintaining at least some of the scene data in a cache data structure and traversing the cache data structure at a second rate that is lower than the first rate, and to provide the graphics information to the first component; the cache data structure arranged as a hierarhical tree of nodes in which at least one of the nodes comprises a container structure that includes drawing instructions; and wherein the first component provides return information to the second component that the second component uses to traverse the cache data structure or maintain the scene data in the cache data structure.

2. The system of claim 1 wherein the graphics information comprises image data in a format understood by the first component.

3. The system of claim 1 wherein the graphics information comprises instructions.

4. The system of claim 3 wherein the instructions include at least one interpolation command, and wherein the first component includes an interpolation mechanism that changes the graphics data provided to the graphics subsystem by interpolating an image within the graphics data over time.

5. The system of claim 1 wherein the second component accesses animation parameters to vary the graphics information provided to the first component.

6. The system of claim 1 wherein the second component operates in response to a change in the scene data to output.

7. The system of claim 1 wherein the second component operates when the first component indicates that the graphics information is needed.

8. The system of claim 1 wherein the second component dynamically adjusts the amount of the graphics information provided to the first component based on the return information from the first component.

9. The system of claim 1 wherein the second component operates at a frequency that is based on an animation parameter in the scene data.

10. The system of claim 3 wherein the second component provides the graphics information to the first component via an instruction stream.

11. The system of claim 1 wherein the second component provides the graphics information to the first component via an instruction stream.

12. The system of claim 1 wherein the second component provides the graphics information to the first component via a network connection.

13. The system of claim 1 wherein the first component maintains the graphics information provided by the second component in a set of at least one queue.

14. The system of claim 1 further comprising at least one other second component that provides other graphics information to the first component, and wherein the first component composes the graphics data provided to the graphics subsystem from a composition of the graphics information from each second component.

15. The system of claim 14 wherein the first component maintains the graphics information provided by the second component in a set of at least one queue for each high level component.

16. The system of claim 1 wherein the first component separates the graphics information provided by the second component into visual blocks and resource data structures.

17. The system of claim 1 wherein the first component and second component execute on different threads.

18. A computer-readable medium having stored thereon a data structure, the data structure comprising: a visual update block, including an identifier field having a visual identifier therein, and a field corresponding to an instruction block; the instruction block corresponding to a set of data related to a visual identified by the visual identifier, the set of data being passed from a high-level graphics processing component to a low-level graphics processing component, and the set of data including an instruction that provides the low level graphics processing component with interpolation information, the interpolation information comprising a time interval; and the high-level component constructing the data structure from a scene graph and providing the data structure to the low-level component, the low-level component processing the data structure based in part on the interpolation information into graphics data for passing to a graphics subsystem to output a frame; wherein the field corresponding to the instruction block comprises an instruction block offset pointing to another location in the data structure.

19. A computer-readable medium having stored thereon a data structure, the data structure comprising: a visual update block, including an identifier field having a visual identifier therein, and a field corresponding to an instruction block, the field corresponding to an instruction block comprising an instruction block offset pointing to another location in the data structure; the instruction block corresponding to a set of data related to a visual identified by the visual identifier, the set of data being passed from a high-level graphics processing component to a low-level graphics processing component; and the high-level component constructing the data structure from a scene graph and providing the data structure to the low-level component, the low-level component processing the data structure into graphics data for passing to a graphics subsystem to output a frame.

---

Description

---

FIELD OF THE INVENTION

The invention relates generally to computer systems, and more particularly to the processing of graphical and other video information for display on computer systems.

BACKGROUND OF THE INVENTION

In contemporary computing systems, the capability of graphics and video hardware is growing at a fast pace. In fact, to an extent, the graphics system in contemporary computing systems may be considered more of a compressor than a simple graphics subsystem. At the same time, consumers are expecting more and more quality in displayed images, whether viewing a monitor, television or cellular telephone display, for example.

However, memory and bus speeds have not kept up with the advancements in main processors and/or graphics processors. As a result, the limits of the traditional immediate mode model of accessing graphics on computer systems are being reached. At the same time, developers and consumers are demanding new features and special effects that cannot be met with traditional graphical windowing architectures.

Although certain game programs have been designed to take advantage of the graphics hardware, such game programs operate with different requirements than those of desktop application programs and the like, primarily in that the games do not need to be concerned with other programs that may be concurrently running. Unlike such game programs, applications need to share graphics and other system resources with other applications. They are not, however, generally written in a cooperative, machine-wide sharing model with respect to graphics processing.

For example, performing animation with desktop applications currently requires specialized single-purpose code, or the use of another application. Even then, achieving smooth animation in a multiple windowed environment is difficult if not impossible. In general, this is because accomplishing smooth, high-speed animation requires updating animation parameters and redrawing the scene (which requires traversing and drawing data structures) at a high frame rate, ideally at the hardware refresh rate of the graphics device. However, updating animation parameters and traversing and drawing the data structures that define a scene are generally computationally-intensive. The larger or more animate the scene, the greater the computational requirement, which limits the complexity of a scene that can be animated smoothly.

Compounding the problem is the requirement that each frame of the animation needs to be computed, drawn, and readied for presentation when the graphics hardware performs a display refresh. If the frame is not ready when required by the hardware, the result is a dropped or delayed frame. If enough frames are dropped, there is a noticeable stutter in the animated display. Also, if the frame preparation is not synchronized with the refresh rate, an undesirable effect known as tearing may occur. In practice, contemporary multi-tasking operating systems divide computational resources among the many tasks on the system. However, the amount of time given for frame processing by the operating system task scheduler will rarely align with the graphics hardware frame rate. Consequently, even when sufficient computational resources exist, the animation system may still miss frames due to scheduling problems. For example, an animation task may be scheduled to run too late, or it may get preempted before completing a frame, and not be rescheduled in time to provide a next frame for the next hardware refresh of the screen. These problems get even more complex if the animated graphics need to be composited with video or other sources of asynchronously generated frames.

In general, the current (e.g., WM_PAINT) model for preparing the frames requires too much data processing to keep up with the refresh rate when complex graphics effects (such as complex animation) are desired. As a result, when complex graphics effects are attempted with conventional models, instead of completing the changes in the next frame that result in the perceived visual effects in time for the next frame, the changes may be added over different frames, causing results that are visually and noticeably undesirable. There are computing models that attempt to allow the changes to be put in selectively, by providing object handles to every object in the scene graph. Such models, however, require applications to track a significant number of objects, and also consume far too many resources, as the object handles are present even when the application does not want to make changes to the objects.

In summary, existing models of accessing graphics on computer systems are becoming inadequate for working with current display hardware and satisfying consumer expectations. A new model for processing graphics and video is needed.

SUMMARY OF THE INVENTION

Briefly, the present invention provides a multiple-level graphics processing system and method (e.g., of an operating system) for providing improved graphics access and output including, for example, smooth animation. In one implementation, the graphics processing system comprises two components, including a tick-on-demand or slow-tick high-level component, and a fast-tick (e.g., at the graphics hardware frame rate or multiple thereof) low-level component. In general, the high-level component traverses a scene to be displayed and updates animation parameters with intervals for later interpolation, and passes simplified data structures to the low-level component. The low-level component processes the data structures to obtain output data, including interpolating any parameter intervals as necessary to obtain instantaneous values, and renders the scene for each frame of animation.

In general, the invention solves the above-identified (and other) problems by factoring the graphics data so the most computationally intensive aspects of updating animation parameters and traversing scene data structures are performed on a less demanding schedule at a high-level processing component. The low-level processing component operates more frequently, but deals with less computationally intensive tasks due to the high-level preprocessing that provides relatively simplified data structures and instructions to process. Video frames also may be integrated into the composition during these low-level ticks.

Benefits of this system and method include television-like quality animation as part of an operating system shell, and as an animation engine for animated content. Further benefits include the ability to composite video images with graphics, and also the ability to distribute information to multiple terminals for high-quality video display over network connections that are not necessarily high-bandwidth, at least not sufficiently high bandwidth to carry conventional rasterized graphics bits at the high frame rate required.

The present invention may be provided via a system including a graphics subsystem for outputting frames of display information including graphics, a first component that provides graphics data at a first rate to the graphics subsystem to output the frames of display information, and a second component that interfaces with program code to produce scene data for the program code, the second component configured to process the scene data into graphics information at a second rate that is lower than the first rate, and to provide the graphics information to the first component.

A method and computer-readable medium having computer-executable instructions may include, at a first component, receiving calls including data corresponding to graphical images for output, maintaining the data as scene information, and at a first operating rate, processing the scene information into graphics information, and communicating the graphics information to a second component. At the second component, at a second operating rate that is faster than the first operating rate and based on a frame refresh rate of the graphics subsystem, the method may include receiving the graphics information, processing the graphics information into graphics data formatted for the graphics subsystem, and communicating the graphics data to the graphics subsystem to output the frame.

A computer-readable medium having stored thereon a data structure may comprise a visual update block, including an identifier field having a visual identifier therein, and a field corresponding to an instruction block, the instruction block corresponding to a set of data related to a visual identified by the visual identifier, the set of data being passed from a high-level graphics processing component to a low-level graphics processing component, and the high-level component constructing the data structure from a scene graph and providing the data structure to the low-level component, the low-level component processing the data structure into graphics data for passing to a graphics subsystem to output a frame.

Other benefits and advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which:

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram representing an exemplary computer system into which the present invention may be incorporated;

FIG. 2 is a block diagram representing a media integration layer architecture in accordance with one aspect of the present invention;

FIG. 3 is a block diagram representing an intelligent caching data structure and its relationship to various components in accordance with one aspect of the present invention;

FIG. 4 is a block diagram representing the general flow of control between a high-level composition and animation engine and other levels in accordance with one aspect of the present invention;

FIG. 5 is a block diagram representing example containers and other nodes cached in a simple data structure and their relationships in accordance with one aspect of the present invention;

FIG. 6 is a block diagram representing general components of a low-level composition and animation engine interacting with other components in accordance with one aspect of the present invention;

FIG. 7 is a block diagram representing general components of the low-level composition and animation engine in accordance with one aspect of the present invention;

FIG. 8 is a block diagram representing logical structure of a connection to the low-level composition and animation engine in accordance with one aspect of the present invention;

FIGS. 9 and 10 comprise a block diagram representing the flow of information from a high-level composition and animation engine to the low-level composition and animation engine in accordance with one aspect of the present invention;

FIGS. 11 and 12 are block diagrams representing the flow of information through the media integration layer architecture layer to a graphics subsystem in accordance with one aspect of the present invention;

FIGS. 13-22 comprise data structures and describe other information used to communicate information from the high-level composition and animation engine to the low-level composition and animation engine in accordance with one aspect of the present invention; and

FIGS. 23 and 24 comprise a flow diagram generally describing logic for processing packets in accordance with one aspect of the present invention.

DETAILED DESCRIPTION

Exemplary Operating Environment

FIG. 1 illustrates an example of a suitable computing system environment 100 on which the invention may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.

The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, tablet devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, and so forth, which perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer 110. Components of the computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, Accelerated Graphics Port (AGP) bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

The computer 110 typically includes a variety of computer-readable media. Computer-readable media can be any available media that can be accessed by the computer 110 and includes both volatile and nonvolatile media, and removable and non-removable media. By way of example, and not limitation, computer-readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can accessed by the computer 110. Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of the any of the above should also be included within the scope of computer-readable media.

The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 1 illustrates operating system 134, application programs 135, other program modules 136 and program data 137.

The computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.

The drives and their associated computer storage media, discussed above and illustrated in FIG. 1, provide storage of computer-readable instructions, data structures, program modules and other data for the computer 110. In FIG. 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146 and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers herein to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 20 through input devices such as a tablet (electronic digitizer) 164, a microphone 163, a keyboard 162 and pointing device 161, commonly referred to as mouse, trackball or touch pad. Other input devices (not shown) may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. The monitor 191 may also be integrated with a touch-screen panel 193 or the like that can input digitized input such as handwriting into the computer system 110 via an interface, such as a touch-screen interface 192. Note that the monitor and/or touch screen panel can be physically coupled to a housing in which the computing device 110 is incorporated, such as in a tablet-type personal computer, wherein the touch screen panel 193 essentially serves as the tablet 164. In addition, computers such as the computing device 110 may also include other peripheral output devices such as speakers 195 and printer 196, which may be connected through an output peripheral interface 194 or the like.

The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 110, although only a memory storage device 181 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160 or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 1 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

Media Integration Layer Architecture

One aspect of the present invention is generally directed to leveraging more of the power of the graphics hardware that is present on typical computer systems. To this end, as generally presented in FIG. 2, a media integration layer architecture 200 is provided. An application, control or other similar higher-level program code (e.g., a user interface of an operating system component) 202 accesses the media integration layer architecture 200 via a set of application programming interfaces (APIs) 204 or the like, to access (write or read) graphical information. Note that although many of the examples described herein will refer to an application program interfacing with the APIs, it is understood that other higher-level program code and components (e.g., a user interface of the operating system) will also be able to interface with the lower level components described herein. As such, any reference to such higher-level program code, whether referred to as an application program, user interface, and so on, should be considered equivalent.

It should be noted that for various reasons including security, the media integration layer 200 (which outputs graphics) is preferably incorporated into the operating system. For example, while feasible to allow some or part of the media integration layer 200 to be inserted between the application and the operating system, doing so would enable a malicious program to display whatever graphics it wanted, and thereby cause harm. For example, malicious code could display a dialog box requesting entry of a password to thereby steal a user's password. Other reasons for incorporating the media integration layer 200 into the operating system include stability and efficiency, e.g., the lower levels can efficiently trust that the data and instructions from the higher layers are already verified. Further, the lower levels can expose interfaces that only the operating system is trusted to call responsibly, that is, without exposing those interfaces to unpredictable programs, thereby ensuring greater stability.

In one implementation, the media integration layer architecture 200 includes a high-level composition and animation engine 206, timing and animation components 208, and a low-level compositing and animation engine 210. As used herein, the terms "high-level" and "low-level" are similar to those used in other computing scenarios, wherein in general, the lower a software component relative to higher components, the closer the component is to the hardware. Thus, for example, graphics information sent from the high-level composition and animation engine 206 may be received at the low-level compositing and animation engine 210, where the information is used to send graphics data to the graphics subsystem including the hardware.

As described below, the high-level composition and animation engine (also referred to herein as the high-level compositor and animator or the high-level engine or component) 206 builds a display tree to represent a graphics scene provided by the application program 202, while the timing and animation components provide declarative (or other) animation and timing control. As also described below, the low-level compositing and animation engine (also referred to herein as the low-level compositor and animator or low-level engine or component) 210 composes the renderings for the scenes of multiple applications, and with rendering components, also referred to renderers, implement the actual rendering of graphics to the screen. Note, however, that at times it may be necessary and/or advantageous for some of the rendering to happen at higher levels. For example, while the lower layers service requests from multiple applications, the higher layers are instantiated on a per application basis, whereby is possible to do time consuming or application-specific rendering at a higher levels, and pass references to a bitmap to the lower layers.

In general, the high-level composition and animation engine 206 builds the display structure and traverses the structure creating rendering instructions and simple animation intervals to be passed to the low-level compositing and animation engine 210. The rendering instructions generated by the high level compositor may contain timing and animation information. The low-level compositing and animation engine 210 takes the rendering instructions and animation intervals and manages the animating, rendering and composing the scene that is then provided to the graphics subsystem (e.g., the graphics software and hardware) 212.

Alternatively or in addition to locally displayed output, the high-level composition and animation engine 206 (or one similar thereto) may provide the rendering and animation instructions in an appropriate format to lower-level printing code 220 for sending fixed image data to a printer 222 or the like, and/or may provide rendering instructions and simple animation intervals in an appropriate format to a lower-level terminal transport server 226 for transmission to remote machines 228. Note that richer information also may be passed across the network, e.g., it may be desirable to have the remote machine handle mouse rollover effects locally, without any network traffic.

Multiple Graphics Processing Levels

In accordance with an aspect of the present invention, the media integration layer architecture 200 thus separates graphics processing into multiple levels. Each of these levels performs some intelligent graphics processing which together allows applications, user interfaces and the like 202 to output graphics with smooth animation, composite the graphics with the graphics of other applications and with video frames. The animation and/or compositing may also be synchronized with audio output. For example, by synchronizing audio with the frame rate at the low level component, the timing of audio can essentially be exact with that of video or graphics, and not dependent on the ability of task-scheduled, complex pre-processing to keep up with the refresh rate.

As generally represented in FIG. 3, below the application 202 as communicated with via the APIs 204, the high-level compositor and animator engine 206 caches the application graphical data in a tree structure 300, pre-processes the data in an intelligent manner, and performs numerous other operations (described below) to facilitate the output of complex graphics. In general, the high-level compositor and animator engine 206 performs complex processing (sometimes referred to as compiling) that significantly simplifies the amount of processing and significantly reduces the amount of data that lower levels need to deal with to render the correct output. Note, however, that the amount and type of processing that is performed by the higher level may be dependent to a significant extent on the load, configuration and capabilities of the lower levels. For example, if high capability graphics hardware is present, the higher level may do a lesser amount of processing, and vice-versa. The high-level and low-level layers are adaptive to these factors.

In keeping with the present invention, the high-level composition and animation engine 206 can accomplish such complex processing without overwhelming the available system resources because it operates at a relatively slower rate than the level or levels below. By way of example, and not limitation, the lower levels may operate at the frame (refresh) rate of the hardware graphics processor. For example, the high-level compositor and animator 206 may only operate when needed to effect a display change, on demand, or on another schedule (e.g., every half second). Note that while a single high-level compositor and animator engine 206 is represented in FIG. 3, there may be multiple instances of them, such as one per application, while there is typically only one low-level compositing and animation engine 210 per graphics device, e.g., one for each graphics hardware card on a machine.

Moreover, the high-level compositor and animator 206 can tailor its output to (or be designed to output) a format of the appropriate level or levels below, e.g., essentially any abstract device 302. For example, the high-level compositor and animator 206 can produce compiled output that is ultimately destined for a printer, for transmission over a network to a number of remote terminals for display thereon, or, as will be primarily described herein, for a lower-level compositor and animator 210 that is present above local graphics software and hardware 212. A single high-level compositor and animator may process the output of an application for a plurality of abstract devices, or there may be a suitable instance of a high-level compositor and animator to process the output of an application for each type of abstract device, e.g., one for local graphics, one for a printer and one for a terminal server.

Further, the commands and other data provided by the high-level compositor and animator 206 can be simplified to match the capabilities and requirements of the hardware, e.g., the lesser the hardware, the more high-level pre-processing needed. Still further, the amount of high-level pre-processing may be dynamic, e.g., so as to adjust to the varying processing demands placed on the lower level or levels.

For local graphics output, in one configuration the media integration layer architecture 200 includes the high-level compositor and animator 206, and the low-level compositor and animator 210. As will be described below, in general, the high-level compositor and animator 206 performs complex processing of graphics information received from clients (e.g., applications) to build graphics structures and convert these structures into a stream of graphics commands. The low-level engine 210 then uses the streams of graphics commands from various clients to compose the desktop that is viewed by the computer user, e.g., the low-level compositor composes the desktop by combining the command streams emitted by the various clients present on the desktop into graphics commands consumed by a graphics compositing engine.

In this implementation, the high-level compositor and animator 206 performs the complex processing operations that build and convert the structures 300 into the stream of graphics commands at a rate that is normally much slower than the hardware refresh rate of the graphics hardware of the graphics subsystem 212. As a result of this high-level pre-processing, the low-level engine 210 is able to perform its own processing operations within the hardware refresh interval of the graphics hardware of the graphics subsystem 212. As mentioned above, however, the low-level engine 210 can communicate back to the high-level engine 206 over a back channel so that the high-level pre-processing can dynamically adjust to the low-level processing demands. Note that the back-channel from the low-level compositor and animator 206 to the high-level compositor and animator 206 is primarily for communicating flow control (the low-level engine 210 signaling it needs more data or is receiving too much) to the high level engine 206 and/or error conditions actionable by the high level engine 206. One advantage of such communication is that the low-level compositing and animation engine 210 need not be concerned with priorities or scheduling, but can remain in synchronization with the refresh rate. Instead, the high-level CPU process scheduling already present in contemporary operating systems will control priority. Thus, for example, if an application process attempts to take too much of its share of high-level graphics pre-processing relative to its priority, it will be that application that is adversely affected in its output. Note, however, that when the low-level system is under heavy load, it can choose to prioritize the changes and demands of one process/high-level component over another. For example, the foreground application can be given priority.

The High-Level Compositor and Animator

In one embodiment, the media integration layer 200 including the high-level compositor and animator 206 adjusts for hardware differences on a given machine, because each user application cannot realistically be written to handle the many types and variations of graphics hardware. However, applications may also contribute to the improved graphics processing provided by the media integration layer 200, namely by providing more (and different) information to the high-level compositor and animator 206 than that presently passed to an operating system's graphics APIs. For example, applications that are aware of the media integration layer 200 may provide different data, including animation intentions and the like via the media integration layer APIs 202. By way of example, instead of performing animation by continually redrawing a slightly varied image, the application can provide an instruction as to how a particular image should move over time, e.g., relative to a fixed background. The media integration layer 200 then handles the automation in a smoothly rendered way, as generally described below.

In general, as represented in FIGS. 3 and 4, the application 202 builds a scene graph data structure via APIs 204. The data includes high level structure and primitive data, and is put into a cache data structure 300 that is used to intelligently cache visual information.

One of the objects (or structures) in the overall intelligent caching data structure 300 is a container, represented in FIG. 4 by containers 402, 404 or 408, (alternatively referred to as a Visual2D). In one implementation, a container (e.g., 404) provides identity in that an application can hold a handle to it, and includes procedural parameters which can be used for hooking up animation and templating, hit-testing and user data. Note however that the containers represented herein are not the only types of containers that might be exposed. Other examples may include containers that are optimized for storing lines in a paragraph or for storing many children in a grid. Children containers may be added and removed without clearing the current list of children, although certain types of containers may not allow random access to the children. The structure exposed through the API can be adapted as needed.

Other (internal) nodes of this data structure include transforms 406, alpha nodes, cache nodes, and primitive nodes 410, 412, used to store internal data not directly associated with an API container. Primitives are generally stored as a stream of instructions that can be passed directly to the graphics device.

As represented in the tree segment 500 of FIG. 5, a container such as 510 can thus hold other containers 512 or drawing primitives 516, wherein storage of the primitives inside of any container can be considered a stream of graphics instructions. A container can also store other containers, in effect creating a graph, i.e., containers can be referenced by more than one container so that the data structure is a directed acyclic graph (DAG) of containers and lists of primitives (wherein no container can contain one of its parent containers). As also represented in FIG. 5, by allowing trees to reference other trees in a graph-like way, any of the containers, such as the container 518 in the tree segment 502 may be reused in different places, yet with different parameters.

A container is populated via an open/close pattern, such as generally represented in the drawing context 416 of FIG. 4. More particularly, the higher level code 202 opens a container 408 in the data structure, provides the drawing context 416 to write drawing primitives and/or add other containers into the data structure, and then closes the container 408. In one alternative implementation, when the container is closed, its data is put into a change queue 418 that is then applied at some later time. The opening and closing of containers is one of the main mechanisms for changing the data structure. Note that other usage patterns may be employed, particularly for different types of containers.

In this alternative, because the changes to the data structure are put into a queue, a transaction-like (or batch-like) system for updating the data structure is enabled. As a result, when opening and writing to a container, no changes are apparent on the screen until the container is closed. The changes to the screen are atomic and there are no temporal artifacts (also referred to as structural tearing) of a partially drawn screen. Further, such transactional behavior can be extended so that changes to multiple containers are applied at once. In this way the higher level code 202 can set up many changes to a scene and apply those changes all at once.

In one alternative implementation, changes to the data structure are made asynchronously by posting changes to the queue 418 via a display manager 420, such that the changes will be processed on a rendering thread 422, and for example, sent to the low level compositor and animator 210, (wherein the abstract device 302 of FIG. 3 comprises the abstraction that encapsulates the conversion of rendering commands issued by the high level compositor 206 into rendering commands streamed to the low level compositor 210). The transaction-like model also enables modifications to the data structure to be made without interrupting reading from the data structure. Although the above-described queue model enables the read passes from the high-level engine 206 to run independent of any actions that the user takes, user applications need the cache to maintain a consistent view of the APIs, which may lead to inefficiencies. By way of example, consider a user application on the main user thread setting a property on a container (object in the high-level engine 206). In the queue model, this property gets put into a queue to be applied to the high-level engine 206 data structure. However, if the user application tries to immediately read back that property from the container, the system will need to read the property back based on what is currently in the queue (which is inefficient), synchronize with the rendering thread and apply the pending changes in the queue (which is inefficient and would negate the benefits of having the queue), or keep copies of user changeable data, both the render version and the pending version, on the container (which is an inefficient use of memory).

Because there may be a considerable amount of reading back by applications, an alternative implementation essentially eliminates the queue by synchronizing the updating of the high-level engine 206 data structures and the main user thread. Although this enables the user application to freeze the rendering, the overall system is more efficient. However, to mitigate the perceived effects of possible freezing, various parts of the animation and timing system may be run independently to communicate information down to the low-level engine 210, while trusting the low-level engine 210 to do more animation processing independent of the high-level engine 206. Then, if the high-level engine 206 is frozen because of a user action, the output to the screen will still be relatively smooth and consistent.

Yet another alternative is to eliminate the render thread, and have the main user thread perform any processing necessary for the high-level engine 206 to pass the rendering instructions to the low-level engine 210. This is a more efficient use of threads in some cases.

Returning to FIG. 4, the container 408 comprises a basic identity node that contains drawing primitives, while the draw context 416 comprises a graph builder (e.g., a helper object) obtained from a container that can be used to add primitives, transforms, clips or other drawing operations to the container. The display manager 420 comprises a hosting object that represents an instance of the high-level compositor and animator 206, and for example, can attach to an hand (handle to a window) or an visual (handle to a visual container). The display manager 420 has a pointer to the root container 402 for the scene, dispatches events to the high level code when containers are invalid and need to be redrawn, and provides access to services such as hit testing and coordinate transforms.

Although the higher level code 202 can hold a handle or the like to some of the objects in the data structure and containers, most of the objects in the container do not have an identity from the perspective of the application. In particular, access to this structure is restricted in that most usage patterns are "write only." By limiting identity in this manner, more of the information stored in the data structure can be optimized, and the higher level code 202 does not have to store object information or deal with managing the objects' lifetimes.

For example, the resources that maintain part of the graph that is not needed (e.g., corresponds to visual information that has been clipped or scrolled off the screen) may be reclaimed, with the application requested to redraw the scene if later needed. Thus, generally when a container is opened its contents are cleared and forgotten. If those contents do not have identity, then they may safely disappear so that the resources for them can be reclaimed by the system. If the higher level code 202 or some other part of the graph is holding on to child containers, those containers stay around and can be reinserted. However, this pattern can be changed and adapted depending on the needs of the higher level code 202.

Thus, to summarize, the container is an object that has identity in that the high level code using the data structure can hold a handle to that object. The opposite of an object with identity is plain data, and while the user code may employ a mental model that treats the data without identity as an object, once this data is committed to the system there is no way to later reference that object. In this manner, the object can be transformed and changed in ways that are convenient to the system.

As a simplified example, an API function for drawing a line of text might include a TextLine object. The user of this object would prime the TextLine object with the actual text to be drawn, along with the other information on how to render different runs of that text (font, size, brush, and so forth). When the user program code wants to actually add that line of text to the data structure, the program code may take a drawing context for a particular open node, and pass the TextLine object into a drawing function on the drawing context. The system in effect takes the data that is in that TextLine object and copies the data into the data structure. Because this data does not have identity, the high-level compositor and animator engine 206 is free to take the contents of that line, run algorithms (e.g., OpenType) to break the text down to glyphs with positions, and store the positioned glyph data instead of the raw text. After that line was drawn the system would have no reference to the TextLine object that was used to draw the line, i.e., the data that the system stores does not have any identity.

Alternatively, the higher level code 202 may request that identity be preserved on that TextLine object, requiring the storing of a reference to that object in the data structure. In this manner, if the higher level code 202 later changes the TextLine object, the system will discover that change and reflect it in the rendered output. Note that in a more realistic example, identity would not be exposed on the text line object itself, but rather the application would hold a handle to a container and make changes as desired by parameterizing that container, as described in the aforementioned U.S. patent application entitled "Generic Parameterization for a Scene Graph." Nevertheless, one of the main aspects of the data structure is to reduce the need for the higher level code 202 to create such objects with identity, whereby a reduced number of points in the data structure will be referenced by the controlling code 202. This enables more optimization of the data structure.

For example, because of the reduction in the amount of identity exposed outside of the data structure, an optimization such as the dense storage of primitives is enabled. To this end, vector graphic data is stored in a "primitive list" or primitive container. These containers are implementation specific and are not exposed with identity to the higher-level code 202. When the caller writes data into a container, that data is either stored in separate objects that are linked in, like the containers, (e.g., with transforms), or can be streamed into a packed and flattened data array. This array may not only store the vector graphic data in a compact way, but may also track the resources that go along with those primitives. Because the individual primitives do not have identity, there is no need to separate the primitives out or provide a way for the user to change those primitives later, enabling more efficient storage of the primitives.

As another optimization, when a subgraph is not changing, it is possible to store a bitmap of the contents of that tree, and attach the bitmap to a container, thereby reducing the amount of high-level processing needed. Further, when a subgraph or part of a primitive list requires significant processing before it can be passed to a lower-level code for rendering, (e.g. tessellation of vector graphics before being handed off to a hardware device), the post-processed result may be cached for later reuse.

Moreover, since there is no exposure of the structure except for specific read operations (described below), the data structure is free to reorganize containers so long as the rendered result is the same. A container may therefore store the child containers in a space partitioning tree to optimize rendering and other read operations. Further, the data structure may be displayed multiple times on the same device or on multiple devices. For this reason the caches may be keyed based on device if they are device dependent. If a subtree is recognized as being static, repainted often because of animations around it and yet is dense enough to warrant the resource drain, a cache node may be automatically inserted for that sub-tree.

For rendering, the data structure is read (either at some scheduled time or by a different thread) and processed information of some form is passed to the lower-level animator and compositor 210. To this end, in one alternative implementation, a render object and thread (per process) 422 traverses the data structure 300 to drive the render process. In another alternative, instead of running on its own thread, the render process may share time on a common thread with the rest of the user's code in a type of "cooperative multitasking" arrangement. The data structure 300 can be used for direct rendering, although preferably it is compiled into the visual information that is fed to the lower-level components for very fast compositing and animation. The data structure 300 can also be compiled in different ways, such as to be sent across a network to a remote terminal, to a printer and/or serialized to disk or some other more permanent storage medium for interchange or caching.

In one alternative implementation, the data structure 300 is read for rendering on another thread 422. However, it should be noted that the use of another thread is not a requirement, e.g., the "render thread" may alternatively comprise a cooperative sharing mechanism that runs on the same thread as everything else.

In the alternative model that uses a rendering process/thread, the rendering thread runs as needed to provide the intended effect. Each time the thread runs, it first applies any pending changes that are in the change queue 418. The render thread 422 then walks the data structure 300 to collect information such as bounding boxes and collect invalidations (described below). Lastly it walks the areas that have changed since last time or need to be rendered for some other reason, and executes the rendering instructions that are stored in the data structure. Note that in the alternative model that does not use the