Replace KD-Tree with Octree

[PavelBlend]

While reading the messages by Pyroevil on the forum, I noticed that he wanted to replace KD-Tree with Octree. Octree can be faster.

@OmidGhotbi do you know if Octree will be faster than KD-Tree? Will it be difficult to rewrite the code in Octree? Is it worth spending energy on this?

[OmidGhotbi]

not sure, it depends on many things, both are tree-based data used for organizing points in a multi-dimensional space, an octree is more manageable but you can not say it is faster hugely, it's based on many parameters,
the biggest problem is we depend on data from python in blender, collision and links and particles are in blender.
look at this.

i managed to get 90% of CPU power, If i make it stable enough i can get amazing results. if we have a better equation and better Octreeit will be more interesting as well.
My problem is you can see it's faster and so smooth compared to the last code but at the end, most of Cpu usage will be wasted for drawing more smoother UI getting and sending data to the blender and calculating collision etc.
As more power I got from CPU I need to spend more and more on Blender. :(

[OmidGhotbi]

[OmidGhotbi]

i managed to write the Octree version last night to test it:

the results are more or less the same, it can crash on breaking point (sometimes works fine no issue) that i need to investigate what is wrong with it but i in the matter of performance I did not gain so much speed from it.


One thing I noticed it needs almost 3 times the memory.
i think i do not know how to use the debugging symbols in blender it gives me nothing, absolutely nothing. can you help me with that?

[PavelBlend]

Pyroevil wrote about octree here: blenderartists forum

I find a python kdtree here : http://code.google.com/p/python-kdtree/
It’s very powerfull , kdtree generation take 13sec for 250 000particles but requesting to find the nearest neighbours particles of a particle or of a coordinate take 0.000002sec !And I can do a search for the 2 … 3 … 500 nearest neighbours and the time to find it is approximatly the same !!! The only problem is I cannot update particles position without have to rebuild the entire tree. I need to find a script with implementation of adding particles or changing particles corrdinate with self-balancing kd-tree. And just by reading wikipedia articles to see it’s seem to not be easy : [http://en.wikipedia.org/wiki/K-d_tree#Adding_elements 1](http://en.wikipedia.org/wiki/K-d_tree#Adding_elements)

My second option is octree. Octree seem to be easy to build and change I think. I need to find a good integration of it before to thinking about create my own. I’m not sure how octree exactly works like did a request like nearest neighbours.

My last option is to code my one tree. It’s I tree I have imaginated and it’s work. But it’s for sure is not the most efficient. Why ? because it’s soo simple than it’s impossible nobody thinking about it before me. I talk with my brother( I real coder/developper , ex-worker at Ubisoft and currently return at university to improve is skill ) yesterday and he think my idea is not bad but have probably limitation when time to come implementing other collision gemetry objects in the system than “same size” self-colliding particles.

My best guest for performance is Kd-Tree. Apparently XSI-ICE use it. I just need to find a self-balanced one :confused:. A lot of google search and reading to do !

The idea is not to rebuild Octree, but to update it. Construction takes a long time.

[PavelBlend]

can you help me with that?

I'm not good at C. I don't know how to do this in blender.

[OmidGhotbi]

Thanks for the resource, i rewrote the code in Octree I can see the collision detection and movement are better but the speed is exactly the same, it did not change at all maybe in 1 second in every minute not sure because many parameters are random so we can not say for sure.
the problem is we are dependent on the blender physics system and collision detection etc, and I'm pretty sure it is a single thread nothing we can do for it unless build the blender from the source code.
take a look at this.
https://archive.blender.org/developer/D11186
we can not improve more than this, I tested it eleven when I managed to get 99% of the CPU it was not worth it because I spent more and more CPU on the blender itself.
The best balanced performance I got was around 25% to 30% of CPU the update in blender and particles was significantly better. and I need to repeat most of the process on a blender.
The only option is to separate it from the blender or make the physics and particles system in the blender multithreaded.

I noticed when I load just the cache blender will get slow on collision and that's strange, basically, blender will calculate particles no matter what we do and we always lose performance because of it.

[PavelBlend]

The only option is to separate it from the blender or make the physics and particles system in the blender multithreaded.

I do not know how to do it. I would like to rewrite molecular so that it becomes a separate program. Blender introduces many restrictions for the addon. And if this program works stably, then integrate it with blender in the form of a pyd library. But I have no experience in creating such programs.

[OmidGhotbi]

I need to rewrite the code with TBB in C++ because I have seen so many memory-related issue that they do not make any sense. sometimes one variable will change between 2 lines and this is mostly about multithreading writing one variable at the same time or we have a memory leak.
if I gain nothing from TBB then we can try other solutions.
and finally, we need to move to outside of blender limited. i will try my best to create start point that we can work on it together. for the moment no matter how much speed I gain because it will be sacrificed for the blender or overheads.

[OmidGhotbi]

one thing i need to mention is I replaced quick_sort with heap sort and merge sort so I can see if the problem is in recursive and it causes overflow. it acts better and more stable with big particle numbers bu again no speed gain. I'm almost sure that blender will not let us gain control of more than 1 or 2 cores.