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