(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:
ToArrayfunctions don’t make a lot of sense, how should a sparse array get converted to a normal array? You can use the pulblic field
Datato get access to the underlying arrays if you’d like to copy to and from
- Indexing into the the array can add data. For example
array=2will add an index
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
AddValueto 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:
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.
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:
- Unity’s code examples here: https://docs.unity3d.com/ScriptReference/Unity.Collections.LowLevel.Unsafe.NativeContainerAttribute.html
- Unity’s Collections Package which contains code for additional native containers.
- Jackson Dunstan’s blog is a invaluable. I’ve used his NativeCollections for extra tips and ideas.
- If you’d like to make your native container compatible with the job system, then use this guide https://docs.unity3d.com/Packagesfirstname.lastname@example.org/manual/custom_job_types.html?_ga=2.122162947.960630263.1577096340-1341159195.1576389166#available-attributes and this example code https://github.com/Unity-Technologies/EntityComponentSystemSamples/tree/a6b5ca01e96f4dd859fdb921bda2943323386038/Samples/Assets/NativeCounterDemo.
The code for the NativeSparseArray and Native Collection Extensions are available in the Github repo.