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 #if 0
  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)
  33 {
  34     for (LeafVector::iterator iter = _leafStorage.begin();
  35          iter != _leafStorage.end();
  36          ++iter)
  37         *iter = new LOD;
  38     vector<Group*> parentNodes(1);
  39     parentNodes[0] = _root.get();
  40     unsigned leafDim = 2;
  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));
  49             }
  50         }
  51         parentNodes.swap(interiorNodes);
  52     }
  53     VectorArrayAdapter<vector<Group*> > leafParents(parentNodes,
  54                                                     _dimension / 2);
  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));
  58 }
  59
  60 void QuadTreeBuilder::addNode(Node* node, int lod, const Matrix& transform)
  61 {
  62     Vec3 center = node->getBound().center() * transform;
  63
  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));
  68
  69     _leaves(y, x)->addChild(node, 0, lod);
  70 }
  71
  72 osg::Group* QuadTreeBuilder::makeQuadTree(LodMap& models,
  73                                           const Matrix& transform)
  74 {
  75     typedef vector<ref_ptr<Node> > NodeList;
  76     BoundingBox extents;
  77     for (LodMap::iterator iter = models.begin(); iter != models.end(); ++iter) {
  78         const Vec3 center = (*iter).first->getBound().center() * transform;
  79         extents.expandBy(center);
  80     }
  81     const Vec2 quadMin(extents.xMin(), extents.yMin());
  82     const Vec2 quadMax(extents.xMax(), extents.yMax());
  83     ref_ptr<Group> result;
  84     {
  85         QuadTreeBuilder quadTree(quadMin, quadMax);
  86         for (LodMap::iterator iter = models.begin();
  87              iter != models.end();
  88              ++iter) {
  89             quadTree.addNode(iter->first.get(), iter->second, transform);
  90         }
  91         result = quadTree.getRoot();
  92     }
  93     return result.release();
  94 }
  95 #endif
  96 }