Multi-dimensional acceleration structure

A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, causes a computing device to implement an acceleration structure, by performing the steps of:

• determining a position of an entity in a three-dimensional (3D) scene, wherein the position of the entity is determined relative to a location of a camera configured to capture an image of the 3D scene;
• mapping the position of the entity to a 3D voxel grid coordinate in the acceleration structure, wherein the acceleration structure comprises a central grid structure and six additional grid structures organized around the central grid structure in 3D space, wherein each of the central grid structure and the six additional grid structures comprises a set of voxels;
• determining a first offset value corresponding to the 3D voxel grid coordinate, wherein the first offset value corresponds to either the central grid structure or one of the six additional grid structures;
• and
• determining a second offset value corresponding to the 3D voxel grid coordinate, wherein the second offset value corresponds to a particular voxel within either the central grid structure or one of the six additional grid structures corresponding to the first offset value, wherein data corresponding to the entity is stored in memory a location based on the first offset value and the second offset value.

A device for implementing an acceleration structure, the device comprising:

• a memory storing instructions;
• and
• one or more processors configured to the execute the instructions to cause the device to:
• determine a position of an entity in a three-dimensional (3D) scene, wherein the position of the entity is determined relative to a location of a camera configured to capture an image of the 3D scene;
• map the position of the entity to a 3D voxel grid coordinate in the acceleration structure, wherein the acceleration structure comprises a central grid structure and six additional grid structures organized around the central grid structure in 3D space, wherein each of the central grid structure and the six additional grid structures comprises a set of voxels;
• determine a first offset value corresponding to the 3D voxel grid coordinate, wherein the first offset value corresponds to either the central grid structure or one of the six additional grid structures;
• and
• determine a second offset value corresponding to the 3D voxel grid coordinate, wherein the second offset value corresponds to a particular voxel within either the central grid structure or one of the six additional grid structures corresponding to the first offset value, wherein data corresponding to the entity is stored in memory a location based on the first offset value and the second offset value.