1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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);
};
|
