← Back to branch summary

~ubuntu-branches/debian/jessie/stellarium/jessie

« back to all changes in this revision

Viewing changes to src/core/StelGeodesicGrid.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Cédric Delfosse
  • Date: 2009-03-13 20:07:22 UTC
  • mfrom: (1.1.8 upstream)
  • mto: (11.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 7.
  • Revision ID: james.westby@ubuntu.com-20090313200722-gbgujsmzsa8a02ty
Import upstream version 0.10.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/StelGeodesicGrid.hpp
 
1
/*
 
2
 
 
3
StelGeodesicGrid: a library for dividing the sphere into triangle zones
 
4
by subdividing the icosahedron
 
5
 
 
6
Author and Copyright: Johannes Gajdosik, 2006
 
7
 
 
8
This library requires a simple Vector library,
 
9
which may have different copyright and license,
 
10
for example Vec3d from VecMath.hpp.
 
11
 
 
12
In the moment I choose to distribute the library under the GPL,
 
13
later I may choose to additionally distribute it under a more
 
14
relaxed license like the LGPL. If you want to have the library
 
15
under another license, please ask me.
 
16
 
 
17
 
 
18
 
 
19
This library is free software; you can redistribute it and/or
 
20
modify it under the terms of the GNU General Public License
 
21
as published by the Free Software Foundation; either version 2
 
22
of the License, or (at your option) any later version.
 
23
 
 
24
This library is distributed in the hope that it will be useful,
 
25
but WITHOUT ANY WARRANTY; without even the implied warranty of
 
26
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
27
GNU General Public License for more details.
 
28
 
 
29
You should have received a copy of the GNU General Public License
 
30
along with this library; if not, write to the Free Software
 
31
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
32
 
 
33
*/
 
34
 
 
35
#ifndef _STELGEODESICGRID_HPP_
 
36
#define _STELGEODESICGRID_HPP_
 
37
 
 
38
#include "StelSphereGeometry.hpp"
 
39
 
 
40
class GeodesicSearchResult;
 
41
 
 
42
class StelGeodesicGrid
 
43
{
 
44
        // Grid of triangles (zones) on the sphere with radius 1,
 
45
        // generated by subdividing the icosahedron.
 
46
        // level 0: just the icosahedron, 20 zones
 
47
        // level 1: 80 zones, level 2: 320 zones, ...
 
48
        // Each zone has a unique integer number in the range
 
49
        // [0,getNrOfZones()-1].
 
50
public:
 
51
        StelGeodesicGrid(int maxLevel);
 
52
        ~StelGeodesicGrid(void);
 
53
        
 
54
        
 
55
        int getMaxLevel(void) const {return maxLevel;}
 
56
        
 
57
        static int nrOfZones(int level)
 
58
        {return (20<<(level<<1));} // 20*4^level
 
59
        
 
60
        int getNrOfZones(void) const {return nrOfZones(maxLevel);}
 
61
        
 
62
        //! Return the position of the 3 corners for the triangle at the given level and index
 
63
        void getTriangleCorners(int lev, int index, Vec3d& c0, Vec3d& c1, Vec3d& c2) const;
 
64
        //! Return the index of the partner triangle with which to form a paralelogram
 
65
        int getPartnerTriangle(int lev, int index) const;
 
66
        
 
67
        typedef void (VisitFunc)(int lev,int index,
 
68
                                 const Vec3d &c0,
 
69
                                 const Vec3d &c1,
 
70
                                 const Vec3d &c2,
 
71
                                 void *context);
 
72
        
 
73
        void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;
 
74
 
 
75
        //! Find the zone number in which a given point lies.
 
76
        //! prerequisite: v*v==1
 
77
        //! When the point lies on the border of two or more zones,
 
78
        //! one such zone is returned (always the same one,
 
79
        //! because the algorithm is deterministic).
 
80
        int searchZone(const Vec3d &v,int searchLevel) const;
 
81
 
 
82
        //! Find all zones that lie fully(inside) or partly(border)
 
83
        //! in the intersection of the given half spaces.
 
84
        //! The result is accurate when (0,0,0) lies on the border of
 
85
        //! each half space. If this is not the case,
 
86
        //! the result may be inaccurate, because it is assumed, that
 
87
        //! a zone lies in a half space when its 3 corners lie in this half space.
 
88
        //! inside[l] points to the begin of an integer array of size nrOfZones(l),
 
89
        //! border[l] points to one after the end of the same integer array.
 
90
        //! The array will be filled from the beginning with the inside zone numbers
 
91
        //! and from the end with the border zone numbers of the given level l
 
92
        //! for 0<=l<=getMaxLevel().
 
93
        //! inside[l] will not contain zones that are already contained
 
94
        //! in inside[l1] for some l1 < l.
 
95
        //! In order to restrict search depth set maxSearchLevel < maxLevel,
 
96
        //! for full search depth set maxSearchLevel = maxLevel,
 
97
        void searchZones(const StelGeom::ConvexS& convex,
 
98
                         int **inside,int **border,int maxSearchLevel) const;
 
99
 
 
100
        //! Return a search result matching the given spatial region
 
101
        //! The result is cached, meaning that it is very fast to search the same region consecutively
 
102
        //! @return a GeodesicSearchResult instance which must be used with GeodesicSearchBorderIterator and GeodesicSearchInsideIterator
 
103
        const GeodesicSearchResult* search(const StelGeom::ConvexS& convex, int maxSearchLevel) const;
 
104
        
 
105
        //! Convenience function returning a search result matching the given spatial region
 
106
        //! The result is cached, meaning that it is very fast to search the same region consecutively
 
107
        //! @return a GeodesicSearchResult instance which must be used with GeodesicSearchBorderIterator and GeodesicSearchInsideIterator
 
108
        const GeodesicSearchResult* search(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2,const Vec3d &e3,int maxSearchLevel) const;
 
109
 
 
110
private:
 
111
        const Vec3d& getTriangleCorner(int lev, int index, int cornerNumber) const;
 
112
        void initTriangle(int lev,int index,
 
113
                          const Vec3d &c0,
 
114
                          const Vec3d &c1,
 
115
                          const Vec3d &c2);
 
116
        void visitTriangles(int lev,int index,
 
117
                            const Vec3d &c0,
 
118
                            const Vec3d &c1,
 
119
                            const Vec3d &c2,
 
120
                            int maxVisitLevel,
 
121
                            VisitFunc *func,
 
122
                            void *context) const;
 
123
        void searchZones(int lev,int index,
 
124
                         const StelGeom::ConvexS& convex,
 
125
                         const int *indexOfUsedHalfSpaces,
 
126
                         const int halfSpacesUsed,
 
127
                         const bool *corner0_inside,
 
128
                         const bool *corner1_inside,
 
129
                         const bool *corner2_inside,
 
130
                         int **inside,int **border,int maxSearchLevel) const;
 
131
 
 
132
        const int maxLevel;
 
133
        struct Triangle
 
134
        {
 
135
                Vec3d e0,e1,e2;   // Seitenmittelpunkte
 
136
        };
 
137
        Triangle **triangles;
 
138
        // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
 
139
        // 2+10*4^n corners
 
140
        
 
141
        //! A cached search result used to avoid doing twice the same search
 
142
        mutable GeodesicSearchResult* cacheSearchResult;
 
143
        mutable int lastMaxSearchlevel;
 
144
        mutable StelGeom::ConvexS lastSearchRegion;
 
145
};
 
146
 
 
147
class GeodesicSearchResult
 
148
{
 
149
public:
 
150
        GeodesicSearchResult(const StelGeodesicGrid &grid);
 
151
        ~GeodesicSearchResult(void);
 
152
        void print(void) const;
 
153
private:
 
154
        friend class GeodesicSearchInsideIterator;
 
155
        friend class GeodesicSearchBorderIterator;
 
156
        friend class StelGeodesicGrid;
 
157
        
 
158
        void search(const StelGeom::ConvexS& convex, int maxSearchLevel);
 
159
        
 
160
        const StelGeodesicGrid &grid;
 
161
        int **const zones;
 
162
        int **const inside;
 
163
        int **const border;
 
164
};
 
165
 
 
166
class GeodesicSearchBorderIterator
 
167
{
 
168
public:
 
169
        GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)
 
170
                : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
 
171
                                     ?ar.grid.getMaxLevel():alevel),
 
172
                        end(ar.zones[GeodesicSearchBorderIterator::level]+
 
173
                            StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
 
174
        {reset();}
 
175
        void reset(void) {index = r.border[level];}
 
176
        int next(void) // returns -1 when finished
 
177
        {if (index < end) {return *index++;} return -1;}
 
178
private:
 
179
        const GeodesicSearchResult &r;
 
180
        const int level;
 
181
        const int *const end;
 
182
        const int *index;
 
183
};
 
184
 
 
185
 
 
186
class GeodesicSearchInsideIterator
 
187
{
 
188
public:
 
189
        GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)
 
190
                :       r(ar), 
 
191
                        maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
 
192
        {reset();}
 
193
        void reset(void);
 
194
        int next(void); // returns -1 when finished
 
195
private:
 
196
        const GeodesicSearchResult &r;
 
197
        const int maxLevel;
 
198
        int level;
 
199
        int maxCount;
 
200
        int *indexP;
 
201
        int *endP;
 
202
        int index;
 
203
        int count;
 
204
};
 
205
 
 
206
#endif // _STELGEODESICGRID_HPP_