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 
00054     void clear()
00055     {
00056         rootNode->clear();
00057     }
00058 
00059 private:
00060 
00062     struct NodeElem
00063     {
00064         NodeElem() {;}
00065         NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00066         StelRegionObjectP obj;
00067         SphericalCap cap;
00068     };
00069 
00073     struct Node
00074     {
00075         virtual ~Node() {;}
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 
00110         void clear()
00111         {
00112             elements.clear();
00113             children.clear();
00114         }
00115     };
00116 
00119     class RootNode : public Node
00120     {
00121         public:
00122             RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
00123             {
00124             }
00125 
00127             virtual void split()
00128             {
00129                 static const Vec3d vertice[6] =
00130                 {
00131                     Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00132                 };
00133 
00134                 static const int verticeIndice[8][3] =
00135                 {
00136                     {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00137                 };
00138 
00139                 // Create the 8 base triangles
00140                 Node node;
00141                 for (int i=0;i<8;++i)
00142                 {
00143                     node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00144                     Q_ASSERT(node.triangle.checkValid());
00145                     children.append(node);
00146                 }
00147             }
00148 
00150             void insert(const NodeElem& el, int level)
00151             {
00152                 insert(*this, el, level);
00153             }
00154 
00156             template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00157             {
00158                 processIntersectingRegions(*this, region, func);
00159             }
00160 
00162             template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00163             {
00164                 processContainedRegions(*this, region, func);
00165             }
00166 
00168             template<class FuncObject> void processAll(FuncObject& func) const
00169             {
00170                 processAll(*this, func);
00171             }
00172 
00173         private:
00175             void insert(Node& node, const NodeElem& el, int level)
00176             {
00177                 if (node.children.isEmpty())
00178                 {
00179                     node.elements.append(el);
00180                     // If we have too many objects in the node, we split it.
00181                     if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
00182                     {
00183                         node.split();
00184                         const QVector<NodeElem> nodeElems = node.elements;
00185                         node.elements.clear();
00186                         // Re-insert the elements
00187                         for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
00188                         {
00189                             insert(node, *iter, level);
00190                         }
00191                     }
00192                     return;
00193                 }
00194 
00195                 // If we have children and one of them contains the element, store it in a sub-level
00196                 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00197                 {
00198                     if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
00199                     {
00200                         insert(*iter, el, level+1);
00201                         return;
00202                     }
00203                 }
00204                 // Else store it here
00205                 node.elements.append(el);
00206             }
00207 
00209             template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00210             {
00211                 foreach (const NodeElem& el, node.elements)
00212                 {
00213                     if (region->intersects(el.obj->getRegion().data()))
00214                         func(el.obj);
00215                 }
00216                 foreach (const Node& child, node.children)
00217                 {
00218                     if (region->contains(child.triangle))
00219                         processAll(child, func);
00220                     else if (region->intersects(child.triangle))
00221                         processIntersectingRegions(child, region, func);
00222                 }
00223             }
00224 
00226             template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00227             {
00228                 foreach (const NodeElem& el, node.elements)
00229                 {
00230                     if (region->contains(el.obj->getRegion().data()))
00231                         func(el.obj);
00232                 }
00233                 foreach (const Node& child, node.children)
00234                 {
00235                     if (region->contains(child.triangle))
00236                         processAll(child, func);
00237                     else if (region->intersects(child.triangle))
00238                         processContainedRegions(child, region, func);
00239                 }
00240             }
00241 
00243             template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00244             {
00245                 foreach (const NodeElem& el, node.elements)
00246                     func(el.obj);
00247                 foreach (const Node& child, node.children)
00248                     processAll(child, func);
00249             }
00250 
00252             int maxObjectsPerNode;
00254             int maxLevel;
00255     };
00256 
00258     int maxObjectsPerNode;
00259 
00260     RootNode* rootNode;
00261 };
00262 
00263 #endif // _STELSPHERICALINDEX_HPP_
00264 
00265 

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