Patent ID: 8004518
Filing Date: 2011-08-23
Classification: G06T

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