Simulant  21.12-194
A portable game engine for Windows, OSX, Linux, Dreamcast, and PSP
loose_octree.h
1 #pragma once
2 
3 #include <cstdint>
4 #include "../../math/aabb.h"
5 #include "../../frustum.h"
6 #include "../../generic/check_signature.h"
7 
8 namespace smlt {
9 
10 namespace _loose_octree {
11  static constexpr int32_t ipow(int32_t base, int32_t exp, int32_t result = 1) {
12  return exp < 1 ? result : ipow(base * base, exp / 2, (exp % 2) ? result * base : result);
13  }
14 }
15 
16 /*
17  * Fast loose-octree implementation with O(1) insertions, built on a linear
18  * array for good cache locality.
19  *
20  * TreeData is a structure which contains data needed across the whole tree,
21  * this may usually contain the vertex data for the mesh being inserted.
22  *
23  * NodeData is a structure for storing data on the individual nodes, this is usually
24  * index data for the mesh.
25  */
26 
27 typedef uint8_t Level;
28 typedef uint16_t GridCoord;
29 
30 template<typename TreeData, typename NodeData>
31 class Octree {
32 public:
33  struct Node {
34  Level level = 0;
35  GridCoord grid[3] = {0, 0, 0};
36  NodeData* data = nullptr;
37  uint32_t child_indexes[8];
38 
39  Vec3 centre;
40  float size;
41  };
42 
43  using TraverseCallback = void(Octree::Node*);
44 
45  typedef TreeData tree_data_type;
46  typedef NodeData node_data_type;
47 
48  Octree(const AABB& bounds, uint8_t max_level_count=4, std::shared_ptr<TreeData> tree_data=std::shared_ptr<TreeData>()):
49  tree_data_(tree_data),
50  root_width_(bounds.max_dimension()),
51  bounds_(bounds),
52  centre_(bounds_.centre()) {
53 
54  /* Make sure the bounds are square */
55  float maxd = root_width_;
56  auto halfd = maxd / 2.0f;
57 
58  auto half = Vec3(halfd, halfd, halfd);
59  bounds_.set_min(centre_ - half);
60  bounds_.set_max(centre_ + half);
61 
62  /* Grow the tree to whatever size we passed in */
63  grow(max_level_count);
64  }
65 
66  virtual ~Octree() {
67  /* Make sure we delete the node data */
68  for(auto& node: nodes_) {
69  delete node.data;
70  node.data = nullptr;
71  }
72  }
73 
74  bool is_leaf(Node& node) const {
75  return node.level == (levels_ - 1);
76  }
77 
78  Octree::Node* find_destination_for_sphere(const Vec3& centre, float radius) {
79  auto diameter = radius * 2;
80  auto level_and_node_width = level_for_width(diameter);
81 
82  /* Calculate the cell index to insert the sphere */
83  auto half_width = root_width_ * 0.5f;
84 
85 #ifndef NDEBUG
86  const float E = 0.001f;
87 #endif
88  assert(almost_lequal(centre.x, bounds_.max().x, E) && almost_gequal(centre.x, bounds_.min().x, E));
89  assert(almost_lequal(centre.y, bounds_.max().y, E) && almost_gequal(centre.y, bounds_.min().y, E));
90  assert(almost_lequal(centre.z, bounds_.max().z, E) && almost_gequal(centre.z, bounds_.min().z, E));
91 
92  auto x = (GridCoord) ((centre.x + half_width - centre_.x) / level_and_node_width.second);
93  auto y = (GridCoord) ((centre.y + half_width - centre_.y) / level_and_node_width.second);
94  auto z = (GridCoord) ((centre.z + half_width - centre_.z) / level_and_node_width.second);
95 
96  assert(x >= 0);
97  assert(y >= 0);
98  assert(z >= 0);
99 
100  auto level_width = _loose_octree::ipow(2, level_and_node_width.first);
101  assert(x <= level_width);
102  assert(y <= level_width);
103  assert(z <= level_width);
104 
105  /* This handles the case that the center was on the cusp of the cell
106  * in which case the above calculation will result in an out of range
107  * index */
108  x = std::min<GridCoord>(x, level_width - 1);
109  y = std::min<GridCoord>(y, level_width - 1);
110  z = std::min<GridCoord>(z, level_width - 1);
111 
112  auto idx = calc_index(level_and_node_width.first, x, y, z);
113  assert(idx < nodes_.size());
114 
115  return &nodes_[idx];
116  }
117 
118  Octree::Node* find_destination_for_triangle(const Vec3* vertices) {
119  /*
120  * Return the node that this triangle should be
121  * inserted into (the actual insertion won't happen as that's implementation specific
122  * depending on the NodeData).
123  */
124 
125  AABB bounds(vertices, 3);
126  auto centre = bounds.centre();
127  auto radius = bounds.max_dimension() / 2.0f;
128  return find_destination_for_sphere(centre, radius);
129  }
130 
131  void traverse(std::function<void (Octree::Node*)> cb) {
132  if(nodes_.empty()) {
133  return;
134  }
135 
136  std::function<void (Octree::Node&)> visitor = [&](Octree::Node& node) {
137  cb(&node);
138 
139  if(!is_leaf(node)) {
140  for(auto child: node.child_indexes) {
141  assert(child < nodes_.size());
142  visitor(nodes_[child]);
143  }
144  }
145  };
146 
147  visitor(nodes_[0]);
148  }
149 
150  template<typename Callback>
151  void traverse_visible(const Frustum& frustum, const Callback& cb) {
152  check_signature<Callback, TraverseCallback>();
153 
154  if(nodes_.empty()) {
155  return;
156  }
157 
158  _visible_visitor(frustum, cb, nodes_[0]);
159  }
160 
161  AABB bounds() const { return bounds_; }
162  TreeData* data() const { return tree_data_.get(); }
163 private:
164  template<typename Callback>
165  void _visible_visitor(const Frustum& frustum, const Callback& callback, Octree::Node& node) {
166  if(frustum.intersects_cube(node.centre, node.size * 2.0f)) {
167  callback(&node);
168 
169  if(!is_leaf(node)) {
170  for(auto child: node.child_indexes) {
171  assert(child < nodes_.size());
172  _visible_visitor(frustum, callback, nodes_[child]);
173  }
174  }
175  }
176  }
177 
178  std::pair<Level, float> level_for_width(float obj_width) {
179  /*
180  * Given the diameter of the object
181  * this returns the level the object will fit, and the node width at that level
182  *
183  * I *know* there's a non-iterative way to calculate this, so if you know, let me know!
184  */
185 
186  assert(obj_width <= root_width_);
187 
188  if(obj_width > root_width_) {
189  // Should never happen, but this is the safest thing to do if it does
190  return std::make_pair(0, root_width_);
191  }
192 
193  auto node_width = root_width_;
194  Level depth = 0;
195 
196  while(node_width >= obj_width) {
197  ++depth;
198  node_width *= 0.5f;
199 
200  if(depth == levels_) {
201  break;
202  }
203  }
204 
205  assert(depth >= 1);
206 
207  // Off-by-one
208  return std::make_pair(depth - 1, node_width * 2);
209  }
210 
211  void calc_bounds(Octree::Node& node) const {
212  auto grid_width = _loose_octree::ipow(2, node.level);
213  auto cell_width = bounds_.max_dimension() / grid_width;
214 
215  Vec3 min(node.grid[0] * cell_width, node.grid[1] * cell_width, node.grid[2] * cell_width);
216  min += bounds_.min();
217 
218  float hw = cell_width * 0.5f;
219  node.centre = min + Vec3(hw, hw, hw);
220  node.size = cell_width;
221  }
222 
223  static uint32_t calc_base(uint8_t level) {
224  if(level == 0) return 0;
225  if(level == 1) return 1;
226  return calc_base(level - 1) + _loose_octree::ipow(_loose_octree::ipow(2, level - 1), 3);
227  }
228 
229  static uint32_t calc_index(Level k, GridCoord x, GridCoord y, GridCoord z) {
230  auto level_base = calc_base(k);
231  auto level_width = _loose_octree::ipow(2, k);
232 
233  assert(x < level_width);
234  assert(y < level_width);
235  assert(z < level_width);
236 
237  auto idx = x + level_width * y + level_width * level_width * z;
238  return level_base + idx;
239  }
240 
241  static void calc_child_indexes(Octree::Node& node) {
242  uint8_t count = 0;
243 
244  for(uint32_t z = 0; z <= 1; ++z) {
245  for(uint32_t y = 0; y <= 1; ++y) {
246  for(uint32_t x = 0; x <= 1; ++x) {
247  node.child_indexes[count++] = calc_index(
248  node.level + 1,
249  2 * node.grid[0] + x,
250  2 * node.grid[1] + y,
251  2 * node.grid[2] + z
252  );
253  }
254  }
255  }
256  }
257 
258  void grow(uint8_t required_levels) {
259 
260  auto required_nodes = 0;
261  for(uint8_t i = 0; i < required_levels; ++i) {
262  auto nodes_across = _loose_octree::ipow(2, i);
263  required_nodes += _loose_octree::ipow(nodes_across, 3);
264  }
265 
266  levels_ = required_levels;
267  nodes_.resize(required_nodes, Octree::Node());
268 
269  for(auto k = 0; k < levels_; ++k) {
270  auto nodes_across = _loose_octree::ipow(2, k);
271 
272  for(GridCoord z = 0; z < nodes_across; ++z) {
273  for(GridCoord y = 0; y < nodes_across; ++y) {
274  for(GridCoord x = 0; x < nodes_across; ++x) {
275  auto idx = calc_index(k, x, y, z);
276  assert(idx < nodes_.size());
277 
278  auto& new_node = nodes_[idx];
279 
280  assert(!new_node.data);
281 
282  new_node.grid[0] = x;
283  new_node.grid[1] = y;
284  new_node.grid[2] = z;
285  new_node.level = k;
286  new_node.data = new NodeData();
287 
288  calc_child_indexes(new_node);
289  calc_bounds(new_node);
290  }
291  }
292  }
293  }
294  }
295 
296  std::shared_ptr<TreeData> tree_data_;
297 
298  float root_width_;
299  AABB bounds_;
300  Vec3 centre_;
301 
302  Level levels_ = 0;
303  std::vector<Octree::Node> nodes_;
304 
305  friend class LooseOctreeTests;
306 };
307 
308 }
smlt::Octree
Definition: loose_octree.h:31
smlt::Vec3
Definition: vec3.h:23
half_float::half
Definition: half.hpp:923
smlt::Octree::Node
Definition: loose_octree.h:33
smlt
Definition: animation.cpp:25
half_float::detail::exp
expr exp(half arg)
Definition: half.hpp:2160
smlt::AABB
Definition: aabb.h:22