Intelligent caching data structure for immediate mode graphics

• US 7,064,766 B2
• Filed: 06/27/2002
• Issued: 06/20/2006
• Est. Priority Date: 10/18/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Adam M., Gallo, Kevin T., Michail, Ashraf A., Beda, Joseph S., Schneider, Gerhard A.
• Primary Examiner(s): Chauhan, Ulka
• Assistant Examiner(s): Singh, Dalip K.
• Application Number:
  US10/185,775
• Publication Number:
  US 20030076329A1
• Time in Patent Office: 1,454 Days
• Field of Search: 709/219, 715/500.1, 345/419, 345/473, 345/440, 707/102.3, 707/104.1, 719/328
• US Class Current: 345/557
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/32 Image data format

Abstract

An intelligent caching data structure and mechanisms for storing visual information via objects and data representing graphics information. The data structure is generally associated with mechanisms that intelligently control how the visual information therein is populated and used. The cache data structure can be traversed for direct rendering, or traversed for pre-processing the visual information into an instruction stream for another entity. Much of the data typically has no external reference to it, thereby enabling more of the information stored in the data structure to be processed to conserve resources. A transaction/batching-like model for updating the data structure enables external modifications to the data structure without interrupting reading from the data structure, and such that changes received are atomically implemented. A method and mechanism are provided to call back to an application program in order to create or re-create portions of the data structure as needed, to conserve resources.

Claims

1. In a computing environment, a system comprising,

a cache that maintains visual information;

a queue for maintaining changes to the visual information as requested by higher level program code;

an interface to the cache through which the visual information is accessed by the program code, the program code accessing the visual information via the interface, including requesting access to a container in the cache;

a drawing context that opens the container and provides a surface through which the program code requests changes to data in the container;

a batching mechanism, the batching mechanism deferring the writing of any change to the queue until at least the close of the container, such that changes to the container occur as an atomic operation;

a rendering mechanism that applies the changes in the queue and traverses the cache to create an instruction stream based on the visual information including the changes, wherein the rendering mechanism operates at a fixed rate.

2. The system of claim 1 wherein at least part of the batching mechanism is incorporated into a function of the drawing context.

3. The system of claim 1 wherein the batching mechanism defers the writing of any change to the queue until the close of the container and the close of at least one other container.

4. The system of claim 1 wherein the contents of the container are cleared upon opening of the container.

5. The system of claim 1 wherein the rendering mechanism operates on demand in response to change information being in the queue.

6. In a computing environment, a method comprising:

maintaining a scene graph;

receiving a first request to implement a first change in a structure of the scene graph;

receiving a second request to implement a second change in the structure;

implementing the changes to the first and second data atomically by making the changes only upon receipt of an instruction that requests implementation of the changes, including writing change data to a change queue;

applying the changes in the change queue to the scene graph and traversing the scene graph to generate an instruction stream based on the scene graph including the changes to the structure, wherein applying the changes in the change queue and the traversing of the scene graph occur at a first operating rate to provide the instruction stream to a low-level component, and

executing the low-level component at a second operating rate to provide drawing commands based on the instructions to a graphics subsystem, the second operating rate being greater than the first operating rate and corresponding to a frame rate of the graphics subsystem.

7. The method of claim 6, wherein implementing the changes comprises, writing change data to a change queue.

8. The method of claim 6, wherein the instruction that requests implementation of the changes corresponds to a close command.

9. The method of claim 6 wherein the structure comprises a container, and further comprising, receiving a command to open the container prior to receiving the first and second requests.

10. The method of claim 9, wherein the instruction that requests implementation of the changes corresponds to a command to close the container.

11. The method of claim 9, further comprising, opening the container and clearing the instructions.

12. The method of claim 6 further comprising, receiving an access request to access the structure, and returning a drawing context in response to the access request.

13. The method of claim 6 wherein implementing the changes atomically comprises, making the changes based on receipt of the instruction and receipt of at least one other instruction that corresponds to at least one other structure in the scene graph.

14. A computer-readable medium having computer-executable instructions, comprising:

maintaining a scene graph;

receiving a first request to implement a first change in a structure of the scene graph;

