Building an octree

Starting easy.
fafner
Posts: 1
Joined: Sat Jul 05, 2014 9:57 am

Building an octree

Postby 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

Return to “My First...”

Who is online

Users browsing this forum: No registered users and 1 guest