Depth first ordered bvh

1 files changed, 98 insertions, 41 deletions

diff --git a/include/bvh-node.hpp b/include/bvh-node.hpp
index 2affa38..16c3cb3 100644
--- a/include/bvh-node.hpp
+++ b/include/bvh-node.hpp
@@ -14,16 +14,22 @@ class bvh_node {
 

         aabb bounding_box;

 

-        int32_t left_id    = -1;

+        int32_t next_id    = -1;

         int32_t sphere_id   = -1;

         uint32_t padding[2];

 };

 

+struct temp_node : public bvh_node {

+    int32_t left_id;

+    int32_t df_id;

+};

+

 class bvh {

 public: 

     void build(sphere* spheres, uint32_t spheres_count) {

         nodes = std::vector<bvh_node>(2 * spheres_count - 1);

-        leafs = std::vector<bvh_node>(spheres_count);

+        temp_nodes = std::vector<temp_node>(2 * spheres_count - 1);

+        leafs = std::vector<temp_node>(spheres_count);

         this->spheres = spheres;

 

         for (uint32_t id = 0; id < spheres_count; id++) {

@@ -31,10 +37,26 @@ public:
             leafs[id].sphere_id = id;

         }

 

-        nodes[0] = bvh_node();

+        temp_nodes[0] = temp_node();

 

-        nodes[0].bounding_box = compute_bounds(0, spheres_count);

+        temp_nodes[0].bounding_box = compute_bounds(0, spheres_count);

         subdivide(0, 0, spheres_count);

+

+        set_depth_first_order();

+

+        for (uint32_t id = 0; id < temp_nodes.size(); id++) {

+            auto old_node = temp_nodes[id];

+            auto &node = nodes[old_node.df_id];

+

+            node.sphere_id = old_node.sphere_id;

+            node.bounding_box = old_node.bounding_box;

+

+            if (old_node.next_id != -1) {

+                node.next_id = temp_nodes[old_node.next_id].df_id;

+            }

+        }

+

+        // exporter();

     }

 

     //-------------------------

@@ -43,30 +65,53 @@ public:
     void exporter() {

         std::cout << "digraph bvh {" << std::endl;

 

-        std::cout << "\t 0";

-        traverse(nodes[0].left_id);

+        traverse_depth_first(temp_nodes, 0);

 

-        std::cout << "\t 0";

-        traverse(nodes[0].left_id + 1);

+        // traverse_depth_first_ordered(-1, 0);

 

         std::cout << "}" << std::endl;

     }

 

-    bool traverse(int32_t id) {

+    bool traverse_depth_first(std::vector<temp_node>& nodes, int32_t id) {

         if (id <= 0) {

             std::cout << ";" << std::endl;

             return false;

         }

 

         std::cout << " -> " << id;

-        if (traverse(nodes[id].left_id)) {

+        if (traverse_depth_first(nodes, nodes[id].left_id)) {

             std::cout << "\t " << id;

-            traverse(nodes[id].left_id + 1);

+            traverse_depth_first(nodes, nodes[id].left_id + 1);

         }

 

         return true;

     }

 

+    int32_t traverse_depth_first_ordered(std::vector<bvh_node>& nodes, int32_t parent_id, int32_t id) {

+        if (id == -1) {

+            return -1;

+        }

+

+        if (nodes[id].sphere_id == -1) {

+            int32_t left = id + 1;

+            int32_t next_id;

+

+            std::cout << "\t " << parent_id << " -> " << id << ";\n";

+            next_id = traverse_depth_first_ordered(nodes, id, left);

+

+            if (next_id != -1) {

+                return traverse_depth_first_ordered(nodes, id, next_id);

+            }

+        } else if (nodes[id].sphere_id != -1 && nodes[id].next_id != -1) {

+            std::cout << "\t " << parent_id << " -> " << id << ";\n";

+            return nodes[id].next_id;

+        } else {

+            std::cout << "\t " << parent_id << " -> " << id << ";\n";

+        }

+

+        return -1;

+    }

+

 private:

 

     aabb compute_bounds(uint32_t begin, uint32_t end) {

@@ -80,34 +125,39 @@ private:
         return global_box;

     }

 

+    int32_t find_split_axis(aabb bounding_box) {

+        int32_t split_axis = 0;

+        float size = 0;

+

+        // Find largest axis

+        for (size_t id = 0; id < 3; id++) {

+            auto current_size = bounding_box.maximum[id] - bounding_box.minimum[id];

+            if (current_size > size) {

+                size = current_size;

+                split_axis = id;

+            }

+        }

+

+        return split_axis;

+    }

+

     void subdivide(uint32_t parent_id, uint32_t begin, uint32_t end) {

         size_t count = end - begin;

          if (count == 1) {

-            nodes[parent_id] = leafs[begin];

+            temp_nodes[parent_id] = leafs[begin];

             return;

         }

 

         auto left_id = ++next_node_id;

         auto right_id = ++next_node_id;

 

-        nodes[parent_id].left_id = left_id;

+        temp_nodes[parent_id].left_id = left_id;

 

         if (count == 2) {

-            nodes[left_id] = leafs[begin];

-            nodes[right_id] = leafs[begin + 1];

+            temp_nodes[left_id] = leafs[begin];

+            temp_nodes[right_id] = leafs[begin + 1];

         } else {

-            auto bound = nodes[parent_id].bounding_box;

-            int split_axis = 0;

-            float size = 0;

-

-            // Find largest axis

-            for (size_t id = 0; id < 3; id++) {

-                auto current_size = bound.maximum[id] - bound.minimum[id];

-                if (current_size > size) {

-                    size = current_size;

-                    split_axis = id;

-                }

-            }

+            int32_t split_axis = find_split_axis(temp_nodes[parent_id].bounding_box);

 

             std::sort(leafs.begin() + begin, leafs.begin() + end,

                 [&](const bvh_node& a, const bvh_node& b) {

@@ -115,28 +165,35 @@ private:
                 }

             );

 

-            float split_axis_pos = (bound.maximum.x + bound.minimum.x) * 0.5f;

-            int mid = end - 1;

+            temp_nodes[left_id].bounding_box = compute_bounds(begin, begin + (count / 2));

+            temp_nodes[right_id].bounding_box = compute_bounds(begin + (count / 2), end);

+

+            subdivide(left_id, begin, begin + (count / 2));

+            subdivide(right_id, begin + (count / 2), end);

+        }

+    }

+

+    void set_depth_first_order() {

+        int32_t df_index = 0;

+        depth_first_order(0, -1, df_index);

+    }

 

-            for (size_t i = begin + 1; i < end; i++) {

-                auto leaf = leafs[i];

-                if (spheres[leaf.sphere_id].center[split_axis] >= split_axis_pos) {

-                    mid = i;

-                    break;

-                }

-            }

 

-            nodes[left_id].bounding_box = compute_bounds(begin, mid);

-            nodes[right_id].bounding_box = compute_bounds(mid, end);

+    void depth_first_order(int32_t id, int32_t next_id, int32_t &new_id) {

+        auto &node = temp_nodes[id];

+        node.next_id = next_id;

+        node.df_id = new_id++;

 

-            subdivide(left_id, begin, mid);

-            subdivide(right_id, mid, end);

+        if (node.left_id > 0) {

+            depth_first_order(node.left_id, node.left_id + 1, new_id);

+            depth_first_order(node.left_id + 1, next_id, new_id);

         }

     }

 

 public:

     std::vector<bvh_node> nodes;

-    std::vector<bvh_node> leafs;

+    std::vector<temp_node> temp_nodes;

+    std::vector<temp_node> leafs;

     sphere* spheres;

     uint32_t next_node_id = 0;

 };