Deferred acceleration data structure optimization for improved performance

• US 8,018,453 B2
• Filed: 02/09/2007
• Issued: 09/13/2011
• Est. Priority Date: 02/09/2007
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Fowler, David Keith, Shearer, Robert Allen
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US11/673,042
• Publication Number:
  US 20080192044A1
• Time in Patent Office: 1,677 Days
• Field of Search: 345/419, 345/420, 345/421, 345/423, 345/426, 345/427, 345/506, 345/440, 345/473, 345/522, 707/101
• US Class Current: 345/419
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

Embodiments of the invention provide methods and apparatus to defer the optimization an acceleration data structure (e.g., a kd-tree) in response to movements of objects within a three-dimensional scene. According to one embodiment of the invention, an image processing system may determine portions of an acceleration data structure affected by the movement of an object within a three-dimensional scene. The image processing system may store the affected portion of the ADS in an optimization queue. If the image processing system does not have sufficient processing bandwidth available to optimize the ADS, the image processing system may defer the ADS optimization until sufficient processing bandwidth becomes available. Once sufficient processing bandwidth becomes available, the image processing system may optimize the ADS according to the information stored in the optimization queue.

Claims

1. A method of updating an acceleration data structure, comprising:

Determining, by an image processing system, an affected portion of the acceleration data structure affected by a movement of an object within a three-dimensional scene;

Adding, by the image processing system, an indication of the affected portion to an optimization queue; and

when the processing element has free bandwidth, updating, by the image processing system, the acceleration data structure based on information in the optimization queue.

2. The method of claim 1, wherein updating, by the image processing system, the acceleration data structure based on the information in the optimization queue comprises:

determining, by the image processing system, portions of the three-dimensional scene corresponding to portions of the acceleration data structure indicated in the optimization queue; and

repartitioning, by the image processing system, the portions of the three-dimensional scene based on the position of the object.

3. The method of claim 1, wherein determining, by the image processing system, the portion of the acceleration data structure corresponding to the area into which the object moved comprises:

creating, by the image processing system, a box which surrounds the object in a final position;

tracing, by the image processing system, the box through the integrated acceleration data structure having nodes defining bounding volumes within the three-dimensional scene by taking branches to nodes defining bounding volumes intersected by the box until at least one leaf node is reached; and

adding, by the image processing system, to the optimization queue, a pointer to the at least one leaf node.

4. The method of claim 3, further comprising:

determining, by the image processing system, an internal node in the acceleration data structure which branches to the at least one leaf nodes affected by the movement of the object; and

adding, by the image processing system, to the optimization queue, a pointer to the internal node.

5. The method of claim 3, wherein the optimization queue contains a linked list of nodes defining bounding volumes intersected by the box.

6. The method of claim 1, wherein the acceleration data structure is a k-dimensional tree.

7. The method of claim 3, wherein determining, by the image processing system, when a processing element has free bandwidth comprises monitoring, by the image processing system, at least one of a performance counter or an inbox associated with a processing element.

8. A computer readable non-transitory medium containing a program which, when executed, performs operations comprising:

determining a portion of an acceleration data structure affected by a movement of an object within a three-dimensional scene;

adding an indication of the portion of the acceleration data structure affected by the movement of the object within the three-dimensional scene to an optimization queue; and

when the processing element has free bandwidth, updating the acceleration data structure based on information in the optimization queue.

9. The computer readable non-transitory medium of claim 8, wherein updating the acceleration data structure based on the information in the optimization queue comprises:

determining portions of the three-dimensional scene corresponding to portions of the acceleration data structure indicated in the optimization queue; and

repartitioning the portions of the three-dimensional scene based on the position of the object.

10. The computer readable non-transitory medium of claim 8, wherein determining the portion of the acceleration data structure corresponding to the area into which the object moved comprises:

creating a box which surrounds the object in a final position;

tracing the box through the integrated acceleration data structure having nodes defining bounding volumes within the three-dimensional scene by taking branches to nodes defining bounding volumes intersected by the box until at least one leaf node is reached; and

adding to the optimization queue, a pointer to the at least one leaf node.

11. The computer readable non-transitory medium of claim 10, further comprising:

determining an internal node in the acceleration data structure which branches to the at least one leaf nodes affected by the movement of the object; and

adding to the optimization queue, a pointer to the internal node.

12. The computer readable non-transitory medium of claim 8 wherein the acceleration data structure is a k-dimensional tree.