US 7,893,936 B2Granted

Generating efficient spatial indexes for predictably dynamic objects

AssigneeInternational Business Machines Corporation

InventorRobert Allen Shearer

Life of this patent

Estimating the term…

Loading patent…

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.

Claims19

Dependent claims

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.

3 more elements

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.

3 more elements

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.

2 more elements

Dependencies are inferred from the claim text.