Stellarium 0.11.3
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., 51 Franklin Street, Suite 500, Boston, MA  02110-1335, 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 processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
00044     {
00045         rootNode->processBoundingCapIntersectingRegions(cap, func);
00046     }
00047     
00049     template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00050     {
00051         rootNode->processContainedRegions(region, func);
00052     }
00053 
00055     template<class FuncObject> void processAll(FuncObject& func) const
00056     {
00057         rootNode->processAll(func);
00058     }
00059 
00061     void clear()
00062     {
00063         rootNode->clear();
00064     }
00065 
00067     unsigned int count()
00068     {
00069         CountFunc func;
00070         processAll<CountFunc>(func);
00071         return func.nb;
00072     }
00073 
00074 private:
00075     struct CountFunc
00076     {
00077         CountFunc() : nb(0) {;}
00078         void operator()(const StelRegionObjectP&)
00079         {
00080             ++nb;
00081         }
00082         unsigned int nb;
00083     };
00084 
00086     struct NodeElem
00087     {
00088         NodeElem() {;}
00089         NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00090         StelRegionObjectP obj;
00091         SphericalCap cap;
00092     };
00093 
00097     struct Node
00098     {
00099         virtual ~Node() {;}
00100         QVector<NodeElem> elements;
00101         QVector<Node> children;
00102         SphericalConvexPolygon triangle;
00104         virtual void split()
00105         {
00106             // Default implementation for HTM triangle more than level 0
00107             Q_ASSERT(children.empty());
00108             Q_ASSERT(triangle.getConvexContour().size() == 3);
00109 
00110             const Vec3d& c0 = triangle.getConvexContour().at(0);
00111             const Vec3d& c1 = triangle.getConvexContour().at(1);
00112             const Vec3d& c2 = triangle.getConvexContour().at(2);
00113 
00114             Q_ASSERT((c1^c0)*c2 >= 0.0);
00115             Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00116             e0.normalize();
00117             Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00118             e1.normalize();
00119             Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00120             e2.normalize();
00121 
00122             children.resize(4);
00123             children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00124             Q_ASSERT(children[0].triangle.checkValid());
00125             children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00126             Q_ASSERT(children[1].triangle.checkValid());
00127             children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00128             Q_ASSERT(children[2].triangle.checkValid());
00129             children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00130             Q_ASSERT(children[3].triangle.checkValid());
00131         }
00132 
00134         void clear()
00135         {
00136             elements.clear();
00137             children.clear();
00138         }
00139     };
00140 
00143     class RootNode : public Node
00144     {
00145         public:
00146             RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
00147             {
00148             }
00149 
00151             virtual void split()
00152             {
00153                 static const Vec3d vertice[6] =
00154                 {
00155                     Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00156                 };
00157 
00158                 static const int verticeIndice[8][3] =
00159                 {
00160                     {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00161                 };
00162 
00163                 // Create the 8 base triangles
00164                 Node node;
00165                 for (int i=0;i<8;++i)
00166                 {
00167                     node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00168                     Q_ASSERT(node.triangle.checkValid());
00169                     children.append(node);
00170                 }
00171             }
00172 
00174             void insert(const NodeElem& el, int level)
00175             {
00176                 insert(*this, el, level);
00177             }
00178 
00180             template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00181             {
00182                 processIntersectingRegions(*this, region, func);
00183             }
00184             
00185             template<class FuncObject> void processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
00186             {
00187                 processBoundingCapIntersectingRegions(*this, cap, func);
00188             }
00189 
00191             template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00192             {
00193                 processContainedRegions(*this, region, func);
00194             }
00195 
00197             template<class FuncObject> void processAll(FuncObject& func) const
00198             {
00199                 processAll(*this, func);
00200             }
00201 
00202         private:
00204             void insert(Node& node, const NodeElem& el, int level)
00205             {
00206                 if (node.children.isEmpty())
00207                 {
00208                     node.elements.append(el);
00209                     // If we have too many objects in the node, we split it.
00210                     if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
00211                     {
00212                         node.split();
00213                         const QVector<NodeElem> nodeElems = node.elements;
00214                         node.elements.clear();
00215                         // Re-insert the elements
00216                         for (QVector<NodeElem>::ConstIterator iter = nodeElems.constBegin();iter != nodeElems.constEnd(); ++iter)
00217                         {
00218                             insert(node, *iter, level);
00219                         }
00220                     }
00221                     return;
00222                 }
00223 
00224                 // If we have children and one of them contains the element, store it in a sub-level
00225                 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00226                 {
00227                     if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
00228                     {
00229                         insert(*iter, el, level+1);
00230                         return;
00231                     }
00232                 }
00233                 // Else store it here
00234                 node.elements.append(el);
00235             }
00236 
00238             template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00239             {
00240                 foreach (const NodeElem& el, node.elements)
00241                 {
00242                     if (region->intersects(el.obj->getRegion().data()))
00243                         func(el.obj);
00244                 }
00245                 foreach (const Node& child, node.children)
00246                 {
00247                     if (region->contains(child.triangle))
00248                         processAll(child, func);
00249                     else if (region->intersects(child.triangle))
00250                         processIntersectingRegions(child, region, func);
00251                 }
00252             }
00253             
00254             template<class FuncObject> void processBoundingCapIntersectingRegions(const Node& node, const SphericalCap& cap, FuncObject& func) const
00255             {
00256                 foreach (const NodeElem& el, node.elements)
00257                 {
00258                     if (cap.intersects(el.cap))
00259                         func(el.obj);
00260                 }
00261                 foreach (const Node& child, node.children)
00262                 {
00263                     if (cap.contains(child.triangle))
00264                         processAll(child, func);
00265                     else if (cap.intersects(child.triangle))
00266                         processBoundingCapIntersectingRegions(child, cap, func);
00267                 }
00268             }
00269 
00271             template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00272             {
00273                 foreach (const NodeElem& el, node.elements)
00274                 {
00275                     if (region->contains(el.obj->getRegion().data()))
00276                         func(el.obj);
00277                 }
00278                 foreach (const Node& child, node.children)
00279                 {
00280                     if (region->contains(child.triangle))
00281                         processAll(child, func);
00282                     else if (region->intersects(child.triangle))
00283                         processContainedRegions(child, region, func);
00284                 }
00285             }
00286 
00288             template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00289             {
00290                 foreach (const NodeElem& el, node.elements)
00291                     func(el.obj);
00292                 foreach (const Node& child, node.children)
00293                     processAll(child, func);
00294             }
00295 
00297             int maxObjectsPerNode;
00299             int maxLevel;
00300     };
00301 
00303     int maxObjectsPerNode;
00304 
00305     RootNode* rootNode;
00306 };
00307 
00308 #endif // _STELSPHERICALINDEX_HPP_
00309 
00310 
Generated on Thu May 31 10:37:19 2012 for Stellarium by  doxygen 1.6.3