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.
17 #include <osg/BoundingBox>
19 #include <simgear/scene/util/SGNodeMasks.hxx>
21 #include "QuadTreeBuilder.hxx"
29 QuadTreeBuilder::QuadTreeBuilder(const Vec2& min, const Vec2& max, int depth) :
30 _root(new osg::Group), _min(min), _max(max), _depth(depth),
31 _dimension(1 << depth), _leafStorage(_dimension * _dimension),
32 _leaves(_leafStorage, _dimension)
34 for (LeafVector::iterator iter = _leafStorage.begin();
35 iter != _leafStorage.end();
38 vector<Group*> parentNodes(1);
39 parentNodes[0] = _root.get();
41 for (int i = 0; i < depth - 1; ++i, leafDim *= 2) {
42 VectorArrayAdapter<vector<Group*> > parents(parentNodes, leafDim / 2);
43 vector<Group*> interiorNodes(leafDim * leafDim);
44 VectorArrayAdapter<vector<Group*> > interiors(interiorNodes, leafDim);
45 for (unsigned j = 0; j < leafDim; ++j) {
46 for (unsigned k = 0; k < leafDim; ++k) {
47 interiors(j, k) = new Group;
48 parents(j / 2, k / 2)->addChild(interiors(j, k));
51 parentNodes.swap(interiorNodes);
53 VectorArrayAdapter<vector<Group*> > leafParents(parentNodes,
55 for (int j = 0; j < _dimension; ++j)
56 for (int k =0; k < _dimension; ++k)
57 leafParents(j / 2, k / 2)->addChild(_leaves(j, k));
60 void QuadTreeBuilder::addNode(Node* node, int lod, const Matrix& transform)
62 Vec3 center = node->getBound().center() * transform;
64 int x = (int)(_dimension * (center.x() - _min.x()) / (_max.x() - _min.x()));
65 x = clampTo(x, 0, (_dimension - 1));
66 int y = (int)(_dimension * (center.y() - _min.y()) / (_max.y() - _min.y()));
67 y = clampTo(y, 0, (_dimension -1));
69 _leaves(y, x)->addChild(node, 0, lod);
72 osg::Group* QuadTreeBuilder::makeQuadTree(LodMap& models,
73 const Matrix& transform)
75 typedef vector<ref_ptr<Node> > NodeList;
77 for (LodMap::iterator iter = models.begin(); iter != models.end(); ++iter) {
78 const Vec3 center = (*iter).first->getBound().center() * transform;
79 extents.expandBy(center);
81 const Vec2 quadMin(extents.xMin(), extents.yMin());
82 const Vec2 quadMax(extents.xMax(), extents.yMax());
83 ref_ptr<Group> result;
85 QuadTreeBuilder quadTree(quadMin, quadMax);
86 for (LodMap::iterator iter = models.begin();
89 quadTree.addNode(iter->first.get(), iter->second, transform);
91 result = quadTree.getRoot();
93 return result.release();