The latest feature that I want to share with you is something I wanted to implement long ago. It is the implementation of space partitionning. The space can now be partitionned thanks to an octree.
This allows to considerably optimize algorithms running in O(n²) by making them scale better : the complexity of such algorithms becoming O(nlog(n)) with an octree.
Algorithms of quadratic complexity are typically algorithms where every particle is under the influence of all the others. A few examples :
- particle vs particle collision
- simulation of gravitational forces (universe, galaxies...)
The octree management in SPARK 2 is totally transparent from the user point of view. Modifiers needing octrees have to set a constant to true. In that way, a group containing at least one modifier requesting an octree will create one and maintain it at each update. Neighboring particles and states of octree nodes can then be easily gotten in the update code of modifiers.
I ported the collider modifier (particle vs particle collision) so that it takes advantage of the octree and the increase in performance is quite consequent. With the collision demo I can have 15000 particles colliding with each other at around 60fps. The time step has however to be reduced to keep the simulation realistic.
I modified the collision demo so that it has more particles and it allows to render the octree state (by pressing F2) :
Some changes in the interface are still necessary and maybe the possibility to tweak the octree for fine tuning and gets the best of its power. Some further optimizations might also still be possible.