From df7dc0f1069e6ed8ea24c152eb4c3a5a97e80b91 Mon Sep 17 00:00:00 2001 From: ladevieq Date: Sat, 19 Jun 2021 17:54:16 +0200 Subject: Split on the largest axis on BVH generation --- include/aabb.hpp | 5 +-- include/bvh-node.hpp | 90 ++++++++++++++++++++++++++++++++-------------------- include/vec3.hpp | 2 ++ shaders/compute.comp | 17 ++-------- src/utils.cpp | 56 ++++++++++++++++---------------- src/vec3.cpp | 14 ++++++++ 6 files changed, 104 insertions(+), 80 deletions(-) diff --git a/include/aabb.hpp b/include/aabb.hpp index c5a7b86..76a6872 100644 --- a/include/aabb.hpp +++ b/include/aabb.hpp @@ -3,6 +3,7 @@ #include "vec3.hpp" #include +#include class aabb { public: @@ -22,8 +23,8 @@ class aabb { return aabb(min_point, max_point); } - vec3 minimum; - vec3 maximum; + vec3 minimum = vec3(std::numeric_limits::max()); + vec3 maximum = vec3(std::numeric_limits::min()); }; #endif // !__AABB_HPP_ diff --git a/include/bvh-node.hpp b/include/bvh-node.hpp index 660271a..2affa38 100644 --- a/include/bvh-node.hpp +++ b/include/bvh-node.hpp @@ -3,7 +3,6 @@ #include #include -#include #include "aabb.hpp" #include "sphere.hpp" @@ -24,10 +23,12 @@ class bvh { public: void build(sphere* spheres, uint32_t spheres_count) { nodes = std::vector(2 * spheres_count - 1); - boxes = std::vector(spheres_count); + leafs = std::vector(spheres_count); + this->spheres = spheres; - for (uint32_t sphere_id = 0; sphere_id < spheres_count; sphere_id++) { - boxes[sphere_id] = spheres[sphere_id].bounding_box; + for (uint32_t id = 0; id < spheres_count; id++) { + leafs[id].bounding_box = spheres[id].bounding_box; + leafs[id].sphere_id = id; } nodes[0] = bvh_node(); @@ -43,11 +44,9 @@ public: std::cout << "digraph bvh {" << std::endl; std::cout << "\t 0"; - // preorder(nodes[0].left_id, nodes[0].sphere_id); traverse(nodes[0].left_id); std::cout << "\t 0"; - // preorder(nodes[0].left_id + 1, nodes[0].sphere_id); traverse(nodes[0].left_id + 1); std::cout << "}" << std::endl; @@ -74,50 +73,71 @@ private: aabb global_box = aabb(); for (uint32_t box_id = begin; box_id < end; box_id++) { - global_box = aabb::surrounding_box(global_box, boxes[box_id]); + auto leaf = leafs[box_id]; + global_box = aabb::surrounding_box(global_box, spheres[leaf.sphere_id].bounding_box); } return global_box; } void subdivide(uint32_t parent_id, uint32_t begin, uint32_t end) { - if ((end - begin) == 2) { - auto left_id = ++next_node_id; - auto right_id = ++next_node_id; - - nodes[parent_id].left_id = left_id; + size_t count = end - begin; + if (count == 1) { + nodes[parent_id] = leafs[begin]; + return; + } - nodes[left_id] = bvh_node(); - nodes[right_id] = bvh_node(); + auto left_id = ++next_node_id; + auto right_id = ++next_node_id; - nodes[left_id].bounding_box = boxes[begin]; - nodes[right_id].bounding_box = boxes[begin + 1]; + nodes[parent_id].left_id = left_id; - nodes[left_id].sphere_id = begin; - nodes[right_id].sphere_id = begin + 1; - } else if ((end - begin) == 1) { - nodes[parent_id].bounding_box = boxes[begin]; - nodes[parent_id].sphere_id = begin; + if (count == 2) { + nodes[left_id] = leafs[begin]; + nodes[right_id] = leafs[begin + 1]; } else { - auto left_id = ++next_node_id; - auto right_id = ++next_node_id; - - nodes[parent_id].left_id = left_id; - - nodes[left_id] = bvh_node(); - nodes[right_id] = bvh_node(); - - nodes[left_id].bounding_box = compute_bounds(begin, begin + ((end - begin) / 2) + 1); - nodes[right_id].bounding_box = compute_bounds(begin + ((end - begin) / 2) + 1, end); - - subdivide(left_id, begin, begin + ((end - begin) / 2) + 1); - subdivide(right_id, begin + ((end - begin) / 2) + 1, end); + 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; + } + } + + std::sort(leafs.begin() + begin, leafs.begin() + end, + [&](const bvh_node& a, const bvh_node& b) { + return spheres[a.sphere_id].center[split_axis] < spheres[b.sphere_id].center[split_axis]; + } + ); + + float split_axis_pos = (bound.maximum.x + bound.minimum.x) * 0.5f; + int mid = end - 1; + + 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); + + subdivide(left_id, begin, mid); + subdivide(right_id, mid, end); } } public: std::vector nodes; - std::vector boxes; + std::vector leafs; + sphere* spheres; uint32_t next_node_id = 0; }; diff --git a/include/vec3.hpp b/include/vec3.hpp index 39aab6e..6291e30 100644 --- a/include/vec3.hpp +++ b/include/vec3.hpp @@ -18,6 +18,8 @@ class vec3 { vec3& operator/=(float numerator); + float operator[](int axis); + float length() const; float length_sq() const; diff --git a/shaders/compute.comp b/shaders/compute.comp index c43d48b..2c56fbf 100644 --- a/shaders/compute.comp +++ b/shaders/compute.comp @@ -198,7 +198,7 @@ bool hit_node(ray r, float min_t, float max_t, out hit_info info) { } int stack_id = -1; - int stack[64]; + int stack[512]; bvh_node current_node = nodes[0]; bool hit = false; @@ -237,7 +237,7 @@ bool hit_node(ray r, float min_t, float max_t, out hit_info info) { current_node = nodes[stack[stack_id]]; stack_id--; } else { - return false; + return hit; } } } @@ -245,19 +245,6 @@ 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; - // 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; - // closest_t = temp_info.t; - // hit = true; - // } - // } - // - // return hit; - return hit_node(r, min_t, max_t, info); } diff --git a/src/utils.cpp b/src/utils.cpp index 6db101c..a754b1d 100644 --- a/src/utils.cpp +++ b/src/utils.cpp @@ -59,34 +59,34 @@ uint32_t random_scene(sphere *world) { uint32_t world_sphere_index = 1; int32_t spheres_count = 11; - // for (int a = -spheres_count; a < spheres_count; a++) { - // for (int b = -spheres_count; b < spheres_count; b++) { - // auto choose_mat = randd(); - // point3 center(a + 0.9 * randd(), 0.2, b + 0.9 * randd()); - - // if ((center - point3{ 4, 0.2, 0 }).length() > 0.9) { - // material sphere_material = {}; - - // if (choose_mat < 0.8) { - // // diffuse - // sphere_material.albedo = color::random() * color::random(); - // sphere_material.type = MATERIAL_TYPE::LAMBERTIAN; - // } else if (choose_mat < 0.95) { - // // metal - // sphere_material.albedo = color::random(0.5, 1); - // sphere_material.fuzz = randd(0, 0.5); - // sphere_material.type = MATERIAL_TYPE::METAL; - // } else { - // // glass - // sphere_material.ior = 1.5; - // sphere_material.type = MATERIAL_TYPE::DIELECTRIC; - // } - - // world[world_sphere_index] = { center, sphere_material, 0.2 }; - // world_sphere_index++; - // } - // } - // } + for (int a = -spheres_count; a < spheres_count; a++) { + for (int b = -spheres_count; b < spheres_count; b++) { + auto choose_mat = randd(); + point3 center(a + 0.9 * randd(), 0.2, b + 0.9 * randd()); + + if ((center - point3{ 4, 0.2, 0 }).length() > 0.9) { + material sphere_material = {}; + + if (choose_mat < 0.8) { + // diffuse + sphere_material.albedo = color::random() * color::random(); + sphere_material.type = MATERIAL_TYPE::LAMBERTIAN; + } else if (choose_mat < 0.95) { + // metal + sphere_material.albedo = color::random(0.5, 1); + sphere_material.fuzz = randd(0, 0.5); + sphere_material.type = MATERIAL_TYPE::METAL; + } else { + // glass + sphere_material.ior = 1.5; + sphere_material.type = MATERIAL_TYPE::DIELECTRIC; + } + + world[world_sphere_index] = { center, sphere_material, 0.2 }; + world_sphere_index++; + } + } + } material material1 = {}; material1.ior = 1.5; diff --git a/src/vec3.cpp b/src/vec3.cpp index 8e27a98..8f7a720 100644 --- a/src/vec3.cpp +++ b/src/vec3.cpp @@ -1,4 +1,5 @@ #include +#include #include "vec3.hpp" #include "utils.hpp" @@ -40,6 +41,19 @@ vec3& vec3::operator/=(float numerator) { return *this; } +float vec3::operator[](int axis) { + switch (axis) { + case 0: + return x; + case 1: + return y; + case 2: + return z; + default: + return std::numeric_limits::infinity(); + } +} + float vec3::length() const { return sqrt(length_sq()); } -- cgit v1.3