Combined spatial index for static and dynamic objects within a three-dimensional scene

• US 8,004,518 B2
• Filed: 02/14/2007
• Issued: 08/23/2011
• Est. Priority Date: 02/14/2007
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Fowler, David Keith, Radzikowski, Eric Michael, Shearer, Robert Allen
• Primary Examiner(s): Hajnik, Daniel F
• Application Number:
  US11/674,821
• Publication Number:
  US 20080192054A1
• Time in Patent Office: 1,651 Days
• Field of Search: None
• US Class Current: 345/420
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

Embodiments of the invention create links or branches from a static spatial index which partitions a three-dimensional scene based on the position of static objects to a dynamic object spatial index which partitions a three-dimensional scene based on the position of dynamic objects in a three-dimensional scene. By branching from the static spatial index to the dynamic object spatial index, the image processing system may create a single combined spatial index or a combined acceleration data structure. The combined spatial index may contain information which partitions the three-dimensional scene with respect to both static objects and dynamic objects within the three-dimensional scene. When performing ray tracing, the image processing system may only need to traverse rays issued into the three-dimensional scene through the combined spatial index to determine if the ray intersects either static objects or dynamic objects within the three-dimensional scene.

Claims

1. A method of creating a combined spatial index, comprising:

configuring one or more processors for performing an operation, comprising;

creating a static spatial index which partitions a three-dimensional scene based on the position of static objects within the scene;

creating a bounding volume which surrounds a dynamic object within the scene;

creating a dynamic object spatial index by partitioning the bounding volume which surrounds the dynamic object into at least two bounding volumes;

tracing the bounding volume which surrounds the dynamic object through the static spatial index until at least one leaf node of the static spatial index is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object;

creating at least one branch from the at least one leaf node of the static spatial index to at least one node of the dynamic object spatial index to form the combined spatial index; and

modifying the combined spatial index based on a new position of the dynamic object, wherein at least one of;

(i) the dynamic object spatial index and (ii) a branch from the static spatial index to the dynamic object spatial index is modified.

2. The method of claim 1, wherein the at least one branch is from the at least one leaf node of the static spatial index to a world node of the dynamic object spatial index.

3. The method of claim 1, further comprising:

tracing a bounding volume defined by the at least one leaf node of the static spatial index through the dynamic object spatial index until at least one leaf node of the dynamic object spatial index is reached by taking branches to nodes of the dynamic object spatial index intersected by the bounding volume defined by the at least one leaf node of the static spatial index; and

wherein the at least one branch from a node in the static spatial index to at least one node of the dynamic object spatial index is from the at least one leaf node of the static spatial index to the at least one leaf node of the dynamic object spatial index.

4. The method of claim 1, wherein the static spatial index is a kd-tree having axis-aligned bounding volumes.

5. The method of claim 4, wherein the sides of the bounding volume which surrounds the dynamic object are aligned corresponding to axes used to construct the kd-tree.

6. The method of claim 1, wherein the static spatial index is an integrated accelerated data structure having at least one branch from a node which defines a bounding volume to a node which defines an object.

7. The method of claim 1, wherein modifying the combined spatial index based on the new position of the dynamic object comprises:

updating the bounding volume surrounding the dynamic object based on the new position of the dynamic object;

updating the dynamic object spatial index based on a new position of the bounding volume surrounding the dynamic object; and

tracing the bounding volume surrounding the dynamic object through the static spatial index until at least one leaf node is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object.

18. The method of claim 1, wherein the bounding volume surrounding the dynamic object is traced through the static spatial index until at least one leaf node is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object.

19. The method of claim 1, wherein the at least one node of the dynamic object spatial index comprises an internal node containing:

(i) information which indicates an axis along which the splitting plane is drawn;

(ii) information which indicates a position of the splitting plane along the axis; and

(iii) a pointer to a child node, wherein the child node is selected from a second internal node and a leaf node, wherein the leaf node represents a bounding volume that is not further subdivided by any splitting plane defined by the dynamic object spatial index, and wherein the leaf node comprises a pointer to the dynamic object in the three-dimensional scene.

