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

}

}

## No comments:

Post a Comment