Grid-based loose octree for spatial partitioning

An article comprising:

• a storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for spatial partitioning of a scene represented by a scene graph, the instructions for collecting statistics of objects in the scene graph, determining a looseness value, building a loose octree using objects from the scene graph and the looseness value, determining a minimum depth value based on the collected statistics, and subdividing the scene to the minimum depth value using a grid to form a grid-based loose octree.

An article comprising:

• a storage medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions provide for traversing a data structure used for spatial partitioning of a scene represented by a scene graph, the instructions for determining a cell of a grid of a grid-based loose octree containing a selected object of the scene, determining a level of the grid-based loose octree having a node referencing the selected object, traversing at least one child node of the node referenced by the cell until the level is reached, and checking at least one child node of the node to determine if the selected object fits inside of an octant of the scene represented by the child node.

A data structure comprising:

• a grid-based loose octree having a root node and a plurality of child nodes, each node representing an octant of a scene, wherein a size of an octant is adjusted by a looseness value and at least one node of the grid-based loose octree is referenced by a cell of a grid subdividing the scene.