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>
20 #include "QuadTreeBuilder.hxx"
27 QuadTreeBuilder::QuadTreeBuilder(const Vec2& min, const Vec2& max) :
28 _root(new osg::Group), _min(min), _max(max)
30 for (int i = 0; i < 4; ++i) {
31 Group* interior = new osg::Group;
32 _root->addChild(interior);
33 for (int j = 0; j < 4; ++j) {
34 Group* leaf = new osg::Group;
35 interior->addChild(leaf);
41 void QuadTreeBuilder::addNode(Node* node, const Matrix& transform)
43 Vec3 center = node->getBound().center() * transform;
45 int x = (int)(4.0 * (center.x() - _min.x()) / (_max.x() - _min.x()));
47 int y = (int)(4.0 * (center.y() - _min.y()) / (_max.y() - _min.y()));
49 _leaves[y][x]->addChild(node);
52 osg::Group* QuadTreeBuilder::makeQuadTree(vector<ref_ptr<Node> >& nodes,
53 const Matrix& transform)
55 typedef vector<ref_ptr<Node> > NodeList;
57 for (NodeList::iterator iter = nodes.begin(); iter != nodes.end(); ++iter) {
58 const Vec3 center = (*iter)->getBound().center() * transform;
59 extents.expandBy(center);
61 const Vec2 quadMin(extents.xMin(), extents.yMin());
62 const Vec2 quadMax(extents.xMax(), extents.yMax());
63 ref_ptr<Group> result;
65 QuadTreeBuilder quadTree(quadMin, quadMax);
66 for (NodeList::iterator iter = nodes.begin();
69 quadTree.addNode(iter->get(), transform);
71 result = quadTree.getRoot();
73 return result.release();