Nebula
Loading...
Searching...
No Matches
occupancyquadtree.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
9//------------------------------------------------------------------------------
10#include "core/types.h"
11#include "math/scalar.h"
12#include "util/fixedarray.h"
14namespace Terrain
15{
16
18{
19public:
24
26 void Setup(uint worldSize, uint maxSize, uint minSize);
30 bool Deallocate(const Math::uint2 coord, uint size);
32 bool IsOccupied(const Math::uint2 coord, uint size);
33
35 void DebugRender(ImDrawList* drawList, ImVec2 offset, float scale);
36
37private:
38 struct Node
39 {
41 : topLeft(nullptr)
42 , topRight(nullptr)
43 , bottomLeft(nullptr)
44 , bottomRight(nullptr)
45 , occupied(false)
47 , size(1)
48 , x(UINT32_MAX)
49 , y(UINT32_MAX)
50 {}
59 };
60
62 bool RecursiveAllocate(Node* node, uint size, Math::uint2& outCoord);
64 bool RecursiveDeallocate(Node* node, Math::uint2 coord, uint size);
66 bool RecursiveSearch(Node* node, Math::uint2 coord, uint size);
67
69 void RecursiveDebugRender(Node* node, ImDrawList* drawList, ImVec2 offset, float scale);
70
74};
75
76//------------------------------------------------------------------------------
79inline
84
85//------------------------------------------------------------------------------
88inline
93
94//------------------------------------------------------------------------------
97inline void
98OccupancyQuadTree::Setup(uint worldSize, uint maxSize, uint minSize)
99{
100 this->minSize = minSize;
101 uint numNodes = worldSize / maxSize;
102 this->topLevelNodes.Resize(numNodes);
103 for (uint x = 0; x < numNodes; x++)
104 {
105 this->topLevelNodes[x].Resize(numNodes);
106 for (uint y = 0; y < numNodes; y++)
107 {
108 this->topLevelNodes[x][y].x = x * maxSize;
109 this->topLevelNodes[x][y].y = y * maxSize;
110 this->topLevelNodes[x][y].size = maxSize;
111 this->topLevelNodes[x][y].occupied = false;
112 }
113 }
114}
115
116//------------------------------------------------------------------------------
119inline bool
121{
122 // if the node is not occupied, proceed
123 if (!node->occupied)
124 {
125 // if size matches and no children are used, return
126 if (node->size == size && node->occupancyCounter == 0)
127 {
128 n_assert(node->occupied == false);
129 outCoord = Math::uint2{ node->x, node->y };
130 node->occupied = true;
131 return true;
132 }
133 else if (node->size > size && node->size != this->minSize)
134 {
135 // if the size of the node is bigger than the requested size, visit the children
136 if (node->topLeft == nullptr)
137 {
138 // initialize children, topleft is the origin point
139 const uint halfNodeSize = node->size / 2;
140 node->topLeft = this->allocator.Alloc<Node>();
141 node->topLeft->x = node->x;
142 node->topLeft->y = node->y;
143 node->topLeft->size = halfNodeSize;
144
145 node->topRight = this->allocator.Alloc<Node>();
146 node->topRight->x = node->x + halfNodeSize;
147 node->topRight->y = node->y;
148 node->topRight->size = halfNodeSize;
149
150 node->bottomLeft = this->allocator.Alloc<Node>();
151 node->bottomLeft->x = node->x;
152 node->bottomLeft->y = node->y + halfNodeSize;
153 node->bottomLeft->size = halfNodeSize;
154
155 node->bottomRight = this->allocator.Alloc<Node>();
156 node->bottomRight->x = node->x + halfNodeSize;
157 node->bottomRight->y = node->y + halfNodeSize;
158 node->bottomRight->size = halfNodeSize;
159 }
160
161 if (RecursiveAllocate(node->topLeft, size, outCoord))
162 {
163 node->occupancyCounter++;
164 return true;
165 }
166 if (RecursiveAllocate(node->topRight, size, outCoord))
167 {
168 node->occupancyCounter++;
169 return true;
170 }
171 if (RecursiveAllocate(node->bottomLeft, size, outCoord))
172 {
173 node->occupancyCounter++;
174 return true;
175 }
176 if (RecursiveAllocate(node->bottomRight, size, outCoord))
177 {
178 node->occupancyCounter++;
179 return true;
180 }
181 }
182 }
183
184 return false;
185}
186
187//------------------------------------------------------------------------------
190inline Math::uint2
192{
193 Math::uint2 ret{ UINT32_MAX, UINT32_MAX };
194 for (int x = 0; x < this->topLevelNodes.Size(); x++)
195 {
196 for (int y = 0; y < this->topLevelNodes[x].Size(); y++)
197 {
198 // try to allocate node in this subtree, if failed, just skip to the next top-level node
199 if (RecursiveAllocate(&this->topLevelNodes[x][y], size, ret))
200 return ret;
201 }
202 }
203 return ret;
204}
205
206//------------------------------------------------------------------------------
209inline bool
211{
212 // if node matches size, look for the coordinate
213 if (node->size == size)
214 {
215 if (node->x == coord.x && node->y == coord.y)
216 {
217 n_assert(node->occupancyCounter == 0);
218 n_assert(node->occupied == true);
219 node->occupied = false;
220 return true;
221 }
222 }
223 else if (node->size > size)
224 {
225 // if node size is bigger than the requested size, visit children and unset the bits
226 if (node->topLeft == nullptr)
227 return false;
228
229 if (RecursiveDeallocate(node->topLeft, coord, size))
230 {
231 node->occupancyCounter--;
232 return true;
233 }
234 if (RecursiveDeallocate(node->topRight, coord, size))
235 {
236 node->occupancyCounter--;
237 return true;
238 }
239 if (RecursiveDeallocate(node->bottomLeft, coord, size))
240 {
241 node->occupancyCounter--;
242 return true;
243 }
244 if (RecursiveDeallocate(node->bottomRight, coord, size))
245 {
246 node->occupancyCounter--;
247 return true;
248 }
249 }
250
251 return false;
252}
253
254
255//------------------------------------------------------------------------------
258inline bool
260{
261 // find root node where the coord belongs
262 for (int x = 0; x < this->topLevelNodes.Size(); x++)
263 {
264 for (int y = 0; y < this->topLevelNodes[x].Size(); y++)
265 {
266 Node& node = this->topLevelNodes[x][y];
267 if (RecursiveDeallocate(&node, coord, size))
268 return true;
269 }
270 }
271 return false;
272}
273
274//------------------------------------------------------------------------------
277inline bool
279{
280 // if node matches size, look for the coordinate
281 if (node->size == size)
282 {
283 if (node->x == coord.x && node->y == coord.y)
284 {
285 return node->occupied;
286 }
287 }
288 else if (node->size > size)
289 {
290 // if node size is bigger than the requested size, visit children and unset the bits
291 if (node->topLeft == nullptr)
292 return false;
293
294 if (RecursiveDeallocate(node->topLeft, coord, size))
295 {
296 return true;
297 }
298 if (RecursiveDeallocate(node->topRight, coord, size))
299 {
300 return true;
301 }
302 if (RecursiveDeallocate(node->bottomLeft, coord, size))
303 {
304 return true;
305 }
306 if (RecursiveDeallocate(node->bottomRight, coord, size))
307 {
308 return true;
309 }
310 }
311
312 return false;
313}
314
315//------------------------------------------------------------------------------
318inline bool
320{
321 // find root node where the coord belongs
322 for (int x = 0; x < this->topLevelNodes.Size(); x++)
323 {
324 for (int y = 0; y < this->topLevelNodes[x].Size(); y++)
325 {
326 Node& node = this->topLevelNodes[x][y];
327 if (RecursiveSearch(&node, coord, size))
328 return true;
329 }
330 }
331 return false;
332}
333
334static uint colorIndex = 0;
335
336//------------------------------------------------------------------------------
339inline void
340OccupancyQuadTree::RecursiveDebugRender(Node* node, ImDrawList* drawList, ImVec2 offset, float scale)
341{
342 static ImU32 colors[] =
343 {
344 IM_COL32(128, 0, 0, 128),
345 IM_COL32(0, 128, 0, 128),
346 IM_COL32(0, 0, 128, 128),
347 IM_COL32(128, 0, 128, 128),
348 IM_COL32(128, 128, 0, 128),
349 IM_COL32(0, 128, 128, 128),
350 };
351
352 if (node->occupied)
353 {
354 colorIndex = (colorIndex + 1) % 5;
355
356 ImVec2 min{ (float)offset.x + node->x * scale, (float)offset.y + node->y * scale };
357 ImVec2 max{ (float)offset.x + (node->x + node->size) * scale, (float)offset.y + (node->y + node->size) * scale };
358 drawList->AddRectFilled(min, max, colors[colorIndex]);
359 }
360 else if (node->topLeft)
361 {
362 RecursiveDebugRender(node->topLeft, drawList, offset, scale);
363 RecursiveDebugRender(node->topRight, drawList, offset, scale);
364 RecursiveDebugRender(node->bottomLeft, drawList, offset, scale);
365 RecursiveDebugRender(node->bottomRight, drawList, offset, scale);
366 }
367}
368
369//------------------------------------------------------------------------------
372inline void
373OccupancyQuadTree::DebugRender(ImDrawList* drawList, ImVec2 offset, float scale)
374{
375 colorIndex = 0;
376
377 // find root node where the coord belongs
378 for (int x = 0; x < this->topLevelNodes.Size(); x++)
379 {
380 for (int y = 0; y < this->topLevelNodes[x].Size(); y++)
381 {
382 RecursiveDebugRender(&this->topLevelNodes[x][y], drawList, offset, scale);
383 }
384 }
385}
386
387} // namespace Terrain
Allocates memory in chunks.
Definition arenaallocator.h:36
Definition occupancyquadtree.h:18
Math::uint2 Allocate(uint size)
allocate a region, return region
Definition occupancyquadtree.h:191
bool RecursiveDeallocate(Node *node, Math::uint2 coord, uint size)
recursively traverse tree and deallocate
Definition occupancyquadtree.h:210
Memory::ArenaAllocator< sizeof(Node) *64 > allocator
Definition occupancyquadtree.h:71
void RecursiveDebugRender(Node *node, ImDrawList *drawList, ImVec2 offset, float scale)
recursively debug render
Definition occupancyquadtree.h:340
uint minSize
Definition occupancyquadtree.h:73
Util::FixedArray< Util::FixedArray< Node > > topLevelNodes
Definition occupancyquadtree.h:72
bool IsOccupied(const Math::uint2 coord, uint size)
check if region is alloced
Definition occupancyquadtree.h:319
void DebugRender(ImDrawList *drawList, ImVec2 offset, float scale)
debug render
Definition occupancyquadtree.h:373
bool RecursiveSearch(Node *node, Math::uint2 coord, uint size)
recursively traverse tree and find if allocated
Definition occupancyquadtree.h:278
void Setup(uint worldSize, uint maxSize, uint minSize)
setup with a world size and a biggest allocation size
Definition occupancyquadtree.h:98
bool RecursiveAllocate(Node *node, uint size, Math::uint2 &outCoord)
recursively traverse tree to allocate node from tree
Definition occupancyquadtree.h:120
~OccupancyQuadTree()
destructor
Definition occupancyquadtree.h:89
OccupancyQuadTree()
constructor
Definition occupancyquadtree.h:80
bool Deallocate(const Math::uint2 coord, uint size)
deallocate region
Definition occupancyquadtree.h:259
Implements a fixed size one-dimensional array.
Definition fixedarray.h:20
#define n_assert(exp)
Definition debug.h:50
The occupancy quad tree implements a tree which allows for a quick search.
Definition occupancyquadtree.h:15
static uint colorIndex
Definition occupancyquadtree.h:334
Nebula's scalar datatype.
scalar x
Definition scalar.h:61
scalar y
Definition scalar.h:61
Definition scalar.h:112
unsigned int x
Definition scalar.h:115
unsigned int y
Definition scalar.h:115
Definition occupancyquadtree.h:39
Node()
Definition occupancyquadtree.h:40
Node * bottomRight
Definition occupancyquadtree.h:54
uint size
Definition occupancyquadtree.h:57
Node * bottomLeft
Definition occupancyquadtree.h:53
Node * topLeft
Definition occupancyquadtree.h:51
uint x
Definition occupancyquadtree.h:58
bool occupied
Definition occupancyquadtree.h:55
uint y
Definition occupancyquadtree.h:58
Node * topRight
Definition occupancyquadtree.h:52
uint occupancyCounter
Definition occupancyquadtree.h:56
unsigned int uint
Definition types.h:31