Spatial Process Mapping Using Octrees

by Aether Engine, Hadean Platform

Spatial indexing is a great way to speed up queries of spatial data. The most common queries usually take the form of “index to this point”, or “give me all the points in an area”. These are very general queries that apply in many situations.

By providing very fast distributed spatial indexing, we can solve a broad set of problems strongly linked to gaming.

The state of the art in most spatial indexing databases is some variant of an R-tree (R+ tree or R* tree). These can give desirable performance characteristics in some cases, for batch insert and read heavy spatial queries. But for loads that don’t follow a pattern like “insert once then query many times” but are more random or dynamic they can perform poorly. Another point against R-trees (and non-fixed encoding trees in general) is that exactly because the encoding isn’t fixed, a distributed implementation would require much heavier cooperation and management between all involved workers.

Trees with non-fixed shape cells (under some constraints or pathological cases) can generate high aspect ratio cells. This causes problems for the simulation, whether it is agent based, or cell based, variable size and shape cells are harder to work with. High aspect cells are also worth avoiding because in a lot of simulations computation is proportional to internal volume and communication is proportional to surface area. If we want to maximise useful computation and minimise communication, it’s worth optimising for low aspect ratio cells.

Our spatial index of choice is an Octree (/Quadtree in 2D). The primary reason is that it is backed by an immutable, fractal space filling curve – the Morton Curve (or Z-Order Curve). The immutability provides an important benefit for distributed systems, that there will never be any disagreement about the mapping of positions to codes. The exact nature of the Morton Curve as an interleaving of bits also provides a benefit, that we can always encode and decode very simply and in fewer CPU cycles.

Although a Hilbert curve fits the immutable, fractal space filling curve definition and even provides slightly better locality properties (close points in space are close in the encoding). It is harder (or not possible) to write the same efficient functionality as for the Morton curve. For example, it is unknown whether it is possible to efficiently find the next Hilbert code inside a search area.

Compared to an R-tree, the operations insert, delete, merge and split are simple, uniform and very fast. One key benefit of using an octree and many other trees like KD-Trees or R-Trees is that the split doesn’t evaluate a complex O(N) heuristic to decide how to split (N in the number of entities or things being simulated). The resulting cells (shapes and sizes) are simpler and always perfectly cover the same combined area. This helps create a simpler abstraction for the Aether user, they do not need to deal with high aspect ratio shapes or complex polygons, just power-of-two-sized squares (or cubes in 3D).

The exact implementation of the tree is less important, we can either use an explicit node-index structure, an implicit leaf-node-only structure or even a Morton sorted list of areas. All of these can be very efficient, with few allocations and good cache locality for traversal and searching. The explicit tree structure can be easily accelerated by maintaining a stack for traversals which contains the potentially valid ancestor nodes for every depth in the tree up to the root. Using a find_common_ancestor function, we can then immediately jump to the common ancestor node and traverse down from there instead of from the root. In the majority of cases most of the stack is valid between traversals and indexes, this dramatically reduces the memory accesses.

Indexing positions can be performed quickly because we can encode the position into a Morton code, then either traverse the tree (from a common ancestor) or binary search the Morton sorted list. Both of these will be O(log(N)) in the size of the tree. In practice, with good locality of queries, this can be done in a very small number of iterations.

Range query or area search can be implemented similarly. An arbitrary area (usually an Axis Aligned Bounding Box), is broken down efficiently into Morton-aligned cells (thanks to it being fast to get the next point on the curve inside or outside an AABB). The Morton aligned cells can then be indexed as quickly as the point. This depends heavily on how well aligned and how large the area is, but is O(log(N)) in the area of the search region.

Using this distributed spatial index, we can build up an interface which provides great performance for common simulations at a huge scale. A Hadean process is allocated from a pool and assigned to a Morton aligned cell in the tree. This worker performs some simulation work. It communicates directly to its neighbours by having a local tree-like cache of the global space-process mapping, updated and invalidated/refreshed only when necessary.

This interface is broad enough to support many simulation types, but we can do better. For specific simulations that are agent-like in nature, we can provide tools such as graceful handover of agents near boundaries. This means an agent in the simulation will always be able to interact immediately with other agents within a defined bounding box.