diff options
Diffstat (limited to 'include/bvh-node.hpp')
| -rw-r--r-- | include/bvh-node.hpp | 86 |
1 files changed, 56 insertions, 30 deletions
diff --git a/include/bvh-node.hpp b/include/bvh-node.hpp index ee5068b..3a4ac4b 100644 --- a/include/bvh-node.hpp +++ b/include/bvh-node.hpp @@ -52,9 +52,8 @@ class bvh_node { class bvh {
public:
- // TODO: Fix one level too deep BVH
void build(sphere* spheres, uint32_t spheres_count) {
- nodes = std::vector<bvh_node>(spheres_count * spheres_count);
+ nodes = std::vector<bvh_node>(2 * spheres_count - 1);
boxes = std::vector<aabb>(spheres_count);
for (uint32_t sphere_id = 0; sphere_id < spheres_count; sphere_id++) {
@@ -73,31 +72,49 @@ public: void exporter() {
std::cout << "digraph bvh {" << std::endl;
- std::cout << "\t r";
- preorder(nodes[0].left_id, nodes[0].sphere_id);
+ std::cout << "\t 0";
+ // preorder(nodes[0].left_id, nodes[0].sphere_id);
+ traverse(nodes[0].left_id);
- std::cout << "\t r";
- preorder(nodes[0].left_id + 1, nodes[0].sphere_id);
+ std::cout << "\t 0";
+ // preorder(nodes[0].left_id + 1, nodes[0].sphere_id);
+ traverse(nodes[0].left_id + 1);
std::cout << "}" << std::endl;
}
- void preorder(int32_t id, int32_t sphere_id) {
+ bool traverse(int32_t id) {
if (id <= 0) {
- if (sphere_id < 0) {
- std::cout << ";" << std::endl;
- } else {
- std::cout << " -> sphere_" << sphere_id << ";" << std::endl;
- }
- return;
+ std::cout << ";" << std::endl;
+ return false;
}
std::cout << " -> " << id;
- preorder(nodes[id].left_id, nodes[id].sphere_id);
+ if (traverse(nodes[id].left_id)) {
+ std::cout << "\t " << id;
+ traverse(nodes[id].left_id + 1);
+ }
+
+ return true;
+ }
+
+ void preorder(int32_t id, int32_t sphere_id) {
+ if (id <= 0) {
+ return;
+ }
if (nodes[id].left_id > -1) {
+ std::cout << " -> " << id;
+ preorder(nodes[id].left_id, nodes[id].sphere_id);
+
std::cout << "\t " << id;
- preorder(nodes[id].left_id + 1, nodes[id].sphere_id);
+ if (nodes[nodes[id].left_id + 1].sphere_id == -1) {
+ preorder(nodes[id].left_id + 1, nodes[id].sphere_id);
+ } else {
+ std::cout << " -> sphere_" << nodes[nodes[id].left_id + 1].sphere_id << ";" << std::endl;
+ }
+ } else if (nodes[id].sphere_id > -1) {
+ std::cout << " -> sphere_" << nodes[id].sphere_id << ";" << std::endl;
}
}
@@ -114,35 +131,44 @@ private: }
void subdivide(uint32_t parent_id, uint32_t begin, uint32_t end) {
- if ((end - begin) == 0) {
- return;
- }
-
- auto left_id = parent_id * 2 + 1;
- auto right_id = parent_id * 2 + 2;
+ if ((end - begin) == 2) {
+ auto left_id = ++next_node_id;
+ auto right_id = ++next_node_id;
- nodes[parent_id].left_id = left_id;
+ nodes[parent_id].left_id = left_id;
- nodes[left_id] = bvh_node();
- nodes[right_id] = bvh_node();
+ nodes[left_id] = bvh_node();
+ nodes[right_id] = bvh_node();
- nodes[left_id].bounding_box = compute_bounds(begin, begin + ((end - begin) / 2));
- nodes[right_id].bounding_box = compute_bounds(begin + ((end - begin) / 2), end);
+ nodes[left_id].bounding_box = boxes[begin];
+ nodes[right_id].bounding_box = boxes[begin + 1];
- if ((end - begin) == 2) {
nodes[left_id].sphere_id = begin;
nodes[right_id].sphere_id = begin + 1;
} else if ((end - begin) == 1) {
- nodes[left_id].sphere_id = begin;
+ nodes[parent_id].bounding_box = boxes[begin];
+ nodes[parent_id].sphere_id = begin;
} else {
- subdivide(left_id, begin, begin + ((end - begin) / 2));
- subdivide(right_id, begin + ((end - begin) / 2), end);
+ auto left_id = ++next_node_id;
+ auto right_id = ++next_node_id;
+
+ nodes[parent_id].left_id = left_id;
+
+ nodes[left_id] = bvh_node();
+ nodes[right_id] = bvh_node();
+
+ nodes[left_id].bounding_box = compute_bounds(begin, begin + ((end - begin) / 2) + 1);
+ nodes[right_id].bounding_box = compute_bounds(begin + ((end - begin) / 2) + 1, end);
+
+ subdivide(left_id, begin, begin + ((end - begin) / 2) + 1);
+ subdivide(right_id, begin + ((end - begin) / 2) + 1, end);
}
}
public:
std::vector<bvh_node> nodes;
std::vector<aabb> boxes;
+ uint32_t next_node_id = 0;
};
#endif // !__BVH_NODE_HPP_
|