(Part of a series where I think out loud about an out-of-core point cloud renderer I’m working on.)

A sparse array uss the classic programming trick of adding another layer of indirection. Not by using a pointer, but by adding an abstraction over a traditional array.

I’m in the process of building an Octree for use in a Point Cloud Renderer. The Octree will store nodes layer by layer. This means that some layers will have mostly empty space. Rather then storing the nodes directly, this sparse array has two arrays, one to store the data and the other to store the indices of the data. The data is always sorted, so a binary search can be used to find data or insertion points for adding data.

A sparse array is usually slower for large data sets, and a hash map is preferred. But for the point cloud renderer, most of the time will be bulk processing the nodes for culling, etc. So having all the nodes in contiguous memory is just what I want.

I’d like the SparseArray API to be a close a possible to the NativeArray. But with two caveats:

  • The CopyTo, CopyFrom and ToArray functions don’t make a lot of sense, how should a sparse array get converted to a normal array? You can use the pulblic field Indices and Data to get access to the underlying arrays if you’d like to copy to and from NativeArrays.
  • Indexing into the the array can add data. For example array[1]=2 will add an index 1 with data 2. The array is fixed size, so simple index access can fail if the array is full. It will fail silently fails is collection checks are off. Prefer to IsFull, ContainsIndex and AddValue to explicitly add items and check for errors.

Native Collection Extensions

The Native Collection API is fairly sparse. So I’ve added the following extension methods:

  • Swap
  • Insert
  • RemoveAt
  • BinarySearch

Strangely there is no common interface for the Native Collections, so the common pattern is to make a private function that implements the algorithm using raw pointers. This gets called by type specific wrappers. This means that the assembly must be marked unsafe, and needs a decent amount of unit tests and precondition tests. I’ve followed the example of the native collections and used ENABLE_UNITY_COLLECTIONS_CHECKS to enable the precondition checks.

Job Safety

NativeSparseArray does not do atomic read or writes. It can still safely be used within a job as long as the each job access individual array indices. The underlying indices and data arrays are available as public properties and can be used within Jobs.

Native Container Resources

If you’d lke to write your own native containers then the best resources are:

Code

The code for the NativeSparseArray and Native Collection Extensions are available in the Github repo.