Building an Octree

I've used bits of an article I read (http://codingshuttle.com/2014/01/building-a-multipurpose-octree-datastructre/) on building octrees, for use with a render-engine I'm making. The ray-tracing of the octree seems to work, as I am able to render hard-coded octrees just fine, 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. This is my code right now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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;
}


Sorry for the amount of code. Does anyone have any experience with octrees who can help?


Fafner
Last edited on
Registered users can post here. Sign in or register to post.