BVH simple implementation

5 files changed, 89 insertions, 6 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;