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 OctreeNodeP Octree::insert(EntityP entity, OctreeNodeP node)
  49 {
  50         ASSERT(node.valid() && "invalid node passed");
  51         ASSERT(entity && "null entity passed");
  52
  53         int octantNum = -1;
  54
  55         Plane::Halfspace halfspace;
  56
  57         // TODO this method needs a lot of work
  58         Plane xy = node->getAabb().getPlaneXY();
  59
  60
  61         // make sure the entity is fully inside the volume
  62         if (!(entity->getAabb().max[0] < node->getAabb().max[0] &&
  63                         entity->getAabb().min[0] > node->getAabb().min[0] &&
  64                         entity->getAabb().max[1] < node->getAabb().max[1] &&
  65                         entity->getAabb().min[1] > node->getAabb().min[1] &&
  66                         entity->getAabb().max[2] < node->getAabb().max[2] &&
  67                         entity->getAabb().min[2] > node->getAabb().min[2]))
  68         {
  69                 // TODO this check is only needed for the root node, if we're inside the
  70                 // volume of the root node, we'll be fully inside the child as
  71                 // determined by trying to insert the parent node
  72                 goto done;
  73         }
  74
  75         halfspace = xy.intersects(entity->getSphere());
  76         if (halfspace == Plane::INTERSECT)
  77         {
  78                 halfspace = xy.intersects(entity->getAabb());
  79         }
  80
  81         if (halfspace == Plane::POSITIVE)
  82         {
  83                 Plane xz = node->getAabb().getPlaneXZ();
  84                 halfspace = xz.intersects(entity->getSphere());
  85                 if (halfspace == Plane::INTERSECT)
  86                 {
  87                         halfspace = xz.intersects(entity->getAabb());
  88                 }
  89
  90                 if (halfspace == Plane::POSITIVE)
  91                 {
  92                         Plane yz = node->getAabb().getPlaneYZ();
  93                         halfspace = yz.intersects(entity->getSphere());
  94                         if (halfspace == Plane::INTERSECT)
  95                         {
  96                                 halfspace = yz.intersects(entity->getAabb());
  97                         }
  98
  99                         if (halfspace == Plane::POSITIVE)
 100                         {
 101                                 octantNum = 2;
 102                         }
 103                         else if (halfspace == Plane::NEGATIVE)
 104                         {
 105                                 octantNum = 3;
 106                         }
 107                 }
 108                 else if (halfspace == Plane::NEGATIVE)
 109                 {
 110                         Plane yz = node->getAabb().getPlaneYZ();
 111                         halfspace = yz.intersects(entity->getSphere());
 112                         if (halfspace == Plane::INTERSECT)
 113                         {
 114                                 halfspace = yz.intersects(entity->getAabb());
 115                         }
 116
 117                         if (halfspace == Plane::POSITIVE)
 118                         {
 119                                 octantNum = 1;
 120                         }
 121                         else if (halfspace == Plane::NEGATIVE)
 122                         {
 123                                 octantNum = 0;
 124                         }
 125                 }
 126         }
 127         else if (halfspace == Plane::NEGATIVE)
 128         {
 129                 Plane xz = node->getAabb().getPlaneXZ();
 130                 halfspace = xz.intersects(entity->getSphere());
 131                 if (halfspace == Plane::INTERSECT)
 132                 {
 133                         halfspace = xz.intersects(entity->getAabb());
 134                 }
 135
 136                 if (halfspace == Plane::POSITIVE)
 137                 {
 138                         Plane yz = node->getAabb().getPlaneYZ();
 139                         halfspace = yz.intersects(entity->getSphere());
 140                         if (halfspace == Plane::INTERSECT)
 141                         {
 142                                 halfspace = yz.intersects(entity->getAabb());
 143                         }
 144
 145                         if (halfspace == Plane::POSITIVE)
 146                         {
 147                                 octantNum = 6;
 148                         }
 149                         else if (halfspace == Plane::NEGATIVE)
 150                         {
 151                                 octantNum = 7;
 152                         }
 153                 }
 154                 else if (halfspace == Plane::NEGATIVE)
 155                 {
 156                         Plane yz = node->getAabb().getPlaneYZ();
 157                         halfspace = yz.intersects(entity->getSphere());
 158                         if (halfspace == Plane::INTERSECT)
 159                         {
 160                                 halfspace = yz.intersects(entity->getAabb());
 161                         }
 162
 163                         if (halfspace == Plane::POSITIVE)
 164                         {
 165                                 octantNum = 5;
 166                         }
 167                         else if (halfspace == Plane::NEGATIVE)
 168                         {
 169                                 octantNum = 4;
 170                         }
 171                 }
 172         }
 173
 174 done:
 175
 176         if (octantNum == -1)
 177         {
 178                 node->objects.push_front(entity);
 179                 return node;
 180         }
 181         else
 182         {
 183                 if ((int)tree_.children(node) <= octantNum)
 184                 {
 185                         addChild(node, octantNum);
 186                 }
 187
 188                 OctreeNodeP child = tree_.child(node, octantNum);
 189                 ASSERT(child.valid() && "expected valid child node");
 190
 191                 return insert(entity, child);
 192         }
 193 }
 194
 195 OctreeNodeP Octree::reinsert(EntityP entity, OctreeNodeP node)
 196 {
 197         ASSERT(entity && "null entity passed");
 198         ASSERT(node.valid() && "invalid node passed");
 199
 200         std::list<EntityP>::iterator it;
 201         it = std::find(node->objects.begin(), node->objects.end(), entity);
 202
 203         if (it != node->objects.end())
 204         {
 205                 node->objects.erase(it);
 206         }
 207
 208         return insert(entity);
 209 }
 210
 211
 212 void Octree::addChild(OctreeNodeP node, int index)
 213 {
 214         ASSERT(node.valid() && "invalid node passed");
 215
 216         Aabb octant;
 217
 218         for (int i = tree_.children(node); i <= index; ++i)
 219         {
 220                 node->getAabb().getOctant(octant, i);
 221                 tree_.append(node, octant);
 222         }
 223 }
 224
 225
 226 void Octree::draw(Scalar alpha, OctreeNodeP node)
 227 {
 228         ASSERT(node.valid() && "invalid node passed");
 229
 230         node->draw(alpha);
 231
 232         for (unsigned i = 0; i < tree_.children(node); ++i)
 233         {
 234                 OctreeNodeP child = tree_.child(node, i);
 235                 ASSERT(child.valid() && "expected valid child node");
 236
 237                 draw(alpha, child);
 238         }
 239 }
 240
 241 void Octree::drawIfVisible(Scalar alpha, const Camera& cam, OctreeNodeP node)
 242 {
 243         ASSERT(node.valid() && "invalid node passed");
 244
 245         // try to cull by sphere
 246         Frustum::Collision collision =
 247                 cam.getFrustum().contains(node->getSphere());
 248         if (collision == Frustum::OUTSIDE) return;
 249
 250         // try to cull by aabb
 251         collision = cam.getFrustum().contains(node->getAabb());
 252         if (collision == Frustum::OUTSIDE) return;
 253
 254
 255         if (collision == Frustum::INSIDE)
 256         {
 257                 node->draw(alpha);
 258         }
 259         else // collision == Frustum::INTERSECT
 260         {
 261                 node->drawIfVisible(alpha, cam);
 262         }
 263
 264         if (tree_.children(node) > 0)
 265         {
 266                 if (collision == Frustum::INSIDE)
 267                 {
 268                         for (unsigned i = 0; i < tree_.children(node); ++i)
 269                         {
 270                                 OctreeNodeP child = tree_.child(node, i);
 271                                 ASSERT(child.valid() && "expected valid child node");
 272
 273                                 draw(alpha, child);
 274                         }
 275                 }
 276                 else // collision == Frustum::INTERSECT
 277                 {
 278                         for (unsigned i = 0; i < tree_.children(node); ++i)
 279                         {
 280                                 OctreeNodeP child = tree_.child(node, i);
 281                                 ASSERT(child.valid() && "expected valid child node");
 282
 283                                 drawIfVisible(alpha, cam, child);
 284                         }
 285                 }
 286         }
 287 }
 288
 289
 290 } // namespace Mf
 291
 292 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 293