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