A Hierarchal [[Lattice|Grid]] is a form of [[Data Structure]] (typically [[Spatial Partitioning]]) that is a hierarchical structure of uniform grids. These grids must be uniform - but each grid may have difference sizes dependent on their level in the hierarchy. When used for [[Spatial Partitioning]], object insertion is put in a level corresponding to its size. Larger objects will be higher level while smaller objects are lower. Traversal & Operations through a hierarchal grid is typically more efficient than other implementations. ## Construction For some grid surrounding objects $O$ with a [[Bounding Volume]] of width $\vec W$. The hierarchal grid is composed of many grids ${G_{0},G_{1},G_{2},\dots,G_{n}}$ with each level's cell size computed as the following: $\huge \begin{align} \op{cellSize}(G_{k}) &= 2^{-k} \vec W \\ |G_{k}| &= 2^{k^{2}} \end{align} $ >[!note] Note that it would be $k^3$ in $\R^3$ Where $N$ is the number of dimensions of the space. Inserting an object uses its [[Bounding Volume]] to determine its size for which level to use. $\huge \begin{align} 2r = \frac{w}{2^{k}} &\implies 2^{k} = \frac{w}{2r} \\ w \cong \frac{u+v}{2} &\implies k = \floor{\log\pa{\frac{w}{2r}}} \end{align}$ ## Insertion Insertion is most optimal when doing it with all cells an object $O$ touches, but only in a single level. ## Update / Removal Given an object, find its level $k$, search GridBox array, detach it. ## Object Casting Objective: testing if a given object overlaps with others, returns least of all overlapping objects. Process: 1. Start from top level, traverse hierarchy 2. Check overlapping objects 3. Traverse only cells at the next level overlapping with the given object ## Ray Casting Almost the same as [[Uniform Grids]], 1. Start at the top level $k=0$ 2. Check all intersecting cells for intersection 3. For intersecting cells, traverse downwards (*all children*) 4. Be aware of duplicate hits or "behind hits".