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