Multiple spacial indexes for dynamic scene management in graphics rendering

• US 7,940,265 B2
• Filed: 09/27/2006
• Issued: 05/10/2011
• Est. Priority Date: 09/27/2006
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Brown, Jeffrey D., Hoover, Russell D., Kuesel, Jamie R., Mejdrich, Eric O., Shearer, Robert A.
• Primary Examiner(s): Hajnik, Daniel F
• Application Number:
  US11/535,568
• Publication Number:
  US 20080074416A1
• Time in Patent Office: 1,686 Days
• Field of Search: None
• US Class Current: 345/426
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

According to embodiments of the invention, separate spatial indexes may be created which correspond to dynamic objects in a three dimensional scene and static objects in the three dimensional scene. By creating separate spatial indexes for static and dynamic objects, only the dynamic spatial index may need to be rebuilt in response to movement or changes in shape of objects in the three dimensional scene. Furthermore, the static and dynamic spatial indexes may be stored in separate portions of an image processing system'"'"'s memory cache. By storing the static spatial index and the dynamic spatial index in separate portions of the memory cache, the dynamic portion of the memory cache may be updated without affecting the static portion of the spatial index in the memory cache.

Claims

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

configuring one or more computer processors to perform an operation, comprising;

generating a static spatial index based on at least one static object in the three dimensional scene, the static spatial index having nodes defining bounded volumes of the three dimensional scene;

generating a dynamic spatial index separate from the static spatial index based on at least one dynamic object in the three dimensional scene, the dynamic spatial index having nodes defining bounded volumes of the three dimensional scene, wherein the spatial indexes partition the three dimensional scene into smaller volumes through a use of splitting planes, each of which is parallel to a selected axis;

issuing a ray into the three dimensional scene;

traversing the dynamic spatial index by taking branches to nodes based on the ray intersecting bounding volumes corresponding to nodes in the dynamic spatial index until a dynamic spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the dynamic spatial index leaf node;

traversing the static spatial index based on the ray intersecting bounding volumes corresponding to nodes in static spatial index until a static spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the static spatial index leaf node; and

if a primitive was struck in both the dynamic spatial index leaf node and the static spatial index leaf node, determining a primitive that was intersected first.

2. The method of claim 1, further comprising:

storing the static spatial index in a first portion of a memory cache; and

storing the dynamic spatial index in a second portion of the memory cache.

3. The method of claim 2, further comprising periodically invalidating the second portion of the memory cache after a predetermined amount of time has passed.

4. The method of claim 3, wherein the predetermined amount of time corresponds to the amount of time necessary to render a two dimensional image from the three dimensional scene.

5. The method of claim 1, further comprising periodically rebuilding the static spatial index when at least one static object in the three dimensional scene becomes at least one dynamic object in the three dimensional scene or when at least one dynamic object in the three dimensional scene becomes at least one static object in the three dimensional scene.

6. The method of claim 1, wherein determining a primitive that was intersected first comprises:

calculating a first distance from a view point to a primitive intersected in the dynamic spatial index;

calculating a second distance from the view point to a primitive intersected in the static spatial index;

and determining which primitive was intersected first by comparing the first distance to the second distance.

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

generating a static spatial index based on at least one static object in a three dimensional scene, the static spatial index having nodes defining bounded volumes of the three dimensional scene;

generating a dynamic spatial index separate from the static spatial index based on at least one dynamic object in the three dimensional scene, the dynamic spatial index having nodes defining bounded volumes of the three dimensional scene, wherein the spatial indexes partition the three dimensional scene into smaller volumes through a use of splitting planes, each of which is parallel to a selected axis;

issuing a ray into the three dimensional scene;

traversing the dynamic spatial index by taking branches to nodes based on the ray intersecting bounding volumes corresponding to nodes in the dynamic spatial index until a dynamic spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the dynamic spatial index leaf node;

traversing the static spatial index based on the ray intersecting bounding volumes corresponding to nodes in static spatial index until a static spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the static spatial index leaf node; and

if a primitive was struck in both the dynamic spatial index leaf node and the static spatial index leaf node, determining a primitive that was intersected first.

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

storing the static spatial index in a first portion of a memory cache; and

storing the dynamic spatial index in a second portion of the memory cache.

9. The non-transitory computer readable storage medium of claim 8, wherein the operations further comprise periodically invalidating the second portion of the memory cache after a predetermined amount of time has passed.

10. The non-transitory computer readable storage medium of claim 9, wherein the predetermined amount of time corresponds to the amount of time necessary to render a two dimensional image from the three dimensional scene.

11. The non-transitory computer readable storage medium of claim 7, wherein determining a primitive that was intersected first comprises:

calculating a first distance from a view point to a primitive intersected in the dynamic spatial index;

