csgeom/aabbtree.h
00001 /* 00002 Copyright (C) 2008 by Marten Svanfeldt 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Lesser General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 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 //@@Right? 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 // Destroy only pointers "in use" to track down leaking nodes 00077 DeleteNodeRecursive (rootNode); 00078 #else 00079 // Don't bother with tree traversal, just free all nodes 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 // void AddObjects (csDirtyAccessArray<ObjectType*> objects) 00104 // { 00105 // // Collect any existing objects into the objects array 00106 // { 00107 // ObjectCollectFn collect (objects); 00108 // TraverseLeafs (collect); 00109 // } 00110 // 00111 // // Build a new tree 00112 // DeleteNodeRecursive (rootNode); 00113 // 00114 // // New root 00115 // rootNode = AllocNode (); 00116 // rootNode->SetLeaf (true); 00117 // 00118 // // Build 00119 // BuildTree (rootNode, objects, 0, objects.GetSize ()); 00120 // } 00121 00125 bool MoveObject (ObjectType* object, const csBox3& oldBox) 00126 { 00127 // Traverse down the tree, recursively updating BB if we have an update 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 // Need to split node in two 00272 00273 // Split according to longest axis 00274 const size_t axis = node->GetBBox ().GetSize ().DominantAxis (); 00275 00276 // Save old info 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 // Assign first 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 // Setup new 00312 node->SetLeaf (false); 00313 node->SetChild1 (node1); 00314 node->SetChild2 (node2); 00315 static_cast<NodeExtraData*> (node)->NodeUpdate (*node1, *node2); 00316 00317 // update bbox 00318 node->GetBBox() += object->GetBBox(); 00319 } 00320 } 00321 else 00322 { 00323 // Select left or right depending on closeness to center (find better) 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 // Assign to a leaf 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 // Very dumb, sort by center, split at median 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 // Found node, update the node BB 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; // Found it 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 // Tree was updated, update our bb 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 // Tree was updated, update our bb 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; // Don't overlap in this node 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 // Found node, update the node BB 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; // Found it 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 // Tree was updated, update our bb 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 // We have to delete the left node. We do that by moving the children 00716 // of the right node down. 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 // Tree was updated, update our bb 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 // We have to delete the right node. We do that by moving the children 00756 // of the left node down. 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 // General accessors 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 // Ensure no children are 'lost' 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 ()); // object count is only sensible for leaves 00884 return leafObjCount; 00885 } 00886 00888 bool IsObjectSlotFree () const 00889 { 00890 CS_ASSERT(IsLeaf ()); // object count is only sensible for leaves 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 // Accessor for inner node data 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 // Accessor for leaf node data 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
Generated for Crystal Space 2.0 by doxygen 1.6.1