1 // Copyright (C) 2008 Tim Moore
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.
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.
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
22 #include <osg/BoundingBox>
23 #include <osg/ref_ptr>
29 #include "VectorArrayAdapter.hxx"
33 typedef std::map<osg::ref_ptr<osg::Node>,int> LodMap;
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 {
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)
52 vector<Group*> parentNodes(1);
53 parentNodes[0] = _root.get();
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));
65 parentNodes.swap(interiorNodes);
67 // Save leaf parents for later when we add leaves
68 _leafParentStorage = parentNodes;
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; }
75 osg::Group* getRoot() { return _root.get(); }
77 void addNode(ObjectType& obj)
80 const Vec3 center(_getLocalCoords(obj));
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));
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));
92 _leaves(y, x) = _makeLeaf();
93 _leafParents(y / 2, x / 2)->addChild(_leaves(y, x));
95 _addLeafObject(_leaves(y, x), obj);
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;
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)
112 for (ForwardIterator iter = begin; iter != end; ++iter) {
113 const Vec3 center = _getLocalCoords(*iter);
114 extents.expandBy(center);
116 _min = Vec2(extents.xMin(), extents.yMin());
117 _max = Vec2(extents.xMax(), extents.yMax());
118 std::for_each(begin, end, AddNode(this));
122 typedef std::vector<LeafType> LeafVector;
123 osg::ref_ptr<osg::Group> _root;
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;