GRID-BASED LOOSE OCTREE FOR SPATIAL PARTITIONING

A technique for spatial partitioning and a data structure for storing references to objects in a scene. A grid-based loose octree (GLOtree) is a data structure that combines advantages of a uniform grid-based subdivision method and an octree-based subdivision method to provide a general purpose spatial partitioning method that works well with both static and dynamic scenes. In a GLOtree, objects are located at lower levels of the tree than in the prior art octree. This allows traversals to search for specific objects to be accomplished more quickly when a starting search level of the GLOtree is predicted. The GLOtree uses loose octree nodes that adapt the sizes of octants to the scene.