From 162280cd981b97ffef927553ec230cddcda878ce Mon Sep 17 00:00:00 2001 From: Cosmic Linden Date: Tue, 12 Apr 2022 14:05:51 -0700 Subject: SL-17021: Templatize LLOctreeNode and related classes to allow for option to store elements in octrees as raw pointers. Use for faster allocation in LLVolumeFace::createOctree. --- indra/llmath/lloctree.h | 89 ++++++++++++++++++++++++++----------------------- 1 file changed, 48 insertions(+), 41 deletions(-) (limited to 'indra/llmath/lloctree.h') diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h index 7e73fb6b57..318ee65cc0 100644 --- a/indra/llmath/lloctree.h +++ b/indra/llmath/lloctree.h @@ -48,52 +48,59 @@ extern float gOctreeMinSize; #define LL_OCTREE_MAX_CAPACITY 128 #endif*/ -template class LLOctreeNode; - -template +// T is the type of the element referenced by the octree node. +// T_PTR determines how pointers to elements are stored internally. +// LLOctreeNode> assumes ownership of inserted elements and +// deletes elements removed from the tree. +// LLOctreeNode doesn't take ownership of inserted elements, so the API +// user is responsible for managing the storage lifecycle of elements added to +// the tree. +template class LLOctreeNode; + +template class LLOctreeListener: public LLTreeListener { public: typedef LLTreeListener BaseType; - typedef LLOctreeNode oct_node; + typedef LLOctreeNode oct_node; virtual void handleChildAddition(const oct_node* parent, oct_node* child) = 0; virtual void handleChildRemoval(const oct_node* parent, const oct_node* child) = 0; }; -template +template class LLOctreeTraveler { public: - virtual void traverse(const LLOctreeNode* node); - virtual void visit(const LLOctreeNode* branch) = 0; + virtual void traverse(const LLOctreeNode* node); + virtual void visit(const LLOctreeNode* branch) = 0; }; -template -class LLOctreeTravelerDepthFirst : public LLOctreeTraveler +template +class LLOctreeTravelerDepthFirst : public LLOctreeTraveler { public: - virtual void traverse(const LLOctreeNode* node) override; + virtual void traverse(const LLOctreeNode* node) override; }; -template +template class alignas(16) LLOctreeNode : public LLTreeNode { LL_ALIGN_NEW public: - typedef LLOctreeTraveler oct_traveler; - typedef LLTreeTraveler tree_traveler; - typedef std::vector< LLPointer > element_list; // note: don't remove the whitespace between "> >" + typedef LLOctreeTraveler oct_traveler; + typedef LLTreeTraveler tree_traveler; + typedef std::vector element_list; typedef typename element_list::iterator element_iter; typedef typename element_list::const_iterator const_element_iter; typedef typename std::vector*>::iterator tree_listener_iter; - typedef LLOctreeNode** child_list; - typedef LLOctreeNode** child_iter; + typedef LLOctreeNode** child_list; + typedef LLOctreeNode** child_iter; - typedef LLTreeNode BaseType; - typedef LLOctreeNode oct_node; - typedef LLOctreeListener oct_listener; + typedef LLTreeNode BaseType; + typedef LLOctreeNode oct_node; + typedef LLOctreeListener oct_listener; enum { @@ -255,7 +262,7 @@ public: U8 idx = mChildMap[i]; if (idx != NO_CHILD_NODES) { - LLOctreeNode* child = mChild[idx]; + oct_node* child = mChild[idx]; if (child->getOctant() != i) { @@ -273,7 +280,7 @@ public: oct_node* getNodeAt(const LLVector4a& pos, const F32& rad) { - LLOctreeNode* node = this; + oct_node* node = this; if (node->isInside(pos, rad)) { @@ -295,7 +302,7 @@ public: } else if (!node->contains(rad) && node->getParent()) { //if we got here, data does not exist in this node - return ((LLOctreeNode*) node->getParent())->getNodeAt(pos, rad); + return ((oct_node*) node->getParent())->getNodeAt(pos, rad); } return node; @@ -310,7 +317,7 @@ public: OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << LL_ENDL; return false; } - LLOctreeNode* parent = getOctParent(); + oct_node* parent = getOctParent(); //is it here? if (isInside(data->getPositionGroup())) @@ -343,7 +350,7 @@ public: size.mul(0.5f); //push center in direction of data - LLOctreeNode::pushCenter(center, size, data); + oct_node::pushCenter(center, size, data); // handle case where floating point number gets too small LLVector4a val; @@ -382,7 +389,7 @@ public: llassert(size[0] >= gOctreeMinSize*0.5f); //make the new kid - child = new LLOctreeNode(center, size, this); + child = new oct_node(center, size, this); addChild(child); child->insert(data); @@ -502,7 +509,7 @@ public: for (U32 i = 0; i < getChildCount(); i++) { //we don't contain data, so pass this guy down - LLOctreeNode* child = (LLOctreeNode*) getChild(i); + oct_node* child = (oct_node*) getChild(i); child->removeByAddress(data); } } @@ -656,7 +663,7 @@ protected: oct_node* mParent; U8 mOctant; - LLOctreeNode* mChild[8]; + oct_node* mChild[8]; U8 mChildMap[8]; U32 mChildCount; @@ -664,12 +671,12 @@ protected: }; //just like a regular node, except it might expand on insert and compress on balance -template -class LLOctreeRoot : public LLOctreeNode +template +class LLOctreeRoot : public LLOctreeNode { public: - typedef LLOctreeNode BaseType; - typedef LLOctreeNode oct_node; + typedef LLOctreeNode BaseType; + typedef LLOctreeNode oct_node; LLOctreeRoot(const LLVector4a& center, const LLVector4a& size, @@ -750,7 +757,7 @@ public: oct_node* node = this->getNodeAt(data); if (node == this) { - LLOctreeNode::insert(data); + oct_node::insert(data); } else if (node->isInside(data->getPositionGroup())) { @@ -770,13 +777,13 @@ public: LLVector4a center, size; center = this->getCenter(); size = this->getSize(); - LLOctreeNode::pushCenter(center, size, data); + oct_node::pushCenter(center, size, data); this->setCenter(center); size.mul(2.f); this->setSize(size); this->updateMinMax(); } - LLOctreeNode::insert(data); + oct_node::insert(data); } else { @@ -788,7 +795,7 @@ public: //expand this node LLVector4a newcenter(center); - LLOctreeNode::pushCenter(newcenter, size, data); + oct_node::pushCenter(newcenter, size, data); this->setCenter(newcenter); LLVector4a size2 = size; size2.mul(2.f); @@ -798,11 +805,11 @@ public: llassert(size[0] >= gOctreeMinSize); //copy our children to a new branch - LLOctreeNode* newnode = new LLOctreeNode(center, size, this); + oct_node* newnode = new oct_node(center, size, this); for (U32 i = 0; i < this->getChildCount(); i++) { - LLOctreeNode* child = this->getChild(i); + oct_node* child = this->getChild(i); newnode->addChild(child); } @@ -828,8 +835,8 @@ public: //======================== // LLOctreeTraveler //======================== -template -void LLOctreeTraveler::traverse(const LLOctreeNode* node) +template +void LLOctreeTraveler::traverse(const LLOctreeNode* node) { node->accept(this); for (U32 i = 0; i < node->getChildCount(); i++) @@ -838,8 +845,8 @@ void LLOctreeTraveler::traverse(const LLOctreeNode* node) } } -template -void LLOctreeTravelerDepthFirst::traverse(const LLOctreeNode* node) +template +void LLOctreeTravelerDepthFirst::traverse(const LLOctreeNode* node) { for (U32 i = 0; i < node->getChildCount(); i++) { -- cgit v1.2.3