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(BVHPageNode& group)
65 if (!intersects(_sphere, group.getBoundingSphere()))
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);
73 group.traverse(*this);
75 popNodeList(parentNodeList);
79 BVHSubTreeCollector::apply(BVHTransform& transform)
81 if (!intersects(_sphere, transform.getBoundingSphere()))
84 SGSphered sphere = _sphere;
85 _sphere = transform.sphereToLocal(sphere);
87 NodeList parentNodeList;
88 pushNodeList(parentNodeList);
90 transform.traverse(*this);
93 BVHTransform* currentBvTransform = new BVHTransform;
94 currentBvTransform->setTransform(transform);
95 popNodeList(parentNodeList, currentBvTransform);
97 popNodeList(parentNodeList);
104 BVHSubTreeCollector::apply(BVHMotionTransform& transform)
106 if (!intersects(_sphere, transform.getBoundingSphere()))
109 SGSphered sphere = _sphere;
110 _sphere = transform.sphereToLocal(sphere, transform.getStartTime());
111 _sphere.expandBy(transform.sphereToLocal(sphere, transform.getEndTime()));
113 NodeList parentNodeList;
114 pushNodeList(parentNodeList);
116 transform.traverse(*this);
118 if (haveChildren()) {
119 BVHMotionTransform* currentBvTransform = new BVHMotionTransform;
120 currentBvTransform->setTransform(transform);
121 popNodeList(parentNodeList, currentBvTransform);
123 popNodeList(parentNodeList);
130 BVHSubTreeCollector::apply(BVHLineGeometry& lineSegment)
132 if (!intersects(_sphere, lineSegment.getBoundingSphere()))
134 addNode(&lineSegment);
138 BVHSubTreeCollector::apply(BVHStaticGeometry& node)
140 if (!intersects(_sphere, node.getBoundingSphere()))
143 assert(!_staticNode);
144 node.traverse(*this);
148 BVHStaticGeometry* staticTree;
149 staticTree = new BVHStaticGeometry(_staticNode, node.getStaticData());
155 BVHSubTreeCollector::apply(const BVHStaticBinary& node,
156 const BVHStaticData& data)
158 assert(!_staticNode);
160 if (!intersects(_sphere, node.getBoundingBox()))
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
169 // We have still a chance to seperate something out, try it.
171 node.getLeftChild()->accept(*this, data);
172 SGSharedPtr<const BVHStaticNode> leftStaticNode = _staticNode;
174 node.getRightChild()->accept(*this, data);
175 SGSharedPtr<const BVHStaticNode> rightStaticNode = _staticNode;
178 if (leftStaticNode) {
179 if (rightStaticNode) {
180 BVHBoundingBoxVisitor bbv;
181 leftStaticNode->accept(bbv, data);
182 rightStaticNode->accept(bbv, data);
184 = new BVHStaticBinary(node.getSplitAxis(), leftStaticNode,
185 rightStaticNode, bbv.getBox());
187 _staticNode = leftStaticNode;
190 if (rightStaticNode) {
191 _staticNode = rightStaticNode;
193 // Nothing to report to parents ...
200 BVHSubTreeCollector::apply(const BVHStaticTriangle& node,
201 const BVHStaticData& data)
203 if (!intersects(_sphere, node.getTriangle(data)))
209 BVHSubTreeCollector::addNode(BVHNode* node)
213 if (!_nodeList.capacity())
214 _nodeList.reserve(64);
215 _nodeList.push_back(node);
219 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList, BVHGroup* transform)
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);
228 _nodeList.swap(parentNodeList);
232 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList)
234 // Only do something if we really have children
235 if (!_nodeList.empty()) {
236 if (_nodeList.size() == 1) {
237 parentNodeList.push_back(_nodeList.front());
239 BVHGroup* group = new BVHGroup;
240 NodeList::const_iterator i;
241 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
243 parentNodeList.push_back(group);
246 _nodeList.swap(parentNodeList);
250 BVHSubTreeCollector::getNode() const
252 if (_nodeList.empty())
255 if (_nodeList.size() == 1)
256 return _nodeList.front();
258 BVHGroup* group = new BVHGroup;
259 NodeList::const_iterator i;
260 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)