aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/linden/indra/llmath/lloctree.h
diff options
context:
space:
mode:
authorJacek Antonelli2008-08-15 23:45:34 -0500
committerJacek Antonelli2008-08-15 23:45:34 -0500
commitcd17687f01420952712a500107e0f93e7ab8d5f8 (patch)
treece48c2b706f2c1176290e39fb555fbdf6648ce01 /linden/indra/llmath/lloctree.h
parentSecond Life viewer sources 1.19.0.5 (diff)
downloadmeta-impy-cd17687f01420952712a500107e0f93e7ab8d5f8.zip
meta-impy-cd17687f01420952712a500107e0f93e7ab8d5f8.tar.gz
meta-impy-cd17687f01420952712a500107e0f93e7ab8d5f8.tar.bz2
meta-impy-cd17687f01420952712a500107e0f93e7ab8d5f8.tar.xz
Second Life viewer sources 1.19.1.0
Diffstat (limited to 'linden/indra/llmath/lloctree.h')
-rw-r--r--linden/indra/llmath/lloctree.h382
1 files changed, 176 insertions, 206 deletions
diff --git a/linden/indra/llmath/lloctree.h b/linden/indra/llmath/lloctree.h
index 6eee9fb..203cb41 100644
--- a/linden/indra/llmath/lloctree.h
+++ b/linden/indra/llmath/lloctree.h
@@ -47,10 +47,9 @@
47#if LL_DARWIN 47#if LL_DARWIN
48#define LL_OCTREE_MAX_CAPACITY 32 48#define LL_OCTREE_MAX_CAPACITY 32
49#else 49#else
50#define LL_OCTREE_MAX_CAPACITY 256 50#define LL_OCTREE_MAX_CAPACITY 128
51#endif 51#endif
52 52
53template <class T> class LLOctreeState;
54template <class T> class LLOctreeNode; 53template <class T> class LLOctreeNode;
55 54
56template <class T> 55template <class T>
@@ -64,15 +63,27 @@ public:
64 virtual void handleChildRemoval(const oct_node* parent, const oct_node* child) = 0; 63 virtual void handleChildRemoval(const oct_node* parent, const oct_node* child) = 0;
65}; 64};
66 65
66template <class T>
67class LLOctreeTraveler : public LLTreeTraveler<T>
68{
69public:
70 virtual void traverse(const LLTreeNode<T>* node);
71 virtual void visit(const LLTreeNode<T>* state) { }
72 virtual void visit(const LLOctreeNode<T>* branch) = 0;
73};
67 74
68template <class T> 75template <class T>
69class LLOctreeNode : public LLTreeNode<T> 76class LLOctreeNode : public LLTreeNode<T>
70{ 77{
71public: 78public:
72 79 typedef LLOctreeTraveler<T> oct_traveler;
80 typedef LLTreeTraveler<T> tree_traveler;
81 typedef typename std::set<LLPointer<T> > element_list;
82 typedef typename std::set<LLPointer<T> >::iterator element_iter;
83 typedef typename std::set<LLPointer<T> >::const_iterator const_element_iter;
84 typedef typename std::vector<LLTreeListener<T>*>::iterator tree_listener_iter;
85 typedef typename std::vector<LLOctreeNode<T>* > child_list;
73 typedef LLTreeNode<T> BaseType; 86 typedef LLTreeNode<T> BaseType;
74 typedef LLTreeState<T> tree_state;
75 typedef LLOctreeState<T> oct_state;
76 typedef LLOctreeNode<T> oct_node; 87 typedef LLOctreeNode<T> oct_node;
77 typedef LLOctreeListener<T> oct_listener; 88 typedef LLOctreeListener<T> oct_listener;
78 89
@@ -82,11 +93,9 @@ public:
82 93
83 LLOctreeNode( LLVector3d center, 94 LLOctreeNode( LLVector3d center,
84 LLVector3d size, 95 LLVector3d size,
85 tree_state* state,
86 BaseType* parent, 96 BaseType* parent,
87 U8 octant = 255) 97 U8 octant = 255)
88 : BaseType(state), 98 : mParent((oct_node*)parent),
89 mParent((oct_node*)parent),
90 mCenter(center), 99 mCenter(center),
91 mSize(size), 100 mSize(size),
92 mOctant(octant) 101 mOctant(octant)
@@ -96,9 +105,19 @@ public:
96 { 105 {
97 mOctant = ((oct_node*) mParent)->getOctant(mCenter.mdV); 106 mOctant = ((oct_node*) mParent)->getOctant(mCenter.mdV);
98 } 107 }
108
109 clearChildren();
99 } 110 }
100 111
101 ~LLOctreeNode() { BaseType::destroyListeners(); delete this->mState; } 112 virtual ~LLOctreeNode()
113 {
114 BaseType::destroyListeners();
115
116 for (U32 i = 0; i < getChildCount(); i++)
117 {
118 delete getChild(i);
119 }
120 }
102 121
103 inline const BaseType* getParent() const { return mParent; } 122 inline const BaseType* getParent() const { return mParent; }
104 inline void setParent(BaseType* parent) { mParent = (oct_node*) parent; } 123 inline void setParent(BaseType* parent) { mParent = (oct_node*) parent; }
@@ -106,25 +125,12 @@ public:
106 inline const LLVector3d& getSize() const { return mSize; } 125 inline const LLVector3d& getSize() const { return mSize; }
107 inline void setCenter(LLVector3d center) { mCenter = center; } 126 inline void setCenter(LLVector3d center) { mCenter = center; }
108 inline void setSize(LLVector3d size) { mSize = size; } 127 inline void setSize(LLVector3d size) { mSize = size; }
109 inline bool balance() { return getOctState()->balance(); } 128 inline oct_node* getNodeAt(T* data) { return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
110 inline void validate() { getOctState()->validate(); }
111 inline U32 getChildCount() const { return getOctState()->getChildCount(); }
112 inline oct_node* getChild(U32 index) { return getOctState()->getChild(index); }
113 inline const oct_node* getChild(U32 index) const { return getOctState()->getChild(index); }
114 inline U32 getElementCount() const { return getOctState()->getElementCount(); }
115 inline void removeByAddress(T* data) { getOctState()->removeByAddress(data); }
116 inline bool hasLeafState() const { return getOctState()->isLeaf(); }
117 inline void destroy() { getOctState()->destroy(); }
118 inline oct_node* getNodeAt(T* data) { return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
119 inline oct_node* getNodeAt(const LLVector3d& pos, const F64& rad) { return getOctState()->getNodeAt(pos, rad); }
120 inline U8 getOctant() const { return mOctant; } 129 inline U8 getOctant() const { return mOctant; }
121 inline void setOctant(U8 octant) { mOctant = octant; } 130 inline void setOctant(U8 octant) { mOctant = octant; }
122 inline const oct_state* getOctState() const { return (const oct_state*) BaseType::mState; }
123 inline oct_state* getOctState() { return (oct_state*) BaseType::mState; }
124 inline const oct_node* getOctParent() const { return (const oct_node*) getParent(); } 131 inline const oct_node* getOctParent() const { return (const oct_node*) getParent(); }
125 inline oct_node* getOctParent() { return (oct_node*) getParent(); } 132 inline oct_node* getOctParent() { return (oct_node*) getParent(); }
126 inline void deleteChild(oct_node* child) { getOctState()->deleteChild(child); } 133
127
128 U8 getOctant(const F64 pos[]) const //get the octant pos is in 134 U8 getOctant(const F64 pos[]) const //get the octant pos is in
129 { 135 {
130 U8 ret = 0; 136 U8 ret = 0;
@@ -205,9 +211,9 @@ public:
205 (radius <= p_size && radius > size); 211 (radius <= p_size && radius > size);
206 } 212 }
207 213
208 static void pushCenter(LLVector3d &center, LLVector3d &size, T* data) 214 static void pushCenter(LLVector3d &center, const LLVector3d &size, const T* data)
209 { 215 {
210 LLVector3d pos(data->getPositionGroup()); 216 const LLVector3d& pos = data->getPositionGroup();
211 for (U32 i = 0; i < 3; i++) 217 for (U32 i = 0; i < 3; i++)
212 { 218 {
213 if (pos.mdV[i] > center.mdV[i]) 219 if (pos.mdV[i] > center.mdV[i])
@@ -221,76 +227,25 @@ public:
221 } 227 }
222 } 228 }
223 229
224protected: 230 void accept(oct_traveler* visitor) { visitor->visit(this); }
225 oct_node* mParent; 231 virtual bool isLeaf() const { return mChild.empty(); }
226 LLVector3d mCenter;
227 LLVector3d mSize;
228 LLVector3d mMax;
229 LLVector3d mMin;
230 U8 mOctant;
231};
232
233template <class T>
234class LLOctreeTraveler : public LLTreeTraveler<T>
235{
236public:
237 virtual void traverse(const LLTreeNode<T>* node);
238 virtual void visit(const LLTreeState<T>* state) { }
239 virtual void visit(const LLOctreeState<T>* branch) = 0;
240};
241
242//will pass requests to a child, might make a new child
243template <class T>
244class LLOctreeState : public LLTreeState<T>
245{
246public:
247 typedef LLTreeState<T> BaseType;
248 typedef LLOctreeTraveler<T> oct_traveler;
249 typedef LLOctreeNode<T> oct_node;
250 typedef LLOctreeListener<T> oct_listener;
251 typedef LLTreeTraveler<T> tree_traveler;
252 typedef typename std::set<LLPointer<T> > element_list;
253 typedef typename std::set<LLPointer<T> >::iterator element_iter;
254 typedef typename std::set<LLPointer<T> >::const_iterator const_element_iter;
255 typedef typename std::vector<LLTreeListener<T>*>::iterator tree_listener_iter;
256 typedef typename std::vector<LLOctreeNode<T>* > child_list;
257 232
258 LLOctreeState(oct_node* node = NULL): BaseType(node) { this->clearChildren(); } 233 U32 getElementCount() const { return mData.size(); }
259 virtual ~LLOctreeState() 234 element_list& getData() { return mData; }
260 { 235 const element_list& getData() const { return mData; }
261 for (U32 i = 0; i < getChildCount(); i++)
262 {
263 delete getChild(i);
264 }
265 }
266
267 236
268 virtual void accept(oct_traveler* visitor) { visitor->visit(this); } 237 U32 getChildCount() const { return mChild.size(); }
269 virtual bool isLeaf() const { return mChild.empty(); } 238 oct_node* getChild(U32 index) { return mChild[index]; }
239 const oct_node* getChild(U32 index) const { return mChild[index]; }
240 child_list& getChildren() { return mChild; }
241 const child_list& getChildren() const { return mChild; }
270 242
271 virtual U32 getElementCount() const { return mData.size(); } 243 void accept(tree_traveler* visitor) const { visitor->visit(this); }
272 virtual element_list& getData() { return mData; } 244 void accept(oct_traveler* visitor) const { visitor->visit(this); }
273 virtual const element_list& getData() const { return mData; }
274 245
275 virtual U32 getChildCount() const { return mChild.size(); } 246 oct_node* getNodeAt(const LLVector3d& pos, const F64& rad)
276 virtual oct_node* getChild(U32 index) { return mChild[index]; }
277 virtual const oct_node* getChild(U32 index) const { return mChild[index]; }
278 virtual child_list& getChildren() { return mChild; }
279 virtual const child_list& getChildren() const { return mChild; }
280
281 virtual void accept(tree_traveler* visitor) const { visitor->visit(this); }
282 virtual void accept(oct_traveler* visitor) const { visitor->visit(this); }
283 const oct_node* getOctNode() const { return (const oct_node*) BaseType::getNode(); }
284 oct_node* getOctNode() { return (oct_node*) BaseType::getNode(); }
285
286 virtual oct_node* getNodeAt(T* data)
287 {
288 return getNodeAt(data->getPositionGroup(), data->getBinRadius());
289 }
290
291 virtual oct_node* getNodeAt(const LLVector3d& pos, const F64& rad)
292 { 247 {
293 LLOctreeNode<T>* node = getOctNode(); 248 LLOctreeNode<T>* node = this;
294 249
295 if (node->isInside(pos, rad)) 250 if (node->isInside(pos, rad))
296 { 251 {
@@ -328,26 +283,19 @@ public:
328 { 283 {
329 if (data == NULL) 284 if (data == NULL)
330 { 285 {
331 OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl; 286 //OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
332 return false; 287 return false;
333 } 288 }
334 LLOctreeNode<T>* node = getOctNode(); 289 LLOctreeNode<T>* parent = getOctParent();
335 LLOctreeNode<T>* parent = node->getOctParent();
336 290
337 //is it here? 291 //is it here?
338 if (node->isInside(data->getPositionGroup())) 292 if (isInside(data->getPositionGroup()))
339 { 293 {
340 if (getElementCount() < LL_OCTREE_MAX_CAPACITY && 294 if (getElementCount() < LL_OCTREE_MAX_CAPACITY &&
341 (node->contains(data->getBinRadius()) || 295 (contains(data->getBinRadius()) ||
342 (data->getBinRadius() > node->getSize().mdV[0] && 296 (data->getBinRadius() > getSize().mdV[0] &&
343 parent && parent->getElementCount() >= LL_OCTREE_MAX_CAPACITY))) 297 parent && parent->getElementCount() >= LL_OCTREE_MAX_CAPACITY)))
344 { //it belongs here 298 { //it belongs here
345 if (data == NULL)
346 {
347 OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE LEAF !!!" << llendl;
348 return false;
349 }
350
351#if LL_OCTREE_PARANOIA_CHECK 299#if LL_OCTREE_PARANOIA_CHECK
352 //if this is a redundant insertion, error out (should never happen) 300 //if this is a redundant insertion, error out (should never happen)
353 if (mData.find(data) != mData.end()) 301 if (mData.find(data) != mData.end())
@@ -358,6 +306,7 @@ public:
358#endif 306#endif
359 307
360 mData.insert(data); 308 mData.insert(data);
309 BaseType::insert(data);
361 return true; 310 return true;
362 } 311 }
363 else 312 else
@@ -375,8 +324,8 @@ public:
375 } 324 }
376 325
377 //it's here, but no kids are in the right place, make a new kid 326 //it's here, but no kids are in the right place, make a new kid
378 LLVector3d center(node->getCenter()); 327 LLVector3d center(getCenter());
379 LLVector3d size(node->getSize()*0.5); 328 LLVector3d size(getSize()*0.5);
380 329
381 //push center in direction of data 330 //push center in direction of data
382 LLOctreeNode<T>::pushCenter(center, size, data); 331 LLOctreeNode<T>::pushCenter(center, size, data);
@@ -386,7 +335,6 @@ public:
386 { 335 {
387 //this really isn't possible, something bad has happened 336 //this really isn't possible, something bad has happened
388 OCT_ERRS << "Octree detected floating point error and gave up." << llendl; 337 OCT_ERRS << "Octree detected floating point error and gave up." << llendl;
389 //bool check = node->isInside(data);
390 return false; 338 return false;
391 } 339 }
392 340
@@ -396,25 +344,25 @@ public:
396 if (mChild[i]->getCenter() == center) 344 if (mChild[i]->getCenter() == center)
397 { 345 {
398 OCT_ERRS << "Octree detected duplicate child center and gave up." << llendl; 346 OCT_ERRS << "Octree detected duplicate child center and gave up." << llendl;
399 //bool check = node->isInside(data);
400 //check = getChild(i)->isInside(data);
401 return false; 347 return false;
402 } 348 }
403 } 349 }
404#endif 350#endif
405 351
406 //make the new kid 352 //make the new kid
407 LLOctreeState<T>* newstate = new LLOctreeState<T>(); 353 child = new LLOctreeNode<T>(center, size, this);
408 child = new LLOctreeNode<T>(center, size, newstate, node);
409 addChild(child); 354 addChild(child);
410 355
411 child->insert(data); 356 child->insert(data);
412 } 357 }
413 } 358 }
414 else 359 else
415 { 360 {
416 //it's not in here, give it to the root 361 //it's not in here, give it to the root
417 LLOctreeNode<T>* parent = node->getOctParent(); 362 //OCT_ERRS << "Octree insertion failed, starting over from root!" << llendl;
363
364 oct_node* node = this;
365
418 while (parent) 366 while (parent)
419 { 367 {
420 node = parent; 368 node = parent;
@@ -427,22 +375,20 @@ public:
427 return false; 375 return false;
428 } 376 }
429 377
430 virtual bool remove(T* data) 378 bool remove(T* data)
431 { 379 {
432 oct_node* node = getOctNode();
433
434 if (mData.find(data) != mData.end()) 380 if (mData.find(data) != mData.end())
435 { //we have data 381 { //we have data
436 mData.erase(data); 382 mData.erase(data);
437 node->notifyRemoval(data); 383 notifyRemoval(data);
438 checkAlive(); 384 checkAlive();
439 return true; 385 return true;
440 } 386 }
441 else if (node->isInside(data)) 387 else if (isInside(data))
442 { 388 {
443 oct_node* dest = getNodeAt(data); 389 oct_node* dest = getNodeAt(data);
444 390
445 if (dest != node) 391 if (dest != this)
446 { 392 {
447 return dest->remove(data); 393 return dest->remove(data);
448 } 394 }
@@ -451,7 +397,9 @@ public:
451 //SHE'S GONE MISSING... 397 //SHE'S GONE MISSING...
452 //none of the children have it, let's just brute force this bastard out 398 //none of the children have it, let's just brute force this bastard out
453 //starting with the root node (UGLY CODE COMETH!) 399 //starting with the root node (UGLY CODE COMETH!)
454 oct_node* parent = node->getOctParent(); 400 oct_node* parent = getOctParent();
401 oct_node* node = this;
402
455 while (parent != NULL) 403 while (parent != NULL)
456 { 404 {
457 node = parent; 405 node = parent;
@@ -464,12 +412,12 @@ public:
464 return true; 412 return true;
465 } 413 }
466 414
467 virtual void removeByAddress(T* data) 415 void removeByAddress(T* data)
468 { 416 {
469 if (mData.find(data) != mData.end()) 417 if (mData.find(data) != mData.end())
470 { 418 {
471 mData.erase(data); 419 mData.erase(data);
472 getOctNode()->notifyRemoval(data); 420 notifyRemoval(data);
473 llwarns << "FOUND!" << llendl; 421 llwarns << "FOUND!" << llendl;
474 checkAlive(); 422 checkAlive();
475 return; 423 return;
@@ -482,20 +430,18 @@ public:
482 } 430 }
483 } 431 }
484 432
485 virtual void clearChildren() 433 void clearChildren()
486 { 434 {
487 mChild.clear(); 435 mChild.clear();
488 } 436 }
489 437
490 virtual void validate() 438 void validate()
491 { 439 {
492#if LL_OCTREE_PARANOIA_CHECK 440#if LL_OCTREE_PARANOIA_CHECK
493 LLOctreeNode<T>* node = this->getOctNode();
494
495 for (U32 i = 0; i < getChildCount(); i++) 441 for (U32 i = 0; i < getChildCount(); i++)
496 { 442 {
497 mChild[i]->validate(); 443 mChild[i]->validate();
498 if (mChild[i]->getParent() != node) 444 if (mChild[i]->getParent() != this)
499 { 445 {
500 llerrs << "Octree child has invalid parent." << llendl; 446 llerrs << "Octree child has invalid parent." << llendl;
501 } 447 }
@@ -508,7 +454,7 @@ public:
508 return false; 454 return false;
509 } 455 }
510 456
511 virtual void destroy() 457 void destroy()
512 { 458 {
513 for (U32 i = 0; i < getChildCount(); i++) 459 for (U32 i = 0; i < getChildCount(); i++)
514 { 460 {
@@ -517,7 +463,7 @@ public:
517 } 463 }
518 } 464 }
519 465
520 virtual void addChild(oct_node* child, BOOL silent = FALSE) 466 void addChild(oct_node* child, BOOL silent = FALSE)
521 { 467 {
522#if LL_OCTREE_PARANOIA_CHECK 468#if LL_OCTREE_PARANOIA_CHECK
523 for (U32 i = 0; i < getChildCount(); i++) 469 for (U32 i = 0; i < getChildCount(); i++)
@@ -539,27 +485,24 @@ public:
539#endif 485#endif
540 486
541 mChild.push_back(child); 487 mChild.push_back(child);
542 child->setParent(getOctNode()); 488 child->setParent(this);
543 489
544 if (!silent) 490 if (!silent)
545 { 491 {
546 oct_node* node = getOctNode(); 492 for (U32 i = 0; i < this->getListenerCount(); i++)
547
548 for (U32 i = 0; i < node->getListenerCount(); i++)
549 { 493 {
550 oct_listener* listener = node->getOctListener(i); 494 oct_listener* listener = getOctListener(i);
551 listener->handleChildAddition(node, child); 495 listener->handleChildAddition(this, child);
552 } 496 }
553 } 497 }
554 } 498 }
555 499
556 virtual void removeChild(U8 index, BOOL destroy = FALSE) 500 void removeChild(U8 index, BOOL destroy = FALSE)
557 { 501 {
558 oct_node* node = getOctNode(); 502 for (U32 i = 0; i < this->getListenerCount(); i++)
559 for (U32 i = 0; i < node->getListenerCount(); i++)
560 { 503 {
561 oct_listener* listener = node->getOctListener(i); 504 oct_listener* listener = getOctListener(i);
562 listener->handleChildRemoval(node, getChild(index)); 505 listener->handleChildRemoval(this, getChild(index));
563 } 506 }
564 507
565 if (destroy) 508 if (destroy)
@@ -572,20 +515,19 @@ public:
572 checkAlive(); 515 checkAlive();
573 } 516 }
574 517
575 virtual void checkAlive() 518 void checkAlive()
576 { 519 {
577 if (getChildCount() == 0 && getElementCount() == 0) 520 if (getChildCount() == 0 && getElementCount() == 0)
578 { 521 {
579 oct_node* node = getOctNode(); 522 oct_node* parent = getOctParent();
580 oct_node* parent = node->getOctParent();
581 if (parent) 523 if (parent)
582 { 524 {
583 parent->deleteChild(node); 525 parent->deleteChild(this);
584 } 526 }
585 } 527 }
586 } 528 }
587 529
588 virtual void deleteChild(oct_node* node) 530 void deleteChild(oct_node* node)
589 { 531 {
590 for (U32 i = 0; i < getChildCount(); i++) 532 for (U32 i = 0; i < getChildCount(); i++)
591 { 533 {
@@ -596,55 +538,62 @@ public:
596 } 538 }
597 } 539 }
598 540
599 OCT_ERRS << "Octree failed to delete requested child." << llendl; 541 //OCT_ERRS << "Octree failed to delete requested child." << llendl;
600 } 542 }
601 543
602protected: 544protected:
603 child_list mChild; 545 child_list mChild;
604 element_list mData; 546 element_list mData;
547 oct_node* mParent;
548 LLVector3d mCenter;
549 LLVector3d mSize;
550 LLVector3d mMax;
551 LLVector3d mMin;
552 U8 mOctant;
605}; 553};
606 554
607//just like a branch, except it might expand the node it points to 555//just like a regular node, except it might expand on insert and compress on balance
608template <class T> 556template <class T>
609class LLOctreeRoot : public LLOctreeState<T> 557class LLOctreeRoot : public LLOctreeNode<T>
610{ 558{
611public: 559public:
612 typedef LLOctreeState<T> BaseType; 560 typedef LLOctreeNode<T> BaseType;
613 typedef LLOctreeNode<T> oct_node; 561 typedef LLOctreeNode<T> oct_node;
562
563 LLOctreeRoot( LLVector3d center,
564 LLVector3d size,
565 BaseType* parent)
566 : BaseType(center, size, parent)
567 {
568 }
614 569
615 LLOctreeRoot(oct_node* node = NULL) : BaseType(node) { } 570 bool isLeaf() { return false; }
616
617 oct_node* getOctNode() { return BaseType::getOctNode(); }
618 virtual bool isLeaf() { return false; }
619 571
620 virtual bool balance() 572 bool balance()
621 { 573 {
622 //the cached node might be invalid, so don't reference it
623 if (this->getChildCount() == 1 && 574 if (this->getChildCount() == 1 &&
624 !(this->mChild[0]->hasLeafState()) && 575 !(this->mChild[0]->isLeaf()) &&
625 this->mChild[0]->getElementCount() == 0) 576 this->mChild[0]->getElementCount() == 0)
626 { //if we have only one child and that child is an empty branch, make that child the root 577 { //if we have only one child and that child is an empty branch, make that child the root
627 BaseType* state = this->mChild[0]->getOctState();
628 oct_node* child = this->mChild[0]; 578 oct_node* child = this->mChild[0];
629 oct_node* root = getOctNode(); 579
630
631 //make the root node look like the child 580 //make the root node look like the child
632 root->setCenter(this->mChild[0]->getCenter()); 581 this->setCenter(this->mChild[0]->getCenter());
633 root->setSize(this->mChild[0]->getSize()); 582 this->setSize(this->mChild[0]->getSize());
634 root->updateMinMax(); 583 this->updateMinMax();
635 584
636 //reset root node child list 585 //reset root node child list
637 this->clearChildren(); 586 this->clearChildren();
638 587
639 //copy the child's children into the root node silently 588 //copy the child's children into the root node silently
640 //(don't notify listeners of addition) 589 //(don't notify listeners of addition)
641 for (U32 i = 0; i < state->getChildCount(); i++) 590 for (U32 i = 0; i < child->getChildCount(); i++)
642 { 591 {
643 addChild(state->getChild(i), TRUE); 592 addChild(child->getChild(i), TRUE);
644 } 593 }
645 594
646 //destroy child 595 //destroy child
647 state->clearChildren(); 596 child->clearChildren();
648 delete child; 597 delete child;
649 } 598 }
650 599
@@ -652,69 +601,90 @@ public:
652 } 601 }
653 602
654 // LLOctreeRoot::insert 603 // LLOctreeRoot::insert
655 virtual bool insert(T* data) 604 bool insert(T* data)
656 { 605 {
657 if (data == NULL) 606 if (data == NULL)
658 { 607 {
659 OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl; 608 //OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE ROOT !!!" << llendl;
660 return false; 609 return false;
661 } 610 }
662 611
663 if (data->getBinRadius() > 4096.0) 612 if (data->getBinRadius() > 4096.0)
664 { 613 {
665 OCT_ERRS << "!!! ELEMENT EXCEDES MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl; 614 //OCT_ERRS << "!!! ELEMENT EXCEEDS MAXIMUM SIZE IN OCTREE ROOT !!!" << llendl;
615 return false;
666 } 616 }
667 617
668 LLOctreeNode<T>* node = getOctNode(); 618 const F64 MAX_MAG = 1024.0*1024.0;
669 if (node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup())) 619
620 const LLVector3d& v = data->getPositionGroup();
621 if (!(fabs(v.mdV[0]-this->mCenter.mdV[0]) < MAX_MAG &&
622 fabs(v.mdV[1]-this->mCenter.mdV[1]) < MAX_MAG &&
623 fabs(v.mdV[2]-this->mCenter.mdV[2]) < MAX_MAG))
624 {
625 //OCT_ERRS << "!!! ELEMENT EXCEEDS RANGE OF SPATIAL PARTITION !!!" << llendl;
626 return false;
627 }
628
629 if (this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup()))
670 { 630 {
671 //we got it, just act like a branch 631 //we got it, just act like a branch
672 LLOctreeState<T>::insert(data); 632 oct_node* node = getNodeAt(data);
633 if (node == this)
634 {
635 LLOctreeNode<T>::insert(data);
636 }
637 else
638 {
639 node->insert(data);
640 }
673 } 641 }
674 else if (this->getChildCount() == 0) 642 else if (this->getChildCount() == 0)
675 { 643 {
676 //first object being added, just wrap it up 644 //first object being added, just wrap it up
677 while (!(node->getSize().mdV[0] > data->getBinRadius() && node->isInside(data->getPositionGroup()))) 645 while (!(this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
678 { 646 {
679 LLVector3d center, size; 647 LLVector3d center, size;
680 center = node->getCenter(); 648 center = this->getCenter();
681 size = node->getSize(); 649 size = this->getSize();
682 LLOctreeNode<T>::pushCenter(center, size, data); 650 LLOctreeNode<T>::pushCenter(center, size, data);
683 node->setCenter(center); 651 this->setCenter(center);
684 node->setSize(size*2); 652 this->setSize(size*2);
685 node->updateMinMax(); 653 this->updateMinMax();
686 } 654 }
687 LLOctreeState<T>::insert(data); 655 LLOctreeNode<T>::insert(data);
688 } 656 }
689 else 657 else
690 { 658 {
691 //the data is outside the root node, we need to grow 659 while (!(this->getSize().mdV[0] > data->getBinRadius() && isInside(data->getPositionGroup())))
692 LLVector3d center(node->getCenter());
693 LLVector3d size(node->getSize());
694
695 //expand this node
696 LLVector3d newcenter(center);
697 LLOctreeNode<T>::pushCenter(newcenter, size, data);
698 node->setCenter(newcenter);
699 node->setSize(size*2);
700 node->updateMinMax();
701
702 //copy our children to a new branch
703 LLOctreeState<T>* newstate = new LLOctreeState<T>();
704 LLOctreeNode<T>* newnode = new LLOctreeNode<T>(center, size, newstate, node);
705
706 for (U32 i = 0; i < this->getChildCount(); i++)
707 { 660 {
708 LLOctreeNode<T>* child = this->getChild(i); 661 //the data is outside the root node, we need to grow
709 newstate->addChild(child); 662 LLVector3d center(this->getCenter());
710 } 663 LLVector3d size(this->getSize());
664
665 //expand this node
666 LLVector3d newcenter(center);
667 LLOctreeNode<T>::pushCenter(newcenter, size, data);
668 this->setCenter(newcenter);
669 this->setSize(size*2);
670 this->updateMinMax();
671
672 //copy our children to a new branch
673 LLOctreeNode<T>* newnode = new LLOctreeNode<T>(center, size, this);
674
675 for (U32 i = 0; i < this->getChildCount(); i++)
676 {
677 LLOctreeNode<T>* child = this->getChild(i);
678 newnode->addChild(child);
679 }
711 680
712 //clear our children and add the root copy 681 //clear our children and add the root copy
713 this->clearChildren(); 682 this->clearChildren();
714 addChild(newnode); 683 addChild(newnode);
684 }
715 685
716 //insert the data 686 //insert the data
717 node->insert(data); 687 insert(data);
718 } 688 }
719 689
720 return false; 690 return false;
@@ -726,13 +696,13 @@ public:
726// LLOctreeTraveler 696// LLOctreeTraveler
727//======================== 697//========================
728template <class T> 698template <class T>
729void LLOctreeTraveler<T>::traverse(const LLTreeNode<T>* node) 699void LLOctreeTraveler<T>::traverse(const LLTreeNode<T>* tree_node)
730{ 700{
731 const LLOctreeState<T>* state = (const LLOctreeState<T>*) node->getState(); 701 const LLOctreeNode<T>* node = (const LLOctreeNode<T>*) tree_node;
732 state->accept(this); 702 node->accept(this);
733 for (U32 i = 0; i < state->getChildCount(); i++) 703 for (U32 i = 0; i < node->getChildCount(); i++)
734 { 704 {
735 traverse(state->getChild(i)); 705 traverse(node->getChild(i));
736 } 706 }
737} 707}
738 708
generated by cgit v1.1 at 2025-01-08 16:12:24 +0000