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