Acceleration Data Structure - Bounding Volume Hierarchy

I finished my bounding volume hierarchy earlier this week and I wanted to post my results and my code. The design is base on a binary tree, with each level splitting the higher level in half. Currently, I simply alternate between splitting along the three planes I have an option of splitting on. My initial structure is simply the bounding box of the .obj file (two points - one constructed from the smallest x, y, and z values and the other from the largest values.)

The basic binary tree stuff is sort of from here, but I wrote my own search routine and modified the code a bit.

The major point that could be improved on this is the splitting. Instead of alternating between the dimensions that I split on, I could write a method that determines the best way to split (based on the equality of the triangles in each subdivision.)

I spent a while getting this page to display in a somewhat aesthetic manner. Copy and paste between Kate and Firefox doesn't always look so great, and my blogger template doesn't lend itself to major widening my posts very well.

For a .tar.gz of this current revision, you can download one here. For the acceleration data structure, check out Object.cpp and Object.h.

1 Box (single bounding box)

   real    0m24.015s
   user    0m12.120s
   sys     0m0.070s

2 Boxes -

   real    0m16.169s
   user    0m8.080s
   sys     0m0.030s

16 Boxes -

   real    0m9.564s
   user    0m5.310s
   sys     0m0.050s

From 1 bounding box to 2 it is very easy to see the running time getting cut in half. From 2 to 16, there is not such an obvious speed up. I believe this is because we have to traverse more levels of our tree (not too much locality) verse iterate through bigger triangle vectors (more locality.) If my model had more triangles, I think we would still see an exponential decrease in running time as we increase the number of leaves in the binary tree.

void Object :: BuildLevels(TreeNode * rootNode, int currentDepth, int splitDimension){

 cout << "debugging = " << debugging << "\n";
 debugging = debugging + 1;
 cout << "currentDepth = " << currentDepth << "\n";

 assert (rootNode->item != NULL);6
 
 BoundingBox parentBox = *(rootNode->item);
 
 int maxDepth = 16;
 
 TreeNode * left, * right;
 
 left = new TreeNode();
 right = new TreeNode();

 rootNode->left = left;
 rootNode->right = right;
 
 
 BoundingBox * leftBox, * rightBox;
 
 Point3D smallPoint = parentBox.getSmallPoint();
 Point3D bigPoint = parentBox.getBigPoint();
 
 
 if (splitDimension == 0){
            // split along x
  float halfx = (parentBox.getSmallPoint().x + parentBox.getBigPoint().x) / 2;
  
   // Let's start with the smaller box along an x cut
  // it is defined by the smallest origional point and
  //    the x-cutpoint, y-maxPoint and z-maxpoint
      
  leftBox = new BoundingBox(smallPoint, Point3D(halfx, parentBox.getBigPoint().y,parentBox.getBigPoint().z));
  
  // the right box is defined by the x-cutpoint, y-minPoint,
  // z-minPoint and the bigPoint from the origional box
  rightBox = new BoundingBox(Point3D(halfx, parentBox.getSmallPoint().y, parentBox.getSmallPoint().z), bigPoint);
 }
 
 if (splitDimension == 1){
            // split along y
  float halfy = (parentBox.getSmallPoint().y + parentBox.getBigPoint().y) / 2;
  
  leftBox = new BoundingBox(smallPoint, Point3D(bigPoint.x, halfy, bigPoint.z));
  rightBox = new BoundingBox(Point3D(smallPoint.x, halfy, smallPoint.z), bigPoint);
 }
 
 if (splitDimension == 2){
            // split along z
  float halfz = (parentBox.getSmallPoint().z + parentBox.getBigPoint().z) / 2;
  
  leftBox = new BoundingBox(smallPoint, Point3D(bigPoint.x, bigPoint.y, halfz));
  rightBox = new BoundingBox(Point3D(smallPoint.x, smallPoint.y, halfz), bigPoint);
 }
 
 left->item = leftBox;
 right->item = rightBox;

 // let's go through all the triangles in the root and
 // assign them to the left box, right box or both.
 
 for (int i = 0; i <>triangles.size(); i++){
  
  Triangle * myTriangle =rootNode->triangles[i];
  
  
  if (triangleInsideBox(myTriangle, *leftBox) == true){
   // add the triangle to the left box
   left->triangles.push_back(myTriangle);
  }
  
  if (triangleInsideBox(myTriangle, *rightBox) == true){
   right->triangles.push_back(myTriangle);
  }
  
  if ((triangleInsideBox(myTriangle, *rightBox) == false) && (triangleInsideBox(myTriangle, *leftBox) == false)){
   cout << "ERROR!!! TRIANGLE IN NEITHER BOX!" << "\n";
  }
  
 }
 
 
 if (currentDepth < maxDepth){
  BuildLevels(left, currentDepth + 1,(splitDimension + 1) % 3);
 
  BuildLevels(right, currentDepth + 1,(splitDimension + 1) % 3);
  
  rootNode->triangles.clear();
 }
 
 else{
  cout << "number of boxes in leaf = " << rootNode->triangles.size() << "\n";
  
 }
}