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