receiving a second request to implement a second change in the structure; and

implementing the changes to the first and second data atomically by making the changes only upon receipt of an instruction that requests implementation of the changes, including writing change data to a change queue;

applying the changes in the change queue to the scene graph and traversing the scene graph to generate an instruction stream based on the scene graph including the changes to the structure;

wherein the changes in the change queue and the traversing of the scene graph occur at a first operating rate to provide the instruction stream to a low-level component, and

executing the low-level component at a second operating rate to provide drawing commands based on the instructions to a graphics subsystem, the second operating rate being greater than the first operating rate and corresponding to a frame rate of the graphics subsystem.

15. The computer-readable medium of claim 14, wherein implementing the changes comprises, writing change data to a change queue.

16. The computer-readable medium of claim 14, wherein the instruction that requests implementation of the changes corresponds to a close command.

17. The computer-readable medium of claim 14 wherein the structure comprises a container, and having at least one further computer-executable instruction comprising, receiving a command to open the container prior to receiving the first and second requests.

18. The computer-readable medium of claim 17, wherein the instruction that requests implementation of the changes corresponds to a command to close the container.

19. The computer-readable medium of claim 17, having further computer-executable instructions comprising, opening the container and clearing the instructions.

20. The computer-readable medium of claim 14 having further computer-executable instructions comprising, receiving an access request to access the structure, and returning a drawing context in response to the access request.

21. The computer-readable medium of claim 14 wherein implementing the changes atomically comprises, making the changes based on receipt of the instruction and receipt of at least one other instruction that corresponds to at least one other structure in the scene graph.

22. A computer-readable medium having computer-executable instructions, comprising:

maintaining visual information in a cache data structure including container and data;

reserving an invalid container for storing graphics information, without having space allocated for the graphics information; and

rendering the data structure into data for receipt by another entity at a fixed rate, including determining whether the graphics information of the invalid container is needed, and if so;

1) allocating resources for the graphics information;

2) calling back to higher-level program code to provide the graphics information;

3) receiving the graphics information; and

4) outputting the data for receipt by another entity including information corresponding to the graphics information received.

23. The computer-readable medium of claim 22 wherein reserving the invalid container comprises, marking a container as invalid and reclaiming space allocated for graphics information.

24. The computer-readable medium of claim 22 wherein reserving the invalid container comprises, receiving instructions from the higher-level program code to reserve an invalid container.

25. The computer-readable medium of claim 22 wherein outputting the data for receipt by another entity includes, outputting an instruction stream for a low-level engine that converts the instruction stream to graphics information understood by a graphics subsystem.

26. The computer-readable medium of claim 22 having further computer-executable instructions comprising, waiting for the data from the higher-level program code before completing the rendering of the cache data structure.

27. The computer-readable medium of claim 22 wherein calling back to higher-level program code comprises, queuing a request back to a thread executing the higher-level program code.

32. The computer-readable medium of claim 27 claim 28 wherein the rendering mechanism operates on demand in response to change information being in the queue.

28. A computer-readable medium having computer-executable components, comprising:

a cache that maintains visual information;

a queue for maintaining changes to the visual information as requested by higher level program code;

an interface to the cache through which the visual information is accessed by the program code, the program code accessing the visual information via the interface, including requesting access to a container in the cache; and

a drawing context that opens the container and provides a surface through which the program code requests changes to data in the container, and

a batching mechanism, the batching mechanism deferring the writing of any change to the queue until at least the close of the container, such that changes to the container occur as an atomic operation; and

a rendering mechanism that operates at a fixed rate and applies the changes in the queue and traverses the cache to create an instruction stream based on the visual information including the changes.

29. The computer-readable medium of claim 28 wherein at least part of the batching mechanism is incorporated into a function of the drawing context.

30. The computer-readable medium of claim 28 wherein the batching mechanism defers the writing of any change to the queue until the close of the container and the close of at least one other container.

31. The computer-readable medium of claim 28 wherein the contents of the container are cleared upon opening of the container.

33. In a computing environment, a system comprising,

a cache that maintains visual information;

a queue for maintaining changes to the visual information as requested by higher level program code;

