simgear/scene/util/QuadTreeBuilder.cxx

   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
  17 #include <osg/BoundingBox>
  18 #include <osg/Math>
  19
  20 #include "QuadTreeBuilder.hxx"
  21
  22 using namespace std;
  23 using namespace osg;
  24
  25 namespace simgear
  26 {
  27 QuadTreeBuilder::QuadTreeBuilder(const Vec2& min, const Vec2& max) :
  28     _root(new osg::Group), _min(min), _max(max)
  29 {
  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);
  36             _leaves[i][j] = leaf;
  37         }
  38     }
  39 }
  40
  41 void QuadTreeBuilder::addNode(Node* node, const Matrix& transform)
  42 {
  43     Vec3 center = node->getBound().center() * transform;
  44
  45     int x = (int)(4.0 * (center.x() - _min.x()) / (_max.x() - _min.x()));
  46     x = clampTo(x, 0, 3);
  47     int y = (int)(4.0 * (center.y() - _min.y()) / (_max.y() - _min.y()));
  48     y = clampTo(y, 0, 3);
  49     _leaves[y][x]->addChild(node);
  50 }
  51
  52 osg::Group* QuadTreeBuilder::makeQuadTree(vector<ref_ptr<Node> >& nodes,
  53                                           const Matrix& transform)
  54 {
  55     typedef vector<ref_ptr<Node> > NodeList;
  56     BoundingBox extents;
  57     for (NodeList::iterator iter = nodes.begin(); iter != nodes.end(); ++iter) {
  58         const Vec3 center = (*iter)->getBound().center() * transform;
  59         extents.expandBy(center);
  60     }
  61     const Vec2 quadMin(extents.xMin(), extents.yMin());
  62     const Vec2 quadMax(extents.xMax(), extents.yMax());
  63     ref_ptr<Group> result;
  64     {
  65         QuadTreeBuilder quadTree(quadMin, quadMax);
  66         for (NodeList::iterator iter = nodes.begin();
  67              iter != nodes.end();
  68              ++iter) {
  69             quadTree.addNode(iter->get(), transform);
  70         }
  71         result = quadTree.getRoot();
  72     }
  73     return result.release();
  74 }
  75
  76 }