summaryrefslogtreecommitdiff
path: root/indra/llmath/lloctree.h
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llmath/lloctree.h')
-rw-r--r--indra/llmath/lloctree.h89
1 files changed, 48 insertions, 41 deletions
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 T> class LLOctreeNode;
-
-template <class T>
+// T is the type of the element referenced by the octree node.
+// T_PTR determines how pointers to elements are stored internally.
+// LLOctreeNode<T, LLPointer<T>> assumes ownership of inserted elements and
+// deletes elements removed from the tree.
+// LLOctreeNode<T, T*> 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 T, typename T_PTR> class LLOctreeNode;
+
+template <class T, typename T_PTR>
class LLOctreeListener: public LLTreeListener<T>
{
public:
typedef LLTreeListener<T> BaseType;
- typedef LLOctreeNode<T> oct_node;
+ typedef LLOctreeNode<T, T_PTR> 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 <class T>
+template <class T, typename T_PTR>
class LLOctreeTraveler
{
public:
- virtual void traverse(const LLOctreeNode<T>* node);
- virtual void visit(const LLOctreeNode<T>* branch) = 0;
+ virtual void traverse(const LLOctreeNode<T, T_PTR>* node);
+ virtual void visit(const LLOctreeNode<T, T_PTR>* branch) = 0;
};
-template <class T>
-class LLOctreeTravelerDepthFirst : public LLOctreeTraveler<T>
+template <class T, typename T_PTR>
+class LLOctreeTravelerDepthFirst : public LLOctreeTraveler<T, T_PTR>
{
public:
- virtual void traverse(const LLOctreeNode<T>* node) override;
+ virtual void traverse(const LLOctreeNode<T, T_PTR>* node) override;
};
-template <class T>
+template <class T, typename T_PTR>
class alignas(16) LLOctreeNode : public LLTreeNode<T>
{
LL_ALIGN_NEW
public:
- typedef LLOctreeTraveler<T> oct_traveler;
- typedef LLTreeTraveler<T> tree_traveler;
- typedef std::vector< LLPointer<T> > element_list; // note: don't remove the whitespace between "> >"
+ typedef LLOctreeTraveler<T, T_PTR> oct_traveler;
+ typedef LLTreeTraveler<T> tree_traveler;
+ typedef std::vector<T_PTR> element_list;
typedef typename element_list::iterator element_iter;
typedef typename element_list::const_iterator const_element_iter;
typedef typename std::vector<LLTreeListener<T>*>::iterator tree_listener_iter;
- typedef LLOctreeNode<T>** child_list;
- typedef LLOctreeNode<T>** child_iter;
+ typedef LLOctreeNode<T, T_PTR>** child_list;
+ typedef LLOctreeNode<T, T_PTR>** child_iter;
- typedef LLTreeNode<T> BaseType;
- typedef LLOctreeNode<T> oct_node;
- typedef LLOctreeListener<T> oct_listener;
+ typedef LLTreeNode<T> BaseType;
+ typedef LLOctreeNode<T, T_PTR> oct_node;
+ typedef LLOctreeListener<T, T_PTR> oct_listener;
enum
{
@@ -255,7 +262,7 @@ public:
U8 idx = mChildMap[i];
if (idx != NO_CHILD_NODES)
{
- LLOctreeNode<T>* 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<T>* 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<T>*) 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<T>* 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<T>::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<T>(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<T>* child = (LLOctreeNode<T>*) getChild(i);
+ oct_node* child = (oct_node*) getChild(i);
child->removeByAddress(data);
}
}
@@ -656,7 +663,7 @@ protected:
oct_node* mParent;
U8 mOctant;
- LLOctreeNode<T>* 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 T>
-class LLOctreeRoot : public LLOctreeNode<T>
+template <class T, typename T_PTR>
+class LLOctreeRoot : public LLOctreeNode<T, T_PTR>
{
public:
- typedef LLOctreeNode<T> BaseType;
- typedef LLOctreeNode<T> oct_node;
+ typedef LLOctreeNode<T, T_PTR> BaseType;
+ typedef LLOctreeNode<T, T_PTR> oct_node;
LLOctreeRoot(const LLVector4a& center,
const LLVector4a& size,
@@ -750,7 +757,7 @@ public:
oct_node* node = this->getNodeAt(data);
if (node == this)
{
- LLOctreeNode<T>::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<T>::pushCenter(center, size, data);
+ oct_node::pushCenter(center, size, data);
this->setCenter(center);
size.mul(2.f);
this->setSize(size);
this->updateMinMax();
}
- LLOctreeNode<T>::insert(data);
+ oct_node::insert(data);
}
else
{
@@ -788,7 +795,7 @@ public:
//expand this node
LLVector4a newcenter(center);
- LLOctreeNode<T>::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<T>* newnode = new LLOctreeNode<T>(center, size, this);
+ oct_node* newnode = new oct_node(center, size, this);
for (U32 i = 0; i < this->getChildCount(); i++)
{
- LLOctreeNode<T>* child = this->getChild(i);
+ oct_node* child = this->getChild(i);
newnode->addChild(child);
}
@@ -828,8 +835,8 @@ public:
//========================
// LLOctreeTraveler
//========================
-template <class T>
-void LLOctreeTraveler<T>::traverse(const LLOctreeNode<T>* node)
+template <class T, typename T_PTR>
+void LLOctreeTraveler<T, T_PTR>::traverse(const LLOctreeNode<T, T_PTR>* node)
{
node->accept(this);
for (U32 i = 0; i < node->getChildCount(); i++)
@@ -838,8 +845,8 @@ void LLOctreeTraveler<T>::traverse(const LLOctreeNode<T>* node)
}
}
-template <class T>
-void LLOctreeTravelerDepthFirst<T>::traverse(const LLOctreeNode<T>* node)
+template <class T, typename T_PTR>
+void LLOctreeTravelerDepthFirst<T, T_PTR>::traverse(const LLOctreeNode<T, T_PTR>* node)
{
for (U32 i = 0; i < node->getChildCount(); i++)
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 08:18:44 +0000