1 // Copyright (C) 2008 - 2009 Mathias Froehlich - Mathias.Froehlich@web.de
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.
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.
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.
18 #include "BVHSubTreeCollector.hxx"
20 #include <simgear/math/SGGeometry.hxx>
23 #include "BVHNode.hxx"
24 #include "BVHGroup.hxx"
25 #include "BVHTransform.hxx"
27 #include "BVHStaticData.hxx"
29 #include "BVHStaticNode.hxx"
30 #include "BVHStaticTriangle.hxx"
31 #include "BVHStaticBinary.hxx"
32 #include "BVHStaticGeometry.hxx"
33 #include "BVHBoundingBoxVisitor.hxx"
37 BVHSubTreeCollector::BVHSubTreeCollector(const SGSphered& sphere) :
42 BVHSubTreeCollector::~BVHSubTreeCollector()
47 BVHSubTreeCollector::apply(BVHGroup& group)
49 if (!intersects(_sphere, group.getBoundingSphere()))
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);
57 group.traverse(*this);
59 popNodeList(parentNodeList);
63 BVHSubTreeCollector::apply(BVHTransform& transform)
65 if (!intersects(_sphere, transform.getBoundingSphere()))
68 SGSphered sphere = _sphere;
69 _sphere = transform.sphereToLocal(sphere);
71 NodeList parentNodeList;
72 pushNodeList(parentNodeList);
74 transform.traverse(*this);
77 BVHTransform* currentBvTransform = new BVHTransform;
78 currentBvTransform->setTransform(transform);
79 popNodeList(parentNodeList, currentBvTransform);
81 popNodeList(parentNodeList);
88 BVHSubTreeCollector::apply(BVHMotionTransform& transform)
90 if (!intersects(_sphere, transform.getBoundingSphere()))
93 SGSphered sphere = _sphere;
94 _sphere = transform.sphereToLocal(sphere, transform.getStartTime());
95 _sphere.expandBy(transform.sphereToLocal(sphere, transform.getEndTime()));
97 NodeList parentNodeList;
98 pushNodeList(parentNodeList);
100 transform.traverse(*this);
102 if (haveChildren()) {
103 BVHMotionTransform* currentBvTransform = new BVHMotionTransform;
104 currentBvTransform->setTransform(transform);
105 popNodeList(parentNodeList, currentBvTransform);
107 popNodeList(parentNodeList);
114 BVHSubTreeCollector::apply(BVHLineGeometry& lineSegment)
116 if (!intersects(_sphere, lineSegment.getBoundingSphere()))
118 addNode(&lineSegment);
122 BVHSubTreeCollector::apply(BVHStaticGeometry& node)
124 if (!intersects(_sphere, node.getBoundingSphere()))
127 assert(!_staticNode);
128 node.traverse(*this);
132 BVHStaticGeometry* staticTree;
133 staticTree = new BVHStaticGeometry(_staticNode, node.getStaticData());
139 BVHSubTreeCollector::apply(const BVHStaticBinary& node,
140 const BVHStaticData& data)
142 assert(!_staticNode);
144 if (!intersects(_sphere, node.getBoundingBox()))
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
153 // We have still a chance to seperate something out, try it.
155 node.getLeftChild()->accept(*this, data);
156 SGSharedPtr<const BVHStaticNode> leftStaticNode = _staticNode;
158 node.getRightChild()->accept(*this, data);
159 SGSharedPtr<const BVHStaticNode> rightStaticNode = _staticNode;
162 if (leftStaticNode) {
163 if (rightStaticNode) {
164 BVHBoundingBoxVisitor bbv;
165 leftStaticNode->accept(bbv, data);
166 rightStaticNode->accept(bbv, data);
168 = new BVHStaticBinary(node.getSplitAxis(), leftStaticNode,
169 rightStaticNode, bbv.getBox());
171 _staticNode = leftStaticNode;
174 if (rightStaticNode) {
175 _staticNode = rightStaticNode;
177 // Nothing to report to parents ...
184 BVHSubTreeCollector::apply(const BVHStaticTriangle& node,
185 const BVHStaticData& data)
187 if (!intersects(_sphere, node.getTriangle(data)))
193 BVHSubTreeCollector::addNode(BVHNode* node)
197 if (!_nodeList.capacity())
198 _nodeList.reserve(64);
199 _nodeList.push_back(node);
203 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList, BVHGroup* transform)
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);
212 _nodeList.swap(parentNodeList);
216 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList)
218 // Only do something if we really have children
219 if (!_nodeList.empty()) {
220 if (_nodeList.size() == 1) {
221 parentNodeList.push_back(_nodeList.front());
223 BVHGroup* group = new BVHGroup;
224 NodeList::const_iterator i;
225 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
227 parentNodeList.push_back(group);
230 _nodeList.swap(parentNodeList);
234 BVHSubTreeCollector::getNode() const
236 if (_nodeList.empty())
239 if (_nodeList.size() == 1)
240 return _nodeList.front();
242 BVHGroup* group = new BVHGroup;
243 NodeList::const_iterator i;
244 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)