Electronic Arts Inc.
MULTI-DIMENSIONAL ACCELERATION STRUCTURE

Abstract:

A system and method for implementing an acceleration structure are disclosed. The method includes: determining a position of an entity; mapping the position to a 3D (three-dimensional) voxel grid coordinate in the acceleration structure, which comprises a central grid structure and six additional grid structures each comprising a set of voxels; determining a first offset value corresponding to the 3D voxel grid coordinate that 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 that 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.