Spatial Processes and Spatial Hashing

Spatial Processes

There are four broad categories of spatial processes

  1. Purely Global
  2. Global <-> Local
  3. Local <-> Local
  4. Purely Local

and two general categories of spatial primitives

  1. Field
  2. Particle

Of course, the spatial primitives can be organized into composite structures such as meshes where particles are linked together in a network.

Fields represent global information over a defined N-dimensional range of space while particles represent local information located at an infinitesimal point in space.  Information moves from a local to global context when particles interact with a field.  For example, stigmergic behavior can be generated by having particles leave traces in a field that represents pheromone concentrations over an environment. In stigmergic systems, information flows in a positive feedback loop from local behavior to global concentrations, which in turn affect local behavior.

Spatial Information Flows

The simplest kinds of information flows are those that are internal to an object be it global as in the evolution of a field according to its dynamical equations or local as in the movement of a particle according to kinematics.  In both cases, the state of the spatial system is affected but not in a way that adds any new information or structure.  Existing information is simply transformed and displaced.

The next level of complexity in terms of spatially directed pattern formation occurs when information transfers between local and global contexts.  In such instances, particles are essentially reading from and writing into fields and altering their internal state accordingly.  When information is written into a field by a particle, it loses its specificity (that of being attached to a particular entity) and becomes part of an intensive processes as opposed to an extensive one.  While limiting in the sense that once the information is in the field the actions that contributed to the state of the field can no longer be distinguished, it does open up an efficient communication channel between many local objects since each can read the aggregate state of the local entities as it is mediated by the field.  Communication between individual local objects is not possible through a field however because the number of channels required is prohibitive.  Instead, this has to be done through local to local flows.

Local to local interactions provide the most fine grained spatial information flows but are also the most computationally intensive.  If there are N objects in a space, there are (N-1)^2 channels of interaction.  For local to global flows there are only N channels of interaction.  While incredibly useful in terms of composing complex spatial patterns, the computational cost of local to local interactions can make them impractical.

The classic example of local to local interactions is the N-body problem, which occurs in gravitational and electric field simulations among others.  Both of these problems deal with particles generating fields that affect every other particle.  To simplify the computational complexity of the problem, the local fields of each particle are accumulated into a hierarchy of fields that can then be precisely applied to each particle such that the total runtime is N log(N).  This technique is called the Fast Multipole Method.

While having every particle able to communicate efficiently with every other particle  might be desirable in the ideal case, practically speaking it’s often good enough to have particles communicate with each other within a particular range or with the nearest N particles.  Such a system can be implemented by binning particles according to their location and then operating over the binned particles to realize local to local communication channels.  The fastest algorithm I’ve found for spatial binning and neighborhood calculation is Query Sphere Indexing.

Spatial Hashing

Query sphere indexing is a form of spatial whereby a spatial location is given an integer value that can be used as a key to look up the position quickly from a table.  In the query sphere technique, the space is divided into a finite number of discrete cells and each cell is given an integer hash value based on its coordinate.  Any particle falling within the cell is binned to it and associated with the cell’s integer hash value.

The speed of the query sphere technique comes from precomputing as much information as possible about neighborhoods.  When the data structure is created, a table of relative coordinates in terms of hash indices is calculated for all the possible distances and ordered according to nearest to furthest offset.  For example, if you want to know how many objects are within radius 1 of a point in space, the offset lookup table will provide a list of cell offsets that can be added to the query location efficiently and all of the cells within radius 1 retrieved for processing.

The calculations in the Query Sphere paper are incredibly efficient since they’re all operating on integers using addition and bit manipulation.  In a version of the algorithm I’ve implemented for example, I can hash 302,500 (550×550) points at 33fps and query thousands of neighborhoods for nearest neighbors.  As a result, local to local communication is incredibly efficient and used judiciously can add a lot more detail and complex pattern formation to the evolution of a spatial system.  For instance, once local to local communication becomes efficient, it becomes to describe the formation of aggregate structures such as meshes in a straightforward manner, which can in turn introduce new behaviors and trajectories into the system.

The cubes in the image above are the bins holding particles.  The pink dots are query locations with lines connecting the nearest 16 neighbors within a particular radius.

This entry was posted in Software Engineering, Space and Geometry and tagged , , , . Bookmark the permalink.

One Response to Spatial Processes and Spatial Hashing

  1. Pingback: JULIAN

Leave a Reply