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>
22 #include "BVHNode.hxx"
23 #include "BVHGroup.hxx"
24 #include "BVHTransform.hxx"
26 #include "BVHStaticData.hxx"
28 #include "BVHStaticNode.hxx"
29 #include "BVHStaticTriangle.hxx"
30 #include "BVHStaticBinary.hxx"
31 #include "BVHStaticGeometry.hxx"
32 #include "BVHBoundingBoxVisitor.hxx"
36 BVHSubTreeCollector::BVHSubTreeCollector(const SGSphered& sphere) :
41 BVHSubTreeCollector::~BVHSubTreeCollector()
46 BVHSubTreeCollector::apply(BVHGroup& group)
48 if (!intersects(_sphere, group.getBoundingSphere()))
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);
56 group.traverse(*this);
58 popNodeList(parentNodeList);
62 BVHSubTreeCollector::apply(BVHTransform& transform)
64 if (!intersects(_sphere, transform.getBoundingSphere()))
67 SGSphered sphere = _sphere;
68 _sphere = transform.sphereToLocal(sphere);
70 NodeList parentNodeList;
71 pushNodeList(parentNodeList);
73 transform.traverse(*this);
76 BVHTransform* currentBvTransform = new BVHTransform;
77 currentBvTransform->setTransform(transform);
78 popNodeList(parentNodeList, currentBvTransform);
80 popNodeList(parentNodeList);
87 BVHSubTreeCollector::apply(BVHMotionTransform& transform)
89 if (!intersects(_sphere, transform.getBoundingSphere()))
92 SGSphered sphere = _sphere;
93 _sphere = transform.sphereToLocal(sphere, transform.getStartTime());
94 _sphere.expandBy(transform.sphereToLocal(sphere, transform.getEndTime()));
96 NodeList parentNodeList;
97 pushNodeList(parentNodeList);
99 transform.traverse(*this);
101 if (haveChildren()) {
102 BVHMotionTransform* currentBvTransform = new BVHMotionTransform;
103 currentBvTransform->setTransform(transform);
104 popNodeList(parentNodeList, currentBvTransform);
106 popNodeList(parentNodeList);
113 BVHSubTreeCollector::apply(BVHLineGeometry& lineSegment)
115 if (!intersects(_sphere, lineSegment.getBoundingSphere()))
117 addNode(&lineSegment);
121 BVHSubTreeCollector::apply(BVHStaticGeometry& node)
123 if (!intersects(_sphere, node.getBoundingSphere()))
126 assert(!_staticNode);
127 node.traverse(*this);
131 BVHStaticGeometry* staticTree;
132 staticTree = new BVHStaticGeometry(_staticNode, node.getStaticData());
138 BVHSubTreeCollector::apply(const BVHStaticBinary& node,
139 const BVHStaticData& data)
141 assert(!_staticNode);
143 if (!intersects(_sphere, node.getBoundingBox()))
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
152 // We have still a chance to seperate something out, try it.
154 node.getLeftChild()->accept(*this, data);
155 SGSharedPtr<const BVHStaticNode> leftStaticNode = _staticNode;
157 node.getRightChild()->accept(*this, data);
158 SGSharedPtr<const BVHStaticNode> rightStaticNode = _staticNode;
161 if (leftStaticNode) {
162 if (rightStaticNode) {
163 BVHBoundingBoxVisitor bbv;
164 leftStaticNode->accept(bbv, data);
165 rightStaticNode->accept(bbv, data);
167 = new BVHStaticBinary(node.getSplitAxis(), leftStaticNode,
168 rightStaticNode, bbv.getBox());
170 _staticNode = leftStaticNode;
173 if (rightStaticNode) {
174 _staticNode = rightStaticNode;
176 // Nothing to report to parents ...
183 BVHSubTreeCollector::apply(const BVHStaticTriangle& node,
184 const BVHStaticData& data)
186 if (!intersects(_sphere, node.getTriangle(data)))
192 BVHSubTreeCollector::addNode(BVHNode* node)
196 if (!_nodeList.capacity())
197 _nodeList.reserve(64);
198 _nodeList.push_back(node);
202 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList, BVHGroup* transform)
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);
211 _nodeList.swap(parentNodeList);
215 BVHSubTreeCollector::popNodeList(NodeList& parentNodeList)
217 // Only do something if we really have children
218 if (!_nodeList.empty()) {
219 if (_nodeList.size() == 1) {
220 parentNodeList.push_back(_nodeList.front());
222 BVHGroup* group = new BVHGroup;
223 NodeList::const_iterator i;
224 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)
226 parentNodeList.push_back(group);
229 _nodeList.swap(parentNodeList);
233 BVHSubTreeCollector::getNode() const
235 if (_nodeList.empty())
238 if (_nodeList.size() == 1)
239 return _nodeList.front();
241 BVHGroup* group = new BVHGroup;
242 NodeList::const_iterator i;
243 for (i = _nodeList.begin(); i != _nodeList.end(); ++i)