an interface to the cache through which the visual information is accessed by the program code, the program code accessing the visual information via the interface, including requesting access to a container in the cache;

a drawing context that opens the container and provides a surface through which the program code requests changes to data in the container;

a batching mechanism, the batching mechanism deferring the writing of any change to the queue until at least the close of the container, such that changes to the container occur as an atomic operation; and

a rendering mechanism that applies the changes in the queue and traverses the cache to create an instruction stream based on the visual information including the changes, wherein the rendering mechanism comprises a high-level component that executes at a first operating rate to provide the instruction stream to a low-level component, wherein the low-level component runs at a second operating rate to provide drawing commands based on the instructions to a graphics subsystem, and wherein the second operating rare is greater than the first operating rate and corresponds to a frame rate of the graphics subsystem.

34. The system of claim 33 wherein at least part of the batching mechanism is incorporated into a function of the drawing context.

35. The system of claim 33 wherein the batching mechanism defers the writing of any change to the queue until the close of the container and the close of at least one other container.

36. The system of claim 33 wherein the contents of the container are cleared upon opening of the container.

37. The system of claim 33 wherein the rendering mechanism operates on demand in response to change information being in the queue.

38. A computer-readable medium having computer-executable instructions, comprising:

maintaining visual information in a cache data structure including containers and data;

reserving an invalid container for storing graphics information, without having space allocated for the graphics information; and

rendering the data structure into data for receipt by another entity including executing a high-level component at a first operating rate to provide an instruction stream to a low-level component, the low-level component running at a second operating rate to provide drawing commands based on the instructions to a graphics subsystem, wherein the second operating rate is greater than the first operating rate and corresponds to a frame rate of the graphics subsystem, including determining whether the graphics information of the invalid container is needed, and if so;

2) allocating resources for the graphics information;

2) calling back to higher-level program code to provide the graphics information;

3) receiving the graphics information; and

4) outputting the data for receipt by another entity including information corresponding to the graphics information received.

39. The computer-readable medium of claim 38 wherein reserving the invalid container comprises, marking a container as invalid and reclaiming space allocated for graphics information.

40. The computer-readable medium of claim 38 wherein reserving the invalid container comprises, receiving instructions from the higher-level program code to reserve an invalid container.

41. The computer-readable medium of claim 38 wherein outputting the data for receipt by another entity includes, outputting an instruction stream for a low-level engine that converts the instruction stream to graphics information understood by a graphics subsystem.

42. The computer-readable medium of claim 38 having further computer-executable instructions comprising, waiting for the data from the higher-level program code before completing the rendering of the cache data structure.

43. The computer-readable medium of claim 38 wherein calling back to higher-level program code comprises, queuing a request back to a thread executing the higher-level program code.

44. A computer-readable medium having computer-executable components, comprising:

a cache that maintains visual information;

a queue for maintaining changes to the visual information as requested by higher level program code;

an interface to the cache through which the visual information is accessed by the program code, the program code accessing the visual information via the interface, including requesting access to a container in the cache; and

a drawing context that opens the container and provides a surface through which the program code requests changes to data in the container; and

a batching mechanism, the batching mechanism deferring the writing of any change to the queue until at least the close of the container, such that changes to the container occur as an atomic operation; and

a rendering mechanism comprising a high-level component that executes at a first operating rate to provide an instruction stream to a low-level component, wherein the low-level component rims at a second operating rate to provide drawing commands based on the instructions to a graphics subsystem, and wherein the second operating rate is greater than the first operating rate and corresponds to a frame rate of the graphics subsystem.

45. The computer-readable medium of claim 44 wherein at least part of the batching mechanism is incorporated into a function of the drawing context.

46. The computer-readable medium of claim 44 wherein the batching mechanism defers the writing of any change to the queue until the close of the container and the close of at least one other container.

47. The computer-readable medium of claim 44 wherein the contents of the container are cleared upon opening of the container.

48. The computer-readable medium of claim 44 having at least one further computer-executable component comprising a rendering mechanism that applies the changes in the queue and traverses the cache to create an instruction stream based on the visual information including the changes.

49. The computer-readable medium of claim 44 wherein the rendering mechanism operates on demand in response to change information being in the queue.