lloctree.h

Go to the documentation of this file.
00001 
00032 #ifndef LL_LLOCTREE_H
00033 #define LL_LLOCTREE_H
00034 
00035 #include "lltreenode.h"
00036 #include "v3math.h"
00037 #include <vector>
00038 #include <set>
00039 
00040 #ifdef LL_RELEASE_FOR_DOWNLOAD
00041 #define OCT_ERRS llwarns
00042 #else
00043 #define OCT_ERRS llerrs
00044 #endif
00045 
00046 #define LL_OCTREE_PARANOIA_CHECK 0
00047 #if LL_DARWIN
00048 #define LL_OCTREE_MAX_CAPACITY 32
00049 #else
00050 #define LL_OCTREE_MAX_CAPACITY 256
00051 #endif
00052 
00053 template <class T> class LLOctreeState;
00054 template <class T> class LLOctreeNode;
00055 
00056 template <class T>
00057 class LLOctreeListener: public LLTreeListener<T>
00058 {
00059 public:
00060         typedef LLTreeListener<T> BaseType;
00061         typedef LLOctreeNode<T> oct_node;
00062 
00063         virtual void handleChildAddition(const oct_node* parent, oct_node* child) = 0;
00064         virtual void handleChildRemoval(const oct_node* parent, const oct_node* child) = 0;
00065 };
00066 
00067 
00068 template <class T>
00069 class LLOctreeNode : public LLTreeNode<T>
00070 {
00071 public:
00072 
00073         typedef LLTreeNode<T>           BaseType;
00074         typedef LLTreeState<T>          tree_state;
00075         typedef LLOctreeState<T>        oct_state;
00076         typedef LLOctreeNode<T>         oct_node;
00077         typedef LLOctreeListener<T>     oct_listener;
00078 
00079         static const U8 OCTANT_POSITIVE_X = 0x01;
00080         static const U8 OCTANT_POSITIVE_Y = 0x02;
00081         static const U8 OCTANT_POSITIVE_Z = 0x04;
00082                 
00083         LLOctreeNode(   LLVector3d center, 
00084                                         LLVector3d size, 
00085                                         tree_state* state, 
00086                                         BaseType* parent, 
00087                                         U8 octant = 255)
00088         :       BaseType(state), 
00089                 mParent((oct_node*)parent), 
00090                 mCenter(center), 
00091                 mSize(size), 
00092                 mOctant(octant) 
00093         { 
00094                 updateMinMax();
00095                 if ((mOctant == 255) && mParent)
00096                 {
00097                         mOctant = ((oct_node*) mParent)->getOctant(mCenter.mdV);
00098                 }
00099         }
00100 
00101         ~LLOctreeNode()                                                         { BaseType::destroyListeners(); delete this->mState; }
00102 
00103         inline const BaseType* getParent()      const                   { return mParent; }
00104         inline void setParent(BaseType* parent)                 { mParent = (oct_node*) parent; }
00105         inline const LLVector3d& getCenter() const                      { return mCenter; }
00106         inline const LLVector3d& getSize() const                        { return mSize; }
00107         inline void setCenter(LLVector3d center)                        { mCenter = center; }
00108         inline void setSize(LLVector3d size)                            { mSize = size; }
00109     inline bool balance()                                                               { return getOctState()->balance(); }
00110         inline void validate()                                                          { getOctState()->validate(); }
00111         inline U32 getChildCount()      const                                   { return getOctState()->getChildCount(); }
00112         inline oct_node* getChild(U32 index)                            { return getOctState()->getChild(index); }
00113         inline const oct_node* getChild(U32 index) const        { return getOctState()->getChild(index); }
00114         inline U32 getElementCount() const                                      { return getOctState()->getElementCount(); }
00115         inline void removeByAddress(T* data)                            { getOctState()->removeByAddress(data); }
00116         inline bool hasLeafState()      const                                   { return getOctState()->isLeaf(); }
00117         inline void destroy()                                                           { getOctState()->destroy(); }
00118         inline oct_node* getNodeAt(T* data)                             { return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
00119         inline oct_node* getNodeAt(const LLVector3d& pos, const F64& rad) { return getOctState()->getNodeAt(pos, rad); }
00120         inline U8 getOctant() const                                             { return mOctant; }
00121         inline void setOctant(U8 octant)                                        { mOctant = octant; }
00122         inline const oct_state* getOctState() const             { return (const oct_state*) BaseType::mState; }
00123         inline oct_state* getOctState()                                 { return (oct_state*) BaseType::mState; }
00124         inline const oct_node*  getOctParent() const            { return (const oct_node*) getParent(); }
00125         inline oct_node* getOctParent()                                         { return (oct_node*) getParent(); }
00126         inline void deleteChild(oct_node* child)                        { getOctState()->deleteChild(child); }
00127 
00128         U8 getOctant(const F64 pos[]) const     //get the octant pos is in
00129         {
00130                 U8 ret = 0;
00131 
00132                 if (pos[0] > mCenter.mdV[0])
00133                 {
00134                         ret |= OCTANT_POSITIVE_X;
00135                 }
00136                 if (pos[1] > mCenter.mdV[1])
00137                 {
00138                         ret |= OCTANT_POSITIVE_Y;
00139                 }
00140                 if (pos[2] > mCenter.mdV[2])
00141                 {
00142                         ret |= OCTANT_POSITIVE_Z;
00143                 }
00144 
00145                 return ret;
00146         }
00147         
00148         inline bool isInside(const LLVector3d& pos, const F64& rad) const
00149         {
00150                 return rad <= mSize.mdV[0]*2.0 && isInside(pos); 
00151         }
00152 
00153         inline bool isInside(T* data) const                     
00154         { 
00155                 return isInside(data->getPositionGroup(), data->getBinRadius());
00156         }
00157 
00158         bool isInside(const LLVector3d& pos) const
00159         {
00160                 const F64& x = pos.mdV[0];
00161                 const F64& y = pos.mdV[1];
00162                 const F64& z = pos.mdV[2];
00163                         
00164                 if (x > mMax.mdV[0] || x <= mMin.mdV[0] ||
00165                         y > mMax.mdV[1] || y <= mMin.mdV[1] ||
00166                         z > mMax.mdV[2] || z <= mMin.mdV[2])
00167                 {
00168                         return false;
00169                 }
00170                 
00171                 return true;
00172         }
00173         
00174         void updateMinMax()
00175         {
00176                 for (U32 i = 0; i < 3; i++)
00177                 {
00178                         mMax.mdV[i] = mCenter.mdV[i] + mSize.mdV[i];
00179                         mMin.mdV[i] = mCenter.mdV[i] - mSize.mdV[i];
00180                         mCenter.mdV[i] = mCenter.mdV[i];
00181                 }
00182         }
00183 
00184         inline oct_listener* getOctListener(U32 index) 
00185         { 
00186                 return (oct_listener*) BaseType::getListener(index); 
00187         }
00188 
00189         inline bool contains(T* xform)
00190         {
00191                 return contains(xform->getBinRadius());
00192         }
00193 
00194         bool contains(F64 radius)
00195         {
00196                 if (mParent == NULL)
00197                 {       //root node contains nothing
00198                         return false;
00199                 }
00200 
00201                 F64 size = mSize.mdV[0];
00202                 F64 p_size = size * 2.0;
00203 
00204                 return (radius <= 0.001 && size <= 0.001) ||
00205                                 (radius <= p_size && radius > size);
00206         }
00207 
00208         static void pushCenter(LLVector3d &center, LLVector3d &size, T* data)
00209         {
00210                 LLVector3d pos(data->getPositionGroup());
00211                 for (U32 i = 0; i < 3; i++)
00212                 {
00213                         if (pos.mdV[i] > center.mdV[i])
00214                         {
00215                                 center.mdV[i] += size.mdV[i];
00216                         }
00217                         else 
00218                         {
00219                                 center.mdV[i] -= size.mdV[i];
00220                         }
00221                 }
00222         }
00223 
00224 protected:
00225         oct_node* mParent;
00226         LLVector3d mCenter;
00227         LLVector3d mSize;
00228         LLVector3d mMax;
00229         LLVector3d mMin;
00230         U8 mOctant;
00231 };
00232 
00233 template <class T>
00234 class LLOctreeTraveler : public LLTreeTraveler<T>
00235 {
00236 public:
00237         virtual void traverse(const LLTreeNode<T>* node);
00238         virtual void visit(const LLTreeState<T>* state) { }
00239         virtual void visit(const LLOctreeState<T>* branch) = 0;
00240 };
00241 
00242 //will pass requests to a child, might make a new child
00243 template <class T>
00244 class LLOctreeState : public LLTreeState<T> 
00245 {
00246 public:
00247         typedef LLTreeState<T>                                                                          BaseType;
00248         typedef LLOctreeTraveler<T>                                                                     oct_traveler;
00249         typedef LLOctreeNode<T>                                                                         oct_node;
00250         typedef LLOctreeListener<T>                                                                     oct_listener;
00251         typedef LLTreeTraveler<T>                                                                       tree_traveler;
00252         typedef typename std::set<LLPointer<T> >                                        element_list;
00253         typedef typename std::set<LLPointer<T> >::iterator                      element_iter;
00254         typedef typename std::set<LLPointer<T> >::const_iterator        const_element_iter;
00255         typedef typename std::vector<LLTreeListener<T>*>::iterator      tree_listener_iter;
00256         typedef typename std::vector<LLOctreeNode<T>* >                         child_list;
00257         
00258         LLOctreeState(oct_node* node = NULL): BaseType(node)    { this->clearChildren(); }
00259         virtual ~LLOctreeState() 
00260         {       
00261                 for (U32 i = 0; i < getChildCount(); i++)
00262                 {
00263                         delete getChild(i);
00264                 }
00265         }
00266                                                                                                                                 
00267         
00268         virtual void accept(oct_traveler* visitor)                              { visitor->visit(this); }
00269         virtual bool isLeaf() const                                                             { return mChild.empty(); }
00270         
00271         virtual U32 getElementCount() const                                             { return mData.size(); }
00272         virtual element_list& getData()                                                 { return mData; }
00273         virtual const element_list& getData() const                             { return mData; }
00274         
00275         virtual U32 getChildCount()     const                                           { return mChild.size(); }
00276         virtual oct_node* getChild(U32 index)                                   { return mChild[index]; }
00277         virtual const oct_node* getChild(U32 index) const               { return mChild[index]; }
00278         virtual child_list& getChildren()                                               { return mChild; }
00279         virtual const child_list& getChildren() const                   { return mChild; }
00280         
00281         virtual void accept(tree_traveler* visitor) const               { visitor->visit(this); }
00282         virtual void accept(oct_traveler* visitor) const                { visitor->visit(this); }
00283         const oct_node* getOctNode() const                                              { return (const oct_node*) BaseType::getNode(); }
00284         oct_node* getOctNode()                                                                  { return (oct_node*) BaseType::getNode(); }
00285 
00286         virtual oct_node* getNodeAt(T* data)
00287         {
00288                 return getNodeAt(data->getPositionGroup(), data->getBinRadius());
00289         }
00290 
00291         virtual oct_node* getNodeAt(const LLVector3d& pos, const F64& rad)
00292         { 
00293                 LLOctreeNode<T>* node = getOctNode();
00294 
00295                 if (node->isInside(pos, rad))
00296                 {               
00297                         //do a quick search by octant
00298                         U8 octant = node->getOctant(pos.mdV);
00299                         BOOL keep_going = TRUE;
00300 
00301                         //traverse the tree until we find a node that has no node
00302                         //at the appropriate octant or is smaller than the object.  
00303                         //by definition, that node is the smallest node that contains 
00304                         // the data
00305                         while (keep_going && node->getSize().mdV[0] >= rad)
00306                         {       
00307                                 keep_going = FALSE;
00308                                 for (U32 i = 0; i < node->getChildCount() && !keep_going; i++)
00309                                 {
00310                                         if (node->getChild(i)->getOctant() == octant)
00311                                         {
00312                                                 node = node->getChild(i);
00313                                                 octant = node->getOctant(pos.mdV);
00314                                                 keep_going = TRUE;
00315                                         }
00316                                 }
00317                         }
00318                 }
00319                 else if (!node->contains(rad) && node->getParent())
00320                 { //if we got here, data does not exist in this node
00321                         return ((LLOctreeNode<T>*) node->getParent())->getNodeAt(pos, rad);
00322                 }
00323 
00324                 return node;
00325         }
00326         
00327         virtual bool insert(T* data)
00328         {
00329                 if (data == NULL)
00330                 {
00331                         OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
00332                         return false;
00333                 }
00334                 LLOctreeNode<T>* node = getOctNode();
00335                 LLOctreeNode<T>* parent = node->getOctParent();
00336 
00337                 //is it here?
00338                 if (node->isInside(data->getPositionGroup()))
00339                 {
00340                         if (getElementCount() < LL_OCTREE_MAX_CAPACITY &&
00341                                 (node->contains(data->getBinRadius()) ||
00342                                 (data->getBinRadius() > node->getSize().mdV[0] &&
00343                                 parent && parent->getElementCount() >= LL_OCTREE_MAX_CAPACITY))) 
00344                         { //it belongs here
00345                                 if (data == NULL)
00346                                 {
00347                                         OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE LEAF !!!" << llendl;
00348                                         return false;
00349                                 }
00350                                 
00351 #if LL_OCTREE_PARANOIA_CHECK
00352                                 //if this is a redundant insertion, error out (should never happen)
00353                                 if (mData.find(data) != mData.end())
00354                                 {
00355                                         llwarns << "Redundant octree insertion detected. " << data << llendl;
00356                                         return false;
00357                                 }
00358 #endif
00359 
00360                                 mData.insert(data);
00361                                 return true;
00362                         }
00363                         else
00364                         {       
00365                                 //find a child to give it to
00366                                 oct_node* child = NULL;
00367                                 for (U32 i = 0; i < getChildCount(); i++)
00368                                 {
00369                                         child = getChild(i);
00370                                         if (child->isInside(data->getPositionGroup()))
00371                                         {
00372                                                 child->insert(data);
00373                                                 return false;
00374                                         }
00375                                 }
00376                                 
00377                                 //it's here, but no kids are in the right place, make a new kid
00378                                 LLVector3d center(node->getCenter());
00379                                 LLVector3d size(node->getSize()*0.5);
00380                                         
00381                                 //push center in direction of data
00382                                 LLOctreeNode<T>::pushCenter(center, size, data);
00383 
00384 #if LL_OCTREE_PARANOIA_CHECK
00385                                 if (getChildCount() == 8)
00386                                 {
00387                                         //this really isn't possible, something bad has happened
00388                                         OCT_ERRS << "Octree detected floating point error and gave up." << llendl;
00389                                         //bool check = node->isInside(data);
00390                                         return false;
00391                                 }
00392                                 
00393                                 //make sure no existing node matches this position
00394                                 for (U32 i = 0; i < getChildCount(); i++)
00395                                 {
00396                                         if (mChild[i]->getCenter() == center)
00397                                         {
00398                                                 OCT_ERRS << "Octree detected duplicate child center and gave up." << llendl;
00399                                                 //bool check = node->isInside(data);
00400                                                 //check = getChild(i)->isInside(data);
00401                                                 return false;
00402                                         }
00403                                 }
00404 #endif
00405 
00406                                 //make the new kid
00407                                 LLOctreeState<T>* newstate = new LLOctreeState<T>();
00408                                 child = new LLOctreeNode<T>(center, size, newstate, node);
00409                                 addChild(child);
00410 
00411                                 child->insert(data);
00412                         }
00413                 }
00414                 else 
00415                 {
00416                         //it's not in here, give it to the root
00417                         LLOctreeNode<T>* parent = node->getOctParent();
00418                         while (parent)
00419                         {
00420                                 node = parent;
00421                                 parent = node->getOctParent();
00422                         }
00423 
00424                         node->insert(data);
00425                 }
00426 
00427                 return false;
00428         }
00429 
00430         virtual bool remove(T* data)
00431         {
00432                 oct_node* node = getOctNode();
00433 
00434                 if (mData.find(data) != mData.end())
00435                 {       //we have data
00436                         mData.erase(data);
00437                         node->notifyRemoval(data);
00438                         checkAlive();
00439                         return true;
00440                 }
00441                 else if (node->isInside(data))
00442                 {
00443                         oct_node* dest = getNodeAt(data);
00444 
00445                         if (dest != node)
00446                         {
00447                                 return dest->remove(data);
00448                         }
00449                 }
00450 
00451                 //SHE'S GONE MISSING...
00452                 //none of the children have it, let's just brute force this bastard out
00453                 //starting with the root node (UGLY CODE COMETH!)
00454                 oct_node* parent = node->getOctParent();
00455                 while (parent != NULL)
00456                 {
00457                         node = parent;
00458                         parent = node->getOctParent();
00459                 }
00460 
00461                 //node is now root
00462                 llwarns << "!!! OCTREE REMOVING FACE BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl;
00463                 node->removeByAddress(data);
00464                 return true;
00465         }
00466 
00467         virtual void removeByAddress(T* data)
00468         {
00469         if (mData.find(data) != mData.end())
00470                 {
00471                         mData.erase(data);
00472                         getOctNode()->notifyRemoval(data);
00473                         llwarns << "FOUND!" << llendl;
00474                         checkAlive();
00475                         return;
00476                 }
00477                 
00478                 for (U32 i = 0; i < getChildCount(); i++)
00479                 {       //we don't contain data, so pass this guy down
00480                         LLOctreeNode<T>* child = (LLOctreeNode<T>*) getChild(i);
00481                         child->removeByAddress(data);
00482                 }
00483         }
00484 
00485         virtual void clearChildren()
00486         {
00487                 mChild.clear();
00488         }
00489 
00490         virtual void validate()
00491         {
00492 #if LL_OCTREE_PARANOIA_CHECK
00493                 LLOctreeNode<T>* node = this->getOctNode();
00494 
00495                 for (U32 i = 0; i < getChildCount(); i++)
00496                 {
00497                         mChild[i]->validate();
00498                         if (mChild[i]->getParent() != node)
00499                         {
00500                                 llerrs << "Octree child has invalid parent." << llendl;
00501                         }
00502                 }
00503 #endif
00504         }
00505 
00506         virtual bool balance()
00507         {       
00508                 return false;
00509         }
00510 
00511         virtual void destroy()
00512         {
00513                 for (U32 i = 0; i < getChildCount(); i++) 
00514                 {       
00515                         mChild[i]->destroy();
00516                         delete mChild[i];
00517                 }
00518         }
00519 
00520         virtual void addChild(oct_node* child, BOOL silent = FALSE) 
00521         {
00522 #if LL_OCTREE_PARANOIA_CHECK
00523                 for (U32 i = 0; i < getChildCount(); i++)
00524                 {
00525                         if(mChild[i]->getSize() != child->getSize()) 
00526                         {
00527                                 OCT_ERRS <<"Invalid octree child size." << llendl;
00528                         }
00529                         if (mChild[i]->getCenter() == child->getCenter())
00530                         {
00531                                 OCT_ERRS <<"Duplicate octree child position." << llendl;
00532                         }
00533                 }
00534 
00535                 if (mChild.size() >= 8)
00536                 {
00537                         OCT_ERRS <<"Octree node has too many children... why?" << llendl;
00538                 }
00539 #endif
00540 
00541                 mChild.push_back(child);
00542                 child->setParent(getOctNode());
00543 
00544                 if (!silent)
00545                 {
00546                         oct_node* node = getOctNode();
00547                         
00548                         for (U32 i = 0; i < node->getListenerCount(); i++)
00549                         {
00550                                 oct_listener* listener = node->getOctListener(i);
00551                                 listener->handleChildAddition(node, child);
00552                         }
00553                 }
00554         }
00555 
00556         virtual void removeChild(U8 index, BOOL destroy = FALSE)
00557         {
00558                 oct_node* node = getOctNode();
00559                 for (U32 i = 0; i < node->getListenerCount(); i++)
00560                 {
00561                         oct_listener* listener = node->getOctListener(i);
00562                         listener->handleChildRemoval(node, getChild(index));
00563                 }
00564 
00565                 if (destroy)
00566                 {
00567                         mChild[index]->destroy();
00568                         delete mChild[index];
00569                 }
00570                 mChild.erase(mChild.begin() + index);
00571 
00572                 checkAlive();
00573         }
00574 
00575         virtual void checkAlive()
00576         {
00577                 if (getChildCount() == 0 && getElementCount() == 0)
00578                 {
00579                         oct_node* node = getOctNode();
00580                         oct_node* parent = node->getOctParent();
00581                         if (parent)
00582                         {
00583                                 parent->deleteChild(node);
00584                         }
00585                 }
00586         }
00587 
00588         virtual void deleteChild(oct_node* node)
00589         {
00590                 for (U32 i = 0; i < getChildCount(); i++)
00591                 {
00592                         if (getChild(i) == node)
00593                         {
00594                                 removeChild(i, TRUE);
00595                                 return;
00596                         }
00597                 }
00598 
00599                 OCT_ERRS << "Octree failed to delete requested child." << llendl;
00600         }
00601 
00602 protected:
00603         child_list mChild;
00604         element_list mData;
00605 };
00606 
00607 //just like a branch, except it might expand the node it points to
00608 template <class T>
00609 class LLOctreeRoot : public LLOctreeState<T>
00610 {
00611 public:
00612         typedef LLOctreeState<T>        BaseType;
00613         typedef LLOctreeNode<T>         oct_node;
00614         
00615         LLOctreeRoot(oct_node* node = NULL) : BaseType(node) { }
00616         
00617         oct_node* getOctNode()  { return BaseType::getOctNode(); }
00618         virtual bool isLeaf()   { return false; }
00619 
00620         virtual bool balance()
00621         {       
00622                 //the cached node might be invalid, so don't reference it
00623                 if (this->getChildCount() == 1 && 
00624                         !(this->mChild[0]->hasLeafState()) &&
00625                         this->mChild[0]->getElementCount() == 0) 
00626                 { //if we have only one child and that child is an empty branch, make that child the root
00627                         BaseType* state = this->mChild[0]->getOctState();
00628                         oct_node* child = this->mChild[0];
00629                         oct_node* root = getOctNode();
00630                 
00631                         //make the root node look like the child
00632                         root->setCenter(this->mChild[0]->getCenter());
00633                         root->setSize(this->mChild[0]->getSize());
00634                         root->updateMinMax();
00635 
00636                         //reset root node child list
00637                         this->clearChildren();
00638 
00639                         //copy the child's children into the root node silently 
00640                         //(don't notify listeners of addition)
00641                         for (U32 i = 0; i < state->getChildCount(); i++)
00642                         {
00643                                 addChild(state->getChild(i), TRUE);
00644                         }
00645 
00646                         //destroy child
00647                         state->clearChildren();
00648                         delete child;
00649                 }
00650                 
00651                 return true;
00652         }
00653 
00654         // LLOctreeRoot::insert
00655         virtual bool insert(T* data)
00656         {
00657                 if (data == NULL) 
00658                 {
00659                         OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl;
00660                         return false;
00661                 }
00662                 
00663                 if (data->getBinRadius() > 4096.0)
00664                 {
00665                         OCT_ERRS << "!!! ELEMENT EXCEDES MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl;
00666                 }
00667                 
00668                 LLOctreeNode<T>* node = getOctNode();
00669                 if (node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup()))
00670                 {
00671                         //we got it, just act like a branch
00672                         LLOctreeState<T>::insert(data);
00673                 }
00674                 else if (this->getChildCount() == 0)
00675                 {
00676                         //first object being added, just wrap it up
00677                         while (!(node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup())))
00678                         {
00679                                 LLVector3d center, size;
00680                                 center = node->getCenter();
00681                                 size = node->getSize();
00682                                 LLOctreeNode<T>::pushCenter(center, size, data);
00683                                 node->setCenter(center);
00684                                 node->setSize(size*2);
00685                                 node->updateMinMax();
00686                         }
00687                         LLOctreeState<T>::insert(data);
00688                 }
00689                 else
00690                 {
00691                         //the data is outside the root node, we need to grow
00692                         LLVector3d center(node->getCenter());
00693                         LLVector3d size(node->getSize());
00694 
00695                         //expand this node
00696                         LLVector3d newcenter(center);
00697                         LLOctreeNode<T>::pushCenter(newcenter, size, data);
00698                         node->setCenter(newcenter);
00699                         node->setSize(size*2);
00700                         node->updateMinMax();
00701 
00702                         //copy our children to a new branch
00703                         LLOctreeState<T>* newstate = new LLOctreeState<T>();
00704                         LLOctreeNode<T>* newnode = new LLOctreeNode<T>(center, size, newstate, node);
00705                         
00706                         for (U32 i = 0; i < this->getChildCount(); i++)
00707                         {
00708                                 LLOctreeNode<T>* child = this->getChild(i);
00709                                 newstate->addChild(child);
00710                         }
00711 
00712                         //clear our children and add the root copy
00713                         this->clearChildren();
00714                         addChild(newnode);
00715 
00716                         //insert the data
00717                         node->insert(data);
00718                 }
00719 
00720                 return false;
00721         }
00722 };
00723 
00724 
00725 //========================
00726 //              LLOctreeTraveler
00727 //========================
00728 template <class T>
00729 void LLOctreeTraveler<T>::traverse(const LLTreeNode<T>* node)
00730 {
00731         const LLOctreeState<T>* state = (const LLOctreeState<T>*) node->getState();
00732         state->accept(this);
00733         for (U32 i = 0; i < state->getChildCount(); i++)
00734         {
00735                 traverse(state->getChild(i));
00736         }
00737 }
00738 
00739 #endif

Generated on Thu Jul 1 06:08:55 2010 for Second Life Viewer by  doxygen 1.4.7