BVH simple implementation

10 files changed, 155 insertions, 21 deletions

diff --git a/include/aabb.hpp b/include/aabb.hpp
index 9ec1f3f..18f6d09 100644
--- a/include/aabb.hpp
+++ b/include/aabb.hpp
@@ -3,11 +3,26 @@
 

 #include "vec3.hpp"

 

-class AABB {

-    AABB(vec3 min_point, vec3 max_point): minimum(min_point), maximum(max_point) {}

+class aabb {

+    public:

+        aabb() = default;

+        aabb(vec3 min_point, vec3 max_point): minimum(min_point), maximum(max_point) {}

+        aabb(vec3 position, float radius): minimum(position - vec3(radius)), maximum(position + vec3(radius)) {}

 

-    vec3 minimum;

-    vec3 maximum;

+        static aabb surrounding_box(aabb box0, aabb box1) {

+            point3 min_point(fmin(box0.minimum.x, box1.minimum.x),

+                         fmin(box0.minimum.y, box1.minimum.y),

+                         fmin(box0.minimum.z, box1.minimum.z));

+

+            point3 max_point(fmax(box0.maximum.x, box1.maximum.x),

+                       fmax(box0.maximum.y, box1.maximum.y),

+                       fmax(box0.maximum.z, box1.maximum.z));

+

+            return aabb(min_point, max_point);

+        }

+

+        vec3 minimum;

+        vec3 maximum;

 };

 

 #endif // !__AABB_HPP_

diff --git a/include/bvh-node.hpp b/include/bvh-node.hpp
new file mode 100644
index 0000000..78780e7
--- /dev/null
+++ b/include/bvh-node.hpp
@@ -0,0 +1,54 @@
+#ifndef __BVH_NODE_HPP_

+#define __BVH_NODE_HPP_

+

+#include <vector>

+#include <algorithm>

+

+#include "aabb.hpp"

+#include "sphere.hpp"

+

+class bvh_node {

+    public:

+        bvh_node() = default;

+        bvh_node(sphere& sphere, int32_t sphere_id): bounding_box(sphere.bounding_box), sphere_id(sphere_id){}

+        bvh_node(sphere* spheres, size_t start, size_t end, bvh_node* root_node, int32_t id) {

+            left_node_id = id * 2;

+            right_node_id = id * 2 + 1;

+

+            bvh_node left, right;

+

+            // int axis = randi(0, 2);

+            // auto comparator = (axis == 0) ? box_x_comparator : (axis == 1) ? box_y_comparator : box_z_comparator;

+

+            size_t span = end - start;

+

+            if (span == 1) {

+                root_node[left_node_id - 1] = root_node[right_node_id - 1] = { spheres[start], (int32_t)start };

+            } else if (span == 2) {

+                // if (comparator(spheres[start], spheres[start + 1]) {

+                    root_node[left_node_id - 1] = { spheres[start], (int32_t)start };

+                    root_node[right_node_id - 1] = { spheres[start], (int32_t)start + 1 };

+                // } else {

+                //     root_node[left_node_id - 1] = { spheres[start + 1], start + 1 };

+                //     root_node[right_node_id - 1] = { spheres[start], start };

+                // }

+            } else {

+                uint32_t mid = start + span / 2;

+                root_node[left_node_id - 1] = { spheres, start, mid, root_node, left_node_id };

+                root_node[right_node_id - 1] = { spheres, mid, end, root_node, right_node_id };

+            }

+

+            bounding_box = aabb::surrounding_box(root_node[left_node_id - 1].bounding_box, root_node[right_node_id -1].bounding_box);

+        }

+

+        aabb bounding_box;

+

+        // Store sphere id ?

+        int32_t left_node_id    = -1;

+        int32_t right_node_id   = -1;

+

+        int32_t sphere_id       = -1;

+        uint32_t padding;

+};

+

+#endif // !__BVH_NODE_HPP_

diff --git a/include/sphere.hpp b/include/sphere.hpp
index a338f2e..28bb0bc 100644
--- a/include/sphere.hpp
+++ b/include/sphere.hpp
@@ -1,16 +1,22 @@
 #ifndef __SPHERE_HPP_
 #define __SPHERE_HPP_
 
+#include "aabb.hpp"
 #include "material.hpp"
 
-struct sphere{
+struct sphere {
     sphere() = default;
-    sphere(point3 center, material material, float radius);
+    sphere(point3 center, material material, float radius)
+        : center(center), radius(radius), mat(material),
+            bounding_box(center, radius)
+    {}
 
     point3 center;
 
     material mat;
 
+    aabb bounding_box;
+
     float radius;
     float padding[3];
 };
diff --git a/include/utils.hpp b/include/utils.hpp
index 3821d20..8d46821 100644
--- a/include/utils.hpp
+++ b/include/utils.hpp
@@ -8,6 +8,7 @@
 #include "vec3.hpp"
 #include "sphere.hpp"
 #include "camera.hpp"
+#include "bvh-node.hpp"
 
 struct input_data {
     color sky_color;
@@ -20,6 +21,7 @@ struct input_data {
     vec3 random_in_sphere[1000];
 
     sphere spheres[512];
+    bvh_node nodes[1024];
 
     uint32_t max_bounce;
     uint32_t samples_per_pixel;
@@ -49,6 +51,11 @@ inline float randd() {
 inline float randd(float min, float max) {
     return min + randd() * (max - min);
 }
+
+inline int32_t randi(int32_t min, int32_t max) {
+    return static_cast<int32_t>(randd(min, max + 1));
+}
+
 inline float clamp(float x, float min, float max) {
     if (x < min) return min;
     if (x > max) return max;
diff --git a/include/vec3.hpp b/include/vec3.hpp
index 112fdf9..39aab6e 100644
--- a/include/vec3.hpp
+++ b/include/vec3.hpp
@@ -7,6 +7,7 @@ class vec3 {
     public:
     vec3();
 
+    vec3(float x);
     vec3(float x, float y, float z);
 
     vec3 operator-() const;
diff --git a/shaders/compute.comp b/shaders/compute.comp
index 3510d52..6f35094 100644
--- a/shaders/compute.comp
+++ b/shaders/compute.comp
@@ -27,18 +27,19 @@ struct hit_info {
     bool front_face;
 };
 
+struct aabb {
+    vec4 min;
+    vec4 max;
+};
+
 struct sphere {
     vec4 position;
     material mat;
+    aabb bb;
     float radius;
     float[3] padding;
 };
 
-struct aabb {
-    vec4 min;
-    vec4 max;
-};
-
 struct camera {
     vec4 position;
 
@@ -54,6 +55,14 @@ struct camera {
     float[3] padding;
 };
 
+struct bvh_node {
+    aabb bb;
+    int left;
+    int right;
+    int sphere_id;
+    uint padding;
+};
+
 layout(set = 0, binding = 0) buffer Inputs {
     vec4 sky_color;
     vec4 ground_color;
@@ -64,6 +73,7 @@ layout(set = 0, binding = 0) buffer Inputs {
     vec4[1000] random_in_sphere;
 
     sphere[512] spheres;
+    bvh_node[1024] nodes;
 
     uint max_bounce;
     uint samples_per_pixel;
@@ -116,6 +126,45 @@ bool hit_aabb(aabb b, ray r, float min_t, float max_t) {
     return true;
 }
 
+bool hit_node(bvh_node node, ray r, float min_t, float max_t, out hit_info info) {
+    if (!hit_aabb(node.bb, r, min_t, max_t)) {
+        return false;
+    }
+
+    int stack_id = -1;
+    int stack[64];
+    bvh_node current_node = node;
+
+    while(true) {
+        bool hit_left = hit_aabb(nodes[current_node.left - 1].bb, r, min_t, max_t);
+        bool hit_right = hit_aabb(nodes[current_node.right - 1].bb, r, min_t, max_t);
+
+        if (hit_left && hit_right) {
+            stack_id++;
+            stack[stack_id] = current_node.left - 1;
+
+            current_node = nodes[current_node.right - 1];
+        } else if (hit_left) {
+            current_node = nodes[current_node.left - 1];
+        } else if (hit_right) {
+            current_node = nodes[current_node.right - 1];
+        } else {
+            if (stack_id >= 0) {
+                current_node = nodes[stack[stack_id]];
+                stack_id--;
+            } else {
+                return false;
+            }
+        }
+
+        // Reached a leaf
+        if (current_node.left == -1 && current_node.right == -1) {
+            return true;
+        }
+    }
+
+}
+
 bool hit_sphere(sphere s, ray r, float min_t, float max_t, out hit_info info) {
     vec3 origin_center = r.origin - s.position.xyz;
 
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 6ebef73..048a159 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -14,7 +14,6 @@ add_executable(
     main.cpp
     vec3.cpp
     color.cpp
-    sphere.cpp
     camera.cpp
     vulkan-loader.cpp
     utils.cpp
diff --git a/src/sphere.cpp b/src/sphere.cpp
deleted file mode 100644
index 7ac4185..0000000
--- a/src/sphere.cpp
+++ /dev/null
@@ -1,5 +0,0 @@
-#include "sphere.hpp"
-
-sphere::sphere(point3 center, material material, float radius)
-    : center(center), radius(radius), mat(material)
-{}
diff --git a/src/utils.cpp b/src/utils.cpp
index 5ed2c17..18b2580 100644
--- a/src/utils.cpp
+++ b/src/utils.cpp
@@ -7,9 +7,10 @@
 #include "material.hpp"
 
 std::vector<uint8_t> get_shader_code(const char* path) {
-    FILE* f = fopen(path, "rb");
+    FILE* f = nullptr;
+    errno_t err = fopen_s(&f, path, "rb");
 
-    if (f == nullptr) {
+    if (err != 0) {
         std::cerr << "Cannot open compute shader file !" << std::endl;
         return {};
     }
@@ -39,7 +40,8 @@ std::vector<uint8_t> get_shader_code(std::string& path) {
 color ground_color { 1.0, 1.0, 1.0 };
 color sky_color { 0.5, 0.7, 1.0 };
 
-void random_scene(sphere *world) {
+// Return the number of instantiated spheres
+uint32_t random_scene(sphere *world) {
     material ground_material = { { 0.5, 0.5, 0.5 } };
     ground_material.type = MATERIAL_TYPE::LAMBERTIAN;
     world[0] = sphere{ { 0,-1000,0 }, ground_material, 1000 };
@@ -91,6 +93,8 @@ void random_scene(sphere *world) {
     material3.fuzz = 0.0;
     material3.type = MATERIAL_TYPE::METAL;
     world[world_sphere_index + 2] = { { 4, 1, 0 }, material3, 1.0 };
+
+    return world_sphere_index + 2;
 }
 
 struct input_data create_inputs(uint32_t width, uint32_t height, uint32_t samples_per_pixel) {
@@ -112,6 +116,7 @@ struct input_data create_inputs(uint32_t width, uint32_t height, uint32_t sample
         .cam = camera,
 
         .spheres = {},
+        .nodes = {},
 
         .max_bounce = max_depth,
         .samples_per_pixel = samples_per_pixel,
@@ -138,7 +143,9 @@ struct input_data create_inputs(uint32_t width, uint32_t height, uint32_t sample
     }
 
     // World hittable objects
-    random_scene(inputs.spheres);
+    uint32_t spheres_count = random_scene(inputs.spheres);
+
+    inputs.nodes[0] = { inputs.spheres, 0, spheres_count, inputs.nodes, 1 };
 
     return inputs;
 }
diff --git a/src/vec3.cpp b/src/vec3.cpp
index afc4c97..8e27a98 100644
--- a/src/vec3.cpp
+++ b/src/vec3.cpp
@@ -5,6 +5,7 @@
 
 vec3::vec3(): x(0.0), y(0.0), z(0.0) {}
 
+vec3::vec3(float x): x(x), y(x), z(x) {}
 vec3::vec3(float x, float y, float z): x(x), y(y), z(z) {}
 
 vec3 vec3::operator-() const {