I was wondering what is the best way to store this sparse octree in memory, without taking too much memory or being slow when inserting or removing nodes or being terribly cache unfriendly.
My current node representation is:
class Node
{
ChildArrayStartIndex
ChildArrayMask
}
Where the first variable tells where to find the array of 1-8 children (0 if it doesnt exist) and a mask to tell which ones exist (i took this off some random gpu octree rendering article thing)
Initially im going to store them in a vector of nodes, and when adding a new child to the array check if theres free space after it and if not (or the array doesnt exist) just put it at the end of the vector. (if i keep this method i will add something that keeps track of free spaces in the middle of the vector and moves the blocks of nodes around to remove small spaces)
I thought that would be cache unfriendly and potentially slow when adding nodes, so for the actual octree i was going to have the nodes stored in a bucket with each bucket storing some amount of nodes, and the buckets would be stored in an octree like above, so that nodes close to each other in the tree are in same buckets. (Also thought of instead making buckets only hold nodes in a single level of the octree, which might work better)
Does that sound ok assuming you understood me at all?
Any articles about this or other methods of storage you know about?
My octree stuff is as follows btw (simplified):
temp<elementType>
OctreeBase
temp<elementType>
OctreeIterator (this is used for all octree types, it uses virtual methods of the octree given to it to find nodes and do stuff to them, not sure if i should call this an iterator but dont know what else
)temp<elementType>
OctreeNodeBase (the base just contains the stuff required to store and access an object of elementType
