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