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 
00029 class StelSphericalIndexMultiRes : public StelSphericalIndex
00030 {
00031 public:
00032     StelSphericalIndexMultiRes(int maxObjectsPerNode = 100);
00033     virtual ~StelSphericalIndexMultiRes();
00034 
00036     void insert(StelRegionObjectP obj);
00037 
00039     template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00040     {
00041         for (int i=1;i<MAX_INDEX_LEVEL;++i)
00042         {
00043             const RootNode* node = treeForRadius[i-1];
00044             if (node!=NULL)
00045                 node->processIntersectingRegions(region, func);
00046         }
00047     }
00048 
00050     template<class FuncObject> void processAll(FuncObject& func) const
00051     {
00052         for (int i=1;i<MAX_INDEX_LEVEL;++i)
00053         {
00054             const RootNode* node = treeForRadius[i-1];
00055             if (node!=NULL)
00056                 node->processAll(func);
00057         }
00058     }
00059 
00060 private:
00061     
00063     struct NodeElem
00064     {
00065         NodeElem() {;}
00066         NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00067         StelRegionObjectP obj;
00068         SphericalCap cap;
00069     };
00070 
00074     struct Node
00075     {
00076         QVector<NodeElem> elements;
00077         QVector<Node> children;
00078         SphericalConvexPolygon triangle;
00080         virtual void split()
00081         {
00082             // Default implementation for HTM triangle more than level 0
00083             Q_ASSERT(children.empty());
00084             Q_ASSERT(triangle.getConvexContour().size() == 3);
00085 
00086             const Vec3d& c0 = triangle.getConvexContour().at(0);
00087             const Vec3d& c1 = triangle.getConvexContour().at(1);
00088             const Vec3d& c2 = triangle.getConvexContour().at(2);
00089 
00090             Q_ASSERT((c1^c0)*c2 >= 0.0);
00091             Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00092             e0.normalize();
00093             Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00094             e1.normalize();
00095             Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00096             e2.normalize();
00097 
00098             children.resize(4);
00099             children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00100             Q_ASSERT(children[0].triangle.checkValid());
00101             children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00102             Q_ASSERT(children[1].triangle.checkValid());
00103             children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00104             Q_ASSERT(children[2].triangle.checkValid());
00105             children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00106             Q_ASSERT(children[3].triangle.checkValid());
00107         }
00108     };
00109 
00112     class RootNode : public Node
00113     {
00114         public:
00115             RootNode(double amargin, int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(), maxLevel(amaxLevel), margin(amargin)
00116             {
00117             }
00118         
00120             virtual void split()
00121             {
00122                 static const Vec3d vertice[6] =
00123                 {
00124                     Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00125                 };
00126 
00127                 static const int verticeIndice[8][3] =
00128                 {
00129                     {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00130                 };
00131             
00132                 // Create the 8 base triangles
00133                 Node node;
00134                 for (int i=0;i<8;++i)
00135                 {
00136                     node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00137                     Q_ASSERT(node.triangle.checkValid());
00138                     children.append(node);
00139                 }
00140             }
00141         
00143             void insert(const NodeElem& el, int level)
00144             {
00145                 insert(*this, el, level);
00146             }
00147         
00149             template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00150             {
00151                 processIntersectingRegions(*this, region->getEnlarged(margin), func);
00152             }
00153         
00155             template<class FuncObject> void processAll(FuncObject& func) const
00156             {
00157                 processAll(*this, func);
00158             }
00159                 
00160         private:
00162             void insert(Node& node, const NodeElem& el, int level)
00163             {
00164                 if (node.children.isEmpty())
00165                 {
00166                     node.elements.append(el);
00167                     // If we have too many objects in the node, we split it
00168                     if (level>=maxLevel && node.elements.size() >= maxObjectsPerNode)
00169                     {
00170                         node.split();
00171                         const QVector<NodeElem> nodeElems = node.elements;
00172                         for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
00173                         {
00174                             insert(node, *iter, level+1);
00175                         }
00176                         node.elements.clear();
00177                     }
00178                 }
00179                 else
00180                 {
00181                     // If we have children, store it in a sub-level
00182                     for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00183                     {
00184                         if (iter->triangle.contains(el.cap.n))
00185                         {
00186                             insert(*iter, el, level+1);
00187                             return;
00188                         }
00189                     }
00190                 }
00191             }
00192 
00194             template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00195             {
00196                 foreach (const NodeElem& el, node.elements)
00197                 {
00198                     if (region->intersects(el.obj->getRegion()))
00199                         func(el.obj);
00200                 }
00201                 foreach (const Node& child, node.children)
00202                 {
00203                     if (region->contains(node.triangle))
00204                         processAll(child, func);
00205                     else if (region->intersects(node.triangle))
00206                         processIntersectingRegions(child, region, func);
00207                 }
00208             }
00209 
00211             template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00212             {
00213                 foreach (const NodeElem& el, node.elements)
00214                     func(el.obj);
00215                 foreach (const Node& child, node.children)
00216                     processAll(child, func);
00217             }
00218         
00220             int maxObjectsPerNode;
00222             int maxLevel;
00224             double margin;
00225     };
00226     
00228     int maxObjectsPerNode;
00229     
00231     RootNode* treeForRadius[MAX_INDEX_LEVEL];
00232     
00233     double cosRadius[MAX_INDEX_LEVEL];
00234 };
00235 
00236 #endif // _STELSPHERICALINDEXMULTIRES_HPP_
00237 
00238 

Generated on Mon Mar 22 09:55:38 2010 for Stellarium by  doxygen 1.5.5