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

   1
   2 /*******************************************************************************
   3
   4  Copyright (c) 2009, Charles McGarvey
   5  All rights reserved.
   6
   7  Redistribution   and   use  in  source  and  binary  forms,  with  or  without
   8  modification, are permitted provided that the following conditions are met:
   9
  10    * Redistributions  of  source  code  must retain the above copyright notice,
  11      this list of conditions and the following disclaimer.
  12    * Redistributions  in binary form must reproduce the above copyright notice,
  13      this  list of conditions and the following disclaimer in the documentation
  14      and/or other materials provided with the distribution.
  15
  16  THIS  SOFTWARE  IS  PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  AND  ANY  EXPRESS  OR  IMPLIED  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  DISCLAIMED.  IN  NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  20  FOR  ANY  DIRECT,  INDIRECT,  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  DAMAGES  (INCLUDING,  BUT  NOT  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  22  SERVICES;  LOSS  OF  USE,  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  23  CAUSED  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  24  OR  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  25  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26
  27 *******************************************************************************/
  28
  29 #ifndef _MOOF_OCTREE_HH_
  30 #define _MOOF_OCTREE_HH_
  31
  32 #include <algorithm>
  33 #include <list>
  34
  35 #include <boost/shared_ptr.hpp>
  36
  37 #include <stlplus/ntree.hpp>
  38
  39 #include <Moof/Aabb.hh>
  40 #include <Moof/Drawable.hh>
  41 #include <Moof/Entity.hh>
  42 #include <Moof/Frustum.hh>
  43 #include <Moof/Log.hh>
  44 #include <Moof/Math.hh>
  45 #include <Moof/Sphere.hh>
  46
  47
  48 namespace Mf {
  49
  50
  51 struct OctreeInsertable
  52 {
  53         virtual ~OctreeInsertable() {}
  54
  55         virtual int getOctant(const Aabb<3>& aabb) const = 0;
  56 };
  57
  58
  59 template <class T>
  60 class Octree : public Entity
  61 {
  62         typedef boost::shared_ptr<T> InsertableP;
  63
  64         struct Node : public Entity
  65         {
  66                 std::list<InsertableP> objects;
  67
  68                 Node(const Aabb<3>& aabb)
  69                 {
  70                         mAabb = aabb;
  71                         mSphere.point = mAabb.getCenter();
  72                         mSphere.radius = (mAabb.min - mSphere.point).length();
  73                 }
  74
  75                 void draw(Scalar alpha) const
  76                 {
  77                         mAabb.draw(alpha);
  78                 }
  79
  80                 void printSize()
  81                 {
  82                         logDebug("size of node %d", objects.size());
  83                 }
  84
  85                 void getAll(std::list<InsertableP>& insertables) const
  86                 {
  87                         insertables.insert(insertables.end(), objects.begin(),
  88                                         objects.end());
  89                 }
  90
  91                 void getIfVisible(std::list<InsertableP>& insertables,
  92                                 const Frustum& frustum) const
  93                 {
  94                         typename std::list<InsertableP>::const_iterator it;
  95
  96                         for (it = objects.begin(); it != objects.end(); ++it)
  97                         {
  98                                 if ((*it)->isVisible(frustum)) insertables.push_back(*it);
  99                         }
 100                 }
 101         };
 102
 103
 104 public:
 105
 106         typedef boost::shared_ptr<Octree> Ptr;
 107         typedef typename stlplus::ntree<Node>::iterator NodeP;
 108
 109 private:
 110
 111
 112         NodeP insert(InsertableP entity, NodeP node)
 113         {
 114                 ASSERT(node.valid() && "invalid node passed");
 115                 ASSERT(entity && "null entity passed");
 116
 117                 Aabb<3> entityAabb = entity->getAabb();
 118                 Aabb<3> nodeAabb = node->getAabb();
 119
 120                 if (!(entityAabb.max[0] < nodeAabb.max[0] &&
 121                           entityAabb.min[0] > nodeAabb.min[0] &&
 122                           entityAabb.max[1] < nodeAabb.max[1] &&
 123                           entityAabb.min[1] > nodeAabb.min[1] &&
 124                           entityAabb.max[2] < nodeAabb.max[2] &&
 125                           entityAabb.min[2] > nodeAabb.min[2]))
 126                 {
 127                         node->objects.push_back(entity);
 128                         return node;
 129                 }
 130                 else
 131                 {
 132                         return insert_recurse(entity, node);
 133                 }
 134         }
 135
 136         NodeP insert_recurse(InsertableP entity, NodeP node)
 137         {
 138                 ASSERT(node.valid() && "invalid node passed");
 139                 ASSERT(entity && "null entity passed");
 140
 141                 int octantNum = entity->getOctant(node->getAabb());
 142                 if (octantNum == -1)
 143                 {
 144                         node->objects.push_back(entity);
 145                         return node;
 146                 }
 147                 else
 148                 {
 149                         if ((int)mTree.children(node) <= octantNum)
 150                         {
 151                                 addChild(node, octantNum);
 152                         }
 153
 154                         NodeP child = mTree.child(node, octantNum);
 155                         ASSERT(child.valid() && "expected valid child node");
 156
 157                         return insert_recurse(entity, child);
 158                 }
 159         }
 160
 161         void addChild(NodeP node, int index)
 162         {
 163                 ASSERT(node.valid() && "invalid node passed");
 164
 165                 Aabb<3> octant;
 166
 167                 for (int i = mTree.children(node); i <= index; ++i)
 168                 {
 169                         node->getAabb().getOctant(octant, i);
 170                         mTree.append(node, octant);
 171                 }
 172         }
 173
 174
 175         void getNearbyObjects(std::list<InsertableP>& insertables,
 176                         const OctreeInsertable& entity, NodeP node) const
 177         {
 178                 ASSERT(node.valid() && "invalid node passed");
 179
 180                 node->printSize();
 181
 182                 int octantNum = entity.getOctant(node->getAabb());
 183                 if (octantNum != -1)
 184                 {
 185                         node->getAll(insertables);
 186
 187                         if (octantNum < (int)mTree.children(node))
 188                         {
 189                                 NodeP child = mTree.child(node, octantNum);
 190                                 ASSERT(child.valid() && "expected valid child node");
 191
 192                                 getNearbyObjects(insertables, entity, child);
 193                         }
 194                 }
 195                 else
 196                 {
 197                         logDebug("getting all the rest...");
 198                         getAll(insertables, node);
 199                 }
 200         }
 201
 202
 203         void getAll(std::list<InsertableP>& insertables, NodeP node) const
 204         {
 205                 ASSERT(node.valid() && "invalid node passed");
 206
 207                 node->getAll(insertables);
 208
 209                 for (unsigned i = 0; i < mTree.children(node); ++i)
 210                 {
 211                         NodeP child = mTree.child(node, i);
 212                         ASSERT(child.valid() && "expected valid child node");
 213
 214                         getAll(insertables, child);
 215                 }
 216         }
 217
 218         void getIfVisible(std::list<InsertableP>& insertables,
 219                         const Frustum& frustum, NodeP node) const
 220         {
 221                 ASSERT(node.valid() && "invalid node passed");
 222
 223                 // try to cull by sphere
 224                 Frustum::Collision collision = frustum.contains(node->getSphere());
 225                 if (collision == Frustum::OUTSIDE) return;
 226
 227                 // try to cull by aabb
 228                 collision = frustum.contains(node->getAabb());
 229                 if (collision == Frustum::OUTSIDE) return;
 230
 231
 232                 if (collision == Frustum::INSIDE)
 233                 {
 234                         node->getAll(insertables);
 235                 }
 236                 else // collision == Frustum::INTERSECT
 237                 {
 238                         node->getIfVisible(insertables, frustum);
 239                 }
 240
 241                 if (mTree.children(node) > 0)
 242                 {
 243                         if (collision == Frustum::INSIDE)
 244                         {
 245                                 for (unsigned i = 0; i < mTree.children(node); ++i)
 246                                 {
 247                                         NodeP child = mTree.child(node, i);
 248                                         ASSERT(child.valid() && "expected valid child node");
 249
 250                                         getAll(insertables, child);
 251                                 }
 252                         }
 253                         else // collision == Frustum::INTERSECT
 254                         {
 255                                 for (unsigned i = 0; i < mTree.children(node); ++i)
 256                                 {
 257                                         NodeP child = mTree.child(node, i);
 258                                         ASSERT(child.valid() && "expected valid child node");
 259
 260                                         getIfVisible(insertables, frustum, child);
 261                                 }
 262                         }
 263                 }
 264         }
 265
 266
 267         mutable stlplus::ntree<Node> mTree;
 268
 269
 270 public:
 271
 272         void print(NodeP node)
 273         {
 274                 logInfo("-----");
 275                 logInfo("depth to node: %d", mTree.depth(node));
 276                 logInfo("size of node: %d", mTree.size(node));
 277         }
 278
 279         static Ptr alloc(const Node& rootNode)
 280         {
 281                 return Ptr(new Octree(rootNode));
 282         }
 283
 284         explicit Octree(const Node& rootNode)
 285         {
 286                 mTree.insert(rootNode);
 287         }
 288
 289
 290         NodeP insert(InsertableP entity)
 291         {
 292                 return insert(entity, mTree.root());
 293         }
 294
 295         void remove(InsertableP entity, NodeP node)
 296         {
 297                 ASSERT(entity && "null entity passed");
 298                 ASSERT(node.valid() && "invalid node passed");
 299
 300                 typename std::list<InsertableP>::iterator it;
 301                 it = std::find(node->objects.begin(), node->objects.end(), entity);
 302
 303                 if (it != node->objects.end())
 304                 {
 305                         node->objects.erase(it);
 306                 }
 307         }
 308
 309
 310         NodeP reinsert(InsertableP entity, NodeP node)
 311         {
 312                 remove(entity, node);
 313                 return insert(entity);
 314         }
 315
 316
 317         void draw(Scalar alpha) const
 318         {
 319                 std::list<InsertableP> objects;
 320                 getAll(objects);
 321
 322                 typename std::list<InsertableP>::const_iterator it;
 323                 for (it = objects.begin(); it != objects.end(); ++it)
 324                 {
 325                         (*it)->draw(alpha);
 326                 }
 327         }
 328
 329         void drawIfVisible(Scalar alpha, const Frustum& frustum) const
 330         {
 331                 std::list<InsertableP> objects;
 332                 getIfVisible(objects, frustum);
 333                 //getNearbyObjects(objects, *savedObj);
 334
 335                 typename std::list<InsertableP>::const_iterator it;
 336                 for (it = objects.begin(); it != objects.end(); ++it)
 337                 {
 338                         (*it)->draw(alpha);
 339                 }
 340         }
 341
 342
 343         void getAll(std::list<InsertableP>& insertables) const
 344         {
 345                 getAll(insertables, mTree.root());
 346         }
 347
 348         void getIfVisible(std::list<InsertableP>& insertables,
 349                         const Frustum& frustum) const
 350         {
 351                 getIfVisible(insertables, frustum, mTree.root());
 352         }
 353
 354         mutable const OctreeInsertable* savedObj;
 355
 356
 357         void getNearbyObjects(std::list<InsertableP>& insertables,
 358                         const OctreeInsertable& entity) const
 359         {
 360                 logDebug("--- GETTING NEARBY");
 361                 getNearbyObjects(insertables, entity, mTree.root());
 362                 logDebug("---");
 363                 savedObj = &entity;
 364         }
 365 };
 366
 367
 368 } // namespace Mf
 369
 370 #endif // _MOOF_OCTREE_HH_
 371
 372 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 373