Average performance

[MoritzSkowronski]

Hi,

First of all thank you for the great work and especially the extensive documentation! This is super helpful! I just tried your unity implementation of the space colonization algorithm and on my M1 MacBook, it gets very slow very fast to the point of it actually crashing. Apart from the tube rendering (which was expected to be so heavy in performance), it seems that the rebuilding of the KD-tree every frame mainly leads to the crashes (I'd say with a node count of about 10.000). Is this your experience as well? I'm a bit surprised here, because your javascript demos run so smoothly and they seem to be using a KD-tree as well (and not compute shader magic).

All the best,
Moritz

[jasonwebb]

Hi Moritz! Performance is definitely a challenge with this algorithm, and I didn't really spend any time trying to optimize the code to solve it. This project was mainly a proof of concept, so they is lots of room for improvement for practical applications! I'm not a Unity dev myself, so I probably did a few things wrong too haha.

I see some performance issues in the 2D Javascript versions too, so my hunch is that the biggest performance bottleneck comes from trying to run the algorithm in real-time given that it is CPU-bound and not (like you mentioned) offloaded to a GPU compute shader. The Unity version is also 3D, so there is an exponential increase in the number of nodes being processed each frame because of that extra dimension. Moving the calculations to a compute shader would help for sure, but I'm not sure how to do that in Unity.

Another idea that might improve performance could be to "freeze" old nodes after a certain amount of time. New growth tends surround and constrain older growth, so after a while there isn't much benefit to including old nodes in the KD tree or using them in calculations. IIRC the position of each node is updated based on the positions of all the other nodes (maybe within a radius), so they amount of calculations per frame increases exponentially relative to the number of nodes. Limiting that to only nodes within a radius and skipping "dead" nodes could go a long way!

I also agree that it feels weird to rebuild the KD tree in every step of the simulation, but from what I understand this is faster than trying to diff, update, and prune the tree in every step.