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.

7 files changed, 96 insertions, 81 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++)
 	{
diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index 3de5e04177..414e96f67a 100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -370,7 +370,7 @@ BOOL LLTriangleRayIntersect(const LLVector3& vert0, const LLVector3& vert1, cons
 	}
 }
 
-class LLVolumeOctreeRebound : public LLOctreeTravelerDepthFirst<LLVolumeTriangle>
+class LLVolumeOctreeRebound : public LLOctreeTravelerDepthFirst<LLVolumeTriangle, LLVolumeTriangle*>
 {
 public:
 	const LLVolumeFace* mFace;
@@ -380,7 +380,7 @@ public:
 		mFace = face;
 	}
 
-	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* branch)
+    virtual void visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* branch)
 	{ //this is a depth first traversal, so it's safe to assum all children have complete
 		//bounding data
 	LL_PROFILE_ZONE_SCOPED_CATEGORY_VOLUME
@@ -398,8 +398,7 @@ public:
 			min = *(tri->mV[0]);
 			max = *(tri->mV[0]);
 			
-			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
-				branch->getDataBegin(); iter != branch->getDataEnd(); ++iter)
+            for (LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>::const_element_iter iter = branch->getDataBegin(); iter != branch->getDataEnd(); ++iter)
 			{ //for each triangle in node
 
 				//stretch by triangles in node
@@ -4874,6 +4873,8 @@ void LLVolumeFace::freeData()
 
 	delete mOctree;
 	mOctree = NULL;
+    mOctreeTriangles.clear();
+    mOctreeTriangles.shrink_to_fit();
 }
 
 BOOL LLVolumeFace::create(LLVolume* volume, BOOL partial_build)
@@ -4883,6 +4884,8 @@ BOOL LLVolumeFace::create(LLVolume* volume, BOOL partial_build)
 	//tree for this face is no longer valid
 	delete mOctree;
 	mOctree = NULL;
+    mOctreeTriangles.clear();
+    mOctreeTriangles.shrink_to_fit();
 
 	LL_CHECK_MEMORY
 	BOOL ret = FALSE ;
@@ -5556,12 +5559,18 @@ void LLVolumeFace::createOctree(F32 scaler, const LLVector4a& center, const LLVe
 		return;
 	}
 
-	mOctree = new LLOctreeRoot<LLVolumeTriangle>(center, size, NULL);
+    mOctree = new LLOctreeRoot<LLVolumeTriangle, LLVolumeTriangle*>(center, size, NULL);
 	new LLVolumeOctreeListener(mOctree);
+    // Clear old triangles, but keep the underlying storage pointer
+    mOctreeTriangles.clear();
+    const U32 num_triangles = mNumIndices / 3;
+    // Initialize all the triangles we need
+    mOctreeTriangles.resize(num_triangles);
 
 	for (U32 i = 0; i < mNumIndices; i+= 3)
 	{ //for each triangle
-		LLPointer<LLVolumeTriangle> tri = new LLVolumeTriangle();
+        const U32 triangle_index = i / 3;
+        LLVolumeTriangle* tri = &mOctreeTriangles[triangle_index];
 				
 		const LLVector4a& v0 = mPositions[mIndices[i]];
 		const LLVector4a& v1 = mPositions[mIndices[i+1]];
diff --git a/indra/llmath/llvolume.h b/indra/llmath/llvolume.h
index c0b224b1ff..da155c7b41 100644
--- a/indra/llmath/llvolume.h
+++ b/indra/llmath/llvolume.h
@@ -35,7 +35,8 @@ class LLVolumeParams;
 class LLProfile;
 class LLPath;
 
-template <class T> class LLOctreeNode;
+template<class T> class LLPointer;
+template <class T, typename T_PTR> class LLOctreeNode;
 
 class LLVolumeFace;
 class LLVolume;
@@ -974,7 +975,9 @@ public:
     // vertices per joint.
     LLJointRiggingInfoTab mJointRiggingInfoTab;
     
-	LLOctreeNode<LLVolumeTriangle>* mOctree;
+    // This octree stores raw pointer references to triangles in mOctreeTriangles
+    LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* mOctree;
+    std::vector<LLVolumeTriangle> mOctreeTriangles;
 
 	//whether or not face has been cache optimized
 	BOOL mOptimized;
diff --git a/indra/llmath/llvolumeoctree.cpp b/indra/llmath/llvolumeoctree.cpp
index fb232d5f6c..6894d04d3c 100644
--- a/indra/llmath/llvolumeoctree.cpp
+++ b/indra/llmath/llvolumeoctree.cpp
@@ -75,7 +75,7 @@ BOOL LLLineSegmentBoxIntersect(const LLVector4a& start, const LLVector4a& end, c
 }
 
 
-LLVolumeOctreeListener::LLVolumeOctreeListener(LLOctreeNode<LLVolumeTriangle>* node)
+LLVolumeOctreeListener::LLVolumeOctreeListener(LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node)
 {
 	node->addListener(this);
 }
@@ -85,13 +85,12 @@ LLVolumeOctreeListener::~LLVolumeOctreeListener()
 
 }
 	
