simgear/bvh/BVHSubTreeCollector.cxx

   1 // Copyright (C) 2008 - 2009  Mathias Froehlich - Mathias.Froehlich@web.de
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Library General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Library General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program; if not, write to the Free Software
  15 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16 //
  17
  18 #include "BVHSubTreeCollector.hxx"
  19
  20 #include <simgear/math/SGGeometry.hxx>
  21 #include <cassert>
  22
  23 #include "BVHNode.hxx"
  24 #include "BVHGroup.hxx"
  25 #include "BVHTransform.hxx"
  26
  27 #include "BVHStaticData.hxx"
  28
  29 #include "BVHStaticNode.hxx"
  30 #include "BVHStaticTriangle.hxx"
  31 #include "BVHStaticBinary.hxx"
  32 #include "BVHStaticGeometry.hxx"
  33 #include "BVHBoundingBoxVisitor.hxx"
  34
  35 namespace simgear {
  36
  37 BVHSubTreeCollector::BVHSubTreeCollector(const SGSphered& sphere) :
  38     _sphere(sphere)
  39 {
  40 }
  41
  42 BVHSubTreeCollector::~BVHSubTreeCollector()
  43 {
  44 }
  45
  46 void
  47 BVHSubTreeCollector::apply(BVHGroup& group)
  48 {
  49     if (!intersects(_sphere, group.getBoundingSphere()))
  50         return;
  51
  52     // The _nodeList content is somehow the 'return value' of the subtree.
  53     // Set it to zero to see if we have something to collect down there.
  54     NodeList parentNodeList;
  55     pushNodeList(parentNodeList);
  56
  57     group.traverse(*this);
  58
  59     popNodeList(parentNodeList);
  60 }
  61
  62 void
  63 BVHSubTreeCollector::apply(BVHTransform& transform)
  64 {
  65     if (!intersects(_sphere, transform.getBoundingSphere()))
  66         return;
  67
  68     SGSphered sphere = _sphere;
  69     _sphere = transform.sphereToLocal(sphere);
  70
  71     NodeList parentNodeList;
  72     pushNodeList(parentNodeList);
  73
  74     transform.traverse(*this);
  75
  76     if (haveChildren()) {
  77         BVHTransform* currentBvTransform = new BVHTransform;
  78         currentBvTransform->setTransform(transform);
  79         popNodeList(parentNodeList, currentBvTransform);
  80     } else {
  81         popNodeList(parentNodeList);
  82     }
  83
  84     _sphere = sphere;
  85 }
  86
  87 void
  88 BVHSubTreeCollector::apply(BVHMotionTransform& transform)
  89 {
  90     if (!intersects(_sphere, transform.getBoundingSphere()))
  91         return;
  92
  93     SGSphered sphere = _sphere;
  94     _sphere = transform.sphereToLocal(sphere, transform.getStartTime());
  95     _sphere.expandBy(transform.sphereToLocal(sphere, transform.getEndTime()));
  96
  97     NodeList parentNodeList;
  98     pushNodeList(parentNodeList);
  99
 100     transform.traverse(*this);
 101
 102     if (haveChildren()) {
 103         BVHMotionTransform* currentBvTransform = new BVHMotionTransform;
 104         currentBvTransform->setTransform(transform);
 105         popNodeList(parentNodeList, currentBvTransform);
 106     } else {
 107         popNodeList(parentNodeList);
 108     }
 109
 110     _sphere = sphere;
 111 }
 112
 113 void
 114 BVHSubTreeCollector::apply(BVHLineGeometry& lineSegment)
 115 {
 116     if (!intersects(_sphere, lineSegment.getBoundingSphere()))
 117         return;
 118     addNode(&lineSegment);
 119 }
 120
 121 void
 122 BVHSubTreeCollector::apply(BVHStaticGeometry& node)
 123 {
 124     if (!intersects(_sphere, node.getBoundingSphere()))
 125         return;
 126
 127     assert(!_staticNode);
 128     node.traverse(*this);
 129     if (!_staticNode)
 130         return;
 131
 132     BVHStaticGeometry* staticTree;
 133     staticTree = new BVHStaticGeometry(_staticNode, node.getStaticData());
 134     addNode(staticTree);
 135     _staticNode = 0;
 136 }
 137
 138 void
 139 BVHSubTreeCollector::apply(const BVHStaticBinary& node,
 140                            const BVHStaticData& data)
 141 {
 142     assert(!_staticNode);
 143
 144     if (!intersects(_sphere, node.getBoundingBox()))
 145         return;
 146
 147     SGVec3d corner(node.getBoundingBox().getFarestCorner(_sphere.getCenter()));
 148     if (intersects(_sphere, corner)) {
 149         // If the box is totally contained in the sphere, just take it all
 150         _staticNode = &node;
 151
 152     } else {
 153         // We have still a chance to seperate something out, try it.
 154
 155         node.getLeftChild()->accept(*this, data);
 156         SGSharedPtr<const BVHStaticNode> leftStaticNode = _staticNode;
 157         _staticNode = 0;
 158         node.getRightChild()->accept(*this, data);
 159         SGSharedPtr<const BVHStaticNode> rightStaticNode = _staticNode;
 160         _staticNode = 0;
 161
 162         if (leftStaticNode) {
 163             if (rightStaticNode) {
 164                 BVHBoundingBoxVisitor bbv;
 165                 leftStaticNode->accept(bbv, data);
 166                 rightStaticNode->accept(bbv, data);
 167                 _staticNode
 168                     = new BVHStaticBinary(node.getSplitAxis(), leftStaticNode,
 169                                           rightStaticNode, bbv.getBox());
 170             } else {
 171                 _staticNode = leftStaticNode;
 172             }
 173         } else {
 174             if (rightStaticNode) {
 175                 _staticNode = rightStaticNode;
 176             } else {
 177                 // Nothing to report to parents ...
 178             }
 179         }
 180     }
 181 }
 182
 183 void
 184 BVHSubTreeCollector::apply(const BVHStaticTriangle& node,
 185                            const BVHStaticData& data)
 186 {
 187     if (!intersects(_sphere, node.getTriangle(data)))
 188         return;
 189     _staticNode = &node;
 190 }
 191
 192 void
 193 BVHSubTreeCollector::addNode(BVHNode* node)
 194 {
 195     if (!node)
 196         return;
 197     if (!_nodeList.capacity())
 198         _nodeList.reserve(64);
 199     _nodeList.push_back(node);
 200 }
 201
 202 void
 203 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList, BVHGroup* transform)
 204 {
 205     // Only do something if we really have children
 206     if (!_nodeList.empty()) {
 207         NodeList::const_iterator i;
 208         for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 209             transform->addChild(*i);
 210         parentNodeList.push_back(transform);
 211     }
 212     _nodeList.swap(parentNodeList);
 213 }
 214
 215 void
 216 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList)
 217 {
 218     // Only do something if we really have children
 219     if (!_nodeList.empty()) {
 220         if (_nodeList.size() == 1) {
 221             parentNodeList.push_back(_nodeList.front());
 222         } else {
 223             BVHGroup* group = new BVHGroup;
 224             NodeList::const_iterator i;
 225             for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 226                 group->addChild(*i);
 227             parentNodeList.push_back(group);
 228         }
 229     }
 230     _nodeList.swap(parentNodeList);
 231 }
 232
 233 SGSharedPtr<BVHNode>
 234 BVHSubTreeCollector::getNode() const
 235 {
 236     if (_nodeList.empty())
 237         return 0;
 238
 239     if (_nodeList.size() == 1)
 240         return _nodeList.front();
 241
 242     BVHGroup* group = new BVHGroup;
 243     NodeList::const_iterator i;
 244     for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 245         group->addChild(*i);
 246     return group;
 247 }
 248
 249 }