Generating efficient spatial indexes for predictably dynamic objects

• US 7,893,936 B2
• Filed: 01/12/2007
• Issued: 02/22/2011
• Est. Priority Date: 01/12/2007
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert Allen
• Primary Examiner(s): Hajnik, Daniel F
• Application Number:
  US11/622,613
• Publication Number:
  US 20080170071A1
• Time in Patent Office: 1,502 Days
• Field of Search: None
• US Class Current: 345/420
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

Embodiments of the invention provide methods and apparatus for modifying a spatial index in response to movements of a predictably dynamic object within a three-dimensional scene. According to one embodiment of the invention, in contrast to generating a new spatial index in response to movement of a predictably dynamic object, a portion of an existing spatial index may be modified in response to the movement of a predictably dynamic object. According to one embodiment of the invention, modification may include changing information defining the position of splitting planes along a splitting axis to correspond to the new position of the object within the three-dimensional scene. In contrast to generating a new spatial index, by modifying only a portion of an existing spatial index the amount of time required to perform ray tracing image processing may be reduced.

Claims

1. A method of representing objects located within a three-dimensionl scene in spatial indexes, the method comprising:

providing an object in a first position within the three-dimensional scene, wherein the object moves in a predictable manner;

generating, by operation of one or more computer processors, a spatial index having nodes defining bounded volumes which partition the three-dimensional scene, wherein at least one of the nodes of the spatial index defines bounding volumes containing the object in the first position, wherein the spatial index is selected from a k-dimentional tree (kd-tree), a binary space partitioning (BSP)tree, and an octree, wherein at least one node of the kd-tree defines a single splitting plane for splitting a bounding volume in the three-dimensional scene; and

in response to movement of the object from the first position to a second position, modifying the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the second position and such that the spatial index is not entirely rebuilt, comprising;

modifying, in the spatial index and based on the second position of the object, at least one of;

(i) the information which indicates an axis along which the splitting plane is drawn and (ii) the information which indicates the position of the splitting plane along the axis.

2. The method of claim 1, wherein the at least one of the nodes of the spatial index contains information which indicates the axis along which the splitting plane is drawn, and information which indicates the position of the splitting plane along the axis, wherein the splitting plane creates a bounding volume containing the object.

3. The method of claim 1, wherein the object moves along a predictable path including the first position and the second position.

4. The method of claim 1, further comprising:

moving the object from the second position back to the first position; and

modifying the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the first position.

5. The method of claim 1, wherein the at least one of the nodes of the spatial index further comprises at least one leaf node containing a pointer to information defining the object.

6. The method of claim 1, wherein the at least one of the nodes of the spatial index represents less than the entire spatial index.

18. The method of claim 1, further comprising:

moving the object from the second position back to the first position; and

modifying the at least one node of the kd-tree such that the bounding volumes defined by the at least one of the nodes of the kd-tree contain the object in the first position, comprising;

modifying, in the spatial index and based on the first position of the object, at least one of;

(i) the information which indicates the axis along which the splitting plane is drawn and (ii) the information which indicates the position of the splitting plane along axis.

19. The method of claim 1, wherein the at least one node of the kd-tree 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 kd-tree, and wherein the leaf node comprises a pointer to the object in the three-dimensional scene.

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

providing an object in a first position within the three-dimensional scene, wherein the object moves in a predictable manner;

generating a spatial index having nodes defining bounded volumes which partition the three-dimensional scene, wherein at least one of the nodes of the spatial index defines bounding volumes containing the object in the first position, wherein the spatial index is selected from a k-dimensional tree (kd-tree), a binary space partitioning (BSP) tree, and an octree, wherein at least one node of the kd-tree defines a single splitting plane for splitting a bounding volume in the three-dimensional scene; and

in response to movement of the object from the first position to a second position, modifying the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the second position and such that the spatial index is not entirely rebuilt, comprising;

modifying, in the spatial index and based on the second position of the object, at least one of;

(i) the information which indicates an axis along which the splitting plane is drawn and (ii) the information which indicates the position of the Splitting plane along the axis.

8. The non-transitory computer readable medium of claim 7, wherein the at least one of the nodes of the spatial index contains information which indicates the axis along which the splitting plane is drawn, and information which indicates the position of the splitting plane along the axis, wherein the splitting plane creates a bounding volume containing the object.

9. The non-transitory computer readable medium of claim 7, wherein the object repetitively moves along a predictable path incitiding at least the first position and the second position.

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

moving the object from the second position back to the first position; and

modifying the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the first position.

11. The non-transitory computer readable medium or claim 7, wherein the at least one of the nodes of the spatial index represents less than the entire spatial index.

12. An image processing system, comprising:

spatial index logic configured to generate a spatial index having nodes defining bounded volumes which partition a three-dimensional scene, wherein at least one of the nodes of the spatial index defines bounding volumes containing an object in a first position within the three-dimensional scene, wherein the object moves in a predictable manner, wherein the spatial index is selected from a k-dimensional tree (kd-tree), a binary space partitioning (BSP) tree, and an octree, wherein at least one node of the kd-tree defines a single splitting plane for splitting a bounding volume in the three-dimensional scene; and

a processing element configured to move the object from the first position to a second position; and

wherein the spatial index logic is further configured to modify the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the second position and such that the spatial index is not entirely rebuilt, wherein modifying the at least one of the nodes of the spatial index comprises modifying, in the spatial index and based on the second position of the object, at least one of;

(i) the information which indicates an axis along which the splitting plane is drawn and (ii) the information which indicates the position of the splitting plane along the axis.

13. The image processing system of claim 12, wherein the at least one of the nodes of the spatial index contains information which indicates the axis along which the splitting plane is drawn, and information which indicates the position of the splitting plane along the axis, wherein the splitting plane creates a bounding volume containing the object.

14. The image processing system of claim 12, wherein the object moves along a predictable path including the first position and the second position.

15. The image processing system of claim 12, wherein the physics engine is further configured to move the object from the second position back to the first position;

and

wherein the spatial index logic is further configured to modify the at least one of the nodes of the spatial index such that the bounding volumes defined by the at least one of the nodes of the spatial index contain the object in the first position.

16. The image processing system of claim 12, wherein the at least one of the nodes of the spatial index represents less than the entire spatial index.

17. The image processing system of claim 12, wherein the at least one of the nodes of the spatial index further comprises at least one leaf node containing a pointer to information defining the object.