-void LLVolumeOctreeListener::handleChildAddition(const LLOctreeNode<LLVolumeTriangle>* parent, 
-	LLOctreeNode<LLVolumeTriangle>* child)
+void LLVolumeOctreeListener::handleChildAddition(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* parent, 
+    LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* child)
 {
 	new LLVolumeOctreeListener(child);
 }
 
-
 LLOctreeTriangleRayIntersect::LLOctreeTriangleRayIntersect(const LLVector4a& start, const LLVector4a& dir, 
 							   const LLVolumeFace* face, F32* closest_t,
 							   LLVector4a* intersection,LLVector2* tex_coord, LLVector4a* normal, LLVector4a* tangent)
@@ -108,7 +107,7 @@ LLOctreeTriangleRayIntersect::LLOctreeTriangleRayIntersect(const LLVector4a& sta
 	mEnd.setAdd(mStart, mDir);
 }
 
-void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle>* node)
+void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node)
 {
 	LLVolumeOctreeListener* vl = (LLVolumeOctreeListener*) node->getListener(0);
 
@@ -122,9 +121,9 @@ void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle>
 	}
 }
 
-void LLOctreeTriangleRayIntersect::visit(const LLOctreeNode<LLVolumeTriangle>* node)
+void LLOctreeTriangleRayIntersect::visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node)
 {
-	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = 
+    for (typename LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>::const_element_iter iter =
 			node->getDataBegin(); iter != node->getDataEnd(); ++iter)
 	{
 		const LLVolumeTriangle* tri = *iter;
@@ -219,7 +218,7 @@ const F32& LLVolumeTriangle::getBinRadius() const
 
 //TEST CODE
 
-void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
+void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* branch)
 {
 	LLVolumeOctreeListener* node = (LLVolumeOctreeListener*) branch->getListener(0);
 
@@ -256,7 +255,7 @@ void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
 	}
 
 	//children fit, check data
-	for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getDataBegin(); 
+    for (typename LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>::const_element_iter iter = branch->getDataBegin();
 			iter != branch->getDataEnd(); ++iter)
 	{
 		const LLVolumeTriangle* tri = *iter;
@@ -273,4 +272,3 @@ void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
 	}
 }
 
-
diff --git a/indra/llmath/llvolumeoctree.h b/indra/llmath/llvolumeoctree.h
index b2bc440368..d65bca5e52 100644
--- a/indra/llmath/llvolumeoctree.h
+++ b/indra/llmath/llvolumeoctree.h
@@ -77,11 +77,11 @@ public:
 
 };
 
-class alignas(16) LLVolumeOctreeListener : public LLOctreeListener<LLVolumeTriangle>
+class alignas(16) LLVolumeOctreeListener : public LLOctreeListener<LLVolumeTriangle, LLVolumeTriangle*>
 {
     LL_ALIGN_NEW
 public:
-	LLVolumeOctreeListener(LLOctreeNode<LLVolumeTriangle>* node);
+    LLVolumeOctreeListener(LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node);
 	~LLVolumeOctreeListener();
 	
 	LLVolumeOctreeListener(const LLVolumeOctreeListener& rhs)
@@ -96,11 +96,9 @@ public:
 	}
 
 	 //LISTENER FUNCTIONS
-	virtual void handleChildAddition(const LLOctreeNode<LLVolumeTriangle>* parent, 
-		LLOctreeNode<LLVolumeTriangle>* child);
+    virtual void handleChildAddition(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* parent, LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* child);
 	virtual void handleStateChange(const LLTreeNode<LLVolumeTriangle>* node) { }
-	virtual void handleChildRemoval(const LLOctreeNode<LLVolumeTriangle>* parent, 
-			const LLOctreeNode<LLVolumeTriangle>* child) {	}
+    virtual void handleChildRemoval(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* parent, const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* child) { }
 	virtual void handleInsertion(const LLTreeNode<LLVolumeTriangle>* node, LLVolumeTriangle* tri) { }
 	virtual void handleRemoval(const LLTreeNode<LLVolumeTriangle>* node, LLVolumeTriangle* tri) { }
 	virtual void handleDestruction(const LLTreeNode<LLVolumeTriangle>* node) { }
@@ -111,7 +109,7 @@ public:
 	LL_ALIGN_16(LLVector4a mExtents[2]); // extents (min, max) of this node and all its children
 };
 
