Skip to content
Snippets Groups Projects
BarnesHutTree.cpp 1.49 KiB
Newer Older
#include "BarnesHutTree.hpp"
#include "Node.hpp"
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
#include <iostream>
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
	using namespace std;

	BarnesHutTree::BarnesHutTree() {
	}

	BarnesHutTree::~BarnesHutTree() {
	vector<Box> BarnesHutTree::splitBB(Node* node) {
		return node->getBB().octreeSplit();
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
	int BarnesHutTree::numberOfChildren() {
		return 8;
	}

	void BarnesHutTree::build(vector<Body> bodies) {
		Node* current;
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		if (bodies.empty()) return;
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		//insert root node
		this->nodes->insertAfter(new Node(this));
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		current = this->nodes->next;
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		//assign bodies to root node
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		current->bodies = bodies;
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		//setup proper bounding box
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		current->extendBBforBodies();
		current->extendBBtoCube();
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		current->afterSubtree = current->next;

		//iterate over existing boxes and split if it contains too much bodies
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
		while (current != this->nodes) {
			if (current->isSplitable()) {
				vector<Box> subboxes = this->splitBB(current);
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
				current->leaf = false;

				for (vector<Box>::iterator it = subboxes.begin(); it != subboxes.end(); it++) {
					Node* child = new Node(this);
					child->parent = current;
					child->bb = *it;
					child->bodies = it->copyBodies(current->bodies);
					current->insertAfter(child);
					child->nextSibling = current->next;
					current->next->prevSibling = child;
					if (it != subboxes.begin()) {
						child->afterSubtree = child->next;
					} else {
						child->afterSubtree = current->afterSubtree;
					}
Paul Heinzlreiter's avatar
Paul Heinzlreiter committed
				}
				current->bodies.clear();
			}
			current = current->next;
		}