Patent ID: 7893936
Filing Date: 2011-02-22
Classification: G06T

Abstract:
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: