Generating Efficient Spatial Indexes for Predictably Dynamic Objects

• US 20080170071A1
• Filed: 01/12/2007
• Published: 07/17/2008
• 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
• Granted Patent: US 7,893,936 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• 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-dimensional scene in spatial indexes, the method comprising:

providing an object in a first position within the three-dimensional scene;

generating a spatial index having nodes defining bounded volumes which partition the three-dimensional scene, wherein a first portion of the spatial index defines bounding volumes containing the object; and

in response to movement of the object from the first position to a second position, modifying the first portion of the spatial index based on the second position of the object.

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

3. The method of claim 2, wherein modifying the spatial index based on the second position of the object comprises:

modifying the information which indicates the position of the splitting plane along the splitting plane axis based on the second position of the object.

4. The method of claim 1, wherein the object is a predictably dynamic object that moves along a predictable path including the first position and the second position.

5. The method of claim 1, further comprising:

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

modifying the portion of the spatial index based on the first position of the object.

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

7. The method of claim 1, wherein the first portion of the spatial index represents less than the entire spatial index.

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

providing an object in a first position within the three-dimensional scene;

generating a spatial index having nodes defining bounded volumes which partition the three-dimensional scene, wherein a first portion of the spatial index defines bounding volumes containing the object; and

in response to movement of the object from the first position to a second position, modifying the first portion of the spatial index based on the second position of the object.

9. The computer readable medium of claim 8, wherein the first portion of the spatial index comprises at least one internal node containing information which indicates an axis along which a splitting plane is drawn, and information which indicates a position of the splitting plane along the axis, wherein the splitting plane creates a bounding volume containing the object.

10. The computer readable medium of claim 9, wherein modifying the spatial index based on the second position of the object comprises:

modifying the information which indicates the position of the splitting plane along the splitting plane axis based on the second position of the object.

11. The computer readable medium of claim 8, wherein the object is a predictably dynamic object that repetitively moves along a predictable path including at least the first position and the second position.

12. The computer readable medium of claim 8, wherein the operations further comprise:

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

modifying the portion of the spatial index based on the first position of the object.

13. The computer readable medium of claim 8, wherein the first portion of the spatial index represents less than the entire spatial index.

14. 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 a first portion of the spatial index defines bounding volumes containing an object within the three-dimensional scene; and

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

wherein the spatial index logic is further configured to modify the first portion of the spatial index based on the second position of the object.

15. The image processing system of claim 14, wherein the first portion of the spatial index comprises at least one internal node containing information which indicates an axis along which a splitting plane is drawn, and information which indicates a position of the splitting plane along the axis, wherein the splitting plane creates a bounding volume containing the object.

16. The image processing system of claim 15, wherein modifying the spatial index based on the second position of the object comprises:

modifying the information which indicates the position of the splitting plane along the splitting plane axis based on the second position of the object.

17. The image processing system of claim 14, wherein the object is a predictably dynamic object that moves along a predictable path including the first position and the second position.

18. The image processing system of claim 14, 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 portion of the spatial index based on the first position of the object.

19. The image processing system of claim 14, wherein the first portion of the spatial index represents less than the entire spatial index.

20. The image processing system of claim 14, wherein the first portion of the spatial index further comprises at least one leaf node containing a pointer to information defining the object.