neoGFX
Cross-platform C++ app/game engine
Loading...
Searching...
No Matches
aabb_octree.hpp
Go to the documentation of this file.
1// aabb_octree.hpp
2/*
3 neogfx C++ App/Game Engine
4 Copyright (c) 2015, 2020 Leigh Johnston. All Rights Reserved.
5
6 This program is free software: you can redistribute it and / or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#pragma once
21
22#include <neogfx/neogfx.hpp>
23#include <boost/pool/pool_alloc.hpp>
24#include <neolib/core/vecarray.hpp>
25#include <neolib/core/lifetime.hpp>
26#include <neogfx/core/numerical.hpp>
27#include <neogfx/game/i_ecs.hpp>
28#include <neogfx/game/entity_info.hpp>
29
30namespace neogfx::game
31{
32 template <typename Collider, std::size_t BucketSize = 16, typename Allocator = boost::fast_pool_allocator<Collider>>
33 class aabb_octree
34 {
35 public:
36 typedef Collider collider_type;
37 typedef Allocator allocator_type;
38 typedef typename allocator_type::pointer pointer;
39 typedef typename allocator_type::const_pointer const_pointer;
40 typedef typename allocator_type::reference reference;
41 typedef typename allocator_type::const_reference const_reference;
42 public:
43 typedef const void* const_iterator; // todo
44 typedef void* iterator; // todo
45 private:
46 class node : public neolib::lifetime<>
47 {
48 private:
49 typedef neolib::vecarray<entity_id, BucketSize, -1> entity_list;
50 typedef std::array<std::array<std::array<aabb, 2>, 2>, 2> octants;
51 typedef std::array<std::array<std::array<aabb_2d, 2>, 2>, 2> octants_2d;
52 typedef std::array<std::array<std::array<node*, 2>, 2>, 2> children;
53 private:
54 struct no_parent : std::logic_error { no_parent() : std::logic_error{ "neogfx::aabb_octree::node::no_parent" } {} };
55 struct no_children : std::logic_error { no_children() : std::logic_error{ "neogfx::aabb_octree::node::no_children" } {} };
56 public:
57 node(aabb_octree& aTree, const aabb& aAabb) : iTree{ aTree }, iParent{ nullptr }, iDepth{ 1 }, iAabb{ aAabb }, iChildren {}
58 {
59 iTree.iDepth = std::max(iTree.iDepth, iDepth);
60 populate_octants();
61 }
62 node(const node& aParent, const aabb& aAabb) : iTree{ aParent.iTree }, iParent{ &aParent }, iDepth{ aParent.iDepth + 1 }, iAabb { aAabb }, iChildren{}
63 {
64 iTree.iDepth = std::max(iTree.iDepth, iDepth);
65 populate_octants();
66 }
67 ~node()
68 {
69 set_destroying();
70 if (has_child<0, 0, 0>())
71 remove_child<0, 0, 0>();
72 if (has_child<0, 1, 0>())
73 remove_child<0, 1, 0>();
74 if (has_child<1, 0, 0>())
75 remove_child<1, 0, 0>();
76 if (has_child<1, 1, 0>())
77 remove_child<1, 1, 0>();
78 if (has_child<0, 0, 1>())
79 remove_child<0, 0, 1>();
80 if (has_child<0, 1, 1>())
81 remove_child<0, 1, 1>();
82 if (has_child<1, 0, 1>())
83 remove_child<1, 0, 1>();
84 if (has_child<1, 1, 1>())
85 remove_child<1, 1, 1>();
86 if (has_parent())
87 parent().unsplit(this);
88 }
89 public:
90 bool has_parent() const
91 {
92 return iParent != nullptr;
93 }
94 const node& parent() const
95 {
96 if (has_parent())
97 return *iParent;
98 throw no_parent();
99 }
100 node& parent()
101 {
102 return const_cast<node&>(to_const(*this).parent());
103 }
104 uint32_t depth() const
105 {
106 return iDepth;
107 }
108 const neogfx::aabb& aabb() const
109 {
110 return iAabb;
111 }
112 void add_entity(entity_id aEntity, const collider_type& aCollider)
113 {
114 iTree.iDepth = std::max(iTree.iDepth, iDepth);
115 if (is_split())
116 {
117 if (aabb_intersects(iOctants[0][0][0], aCollider.currentAabb))
118 child<0, 0, 0>().add_entity(aEntity, aCollider);
119 if (aabb_intersects(iOctants[0][1][0], aCollider.currentAabb))
120 child<0, 1, 0>().add_entity(aEntity, aCollider);
121 if (aabb_intersects(iOctants[1][0][0], aCollider.currentAabb))
122 child<1, 0, 0>().add_entity(aEntity, aCollider);
123 if (aabb_intersects(iOctants[1][1][0], aCollider.currentAabb))
124 child<1, 1, 0>().add_entity(aEntity, aCollider);
125 if (aabb_intersects(iOctants[0][0][1], aCollider.currentAabb))
126 child<0, 0, 1>().add_entity(aEntity, aCollider);
127 if (aabb_intersects(iOctants[0][1][1], aCollider.currentAabb))
128 child<0, 1, 1>().add_entity(aEntity, aCollider);
129 if (aabb_intersects(iOctants[1][0][1], aCollider.currentAabb))
130 child<1, 0, 1>().add_entity(aEntity, aCollider);
131 if (aabb_intersects(iOctants[1][1][1], aCollider.currentAabb))
132 child<1, 1, 1>().add_entity(aEntity, aCollider);
133 }
134 else
135 {
136 iEntities.push_back(aEntity);
137 if (iEntities.size() > BucketSize && (iAabb.max - iAabb.min).min() > iTree.minimum_octant_size())
138 split();
139 }
140 }
141 void remove_entity(entity_id aEntity, const collider_type& aCollider)
142 {
143 if (aCollider.previousAabb && aCollider.currentAabb)
144 remove_entity(aEntity, aCollider, aabb_union(*aCollider.previousAabb, *aCollider.currentAabb));
145 }
146 void remove_entity(entity_id aEntity, const collider_type& aCollider, const aabb_2d& aAabb)
147 {
148 if (!aabb_intersects(aCollider.currentAabb, iAabb))
149 {
150 auto existing = std::find(iEntities.begin(), iEntities.end(), aEntity);
151 if (existing != iEntities.end())
152 iEntities.erase(existing);
153 }
154 if (has_child<0, 0, 0>() && aabb_intersects(iOctants[0][0][0], aAabb))
155 child<0, 0, 0>().remove_entity(aEntity, aAabb);
156 if (has_child<0, 0, 1>() && aabb_intersects(iOctants[0][0][1], aAabb))
157 child<0, 0, 1>().remove_entity(aEntity, aAabb);
158 if (has_child<0, 1, 0>() && aabb_intersects(iOctants[0][1][0], aAabb))
159 child<0, 1, 0>().remove_entity(aEntity, aAabb);
160 if (has_child<0, 1, 1>() && aabb_intersects(iOctants[0][1][1], aAabb))
161 child<0, 1, 1>().remove_entity(aEntity, aAabb);
162 if (has_child<1, 0, 0>() && aabb_intersects(iOctants[1][0][0], aAabb))
163 child<1, 0, 0>().remove_entity(aEntity, aAabb);
164 if (has_child<1, 0, 1>() && aabb_intersects(iOctants[1][0][1], aAabb))
165 child<1, 0, 1>().remove_entity(aEntity, aAabb);
166 if (has_child<1, 1, 0>() && aabb_intersects(iOctants[1][1][0], aAabb))
167 child<1, 1, 0>().remove_entity(aEntity, aAabb);
168 if (has_child<1, 1, 1>() && aabb_intersects(iOctants[1][1][1], aAabb))
169 child<1, 1, 1>().remove_entity(aEntity, aAabb);
170 if (empty())
171 iTree.destroy_node(*this);
172 }
173 void update_entity(entity_id aEntity, const collider_type& aCollider)
174 {
175 iTree.iDepth = std::max(iTree.iDepth, iDepth);
176 auto const& currentAabb = aCollider.currentAabb;
177 auto const& previousAabb = aCollider.previousAabb;
178 if (currentAabb == previousAabb)
179 return;
180 if (aabb_intersects(currentAabb, iAabb))
181 add_entity(aEntity, aCollider);
182 if (aabb_intersects(previousAabb, iAabb))
183 remove_entity(aEntity, aCollider, previousAabb);
184 }
185 bool empty() const
186 {
187 bool result = iEntities.empty();
188 if (has_child<0, 0, 0>())
189 result = child<0, 0, 0>().empty() && result;
190 if (has_child<0, 0, 1>())
191 result = child<0, 0, 1>().empty() && result;
192 if (has_child<0, 1, 0>())
193 result = child<0, 1, 0>().empty() && result;
194 if (has_child<0, 1, 1>())
195 result = child<0, 1, 1>().empty() && result;
196 if (has_child<1, 0, 0>())
197 result = child<1, 0, 0>().empty() && result;
198 if (has_child<1, 0, 1>())
199 result = child<1, 0, 1>().empty() && result;
200 if (has_child<1, 1, 0>())
201 result = child<1, 1, 0>().empty() && result;
202 if (has_child<1, 1, 1>())
203 result = child<1, 1, 1>().empty() && result;
204 return result;
205 }
206 const entity_list& entities() const
207 {
208 return iEntities;
209 }
210 template <typename Visitor>
211 void visit(const collider_type& aCandidate, const Visitor& aVisitor) const
212 {
213 if (aCandidate.currentAabb)
214 visit(*aCandidate.currentAabb, aVisitor);
215 }
216 template <typename Visitor>
217 void visit(const vec3& aPoint, const Visitor& aVisitor) const
218 {
219 visit(neogfx::aabb{ aPoint, aPoint }, aVisitor);
220 }
221 template <typename Visitor>
222 void visit(const vec2& aPoint, const Visitor& aVisitor) const
223 {
224 visit(neogfx::aabb_2d{ aPoint, aPoint }, aVisitor);
225 }
226 template <typename Visitor>
227 void visit(const neogfx::aabb& aAabb, const Visitor& aVisitor) const
228 {
229 for (auto e : entities())
230 if (aabb_intersects(aAabb, iTree.iEcs.component<collider_type>().entity_record(e).currentAabb))
231 aVisitor(e);
232 if (has_child<0, 0, 0>() && aabb_intersects(iOctants[0][0][0], aAabb))
233 child<0, 0, 0>().visit(aAabb, aVisitor);
234 if (has_child<0, 0, 1>() && aabb_intersects(iOctants[0][0][1], aAabb))
235 child<0, 0, 1>().visit(aAabb, aVisitor);
236 if (has_child<0, 1, 0>() && aabb_intersects(iOctants[0][1][0], aAabb))
237 child<0, 1, 0>().visit(aAabb, aVisitor);
238 if (has_child<0, 1, 1>() && aabb_intersects(iOctants[0][1][1], aAabb))
239 child<0, 1, 1>().visit(aAabb, aVisitor);
240 if (has_child<1, 0, 0>() && aabb_intersects(iOctants[1][0][0], aAabb))
241 child<1, 0, 0>().visit(aAabb, aVisitor);
242 if (has_child<1, 0, 1>() && aabb_intersects(iOctants[1][0][1], aAabb))
243 child<1, 0, 1>().visit(aAabb, aVisitor);
244 if (has_child<1, 1, 0>() && aabb_intersects(iOctants[1][1][0], aAabb))
245 child<1, 1, 0>().visit(aAabb, aVisitor);
246 if (has_child<1, 1, 1>() && aabb_intersects(iOctants[1][1][1], aAabb))
247 child<1, 1, 1>().visit(aAabb, aVisitor);
248 }
249 template <typename Visitor>
250 void visit(const neogfx::aabb_2d& aAabb, const Visitor& aVisitor) const
251 {
252 for (auto e : entities())
253 if (iTree.iEcs.component<collider_type>().entity_record(e).currentAabb &&
254 aabb_intersects(aAabb, aabb_2d{ *iTree.iEcs.component<collider_type>().entity_record(e).currentAabb }))
255 aVisitor(e);
256 if (has_child<0, 0, 0>() && aabb_intersects(iOctants2d[0][0][0], aAabb))
257 child<0, 0, 0>().visit(aAabb, aVisitor);
258 if (has_child<0, 0, 1>() && aabb_intersects(iOctants2d[0][0][1], aAabb))
259 child<0, 0, 1>().visit(aAabb, aVisitor);
260 if (has_child<0, 1, 0>() && aabb_intersects(iOctants2d[0][1][0], aAabb))
261 child<0, 1, 0>().visit(aAabb, aVisitor);
262 if (has_child<0, 1, 1>() && aabb_intersects(iOctants2d[0][1][1], aAabb))
263 child<0, 1, 1>().visit(aAabb, aVisitor);
264 if (has_child<1, 0, 0>() && aabb_intersects(iOctants2d[1][0][0], aAabb))
265 child<1, 0, 0>().visit(aAabb, aVisitor);
266 if (has_child<1, 0, 1>() && aabb_intersects(iOctants2d[1][0][1], aAabb))
267 child<1, 0, 1>().visit(aAabb, aVisitor);
268 if (has_child<1, 1, 0>() && aabb_intersects(iOctants2d[1][1][0], aAabb))
269 child<1, 1, 0>().visit(aAabb, aVisitor);
270 if (has_child<1, 1, 1>() && aabb_intersects(iOctants2d[1][1][1], aAabb))
271 child<1, 1, 1>().visit(aAabb, aVisitor);
272 }
273 template <typename Visitor>
274 void visit_entities(const Visitor& aVisitor) const
275 {
276 for (auto e : entities())
277 aVisitor(e);
278 if (has_child<0, 0, 0>())
279 child<0, 0, 0>().visit_entities(aVisitor);
280 if (has_child<0, 0, 1>())
281 child<0, 0, 1>().visit_entities(aVisitor);
282 if (has_child<0, 1, 0>())
283 child<0, 1, 0>().visit_entities(aVisitor);
284 if (has_child<0, 1, 1>())
285 child<0, 1, 1>().visit_entities(aVisitor);
286 if (has_child<1, 0, 0>())
287 child<1, 0, 0>().visit_entities(aVisitor);
288 if (has_child<1, 0, 1>())
289 child<1, 0, 1>().visit_entities(aVisitor);
290 if (has_child<1, 1, 0>())
291 child<1, 1, 0>().visit_entities(aVisitor);
292 if (has_child<1, 1, 1>())
293 child<1, 1, 1>().visit_entities(aVisitor);
294 }
295 template <typename Visitor>
296 void visit_aabbs(const Visitor& aVisitor) const
297 {
298 aVisitor(aabb());
299 if (has_child<0, 0, 0>())
300 child<0, 0, 0>().visit_aabbs(aVisitor);
301 if (has_child<0, 0, 1>())
302 child<0, 0, 1>().visit_aabbs(aVisitor);
303 if (has_child<0, 1, 0>())
304 child<0, 1, 0>().visit_aabbs(aVisitor);
305 if (has_child<0, 1, 1>())
306 child<0, 1, 1>().visit_aabbs(aVisitor);
307 if (has_child<1, 0, 0>())
308 child<1, 0, 0>().visit_aabbs(aVisitor);
309 if (has_child<1, 0, 1>())
310 child<1, 0, 1>().visit_aabbs(aVisitor);
311 if (has_child<1, 1, 0>())
312 child<1, 1, 0>().visit_aabbs(aVisitor);
313 if (has_child<1, 1, 1>())
314 child<1, 1, 1>().visit_aabbs(aVisitor);
315 }
316 private:
317 void populate_octants()
318 {
319 auto const& min = iAabb.min;
320 auto const& max = iAabb.max;
321 auto const& center = (min + max) / 2.0;
322 iOctants[0][0][0] = neogfx::aabb{ min, center };
323 iOctants[0][1][0] = neogfx::aabb{ vec3{ min.x, center.y, min.z }, vec3{ center.x, max.y, center.z } };
324 iOctants[1][0][0] = neogfx::aabb{ vec3{ center.x, min.y, min.z }, vec3{ max.x, center.y, center.z } };
325 iOctants[1][1][0] = neogfx::aabb{ vec3{ center.x, center.y, min.z }, vec3{ max.x, max.y, center.z } };
326 iOctants[0][0][1] = neogfx::aabb{ vec3{ min.x, min.y, center.z }, vec3{ center.x, center.y, max.z } };
327 iOctants[0][1][1] = neogfx::aabb{ vec3{ min.x, center.y, center.z }, vec3{ center.x, max.y, max.z } };
328 iOctants[1][0][1] = neogfx::aabb{ vec3{ center.x, min.y, center.z }, vec3{ max.x, center.y, max.z } };
329 iOctants[1][1][1] = neogfx::aabb{ vec3{ center.x, center.y, center.z }, vec3{ max.x, max.y, max.z } };
330 iOctants2d[0][0][0] = aabb_2d{ ~min.xy, ~center.xy };
331 iOctants2d[0][1][0] = aabb_2d{ vec2{ min.x, center.y }, vec2{ center.x, max.y } };
332 iOctants2d[1][0][0] = aabb_2d{ vec2{ center.x, min.y }, vec2{ max.x, center.y } };
333 iOctants2d[1][1][0] = aabb_2d{ ~center.xy, ~max.xy };
334 iOctants2d[0][0][1] = aabb_2d{ ~min.xy, ~center.xy};
335 iOctants2d[0][1][1] = aabb_2d{ vec2{ min.x, center.y }, vec2{ center.x, max.y } };
336 iOctants2d[1][0][1] = aabb_2d{ vec2{ center.x, min.y }, vec2{ max.x, center.y } };
337 iOctants2d[1][1][1] = aabb_2d{ ~center.xy, ~max.xy };
338 }
339 template <std::size_t X, std::size_t Y, std::size_t Z>
340 node& child() const
341 {
342 if (iChildren == std::nullopt)
343 iChildren.emplace();
344 if ((*iChildren)[X][Y][Z] == nullptr)
345 (*iChildren)[X][Y][Z] = iTree.create_node(*this, iOctants[X][Y][Z]);
346 return *(*iChildren)[X][Y][Z];
347 }
348 template <std::size_t X, std::size_t Y, std::size_t Z>
349 bool has_child() const
350 {
351 if (iChildren == std::nullopt)
352 return false;
353 return (*iChildren)[X][Y][Z] != nullptr;
354 }
355 template <std::size_t X, std::size_t Y, std::size_t Z>
356 bool remove_child(node* aDestroyedNode = nullptr) const
357 {
358 if (iChildren == std::nullopt)
359 return true;
360 if ((*iChildren)[X][Y][Z] == nullptr)
361 return true;
362 if ((*iChildren)[X][Y][Z] == aDestroyedNode || aDestroyedNode == nullptr)
363 {
364 auto n = (*iChildren)[X][Y][Z];
365 (*iChildren)[X][Y][Z] = nullptr;
366 iTree.destroy_node(*n);
367 return true;
368 }
369 return false;
370 }
371 bool is_split() const
372 {
373 return iChildren != std::nullopt;
374 }
375 void split()
376 {
377 for (auto e : entities())
378 {
379 auto const& collider = iTree.iEcs.component<collider_type>().entity_record(e);
380 if (aabb_intersects(iOctants[0][0][0], collider.currentAabb))
381 child<0, 0, 0>().add_entity(e, collider);
382 if (aabb_intersects(iOctants[0][0][1], collider.currentAabb))
383 child<0, 0, 1>().add_entity(e, collider);
384 if (aabb_intersects(iOctants[0][1][0], collider.currentAabb))
385 child<0, 1, 0>().add_entity(e, collider);
386 if (aabb_intersects(iOctants[0][1][1], collider.currentAabb))
387 child<0, 1, 1>().add_entity(e, collider);
388 if (aabb_intersects(iOctants[1][0][0], collider.currentAabb))
389 child<1, 0, 0>().add_entity(e, collider);
390 if (aabb_intersects(iOctants[1][0][1], collider.currentAabb))
391 child<1, 0, 1>().add_entity(e, collider);
392 if (aabb_intersects(iOctants[1][1][0], collider.currentAabb))
393 child<1, 1, 0>().add_entity(e, collider);
394 if (aabb_intersects(iOctants[1][1][1], collider.currentAabb))
395 child<1, 1, 1>().add_entity(e, collider);
396 }
397 iEntities.clear();
398 }
399 void unsplit(node* aDestroyedNode)
400 {
401 bool haveChildren = false;
402 if (!remove_child<0, 0, 0>(aDestroyedNode))
403 haveChildren = true;
404 if (!remove_child<0, 1, 0>(aDestroyedNode))
405 haveChildren = true;
406 if (!remove_child<1, 0, 0>(aDestroyedNode))
407 haveChildren = true;
408 if (!remove_child<1, 1, 0>(aDestroyedNode))
409 haveChildren = true;
410 if (!remove_child<0, 0, 1>(aDestroyedNode))
411 haveChildren = true;
412 if (!remove_child<0, 1, 1>(aDestroyedNode))
413 haveChildren = true;
414 if (!remove_child<1, 0, 1>(aDestroyedNode))
415 haveChildren = true;
416 if (!remove_child<1, 1, 1>(aDestroyedNode))
417 haveChildren = true;
418 if (!haveChildren)
419 iChildren = std::nullopt;
420 if (empty())
421 iTree.destroy_node(*this);
422 }
423 private:
424 aabb_octree& iTree;
425 const node* iParent;
426 uint32_t iDepth;
427 neogfx::aabb iAabb;
428 octants iOctants;
429 octants_2d iOctants2d;
430 entity_list iEntities;
431 mutable std::optional<children> iChildren;
432 };
433 typedef typename allocator_type::template rebind<node>::other node_allocator;
434 public:
435 aabb_octree(i_ecs& iEcs, const aabb& aRootAabb = aabb{ vec3{-4096.0, -4096.0, -4096.0}, vec3{4096.0, 4096.0, 4096.0} }, scalar aMinimumOctantSize = 16.0, const allocator_type& aAllocator = allocator_type{}) :
436 iAllocator{ aAllocator },
437 iEcs{ iEcs },
438 iRootAabb{ aRootAabb },
439 iCount{ 0 },
440 iDepth{ 0 },
441 iRootNode{ *this, aRootAabb },
442 iMinimumOctantSize{ aMinimumOctantSize },
443 iCollisionUpdateId{ 0 }
444 {
445 }
446 public:
447 scalar minimum_octant_size() const
448 {
449 return iMinimumOctantSize;
450 }
451 void full_update()
452 {
453 iDepth = 0;
454 iRootNode.~node();
455 new(&iRootNode) node{ *this, iRootAabb };
456 for (auto entity : iEcs.component<collider_type>().entities())
457 {
458 auto& collider = iEcs.component<collider_type>().entity_record(entity);
459 iRootNode.add_entity(entity, collider);
460 }
461 }
462 void dynamic_update()
463 {
464 iDepth = 0;
465 for (auto entity : iEcs.component<collider_type>().entities())
466 {
467 auto& collider = iEcs.component<collider_type>().entity_record(entity);
468 iRootNode.update_entity(entity, collider);
469 }
470 }
471 template <typename CollisionAction>
472 void collisions(CollisionAction aCollisionAction) const
473 {
474 for (auto candidate : iEcs.component<collider_type>().entities())
475 {
476 auto const& candidateInfo = iEcs.component<entity_info>().entity_record(candidate);
477 if (candidateInfo.destroyed)
478 continue;
479 auto& candidateCollider = iEcs.component<collider_type>().entity_record(candidate);
480 if (++iCollisionUpdateId == 0)
481 iCollisionUpdateId = 1;
482 iRootNode.visit(candidateCollider, [&](entity_id aHit)
483 {
484 if (candidateInfo.destroyed)
485 return;
486 if (candidate < aHit)
487 {
488 auto const& hitInfo = iEcs.component<entity_info>().entity_record(aHit);
489 if (hitInfo.destroyed)
490 return;
491 auto& hitCollider = iEcs.component<collider_type>().entity_record(aHit);
492 if ((candidateCollider.mask & hitCollider.mask) == 0 && hitCollider.collisionEventId != iCollisionUpdateId)
493 {
494 hitCollider.collisionEventId = iCollisionUpdateId;
495 aCollisionAction(candidate, aHit);
496 }
497 }
498 });
499 }
500 }
501 template <typename ResultContainer>
502 void pick(const vec3& aPoint, ResultContainer& aResult, std::function<bool(entity_id aMatch, const vec3& aPoint)> aColliderPredicate = [](entity_id, const vec3&) { return true; }) const
503 {
504 iRootNode.visit(aPoint, [&](entity_id aMatch)
505 {
506 auto const& matchInfo = iEcs.component<entity_info>().entity_record(aMatch);
507 if (!matchInfo.destroyed && aColliderPredicate(aMatch, aPoint))
508 aResult.insert(aResult.end(), aMatch);
509 });
510 }
511 template <typename ResultContainer>
512 void pick(const vec2& aPoint, ResultContainer& aResult, std::function<bool(entity_id aMatch, const vec2& aPoint)> aColliderPredicate = [](entity_id, const vec2&) { return true; }) const
513 {
514 iRootNode.visit(aPoint, [&](entity_id aMatch)
515 {
516 auto const& matchInfo = iEcs.component<entity_info>().entity_record(aMatch);
517 if (!matchInfo.destroyed && aColliderPredicate(aMatch, aPoint))
518 aResult.insert(aResult.end(), aMatch);
519 });
520 }
521 template <typename Visitor>
522 void visit_aabbs(const Visitor& aVisitor) const
523 {
524 iRootNode.visit_aabbs(aVisitor);
525 }
526 public:
527 void insert(reference aItem)
528 {
529 iRootNode.add_entity(aItem);
530 }
531 void remove(reference aItem)
532 {
533 iRootNode.remove_entity(aItem);
534 }
535 public:
536 uint32_t count() const
537 {
538 return iCount;
539 }
540 uint32_t depth() const
541 {
542 return iDepth;
543 }
544 public:
545 const node& root_node() const
546 {
547 return iRootNode;
548 }
549 private:
550 node* create_node(const node& aParent, const aabb& aAabb)
551 {
552 ++iCount;
553 node* newNode = iAllocator.allocate(1);
554 iAllocator.construct(newNode, aParent, aAabb);
555 return newNode;
556 }
557 void destroy_node(node& aNode)
558 {
559 if (&aNode != &iRootNode && aNode.is_alive())
560 {
561 --iCount;
562 iAllocator.destroy(&aNode);
563 iAllocator.deallocate(&aNode, 1);
564 }
565 }
566 private:
567 node_allocator iAllocator;
568 i_ecs& iEcs;
569 aabb iRootAabb;
570 scalar iMinimumOctantSize;
571 uint32_t iCount;
572 mutable uint32_t iDepth;
573 node iRootNode;
574 mutable uint32_t iCollisionUpdateId;
575 };
576}
neogfx::game::aabb_octree
Definition aabb_octree.hpp:34
neogfx::game::aabb_octree::depth
uint32_t depth() const
Definition aabb_octree.hpp:540
neogfx::game::aabb_octree::const_iterator
const void * const_iterator
Definition aabb_octree.hpp:43
neogfx::game::aabb_octree::aabb_octree
aabb_octree(i_ecs &iEcs, const aabb &aRootAabb=aabb{ vec3{-4096.0, -4096.0, -4096.0}, vec3{4096.0, 4096.0, 4096.0} }, scalar aMinimumOctantSize=16.0, const allocator_type &aAllocator=allocator_type{})
Definition aabb_octree.hpp:435
neogfx::game::aabb_octree::root_node
const node & root_node() const
Definition aabb_octree.hpp:545
neogfx::game::aabb_octree::pointer
allocator_type::pointer pointer
Definition aabb_octree.hpp:38
neogfx::game::aabb_octree::dynamic_update
void dynamic_update()
Definition aabb_octree.hpp:462
neogfx::game::aabb_octree::collisions
void collisions(CollisionAction aCollisionAction) const
Definition aabb_octree.hpp:472
neogfx::game::aabb_octree::pick
void pick(const vec3 &aPoint, ResultContainer &aResult, std::function< bool(entity_id aMatch, const vec3 &aPoint)> aColliderPredicate=[](entity_id, const vec3 &) { return true;}) const
Definition aabb_octree.hpp:502
neogfx::game::aabb_octree::collider_type
Collider collider_type
Definition aabb_octree.hpp:36
neogfx::game::aabb_octree::count
uint32_t count() const
Definition aabb_octree.hpp:536
neogfx::game::aabb_octree::reference
allocator_type::reference reference
Definition aabb_octree.hpp:40
neogfx::game::aabb_octree::const_pointer
allocator_type::const_pointer const_pointer
Definition aabb_octree.hpp:39
neogfx::game::aabb_octree::remove
void remove(reference aItem)
Definition aabb_octree.hpp:531
neogfx::game::aabb_octree::pick
void pick(const vec2 &aPoint, ResultContainer &aResult, std::function< bool(entity_id aMatch, const vec2 &aPoint)> aColliderPredicate=[](entity_id, const vec2 &) { return true;}) const
Definition aabb_octree.hpp:512
neogfx::game::aabb_octree::allocator_type
Allocator allocator_type
Definition aabb_octree.hpp:37
neogfx::game::aabb_octree::iterator
void * iterator
Definition aabb_octree.hpp:44
neogfx::game::aabb_octree::const_reference
allocator_type::const_reference const_reference
Definition aabb_octree.hpp:41
neogfx::game::aabb_octree::full_update
void full_update()
Definition aabb_octree.hpp:451
neogfx::game::aabb_octree::minimum_octant_size
scalar minimum_octant_size() const
Definition aabb_octree.hpp:447
neogfx::game::aabb_octree::insert
void insert(reference aItem)
Definition aabb_octree.hpp:527
neogfx::game::aabb_octree::visit_aabbs
void visit_aabbs(const Visitor &aVisitor) const
Definition aabb_octree.hpp:522
neolib::ecs::i_ecs
Definition i_ecs.hpp:85
neolib::ecs::i_ecs::component
virtual const i_component & component(component_id aComponentId) const =0
neolib::lifetime::set_destroying
void set_destroying() override
Definition lifetime.hpp:165
neolib::math::basic_vector
Definition numerical.hpp:112
neolib::math::basic_vector::x
value_type x
Definition numerical.hpp:226
neolib::ecs::entity_id
id_t entity_id
Definition ecs_ids.hpp:51
neolib::math::aabb_union
aabb aabb_union(const aabb &left, const aabb &right)
Definition numerical.hpp:1731
neolib::math::aabb_intersects
bool aabb_intersects(const aabb &first, const aabb &second)
Definition numerical.hpp:1752
neolib::math::scalar
double scalar
Definition numerical.hpp:63
entity_info.hpp
i_ecs.hpp
neolib::ecs::entity_info
Definition entity_info.hpp:48
neolib::math::aabb_2d
Definition numerical.hpp:1791