ivanceras / balisong Goto Github PK

currently you are having about 3 times the amount of indirecton nescesary, thereby potentially wasting both cache performance and memory usage.
the first level of indirection is by using a vec to store children, which has intrinsic bound checks, and contains a length, capacity and pointer to the heap memory containing the elements.
you could instead use a fixed sized array.
the second inderection comes from not storing the children inline, too. now this only works, if your T is smaller or equal in size to your pointer size, so 64 bit max, but that should not be too much of a problem if you are storing voxels, 64 bit is a lot of room for that.
now, let me explain why this matters: you have a tree, so most of your lookups are on the leaf-nodes, just because most nodes are leaf nodes. this becomes especially obvious, if you look at how your cursor moves when you iterate over the tree.
by not storing the content in the node, but storing an array of an union type that is either a child node or your actual content, you can loose that indirecton.

the last issue with the current octree is, that you use Option. if your type is not null-optimizable, like for example a pointer or stuff, each usage of option, because its an enum uses 64 extra bits, using one of those bits to store if its Some or None. this is incredibly watefull if your T is small in size.
if you use the optimisation in the previous paragraph, you can (manually) summarize the tag into one one byte field (or 8 1 byte fields, could be faster cause that would not need extra bitshifts, that would need to be tested).

I have a pet project lying around, where i did just that, but the octree currently misses the raycasting-methods.

I can polish that up a bit and publish it as a library or we can try to integrate it into your code base, if you are interested. i would prefer the library-approach, as i would prefer lgpl as license.

I have also experimented with storing the octree in a memory-mapped file, but not finished the implementation yet. that might be interesting for you, too, in case you want to allow rendinging over ram-sized models without manually managing memory.

Also merging children after an insertion made all of them equal is suprizingly hard to do iteratively due to rusts borrow checker. (it only works by basically circumventing it), so that would cause a recursion, but its (obviously) limited to a depth of 64 or 32 depending on pointer size.
But it would remove the need to hollow out statues, or handle the absence of material in any way special (it would just be the material 0, for example, and would fill everything thats not filled by other material)