Stellarium 0.11.2
Home · All Namespaces · All Classes · Functions · Coding Style · Scripting · Plugins · File Structure
core/StelSphericalIndexMultiRes.hpp
00001 /*
00002  * Stellarium
00003  * Copyright (C) 2009 Fabien Chereau
00004  *
00005  * This program is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU General Public License
00007  * as published by the Free Software Foundation; either version 2
00008  * of the License, or (at your option) any later version.
00009  *
00010  * This program is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  * GNU General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00018  */
00019 
00020 #ifndef _STELSPHERICALINDEXMULTIRES_HPP_
00021 #define _STELSPHERICALINDEXMULTIRES_HPP_
00022 
00023 #define MAX_INDEX_LEVEL 8
00024 
00025 #include "StelRegionObject.hpp"
00026 #include "StelSphericalIndex.hpp"
00027 
00030 class StelSphericalIndexMultiRes : public StelSphericalIndex
00031 {
00032 public:
00033     StelSphericalIndexMultiRes(int maxObjectsPerNode = 100);
00034     virtual ~StelSphericalIndexMultiRes();
00035 
00037     void insert(StelRegionObjectP obj);
00038 
00040     template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00041     {
00042         for (int i=1;i<MAX_INDEX_LEVEL;++i)
00043         {
00044             const RootNode* node = treeForRadius[i-1];
00045             if (node!=NULL)
00046                 node->processIntersectingRegions(region, func);
00047         }
00048     }
00049 
00051     template<class FuncObject> void processAll(FuncObject& func) const
00052     {
00053         for (int i=1;i<MAX_INDEX_LEVEL;++i)
00054         {
00055             const RootNode* node = treeForRadius[i-1];
00056             if (node!=NULL)
00057                 node->processAll(func);
00058         }
00059     }
00060 
00061 private:
00062     
00064     struct NodeElem
00065     {
00066         NodeElem() {;}
00067         NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00068         StelRegionObjectP obj;
00069         SphericalCap cap;
00070     };
00071 
00075     struct Node
00076     {
00077         QVector<NodeElem> elements;
00078         QVector<Node> children;
00079         SphericalConvexPolygon triangle;
00081         virtual void split()
00082         {
00083             // Default implementation for HTM triangle more than level 0
00084             Q_ASSERT(children.empty());
00085             Q_ASSERT(triangle.getConvexContour().size() == 3);
00086 
00087             const Vec3d& c0 = triangle.getConvexContour().at(0);
00088             const Vec3d& c1 = triangle.getConvexContour().at(1);
00089             const Vec3d& c2 = triangle.getConvexContour().at(2);
00090 
00091             Q_ASSERT((c1^c0)*c2 >= 0.0);
00092             Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00093             e0.normalize();
00094             Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00095             e1.normalize();
00096             Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00097             e2.normalize();
00098 
00099             children.resize(4);
00100             children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00101             Q_ASSERT(children[0].triangle.checkValid());
00102             children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00103             Q_ASSERT(children[1].triangle.checkValid());
00104             children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00105             Q_ASSERT(children[2].triangle.checkValid());
00106             children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00107             Q_ASSERT(children[3].triangle.checkValid());
00108         }
00109     };
00110 
00113     class RootNode : public Node
00114     {
00115         public:
00116             RootNode(double amargin, int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel), margin(amargin)
00117             {
00118             }
00119         
00121             virtual void split()
00122             {
00123                 static const Vec3d vertice[6] =
00124                 {
00125                     Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00126                 };
00127 
00128                 static const int verticeIndice[8][3] =
00129                 {
00130                     {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00131                 };
00132             
00133                 // Create the 8 base triangles
00134                 Node node;
00135                 for (int i=0;i<8;++i)
00136                 {
00137                     node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00138                     Q_ASSERT(node.triangle.checkValid());
00139                     children.append(node);
00140                 }
00141             }
00142         
00144             void insert(const NodeElem& el, int level)
00145             {
00146                 insert(*this, el, level);
00147             }
00148         
00150             template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00151             {
00152                 processIntersectingRegions(*this, region->getEnlarged(margin), func);
00153             }
00154         
00156             template<class FuncObject> void processAll(FuncObject& func) const
00157             {
00158                 processAll(*this, func);
00159             }
00160                 
00161         private:
00163             void insert(Node& node, const NodeElem& el, int level)
00164             {
00165                 if (node.children.isEmpty())
00166                 {
00167                     node.elements.append(el);
00168                     // If we have too many objects in the node, we split it
00169                     if (level>=maxLevel && node.elements.size() >= maxObjectsPerNode)
00170                     {
00171                         node.split();
00172                         const QVector<NodeElem> nodeElems = node.elements;
00173                         for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
00174                         {
00175                             insert(node, *iter, level+1);
00176                         }
00177                         node.elements.clear();
00178                     }
00179                 }
00180                 else
00181                 {
00182                     // If we have children, store it in a sub-level
00183                     for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00184                     {
00185                         if (iter->triangle.contains(el.cap.n))
00186                         {
00187                             insert(*iter, el, level+1);
00188                             return;
00189                         }
00190                     }
00191                 }
00192             }
00193 
00195             template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00196             {
00197                 foreach (const NodeElem& el, node.elements)
00198                 {
00199                     if (region->intersects(el.obj->getRegion()))
00200                         func(el.obj);
00201                 }
00202                 foreach (const Node& child, node.children)
00203                 {
00204                     if (region->contains(node.triangle))
00205                         processAll(child, func);
00206                     else if (region->intersects(node.triangle))
00207                         processIntersectingRegions(child, region, func);
00208                 }
00209             }
00210 
00212             template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00213             {
00214                 foreach (const NodeElem& el, node.elements)
00215                     func(el.obj);
00216                 foreach (const Node& child, node.children)
00217                     processAll(child, func);
00218             }
00219         
00221             int maxObjectsPerNode;
00223             int maxLevel;
00225             double margin;
00226     };
00227     
00229     int maxObjectsPerNode;
00230     
00232     RootNode* treeForRadius[MAX_INDEX_LEVEL];
00233     
00234     double cosRadius[MAX_INDEX_LEVEL];
00235 };
00236 
00237 #endif // _STELSPHERICALINDEXMULTIRES_HPP_
00238 
00239