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 bool isInsideAabb(const Aabb& aabb) const = 0;
  56         virtual int getOctant(const Aabb& aabb) const = 0;
  57 };
  58
  59
  60 template <class T>
  61 class Octree : public Entity
  62 {
  63         typedef boost::shared_ptr<T> InsertableP;
  64
  65         struct Node : public Entity
  66         {
  67                 std::list<InsertableP> objects;
  68
  69                 Aabb aabb;
  70                 Sphere sphere;
  71
  72                 Node(const Aabb& box) :
  73                         aabb(box)
  74                 {
  75                         sphere.point = aabb.getCenter();
  76                         sphere.radius = (aabb.min - sphere.point).length();
  77                 }
  78
  79                 void draw(Scalar alpha) const
  80                 {
  81                         aabb.draw(alpha);
  82                 }
  83
  84                 void drawIfVisible(Scalar alpha, const Frustum& frustum) const
  85                 {
  86                         if (isVisible(frustum))
  87                         {
  88                                 aabb.draw(alpha);
  89                         }
  90                 }
  91
  92                 void printSize()
  93                 {
  94                         logDebug("size of node %d", objects.size());
  95                 }
  96
  97                 void getAll(std::list<InsertableP>& insertables) const
  98                 {
  99                         insertables.insert(insertables.end(), objects.begin(),
 100                                         objects.end());
 101                 }
 102
 103                 void getIfVisible(std::list<InsertableP>& insertables,
 104                                 const Frustum& frustum) const
 105                 {
 106                         typename std::list<InsertableP>::const_iterator it;
 107
 108                         for (it = objects.begin(); it != objects.end(); ++it)
 109                         {
 110                                 if ((*it)->isVisible(frustum)) insertables.push_back(*it);
 111                         }
 112                 }
 113
 114
 115                 bool isVisible(const Frustum& frustum) const
 116                 {
 117                         if (sphere.isVisible(frustum))
 118                         {
 119                                 return aabb.isVisible(frustum);
 120                         }
 121
 122                         return false;
 123                 }
 124         };
 125
 126
 127 public:
 128
 129         typedef boost::shared_ptr<Octree> Ptr;
 130         typedef typename stlplus::ntree<Node>::iterator NodeP;
 131
 132 private:
 133
 134
 135         NodeP insert(InsertableP entity, NodeP node)
 136         {
 137                 ASSERT(node.valid() && "invalid node passed");
 138                 ASSERT(entity && "null entity passed");
 139
 140                 if (entity->isInsideAabb(node->aabb))
 141                 {
 142                         return insert_recurse(entity, node);
 143                 }
 144                 else
 145                 {
 146                         node->objects.push_back(entity);
 147                         return node;
 148                 }
 149         }
 150
 151         NodeP insert_recurse(InsertableP entity, NodeP node)
 152         {
 153                 ASSERT(node.valid() && "invalid node passed");
 154                 ASSERT(entity && "null entity passed");
 155
 156                 int octantNum = entity->getOctant(node->aabb);
 157                 if (octantNum == -1)
 158                 {
 159                         node->objects.push_back(entity);
 160                         return node;
 161                 }
 162                 else
 163                 {
 164                         if ((int)tree_.children(node) <= octantNum)
 165                         {
 166                                 addChild(node, octantNum);
 167                         }
 168
 169                         NodeP child = tree_.child(node, octantNum);
 170                         ASSERT(child.valid() && "expected valid child node");
 171
 172                         return insert_recurse(entity, child);
 173                 }
 174         }
 175
 176         void addChild(NodeP node, int index)
 177         {
 178                 ASSERT(node.valid() && "invalid node passed");
 179
 180                 Aabb octant;
 181
 182                 for (int i = tree_.children(node); i <= index; ++i)
 183                 {
 184                         node->aabb.getOctant(octant, i);
 185                         tree_.append(node, octant);
 186                 }
 187         }
 188
 189
 190         void getNearbyObjects(std::list<InsertableP>& insertables,
 191                         const OctreeInsertable& entity, NodeP node) const
 192         {
 193                 ASSERT(node.valid() && "invalid node passed");
 194
 195                 node->printSize();
 196
 197                 int octantNum = entity.getOctant(node->aabb);
 198                 if (octantNum != -1)
 199                 {
 200                         node->getAll(insertables);
 201
 202                         if (octantNum < (int)tree_.children(node))
 203                         {
 204                                 NodeP child = tree_.child(node, octantNum);
 205                                 ASSERT(child.valid() && "expected valid child node");
 206
 207                                 getNearbyObjects(insertables, entity, child);
 208                         }
 209                 }
 210                 else
 211                 {
 212                         logDebug("getting all the rest...");
 213                         getAll(insertables, node);
 214                 }
 215         }
 216
 217
 218         void getAll(std::list<InsertableP>& insertables, NodeP node) const
 219         {
 220                 ASSERT(node.valid() && "invalid node passed");
 221
 222                 node->getAll(insertables);
 223
 224                 for (unsigned i = 0; i < tree_.children(node); ++i)
 225                 {
 226                         NodeP child = tree_.child(node, i);
 227                         ASSERT(child.valid() && "expected valid child node");
 228
 229                         getAll(insertables, child);
 230                 }
 231         }
 232
 233         void getIfVisible(std::list<InsertableP>& insertables,
 234                         const Frustum& frustum, NodeP node) const
 235         {
 236                 ASSERT(node.valid() && "invalid node passed");
 237
 238                 // try to cull by sphere
 239                 Frustum::Collision collision = frustum.contains(node->sphere);
 240                 if (collision == Frustum::OUTSIDE) return;
 241
 242                 // try to cull by aabb
 243                 collision = frustum.contains(node->aabb);
 244                 if (collision == Frustum::OUTSIDE) return;
 245
 246
 247                 if (collision == Frustum::INSIDE)
 248                 {
 249                         node->getAll(insertables);
 250                 }
 251                 else // collision == Frustum::INTERSECT
 252                 {
 253                         node->getIfVisible(insertables, frustum);
 254                 }
 255
 256                 if (tree_.children(node) > 0)
 257                 {
 258                         if (collision == Frustum::INSIDE)
 259                         {
 260                                 for (unsigned i = 0; i < tree_.children(node); ++i)
 261                                 {
 262                                         NodeP child = tree_.child(node, i);
 263                                         ASSERT(child.valid() && "expected valid child node");
 264
 265                                         getAll(insertables, child);
 266                                 }
 267                         }
 268                         else // collision == Frustum::INTERSECT
 269                         {
 270                                 for (unsigned i = 0; i < tree_.children(node); ++i)
 271                                 {
 272                                         NodeP child = tree_.child(node, i);
 273                                         ASSERT(child.valid() && "expected valid child node");
 274
 275                                         getIfVisible(insertables, frustum, child);
 276                                 }
 277                         }
 278                 }
 279         }
 280
 281
 282         mutable stlplus::ntree<Node> tree_;
 283
 284
 285 public:
 286
 287         void print(NodeP node)
 288         {
 289                 logInfo("-----");
 290                 logInfo("depth to node: %d", tree_.depth(node));
 291                 logInfo("size of node: %d", tree_.size(node));
 292         }
 293
 294         static Ptr alloc(const Node& rootNode)
 295         {
 296                 return Ptr(new Octree(rootNode));
 297         }
 298
 299         explicit Octree(const Node& rootNode)
 300         {
 301                 tree_.insert(rootNode);
 302         }
 303
 304
 305         NodeP insert(InsertableP entity)
 306         {
 307                 return insert(entity, tree_.root());
 308         }
 309
 310         void remove(InsertableP entity, NodeP node)
 311         {
 312                 ASSERT(entity && "null entity passed");
 313                 ASSERT(node.valid() && "invalid node passed");
 314
 315                 typename std::list<InsertableP>::iterator it;
 316                 it = std::find(node->objects.begin(), node->objects.end(), entity);
 317
 318                 if (it != node->objects.end())
 319                 {
 320                         node->objects.erase(it);
 321                 }
 322         }
 323
 324
 325         NodeP reinsert(InsertableP entity, NodeP node)
 326         {
 327                 remove(entity, node);
 328                 return insert(entity);
 329         }
 330
 331
 332         void draw(Scalar alpha) const
 333         {
 334                 std::list<InsertableP> objects;
 335                 getAll(objects);
 336
 337                 typename std::list<InsertableP>::const_iterator it;
 338                 for (it = objects.begin(); it != objects.end(); ++it)
 339                 {
 340                         (*it)->draw(alpha);
 341                 }
 342         }
 343
 344         void drawIfVisible(Scalar alpha, const Frustum& frustum) const
 345         {
 346                 std::list<InsertableP> objects;
 347                 //getIfVisible(objects, frustum);
 348                 getNearbyObjects(objects, *savedObj);
 349
 350                 typename std::list<InsertableP>::const_iterator it;
 351                 for (it = objects.begin(); it != objects.end(); ++it)
 352                 {
 353                         (*it)->draw(alpha);
 354                 }
 355         }
 356
 357
 358         void getAll(std::list<InsertableP>& insertables) const
 359         {
 360                 getAll(insertables, tree_.root());
 361         }
 362
 363         void getIfVisible(std::list<InsertableP>& insertables,
 364                         const Frustum& frustum) const
 365         {
 366                 getIfVisible(insertables, frustum, tree_.root());
 367         }
 368
 369         mutable const OctreeInsertable* savedObj;
 370
 371
 372         void getNearbyObjects(std::list<InsertableP>& insertables,
 373                         const OctreeInsertable& entity) const
 374         {
 375                 logDebug("--- GETTING NEARBY");
 376                 getNearbyObjects(insertables, entity, tree_.root());
 377                 logDebug("---");
 378                 savedObj = &entity;
 379         }
 380 };
 381
 382
 383 } // namespace Mf
 384
 385 #endif // _MOOF_OCTREE_HH_
 386
 387 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 388