simgear/bvh/BVHStaticGeometryBuilder.hxx

   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 #ifndef BVHStaticGeometryBuilder_hxx
  19 #define BVHStaticGeometryBuilder_hxx
  20
  21 #include <algorithm>
  22 #include <map>
  23 #include <set>
  24
  25 #include <simgear/structure/SGReferenced.hxx>
  26 #include <simgear/structure/SGSharedPtr.hxx>
  27
  28 #include "BVHVisitor.hxx"
  29 #include "BVHNode.hxx"
  30 #include "BVHGroup.hxx"
  31 #include "BVHTransform.hxx"
  32
  33 #include "BVHStaticData.hxx"
  34
  35 #include "BVHStaticNode.hxx"
  36 #include "BVHStaticLeaf.hxx"
  37 #include "BVHStaticTriangle.hxx"
  38 #include "BVHStaticBinary.hxx"
  39 #include "BVHStaticGeometry.hxx"
  40
  41 namespace simgear {
  42
  43 class BVHStaticGeometryBuilder : public SGReferenced {
  44 public:
  45     BVHStaticGeometryBuilder() :
  46         _staticData(new BVHStaticData),
  47         _currentMaterial(0),
  48         _currentMaterialIndex(~0u)
  49     { }
  50     virtual ~BVHStaticGeometryBuilder()
  51     { }
  52
  53     struct LeafRef {
  54         LeafRef(const BVHStaticLeaf* leaf, const BVHStaticData& data) :
  55             _leaf(leaf),
  56             _box(_leaf->computeBoundingBox(data)),
  57             _center(_leaf->computeCenter(data))
  58         { }
  59         SGSharedPtr<const BVHStaticLeaf> _leaf;
  60         SGBoxf _box;
  61         SGVec3f _center;
  62     };
  63     typedef std::list<LeafRef> LeafRefList;
  64
  65     struct LeafRefLess : public std::binary_function<LeafRef, LeafRef, bool> {
  66         LeafRefLess(unsigned sortAxis) : _sortAxis(sortAxis) {}
  67         bool operator()(const LeafRef& x, const LeafRef& y)
  68         { return x._center[_sortAxis] < y._center[_sortAxis]; }
  69         unsigned _sortAxis;
  70     };
  71
  72     SGSharedPtr<BVHStaticData> _staticData;
  73     LeafRefList _leafRefList;
  74
  75     typedef std::map<SGVec3f, unsigned> VertexMap;
  76     VertexMap _vertexMap;
  77
  78     typedef std::set<SGVec3<unsigned> > TriangleSet;
  79     TriangleSet _triangleSet;
  80
  81     void setCurrentMaterial(const BVHMaterial* material)
  82     {
  83         _currentMaterial = material;
  84         _currentMaterialIndex = addMaterial(material);
  85     }
  86     const BVHMaterial* getCurrentMaterial() const
  87     {
  88         return _currentMaterial;
  89     }
  90     unsigned addMaterial(const BVHMaterial* material)
  91     {
  92         MaterialMap::const_iterator i = _materialMap.find(material);
  93         if (i != _materialMap.end())
  94             return i->second;
  95         unsigned index = _staticData->addMaterial(material);
  96         _materialMap[material] = index;
  97         return index;
  98     }
  99
 100     typedef std::map<const BVHMaterial*, unsigned> MaterialMap;
 101     MaterialMap _materialMap;
 102     const BVHMaterial* _currentMaterial;
 103     unsigned _currentMaterialIndex;
 104
 105     void addTriangle(const SGVec3f& v1, const SGVec3f& v2, const SGVec3f& v3)
 106     {
 107         unsigned indices[3] = { addVertex(v1), addVertex(v2), addVertex(v3) };
 108         std::sort(indices, indices + 3);
 109         SGVec3<unsigned> indexKey(indices);
 110         if (_triangleSet.find(indexKey) != _triangleSet.end())
 111             return;
 112         _triangleSet.insert(indexKey);
 113         BVHStaticTriangle* staticTriangle;
 114         staticTriangle = new BVHStaticTriangle(_currentMaterialIndex, indices);
 115         _leafRefList.push_back(LeafRef(staticTriangle, *_staticData));
 116     }
 117     unsigned addVertex(const SGVec3f& v)
 118     {
 119         VertexMap::const_iterator i = _vertexMap.find(v);
 120         if (i != _vertexMap.end())
 121             return i->second;
 122         unsigned index = _staticData->addVertex(v);
 123         _vertexMap[v] = index;
 124         return index;
 125     }
 126
 127     BVHStaticGeometry* buildTree()
 128     {
 129         const BVHStaticNode* tree = buildTreeRecursive(_leafRefList);
 130         if (!tree)
 131             return 0;
 132         _staticData->trim();
 133         return new BVHStaticGeometry(tree, _staticData);
 134     }
 135
 136 private:
 137     static void
 138     centerSplitLeafs(unsigned splitAxis, const double& splitValue,
 139                      LeafRefList& leafs, LeafRefList split[2])
 140     {
 141         while (!leafs.empty()) {
 142             if (leafs.front()._center[splitAxis] < splitValue) {
 143                 split[0].splice(split[0].begin(), leafs, leafs.begin());
 144             } else {
 145                 split[1].splice(split[1].begin(), leafs, leafs.begin());
 146             }
 147         }
 148     }
 149
 150     static void
 151     equalSplitLeafs(unsigned splitAxis, LeafRefList& leafs,
 152                     LeafRefList split[2])
 153     {
 154         leafs.sort(LeafRefLess(splitAxis));
 155         while (true) {
 156             if (leafs.empty())
 157                 break;
 158             split[0].splice(split[0].begin(), leafs, leafs.begin());
 159
 160             if (leafs.empty())
 161                 break;
 162             split[1].splice(split[1].begin(), leafs, --leafs.end());
 163         }
 164     }
 165
 166     static const BVHStaticNode* buildTreeRecursive(LeafRefList& leafs)
 167     {
 168         // recursion termination
 169         if (leafs.empty())
 170             return 0;
 171         // FIXME size is O(n)!!!
 172         //   if (leafs.size() == 1)
 173         if (++leafs.begin() == leafs.end())
 174             return leafs.front()._leaf;
 175
 176         SGBoxf box;
 177         for (LeafRefList::const_iterator i = leafs.begin();
 178              i != leafs.end(); ++i)
 179             box.expandBy(i->_box);
 180
 181         //   // FIXME ...
 182         //   if (length(box.getSize()) < 1)
 183         //     return new BVHBox(box);
 184
 185         if (box.empty())
 186             return 0;
 187
 188         unsigned splitAxis = box.getBroadestAxis();
 189         LeafRefList splitLeafs[2];
 190         double splitValue = box.getCenter()[splitAxis];
 191         centerSplitLeafs(splitAxis, splitValue, leafs, splitLeafs);
 192
 193         if (splitLeafs[0].empty() || splitLeafs[1].empty()) {
 194             for (unsigned i = 0; i < 3 ; ++i) {
 195                 if (i == splitAxis)
 196                     continue;
 197
 198                 leafs.swap(splitLeafs[0]);
 199                 leafs.splice(leafs.begin(), splitLeafs[1]);
 200                 splitValue = box.getCenter()[i];
 201                 centerSplitLeafs(i, splitValue, leafs, splitLeafs);
 202
 203                 if (!splitLeafs[0].empty() && !splitLeafs[1].empty()) {
 204                     splitAxis = i;
 205                     break;
 206                 }
 207             }
 208         }
 209         if (splitLeafs[0].empty() || splitLeafs[1].empty()) {
 210             leafs.swap(splitLeafs[0]);
 211             leafs.splice(leafs.begin(), splitLeafs[1]);
 212             equalSplitLeafs(splitAxis, leafs, splitLeafs);
 213         }
 214
 215         const BVHStaticNode* child0 = buildTreeRecursive(splitLeafs[0]);
 216         const BVHStaticNode* child1 = buildTreeRecursive(splitLeafs[1]);
 217         if (!child0)
 218             return child1;
 219         if (!child1)
 220             return child0;
 221
 222         return new BVHStaticBinary(splitAxis, child0, child1, box);
 223     }
 224 };
 225
 226 }
 227
 228 #endif