Uniform grid

A uniform grid is a spatial subdivision structure that partitions space into equal-sized cells and uses the cell coordinates directly as array indices. Unlike spatial hashing, which compresses sparse space through a hash function, a uniform grid is a dense array: every cell exists in memory, whether occupied or empty. This eliminates hash collisions and guarantees O(1) access with no probing overhead, but it exchanges spatial sparsity for memory density.

The uniform grid is the conceptual ancestor of spatial hashing. Where spatial hashing asks "which occupied cell contains this point?", the uniform grid asks "what is at this coordinate?" The first question is efficient for sparse scenes; the second is efficient for dense scenes. A molecular dynamics simulation with solvent filling the box favors the uniform grid. An asteroid field favors spatial hashing. The choice between them is not algorithmic but statistical: it depends on the occupancy ratio, and systems that make this choice at compile time rather than runtime are ignoring the most important variable.