1 files changed, 69 insertions, 0 deletions
diff --git a/src/3d/bvh.h b/src/3d/bvh.h
new file mode 100644
index 0000000..97e9a06
--- /dev/null
+++ b/src/3d/bvh.h
@@ -0,0 +1,69 @@
+// This file is part of the 64k demo project.
+// It defines the Bounding Volume Hierarchy (BVH) for scene acceleration.
+
+#pragma once
+
+#include "3d/object.h"
+#include "util/mini_math.h"
+#include <cstdint>
+#include <vector>
+
+struct BVHNode {
+  float min_x, min_y, min_z;
+  int32_t left_idx; // If < 0, this is a leaf node.
+
+  float max_x, max_y, max_z;
+  int32_t right_idx; // If leaf, this holds the object_index.
+};
+
+struct AABB {
+  vec3 min;
+  vec3 max;
+
+  AABB() : min(1e10f, 1e10f, 1e10f), max(-1e10f, -1e10f, -1e10f) {
+  }
+  AABB(vec3 min, vec3 max) : min(min), max(max) {
+  }
+
+  void expand(vec3 p) {
+    if (p.x < min.x)
+      min.x = p.x;
+    if (p.y < min.y)
+      min.y = p.y;
+    if (p.z < min.z)
+      min.z = p.z;
+    if (p.x > max.x)
+      max.x = p.x;
+    if (p.y > max.y)
+      max.y = p.y;
+    if (p.z > max.z)
+      max.z = p.z;
+  }
+
+  void expand(const AABB& other) {
+    expand(other.min);
+    expand(other.max);
+  }
+
+  bool intersects(const AABB& other) const {
+    return (min.x <= other.max.x && max.x >= other.min.x) &&
+           (min.y <= other.max.y && max.y >= other.min.y) &&
+           (min.z <= other.max.z && max.z >= other.min.z);
+  }
+
+  vec3 center() const {
+    return (min + max) * 0.5f;
+  }
+};
+
+class BVH {
+ public:
+  std::vector<BVHNode> nodes;
+
+  void query(const AABB& box, std::vector<int>& out_indices) const;
+};
+
+class BVHBuilder {
+ public:
+  static void build(BVH& out_bvh, const std::vector<Object3D>& objects);
+};