Linearize octree node storage

CelestiaProject / Celestia

Real-time 3D visualization of space.

https://celestiaproject.space

GNU General Public License v2.0

1.87k stars 310 forks source link

Linearize octree node storage #2222

Closed ajtribick closed 4 months ago

ajtribick commented 4 months ago

Separate octree types and octree node types
Store nodes in vectors (BlockArray for the DynamicOctree)
For static octree, order the nodes in depth-first order, together with the node to jump to when skipping the subtree
Avoids need to perform recursive calls when processing the octree (including the destructor)

ajtribick commented 4 months ago

The switch from creating all 8 child nodes at the same time to only creating when an object needs to be added reduces the number of nodes in the final octree:

Stars: 112745 --> 111176 DSOs: 6337 -> 4095

We also track the brightness via the objects contained within each node (and descendant nodes) rather than using the computed threshold magnitudes, this should allow for earlier culling of faint nodes when processing visible objects.

375gnu commented 4 months ago

Any difference in loading & finding stars?

sonarcloud[bot] commented 4 months ago

Quality Gate passed

Issues
0 New issues
0 Accepted issues

Measures
0 Security Hotspots
0.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarCloud

ajtribick commented 4 months ago

Didn't see any major differences in render time processing the star octree, seems slightly faster (by 0.1-0.5 ms, so nothing really noticeable) to build the star octree.