diff options
Diffstat (limited to 'dev/MinGfx/src/bvh.cc')
-rw-r--r-- | dev/MinGfx/src/bvh.cc | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/dev/MinGfx/src/bvh.cc b/dev/MinGfx/src/bvh.cc new file mode 100644 index 0000000..ff8dbbc --- /dev/null +++ b/dev/MinGfx/src/bvh.cc @@ -0,0 +1,120 @@ +#include "bvh.h" + +#include "mesh.h" +#include "ray.h" + +#include <float.h> +#include <algorithm> + +namespace mingfx { + + +BVH::BVH() : root_(NULL) { +} + +BVH::~BVH() { + FreeNodeRecursive(root_); +} + +void BVH::CreateFromMesh(const Mesh &mesh) { + FreeNodeRecursive(root_); + + std::vector<AABB> tri_boxes; + for (int i=0; i<mesh.num_triangles(); i++) { + AABB box = AABB(mesh, i); + box.set_user_data(i); + tri_boxes.push_back(box); + } + + root_ = new Node(); + BuildHierarchyRecursive(root_, tri_boxes); +} + +void BVH::CreateFromListOfBoxes(const std::vector<AABB> &boxes) { + FreeNodeRecursive(root_); + + root_ = new Node(); + BuildHierarchyRecursive(root_, boxes); +} + + +void BVH::FreeNodeRecursive(Node* node) { + if (node == NULL) return; + FreeNodeRecursive(node->child1); + FreeNodeRecursive(node->child2); + delete node; +} + +bool sort_by_x(const AABB &lhs, const AABB &rhs) { + return (lhs.min()[0] + lhs.max()[0]) < (rhs.min()[0] + rhs.max()[0]); +} + +bool sort_by_y(const AABB &lhs, const AABB &rhs) { + return (lhs.min()[1] + lhs.max()[1]) < (rhs.min()[1] + rhs.max()[1]); +} + +bool sort_by_z(const AABB &lhs, const AABB &rhs) { + return (lhs.min()[2] + lhs.max()[2]) < (rhs.min()[2] + rhs.max()[2]); +} + +void BVH::BuildHierarchyRecursive(Node *node, std::vector<AABB> tri_boxes) { + // got down to a leaf, a single box + if (tri_boxes.size() == 1) { + node->box = tri_boxes[0]; + return; + } + + // calc the full bounding box for this node + for (int i=0; i<tri_boxes.size(); i++) { + node->box = node->box + tri_boxes[i]; + } + + // sort boxes along the longest axis + Vector3 dims = node->box.Dimensions(); + dims[0] = fabsf(dims[0]); + dims[1] = fabsf(dims[1]); + dims[2] = fabsf(dims[2]); + + if ((dims[0] > dims[1]) && (dims[0] > dims[2])) { + std::sort(tri_boxes.begin(), tri_boxes.end(), sort_by_x); + } + else if ((dims[1] > dims[0]) && (dims[1] > dims[2])) { + std::sort(tri_boxes.begin(), tri_boxes.end(), sort_by_y); + } + else { + std::sort(tri_boxes.begin(), tri_boxes.end(), sort_by_z); + } + + // assign half to child1 and half to child2 + std::size_t const half_size = tri_boxes.size() / 2; + std::vector<AABB> left_boxes(tri_boxes.begin(), tri_boxes.begin() + half_size); + std::vector<AABB> right_boxes(tri_boxes.begin() + half_size, tri_boxes.end()); + + node->child1 = new Node(); + BuildHierarchyRecursive(node->child1, left_boxes); + node->child2 = new Node(); + BuildHierarchyRecursive(node->child2, right_boxes); +} + +std::vector<int> BVH::IntersectAndReturnUserData(const Ray &r) const { + std::vector<int> data_list; + IntersectRecursive(r, root_, &data_list); + return data_list; +} + +void BVH::IntersectRecursive(const Ray &r, Node *node, std::vector<int> *data_list) const { + float t; + if (r.IntersectAABB(node->box, &t)) { + if ((node->child1 == NULL) && (node->child2 == NULL)) { + // reached a leaf node, add the object's user data to the list + data_list->push_back(node->box.user_data()); + } + else { + // go deeper and check children + IntersectRecursive(r, node->child1, data_list); + IntersectRecursive(r, node->child2, data_list); + } + } +} + +} // end namespace |