1//************************************ bs::framework - Copyright 2014 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5#include "Prerequisites/BsPrerequisitesUtil.h"
6#include "Math/BsMath.h"
7#include "Math/BsVector4I.h"
8#include "Math/BsSIMD.h"
9#include "Allocators/BsPoolAlloc.h"
10
11namespace bs
12{
13 /** @addtogroup General
14 * @{
15 */
16
17 /** Identifier that may be used for finding an element in the quadtree. */
18 class QuadtreeElementId
19 {
20 public:
21 QuadtreeElementId() = default;
22
23 QuadtreeElementId(void* node, UINT32 elementIdx)
24 :node(node), elementIdx(elementIdx)
25 { }
26
27 private:
28 template<class, class>
29 friend class Quadtree;
30
31 void* node = nullptr;
32 UINT32 elementIdx = 0u;
33 };
34
35 /**
36 * Spatial partitioning tree for 2D space.
37 *
38 * @tparam ElemType Type of elements to be stored in the tree.
39 * @tparam Options Class that controls various options of the tree. It must provide the following enums:
40 * - LoosePadding: Denominator used to determine how much padding to add to each child node.
41 * The extra padding percent is determined as (1.0f / LoosePadding). Larger
42 * padding ensures elements are less likely to get stuck on a higher node
43 * due to them straddling the boundary between the nodes.
44 * - MinElementsPerNode: Determines at which point should node's children be removed and moved
45 * back into the parent (node is collapsed). This can occurr on element
46 * removal, when the element count drops below the specified number.
47 * - MaxElementsPerNode: Determines at which point should a node be split into child nodes.
48 * If an element counter moves past this number the elements will be
49 * added to child nodes, if possible. If a node is already at maximum
50 * depth, this is ignored.
51 * - MaxDepth: Maximum depth of nodes in the tree. Nodes at this depth will not be subdivided
52 * even if they element counts go past MaxElementsPerNode.
53 * It must also provide the following methods:
54 * - "static simd::Rect2 getBounds(const ElemType&, void*)"
55 * - Returns the bounds for the provided element
56 * - "static void setElementId(const Quadtree::ElementId&, void*)"
57 * - Gets called when element's ID is first assigned or subsequentily modified
58 */
59 template<class ElemType, class Options>
60 class Quadtree
61 {
62 /**
63 * A sequential group of elements within a node. If number of elements exceeds the limit of the group multiple
64 * groups will be linked together in a linked list fashion.
65 */
66 struct ElementGroup
67 {
68 ElemType v[Options::MaxElementsPerNode];
69 ElementGroup* next = nullptr;
70 };
71
72 /**
73 * A sequential group of element bounds within a node. If number of elements exceeds the limit of the group multiple
74 * groups will be linked together in a linked list fashion.
75 */
76 struct ElementBoundGroup
77 {
78 simd::Rect2 v[Options::MaxElementsPerNode];
79 ElementBoundGroup* next = nullptr;
80 };
81
82 /** Container class for all elements (and their bounds) within a single node. */
83 struct NodeElements
84 {
85 ElementGroup* values = nullptr;
86 ElementBoundGroup* bounds = nullptr;
87 UINT32 count = 0;
88 };
89 public:
90 /** Contains a reference to one of the eight child nodes in an quadtree node. */
91 struct HChildNode
92 {
93 union
94 {
95 struct
96 {
97 UINT32 x : 1;
98 UINT32 y : 1;
99 UINT32 empty : 1;
100 };
101
102 struct
103 {
104 UINT32 index : 2;
105 UINT32 empty2 : 1;
106 };
107 };
108
109 HChildNode()
110 :empty(true)
111 { }
112
113 HChildNode(UINT32 x, UINT32 y)
114 :x(x), y(y), empty(false)
115 { }
116
117 HChildNode(UINT32 index)
118 :index(index), empty2(false)
119 { }
120 };
121
122 /** Contains a range of child nodes in an quadtree node. */
123 struct NodeChildRange
124 {
125 union
126 {
127 struct
128 {
129 UINT32 posX : 1;
130 UINT32 posY : 1;
131 UINT32 negX : 1;
132 UINT32 negY : 1;
133 };
134
135 struct
136 {
137 UINT32 posBits : 2;
138 UINT32 negBits : 2;
139 };
140
141 UINT32 allBits : 4;
142 };
143
144 /** Constructs a range overlapping no nodes. */
145 NodeChildRange()
146 :allBits(0)
147 { }
148
149 /** Constructs a range overlapping a single node. */
150 NodeChildRange(HChildNode child)
151 :posBits(child.index), negBits(~child.index)
152 { }
153
154 /** Checks if the range contains the provided child. */
155 bool contains(HChildNode child)
156 {
157 NodeChildRange childRange(child);
158 return (allBits & childRange.allBits) == childRange.allBits;
159 }
160 };
161
162 /** Represents a single quadtree node. */
163 class Node
164 {
165 public:
166 /** Constructs a new leaf node with the specified parent. */
167 Node(Node* parent)
168 :mParent(parent), mTotalNumElements(0), mIsLeaf(true)
169 { }
170
171 /** Returns a child node with the specified index. May return null. */
172 Node* getChild(HChildNode child) const
173 {
174 return mChildren[child.index];
175 }
176
177 /** Checks has the specified child node been created. */
178 bool hasChild(HChildNode child) const
179 {
180 return mChildren[child.index] != nullptr;
181 }
182
183 private:
184 friend class ElementIterator;
185 friend class Quadtree;
186
187 /** Maps a global element index to a set of element groups and an index within those groups. */
188 UINT32 mapToGroup(UINT32 elementIdx, ElementGroup** elements, ElementBoundGroup** bounds)
189 {
190 UINT32 numGroups = Math::divideAndRoundUp(mElements.count, (UINT32)Options::MaxElementsPerNode);
191 UINT32 groupIdx = numGroups - elementIdx / Options::MaxElementsPerNode - 1;
192
193 *elements = mElements.values;
194 *bounds = mElements.bounds;
195 for (UINT32 i = 0; i < groupIdx; i++)
196 {
197 *elements = (*elements)->next;
198 *bounds = (*bounds)->next;
199 }
200
201 return elementIdx % Options::MaxElementsPerNode;
202 }
203
204 NodeElements mElements;
205
206 Node* mParent;
207 Node* mChildren[4] = { nullptr, nullptr, nullptr, nullptr };
208
209 UINT32 mTotalNumElements : 31;
210 UINT32 mIsLeaf : 1;
211 };
212
213 /**
214 * Contains bounds for a specific node. This is necessary since the nodes themselves do not store bounds
215 * information. Instead we construct it on-the-fly as we traverse the tree, using this class.
216 */
217 class NodeBounds
218 {
219 public:
220 NodeBounds() = default;
221
222 /** Initializes a new bounds object using the provided node bounds. */
223 NodeBounds(const simd::Rect2& bounds)
224 :mBounds(bounds)
225 {
226 static constexpr float childExtentScale = 0.5f * (1.0f + 1.0f / Options::LoosePadding);
227
228 mChildExtent = bounds.extents.x * childExtentScale;
229 mChildOffset = bounds.extents.x - mChildExtent;
230 }
231
232 /** Returns the bounds of the node this object represents. */
233 const simd::Rect2& getBounds() const { return mBounds; }
234
235 /** Attempts to find a child node that can fully contain the provided bounds. */
236 HChildNode findContainingChild(const simd::Rect2& bounds) const
237 {
238 auto queryCenter = simd::load<simd::float32x4>(&bounds.center);
239
240 auto nodeCenter = simd::load<simd::float32x4>(&mBounds.center);
241 auto childOffset = simd::load_splat<simd::float32x4>(&mChildOffset);
242
243 auto negativeCenter = simd::sub(nodeCenter, childOffset);
244 auto negativeDiff = simd::sub(queryCenter, negativeCenter);
245
246 auto positiveCenter = simd::add(nodeCenter, childOffset);
247 auto positiveDiff = simd::sub(positiveCenter, queryCenter);
248
249 auto diff = simd::min(negativeDiff, positiveDiff);
250
251 auto queryExtents = simd::load<simd::float32x4>(&bounds.extents);
252 auto childExtent = simd::load_splat<simd::float32x4>(&mChildExtent);
253
254 HChildNode output;
255
256 simd::mask_float32x4 mask = simd::cmp_gt(simd::add(queryExtents, diff), childExtent);
257 if (simd::test_bits_any(simd::bit_cast<simd::uint32x4>(mask)) == false)
258 {
259 auto ones = simd::make_uint<simd::uint32x4>(1, 1, 1, 1);
260 auto zeroes = simd::make_uint<simd::uint32x4>(0, 0, 0, 0);
261
262 // Find node closest to the query center
263 mask = simd::cmp_gt(queryCenter, nodeCenter);
264 auto result = simd::blend(ones, zeroes, mask);
265
266 Vector4I scalarResult;
267 simd::store(&scalarResult, result);
268
269 output.x = scalarResult.x;
270 output.y = scalarResult.y;
271
272 output.empty = false;
273 }
274
275 return output;
276 }
277
278 /** Returns a range of child nodes that intersect the provided bounds. */
279 NodeChildRange findIntersectingChildren(const simd::Rect2& bounds) const
280 {
281 auto queryCenter = simd::load<simd::float32x4>(&bounds.center);
282 auto queryExtents = simd::load<simd::float32x4>(&bounds.extents);
283
284 auto queryMax = simd::add(queryCenter, queryExtents);
285 auto queryMin = simd::sub(queryCenter, queryExtents);
286
287 auto nodeCenter = simd::load<simd::float32x4>(&mBounds.center);
288 auto childOffset = simd::load_splat<simd::float32x4>(&mChildOffset);
289
290 auto negativeCenter = simd::sub(nodeCenter, childOffset);
291 auto positiveCenter = simd::add(nodeCenter, childOffset);
292
293 auto childExtent = simd::load_splat<simd::float32x4>(&mChildExtent);
294 auto negativeMax = simd::add(negativeCenter, childExtent);
295 auto positiveMin = simd::sub(positiveCenter, childExtent);
296
297 NodeChildRange output;
298
299 auto ones = simd::make_uint<simd::uint32x4>(1, 1, 1, 1);
300 auto zeroes = simd::make_uint<simd::uint32x4>(0, 0, 0, 0);
301
302 simd::mask_float32x4 mask = simd::cmp_gt(queryMax, positiveMin);
303 simd::uint32x4 result = simd::blend(ones, zeroes, mask);
304
305 Vector4I scalarResult;
306 simd::store(&scalarResult, result);
307
308 output.posX = scalarResult.x;
309 output.posY = scalarResult.y;
310
311 mask = simd::cmp_le(queryMin, negativeMax);
312 result = simd::blend(ones, zeroes, mask);
313
314 simd::store(&scalarResult, result);
315
316 output.negX = scalarResult.x;
317 output.negY = scalarResult.y;
318
319 return output;
320 }
321
322 /** Calculates bounds for the provided child node. */
323 NodeBounds getChild(HChildNode child) const
324 {
325 static constexpr const float map[2] = { -1.0f, 1.0f };
326
327 return NodeBounds(
328 simd::Rect2(
329 Vector2(
330 mBounds.center.x + mChildOffset * map[child.x],
331 mBounds.center.y + mChildOffset * map[child.y]
332 ),
333 mChildExtent
334 )
335 );
336 }
337
338 private:
339 simd::Rect2 mBounds;
340 float mChildExtent;
341 float mChildOffset;
342 };
343
344 /** Contains a reference to a specific quadtree node, as well as information about its bounds. */
345 class HNode
346 {
347 public:
348 HNode() = default;
349
350 HNode(const Node* node, const NodeBounds& bounds)
351 :mNode(node), mBounds(bounds)
352 { }
353
354 /** Returns the referenced node. */
355 const Node* getNode() const { return mNode; }
356
357 /** Returns the node bounds. */
358 const NodeBounds& getBounds() const { return mBounds; }
359
360 private:
361 const Node* mNode = nullptr;
362 NodeBounds mBounds;
363 };
364
365 /**
366 * Iterator that iterates over quadtree nodes. By default only the first inserted node will be iterated over and it
367 * is up the the user to add new ones using pushChild(). The iterator takes care of updating the node bounds
368 * accordingly.
369 */
370 class NodeIterator
371 {
372 public:
373 /** Initializes the iterator, starting with the root quadtree node. */
374 NodeIterator(const Quadtree& tree)
375 :mCurrentNode(HNode(&tree.mRoot, tree.mRootBounds)), mStackAlloc(), mNodeStack(&mStackAlloc)
376 {
377 mNodeStack.push_back(mCurrentNode);
378 }
379
380 /** Initializes the iterator using a specific node and its bounds. */
381 NodeIterator(const Node* node, const NodeBounds& bounds)
382 :mCurrentNode(HNode(node, bounds)), mStackAlloc(), mNodeStack(&mStackAlloc)
383 {
384 mNodeStack.push_back(mCurrentNode);
385 }
386
387 /**
388 * Returns a reference to the current node. moveNext() must be called at least once and it must return true
389 * prior to attempting to access this data.
390 */
391 const HNode& getCurrent() const { return mCurrentNode; }
392
393 /**
394 * Moves to the next entry in the iterator. Iterator starts at a position before the first element, therefore
395 * this method must be called at least once before attempting to access the current node. If the method returns
396 * false it means the iterator end has been reached and attempting to access data will result in an error.
397 */
398 bool moveNext()
399 {
400 if (mNodeStack.empty())
401 {
402 mCurrentNode = HNode();
403 return false;
404 }
405
406 mCurrentNode = mNodeStack.back();
407 mNodeStack.erase(mNodeStack.end() - 1);
408
409 return true;
410 }
411
412 /** Inserts a child of the current node to be iterated over. */
413 void pushChild(const HChildNode& child)
414 {
415 Node* childNode = mCurrentNode.getNode()->getChild(child);
416 NodeBounds childBounds = mCurrentNode.getBounds().getChild(child);
417
418 mNodeStack.emplace_back(childNode, childBounds);
419 }
420
421 private:
422 HNode mCurrentNode;
423 StaticAlloc<Options::MaxDepth * 4 * sizeof(HNode), FreeAlloc> mStackAlloc;
424 StaticVector<HNode, Options::MaxDepth * 4> mNodeStack;
425 };
426
427 /** Iterator that iterates over all elements in a single node. */
428 class ElementIterator
429 {
430 public:
431 ElementIterator() = default;
432
433 /** Constructs an iterator that iterates over the specified node's elements. */
434 ElementIterator(const Node* node)
435 : mCurrentIdx(-1)
436 , mCurrentElemGroup(node->mElements.values)
437 , mCurrentBoundGroup(node->mElements.bounds)
438 {
439 UINT32 numGroups = Math::divideAndRoundUp(node->mElements.count, (UINT32)Options::MaxElementsPerNode);
440 mElemsInGroup = node->mElements.count - (numGroups - 1) * Options::MaxElementsPerNode;
441 }
442
443 /**
444 * Moves to the next element in the node. Iterator starts at a position before the first element, therefore
445 * this method must be called at least once before attempting to access the current element data. If the method
446 * returns false it means iterator end has been reached and attempting to access data will result in an error.
447 */
448 bool moveNext()
449 {
450 if (!mCurrentElemGroup)
451 return false;
452
453 mCurrentIdx++;
454
455 if ((UINT32)mCurrentIdx == mElemsInGroup) // Next group
456 {
457 mCurrentElemGroup = mCurrentElemGroup->next;
458 mCurrentBoundGroup = mCurrentBoundGroup->next;
459 mElemsInGroup = Options::MaxElementsPerNode; // Following groups are always full
460 mCurrentIdx = 0;
461
462 if (!mCurrentElemGroup)
463 return false;
464 }
465
466 return true;
467 }
468
469 /**
470 * Returns the bounds of the current element. moveNext() must be called at least once and it must return true
471 * prior to attempting to access this data.
472 */
473 const simd::Rect2& getCurrentBounds() const { return mCurrentBoundGroup->v[mCurrentIdx]; }
474
475 /**
476 * Returns the contents of the current element. moveNext() must be called at least once and it must return true
477 * prior to attempting to access this data.
478 */
479 const ElemType& getCurrentElem() const { return mCurrentElemGroup->v[mCurrentIdx]; }
480
481 private:
482 INT32 mCurrentIdx = -1;
483 ElementGroup* mCurrentElemGroup = nullptr;
484 ElementBoundGroup* mCurrentBoundGroup = nullptr;
485 UINT32 mElemsInGroup = 0;
486 };
487
488 /** Iterators that iterates over all elements intersecting the specified Rect2. */
489 class BoxIntersectIterator
490 {
491 public:
492 /**
493 * Constructs an iterator that iterates over all elements in the specified tree that intersect the specified
494 * bounds.
495 */
496 BoxIntersectIterator(const Quadtree& tree, const Rect2& bounds)
497 :mNodeIter(tree), mBounds(simd::Rect2(bounds))
498 { }
499
500 /**
501 * Returns the contents of the current element. moveNext() must be called at least once and it must return true
502 * prior to attempting to access this data.
503 */
504 const ElemType& getElement() const
505 {
506 return mElemIter.getCurrentElem();
507 }
508
509 /**
510 * Moves to the next intersecting element. Iterator starts at a position before the first element, therefore
511 * this method must be called at least once before attempting to access the current element data. If the method
512 * returns false it means iterator end has been reached and attempting to access data will result in an error.
513 */
514 bool moveNext()
515 {
516 while (true)
517 {
518 // First check elements of the current node (if any)
519 while (mElemIter.moveNext())
520 {
521 const simd::Rect2& bounds = mElemIter.getCurrentBounds();
522 if (bounds.overlaps(mBounds))
523 return true;
524 }
525
526 // No more elements in this node, move to the next one
527 if (!mNodeIter.moveNext())
528 return false; // No more nodes to check
529
530 const HNode& nodeRef = mNodeIter.getCurrent();
531 mElemIter = ElementIterator(nodeRef.getNode());
532
533 // Add all intersecting child nodes to the iterator
534 NodeChildRange childRange = nodeRef.getBounds().findIntersectingChildren(mBounds);
535 for (UINT32 i = 0; i < 4; i++)
536 {
537 if (childRange.contains(i) && nodeRef.getNode()->hasChild(i))
538 mNodeIter.pushChild(i);
539 }
540 }
541
542 return false;
543 }
544
545 private:
546 NodeIterator mNodeIter;
547 ElementIterator mElemIter;
548 simd::Rect2 mBounds;
549 };
550
551 /**
552 * Constructs an quadtree with the specified bounds.
553 *
554 * @param[in] center Origin of the root node.
555 * @param[in] extent Extent (half-size) of the root node in all directions;
556 * @param[in] context Optional user context that will be passed along to getBounds() and setElementId()
557 * methods on the provided Options class.
558 */
559 Quadtree(const Vector2& center, float extent, void* context = nullptr)
560 : mRootBounds(simd::Rect2(center, extent))
561 , mMinNodeExtent(extent * std::pow(0.5f * (1.0f + 1.0f / Options::LoosePadding), Options::MaxDepth))
562 , mContext(context)
563 {
564 }
565
566 ~Quadtree()
567 {
568 destroyNode(&mRoot);
569 }
570
571 /** Adds a new element to the quadtree. */
572 void addElement(const ElemType& elem)
573 {
574 addElementToNode(elem, &mRoot, mRootBounds);
575 }
576
577 /** Removes an existing element from the quadtree. */
578 void removeElement(const QuadtreeElementId& elemId)
579 {
580 Node* node = (Node*)elemId.node;
581
582 popElement(node, elemId.elementIdx);
583
584 // Reduce element counts in this and any parent nodes, check if nodes need collapsing
585 Node* iterNode = node;
586 Node* nodeToCollapse = nullptr;
587 while (iterNode)
588 {
589 --iterNode->mTotalNumElements;
590
591 if (iterNode->mTotalNumElements < Options::MinElementsPerNode)
592 nodeToCollapse = iterNode;
593
594 iterNode = iterNode->mParent;
595 }
596
597 if (nodeToCollapse)
598 {
599 // Add all the child node elements to the current node
600 bs_frame_mark();
601 {
602 FrameStack<Node*> todo;
603 todo.push(node);
604
605 while (!todo.empty())
606 {
607 Node* curNode = todo.top();
608 todo.pop();
609
610 for (UINT32 i = 0; i < 4; i++)
611 {
612 if (curNode->hasChild(i))
613 {
614 Node* childNode = curNode->getChild(i);
615
616 ElementIterator elemIter(childNode);
617 while (elemIter.moveNext())
618 pushElement(node, elemIter.getCurrentElem(), elemIter.getCurrentBounds());
619
620 todo.push(childNode);
621 }
622 }
623 }
624 }
625 bs_frame_clear();
626
627 node->mIsLeaf = true;
628
629 // Recursively delete all child nodes
630 for (UINT32 i = 0; i < 4; i++)
631 {
632 if (node->mChildren[i])
633 {
634 destroyNode(node->mChildren[i]);
635
636 mNodeAlloc.destruct(node->mChildren[i]);
637 node->mChildren[i] = nullptr;
638 }
639 }
640 }
641 }
642
643 private:
644 /** Adds a new element to the specified node. Potentially also subdivides the node. */
645 void addElementToNode(const ElemType& elem, Node* node, const NodeBounds& nodeBounds)
646 {
647 simd::Rect2 elemBounds = Options::getBounds(elem, mContext);
648
649 ++node->mTotalNumElements;
650 if (node->mIsLeaf)
651 {
652 const simd::Rect2& bounds = nodeBounds.getBounds();
653
654 // Check if the node has too many elements and should be broken up
655 if ((node->mElements.count + 1) > Options::MaxElementsPerNode && bounds.extents.x > mMinNodeExtent)
656 {
657 // Clear all elements from the current node
658 NodeElements elements = node->mElements;
659
660 ElementIterator elemIter(node);
661 node->mElements = NodeElements();
662
663 // Mark the node as non-leaf, allowing children to be created
664 node->mIsLeaf = false;
665 node->mTotalNumElements = 0;
666
667 // Re-insert all previous elements into this node (likely creating child nodes)
668 while (elemIter.moveNext())
669 addElementToNode(elemIter.getCurrentElem(), node, nodeBounds);
670
671 // Free the element and bound groups from this node
672 freeElements(elements);
673
674 // Insert the current element
675 addElementToNode(elem, node, nodeBounds);
676 }
677 else
678 {
679 // No need to sub-divide, just add the element to this node
680 pushElement(node, elem, elemBounds);
681 }
682 }
683 else
684 {
685 // Attempt to find a child the element fits into
686 HChildNode child = nodeBounds.findContainingChild(elemBounds);
687
688 if (child.empty)
689 {
690 // Element doesn't fit into a child, add it to this node
691 pushElement(node, elem, elemBounds);
692 }
693 else
694 {
695 // Create the child node if needed, and add the element to it
696 if (!node->mChildren[child.index])
697 node->mChildren[child.index] = mNodeAlloc.template construct<Node>(node);
698
699 addElementToNode(elem, node->mChildren[child.index], nodeBounds.getChild(child));
700 }
701 }
702 }
703
704 /** Cleans up memory used by the provided node. Should be called instead of the node destructor. */
705 void destroyNode(Node* node)
706 {
707 freeElements(node->mElements);
708
709 for (auto& entry : node->mChildren)
710 {
711 if (entry != nullptr)
712 {
713 destroyNode(entry);
714 mNodeAlloc.destruct(entry);
715 }
716 }
717 }
718
719 /** Adds a new element to the node's element list. */
720 void pushElement(Node* node, const ElemType& elem, const simd::Rect2& bounds)
721 {
722 NodeElements& elements = node->mElements;
723
724 UINT32 freeIdx = elements.count % Options::MaxElementsPerNode;
725 if (freeIdx == 0) // New group needed
726 {
727 ElementGroup* elementGroup = (ElementGroup*)mElemAlloc.template construct<ElementGroup>();
728 ElementBoundGroup* boundGroup = (ElementBoundGroup*)mElemBoundsAlloc.template construct<ElementBoundGroup>();
729
730 elementGroup->next = elements.values;
731 boundGroup->next = elements.bounds;
732
733 elements.values = elementGroup;
734 elements.bounds = boundGroup;
735 }
736
737 elements.values->v[freeIdx] = elem;
738 elements.bounds->v[freeIdx] = bounds;
739
740 UINT32 elementIdx = elements.count;
741 Options::setElementId(elem, QuadtreeElementId(node, elementIdx), mContext);
742
743 ++elements.count;
744 }
745
746 /** Removes the specified element from the node's element list. */
747 void popElement(Node* node, UINT32 elementIdx)
748 {
749 NodeElements& elements = node->mElements;
750
751 ElementGroup* elemGroup;
752 ElementBoundGroup* boundGroup;
753 elementIdx = node->mapToGroup(elementIdx, &elemGroup, &boundGroup);
754
755 ElementGroup* lastElemGroup;
756 ElementBoundGroup* lastBoundGroup;
757 UINT32 lastElementIdx = node->mapToGroup(elements.count - 1, &lastElemGroup, &lastBoundGroup);
758
759 if (elements.count > 1)
760 {
761 std::swap(elemGroup->v[elementIdx], lastElemGroup->v[lastElementIdx]);
762 std::swap(boundGroup->v[elementIdx], lastBoundGroup->v[lastElementIdx]);
763
764 Options::setElementId(elemGroup->v[elementIdx], QuadtreeElementId(node, elementIdx), mContext);
765 }
766
767 if (lastElementIdx == 0) // Last element in that group, remove it completely
768 {
769 elements.values = lastElemGroup->next;
770 elements.bounds = lastBoundGroup->next;
771
772 mElemAlloc.destruct(lastElemGroup);
773 mElemBoundsAlloc.destruct(lastBoundGroup);
774 }
775
776 --elements.count;
777 }
778
779 /** Clears all elements from a node. */
780 void freeElements(NodeElements& elements)
781 {
782 // Free the element and bound groups from this node
783 ElementGroup* curElemGroup = elements.values;
784 while (curElemGroup)
785 {
786 ElementGroup* toDelete = curElemGroup;
787 curElemGroup = curElemGroup->next;
788
789 mElemAlloc.destruct(toDelete);
790 }
791
792 ElementBoundGroup* curBoundGroup = elements.bounds;
793 while (curBoundGroup)
794 {
795 ElementBoundGroup* toDelete = curBoundGroup;
796 curBoundGroup = curBoundGroup->next;
797
798 mElemBoundsAlloc.destruct(toDelete);
799 }
800
801 elements.values = nullptr;
802 elements.bounds = nullptr;
803 elements.count = 0;
804 }
805
806 Node mRoot{ nullptr };
807 NodeBounds mRootBounds;
808 float mMinNodeExtent;
809 void* mContext;
810
811 PoolAlloc<sizeof(Node)> mNodeAlloc;
812 PoolAlloc<sizeof(ElementGroup)> mElemAlloc;
813 PoolAlloc<sizeof(ElementBoundGroup), 512, 16> mElemBoundsAlloc;
814 };
815
816 /** @} */
817}
818