00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_CSGEOM_AABBTREE_H__
00020 #define __CS_CSGEOM_AABBTREE_H__
00021
00022 #include "csutil/blockallocator.h"
00023 #include "csgeom/box.h"
00024 #include "csutil/dirtyaccessarray.h"
00025
00026 namespace CS
00027 {
00028 namespace Geometry
00029 {
00030 template<typename ObjectType>
00031 struct AABBTreeNodeExtraDataNone
00032 {
00033 void LeafAddObject (ObjectType*) {}
00034 void LeafUpdateObjects (ObjectType**, uint) {}
00035 void NodeUpdate (const AABBTreeNodeExtraDataNone& child1,
00036 const AABBTreeNodeExtraDataNone& child2) {}
00037 };
00038
00042 template<
00043 typename ObjectType,
00044 unsigned int objectsPerLeaf = 1,
00045 typename NodeExtraData = AABBTreeNodeExtraDataNone<ObjectType>
00046 >
00047 class AABBTree
00048 {
00049 public:
00051 enum
00052 {
00053 AABB_NODE_INNER = 0x0,
00054 AABB_NODE_LEAF = 0x1,
00055 AABB_NODE_TYPE_MASK = 0x1,
00056
00057 AABB_NODE_FLAG_SHIFT = 0x08,
00058 AABB_NODE_FLAG_MASK = 0xFF00
00059 };
00060
00062 class Node;
00063
00065 AABBTree ()
00066 : rootNode (0)
00067 {
00068 rootNode = AllocNode ();
00069 rootNode->SetLeaf (true);
00070 }
00071
00073 ~AABBTree ()
00074 {
00075 #ifdef CS_DEBUG
00076
00077 DeleteNodeRecursive (rootNode);
00078 #else
00079
00080 nodeAllocator.DeleteAll ();
00081 #endif
00082 }
00083
00087 void AddObject (ObjectType* object)
00088 {
00089 AddObjectRecursive (rootNode, object);
00090 }
00091
00095 bool RemoveObject (const ObjectType* object)
00096 {
00097 return RemoveObjectRec (object, rootNode);
00098 }
00099
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00125 bool MoveObject (ObjectType* object, const csBox3& oldBox)
00126 {
00127
00128 return MoveObjectRec (object, rootNode, oldBox);
00129 }
00130
00134 template<typename InnerFn, typename LeafFn>
00135 void Traverse (InnerFn& inner, LeafFn& leaf)
00136 {
00137 if (rootNode)
00138 TraverseRec (inner, leaf, rootNode);
00139 }
00140
00144 template<typename InnerFn, typename LeafFn>
00145 void Traverse (InnerFn& inner, LeafFn& leaf) const
00146 {
00147 if (rootNode)
00148 TraverseRec (inner, leaf, rootNode);
00149 }
00150
00154 template<typename InnerFn, typename LeafFn>
00155 void TraverseF2B (InnerFn& inner, LeafFn& leaf, const csVector3& direction)
00156 {
00157 if (rootNode)
00158 TraverseRecF2B (inner, leaf, direction, rootNode);
00159 }
00160
00164 template<typename InnerFn, typename LeafFn>
00165 void TraverseF2B (InnerFn& inner, LeafFn& leaf, const csVector3& direction) const
00166 {
00167 if (rootNode)
00168 TraverseRecF2B (inner, leaf, direction, rootNode);
00169 }
00170
00174 template<typename InnerFn, typename LeafFn>
00175 void TraverseOut (InnerFn& inner, LeafFn& leaf, const csVector3& point)
00176 {
00177 if (rootNode)
00178 TraverseRecOut (inner, leaf, point, rootNode);
00179 }
00180
00184 template<typename InnerFn, typename LeafFn>
00185 void TraverseOut (InnerFn& inner, LeafFn& leaf, const csVector3& point) const
00186 {
00187 if (rootNode)
00188 TraverseRecOut (inner, leaf, point, rootNode);
00189 }
00190
00194 struct InnerNodeNoOp
00195 {
00196 bool operator() (const Node* n)
00197 {
00198 CS_ASSERT_MSG("Invalid AABB-tree", !n->IsLeaf ());
00199 return true;
00200 }
00201 };
00202
00206 struct LeafNodeNoOp
00207 {
00208 bool operator() (const Node* n)
00209 {
00210 CS_ASSERT_MSG("Invalid AABB-tree", n->IsLeaf ());
00211 return true;
00212 }
00213 };
00214
00215 protected:
00216
00220 struct ObjectTypeSortByCenter
00221 {
00222 ObjectTypeSortByCenter (size_t axis)
00223 : axis (axis)
00224 {}
00225
00226 bool operator() (ObjectType* o1, ObjectType* o2)
00227 {
00228 return o1->GetBBox ().GetCenter ()[axis] <
00229 o2->GetBBox ().GetCenter ()[axis];
00230 }
00231
00232 size_t axis;
00233 };
00234
00238 struct ObjectCollectFn
00239 {
00240 ObjectCollectFn (csDirtyAccessArray<ObjectType*>& objects)
00241 : objects (objects)
00242 {}
00243
00244 void operator() (Node* child)
00245 {
00246 CS_ASSERT(child->IsLeaf ());
00247 for (size_t i = 0; child->GetObjectCount (); ++i)
00248 {
00249 objects.Push (child->GetLeafData (i));
00250 }
00251 }
00252
00253 csDirtyAccessArray<ObjectType*>& objects;
00254 };
00255
00256
00260 void AddObjectRecursive (Node* node, ObjectType* object)
00261 {
00262 if (node->IsLeaf ())
00263 {
00264 if (node->IsObjectSlotFree ())
00265 {
00266 node->AddLeafData (object);
00267 static_cast<NodeExtraData*> (node)->LeafAddObject (object);
00268 }
00269 else
00270 {
00271
00272
00273
00274 const size_t axis = node->GetBBox ().GetSize ().DominantAxis ();
00275
00276
00277 ObjectType* oldNodeI[objectsPerLeaf+1];
00278
00279 oldNodeI[0] = object;
00280
00281 size_t oldNodeCount = node->GetObjectCount ();
00282 for (size_t i = 0; i < oldNodeCount; ++i)
00283 {
00284 oldNodeI[i+1] = node->GetLeafData (i);
00285 }
00286
00287 {
00288 ObjectTypeSortByCenter sorter (axis);
00289 std::sort (oldNodeI, oldNodeI+oldNodeCount+1, sorter);
00290 }
00291
00292 Node* node1 = AllocNode ();
00293 node1->SetLeaf (true);
00294 Node* node2 = AllocNode ();
00295 node2->SetLeaf (true);
00296
00297
00298 {
00299 size_t i = 0;
00300 for (i = 0; i < (oldNodeCount+1)/2; ++i)
00301 {
00302 AddObjectRecursive (node1, oldNodeI[i]);
00303 }
00304
00305 for (; i < oldNodeCount+1; ++i)
00306 {
00307 AddObjectRecursive (node2, oldNodeI[i]);
00308 }
00309 }
00310
00311
00312 node->SetLeaf (false);
00313 node->SetChild1 (node1);
00314 node->SetChild2 (node2);
00315 static_cast<NodeExtraData*> (node)->NodeUpdate (*node1, *node2);
00316
00317
00318 node->GetBBox() += object->GetBBox();
00319 }
00320 }
00321 else
00322 {
00323
00324 const csVector3 objBoxCenter = object->GetBBox ().GetCenter ();
00325 const size_t axis = node->GetBBox ().GetCenter ().DominantAxis ();
00326
00327 if (objBoxCenter[axis] < node->GetBBox ().GetCenter ()[axis])
00328 {
00329 AddObjectRecursive (node->GetChild1 (), object);
00330 node->GetBBox ().AddBoundingBox (node->GetChild1 ()->GetBBox ());
00331 }
00332 else
00333 {
00334 AddObjectRecursive (node->GetChild2 (), object);
00335 node->GetBBox ().AddBoundingBox (node->GetChild2 ()->GetBBox ());
00336 }
00337 static_cast<NodeExtraData*> (node)->NodeUpdate (*node->GetChild1(), *node->GetChild2());
00338 }
00339 }
00340
00344 template<typename InnerFn, typename LeafFn>
00345 bool TraverseRec (InnerFn& inner, LeafFn& leaf, Node* node)
00346 {
00347 bool ret = true;
00348 if (!node)
00349 return ret;
00350
00351 if (node->IsLeaf ())
00352 {
00353 ret = leaf (node);
00354 }
00355 else
00356 {
00357 if (inner (node))
00358 {
00359 ret = TraverseRec (inner, leaf, node->GetChild1 ());
00360 if (ret) ret = TraverseRec (inner, leaf, node->GetChild2 ());
00361 }
00362 }
00363 return ret;
00364 }
00365
00369 template<typename InnerFn, typename LeafFn>
00370 bool TraverseRec (InnerFn& inner, LeafFn& leaf, const Node* node) const
00371 {
00372 bool ret = true;
00373 if (!node)
00374 return ret;
00375
00376 if (node->IsLeaf ())
00377 {
00378 ret = leaf (node);
00379 }
00380 else
00381 {
00382 if (inner (node))
00383 {
00384 ret = TraverseRec (inner, leaf, node->GetChild1 ());
00385 if (ret) ret = TraverseRec (inner, leaf, node->GetChild2 ());
00386 }
00387 }
00388 return ret;
00389 }
00390
00394 template<typename InnerFn, typename LeafFn>
00395 bool TraverseRecF2B (InnerFn& inner, LeafFn& leaf, const csVector3& direction, Node* node)
00396 {
00397 bool ret = true;
00398 if (!node)
00399 return ret;
00400
00401 if (node->IsLeaf ())
00402 {
00403 ret = leaf (node);
00404 }
00405 else
00406 {
00407 if (inner (node))
00408 {
00409 const csVector3 centerDiff = node->GetChild2 ()->GetBBox ().GetCenter () -
00410 node->GetChild1 ()->GetBBox ().GetCenter ();
00411
00412 const size_t firstIdx = (centerDiff * direction > 0) ? 0 : 1;
00413
00414 ret = TraverseRecF2B (inner, leaf, direction, node->GetChild (firstIdx));
00415 ret &= TraverseRecF2B (inner, leaf, direction, node->GetChild (1-firstIdx));
00416 }
00417 }
00418 return ret;
00419 }
00420
00421
00425 template<typename InnerFn, typename LeafFn>
00426 bool TraverseRecF2B (InnerFn& inner, LeafFn& leaf, const csVector3& direction, const Node* node) const
00427 {
00428 bool ret = true;
00429 if (!node)
00430 return ret;
00431
00432 if (node->IsLeaf ())
00433 {
00434 ret = leaf (node);
00435 }
00436 else
00437 {
00438 if (inner (node))
00439 {
00440 const csVector3 centerDiff = node->GetChild2 ()->GetBBox ().GetCenter () -
00441 node->GetChild1 ()->GetBBox ().GetCenter ();
00442
00443 const size_t firstIdx = (centerDiff * direction > 0) ? 0 : 1;
00444
00445 ret = TraverseRecF2B (inner, leaf, direction, node->GetChild (firstIdx));
00446 ret &= TraverseRecF2B (inner, leaf, direction, node->GetChild (1-firstIdx));
00447 }
00448 }
00449 return ret;
00450 }
00451
00452
00456 template<typename InnerFn, typename LeafFn>
00457 bool TraverseRecOut (InnerFn& inner, LeafFn& leaf, const csVector3& point, Node* node)
00458 {
00459 bool ret = true;
00460 if (!node)
00461 return ret;
00462
00463 if (node->IsLeaf ())
00464 {
00465 ret = leaf (node);
00466 }
00467 else
00468 {
00469 if (inner (node))
00470 {
00471 const float ch1LenSq = (node->GetChild1 ()->GetBBox ().GetCenter () - point).SquaredNorm ();
00472 const float ch2LenSq = (node->GetChild2 ()->GetBBox ().GetCenter () - point).SquaredNorm ();
00473
00474 const size_t firstIdx = (ch1LenSq > ch2LenSq) ? 0 : 1;
00475
00476 ret = TraverseRecOut (inner, leaf, point, node->GetChild (firstIdx));
00477 if (ret) ret = TraverseRecOut (inner, leaf, point, node->GetChild (1-firstIdx));
00478 }
00479 }
00480 return ret;
00481 }
00482
00486 template<typename InnerFn, typename LeafFn>
00487 bool TraverseRecOut (InnerFn& inner, LeafFn& leaf, const csVector3& point, const Node* node) const
00488 {
00489 bool ret = true;
00490 if (!node)
00491 return ret;
00492
00493 if (node->IsLeaf ())
00494 {
00495 ret = leaf (node);
00496 }
00497 else
00498 {
00499 if (inner (node))
00500 {
00501 const float ch1LenSq = (node->GetChild1 ()->GetBBox ().GetCenter () - point).SquaredNorm ();
00502 const float ch2LenSq = (node->GetChild2 ()->GetBBox ().GetCenter () - point).SquaredNorm ();
00503
00504 const size_t firstIdx = (ch1LenSq > ch2LenSq) ? 0 : 1;
00505
00506 ret = TraverseRecOut (inner, leaf, point, node->GetChild (firstIdx));
00507 if (ret) ret = TraverseRecOut (inner, leaf, point, node->GetChild (1-firstIdx));
00508 }
00509 }
00510 return ret;
00511 }
00512
00516 void BuildTree (Node* root, csDirtyAccessArray<ObjectType*>& objects,
00517 size_t objectStart, size_t objectEnd)
00518 {
00519 if (objectEnd <= objectStart)
00520 return;
00521
00522 const size_t numObjects = objectEnd - objectStart;
00523 const bool fewEnough = numObjects <= objectsPerLeaf;
00524
00525 if (fewEnough)
00526 {
00527
00528 root->SetLeaf (true);
00529 for (size_t i = objectStart; i < objectEnd; ++i)
00530 {
00531 root->AddLeafData (objects[i]);
00532 }
00533 static_cast<NodeExtraData*> (root)->LeafUpdateObjects (
00534 root->GetLeafObjects (), root->GetObjectCount());
00535 }
00536 else
00537 {
00538
00539 const size_t axis = root->GetBBox ().GetSize ().DominantAxis ();
00540
00541 {
00542 ObjectTypeSortByCenter sorter (axis);
00543 ObjectType** arr = objects.GetArray ();
00544 std::sort (arr + objectStart, arr + objectEnd, sorter);
00545
00546 const size_t median = objectStart + numObjects / 2;
00547
00548 Node* left = AllocNode ();
00549 Node* right = AllocNode ();
00550
00551 root->SetChild1 (left);
00552 root->SetChild2 (right);
00553
00554 BuildTree (left, objects, objectStart, median);
00555 BuildTree (right, objects, median + 1, objectEnd);
00556 static_cast<NodeExtraData*> (root)->NodeUpdate (*left, *right);
00557 }
00558
00559 }
00560
00561 }
00562
00566 Node* FindObjectNodeRec (Node* node, ObjectType* object)
00567 {
00568 {
00569 const csBox3& objBox = object->GetBBox ();
00570 if (!node->GetBBox ().Overlap (objBox))
00571 {
00572 return 0;
00573 }
00574 }
00575
00576 if (node->IsLeaf ())
00577 {
00578 for (size_t i = 0; i < node->GetObjectCount (); ++i)
00579 {
00580 if (node->GetLeafData (i) == object)
00581 {
00582 return node;
00583 }
00584 }
00585 }
00586 else
00587 {
00588 Node* result = FindObjectNodeRec (node->GetChild1 (), object);
00589
00590 if (!result)
00591 result = FindObjectNodeRec (node->GetChild2 (), object);
00592
00593 return result;
00594 }
00595
00596 return 0;
00597 }
00598
00602 bool MoveObjectRec (ObjectType* object, Node* node, const csBox3& oldBox)
00603 {
00604 if (node && oldBox.Overlap (node->GetBBox ()))
00605 {
00606 if (node->IsLeaf ())
00607 {
00608 for (size_t i = 0; i < node->GetObjectCount (); ++i)
00609 {
00610 if (node->GetLeafData (i) == object)
00611 {
00612
00613 csBox3 newNodeBB = node->GetLeafData (0)->GetBBox ();
00614 for (size_t i = 1; i < node->GetObjectCount (); ++i)
00615 {
00616 newNodeBB += node->GetLeafData (i)->GetBBox ();
00617 }
00618 node->SetBBox (newNodeBB);
00619
00620 return true;
00621 }
00622 }
00623 }
00624 else
00625 {
00626 Node* left = node->GetChild1 ();
00627 Node* right = node->GetChild2 ();
00628
00629 if (left && MoveObjectRec (object, left, oldBox))
00630 {
00631
00632 csBox3 newNodeBB = left->GetBBox ();
00633 if (right)
00634 {
00635 newNodeBB += right->GetBBox ();
00636 }
00637 node->SetBBox (newNodeBB);
00638
00639 return true;
00640 }
00641
00642 if (right && MoveObjectRec (object, right, oldBox))
00643 {
00644
00645 csBox3 newNodeBB = right->GetBBox ();
00646 if (left)
00647 {
00648 newNodeBB += left->GetBBox ();
00649 }
00650 node->SetBBox (newNodeBB);
00651
00652 return true;
00653 }
00654 }
00655 }
00656
00657 return false;
00658 }
00659
00663 bool RemoveObjectRec (const ObjectType* object, Node* node)
00664 {
00665 const csBox3& objBox = object->GetBBox ();
00666
00667 if (node && objBox.Overlap (node->GetBBox ()))
00668 {
00669 if (node->IsLeaf ())
00670 {
00671 for (size_t i = 0; i < node->GetObjectCount (); ++i)
00672 {
00673 if (node->GetLeafData (i) == object)
00674 {
00675
00676 csBox3 newNodeBB;
00677 for (size_t j = 0; j < node->GetObjectCount (); ++j)
00678 {
00679 if (i != j)
00680 {
00681 newNodeBB += node->GetLeafData (j)->GetBBox ();
00682 }
00683 }
00684 node->SetBBox (newNodeBB);
00685 node->RemoveLeafData (i);
00686 static_cast<NodeExtraData*> (node)->LeafUpdateObjects (
00687 node->GetLeafObjects(), node->GetObjectCount());
00688
00689 return true;
00690 }
00691 }
00692 }
00693 else
00694 {
00695 Node* left = node->GetChild1 ();
00696 Node* right = node->GetChild2 ();
00697
00698 if (left && RemoveObjectRec (object, left))
00699 {
00700 csBox3 newNodeBB;
00701
00702 if (right)
00703 {
00704 newNodeBB = right->GetBBox ();
00705 }
00706
00707
00708 if (!left->IsLeaf() || left->GetObjectCount () > 0)
00709 {
00710 newNodeBB += left->GetBBox ();
00711 static_cast<NodeExtraData*> (node)->NodeUpdate (*left, *right);
00712 }
00713 else
00714 {
00715
00716
00717 if (right)
00718 {
00719 node->Copy (right);
00720 nodeAllocator.Free (left);
00721 nodeAllocator.Free (right);
00722 newNodeBB = node->GetBBox ();
00723 }
00724 else
00725 {
00726 node->SetChild1 (0);
00727 node->SetLeaf (true);
00728 static_cast<NodeExtraData*> (node)->LeafUpdateObjects (0, 0);
00729 nodeAllocator.Free (left);
00730 }
00731 }
00732
00733 node->SetBBox (newNodeBB);
00734
00735 return true;
00736 }
00737
00738 if (right && RemoveObjectRec (object, right))
00739 {
00740 csBox3 newNodeBB;
00741
00742 if (left)
00743 {
00744 newNodeBB = left->GetBBox ();
00745 }
00746
00747
00748 if (!right->IsLeaf() || right->GetObjectCount () > 0)
00749 {
00750 newNodeBB += right->GetBBox ();
00751 static_cast<NodeExtraData*> (node)->NodeUpdate (*left, *right);
00752 }
00753 else
00754 {
00755
00756
00757 if (left)
00758 {
00759 node->Copy (left);
00760 nodeAllocator.Free (left);
00761 nodeAllocator.Free (right);
00762 newNodeBB = node->GetBBox ();
00763 }
00764 else
00765 {
00766 node->SetChild2 (0);
00767 node->SetLeaf (true);
00768 static_cast<NodeExtraData*> (node)->LeafUpdateObjects (0, 0);
00769 nodeAllocator.Free (right);
00770 }
00771 }
00772
00773 node->SetBBox (newNodeBB);
00774
00775 return true;
00776 }
00777 }
00778 }
00779
00780 return false;
00781 }
00782
00786 Node* AllocNode ()
00787 {
00788 return nodeAllocator.Alloc ();
00789 }
00790
00794 void DeleteNodeRecursive (Node* node)
00795 {
00796 if (!node)
00797 return;
00798
00799 if (!node->IsLeaf ())
00800 {
00801 DeleteNodeRecursive (node->GetChild1 ());
00802 DeleteNodeRecursive (node->GetChild2 ());
00803 }
00804
00805 nodeAllocator.Free (node);
00806 }
00807
00808 typedef csBlockAllocator<
00809 Node,
00810 CS::Memory::AllocatorAlign<32>,
00811 csBlockAllocatorDisposeLeaky<Node>,
00812 csBlockAllocatorSizeObjectAlign<Node, 32>
00813 > NodeAllocatorType;
00814
00816 NodeAllocatorType nodeAllocator;
00817
00819 Node* rootNode;
00820
00821
00822 };
00823
00827 template<
00828 typename ObjectType,
00829 unsigned int objectsPerLeaf,
00830 typename NodeExtraData
00831 >
00832 class AABBTree<ObjectType, objectsPerLeaf, NodeExtraData>::Node : public NodeExtraData
00833 {
00834 public:
00835 Node ()
00836 : typeAndFlags (AABB_NODE_INNER), leafObjCount (0)
00837 {
00838 children[0] = children[1] = 0;
00839 }
00840
00841
00843 bool IsLeaf () const
00844 {
00845 return (typeAndFlags & AABB_NODE_TYPE_MASK) == AABB_NODE_LEAF;
00846 }
00847
00849 void SetLeaf (bool isLeaf)
00850 {
00851 if (isLeaf && !IsLeaf ())
00852 {
00853 typeAndFlags |= AABB_NODE_LEAF;
00854
00855 CS_ASSERT(children[0] == 0);
00856 CS_ASSERT(children[1] == 0);
00857 leafObjCount = 0;
00858 }
00859 else if (!isLeaf && IsLeaf ())
00860 {
00861 typeAndFlags &= ~AABB_NODE_LEAF;
00862 leafObjCount = 0;
00863 children[0] = children[1] = 0;
00864 }
00865 }
00866
00868 uint GetFlags () const
00869 {
00870 return typeAndFlags >> AABB_NODE_FLAG_SHIFT;
00871 }
00872
00874 void SetFlags (uint newFlags)
00875 {
00876 typeAndFlags = (typeAndFlags & ~AABB_NODE_FLAG_MASK) |
00877 (newFlags << AABB_NODE_FLAG_SHIFT);
00878 }
00879
00881 uint GetObjectCount () const
00882 {
00883 CS_ASSERT(IsLeaf ());
00884 return leafObjCount;
00885 }
00886
00888 bool IsObjectSlotFree () const
00889 {
00890 CS_ASSERT(IsLeaf ());
00891 return leafObjCount < objectsPerLeaf;
00892 }
00893
00895 const csBox3& GetBBox () const
00896 {
00897 return boundingBox;
00898 }
00899
00901 csBox3& GetBBox ()
00902 {
00903 return boundingBox;
00904 }
00905
00907 void SetBBox (const csBox3& box)
00908 {
00909 boundingBox = box;
00910 }
00911
00912
00914 Node* GetChild1 () const
00915 {
00916 CS_ASSERT(!IsLeaf ());
00917 return children[0];
00918 }
00919
00921 Node* GetChild2 () const
00922 {
00923 CS_ASSERT(!IsLeaf ());
00924 return children[1];
00925 }
00926
00928 Node* GetChild (size_t i) const
00929 {
00930 CS_ASSERT(!IsLeaf () && i < 2);
00931 return children[i];
00932 }
00933
00935 void SetChild1 (Node* child)
00936 {
00937 CS_ASSERT(!IsLeaf ());
00938 children[0] = child;
00939 }
00940
00942 void SetChild2 (Node* child)
00943 {
00944 CS_ASSERT(!IsLeaf ());
00945 children[1] = child;
00946 }
00947
00949 void Copy (Node* source)
00950 {
00951 typeAndFlags = source->typeAndFlags;
00952 if (IsLeaf ())
00953 {
00954 memcpy (leafStorage, source->leafStorage, sizeof (ObjectType*) * objectsPerLeaf);
00955 }
00956 else
00957 {
00958 SetChild1 (source->GetChild1 ());
00959 SetChild2 (source->GetChild2 ());
00960 }
00961 leafObjCount = source->leafObjCount;
00962 SetBBox (source->GetBBox ());
00963 NodeExtraData::operator= (*source);
00964 }
00965
00966
00968 ObjectType* GetLeafData (size_t index) const
00969 {
00970 CS_ASSERT(IsLeaf ());
00971 CS_ASSERT(index < objectsPerLeaf);
00972
00973 return leafStorage[index];
00974 }
00975
00976 ObjectType** GetLeafObjects ()
00977 {
00978 CS_ASSERT(IsLeaf ());
00979 return leafStorage;
00980 }
00981
00983 void AddLeafData (ObjectType* object)
00984 {
00985 CS_ASSERT(IsLeaf ());
00986 CS_ASSERT(leafObjCount < objectsPerLeaf);
00987 leafStorage[leafObjCount++] = object;
00988
00989 boundingBox.AddBoundingBox (object->GetBBox ());
00990 }
00991
00992 void RemoveLeafData (size_t index)
00993 {
00994 CS_ASSERT(IsLeaf ());
00995 CS_ASSERT(leafObjCount > 0);
00996 leafStorage[index] = leafStorage[--leafObjCount];
00997 }
00998
00999 private:
01001 uint16 typeAndFlags;
01002
01004 uint16 leafObjCount;
01005
01007 csBox3 boundingBox;
01008
01010 union
01011 {
01012 ObjectType* leafStorage[objectsPerLeaf];
01013 Node* children[2];
01014 };
01015 };
01016
01017
01018 }
01019 }
01020
01021 #endif