20. The method of claim 1, wherein the static spatial index is created based on the static objects and not based on any dynamic object within the three-dimensional scene, wherein the dynamic object spatial index is created based on the dynamic object and not based on any static object within the three-dimensional scene, and wherein the dynamic object spatial index and the static spatial index are created separately from one another.

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

creating a static spatial index which partitions a three-dimensional scene based on the position of static objects within the scene;

creating a bounding volume which surrounds a dynamic object within the scene;

creating a dynamic object spatial index by partitioning the bounding volume which surrounds the dynamic object into at least two bounding volumes;

tracing the bounding volume which surrounds the dynamic object through the static spatial index until at least one leaf node is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object;

creating at least one branch from the at least one leaf node of static spatial index to at least one node of the dynamic object spatial index to form a combined spatial index; and

modifying the combined spatial index based on a new position of the dynamic object, wherein at least one of;

(i) the dynamic object spatial index and (ii) a branch from the static spatial index to the dynamic object spatial index is modified.

9. The non-transitory computer readable medium of claim 8, wherein the at least one branch is from the at least one leaf node of the static spatial index to a world node of the dynamic object spatial index.

10. The non-transitory computer readable medium of claim 8, wherein modifying the combined spatial index based on the new position of the dynamic object comprises:

tracing a bounding volume defined by the at least one leaf node of the static spatial index through the dynamic object spatial index until at least one leaf node of the dynamic object spatial index is reached by taking branches to nodes of the dynamic object spatial index intersected by the bounding volume defined by the at least one leaf node of the static spatial index; and

wherein the at least one branch from a node in the static spatial index to at least one node of the dynamic object spatial index is from the at least one leaf node of the static spatial index to the at least one leaf node of the dynamic object spatial index.

11. The non-transitory computer readable medium of claim 8, wherein the operations further comprise:

updating the bounding volume surrounding the dynamic object based on the new position of the dynamic object;

updating the dynamic object spatial index based on a new position of the bounding volume surrounding the dynamic object; and

tracing the bounding volume surrounding the dynamic object through the static spatial index until at least one leaf node is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object.

12. A system, comprising:

a memory comprising a static spatial index which partitions a three-dimensional scene based on the position of static objects within the scene; and

a processing element configured to;

create a bounding volume which surrounds a dynamic object within the scene;

create a dynamic object spatial index by partitioning the bounding volume which surrounds the dynamic object into at least two bounding volumes;

trace the bounding volume which surrounds the dynamic object through the static spatial index until at least one leaf node of the static spatial index is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object;

create at least one branch from the at least one leaf node of the static spatial index to at least one node of the dynamic object spatial index to form a combined spatial index; and

modify the combined spatial index based on a new position of the dynamic object, wherein at least one of;

(i) the dynamic object spatial index and (ii) a branch from the static spatial index to the dynamic object spatial index is modified.

13. The system of claim 12, wherein the at least one branch is from the at least one leaf node of the static spatial index to a world node of the dynamic object spatial index.

14. The system of claim 12, wherein the processing element is further configured to trace a bounding volume defined by the at least one leaf node of the static spatial index through the dynamic object spatial index until at least one leaf node of the dynamic object spatial index is reached by taking branches to nodes of the dynamic object spatial index intersected by the bounding volume defined by the at least one leaf node of the static spatial index;

and

wherein the at least one branch from a node in the static spatial index to at least one node of the dynamic object spatial index is from the at least one leaf node of the static spatial index to the at least one leaf node of the dynamic object spatial index.

15. The system of claim 12, wherein modifying the combined spatial index based on the new position of the dynamic object comprises:

updating the bounding volume surrounding the dynamic object based on the new position of the dynamic object;

updating the dynamic object spatial index based on a new position of the bounding volume surrounding the dynamic object; and

tracing the bounding volume surrounding the dynamic object through the static spatial index until at least one leaf node is reached by taking branches to nodes of the static spatial index intersected by the bounding volume which surrounds the dynamic object.

16. The system of claim 12, further comprising:

a second processing element configured to perform ray-tracing by issuing rays into the three-dimensional scene and tracing rays through the combined spatial index by taking branches to nodes defining bounding volumes within the three-dimensional scene to determine if the ray intersects static or dynamic objects within the three-dimensional scene.

17. The system of claim 16, wherein the first processing element and the second processing element are on the same chip.