Speed concerns of octree implementation
<p>For couple of days now I am trying to speed up my Force-Directed graph implementation. So far I've implemented Barnes-Hut algorithm that's using octree to decrease number of computations. I've tested it multiple times and number of force related computations is indeed drastically decreased. Below is the plot of computations to number of nodes without Barns-Hut (blue line) and with (red line):
<a href="https://i.stack.imgur.com/VfH2h.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/VfH2h.png" alt="plot" /></a>
Even though now it should be a lot faster, the truth is that in the matter of speed (time) the upgrade is only few percent.</p>
<p>One part I suppose might be causing this is tree creation and elements in tree placing. Because elements are constantly moving I need to recreate tree each loop until some stop condition is reached. But if I will spend lot of time creating tree I will lost there time I've gained on force computation increase. That's my thinking at least. This is how I am adding elements in my main file loop:</p>
<pre><code>void AddTreeElements(Octree* tree, glm::vec3* boundries, Graph&amp; graph)
{
    for(auto&amp; node:graph.NodeVector())
    {
        node.parent_group = nullptr;
        if(node.pos[0] &lt; boundries[1][0] &amp;&amp; node.pos[0] &gt; boundries[0][0] &amp;&amp;
                node.pos[1] &gt; boundries[4][1] &amp;&amp; node.pos[1] &lt; boundries[1][1] &amp;&amp;
                node.pos[2] &lt; boundries[0][2] &amp;&amp; node.pos[2] &gt; boundries[3][2])
        {
            tree-&gt;AddObject(&amp;node.second);
            continue;
        }

        if(node.pos[0] &lt; boundries[0][0])
        {
            boundries[0][0] = node.pos[0]-1.0f;
            boundries[3][0] = node.pos[0]-1.0f;
            boundries[4][0] = node.pos[0]-1.0f;
            boundries[7][0] = node.pos[0]-1.0f;
        }
        else if(node.pos[0] &gt; boundries[1][0])
        {
            boundries[1][0] = node.pos[0]+1.0f;
            boundries[2][0] = node.pos[0]+1.0f;
            boundries[5][0] = node.pos[0]+1.0f;
            boundries[6][0] = node.pos[0]+1.0f;
        }

        if(node.pos[1] &lt; boundries[4][1])
        {
            boundries[4][1] = node.pos[1]-1.0f;
            boundries[5][1] = node.pos[1]-1.0f;
            boundries[6][1] = node.pos[1]-1.0f;
            boundries[7][1] = node.pos[1]-1.0f;
        }
        else if(node.pos[1] &gt; boundries[0][1])
        {
            boundries[0][1] = node.pos[1]+1.0f;
            boundries[1][1] = node.pos[1]+1.0f;
            boundries[2][1] = node.pos[1]+1.0f;
            boundries[3][1] = node.pos[1]+1.0f;
        }

        if(node.pos[2] &lt; boundries[3][2])
        {
            boundries[2][2] = node.pos[2]-1.0f;
            boundries[3][2] = node.pos[2]-1.0f;
            boundries[6][2] = node.pos[2]-1.0f;
            boundries[7][2] = node.pos[2]-1.0f;
        }
        else if(node.pos[2] &gt; boundries[0][2])
        {
            boundries[0][2] = node.pos[2]+1.0f;
            boundries[1][2] = node.pos[2]+1.0f;
            boundries[4][2] = node.pos[2]+1.0f;
            boundries[5][2] = node.pos[2]+1.0f;
        }
    }
}
</code></pre>
<p>What I am doing here is go through all my elements in graph and add them to tree root. Also, I am extending my box that is representing my octree borders for next loop, so all nodes will fit inside.</p>
<p>Fields important to octree structure update are as follows:</p>
<pre><code>Octree* trees[2][2][2];
glm::vec3 vBoundriesBox[8];
bool leaf;
float combined_weight = 0;
std::vector&lt;Element*&gt; objects;
</code></pre>
<p>and part of code responsible for update:</p>
<pre><code>#define MAX_LEVELS 5

void Octree::AddObject(Element* object)
{
    this-&gt;objects.push_back(object);
}

void Octree::Update()
{
    if(this-&gt;objects.size()&lt;=1 || level &gt; MAX_LEVELS)
    {
        for(Element* Element:this-&gt;objects)
        {
            Element-&gt;parent_group = this;
        }
        return;
    }

    if(leaf)
    {
        GenerateChildren();
        leaf = false;
    }

    while (!this-&gt;objects.empty())
    {
        Element* obj = this-&gt;objects.back();
        this-&gt;objects.pop_back();
        if(contains(trees[0][0][0],obj))
        {
            trees[0][0][0]-&gt;AddObject(obj);
            trees[0][0][0]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[0][0][1],obj))
        {
            trees[0][0][1]-&gt;AddObject(obj);
            trees[0][0][1]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[0][1][0],obj))
        {
            trees[0][1][0]-&gt;AddObject(obj);
            trees[0][1][0]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[0][1][1],obj))
        {
            trees[0][1][1]-&gt;AddObject(obj);
            trees[0][1][1]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[1][0][0],obj))
        {
            trees[1][0][0]-&gt;AddObject(obj);
            trees[1][0][0]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[1][0][1],obj))
        {
            trees[1][0][1]-&gt;AddObject(obj);
            trees[1][0][1]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[1][1][0],obj))
        {
            trees[1][1][0]-&gt;AddObject(obj);
            trees[1][1][0]-&gt;combined_weight += obj-&gt;weight;
        } else if(contains(trees[1][1][1],obj))
        {
            trees[1][1][1]-&gt;AddObject(obj);
            trees[1][1][1]-&gt;combined_weight += obj-&gt;weight;
        }
    }

    for(int i=0;i&lt;2;i++)
    {
        for(int j=0;j&lt;2;j++)
        {
            for(int k=0;k&lt;2;k++)
            {
                trees[i][j][k]-&gt;Update();
            }
        }
    }
}

bool Octree::contains(Octree* child, Element* object)
{
    if(object-&gt;pos[0] &gt;= child-&gt;vBoundriesBox[0][0] &amp;&amp; object-&gt;pos[0] &lt;= child-&gt;vBoundriesBox[1][0] &amp;&amp;
       object-&gt;pos[1] &gt;= child-&gt;vBoundriesBox[4][1] &amp;&amp; object-&gt;pos[1] &lt;= child-&gt;vBoundriesBox[0][1] &amp;&amp;
       object-&gt;pos[2] &gt;= child-&gt;vBoundriesBox[3][2] &amp;&amp; object-&gt;pos[2] &lt;= child-&gt;vBoundriesBox[0][2])
        return true;
    return false;
}
</code></pre>
<p>Because I am using pointers to move around tree elements I don't think object creation/destruction is an issue here. The one place I suppose might have impact on speed is this one:</p>
<pre><code>Element* obj = this-&gt;objects.back();
this-&gt;objects.pop_back();
if(contains(trees[0][0][0],obj))
</code></pre>
<p>Although I am not sure how I can ommit/speed it up. Does someone has any suggestions what can be done here?</p>
<p><strong>EDIT:</strong></p>
<p>I've done some napkin math and I suppose there is one more place which might be causing major speed decrease. Boundries checking in <code>Update</code> method looks like is doing a lot and what I calculated is that the added complexity due to this is in worst case scenario:</p>
<p>number_of_elements*number_of_childern*number_of_faces*MAX_LEVELS</p>
<p>which in my case is equal to number_of_elements*240.</p>
<p>Can someone please confirm if my idea is reasonable?</p>