simgear/scene/util/QuadTreeBuilder.hxx

   1 // Copyright (C) 2008  Tim Moore
   2 //
   3 // This program is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU General Public License as
   5 // published by the Free Software Foundation; either version 2 of the
   6 // License, or (at your option) any later version.
   7 //
   8 // This program is distributed in the hope that it will be useful, but
   9 // WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // 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 #ifndef SIMGEAR_QUADTREEBUILDER_HXX
  17 #define SIMGEAR_QUADTREEBUILDER_HXX 1
  18
  19 #include <algorithm>
  20 #include <functional>
  21 #include <vector>
  22 #include <osg/BoundingBox>
  23 #include <osg/ref_ptr>
  24 #include <osg/Node>
  25 #include <osg/Group>
  26 #include <osg/Matrix>
  27 #include <osg/Vec2>
  28 #include <osg/LOD>
  29 #include "VectorArrayAdapter.hxx"
  30
  31 namespace simgear
  32 {
  33 typedef std::map<osg::ref_ptr<osg::Node>,int> LodMap;
  34
  35 // Create a quad tree based on x, y extents
  36 template <typename LeafType, typename ObjectType, typename MakeLeaf,
  37           typename AddLeafObject, typename GetObjectLocalCoords>
  38 class QuadTreeBuilder {
  39 public:
  40     QuadTreeBuilder(const GetObjectLocalCoords& getLocalCoords,
  41                     const AddLeafObject& addLeafObject, int depth = 2,
  42                     const MakeLeaf& makeLeaf = MakeLeaf()) :
  43         _root(new osg::Group), _depth(depth),
  44         _dimension(1 << depth), _leafStorage(_dimension * _dimension),
  45         _leaves(_leafStorage, _dimension),
  46         _leafParents(_leafParentStorage, _dimension / 2),
  47         _getLocalCoords(getLocalCoords),
  48         _addLeafObject(addLeafObject), _makeLeaf(makeLeaf)
  49     {
  50         using namespace std;
  51         using namespace osg;
  52         vector<Group*> parentNodes(1);
  53         parentNodes[0] = _root.get();
  54         unsigned leafDim = 2;
  55         for (int i = 0; i < depth - 1;  ++i, leafDim *= 2) {
  56             VectorArrayAdapter<vector<Group*> > parents(parentNodes, leafDim / 2);
  57             vector<Group*> interiorNodes(leafDim * leafDim);
  58             VectorArrayAdapter<vector<Group*> > interiors(interiorNodes, leafDim);
  59             for (unsigned j = 0; j < leafDim; ++j) {
  60                 for (unsigned k = 0; k < leafDim; ++k) {
  61                     interiors(j, k) = new Group;
  62                     parents(j / 2, k / 2)->addChild(interiors(j, k));
  63                 }
  64             }
  65             parentNodes.swap(interiorNodes);
  66         }
  67         // Save leaf parents for later when we add leaves
  68         _leafParentStorage = parentNodes;
  69     }
  70     osg::Vec2 getMin() { return _min; }
  71     void setMin(const osg::Vec2& min) { _min = min; }
  72     osg::Vec2 getMax() { return _max; }
  73     void setMax(const osg::Vec2& max) { _max = max; }
  74     ~QuadTreeBuilder() {}
  75     osg::Group* getRoot() { return _root.get(); }
  76
  77     void addNode(ObjectType& obj)
  78     {
  79         using namespace osg;
  80         const Vec3 center(_getLocalCoords(obj));
  81         int x = 0;
  82         if (_max.x() != _min.x())
  83             x = (int)(_dimension * (center.x() - _min.x())
  84                       / (_max.x() - _min.x()));
  85         x = clampTo(x, 0, (_dimension - 1));
  86         int y = 0;
  87         if (_max.y() != _min.y())
  88             y = (int)(_dimension * (center.y() - _min.y())
  89                       / (_max.y() - _min.y()));
  90         y = clampTo(y, 0, (_dimension -1));
  91         if (!_leaves(y, x)) {
  92             _leaves(y, x) = _makeLeaf();
  93             _leafParents(y / 2, x / 2)->addChild(_leaves(y, x));
  94         }
  95         _addLeafObject(_leaves(y, x), obj);
  96     }
  97     // STL craziness
  98     struct AddNode
  99     {
 100         AddNode(QuadTreeBuilder* qt) : _qt(qt) {}
 101         AddNode(const AddNode& rhs) : _qt(rhs._qt) {}
 102         void operator() (ObjectType& obj) const { _qt->addNode(obj); }
 103         QuadTreeBuilder *_qt;
 104     };
 105     // Make a quadtree of nodes from a map of nodes and LOD values
 106     template <typename ForwardIterator>
 107     void buildQuadTree(const ForwardIterator& begin,
 108                        const ForwardIterator& end)
 109     {
 110         using namespace osg;
 111         BoundingBox extents;
 112         for (ForwardIterator iter = begin; iter != end; ++iter) {
 113             const Vec3 center = _getLocalCoords(*iter);
 114             extents.expandBy(center);
 115         }
 116         _min = Vec2(extents.xMin(), extents.yMin());
 117         _max = Vec2(extents.xMax(), extents.yMax());
 118         std::for_each(begin, end, AddNode(this));
 119     }
 120
 121 protected:
 122     typedef std::vector<LeafType> LeafVector;
 123     osg::ref_ptr<osg::Group> _root;
 124     osg::Vec2 _min;
 125     osg::Vec2 _max;
 126     int _depth;
 127     int _dimension;
 128     LeafVector _leafStorage;
 129     VectorArrayAdapter<LeafVector> _leaves;
 130     std::vector<osg::Group*> _leafParentStorage;
 131     VectorArrayAdapter<std::vector<osg::Group*> > _leafParents;
 132     const GetObjectLocalCoords _getLocalCoords;
 133     const AddLeafObject _addLeafObject;
 134     const MakeLeaf _makeLeaf;
 135 };
 136
 137 }
 138 #endif