diff options
-rw-r--r-- | indra/llmath/lloctree.h | 89 | ||||
-rw-r--r-- | indra/llmath/llvolume.cpp | 21 | ||||
-rw-r--r-- | indra/llmath/llvolume.h | 7 | ||||
-rw-r--r-- | indra/llmath/llvolumeoctree.cpp | 18 | ||||
-rw-r--r-- | indra/llmath/llvolumeoctree.h | 20 | ||||
-rw-r--r-- | indra/newview/llspatialpartition.cpp | 6 | ||||
-rw-r--r-- | indra/newview/llvieweroctree.h | 16 |
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) |