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 <list>
  33
  34 #include <boost/shared_ptr.hpp>
  35
  36 #include <stlplus/ntree.hpp>
  37
  38 #include <Moof/Aabb.hh>
  39 #include <Moof/Drawable.hh>
  40 #include <Moof/Entity.hh>
  41 #include <Moof/Math.hh>
  42 #include <Moof/Sphere.hh>
  43
  44
  45 namespace Mf {
  46
  47
  48 struct OctreeNode : public Entity
  49 {
  50         std::list<EntityPtr> objects;
  51
  52         OctreeNode()
  53         {
  54                 aabb_.min = Vector3(-1.0, -1.0, -1.0);
  55                 aabb_.max = Vector3(1.0, 1.0, 1.0);
  56                 sphere_.init(Vector3(0.0, 0.0, 0.0), 1.41421);
  57         }
  58
  59         OctreeNode(const Aabb& aabb)
  60         {
  61                 aabb_ = aabb;
  62                 sphere_.point = aabb.getCenter();
  63                 sphere_.radius = (aabb.min - sphere_.point).length();
  64         }
  65
  66         void draw(Scalar alpha) const
  67         {
  68                 std::list<EntityPtr>::const_iterator it;
  69
  70                 for (it = objects.begin(); it != objects.end(); ++it)
  71                 {
  72                         (*it)->draw(alpha);
  73                 }
  74                 if (!objects.empty())
  75                         aabb_.draw(); // temporary
  76         }
  77
  78         void drawIfVisible(Scalar alpha, const Camera& cam) const
  79         {
  80                 std::list<EntityPtr>::const_iterator it;
  81
  82                 for (it = objects.begin(); it != objects.end(); ++it)
  83                 {
  84                         (*it)->drawIfVisible(alpha, cam);
  85                 }
  86                 if (!objects.empty())
  87                         aabb_.draw();
  88         }
  89
  90
  91         bool isVisible(const Camera& cam) const
  92         {
  93                 if (sphere_.isVisible(cam))
  94                 {
  95                         return aabb_.isVisible(cam);
  96                 }
  97
  98                 return false;
  99         }
 100 };
 101
 102
 103 class Octree;
 104 typedef boost::shared_ptr<Octree> OctreePtr;
 105
 106 class Octree
 107 {
 108
 109         stlplus::ntree<OctreeNode> root_;
 110
 111 public:
 112
 113         explicit Octree(const OctreeNode& rootNode)
 114         {
 115                 root_.insert(rootNode);
 116         }
 117
 118         void insert(EntityPtr entity)
 119         {
 120                 insert(root_.root(), entity);
 121         }
 122
 123         void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
 124         {
 125                 Plane::Halfspace halfspace;
 126                 int octantNum = -1;
 127
 128                 if (!node.valid())
 129                 {
 130                         std::cerr << "cannot insert into invalid node" << std::endl;
 131                         return;
 132                 }
 133
 134                 Plane xy = node->getAabb().getPlaneXY();
 135                 halfspace = xy.intersectsSphere(entity->getSphere());
 136
 137                 if (halfspace == Plane::POSITIVE)
 138                 {
 139                         Plane xz = node->getAabb().getPlaneXZ();
 140                         halfspace = xz.intersectsSphere(entity->getSphere());
 141
 142                         if (halfspace == Plane::POSITIVE)
 143                         {
 144                                 Plane yz = node->getAabb().getPlaneYZ();
 145                                 halfspace = yz.intersectsSphere(entity->getSphere());
 146
 147                                 if (halfspace == Plane::POSITIVE)
 148                                 {
 149                                         octantNum = 2;
 150                                 }
 151                                 else if (halfspace == Plane::NEGATIVE)
 152                                 {
 153                                         octantNum = 3;
 154                                 }
 155                         }
 156                         else if (halfspace == Plane::NEGATIVE)
 157                         {
 158                                 Plane yz = node->getAabb().getPlaneYZ();
 159                                 halfspace = yz.intersectsSphere(entity->getSphere());
 160
 161                                 if (halfspace == Plane::POSITIVE)
 162                                 {
 163                                         octantNum = 1;
 164                                 }
 165                                 else if (halfspace == Plane::NEGATIVE)
 166                                 {
 167                                         octantNum = 0;
 168                                 }
 169                         }
 170                 }
 171                 else if (halfspace == Plane::NEGATIVE)
 172                 {
 173                         Plane xz = node->getAabb().getPlaneXZ();
 174                         halfspace = xz.intersectsSphere(entity->getSphere());
 175
 176                         if (halfspace == Plane::POSITIVE)
 177                         {
 178                                 Plane yz = node->getAabb().getPlaneYZ();
 179                                 halfspace = yz.intersectsSphere(entity->getSphere());
 180
 181                                 if (halfspace == Plane::POSITIVE)
 182                                 {
 183                                         octantNum = 6;
 184                                 }
 185                                 else if (halfspace == Plane::NEGATIVE)
 186                                 {
 187                                         octantNum = 7;
 188                                 }
 189                         }
 190                         else if (halfspace == Plane::NEGATIVE)
 191                         {
 192                                 Plane yz = node->getAabb().getPlaneYZ();
 193                                 halfspace = yz.intersectsSphere(entity->getSphere());
 194
 195                                 if (halfspace == Plane::POSITIVE)
 196                                 {
 197                                         octantNum = 5;
 198                                 }
 199                                 else if (halfspace == Plane::NEGATIVE)
 200                                 {
 201                                         octantNum = 4;
 202                                 }
 203                         }
 204                 }
 205
 206                 if (octantNum == -1)
 207                 {
 208                         node->objects.push_front(entity);
 209                         //return node;
 210                 }
 211                 else
 212                 {
 213                         if (root_.children(node) == 0)
 214                         {
 215                                 addChildren(node);
 216                         }
 217
 218                         stlplus::ntree<OctreeNode>::iterator child = root_.child(node, octantNum);
 219
 220                         if (child.valid())
 221                         {
 222                                 return insert(child, entity);
 223                         }
 224                         else
 225                         {
 226                                 std::cerr << "expected but found no child at index " << octantNum << std::endl;
 227                                 //return stlplus::ntree<OctreeNode>::iterator();
 228                         }
 229                         //return WeakPtr();
 230                 }
 231         }
 232
 233         void addChildren(stlplus::ntree<OctreeNode>::iterator node)
 234         {
 235                 Aabb octant;
 236
 237                 if (!node.valid())
 238                 {
 239                         std::cerr << "cannot add children to invalid node" << std::endl;
 240                         return;
 241                 }
 242
 243                 for (int i = 0; i < 8; ++i)
 244                 {
 245                         node->getAabb().getOctant(octant, i);
 246                         //OctreeNode octantNode(octant);
 247
 248                         root_.append(node, octant);
 249                 }
 250         }
 251
 252         void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
 253         {
 254                 if (!node.valid())
 255                 {
 256                         std::cerr << "cannot draw null child node :-(" << std::endl;
 257                         return;
 258                 }
 259
 260                 node->draw(alpha);
 261
 262                 for (unsigned i = 0; i < root_.children(node); ++i)
 263                 {
 264                         stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
 265
 266                         if (child.valid())
 267                         {
 268                                 draw(child, alpha);
 269                         }
 270                         else
 271                         {
 272                                 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
 273                         }
 274
 275                 }
 276         }
 277
 278         void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
 279                         Scalar alpha, const Camera& cam)
 280         {
 281                 //node.drawIfVisible(alpha, cam);
 282
 283                 if (!node.valid())
 284                 {
 285                         std::cerr << "invalid child while drawing :-(" << std::endl;
 286                         return;
 287                 }
 288
 289                 Frustum::Collision collision =
 290                         cam.getFrustum().containsSphere(node->getSphere());
 291                 if (collision == Frustum::OUTSIDE) return;
 292
 293                 collision = cam.getFrustum().containsAabb(node->getAabb());
 294                 if (collision == Frustum::OUTSIDE) return;
 295
 296
 297                 if (collision == Frustum::INSIDE)
 298                 {
 299                         node->draw(alpha);
 300                 }
 301                 else // collision == Frustum::INTERSECT
 302                 {
 303                         node->drawIfVisible(alpha, cam);
 304                 }
 305
 306                 if (root_.children(node) > 0)
 307                 {
 308                         if (collision == Frustum::INSIDE)
 309                         {
 310                                 for (unsigned i = 0; i < root_.children(node); ++i)
 311                                 {
 312                                         stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
 313
 314                                         if (child.valid())
 315                                         {
 316                                                 draw(child, alpha);
 317                                         }
 318                                         else
 319                                         {
 320                                                 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
 321                                         }
 322
 323                                 }
 324                         }
 325                         else // collision == Frustum::INTERSECT
 326                         {
 327                                 for (unsigned i = 0; i < root_.children(node); ++i)
 328                                 {
 329                                         stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
 330
 331                                         if (child.valid())
 332                                         {
 333                                                 drawIfVisible(child, alpha, cam);
 334                                         }
 335                                         else
 336                                         {
 337                                                 std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
 338                                         }
 339                                 }
 340                         }
 341                 }
 342         }
 343
 344         void drawIfVisible(Scalar alpha, const Camera& cam)
 345         {
 346                 drawIfVisible(root_.root(), alpha, cam);
 347         }
 348
 349 };
 350
 351
 352
 353 } // namespace Mf
 354
 355 #endif // _MOOF_OCTREE_HH_
 356
 357 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 358