From 38d6d37f2d982fa959e9e8a4a3f7e1ccfad7b5d4 Mon Sep 17 00:00:00 2001 From: Jacek Antonelli Date: Fri, 15 Aug 2008 23:44:46 -0500 Subject: Second Life viewer sources 1.13.2.12 --- linden/indra/llmath/lloctree.h | 712 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 712 insertions(+) create mode 100644 linden/indra/llmath/lloctree.h (limited to 'linden/indra/llmath/lloctree.h') diff --git a/linden/indra/llmath/lloctree.h b/linden/indra/llmath/lloctree.h new file mode 100644 index 0000000..6e068cd --- /dev/null +++ b/linden/indra/llmath/lloctree.h @@ -0,0 +1,712 @@ +/** + * @file lloctree.h + * @brief Octree declaration. + * + * Copyright (c) 2005-2007, Linden Research, Inc. + * + * The source code in this file ("Source Code") is provided by Linden Lab + * to you under the terms of the GNU General Public License, version 2.0 + * ("GPL"), unless you have obtained a separate licensing agreement + * ("Other License"), formally executed by you and Linden Lab. Terms of + * the GPL can be found in doc/GPL-license.txt in this distribution, or + * online at http://secondlife.com/developers/opensource/gplv2 + * + * There are special exceptions to the terms and conditions of the GPL as + * it is applied to this Source Code. View the full text of the exception + * in the file doc/FLOSS-exception.txt in this software distribution, or + * online at http://secondlife.com/developers/opensource/flossexception + * + * By copying, modifying or distributing this software, you acknowledge + * that you have read and understood your obligations described above, + * and agree to abide by those obligations. + * + * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO + * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY, + * COMPLETENESS OR PERFORMANCE. + */ + +#ifndef LL_LLOCTREE_H +#define LL_LLOCTREE_H + +#include "lltreenode.h" +#include "v3math.h" +#include +#include + +#ifdef LL_RELEASE_FOR_DOWNLOAD +#define OCT_ERRS llwarns +#else +#define OCT_ERRS llerrs +#endif + +#define LL_OCTREE_PARANOIA_CHECK 0 + +template class LLOctreeState; +template class LLOctreeNode; + +template +class LLOctreeListener: public LLTreeListener +{ +public: + typedef LLTreeListener BaseType; + typedef LLOctreeNode oct_node; + + virtual ~LLOctreeListener() { }; + 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 LLOctreeNode : public LLTreeNode +{ +public: + + typedef LLTreeNode BaseType; + typedef LLTreeState tree_state; + typedef LLOctreeState oct_state; + typedef LLOctreeNode oct_node; + typedef LLOctreeListener oct_listener; + + static const U8 OCTANT_POSITIVE_X = 0x01; + static const U8 OCTANT_POSITIVE_Y = 0x02; + static const U8 OCTANT_POSITIVE_Z = 0x04; + + LLOctreeNode( LLVector3d center, + LLVector3d size, + tree_state* state, + BaseType* parent, + U8 octant = 255) + : BaseType(state), + mParent((oct_node*)parent), + mCenter(center), + mSize(size), + mOctant(octant) + { + updateMinMax(); + if ((mOctant == 255) && mParent) + { + mOctant = ((oct_node*) mParent)->getOctant(mCenter.mdV); + } + } + + virtual ~LLOctreeNode() { BaseType::destroyListeners(); delete this->mState; } + + virtual const BaseType* getParent() const { return mParent; } + virtual void setParent(BaseType* parent) { mParent = (oct_node*) parent; } + virtual const LLVector3d& getCenter() const { return mCenter; } + virtual const LLVector3d& getSize() const { return mSize; } + virtual void setCenter(LLVector3d center) { mCenter = center; } + virtual void setSize(LLVector3d size) { mSize = size; } + virtual bool balance() { return getOctState()->balance(); } + virtual void validate() { getOctState()->validate(); } + virtual U32 getChildCount() const { return getOctState()->getChildCount(); } + virtual oct_node* getChild(U32 index) { return getOctState()->getChild(index); } + virtual const oct_node* getChild(U32 index) const { return getOctState()->getChild(index); } + virtual U32 getElementCount() const { return getOctState()->getElementCount(); } + virtual void removeByAddress(T* data) { getOctState()->removeByAddress(data); } + virtual bool hasLeafState() const { return getOctState()->isLeaf(); } + virtual void destroy() { getOctState()->destroy(); } + virtual oct_node* getNodeAt(T* data) { return getOctState()->getNodeAt(data); } + virtual U8 getOctant() const { return mOctant; } + virtual void setOctant(U8 octant) { mOctant = octant; } + virtual const oct_state* getOctState() const { return (const oct_state*) BaseType::mState; } + virtual oct_state* getOctState() { return (oct_state*) BaseType::mState; } + virtual const oct_node* getOctParent() const { return (const oct_node*) getParent(); } + virtual oct_node* getOctParent() { return (oct_node*) getParent(); } + virtual void deleteChild(oct_node* child) { getOctState()->deleteChild(child); } + + virtual U8 getOctant(const F64 pos[]) const //get the octant pos is in + { + U8 ret = 0; + + if (pos[0] > mCenter.mdV[0]) + { + ret |= OCTANT_POSITIVE_X; + } + if (pos[1] > mCenter.mdV[1]) + { + ret |= OCTANT_POSITIVE_Y; + } + if (pos[2] > mCenter.mdV[2]) + { + ret |= OCTANT_POSITIVE_Z; + } + + return ret; + } + + virtual bool isInside(T* data) const + { + return data->getBinRadius() <= mSize.mdV[0]*2.0 && isInside(data->getPositionGroup()); + } + + virtual bool isInside(const LLVector3d& pos) const + { + const F64& x = pos.mdV[0]; + const F64& y = pos.mdV[1]; + const F64& z = pos.mdV[2]; + + if (x > mMax.mdV[0] || x <= mMin.mdV[0] || + y > mMax.mdV[1] || y <= mMin.mdV[1] || + z > mMax.mdV[2] || z <= mMin.mdV[2]) + { + return false; + } + + return true; + } + + virtual void updateMinMax() + { + for (U32 i = 0; i < 3; i++) + { + mMax.mdV[i] = mCenter.mdV[i] + mSize.mdV[i]; + mMin.mdV[i] = mCenter.mdV[i] - mSize.mdV[i]; + mCenter.mdV[i] = mCenter.mdV[i]; + } + } + + virtual oct_listener* getOctListener(U32 index) + { + return (oct_listener*) BaseType::getListener(index); + } + + bool contains(T* xform) + { + if (mParent == NULL) + { //root node contains nothing + return false; + } + + F64 size = mSize.mdV[0]; + F64 p_size = size * 2.0; + F64 radius = xform->getBinRadius(); + + return (radius <= 0.001 && size <= 0.001) || + (radius <= p_size && radius > size); + } + + static void pushCenter(LLVector3d ¢er, LLVector3d &size, T* data) + { + LLVector3 pos(data->getPositionGroup()); + F64 p[] = + { + (F64) pos.mV[0], + (F64) pos.mV[1], + (F64) pos.mV[2] + }; + + for (U32 i = 0; i < 3; i++) + { + if (p[i] > center.mdV[i]) + { + center.mdV[i] += size.mdV[i]; + } + else + { + center.mdV[i] -= size.mdV[i]; + } + } + } + +protected: + oct_node* mParent; + LLVector3d mCenter; + LLVector3d mSize; + LLVector3d mMax; + LLVector3d mMin; + U8 mOctant; +}; + +template +class LLOctreeTraveler : public LLTreeTraveler +{ +public: + virtual void traverse(const LLTreeNode* node); + virtual void visit(const LLTreeState* state) { } + virtual void visit(const LLOctreeState* branch) = 0; +}; + +//will pass requests to a child, might make a new child +template +class LLOctreeState : public LLTreeState +{ +public: + typedef LLTreeState BaseType; + typedef LLOctreeTraveler oct_traveler; + typedef LLOctreeNode oct_node; + typedef LLOctreeListener oct_listener; + typedef LLTreeTraveler tree_traveler; + typedef typename std::set > element_list; + typedef typename std::set >::iterator element_iter; + typedef typename std::set >::const_iterator const_element_iter; + typedef typename std::vector*>::iterator tree_listener_iter; + typedef typename std::vector* > child_list; + + LLOctreeState(oct_node* node = NULL): BaseType(node) { this->clearChildren(); } + virtual ~LLOctreeState() + { + for (U32 i = 0; i < getChildCount(); i++) + { + delete getChild(i); + } + } + + + virtual void accept(oct_traveler* visitor) { visitor->visit(this); } + virtual bool isLeaf() const { return mChild.empty(); } + + virtual U32 getElementCount() const { return mData.size(); } + virtual element_list& getData() { return mData; } + virtual const element_list& getData() const { return mData; } + + virtual U32 getChildCount() const { return mChild.size(); } + virtual oct_node* getChild(U32 index) { return mChild[index]; } + virtual const oct_node* getChild(U32 index) const { return mChild[index]; } + virtual child_list& getChildren() { return mChild; } + virtual const child_list& getChildren() const { return mChild; } + + virtual void accept(tree_traveler* visitor) const { visitor->visit(this); } + virtual void accept(oct_traveler* visitor) const { visitor->visit(this); } + const oct_node* getOctNode() const { return (const oct_node*) BaseType::getNode(); } + oct_node* getOctNode() { return (oct_node*) BaseType::getNode(); } + + virtual oct_node* getNodeAt(T* data) + { + const LLVector3d& pos = data->getPositionGroup(); + LLOctreeNode* node = getOctNode(); + + if (node->isInside(data)) + { + //do a quick search by octant + U8 octant = node->getOctant(pos.mdV); + BOOL keep_going = TRUE; + + //traverse the tree until we find a node that has no node + //at the appropriate octant or is smaller than the object. + //by definition, that node is the smallest node that contains + // the data + while (keep_going && node->getSize().mdV[0] >= data->getBinRadius()) + { + keep_going = FALSE; + for (U32 i = 0; i < node->getChildCount() && !keep_going; i++) + { + if (node->getChild(i)->getOctant() == octant) + { + node = node->getChild(i); + octant = node->getOctant(pos.mdV); + keep_going = TRUE; + } + } + } + } + else if (!node->contains(data) && node->getParent()) + { //if we got here, data does not exist in this node + return ((LLOctreeNode*) node->getParent())->getNodeAt(data); + } + + return node; + } + + virtual bool insert(T* data) + { + if (data == NULL) + { + OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl; + return false; + } + LLOctreeNode* node = getOctNode(); + + if (data->getBinRadius() <= node->getSize().mdV[0]) + { + oct_node* dest = getNodeAt(data); + + if (dest != node) + { + dest->insert(data); + return false; + } + } + + //no kid found, is it even here? + if (node->isInside(data)) + { + if (node->contains(data)) + { //it belongs here + if (data == NULL) + { + OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE LEAF !!!" << llendl; + return false; + } + +#if LL_OCTREE_PARANOIA_CHECK + //if this is a redundant insertion, error out (should never happen) + if (mData.find(data) != mData.end()) + { + llwarns << "Redundant octree insertion detected. " << data << llendl; + return false; + } +#endif + + mData.insert(data); + return true; + } + else + { + //it's here, but no kids are in the right place, make a new kid + LLVector3d center(node->getCenter()); + LLVector3d size(node->getSize()*0.5); + + //push center in direction of data + LLOctreeNode::pushCenter(center, size, data); + +#if LL_OCTREE_PARANOIA_CHECK + if (getChildCount() == 8) + { + //this really isn't possible, something bad has happened + OCT_ERRS << "Octree detected floating point error and gave up." << llendl; + //bool check = node->isInside(data); + return false; + } + + //make sure no existing node matches this position + for (U32 i = 0; i < getChildCount(); i++) + { + if (mChild[i]->getCenter() == center) + { + OCT_ERRS << "Octree detected duplicate child center and gave up." << llendl; + //bool check = node->isInside(data); + //check = getChild(i)->isInside(data); + return false; + } + } +#endif + + //make the new kid + LLOctreeState* newstate = new LLOctreeState(); + oct_node* child = new LLOctreeNode(center, size, newstate, node); + addChild(child); + + child->insert(data); + } + } + else + { + //it's not in here, give it to the parent + node->getOctParent()->insert(data); + } + + return false; + } + + virtual bool remove(T* data) + { + oct_node* node = getOctNode(); + + if (mData.find(data) != mData.end()) + { //we have data + mData.erase(data); + node->notifyRemoval(data); + checkAlive(); + return true; + } + else if (node->isInside(data)) + { + oct_node* dest = getNodeAt(data); + + if (dest != node) + { + return dest->remove(data); + } + } + + //SHE'S GONE MISSING... + //none of the children have it, let's just brute force this bastard out + //starting with the root node (UGLY CODE COMETH!) + oct_node* parent = node->getOctParent(); + while (parent != NULL) + { + node = parent; + parent = node->getOctParent(); + } + + //node is now root + llwarns << "!!! OCTREE REMOVING FACE BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl; + node->removeByAddress(data); + return true; + } + + virtual void removeByAddress(T* data) + { + if (mData.find(data) != mData.end()) + { + mData.erase(data); + getOctNode()->notifyRemoval(data); + llwarns << "FOUND!" << llendl; + checkAlive(); + return; + } + + for (U32 i = 0; i < getChildCount(); i++) + { //we don't contain data, so pass this guy down + LLOctreeNode* child = (LLOctreeNode*) getChild(i); + child->removeByAddress(data); + } + } + + virtual void clearChildren() + { + mChild.clear(); + } + + virtual void validate() + { +#if LL_OCTREE_PARANOIA_CHECK + LLOctreeNode* node = this->getOctNode(); + + for (U32 i = 0; i < getChildCount(); i++) + { + mChild[i]->validate(); + if (mChild[i]->getParent() != node) + { + llerrs << "Octree child has invalid parent." << llendl; + } + } +#endif + } + + virtual bool balance() + { + return false; + } + + virtual void destroy() + { + for (U32 i = 0; i < getChildCount(); i++) + { + mChild[i]->destroy(); + delete mChild[i]; + } + } + + virtual void addChild(oct_node* child, BOOL silent = FALSE) + { +#if LL_OCTREE_PARANOIA_CHECK + for (U32 i = 0; i < getChildCount(); i++) + { + if(mChild[i]->getSize() != child->getSize()) + { + OCT_ERRS <<"Invalid octree child size." << llendl; + } + if (mChild[i]->getCenter() == child->getCenter()) + { + OCT_ERRS <<"Duplicate octree child position." << llendl; + } + } + + if (mChild.size() >= 8) + { + OCT_ERRS <<"Octree node has too many children... why?" << llendl; + } +#endif + + mChild.push_back(child); + child->setParent(getOctNode()); + + if (!silent) + { + oct_node* node = getOctNode(); + + for (U32 i = 0; i < node->getListenerCount(); i++) + { + oct_listener* listener = node->getOctListener(i); + listener->handleChildAddition(node, child); + } + } + } + + virtual void removeChild(U8 index, BOOL destroy = FALSE) + { + oct_node* node = getOctNode(); + for (U32 i = 0; i < node->getListenerCount(); i++) + { + oct_listener* listener = node->getOctListener(i); + listener->handleChildRemoval(node, getChild(index)); + } + + if (destroy) + { + mChild[index]->destroy(); + delete mChild[index]; + } + mChild.erase(mChild.begin() + index); + + checkAlive(); + } + + virtual void checkAlive() + { + if (getChildCount() == 0 && getElementCount() == 0) + { + oct_node* node = getOctNode(); + oct_node* parent = node->getOctParent(); + if (parent) + { + parent->deleteChild(node); + } + } + } + + virtual void deleteChild(oct_node* node) + { + for (U32 i = 0; i < getChildCount(); i++) + { + if (getChild(i) == node) + { + removeChild(i, TRUE); + return; + } + } + + OCT_ERRS << "Octree failed to delete requested child." << llendl; + } + +protected: + child_list mChild; + element_list mData; +}; + +//just like a branch, except it might expand the node it points to +template +class LLOctreeRoot : public LLOctreeState +{ +public: + typedef LLOctreeState BaseType; + typedef LLOctreeNode oct_node; + + LLOctreeRoot(oct_node* node = NULL) : BaseType(node) { } + + oct_node* getOctNode() { return BaseType::getOctNode(); } + virtual bool isLeaf() { return false; } + + virtual bool balance() + { + //the cached node might be invalid, so don't reference it + if (this->getChildCount() == 1 && + !(this->mChild[0]->hasLeafState()) && + this->mChild[0]->getElementCount() == 0) + { //if we have only one child and that child is an empty branch, make that child the root + BaseType* state = this->mChild[0]->getOctState(); + oct_node* child = this->mChild[0]; + oct_node* root = getOctNode(); + + //make the root node look like the child + root->setCenter(this->mChild[0]->getCenter()); + root->setSize(this->mChild[0]->getSize()); + root->updateMinMax(); + + //reset root node child list + this->clearChildren(); + + //copy the child's children into the root node silently + //(don't notify listeners of addition) + for (U32 i = 0; i < state->getChildCount(); i++) + { + addChild(state->getChild(i), TRUE); + } + + //destroy child + state->clearChildren(); + delete child; + } + + return true; + } + + // LLOctreeRoot::insert + virtual bool insert(T* data) + { + if (data == NULL) + { + OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl; + return false; + } + + if (data->getBinRadius() > 4096.0) + { + OCT_ERRS << "!!! ELEMENT EXCEDES MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl; + } + + LLOctreeNode* node = getOctNode(); + if (node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup())) + { + //we got it, just act like a branch + LLOctreeState::insert(data); + } + else if (this->getChildCount() == 0) + { + //first object being added, just wrap it up + while (!(node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup()))) + { + LLVector3d center, size; + center = node->getCenter(); + size = node->getSize(); + LLOctreeNode::pushCenter(center, size, data); + node->setCenter(center); + node->setSize(size*2); + node->updateMinMax(); + } + LLOctreeState::insert(data); + } + else + { + //the data is outside the root node, we need to grow + LLVector3d center(node->getCenter()); + LLVector3d size(node->getSize()); + + //expand this node + LLVector3d newcenter(center); + LLOctreeNode::pushCenter(newcenter, size, data); + node->setCenter(newcenter); + node->setSize(size*2); + node->updateMinMax(); + + //copy our children to a new branch + LLOctreeState* newstate = new LLOctreeState(); + LLOctreeNode* newnode = new LLOctreeNode(center, size, newstate, node); + + for (U32 i = 0; i < this->getChildCount(); i++) + { + LLOctreeNode* child = this->getChild(i); + newstate->addChild(child); + } + + //clear our children and add the root copy + this->clearChildren(); + addChild(newnode); + + //insert the data + node->insert(data); + } + + return false; + } +}; + + +//======================== +// LLOctreeTraveler +//======================== +template +void LLOctreeTraveler::traverse(const LLTreeNode* node) +{ + const LLOctreeState* state = (const LLOctreeState*) node->getState(); + state->accept(this); + for (U32 i = 0; i < state->getChildCount(); i++) + { + traverse(state->getChild(i)); + } +} + +#endif -- cgit v1.1