ECS Linear Octree for storing voxel

Unity Engine
, ,
1

Is it possible to implement linear octree with NativeList of 8 int?
I can’t find the source code and tempted to write it myself but I don’t want to reinvent the wheel

I have naive idea that it should just store 8 int in the node. If the value is more than 0 then it is index to child node, and if it is negative then it is the 31 bits of value. Then if there is subdivision, I could add new node to the NativeList and store index, else store the value as zero or negative

The function of getting value is easy. But now I struggle to implement the voxel decomposition process. Are there efficient algorithm in ECS? For example, should I spawn parallel job to decompose the voxel? Or is there any sequential but more efficient algorithm?

Also if the voxel can be modified as a terrain system, is it better to store 9 ints (1 for parent reference) or use NativeHashMap instead of NativeList?

If there is any existing implementation like these please help me know about that

Thank you very much

p.s. another thing I wonder is what is the convention for encode/decode octree index?

Naively, I have been using xyz as bit code
0b000 for left|bottom|back
0b001 for left|bottom|front
0b010 for left|top|back
…
0b111 for right|top|front

Is this normal? Or should I use zyx or anything?

2

I recently worked on something similar, but not ECS but a burstable octree/quatree struct. Nodes have an index, size and voxel data, and use lookups to determine the child nodes and other information like index-> position. For me it was mainly about small node size. I use ushort and byte for index and size, and with the voxel i get 6 bytes per node. For 8 node child indexes there are already 32 bytes. However, this is relatively complicated, it took me almost a week for the lookups.

The index are like:

/*
-----------------------------------------
| 42 | 43 | 46 | 47 | 58 | 59 | 62 | 63 |
-----------------------------------------
| 40 | 41 | 44 | 45 | 56 | 57 | 60 | 61 |
-----------------------------------------
| 34 | 35 | 38 | 39 | 50 | 51 | 54 | 55 |
-----------------------------------------
| 32 | 33 | 36 | 37 | 48 | 49 | 52 | 53 |
-----------------------------------------
| 10 | 11 | 14 | 15 | 26 | 27 | 30 | 31 |
-----------------------------------------
| 8  | 9  | 12 | 13 | 24 | 25 | 28 | 29 |
-----------------------------------------
| 2  | 3  | 6  | 7  | 18 | 19 | 22 | 23 |
-----------------------------------------
| 0  | 1  | 4  | 5  | 16 | 17 | 20 | 21 |
-----------------------------------------
*/

Edit:
a lookup example for the children):
children(index: 0, depth: 1) = [16, 32, 48];
children(index: 0, depth: 2) = [4, 8, 12];
children(index: 0, depth: 3) = [1, 2, 3];
However, you have to rethink how an octree / quadtree works.