CrystalSpace

Public API Reference

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.7.6.1