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(BVHPageNode& group)
  64 {
  65     if (!intersects(_sphere, group.getBoundingSphere()))
  66         return;
  67
  68     // The _nodeList content is somehow the 'return value' of the subtree.
  69     // Set it to zero to see if we have something to collect down there.
  70     NodeList parentNodeList;
  71     pushNodeList(parentNodeList);
  72
  73     group.traverse(*this);
  74
  75     popNodeList(parentNodeList);
  76 }
  77
  78 void
  79 BVHSubTreeCollector::apply(BVHTransform& transform)
  80 {
  81     if (!intersects(_sphere, transform.getBoundingSphere()))
  82         return;
  83
  84     SGSphered sphere = _sphere;
  85     _sphere = transform.sphereToLocal(sphere);
  86
  87     NodeList parentNodeList;
  88     pushNodeList(parentNodeList);
  89
  90     transform.traverse(*this);
  91
  92     if (haveChildren()) {
  93         BVHTransform* currentBvTransform = new BVHTransform;
  94         currentBvTransform->setTransform(transform);
  95         popNodeList(parentNodeList, currentBvTransform);
  96     } else {
  97         popNodeList(parentNodeList);
  98     }
  99
 100     _sphere = sphere;
 101 }
 102
 103 void
 104 BVHSubTreeCollector::apply(BVHMotionTransform& transform)
 105 {
 106     if (!intersects(_sphere, transform.getBoundingSphere()))
 107         return;
 108
 109     SGSphered sphere = _sphere;
 110     _sphere = transform.sphereToLocal(sphere, transform.getStartTime());
 111     _sphere.expandBy(transform.sphereToLocal(sphere, transform.getEndTime()));
 112
 113     NodeList parentNodeList;
 114     pushNodeList(parentNodeList);
 115
 116     transform.traverse(*this);
 117
 118     if (haveChildren()) {
 119         BVHMotionTransform* currentBvTransform = new BVHMotionTransform;
 120         currentBvTransform->setTransform(transform);
 121         popNodeList(parentNodeList, currentBvTransform);
 122     } else {
 123         popNodeList(parentNodeList);
 124     }
 125
 126     _sphere = sphere;
 127 }
 128
 129 void
 130 BVHSubTreeCollector::apply(BVHLineGeometry& lineSegment)
 131 {
 132     if (!intersects(_sphere, lineSegment.getBoundingSphere()))
 133         return;
 134     addNode(&lineSegment);
 135 }
 136
 137 void
 138 BVHSubTreeCollector::apply(BVHStaticGeometry& node)
 139 {
 140     if (!intersects(_sphere, node.getBoundingSphere()))
 141         return;
 142
 143     assert(!_staticNode);
 144     node.traverse(*this);
 145     if (!_staticNode)
 146         return;
 147
 148     BVHStaticGeometry* staticTree;
 149     staticTree = new BVHStaticGeometry(_staticNode, node.getStaticData());
 150     addNode(staticTree);
 151     _staticNode = 0;
 152 }
 153
 154 void
 155 BVHSubTreeCollector::apply(const BVHStaticBinary& node,
 156                            const BVHStaticData& data)
 157 {
 158     assert(!_staticNode);
 159
 160     if (!intersects(_sphere, node.getBoundingBox()))
 161         return;
 162
 163     SGVec3d corner(node.getBoundingBox().getFarestCorner(_sphere.getCenter()));
 164     if (intersects(_sphere, corner)) {
 165         // If the box is totally contained in the sphere, just take it all
 166         _staticNode = &node;
 167
 168     } else {
 169         // We have still a chance to seperate something out, try it.
 170
 171         node.getLeftChild()->accept(*this, data);
 172         SGSharedPtr<const BVHStaticNode> leftStaticNode = _staticNode;
 173         _staticNode = 0;
 174         node.getRightChild()->accept(*this, data);
 175         SGSharedPtr<const BVHStaticNode> rightStaticNode = _staticNode;
 176         _staticNode = 0;
 177
 178         if (leftStaticNode) {
 179             if (rightStaticNode) {
 180                 BVHBoundingBoxVisitor bbv;
 181                 leftStaticNode->accept(bbv, data);
 182                 rightStaticNode->accept(bbv, data);
 183                 _staticNode
 184                     = new BVHStaticBinary(node.getSplitAxis(), leftStaticNode,
 185                                           rightStaticNode, bbv.getBox());
 186             } else {
 187                 _staticNode = leftStaticNode;
 188             }
 189         } else {
 190             if (rightStaticNode) {
 191                 _staticNode = rightStaticNode;
 192             } else {
 193                 // Nothing to report to parents ...
 194             }
 195         }
 196     }
 197 }
 198
 199 void
 200 BVHSubTreeCollector::apply(const BVHStaticTriangle& node,
 201                            const BVHStaticData& data)
 202 {
 203     if (!intersects(_sphere, node.getTriangle(data)))
 204         return;
 205     _staticNode = &node;
 206 }
 207
 208 void
 209 BVHSubTreeCollector::addNode(BVHNode* node)
 210 {
 211     if (!node)
 212         return;
 213     if (!_nodeList.capacity())
 214         _nodeList.reserve(64);
 215     _nodeList.push_back(node);
 216 }
 217
 218 void
 219 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList, BVHGroup* transform)
 220 {
 221     // Only do something if we really have children
 222     if (!_nodeList.empty()) {
 223         NodeList::const_iterator i;
 224         for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 225             transform->addChild(*i);
 226         parentNodeList.push_back(transform);
 227     }
 228     _nodeList.swap(parentNodeList);
 229 }
 230
 231 void
 232 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList)
 233 {
 234     // Only do something if we really have children
 235     if (!_nodeList.empty()) {
 236         if (_nodeList.size() == 1) {
 237             parentNodeList.push_back(_nodeList.front());
 238         } else {
 239             BVHGroup* group = new BVHGroup;
 240             NodeList::const_iterator i;
 241             for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 242                 group->addChild(*i);
 243             parentNodeList.push_back(group);
 244         }
 245     }
 246     _nodeList.swap(parentNodeList);
 247 }
 248
 249 SGSharedPtr<BVHNode>
 250 BVHSubTreeCollector::getNode() const
 251 {
 252     if (_nodeList.empty())
 253         return 0;
 254
 255     if (_nodeList.size() == 1)
 256         return _nodeList.front();
 257
 258     BVHGroup* group = new BVHGroup;
 259     NodeList::const_iterator i;
 260     for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
 261         group->addChild(*i);
 262     return group;
 263 }
 264
 265 }