From 4a6aae00f61814871f48c2c6a2b86f1b57b206ba Mon Sep 17 00:00:00 2001
From: ladevieq <ladevie.quentin@gmail.com>
Date: Tue, 25 May 2021 23:23:44 +0200
Subject: Fix BVH traversal and use PCG instead of wang hash

---
 include/bvh-node.hpp | 50 --------------------------------------------------
 shaders/compute.comp | 35 +++++++++++++++++++++--------------
 2 files changed, 21 insertions(+), 64 deletions(-)

diff --git a/include/bvh-node.hpp b/include/bvh-node.hpp
index 3a4ac4b..660271a 100644
--- a/include/bvh-node.hpp
+++ b/include/bvh-node.hpp
@@ -12,40 +12,10 @@ 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;
 
         int32_t left_id    = -1;
-
         int32_t sphere_id   = -1;
         uint32_t padding[2];
 };
@@ -98,26 +68,6 @@ public:
         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;
-            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;
-        }
-    }
-
 private:
 
     aabb compute_bounds(uint32_t begin, uint32_t end) {
diff --git a/shaders/compute.comp b/shaders/compute.comp
index 3090e3b..c43d48b 100644
--- a/shaders/compute.comp
+++ b/shaders/compute.comp
@@ -91,20 +91,17 @@ vec3 at(ray r, float t) {
     return r.origin + r.direction * t;
 }
 
-
-uint wang_hash(inout uint seed)
+uint pcg_hash(inout uint seed)
 {
-    seed = (seed ^ 61) ^ (seed >> 16);
-    seed *= 9;
-    seed = seed ^ (seed >> 4);
-    seed *= 0x27d4eb2d;
-    seed = seed ^ (seed >> 15);
-    return seed;
+    uint state = seed;
+    seed *= 747796405u + 2891336453u;
+    uint word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u;
+    return (word >> 22u) ^ word;
 }
 
 float rand(inout uint seed)
 {
-    return float(wang_hash(seed)) / 4294967296.0;
+    return float(pcg_hash(seed)) / 4294967296.0;
 }
 
 vec3 unit_vec(inout uint seed) {
@@ -203,14 +200,24 @@ bool hit_node(ray r, float min_t, float max_t, out hit_info info) {
     int stack_id = -1;
     int stack[64];
     bvh_node current_node = nodes[0];
+    bool hit = false;
 
     while(true) {
         // Reached a leaf
         if (current_node.sphere_id != -1) {
-            hit_sphere(spheres[current_node.sphere_id], r, min_t, closest_t, temp_info);
-            info = temp_info;
-            closest_t = temp_info.t;
-            continue;
+            if (hit_sphere(spheres[current_node.sphere_id], r, min_t, closest_t, temp_info)) {
+                info = temp_info;
+                closest_t = temp_info.t;
+                hit = true;
+            }
+
+            if (stack_id >= 0) {
+                current_node = nodes[stack[stack_id]];
+                stack_id--;
+                continue;
+            }
+
+            return hit;
         }
 
         bool hit_left = hit_aabb(nodes[current_node.left].bb, r, min_t, max_t);
@@ -240,7 +247,7 @@ bool hit_node(ray r, float min_t, float max_t, out hit_info info) {
 bool hit_spheres(ray r, float min_t, float max_t, out hit_info info) {
     float closest_t = max_t;
     hit_info temp_info;
-    bool hit = false;
+    // bool hit = false;
     // for (uint sphere_index = 0; sphere_index <= spheres_count; sphere_index++) {
     //     if (spheres[sphere_index].radius > 0.0 && hit_sphere(spheres[sphere_index], r, min_t, closest_t, temp_info)) {
     //         info = temp_info;
-- 
cgit v1.3