calculating a second distance from the view point to a primitive intersected in the static spatial index;

and determining which primitive was intersected first by comparing the first distance to the second distance.

12. An image processing system, comprising:

a memory comprising;

a static spatial index based on at least one static object in a three dimensional scene, the static spatial index having nodes defining bounded volumes of the three dimensional scene; and

a dynamic spatial index separate from the static spatial index based on at least one dynamic object in the three dimensional scene, the dynamic spatial index having nodes defining bounded volumes of the three dimensional scene; and

a first processing element configured to;

issue a ray into the three dimensional scene;

traverse the dynamic spatial index by taking branches to nodes based on the ray intersecting bounding volumes corresponding to nodes in the dynamic spatial index until a dynamic spatial index leaf node is reached, and determine if the ray strikes a primitive contained within a bounding volume corresponding to the dynamic spatial index leaf node;

traverse the static spatial index based on the ray intersecting bounding volumes corresponding to nodes in static spatial index until a static spatial index leaf node is reached, and determine if the ray strikes a primitive contained within a bounding volume corresponding to the static spatial index leaf node; and

if a primitive was struck in both the dynamic spatial index leaf node and the static spatial index leaf node, determine a primitive that was intersected first.

13. The image processing system of claim 12, wherein the first processing element further comprises a memory cache, wherein the static spatial index is stored in a first portion of the memory cache and the dynamic spatial index is stored in a second portion of the memory cache, and wherein the first processing element is further configured to periodically invalidate the second portion of the memory cache after a predetermined amount of time, wherein the predefined amount of time corresponds to the amount of time necessary to render a frame from the three dimensional image.

14. The image processing system of claim 12, wherein the image processing system is configured to periodically rebuild the static spatial index when at least one static object in the three dimensional scene becomes at least one dynamic object in the three dimensional scene or when at least one dynamic object in the three dimensional scene becomes at least one static object in the three dimensional scene.

15. The image processing system of claim 12, wherein determining a primitive that was intersected first comprises:

calculating a first distance from a view point to a primitive intersected in the dynamic spatial index;

calculating a second distance from the view point to a primitive intersected in the static spatial index;

and determining which primitive was intersected first by comparing the first distance to the second distance.

16. A method of representing objects located within a three dimensional scene in spatial indexes, the method comprising:

configuring one or more computer processors to perform an operation, comprising;

generating a static spatial index based on at least one static object in the three dimensional scene, the static spatial index having nodes defining bounded volumes of the three dimensional scene;

generating a dynamic spatial index separate from the static spatial index based on at least one dynamic object in the three dimensional scene, the dynamic spatial index having nodes defining bounded volumes of the three dimensional scene;

issuing a ray into the three dimensional scene;

traversing the dynamic spatial index by taking branches to nodes based on the ray intersecting bounding volumes corresponding to nodes in the dynamic spatial index until a dynamic spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the dynamic spatial index leaf node;

traversing the static spatial index based on the ray intersecting bounding volumes corresponding to nodes in static spatial index until a static spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the static spatial index leaf node; and

if a primitive was struck in both the dynamic spatial index leaf node and the static spatial index leaf node, determining a primitive that was intersected first.

17. The method of claim 16, wherein determining a primitive that was intersected first comprises:

calculating a first distance from a view point to a primitive intersected in the dynamic spatial index;

calculating a second distance from the view point to a primitive intersected in the static spatial index;

and determining which primitive was intersected first by comparing the first distance to the second distance.

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

generating a static spatial index based on at least one static object in a three dimensional scene, the static spatial index having nodes defining bounded volumes of the three dimensional scene;

generating a dynamic spatial index separate from the static spatial index based on at least one dynamic object in the three dimensional scene, the dynamic spatial index having nodes defining bounded volumes of the three dimensional scene;

issuing a ray into the three dimensional scene;

traversing the dynamic spatial index by taking branches to nodes based on the ray intersecting bounding volumes corresponding to nodes in the dynamic spatial index until a dynamic spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the dynamic spatial index leaf node;

traversing the static spatial index based on the ray intersecting bounding volumes corresponding to nodes in static spatial index until a static spatial index leaf node is reached, and determining if the ray strikes a primitive contained within a bounding volume corresponding to the static spatial index leaf node; and

if a primitive was struck in both the dynamic spatial index leaf node and the static spatial index leaf node, determining a primitive that was intersected first.

19. The non-transitory computer readable storage medium of claim 18, wherein determining a primitive that was intersected first comprises:

calculating a first distance from a view point to a primitive intersected in the dynamic spatial index;

calculating a second distance from the view point to a primitive intersected in the static spatial index;

and determining which primitive was intersected first by comparing the first distance to the second distance.