00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
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
00045
00046
00047
00048
00049
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));}
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;
00136 };
00137 Triangle **triangles;
00138
00139
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)
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);
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_