-class LLOctreeTriangleRayIntersect : public LLOctreeTraveler<LLVolumeTriangle>
+class LLOctreeTriangleRayIntersect : public LLOctreeTraveler<LLVolumeTriangle, LLVolumeTriangle*>
 {
 public:
 	const LLVolumeFace* mFace;
@@ -129,14 +127,14 @@ public:
 								   const LLVolumeFace* face, F32* closest_t,
 								   LLVector4a* intersection,LLVector2* tex_coord, LLVector4a* normal, LLVector4a* tangent);
 
-	void traverse(const LLOctreeNode<LLVolumeTriangle>* node);
+    void traverse(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node);
 
-	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* node);
+    virtual void visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* node);
 };
 
-class LLVolumeOctreeValidate : public LLOctreeTraveler<LLVolumeTriangle>
+class LLVolumeOctreeValidate : public LLOctreeTraveler<LLVolumeTriangle, LLVolumeTriangle*>
 {
-	virtual void visit(const LLOctreeNode<LLVolumeTriangle>* branch);
+    virtual void visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* branch);
 };
 
 #endif
diff --git a/indra/newview/llspatialpartition.cpp b/indra/newview/llspatialpartition.cpp
index c16a1854be..9cfbe99df4 100644
--- a/indra/newview/llspatialpartition.cpp
+++ b/indra/newview/llspatialpartition.cpp
@@ -3087,7 +3087,7 @@ public:
 
 	}
 
-	void visit(const LLOctreeNode<LLVolumeTriangle>* branch)
+    void visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* branch)
 	{
 		LLVolumeOctreeListener* vl = (LLVolumeOctreeListener*) branch->getListener(0);
 
@@ -3129,7 +3129,7 @@ public:
 			}
 
 			gGL.begin(LLRender::TRIANGLES);
-			for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getDataBegin();
+            for (LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>::const_element_iter iter = branch->getDataBegin();
 					iter != branch->getDataEnd();
 					++iter)
 			{
@@ -3846,7 +3846,7 @@ BOOL LLSpatialPartition::isVisible(const LLVector3& v)
 }
 
 LL_ALIGN_PREFIX(16)
-class LLOctreeIntersect : public LLOctreeTraveler<LLViewerOctreeEntry>
+class LLOctreeIntersect : public LLOctreeTraveler<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>>
 {
 public:
 	LL_ALIGN_16(LLVector4a mStart);
diff --git a/indra/newview/llvieweroctree.h b/indra/newview/llvieweroctree.h
index 29f3d8cba9..7666062f99 100644
--- a/indra/newview/llvieweroctree.h
+++ b/indra/newview/llvieweroctree.h
@@ -45,11 +45,11 @@ class LLViewerOctreeGroup;
 class LLViewerOctreeEntry;
 class LLViewerOctreePartition;
 
-typedef LLOctreeListener<LLViewerOctreeEntry>	OctreeListener;
-typedef LLTreeNode<LLViewerOctreeEntry>			TreeNode;
-typedef LLOctreeNode<LLViewerOctreeEntry>		OctreeNode;
-typedef LLOctreeRoot<LLViewerOctreeEntry>		OctreeRoot;
-typedef LLOctreeTraveler<LLViewerOctreeEntry>	OctreeTraveler;
+typedef LLOctreeListener<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>> OctreeListener;
+typedef LLTreeNode<LLViewerOctreeEntry> TreeNode;
+typedef LLOctreeNode<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>> OctreeNode;
+typedef LLOctreeRoot<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>> OctreeRoot;
+typedef LLOctreeTraveler<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>> OctreeTraveler;
 
 #if LL_OCTREE_PARANOIA_CHECK
 #define assert_octree_valid(x) x->validate()
@@ -179,7 +179,7 @@ protected:
 //defines an octree group for an octree node, which contains multiple entries.
 //LL_ALIGN_PREFIX(16)
 class LLViewerOctreeGroup
-:	public LLOctreeListener<LLViewerOctreeEntry>
+:	public OctreeListener
 {
     LL_ALIGN_NEW
 	friend class LLViewerOctreeCull;
@@ -198,8 +198,8 @@ public:
 	};
 
 public:
-	typedef LLOctreeNode<LLViewerOctreeEntry>::element_iter element_iter;
-	typedef LLOctreeNode<LLViewerOctreeEntry>::element_list element_list;
+	typedef OctreeNode::element_iter element_iter;
+	typedef OctreeNode::element_list element_list;
 
 	LLViewerOctreeGroup(OctreeNode* node);
 	LLViewerOctreeGroup(const LLViewerOctreeGroup& rhs)