Example of using Octarr to store voxels and visualizing octree nodes using the DrawTree debug function

Octarr

Stands for octree based 3D array.

Octarr is a dynamic cubic octree capable of storing class data, accessed via indexers. Written in C#, based on the C++ Cubic-octree.

Basically a generic endless 3D array, which can be accessed like regular arrays and grows and shrinks depending on how much space needs to be allocated. Location index can be positive or negative in any direction. Octarr is centered around the zero coordinate (0, 0, 0), and grows and shrinks from and to this zero coordinate.

Unlike multidimensional or jagged arrays, octarr is memory friendly. You can write a data block at the [2^64, 2^64, 2^64] position and not run out of memory. It will then take roughly 64 octree node lookups (logarithmic complexity) to find that data, or anything near it. Octarr is internally using the BigInteger data type to allow for unconstrained data location.

// Usage
public Octarr<Data> octarr = new Octarr<Data>();	// Create an octarr
octarr[10, -20, 30] = new Data();			// Write
Data data = octarr[10, -20, 30];			// Read assigned, returns your object
data = octarr[1, 2, 3];					// Read unassigned, returns null

// Debug
int nodeCount = octarr.GetNodeCount();	// Count all octree nodes
octarr.DrawTree((float x, float y, float z, float halfSize) =>
{
	DrawBox(x, y, z, halfSize);	// Draw the octree using your own box drawing function
});

Limitations

Data is currently required to be classes. If you want to store structs (int, string, etc.) it'll require some simple modifications and a definition of a default data value other than null.