Home · All Namespaces · All Classes · Functions · Coding Style · 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 Vec3d 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 
00042 class StelGeodesicGrid
00043 {
00044     // Grid of triangles (zones) on the sphere with radius 1,
00045     // generated by subdividing the icosahedron.
00046     // level 0: just the icosahedron, 20 zones
00047     // level 1: 80 zones, level 2: 320 zones, ...
00048     // Each zone has a unique integer number in the range
00049     // [0,getNrOfZones()-1].
00050 public:
00051     StelGeodesicGrid(int maxLevel);
00052     ~StelGeodesicGrid(void);
00053     
00054     
00055     int getMaxLevel(void) const {return maxLevel;}
00056     
00057     static int nrOfZones(int level)
00058     {return (20<<(level<<1));} // 20*4^level
00059     
00060     int getNrOfZones(void) const {return nrOfZones(maxLevel);}
00061     
00063     void getTriangleCorners(int lev, int index, Vec3d& c0, Vec3d& c1, Vec3d& c2) const;
00065     int getPartnerTriangle(int lev, int index) const;
00066     
00067     typedef void (VisitFunc)(int lev,int index,
00068                              const Vec3d &c0,
00069                              const Vec3d &c1,
00070                              const Vec3d &c2,
00071                              void *context);
00072     
00073     void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;
00074 
00080     int searchZone(const Vec3d &v,int searchLevel) const;
00081 
00097     void searchZones(const StelGeom::ConvexS& convex,
00098                      int **inside,int **border,int maxSearchLevel) const;
00099 
00103     const GeodesicSearchResult* search(const StelGeom::ConvexS& convex, int maxSearchLevel) const;
00104     
00108     const GeodesicSearchResult* search(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2,const Vec3d &e3,int maxSearchLevel) const;
00109 
00110 private:
00111     const Vec3d& getTriangleCorner(int lev, int index, int cornerNumber) const;
00112     void initTriangle(int lev,int index,
00113                       const Vec3d &c0,
00114                       const Vec3d &c1,
00115                       const Vec3d &c2);
00116     void visitTriangles(int lev,int index,
00117                         const Vec3d &c0,
00118                         const Vec3d &c1,
00119                         const Vec3d &c2,
00120                         int maxVisitLevel,
00121                         VisitFunc *func,
00122                         void *context) const;
00123     void searchZones(int lev,int index,
00124                      const StelGeom::ConvexS& convex,
00125                      const int *indexOfUsedHalfSpaces,
00126                      const int halfSpacesUsed,
00127                      const bool *corner0_inside,
00128                      const bool *corner1_inside,
00129                      const bool *corner2_inside,
00130                      int **inside,int **border,int maxSearchLevel) const;
00131 
00132     const int maxLevel;
00133     struct Triangle
00134     {
00135         Vec3d e0,e1,e2;   // Seitenmittelpunkte
00136     };
00137     Triangle **triangles;
00138     // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
00139     // 2+10*4^n corners
00140     
00142     mutable GeodesicSearchResult* cacheSearchResult;
00143     mutable int lastMaxSearchlevel;
00144     mutable StelGeom::ConvexS lastSearchRegion;
00145 };
00146 
00147 class GeodesicSearchResult
00148 {
00149 public:
00150     GeodesicSearchResult(const StelGeodesicGrid &grid);
00151     ~GeodesicSearchResult(void);
00152     void print(void) const;
00153 private:
00154     friend class GeodesicSearchInsideIterator;
00155     friend class GeodesicSearchBorderIterator;
00156     friend class StelGeodesicGrid;
00157     
00158     void search(const StelGeom::ConvexS& convex, int maxSearchLevel);
00159     
00160     const StelGeodesicGrid &grid;
00161     int **const zones;
00162     int **const inside;
00163     int **const border;
00164 };
00165 
00166 class GeodesicSearchBorderIterator
00167 {
00168 public:
00169     GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)
00170         : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
00171                          ?ar.grid.getMaxLevel():alevel),
00172             end(ar.zones[GeodesicSearchBorderIterator::level]+
00173                 StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
00174     {reset();}
00175     void reset(void) {index = r.border[level];}
00176     int next(void) // returns -1 when finished
00177     {if (index < end) {return *index++;} return -1;}
00178 private:
00179     const GeodesicSearchResult &r;
00180     const int level;
00181     const int *const end;
00182     const int *index;
00183 };
00184 
00185 
00186 class GeodesicSearchInsideIterator
00187 {
00188 public:
00189     GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)
00190         :   r(ar), 
00191             maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
00192     {reset();}
00193     void reset(void);
00194     int next(void); // returns -1 when finished
00195 private:
00196     const GeodesicSearchResult &r;
00197     const int maxLevel;
00198     int level;
00199     int maxCount;
00200     int *indexP;
00201     int *endP;
00202     int index;
00203     int count;
00204 };
00205 
00206 #endif // _STELGEODESICGRID_HPP_

Generated on Mon Mar 9 16:16:15 2009 for Stellarium by  doxygen 1.5.5