US 8,004,518 B2 · Combined spatial index for static and dynamic objects within a three-dimensional scene

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.

Claims20

Dependent claims

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.

6 more elements

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.

5 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims20