Spatial 3D tree

A generic collection that offers an efficient point lookup in 3D space using a custom octree implementation.

The Spatial3DTree implements a self-regulating Octree.
When items gets added, it grows the octree if needed while keeping the existing data intact.
On the other hand, when items are removed, the octree shrinks as much as possible.
As many objects move around in Unity, moving objects in the Spatial3DTree is also supported.

To find items in the Spatial3DTree, one uses specialized enumerators.
These enumerators differ in the shape they are using for inclusion/exclusion testing.

Enumerators

• Spatial3DTreeEnumerator
  Enumerates over a Spatial3DTree and returns all items.
• SphereCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are within a sphere.
• AabbCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are within an axis aligned bounding box
• ShapeCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are within an user defined shape
• InverseSphereCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are outside a sphere
• InverseAabbCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are outside an axis aligned bounding box
• InverseShapeCastEnumerator
  Enumerates over a Spatial3DTree and returns all items that are outside an user defined shape

Custom filter
In order to customize the filter, you can overwrite a few base classes.
Depending on your use case, different implementations make sense.

• IShape
  Implement this to define the shape.
  Needs to be used with a ShapeCastEnumerator or InverseShapeCastEnumerator to get the items.
• Spatial3DTreeInclusionEnumeratorBase
  Base class for custom Spatial3DTree enumerators that look for items inside a shape.
• Spatial3DTreeExclusionEnumeratorBase
  Base class for custom Spatial3DTree enumerators that look for items outside a shape

Example images

Highlighting all points inside a sphere cast.

Visualization of the spatial 3d tree structure with evenly distributed points.

Visualization of the spatial 3d tree structure with chunked together points.