Thursday, April 3, 2008

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

if (triangleInsideBox(myTriangle, *rightBox) == true){

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);


cout << "number of boxes in leaf = " << rootNode->triangles.size() << "\n";


No comments: