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 #ifndef BVHStaticGeometryBuilder_hxx
19 #define BVHStaticGeometryBuilder_hxx
21 #include <simgear/structure/SGReferenced.hxx>
22 #include <simgear/structure/SGSharedPtr.hxx>
24 #include "BVHVisitor.hxx"
25 #include "BVHNode.hxx"
26 #include "BVHGroup.hxx"
27 #include "BVHTransform.hxx"
29 #include "BVHStaticData.hxx"
31 #include "BVHStaticNode.hxx"
32 #include "BVHStaticLeaf.hxx"
33 #include "BVHStaticTriangle.hxx"
34 #include "BVHStaticBinary.hxx"
35 #include "BVHStaticGeometry.hxx"
39 class BVHStaticGeometryBuilder : public SGReferenced {
41 BVHStaticGeometryBuilder() :
42 _staticData(new BVHStaticData),
44 _currentMaterialIndex(~0u)
46 virtual ~BVHStaticGeometryBuilder()
50 LeafRef(const BVHStaticLeaf* leaf, const BVHStaticData& data) :
52 _box(_leaf->computeBoundingBox(data)),
53 _center(_leaf->computeCenter(data))
55 SGSharedPtr<const BVHStaticLeaf> _leaf;
59 typedef std::list<LeafRef> LeafRefList;
61 struct LeafRefLess : public std::binary_function<LeafRef, LeafRef, bool> {
62 LeafRefLess(unsigned sortAxis) : _sortAxis(sortAxis) {}
63 bool operator()(const LeafRef& x, const LeafRef& y)
64 { return x._center[_sortAxis] < y._center[_sortAxis]; }
68 SGSharedPtr<BVHStaticData> _staticData;
69 LeafRefList _leafRefList;
71 typedef std::map<SGVec3f, unsigned> VertexMap;
74 void setCurrentMaterial(const SGMaterial* material)
76 _currentMaterial = material;
77 _currentMaterialIndex = addMaterial(material);
79 const SGMaterial* getCurrentMaterial() const
81 return _currentMaterial;
83 unsigned addMaterial(const SGMaterial* material)
85 MaterialMap::const_iterator i = _materialMap.find(material);
86 if (i != _materialMap.end())
88 unsigned index = _staticData->addMaterial(material);
89 _materialMap[material] = index;
93 typedef std::map<const SGMaterial*, unsigned> MaterialMap;
94 MaterialMap _materialMap;
95 const SGMaterial* _currentMaterial;
96 unsigned _currentMaterialIndex;
98 void addTriangle(const SGVec3f& v1, const SGVec3f& v2, const SGVec3f& v3)
100 unsigned indices[3] = { addVertex(v1), addVertex(v2), addVertex(v3) };
101 BVHStaticTriangle* staticTriangle;
102 staticTriangle = new BVHStaticTriangle(_currentMaterialIndex, indices);
103 _leafRefList.push_back(LeafRef(staticTriangle, *_staticData));
105 unsigned addVertex(const SGVec3f& v)
107 VertexMap::const_iterator i = _vertexMap.find(v);
108 if (i != _vertexMap.end())
110 unsigned index = _staticData->addVertex(v);
111 _vertexMap[v] = index;
115 BVHStaticGeometry* buildTree()
117 const BVHStaticNode* tree = buildTreeRecursive(_leafRefList);
120 return new BVHStaticGeometry(tree, _staticData);
125 centerSplitLeafs(unsigned splitAxis, const double& splitValue,
126 LeafRefList& leafs, LeafRefList split[2])
128 while (!leafs.empty()) {
129 if (leafs.front()._center[splitAxis] < splitValue) {
130 split[0].splice(split[0].begin(), leafs, leafs.begin());
132 split[1].splice(split[1].begin(), leafs, leafs.begin());
138 equalSplitLeafs(unsigned splitAxis, LeafRefList& leafs,
139 LeafRefList split[2])
141 leafs.sort(LeafRefLess(splitAxis));
145 split[0].splice(split[0].begin(), leafs, leafs.begin());
149 split[1].splice(split[1].begin(), leafs, --leafs.end());
153 static const BVHStaticNode* buildTreeRecursive(LeafRefList& leafs)
155 // recursion termination
158 // FIXME size is O(n)!!!
159 // if (leafs.size() == 1)
160 if (++leafs.begin() == leafs.end())
161 return leafs.front()._leaf;
164 for (LeafRefList::const_iterator i = leafs.begin();
165 i != leafs.end(); ++i)
166 box.expandBy(i->_box);
169 // if (length(box.getSize()) < 1)
170 // return new BVHBox(box);
175 unsigned splitAxis = box.getBroadestAxis();
176 LeafRefList splitLeafs[2];
177 double splitValue = box.getCenter()[splitAxis];
178 centerSplitLeafs(splitAxis, splitValue, leafs, splitLeafs);
180 if (splitLeafs[0].empty() || splitLeafs[1].empty()) {
181 for (unsigned i = 0; i < 3 ; ++i) {
185 leafs.swap(splitLeafs[0]);
186 leafs.splice(leafs.begin(), splitLeafs[1]);
187 splitValue = box.getCenter()[i];
188 centerSplitLeafs(i, splitValue, leafs, splitLeafs);
190 if (!splitLeafs[0].empty() && !splitLeafs[1].empty()) {
196 if (splitLeafs[0].empty() || splitLeafs[1].empty()) {
197 leafs.swap(splitLeafs[0]);
198 leafs.splice(leafs.begin(), splitLeafs[1]);
199 equalSplitLeafs(splitAxis, leafs, splitLeafs);
202 const BVHStaticNode* child0 = buildTreeRecursive(splitLeafs[0]);
203 const BVHStaticNode* child1 = buildTreeRecursive(splitLeafs[1]);
209 return new BVHStaticBinary(splitAxis, child0, child1, box);