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

   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 #include "Camera.hh"
  30 #include "Log.hh"
  31 #include "Octree.hh"
  32
  33
  34 namespace Mf {
  35
  36
  37 void Octree::sort()
  38 {
  39         stlplus::ntree<OctreeNode>::prefix_iterator it;
  40
  41         for (it = tree_.prefix_begin(); it != tree_.prefix_end(); ++it)
  42         {
  43                 it->sort();
  44         }
  45 }
  46
  47
  48 stlplus::ntree<OctreeNode>::iterator Octree::insert(stlplus::ntree<OctreeNode>::iterator node,
  49                 EntityP entity)
  50 {
  51         ASSERT(node.valid() && "invalid node passed");
  52         ASSERT(entity && "null entity passed");
  53
  54         Plane::Halfspace halfspace;
  55         int octantNum = -1;
  56
  57         Plane xy = node->getAabb().getPlaneXY();
  58         halfspace = xy.intersectsSphere(entity->getSphere());
  59         if (halfspace == Plane::INTERSECT)
  60         {
  61                 halfspace = xy.intersectsAabb(entity->getAabb());
  62         }
  63
  64         if (halfspace == Plane::POSITIVE)
  65         {
  66                 Plane xz = node->getAabb().getPlaneXZ();
  67                 halfspace = xz.intersectsSphere(entity->getSphere());
  68                 if (halfspace == Plane::INTERSECT)
  69                 {
  70                         halfspace = xz.intersectsAabb(entity->getAabb());
  71                 }
  72
  73                 if (halfspace == Plane::POSITIVE)
  74                 {
  75                         Plane yz = node->getAabb().getPlaneYZ();
  76                         halfspace = yz.intersectsSphere(entity->getSphere());
  77                         if (halfspace == Plane::INTERSECT)
  78                         {
  79                                 halfspace = yz.intersectsAabb(entity->getAabb());
  80                         }
  81
  82                         if (halfspace == Plane::POSITIVE)
  83                         {
  84                                 octantNum = 2;
  85                         }
  86                         else if (halfspace == Plane::NEGATIVE)
  87                         {
  88                                 octantNum = 3;
  89                         }
  90                 }
  91                 else if (halfspace == Plane::NEGATIVE)
  92                 {
  93                         Plane yz = node->getAabb().getPlaneYZ();
  94                         halfspace = yz.intersectsSphere(entity->getSphere());
  95                         if (halfspace == Plane::INTERSECT)
  96                         {
  97                                 halfspace = yz.intersectsAabb(entity->getAabb());
  98                         }
  99
 100                         if (halfspace == Plane::POSITIVE)
 101                         {
 102                                 octantNum = 1;
 103                         }
 104                         else if (halfspace == Plane::NEGATIVE)
 105                         {
 106                                 octantNum = 0;
 107                         }
 108                 }
 109         }
 110         else if (halfspace == Plane::NEGATIVE)
 111         {
 112                 Plane xz = node->getAabb().getPlaneXZ();
 113                 halfspace = xz.intersectsSphere(entity->getSphere());
 114                 if (halfspace == Plane::INTERSECT)
 115                 {
 116                         halfspace = xz.intersectsAabb(entity->getAabb());
 117                 }
 118
 119                 if (halfspace == Plane::POSITIVE)
 120                 {
 121                         Plane yz = node->getAabb().getPlaneYZ();
 122                         halfspace = yz.intersectsSphere(entity->getSphere());
 123                         if (halfspace == Plane::INTERSECT)
 124                         {
 125                                 halfspace = yz.intersectsAabb(entity->getAabb());
 126                         }
 127
 128                         if (halfspace == Plane::POSITIVE)
 129                         {
 130                                 octantNum = 6;
 131                         }
 132                         else if (halfspace == Plane::NEGATIVE)
 133                         {
 134                                 octantNum = 7;
 135                         }
 136                 }
 137                 else if (halfspace == Plane::NEGATIVE)
 138                 {
 139                         Plane yz = node->getAabb().getPlaneYZ();
 140                         halfspace = yz.intersectsSphere(entity->getSphere());
 141                         if (halfspace == Plane::INTERSECT)
 142                         {
 143                                 halfspace = yz.intersectsAabb(entity->getAabb());
 144                         }
 145
 146                         if (halfspace == Plane::POSITIVE)
 147                         {
 148                                 octantNum = 5;
 149                         }
 150                         else if (halfspace == Plane::NEGATIVE)
 151                         {
 152                                 octantNum = 4;
 153                         }
 154                 }
 155         }
 156
 157         if (octantNum == -1)
 158         {
 159                 node->objects.push_front(entity);
 160                 return node;
 161         }
 162         else
 163         {
 164                 if ((int)tree_.children(node) <= octantNum)
 165                 {
 166                         addChild(node, octantNum);
 167                 }
 168
 169                 stlplus::ntree<OctreeNode>::iterator child = tree_.child(node, octantNum);
 170                 ASSERT(child.valid() && "expected valid child node");
 171
 172                 return insert(child, entity);
 173         }
 174 }
 175
 176 stlplus::ntree<OctreeNode>::iterator Octree::reinsert(EntityP entity,
 177                 stlplus::ntree<OctreeNode>::iterator node)
 178 {
 179         ASSERT(entity && "null entity passed");
 180         ASSERT(node.valid() && "invalid node passed");
 181
 182         std::list<EntityP>::iterator it;
 183         it = std::find(node->objects.begin(), node->objects.end(), entity);
 184
 185         if (it != node->objects.end())
 186         {
 187                 node->objects.erase(it);
 188         }
 189
 190         return insert(entity);
 191 }
 192
 193
 194 void Octree::addChild(stlplus::ntree<OctreeNode>::iterator node, int index)
 195 {
 196         ASSERT(node.valid() && "invalid node passed");
 197
 198         Aabb octant;
 199
 200         for (int i = tree_.children(node); i <= index; ++i)
 201         {
 202                 node->getAabb().getOctant(octant, i);
 203                 tree_.append(node, octant);
 204         }
 205 }
 206
 207
 208 void Octree::draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
 209 {
 210         ASSERT(node.valid() && "invalid node passed");
 211
 212         node->draw(alpha);
 213
 214         for (unsigned i = 0; i < tree_.children(node); ++i)
 215         {
 216                 stlplus::ntree<OctreeNode>::iterator child = tree_.child(node, i);
 217                 ASSERT(child.valid() && "expected valid child node");
 218
 219                 draw(child, alpha);
 220         }
 221 }
 222
 223 void Octree::drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
 224                 Scalar alpha, const Camera& cam)
 225 {
 226         ASSERT(node.valid() && "invalid node passed");
 227
 228         // try to cull by sphere
 229         Frustum::Collision collision =
 230                 cam.getFrustum().containsSphere(node->getSphere());
 231         if (collision == Frustum::OUTSIDE) return;
 232
 233         // try to cull by aabb
 234         collision = cam.getFrustum().containsAabb(node->getAabb());
 235         if (collision == Frustum::OUTSIDE) return;
 236
 237
 238         if (collision == Frustum::INSIDE)
 239         {
 240                 node->draw(alpha);
 241         }
 242         else // collision == Frustum::INTERSECT
 243         {
 244                 node->drawIfVisible(alpha, cam);
 245         }
 246
 247         if (tree_.children(node) > 0)
 248         {
 249                 if (collision == Frustum::INSIDE)
 250                 {
 251                         for (unsigned i = 0; i < tree_.children(node); ++i)
 252                         {
 253                                 stlplus::ntree<OctreeNode>::iterator child = tree_.child(node, i);
 254                                 ASSERT(child.valid() && "expected valid child node");
 255
 256                                 draw(child, alpha);
 257                         }
 258                 }
 259                 else // collision == Frustum::INTERSECT
 260                 {
 261                         for (unsigned i = 0; i < tree_.children(node); ++i)
 262                         {
 263                                 stlplus::ntree<OctreeNode>::iterator child = tree_.child(node, i);
 264                                 ASSERT(child.valid() && "expected valid child node");
 265
 266                                 drawIfVisible(child, alpha, cam);
 267                         }
 268                 }
 269         }
 270 }
 271
 272
 273 } // namespace Mf
 274
 275 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 276