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