Home · All Namespaces · All Classes · Functions · Coding Style · Scripting · Plugins · File Structure

core/StelSphericalIndex.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 _STELSPHERICALINDEX_HPP_
00021 #define _STELSPHERICALINDEX_HPP_
00022 
00023 #include "StelRegionObject.hpp"
00024 
00027 class StelSphericalIndex
00028 {
00029 public:
00030     StelSphericalIndex(int maxObjectsPerNode = 100, int maxLevel=7);
00031     virtual ~StelSphericalIndex();
00032 
00034     void insert(StelRegionObjectP obj);
00035 
00037     template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00038     {
00039         rootNode->processIntersectingRegions(region, func);
00040     }
00041 
00043     template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00044     {
00045         rootNode->processContainedRegions(region, func);
00046     }
00047 
00049     template<class FuncObject> void processAll(FuncObject& func) const
00050     {
00051         rootNode->processAll(func);
00052     }
00053 
00055     void clear()
00056     {
00057         rootNode->clear();
00058     }
00059 
00061     unsigned int count()
00062     {
00063         CountFunc func;
00064         processAll<CountFunc>(func);
00065         return func.nb;
00066     }
00067 
00068 private:
00069     struct CountFunc
00070     {
00071         CountFunc() : nb(0) {;}
00072         void operator()(const StelRegionObjectP&)
00073         {
00074             ++nb;
00075         }
00076         unsigned int nb;
00077     };
00078 
00080     struct NodeElem
00081     {
00082         NodeElem() {;}
00083         NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00084         StelRegionObjectP obj;
00085         SphericalCap cap;
00086     };
00087 
00091     struct Node
00092     {
00093         virtual ~Node() {;}
00094         QVector<NodeElem> elements;
00095         QVector<Node> children;
00096         SphericalConvexPolygon triangle;
00098         virtual void split()
00099         {
00100             // Default implementation for HTM triangle more than level 0
00101             Q_ASSERT(children.empty());
00102             Q_ASSERT(triangle.getConvexContour().size() == 3);
00103 
00104             const Vec3d& c0 = triangle.getConvexContour().at(0);
00105             const Vec3d& c1 = triangle.getConvexContour().at(1);
00106             const Vec3d& c2 = triangle.getConvexContour().at(2);
00107 
00108             Q_ASSERT((c1^c0)*c2 >= 0.0);
00109             Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00110             e0.normalize();
00111             Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00112             e1.normalize();
00113             Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00114             e2.normalize();
00115 
00116             children.resize(4);
00117             children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00118             Q_ASSERT(children[0].triangle.checkValid());
00119             children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00120             Q_ASSERT(children[1].triangle.checkValid());
00121             children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00122             Q_ASSERT(children[2].triangle.checkValid());
00123             children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00124             Q_ASSERT(children[3].triangle.checkValid());
00125         }
00126 
00128         void clear()
00129         {
00130             elements.clear();
00131             children.clear();
00132         }
00133     };
00134 
00137     class RootNode : public Node
00138     {
00139         public:
00140             RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
00141             {
00142             }
00143 
00145             virtual void split()
00146             {
00147                 static const Vec3d vertice[6] =
00148                 {
00149                     Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00150                 };
00151 
00152                 static const int verticeIndice[8][3] =
00153                 {
00154                     {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00155                 };
00156 
00157                 // Create the 8 base triangles
00158                 Node node;
00159                 for (int i=0;i<8;++i)
00160                 {
00161                     node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00162                     Q_ASSERT(node.triangle.checkValid());
00163                     children.append(node);
00164                 }
00165             }
00166 
00168             void insert(const NodeElem& el, int level)
00169             {
00170                 insert(*this, el, level);
00171             }
00172 
00174             template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00175             {
00176                 processIntersectingRegions(*this, region, func);
00177             }
00178 
00180             template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00181             {
00182                 processContainedRegions(*this, region, func);
00183             }
00184 
00186             template<class FuncObject> void processAll(FuncObject& func) const
00187             {
00188                 processAll(*this, func);
00189             }
00190 
00191         private:
00193             void insert(Node& node, const NodeElem& el, int level)
00194             {
00195                 if (node.children.isEmpty())
00196                 {
00197                     node.elements.append(el);
00198                     // If we have too many objects in the node, we split it.
00199                     if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
00200                     {
00201                         node.split();
00202                         const QVector<NodeElem> nodeElems = node.elements;
00203                         node.elements.clear();
00204                         // Re-insert the elements
00205                         for (QVector<NodeElem>::ConstIterator iter = nodeElems.constBegin();iter != nodeElems.constEnd(); ++iter)
00206                         {
00207                             insert(node, *iter, level);
00208                         }
00209                     }
00210                     return;
00211                 }
00212 
00213                 // If we have children and one of them contains the element, store it in a sub-level
00214                 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00215                 {
00216                     if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
00217                     {
00218                         insert(*iter, el, level+1);
00219                         return;
00220                     }
00221                 }
00222                 // Else store it here
00223                 node.elements.append(el);
00224             }
00225 
00227             template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00228             {
00229                 foreach (const NodeElem& el, node.elements)
00230                 {
00231                     if (region->intersects(el.obj->getRegion().data()))
00232                         func(el.obj);
00233                 }
00234                 foreach (const Node& child, node.children)
00235                 {
00236                     if (region->contains(child.triangle))
00237                         processAll(child, func);
00238                     else if (region->intersects(child.triangle))
00239                         processIntersectingRegions(child, region, func);
00240                 }
00241             }
00242 
00244             template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00245             {
00246                 foreach (const NodeElem& el, node.elements)
00247                 {
00248                     if (region->contains(el.obj->getRegion().data()))
00249                         func(el.obj);
00250                 }
00251                 foreach (const Node& child, node.children)
00252                 {
00253                     if (region->contains(child.triangle))
00254                         processAll(child, func);
00255                     else if (region->intersects(child.triangle))
00256                         processContainedRegions(child, region, func);
00257                 }
00258             }
00259 
00261             template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00262             {
00263                 foreach (const NodeElem& el, node.elements)
00264                     func(el.obj);
00265                 foreach (const Node& child, node.children)
00266                     processAll(child, func);
00267             }
00268 
00270             int maxObjectsPerNode;
00272             int maxLevel;
00273     };
00274 
00276     int maxObjectsPerNode;
00277 
00278     RootNode* rootNode;
00279 };
00280 
00281 #endif // _STELSPHERICALINDEX_HPP_
00282 
00283 

Generated on Wed Jun 2 13:11:13 2010 for Stellarium by  doxygen 1.5.5