Dogcows Code - chaz/yoink/blob - src/Moof/Octree.hh

   1
   2 /*]  Copyright (c) 2009-2010, Charles McGarvey  [**************************
   3 **]  All rights reserved.
   4 *
   5 * vi:ts=4 sw=4 tw=75
   6 *
   7 * Distributable under the terms and conditions of the 2-clause BSD license;
   8 * see the file COPYING for a complete text of the license.
   9 *
  10 **************************************************************************/
  11
  12 #ifndef _MOOF_OCTREE_HH_
  13 #define _MOOF_OCTREE_HH_
  14
  15 #include <algorithm>
  16 #include <list>
  17
  18 #include <boost/shared_ptr.hpp>
  19 #include <stlplus/ntree.hpp>
  20
  21 #include <Moof/Aabb.hh>
  22 #include <Moof/Drawable.hh>
  23 #include <Moof/Entity.hh>
  24 #include <Moof/Frustum.hh>
  25 #include <Moof/Log.hh>
  26 #include <Moof/Math.hh>
  27 #include <Moof/Sphere.hh>
  28
  29
  30 namespace Mf {
  31
  32
  33 struct OctreeInsertable
  34 {
  35         virtual ~OctreeInsertable() {}
  36
  37         virtual int getOctant(const Aabb<3>& aabb) const = 0;
  38 };
  39
  40
  41 template <class T>
  42 class Octree : public Entity
  43 {
  44         typedef boost::shared_ptr<T> InsertableP;
  45
  46         struct Node : public Entity
  47         {
  48                 std::list<InsertableP> objects;
  49
  50                 Node(const Aabb<3>& aabb)
  51                 {
  52                         mAabb = aabb;
  53                         mSphere.point = mAabb.getCenter();
  54                         mSphere.radius = (mAabb.min - mSphere.point).length();
  55                 }
  56
  57                 void draw(Scalar alpha) const
  58                 {
  59                         mAabb.draw(alpha);
  60                 }
  61
  62                 void printSize()
  63                 {
  64                         logInfo << "size of node " << objects.size() << std::endl;
  65                 }
  66
  67                 void getAll(std::list<InsertableP>& insertables) const
  68                 {
  69                         insertables.insert(insertables.end(), objects.begin(),
  70                                         objects.end());
  71                 }
  72
  73                 void getIfVisible(std::list<InsertableP>& insertables,
  74                                 const Frustum& frustum) const
  75                 {
  76                         typename std::list<InsertableP>::const_iterator it;
  77
  78                         for (it = objects.begin(); it != objects.end(); ++it)
  79                         {
  80                                 if ((*it)->isVisible(frustum)) insertables.push_back(*it);
  81                         }
  82                 }
  83         };
  84
  85
  86 public:
  87
  88         typedef boost::shared_ptr<Octree> Ptr;
  89         typedef typename stlplus::ntree<Node>::iterator NodeP;
  90
  91 private:
  92
  93
  94         NodeP insert(InsertableP entity, NodeP node)
  95         {
  96                 ASSERT(node.valid() && "invalid node passed");
  97                 ASSERT(entity && "null entity passed");
  98
  99                 Aabb<3> entityAabb = entity->getAabb();
 100                 Aabb<3> nodeAabb = node->getAabb();
 101
 102                 if (!(entityAabb.max[0] < nodeAabb.max[0] &&
 103                           entityAabb.min[0] > nodeAabb.min[0] &&
 104                           entityAabb.max[1] < nodeAabb.max[1] &&
 105                           entityAabb.min[1] > nodeAabb.min[1] &&
 106                           entityAabb.max[2] < nodeAabb.max[2] &&
 107                           entityAabb.min[2] > nodeAabb.min[2]))
 108                 {
 109                         node->objects.push_back(entity);
 110                         return node;
 111                 }
 112                 else
 113                 {
 114                         return insert_recurse(entity, node);
 115                 }
 116         }
 117
 118         NodeP insert_recurse(InsertableP entity, NodeP node)
 119         {
 120                 ASSERT(node.valid() && "invalid node passed");
 121                 ASSERT(entity && "null entity passed");
 122
 123                 int octantNum = entity->getOctant(node->getAabb());
 124                 if (octantNum == -1)
 125                 {
 126                         node->objects.push_back(entity);
 127                         return node;
 128                 }
 129                 else
 130                 {
 131                         if ((int)mTree.children(node) <= octantNum)
 132                         {
 133                                 addChild(node, octantNum);
 134                         }
 135
 136                         NodeP child = mTree.child(node, octantNum);
 137                         ASSERT(child.valid() && "expected valid child node");
 138
 139                         return insert_recurse(entity, child);
 140                 }
 141         }
 142
 143         void addChild(NodeP node, int index)
 144         {
 145                 ASSERT(node.valid() && "invalid node passed");
 146
 147                 Aabb<3> octant;
 148
 149                 for (int i = mTree.children(node); i <= index; ++i)
 150                 {
 151                         node->getAabb().getOctant(octant, i);
 152                         mTree.append(node, octant);
 153                 }
 154         }
 155
 156
 157         void getNearbyObjects(std::list<InsertableP>& insertables,
 158                         const OctreeInsertable& entity, NodeP node) const
 159         {
 160                 ASSERT(node.valid() && "invalid node passed");
 161
 162                 node->printSize();
 163
 164                 int octantNum = entity.getOctant(node->getAabb());
 165                 if (octantNum != -1)
 166                 {
 167                         node->getAll(insertables);
 168
 169                         if (octantNum < (int)mTree.children(node))
 170                         {
 171                                 NodeP child = mTree.child(node, octantNum);
 172                                 ASSERT(child.valid() && "expected valid child node");
 173
 174                                 getNearbyObjects(insertables, entity, child);
 175                         }
 176                 }
 177                 else
 178                 {
 179                         logInfo("getting all the rest...");
 180                         getAll(insertables, node);
 181                 }
 182         }
 183
 184
 185         void getAll(std::list<InsertableP>& insertables, NodeP node) const
 186         {
 187                 ASSERT(node.valid() && "invalid node passed");
 188
 189                 node->getAll(insertables);
 190
 191                 for (unsigned i = 0; i < mTree.children(node); ++i)
 192                 {
 193                         NodeP child = mTree.child(node, i);
 194                         ASSERT(child.valid() && "expected valid child node");
 195
 196                         getAll(insertables, child);
 197                 }
 198         }
 199
 200         void getIfVisible(std::list<InsertableP>& insertables,
 201                         const Frustum& frustum, NodeP node) const
 202         {
 203                 ASSERT(node.valid() && "invalid node passed");
 204
 205                 // try to cull by sphere
 206                 Frustum::Collision collision = frustum.contains(node->getSphere());
 207                 if (collision == Frustum::OUTSIDE) return;
 208
 209                 // try to cull by aabb
 210                 collision = frustum.contains(node->getAabb());
 211                 if (collision == Frustum::OUTSIDE) return;
 212
 213
 214                 if (collision == Frustum::INSIDE)
 215                 {
 216                         node->getAll(insertables);
 217                 }
 218                 else // collision == Frustum::INTERSECT
 219                 {
 220                         node->getIfVisible(insertables, frustum);
 221                 }
 222
 223                 if (mTree.children(node) > 0)
 224                 {
 225                         if (collision == Frustum::INSIDE)
 226                         {
 227                                 for (unsigned i = 0; i < mTree.children(node); ++i)
 228                                 {
 229                                         NodeP child = mTree.child(node, i);
 230                                         ASSERT(child.valid() && "expected valid child node");
 231
 232                                         getAll(insertables, child);
 233                                 }
 234                         }
 235                         else // collision == Frustum::INTERSECT
 236                         {
 237                                 for (unsigned i = 0; i < mTree.children(node); ++i)
 238                                 {
 239                                         NodeP child = mTree.child(node, i);
 240                                         ASSERT(child.valid() && "expected valid child node");
 241
 242                                         getIfVisible(insertables, frustum, child);
 243                                 }
 244                         }
 245                 }
 246         }
 247
 248
 249         mutable stlplus::ntree<Node> mTree;
 250
 251
 252 public:
 253
 254         void print(NodeP node)
 255         {
 256                 logInfo("-----");
 257                 logInfo << "depth to node: " << mTree.depth(node) << std::endl;
 258                 logInfo << "size of node: " << mTree.size(node) << std::endl;
 259         }
 260
 261         static Ptr alloc(const Node& rootNode)
 262         {
 263                 return Ptr(new Octree(rootNode));
 264         }
 265
 266         explicit Octree(const Node& rootNode)
 267         {
 268                 mTree.insert(rootNode);
 269         }
 270
 271
 272         NodeP insert(InsertableP entity)
 273         {
 274                 return insert(entity, mTree.root());
 275         }
 276
 277         void remove(InsertableP entity, NodeP node)
 278         {
 279                 ASSERT(entity && "null entity passed");
 280                 ASSERT(node.valid() && "invalid node passed");
 281
 282                 typename std::list<InsertableP>::iterator it;
 283                 it = std::find(node->objects.begin(), node->objects.end(), entity);
 284
 285                 if (it != node->objects.end())
 286                 {
 287                         node->objects.erase(it);
 288                 }
 289         }
 290
 291
 292         NodeP reinsert(InsertableP entity, NodeP node)
 293         {
 294                 remove(entity, node);
 295                 return insert(entity);
 296         }
 297
 298
 299         void draw(Scalar alpha) const
 300         {
 301                 std::list<InsertableP> objects;
 302                 getAll(objects);
 303
 304                 typename std::list<InsertableP>::const_iterator it;
 305                 for (it = objects.begin(); it != objects.end(); ++it)
 306                 {
 307                         (*it)->draw(alpha);
 308                 }
 309         }
 310
 311         void drawIfVisible(Scalar alpha, const Frustum& frustum) const
 312         {
 313                 std::list<InsertableP> objects;
 314                 getIfVisible(objects, frustum);
 315                 //getNearbyObjects(objects, *savedObj);
 316
 317                 typename std::list<InsertableP>::const_iterator it;
 318                 for (it = objects.begin(); it != objects.end(); ++it)
 319                 {
 320                         (*it)->draw(alpha);
 321                 }
 322         }
 323
 324
 325         void getAll(std::list<InsertableP>& insertables) const
 326         {
 327                 getAll(insertables, mTree.root());
 328         }
 329
 330         void getIfVisible(std::list<InsertableP>& insertables,
 331                         const Frustum& frustum) const
 332         {
 333                 getIfVisible(insertables, frustum, mTree.root());
 334         }
 335
 336         mutable const OctreeInsertable* savedObj;
 337
 338
 339         void getNearbyObjects(std::list<InsertableP>& insertables,
 340                         const OctreeInsertable& entity) const
 341         {
 342                 logInfo("--- GETTING NEARBY");
 343                 getNearbyObjects(insertables, entity, mTree.root());
 344                 logInfo("---");
 345                 savedObj = &entity;
 346         }
 347 };
 348
 349
 350 } // namespace Mf
 351
 352 #endif // _MOOF_OCTREE_HH_
 353