StelGeodesicGrid.hpp

/*
 
StelGeodesicGrid: a library for dividing the sphere into triangle zones
by subdividing the icosahedron
 
Author and Copyright: Johannes Gajdosik, 2006
 
This library requires a simple Vector library,
which may have different copyright and license,
for example Vec3f from VecMath.hpp.
 
In the moment I choose to distribute the library under the GPL,
later I may choose to additionally distribute it under a more
relaxed license like the LGPL. If you want to have the library
under another license, please ask me.
 
 
 
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
 
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA  02110-1335, USA.
 
*/

#ifndef _STELGEODESICGRID_HPP_
#define _STELGEODESICGRID_HPP_

#include "StelSphereGeometry.hpp"

class GeodesicSearchResult;

class StelGeodesicGrid
{
public:
    StelGeodesicGrid(int maxLevel);
    ~StelGeodesicGrid(void);
    
    int getMaxLevel(void) const {return maxLevel;}
    
    static int nrOfZones(int level) {return (20<<(level<<1));} // 20*4^level
    
    int getNrOfZones(void) const {return nrOfZones(maxLevel);}
    
    typedef void (VisitFunc)(int lev,int index,
                             const Vec3f &c0,
                             const Vec3f &c1,
                             const Vec3f &c2,
                             void *context);
    void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;

    int getZoneNumberForPoint(const Vec3f &v,int searchLevel) const;

    void getTriangleCorners(int lev, int index, Vec3f& c0, Vec3f& c1, Vec3f& c2) const;
    
    int getPartnerTriangle(int lev, int index) const;
    
    const GeodesicSearchResult* search(const QVector<SphericalCap>& convex, int maxSearchLevel) const;

private:
    friend class GeodesicSearchResult;
    
    void searchZones(const QVector<SphericalCap>& convex,
                     int **inside,int **border,int maxSearchLevel) const;
    
    const Vec3f& getTriangleCorner(int lev, int index, int cornerNumber) const;
    void initTriangle(int lev,int index,
                      const Vec3f &c0,
                      const Vec3f &c1,
                      const Vec3f &c2);
    void visitTriangles(int lev,int index,
                        const Vec3f &c0,
                        const Vec3f &c1,
                        const Vec3f &c2,
                        int maxVisitLevel,
                        VisitFunc *func,
                        void *context) const;
    void searchZones(int lev,int index,
                     const QVector<SphericalCap>& convex,
                     const int *indexOfUsedSphericalCaps,
                     const int halfSpacesUsed,
                     const bool *corner0_inside,
                     const bool *corner1_inside,
                     const bool *corner2_inside,
                     int **inside,int **border,int maxSearchLevel) const;

    const int maxLevel;
    struct Triangle
    {
        Vec3f e0,e1,e2;   // Seitenmittelpunkte
    };
    Triangle **triangles;
    // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
    // 2+10*4^n corners
    
    mutable GeodesicSearchResult* cacheSearchResult;
    mutable int lastMaxSearchlevel;
    mutable QVector<SphericalCap> lastSearchRegion;
};

class GeodesicSearchResult
{
public:
    GeodesicSearchResult(const StelGeodesicGrid &grid);
    ~GeodesicSearchResult(void);
    void print(void) const;
private:
    friend class GeodesicSearchInsideIterator;
    friend class GeodesicSearchBorderIterator;
    friend class StelGeodesicGrid;
    
    void search(const QVector<SphericalCap>& convex, int maxSearchLevel);
    
    const StelGeodesicGrid &grid;
    int **const zones;
    int **const inside;
    int **const border;
};

class GeodesicSearchBorderIterator
{
public:
    GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)
        : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
                         ?ar.grid.getMaxLevel():alevel),
            end(ar.zones[GeodesicSearchBorderIterator::level]+
                StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
    {reset();}
    void reset(void) {index = r.border[level];}
    int next(void) // returns -1 when finished
    {if (index < end) {return *index++;} return -1;}
private:
    const GeodesicSearchResult &r;
    const int level;
    const int *const end;
    const int *index;
};


class GeodesicSearchInsideIterator
{
public:
    GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)
        :   r(ar), 
            maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
    {reset();}
    void reset(void);
    int next(void); // returns -1 when finished
private:
    const GeodesicSearchResult &r;
    const int maxLevel;
    int level;
    int maxCount;
    int *indexP;
    int *endP;
    int index;
    int count;
};

#endif // _STELGEODESICGRID_HPP_