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

core/StelGeodesicGrid.hpp

00001 /*
00002  
00003 StelGeodesicGrid: a library for dividing the sphere into triangle zones
00004 by subdividing the icosahedron
00005  
00006 Author and Copyright: Johannes Gajdosik, 2006
00007  
00008 This library requires a simple Vector library,
00009 which may have different copyright and license,
00010 for example Vec3f from VecMath.hpp.
00011  
00012 In the moment I choose to distribute the library under the GPL,
00013 later I may choose to additionally distribute it under a more
00014 relaxed license like the LGPL. If you want to have the library
00015 under another license, please ask me.
00016  
00017  
00018  
00019 This library is free software; you can redistribute it and/or
00020 modify it under the terms of the GNU General Public License
00021 as published by the Free Software Foundation; either version 2
00022 of the License, or (at your option) any later version.
00023  
00024 This library is distributed in the hope that it will be useful,
00025 but WITHOUT ANY WARRANTY; without even the implied warranty of
00026 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00027 GNU General Public License for more details.
00028  
00029 You should have received a copy of the GNU General Public License
00030 along with this library; if not, write to the Free Software
00031 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00032  
00033 */
00034 
00035 #ifndef _STELGEODESICGRID_HPP_
00036 #define _STELGEODESICGRID_HPP_
00037 
00038 #include "StelSphereGeometry.hpp"
00039 
00040 class GeodesicSearchResult;
00041 
00047 class StelGeodesicGrid
00048 {
00049 public:
00050     StelGeodesicGrid(int maxLevel);
00051     ~StelGeodesicGrid(void);
00052     
00053     int getMaxLevel(void) const {return maxLevel;}
00054     
00055     static int nrOfZones(int level) {return (20<<(level<<1));} // 20*4^level
00056     
00057     int getNrOfZones(void) const {return nrOfZones(maxLevel);}
00058     
00059     typedef void (VisitFunc)(int lev,int index,
00060                              const Vec3f &c0,
00061                              const Vec3f &c1,
00062                              const Vec3f &c2,
00063                              void *context);
00064     void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;
00065 
00071     int getZoneNumberForPoint(const Vec3f &v,int searchLevel) const;
00072 
00074     void getTriangleCorners(int lev, int index, Vec3f& c0, Vec3f& c1, Vec3f& c2) const;
00075     
00077     int getPartnerTriangle(int lev, int index) const;
00078     
00082     const GeodesicSearchResult* search(const QVector<SphericalCap>& convex, int maxSearchLevel) const;
00083 
00084 private:
00085     friend class GeodesicSearchResult;
00086     
00102     void searchZones(const QVector<SphericalCap>& convex,
00103                      int **inside,int **border,int maxSearchLevel) const;
00104     
00105     const Vec3f& getTriangleCorner(int lev, int index, int cornerNumber) const;
00106     void initTriangle(int lev,int index,
00107                       const Vec3f &c0,
00108                       const Vec3f &c1,
00109                       const Vec3f &c2);
00110     void visitTriangles(int lev,int index,
00111                         const Vec3f &c0,
00112                         const Vec3f &c1,
00113                         const Vec3f &c2,
00114                         int maxVisitLevel,
00115                         VisitFunc *func,
00116                         void *context) const;
00117     void searchZones(int lev,int index,
00118                      const QVector<SphericalCap>& convex,
00119                      const int *indexOfUsedSphericalCaps,
00120                      const int halfSpacesUsed,
00121                      const bool *corner0_inside,
00122                      const bool *corner1_inside,
00123                      const bool *corner2_inside,
00124                      int **inside,int **border,int maxSearchLevel) const;
00125 
00126     const int maxLevel;
00127     struct Triangle
00128     {
00129         Vec3f e0,e1,e2;   // Seitenmittelpunkte
00130     };
00131     Triangle **triangles;
00132     // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
00133     // 2+10*4^n corners
00134     
00136     mutable GeodesicSearchResult* cacheSearchResult;
00137     mutable int lastMaxSearchlevel;
00138     mutable QVector<SphericalCap> lastSearchRegion;
00139 };
00140 
00141 class GeodesicSearchResult
00142 {
00143 public:
00144     GeodesicSearchResult(const StelGeodesicGrid &grid);
00145     ~GeodesicSearchResult(void);
00146     void print(void) const;
00147 private:
00148     friend class GeodesicSearchInsideIterator;
00149     friend class GeodesicSearchBorderIterator;
00150     friend class StelGeodesicGrid;
00151     
00152     void search(const QVector<SphericalCap>& convex, int maxSearchLevel);
00153     
00154     const StelGeodesicGrid &grid;
00155     int **const zones;
00156     int **const inside;
00157     int **const border;
00158 };
00159 
00160 class GeodesicSearchBorderIterator
00161 {
00162 public:
00163     GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)
00164         : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
00165                          ?ar.grid.getMaxLevel():alevel),
00166             end(ar.zones[GeodesicSearchBorderIterator::level]+
00167                 StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
00168     {reset();}
00169     void reset(void) {index = r.border[level];}
00170     int next(void) // returns -1 when finished
00171     {if (index < end) {return *index++;} return -1;}
00172 private:
00173     const GeodesicSearchResult &r;
00174     const int level;
00175     const int *const end;
00176     const int *index;
00177 };
00178 
00179 
00180 class GeodesicSearchInsideIterator
00181 {
00182 public:
00183     GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)
00184         :   r(ar), 
00185             maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
00186     {reset();}
00187     void reset(void);
00188     int next(void); // returns -1 when finished
00189 private:
00190     const GeodesicSearchResult &r;
00191     const int maxLevel;
00192     int level;
00193     int maxCount;
00194     int *indexP;
00195     int *endP;
00196     int index;
00197     int count;
00198 };
00199 
00200 #endif // _STELGEODESICGRID_HPP_

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