I am trying to solve a Force-Directed / Barnes-Hut chart problem in a graphical visualization application. I have checked so far the creation of the octets, and it looks correct (the tree is represented by fields and circles - my nodes in the graph):
My fields are as Quadtreefollows:
class Quadtree
{
public:
int level;
Quadtree* trees[2][2][2];
glm::vec3 vBoundriesBox[8];
glm::vec3 center;
bool leaf;
float combined_weight = 0;
std::vector<Element*> objects;
private:
protected:
}
This is how I add elements recursively to my quadrant:
void Quadtree::AddObject(Element* object)
{
this->objects.push_back(object);
}
void Quadtree::Update()
{
if(this->objects.size()<=1 || level > MAX_LEVELS)
{
for(Element* Element:this->objects)
{
Element->parent_group = this;
this->combined_weight += Element->weight;
}
return;
}
if(leaf)
{
GenerateChildren();
leaf = false;
}
while (!this->objects.empty())
{
Element* obj = this->objects.back();
this->objects.pop_back();
if(contains(trees[0][0][0],obj))
{
trees[0][0][0]->AddObject(obj);
trees[0][0][0]->combined_weight += obj->weight;
} else if(contains(trees[0][0][1],obj))
{
trees[0][0][1]->AddObject(obj);
trees[0][0][1]->combined_weight += obj->weight;
} else if(contains(trees[0][1][0],obj))
{
trees[0][1][0]->AddObject(obj);
trees[0][1][0]->combined_weight += obj->weight;
} else if(contains(trees[0][1][1],obj))
{
trees[0][1][1]->AddObject(obj);
trees[0][1][1]->combined_weight += obj->weight;
} else if(contains(trees[1][0][0],obj))
{
trees[1][0][0]->AddObject(obj);
trees[1][0][0]->combined_weight += obj->weight;
} else if(contains(trees[1][0][1],obj))
{
trees[1][0][1]->AddObject(obj);
trees[1][0][1]->combined_weight += obj->weight;
} else if(contains(trees[1][1][0],obj))
{
trees[1][1][0]->AddObject(obj);
trees[1][1][0]->combined_weight += obj->weight;
} else if(contains(trees[1][1][1],obj))
{
trees[1][1][1]->AddObject(obj);
trees[1][1][1]->combined_weight += obj->weight;
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
trees[i][j][k]->Update();
}
}
}
}
bool Quadtree::contains(Quadtree* child, Element* object)
{
if(object->pos[0] >= child->vBoundriesBox[0][0] && object->pos[0] <= child->vBoundriesBox[1][0] &&
object->pos[1] >= child->vBoundriesBox[4][1] && object->pos[1] <= child->vBoundriesBox[0][1] &&
object->pos[2] >= child->vBoundriesBox[3][2] && object->pos[2] <= child->vBoundriesBox[0][2])
return true;
return false;
}
As you can see in the figure, the nodes are very grouped. I tried to figure out how to fix my repulsive force calculations, but it still doesn't work, and the result is still the same.
So how do I calculate it:
First, in my main file, I run a loop through all nodes of the graph:
for(auto& n_el:graph->node_vector)
{
tree->CheckNode(&n_el);
}
Further in my class Qyadtree( tree- this is a class object), I have this recursive method:
void Quadtree::CheckNode(Node* node)
{
glm::vec3 diff = this->center - node->pos;
double distance_sqr = (diff.x * diff.x) + (diff.y*diff.y) + (diff.z*diff.z);
double width_sqr = (vBoundriesBox[1][0] - vBoundriesBox[0][0]) * (vBoundriesBox[1][0] - vBoundriesBox[0][0]);
if(width_sqr/distance_sqr < 10.0f || leaf)
{
if(leaf)
{
for(auto& n: objects)
{
n->Repulse(&objects);
}
}
else
{
node->RepulseWithGroup(this);
}
}
else
{
for(int i=0; i<2; i++)
{
for(int j=0; j<2; j++)
{
for(int k=0; k<2; k++)
{
trees[i][j][k]->CheckNode(node);
}
}
}
}
}
, , node :
double Node::Repulse(std::vector<Node*>* nodes)
{
double dx;
double dy;
double dz;
double force = 0.0;
double distance_between;
double delta_weights;
double temp;
for(auto& element_node:*nodes)
{
if(this->name == element_node->name)
{
continue;
}
if(!element_node->use) continue;
delta_weights = 0.5 + abs(this->weight - element_node->weight);
dx = this->pos[0] - element_node->pos[0];
dy = this->pos[1] - element_node->pos[1];
dz = this->pos[2] - element_node->pos[2];
distance_between = dx * dx + dy * dy + dz * dz;
force = 0.19998 * delta_weights/(distance_between * distance_between);
temp = std::min(1.0, force);
if(temp<0.0001)
{
temp = 0;
}
double mx = temp * dx;
double my = temp * dy;
double mz = temp * dz;
this->pos[0] += mx;
this->pos[1] += my;
this->pos[2] += mz;
element_node->pos[0] -= mx;
element_node->pos[1] -= my;
element_node->pos[2] -= mz;
}
}
void Node::RepulseWithGroup(Quadtree* tree)
{
double dx;
double dy;
double dz;
double force = 0.0;
double distance_between;
double delta_weights;
double temp;
delta_weights = 0.5 + abs(this->weight - tree->combined_weight);
dx = this->pos[0] - tree->center.x;
dy = this->pos[1] - tree->center.y;
dz = this->pos[2] - tree->center.z;
distance_between = dx * dx + dy * dy + dz * dz;
force = 0.19998 * delta_weights/(distance_between * distance_between);
temp = std::min(1.0, force);
if(temp<0.0001)
{
temp = 0;
}
double mx = temp * dx;
double my = temp * dy;
double mz = temp * dz;
this->pos[0] += mx + this->parent_group->repulsion_force.x;
this->pos[1] += my + this->parent_group->repulsion_force.y;
this->pos[2] += mz + this->parent_group->repulsion_force.z;
}
, :
if(width_sqr/distance_sqr < 10.0f || leaf)
{
if(leaf)
{
for(auto& n: objects)
{
n->Repulse(&objects);
}
}
else
{
node->RepulseWithGroup(this);
}
}
, , . , , . .
, ( , octree ) - . , / :
, , , O(n^2), Barnes-Hut O(nlogn). , nlogn.
- , ? , , - .
EDIT:
@Ilmari Karonen, MAX_LEVELS 5, 20, 50, 100. . -, , ( )