Building an octree

Practical and theoretical implementation discussion.
Post Reply
fafner
Posts: 1
Joined: Sat Jul 05, 2014 9:57 am

Building an octree

Post by fafner » Sat Jul 05, 2014 4:31 pm

Hi,

this is my first post here, I hope its the right place to ask this question:)

I've used bits of an article I read (http://codingshuttle.com/2014/01/buildi ... astructre/) on building octrees, for use with a path tracer I'm making. The ray-tracing of the octree seems to work, as I am able to render hard-coded octrees just fine,

Image

but building the octree from for example an obj-file (which I know is being loaded correctly), by using the build()-function below, gives results varying from segfaults to only rendering part of the mesh. Sorry I can't be more technical/specific about what is going wrong.

Image

This is a mesh rendered without octree (extremely slow)

This is my code right now:

Code: Select all

void OctreeAccelerator::build()
{
	BoundingBox bb = Composite::getBoundingBox();

	//construct octree bounding box by the largest direction in the composite bb
	double wx = bb.p2.x - bb.p1.x;
	double wy = bb.p2.y - bb.p1.y;
	double wz = bb.p2.z - bb.p1.z;
	double nw = max(wx, max(wy, wz)) / 2;
	Vector3 center(bb.p1.x+wx/2, bb.p1.y+wy/2, bb.p1.z+wz/2);
	Vector3 p1(center.x-nw, center.y-nw, center.z-nw);
	Vector3 p2(center.x+nw, center.y+nw, center.z+nw);
	std::shared_ptr<BoundingBox> nb(new BoundingBox(p1, p2));

	root = buildOctree(objects, nb, 20);

	objects.erase(objects.begin(), objects.end());
}

std::shared_ptr<OctreeNode> OctreeAccelerator::buildOctree(std::vector<std::shared_ptr<Object> > obj, std::shared_ptr<BoundingBox> bb, int depth)
{
	if (depth < 0 || obj.size() < 3)
		return nullptr;

	std::vector<std::shared_ptr<BoundingBox> >boxes = bb->splitToEight();

	//Create node and attach objects
	std::shared_ptr<OctreeNode> node(new OctreeNode(bb));
	node->leaves = std::vector<std::shared_ptr<Object> >(obj);

	std::vector<std::shared_ptr<Object> > boxObjects[8];
	for(unsigned long i = 0; i < obj.size(); i++)
	{
		std::shared_ptr<Object> g = objects.at(i);
		for(int box = 0; box < 8; box++)
		{
			if (g->geometry->overlaps(boxes[box]))
			{
				boxObjects[box].push_back(obj[i]);
			}
		}
	}

	for(int i = 0; i < 8; i++)
	{
		size_t size = boxObjects[i].size();
		if (size)
			node->childNodes[i] = buildOctree(boxObjects[i], boxes[i], depth-1);
	}

	return node;
}

...

std::vector<std::shared_ptr<BoundingBox> > BoundingBox::splitToEight() {
	std::vector<std::shared_ptr<BoundingBox> > boxes;
	for(int i = 0; i < 8; i++)
	{
		Vector3 newOrigin = getCenter();

		float halfDimX = (p2.x - p1.x) / 4;
		float halfDimY = (p2.y - p1.y) / 4;
		float halfDimZ = (p2.z - p1.z) / 4;

		newOrigin.x += halfDimX*2 * (i&4 ? 0.5f : -0.5f);
		newOrigin.y += halfDimY*2 * (i&2 ? 0.5f : -0.5f);
		newOrigin.z += halfDimZ*2 * (i&1 ? 0.5f : -0.5f);
		Vector3 p1(newOrigin.x - halfDimX, newOrigin.y - halfDimY, newOrigin.z - halfDimZ);
		Vector3 p2(newOrigin.x + halfDimX, newOrigin.y + halfDimY, newOrigin.z + halfDimZ);
		std::shared_ptr<BoundingBox> nb(new BoundingBox(p1, p2));
		boxes.push_back(nb);
	}

	return boxes;
}
I'm sorry for the amount of code. Does anyone have any tips on what I might be doing wrong?


Fafner

Post Reply