4 #include "../../math/aabb.h"
5 #include "../../frustum.h"
6 #include "../../generic/check_signature.h"
10 static constexpr int64_t ipow(int64_t base,
int exp, int64_t result = 1) {
11 return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
25 typedef uint8_t Level;
26 typedef uint16_t GridCoord;
28 template<
typename TreeData,
typename NodeData>
33 GridCoord grid[2] = {0, 0};
34 NodeData* data =
nullptr;
35 uint32_t child_indexes[4];
43 typedef TreeData tree_data_type;
44 typedef NodeData node_data_type;
46 Quadtree(
const AABB& bounds, uint8_t max_level_count=4, std::shared_ptr<TreeData> tree_data=std::shared_ptr<TreeData>()):
47 tree_data_(tree_data),
48 root_width_(bounds.max_dimension()),
50 center_(bounds_.center()) {
53 float maxd = root_width_;
54 auto halfd = maxd / 2.0f;
60 grow(max_level_count);
65 for(
auto& node: nodes_) {
71 bool is_leaf(Node& node)
const {
72 return node.level == (levels_ - 1);
75 Quadtree::Node* find_destination_for_sphere(
const Vec3& center,
float radius) {
76 auto diameter = radius * 2.0f;
77 auto level_and_node_width = level_for_width(diameter);
80 auto half_width = root_width_ * 0.5f;
82 assert(center.x <= bounds_.max().x && center.x >= bounds_.min().x);
83 assert(center.z <= bounds_.max().z && center.z >= bounds_.min().z);
85 auto x = (GridCoord) ((center.x + half_width - center_.x) / level_and_node_width.second);
86 auto z = (GridCoord) ((center.z + half_width - center_.z) / level_and_node_width.second);
91 auto level_width = ipow(2, level_and_node_width.first);
92 assert(x <= level_width);
93 assert(z <= level_width);
98 x = std::min<GridCoord>(x, level_width - 1);
99 z = std::min<GridCoord>(z, level_width - 1);
101 auto idx = calc_index(level_and_node_width.first, x, z);
102 assert(idx < nodes_.size());
107 Quadtree::Node* find_destination_for_triangle(
const Vec3* vertices) {
114 AABB bounds(vertices, 3);
115 auto center = bounds.center();
116 auto radius = bounds.max_dimension() / 2.0f;
117 return find_destination_for_sphere(center, radius);
120 void traverse(std::function<
void (Quadtree::Node*)> cb) {
125 std::function<void (Quadtree::Node&)> visitor = [&](Quadtree::Node& node) {
129 for(
auto child: node.child_indexes) {
130 assert(child < nodes_.size());
131 visitor(nodes_[child]);
139 template<
typename Callback>
140 void traverse_visible(
const Frustum& frustum,
const Callback& cb) {
141 check_signature<Callback, TraverseCallback>();
147 _visible_visitor(frustum, cb, nodes_[0]);
150 AABB bounds()
const {
return bounds_; }
152 TreeData* data()
const {
return tree_data_.get(); }
154 template<
typename Callback>
155 void _visible_visitor(
const Frustum& frustum,
const Callback& callback, Quadtree::Node& node) {
156 if(frustum.intersects_cube(node.center, node.size * 2.0f)) {
160 for(
auto child: node.child_indexes) {
161 assert(child < nodes_.size());
162 _visible_visitor(frustum, callback, nodes_[child]);
168 std::pair<Level, float> level_for_width(
float obj_width) {
176 assert(obj_width <= root_width_);
178 if(obj_width > root_width_) {
180 return std::make_pair(0, root_width_);
183 auto node_width = root_width_;
186 while(node_width >= obj_width) {
190 if(depth == levels_) {
198 return std::make_pair(depth - 1, node_width * 2);
201 void calc_bounds(Quadtree::Node& node)
const {
202 auto grid_width = ipow(2, node.level);
203 auto cell_width = bounds_.max_dimension() / grid_width;
205 Vec3 min(node.grid[0] * cell_width, 0, node.grid[1] * cell_width);
206 min += bounds_.min();
208 float hw = cell_width * 0.5f;
209 node.center = min + Vec3(hw, hw, hw);
210 node.size = cell_width;
213 static uint32_t calc_base(uint8_t level) {
214 if(level == 0)
return 0;
215 if(level == 1)
return 1;
216 return calc_base(level - 1) + ipow(ipow(2, level - 1), 2);
219 static uint32_t calc_index(Level k, GridCoord x, GridCoord z) {
220 auto level_base = calc_base(k);
221 auto level_width = ipow(2, k);
223 assert(x < level_width);
224 assert(z < level_width);
226 auto idx = x + level_width * z;
227 return level_base + idx;
230 static void calc_child_indexes(Quadtree::Node& node) {
232 for(uint32_t z = 0; z <= 1; ++z) {
233 for(uint32_t x = 0; x <= 1; ++x) {
234 node.child_indexes[count++] = calc_index(
236 2 * node.grid[0] + x,
243 void grow(uint8_t required_levels) {
245 auto required_nodes = 0;
246 for(uint8_t i = 0; i < required_levels; ++i) {
247 auto nodes_across = ipow(2, i);
248 required_nodes += ipow(nodes_across, 2);
251 levels_ = required_levels;
252 nodes_.resize(required_nodes, Quadtree::Node());
254 for(
auto k = 0; k < levels_; ++k) {
255 auto nodes_across = ipow(2, k);
257 for(GridCoord z = 0; z < nodes_across; ++z) {
258 for(GridCoord x = 0; x < nodes_across; ++x) {
259 auto idx = calc_index(k, x, z);
260 assert(idx < nodes_.size());
261 auto& new_node = nodes_[idx];
263 assert(!new_node.data);
265 new_node.grid[0] = x;
266 new_node.grid[1] = z;
268 new_node.data =
new NodeData();
270 calc_child_indexes(new_node);
271 calc_bounds(new_node);
277 std::shared_ptr<TreeData> tree_data_;
284 std::vector<Quadtree::Node> nodes_;
286 friend class LooseQuadtreeTests;