balisong
balisong copied to clipboard
ivanceras
Optimize octree by a bit, memory-wise
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)
Hi, I appreciate your detailed exploration and explanation of this pet project, but I wrote this project while I was just learning rust and exploring voxels as well. It was fun, but I don't really see any practical usage for this. I am working on some other projects that are practically useful. I don't have any plans of continuing graphics exploration for now, as there are real good solutions out there that are far much better than voxels. I was just really scratching my itch at that time and I feel satisfied with just looking at the rendered objects from voxel data.
Good luck on your pet project.
Hello @iqualfragile I'm itching on scratching more on this project. I'm ambitious of implementing a detailed volumetric rendering implementation using high resolution voxels. I know rust better now, and understand some of the errors I've made during the exploration of these project. I do want to collaborate with you on pushing on this idea. I'm hesitant with using restrictive license though, which means if a certain entity is interested in doing some commercial version of the project, it wouldn't be able to do so and will loose our opportunity to have a commercial support.
hi @ivanceras i, am still interested in doing this.
tech wise i think we should use nightly until unsafe_unions hits stable, because that makes things so much easier. i had been using a macro before, which worked, but was a bit meh.
license wise: well, lgpl (and gpl, too, btw) does allow selling of the product, and lgpl specifically does not force a project wishing to use the library to have a lgpl license, too. i think that is a fair deal, people use the library however they want, in whichever project (commercial/closed source or not) they want, but if they make changes to the library they should contribute those back. i would even prefer a license which excludes military use, because right now linux is used to guide missiles, and i do not want code i write to contribute to killing people, which is essentially what a military does, kill people. and seeing military uses for a good voxel library does not require a lot of imagination.
i think i have a pretty good understanding of how to implement the octree as dense as possible, but i do not know too much about the raycasting/rendering part of things, and would be interested in learning a bit in that regard, so i think this could be a good match.
@ivanceras unions are now in rust, i rewrote my code using it, it looks good to me, want to get started?
Hi @iqualfragile I did an initial rewrite of the code, but at that time my PC broke down with the uncommitted code with it. Unfortunately, I'm not touching any of this code anytime soon. Since I been very busy with lots of stuffs.
Did you mean struct instead of unions? Struct has been there for long already, but didn't know about unions. Is that an RFC? a link to it maybe.
https://github.com/rust-lang/rust/issues/32836
unions are just like enums, but without the tag, so you need to externally save which variant they currently are, and accesses are unsafe.
they are not strictly in rust yet, but they are in nightly, so its useable.
about your loss of code: better to rewrite it quickly while you still remember all your decisions, later on you will actually have to redo the thinking, not just the typing