From be5f1133bff5d4c551e2702211acb155d8819fd0 Mon Sep 17 00:00:00 2001
From: ladevieq <ladevie.quentin@gmail.com>
Date: Mon, 29 Mar 2021 22:25:29 +0200
Subject: BVH simple implementation

---
 include/aabb.hpp     | 23 ++++++++++++++++++----
 include/bvh-node.hpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 include/sphere.hpp   | 10 ++++++++--
 include/utils.hpp    |  7 +++++++
 include/vec3.hpp     |  1 +
 5 files changed, 89 insertions(+), 6 deletions(-)
 create mode 100644 include/bvh-node.hpp

(limited to 'include')

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;
-- 
cgit v1.3