StelSphereGeometry.hpp

Go to the documentation of this file.

/*
 * Stellarium
 * Copyright (C) 2009 Fabien Chereau
 *
 * This program 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 program 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 program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA  02110-1335, USA.
 */

#ifndef _STELSPHEREGEOMETRY_HPP_
#define _STELSPHEREGEOMETRY_HPP_

#include <QDebug>
#include <QSharedPointer>
#include <QVariant>
#include <QVarLengthArray>
#include <QVector>

#include "OctahedronPolygon.hpp"
#include "renderer/StelVertexBuffer.hpp"
#include "Triplet.hpp"
#include "VecMath.hpp"

class SphericalRegion;
class SphericalPolygon;
class SphericalConvexPolygon;
class SphericalCap;
class SphericalPoint;
class AllSkySphericalRegion;
class EmptySphericalRegion;



class SphericalRegionP : public QSharedPointer<SphericalRegion>
{
public:
    // Override the constructors of QSharedPointer
    SphericalRegionP() {;}
    SphericalRegionP(SphericalRegion* ptr) : QSharedPointer<SphericalRegion>(ptr) {;}
    template <class Deleter> SphericalRegionP(SphericalRegion* ptr, Deleter deleter) : QSharedPointer<SphericalRegion>(ptr, deleter) {;}
    SphericalRegionP(const SphericalRegionP& other) : QSharedPointer<SphericalRegion>(other) {;}
    SphericalRegionP(const QWeakPointer<SphericalRegion>& other) : QSharedPointer<SphericalRegion>(other) {;}

    static SphericalRegionP loadFromJson(QIODevice* in);

    static SphericalRegionP loadFromJson(const QByteArray& a);

    static SphericalRegionP loadFromQVariant(const QVariantMap& map);
    // It can only be a pure shape definition, without texture coords
    static SphericalRegionP loadFromQVariant(const QVariantList& list);

    static void serializeToJson(const QVariant& jsonObject, QIODevice* output, int indentLevel=0);

    static int metaTypeId;

private:

    static int initialize();
};

// Allow to use SphericalRegionP with the Qt MetaType system.
Q_DECLARE_METATYPE(SphericalRegionP);

QDataStream& operator<<(QDataStream& out, const SphericalRegionP& region);
QDataStream& operator>>(QDataStream& in, SphericalRegionP& region);

class SphericalRegion
{
public:
    enum SphericalRegionType
    {
        Point = 0,
        Cap = 1,
        AllSky = 2,
        Polygon = 3,
        ConvexPolygon = 4,
        Empty = 5,
        Invalid = 6
    };

    struct DrawParams
    {
        DrawParams(class StelProjector* projector)
            : projector_(projector)
            , clippingCap_(NULL)
            , subdivide_(true)
            , maxSqDistortion_(5.0)
        {}

        bool operator != (const DrawParams& rhs) const 
        {
            // Projector is ignored, as even if the pointer points to the same object, 
            // the objects' state might have changed, making comparison useless. 
            // Instead, we only cache in cases when projector is not used used outside 
            // Renderer (i.e. not affecting vertex buffers that get cached) or NULL.

            // Clipping caps are only considered equal when NULL (which is the 
            // most common case, anyway). There is no opportunity for special handling
            // like projectors, since, when not NULL, clipping caps are always used 
            // in vertex buffer generation.

            return (clippingCap_ == NULL && rhs.clippingCap_ == NULL) ||
                   subdivide_ != rhs.subdivide_   ||
                   //Fuzzy compare might be better here
                   maxSqDistortion_ != rhs.maxSqDistortion_;
        }

        DrawParams& clippingCap(const SphericalCap* clippingCap)
        {
            clippingCap_ = clippingCap;
            return *this;
        }

        DrawParams& doNotSubdivide()
        {
            subdivide_ = false;
            return *this;
        }

        DrawParams& maxSqDistortion(const double maxSqDistortion)
        {
            maxSqDistortion_ = maxSqDistortion;
            return *this;
        }

        class StelProjector* projector_;

        const SphericalCap* clippingCap_;

        bool subdivide_;

        double maxSqDistortion_;
    };

    struct PlainVertex
    {
        Vec3f position;
        PlainVertex(const Vec3f& position) : position(position){}
        PlainVertex(const Vec3d& pos) : position(pos[0], pos[1], pos[2]) {}
        VERTEX_ATTRIBUTES(Vec3f Position)
    };

    struct TexturedVertex
    {
        Vec3f position;
        Vec2f texCoord;
        TexturedVertex(const Vec3f& position, const Vec2f& texCoord)
            : position(position) , texCoord(texCoord) {}
        TexturedVertex(const Vec3d& pos, const Vec2f& texCoord)
            : position(pos[0], pos[1], pos[2]) , texCoord(texCoord) {}
        VERTEX_ATTRIBUTES(Vec3f Position, Vec2f TexCoord)
    };

    SphericalRegion()
        : fillPlainVertexBuffer(NULL)
        , previousFillDrawParams(NULL)
    {
        // Make sure previousFillDrawParams is invalid at start, so it gets replaced 
        // at first drawFill() call.
        previousFillDrawParams.maxSqDistortion_ = -42.0f;
    }

    virtual ~SphericalRegion() 
    {
        if(NULL != fillPlainVertexBuffer)
        {
            delete fillPlainVertexBuffer;
        }
    }

    virtual SphericalRegionType getType() const = 0;

    virtual OctahedronPolygon getOctahedronPolygon() const =0;

    virtual double getArea() const {return getOctahedronPolygon().getArea();}

    virtual bool isEmpty() const {return getOctahedronPolygon().isEmpty();}

    virtual Vec3d getPointInside() const {return getOctahedronPolygon().getPointInside();}

    virtual QVector<SphericalCap> getBoundingSphericalCaps() const;

    virtual SphericalCap getBoundingCap() const;

    virtual SphericalRegionP getEnlarged(double margin) const;

    virtual const QVector<Vec3d>& getFillVertexPositions() const
    {
        return getOctahedronPolygon().fillVertices();
    }

    virtual PrimitiveType getFillPrimitiveType() const 
    {
        return PrimitiveType_Triangles;
    }

    virtual const QVector<Vec3d>& getOutlineVertexPositions() const 
    {
        // This is a workaround around a compiler bug with Clang (as of Clang 3.2).
        // Returning the reference directly results in an uninitialized
        // reference which breaks calling code.
        const QVector<Vec3d>& result(getOctahedronPolygon().outlineVertices());
        return result;
    }

    virtual PrimitiveType getOutlinePrimitiveType() const
    {
        return PrimitiveType_Lines;
    }

    virtual QVector<QVector<Vec3d > > getSimplifiedContours() const;
    
    virtual QVariantList toQVariant() const = 0;

    virtual void serialize(QDataStream& out) const = 0;

    QByteArray toJSON() const;

    bool contains(const SphericalRegion* r) const;
    bool contains(const SphericalRegionP r) const {return contains(r.data());}
    virtual bool contains(const Vec3d& p) const {return getOctahedronPolygon().contains(p);}
    virtual bool contains(const SphericalPolygon& r) const;
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const;
    virtual bool contains(const SphericalPoint& r) const;
    virtual bool contains(const AllSkySphericalRegion& r) const;
    bool contains(const EmptySphericalRegion&) const {return false;}

    bool intersects(const SphericalRegion* r) const;
    bool intersects(const SphericalRegionP r) const {return intersects(r.data());}
    bool intersects(const Vec3d& p) const {return contains(p);}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& r) const;
    virtual bool intersects(const SphericalPoint& r) const;
    virtual bool intersects(const AllSkySphericalRegion& r) const;
    bool intersects(const EmptySphericalRegion&) const {return false;}

    SphericalRegionP getIntersection(const SphericalRegion* r) const;
    SphericalRegionP getIntersection(const SphericalRegionP r) const {return getIntersection(r.data());}
    virtual SphericalRegionP getIntersection(const SphericalPolygon& r) const;
    virtual SphericalRegionP getIntersection(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getIntersection(const SphericalCap& r) const;
    virtual SphericalRegionP getIntersection(const SphericalPoint& r) const;
    virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& r) const;
    SphericalRegionP getIntersection(const EmptySphericalRegion& r) const;

    SphericalRegionP getUnion(const SphericalRegion* r) const;
    SphericalRegionP getUnion(const SphericalRegionP r) const {return getUnion(r.data());}
    virtual SphericalRegionP getUnion(const SphericalPolygon& r) const;
    virtual SphericalRegionP getUnion(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getUnion(const SphericalCap& r) const;
    virtual SphericalRegionP getUnion(const SphericalPoint& r) const;
    SphericalRegionP getUnion(const AllSkySphericalRegion& r) const;
    virtual SphericalRegionP getUnion(const EmptySphericalRegion& r) const;

    SphericalRegionP getSubtraction(const SphericalRegion* r) const;
    SphericalRegionP getSubtraction(const SphericalRegionP r) const {return getSubtraction(r.data());}
    virtual SphericalRegionP getSubtraction(const SphericalPolygon& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalCap& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalPoint& r) const;
    SphericalRegionP getSubtraction(const AllSkySphericalRegion& r) const;
    virtual SphericalRegionP getSubtraction(const EmptySphericalRegion& r) const;

    virtual void drawFill(class StelRenderer* renderer, const DrawParams& params);

    virtual void drawOutline(class StelRenderer* renderer, const DrawParams& params);

protected:
    StelVertexBuffer<PlainVertex>* fillPlainVertexBuffer;

    bool useProjector;

    virtual void updateFillVertexBuffer(class StelRenderer* renderer, const DrawParams& params, bool handleDiscontinuity);

    virtual void drawFillVertexBuffer(class StelRenderer* renderer, class StelProjector* projector);

    virtual bool needToUpdateFillVertexBuffers() const
    {
        // Can't determine whether we can cache anything - 
        // we'd need to know if polygon returned by getOctahedronPolygon has changed,
        // but since getOctahedronPolygon returns by value, not reference,
        // it returns a new octahedronPolygon every time.
        //
        // If it was by reference, _and_ guaranteed to always point to the same polygon,
        // we might store a flag in the polygon determining if its vertex array has 
        // changed, and use that for caching.
        return true;
    }

    virtual void fillVertexBuffersUpdated() {}

private:
    DrawParams previousFillDrawParams;

    bool containsDefault(const SphericalRegion* r) const;
    bool intersectsDefault(const SphericalRegion* r) const;
    SphericalRegionP getIntersectionDefault(const SphericalRegion* r) const;
    SphericalRegionP getUnionDefault(const SphericalRegion* r) const;
    SphericalRegionP getSubtractionDefault(const SphericalRegion* r) const;
};


class SphericalCap : public SphericalRegion
{
public:
    SphericalCap() : d(0) {;}

    SphericalCap(double x, double y, double z) : n(x,y,z), d(0) {;}

    SphericalCap(const Vec3d& an, double ar) : n(an), d(ar) {Q_ASSERT(d==0 || std::fabs(n.lengthSquared()-1.)<0.0000001);}

    SphericalCap(const SphericalCap& other) : SphericalRegion(), n(other.n), d(other.d) {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Cap;}
    virtual OctahedronPolygon getOctahedronPolygon() const;

    virtual double getArea() const {return 2.*M_PI*(1.-d);}

    virtual bool isEmpty() const {return d>=1.;}

    virtual Vec3d getPointInside() const {return n;}

    virtual SphericalCap getBoundingCap() const {return *this;}

    // Contain and intersect    
    bool contains(const Vec3d &v) const 
    {
        Q_ASSERT(d==0 || std::fabs(v.lengthSquared()-1.)<0.00000021);
        return (v*n>=d);
    }
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& h) const
    {
        const double a = n*h.n-d*h.d;
        return d<=h.d && ( a>=1. || (a>=0. && a*a >= (1.-d*d)*(1.-h.d*h.d)));
    }
    virtual bool contains(const AllSkySphericalRegion&) const {return d<=-1;}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& h) const
    {
        const double a = d*h.d - n*h.n;
        return d+h.d<=0. || a<=0. || (a<=1. && a*a <= (1.-d*d)*(1.-h.d*h.d));
    }
    virtual bool intersects(const AllSkySphericalRegion&) const {return d<=1.;}

    virtual QVariantList toQVariant() const;

    virtual void serialize(QDataStream& out) const {out << n << d;}

    // Methods specific to SphericalCap

    double getRadius() const {return std::acos(d);}

    inline bool intersectsHalfSpace(double hn0, double hn1, double hn2) const
    {
        const double a = n[0]*hn0+n[1]*hn1+n[2]*hn2;
        return d<=0. || a<=0. || (a<=1. && a*a <= (1.-d*d));
    }

    bool clipGreatCircle(Vec3d& v1, Vec3d& v2) const;

    bool operator==(const SphericalCap& other) const {return (n==other.n && d==other.d);}

    QVector<Vec3d> getClosedOutlineContour() const;

    bool intersectsConvexContour(const Vec3d* vertice, int nbVertice) const;

    bool containsTriangle(const Triplet<Vec3d> triangle) const;

    bool intersectsTriangle(const Triplet<Vec3d>& triangle) const;

    static SphericalRegionP deserialize(QDataStream& in);

    static double relativeAreaOverlap(const SphericalCap& c1, const SphericalCap& c2);

    static double relativeDiameterOverlap(const SphericalCap& c1, const SphericalCap& c2);

    static bool intersectionPoints(const SphericalCap& h1, const SphericalCap& h2, Vec3d& p1, Vec3d& p2);

    Vec3d n;
    double d;
};

inline bool sideHalfSpaceContains(const Vec3d& v1, const Vec3d& v2, const Vec3d& p)
{
    return (v1[1] * v2[2] - v1[2] * v2[1])*p[0] +
            (v1[2] * v2[0] - v1[0] * v2[2])*p[1] +
            (v1[0] * v2[1] - v1[1] * v2[0])*p[2]>=-1e-17;
}

inline bool sideHalfSpaceContains(const Vec3d& v1, const Vec3d& v2, const SphericalCap& h)
{
    Vec3d n(v1[1]*v2[2]-v1[2]*v2[1], v2[0]*v1[2]-v2[2]*v1[0], v2[1]*v1[0]-v2[0]*v1[1]);
    n.normalize();
    const double a = n*h.n;
    return 0<=h.d && ( a>=1. || (a>=0. && a*a >= 1.-h.d*h.d));
}

inline bool sideHalfSpaceIntersects(const Vec3d& v1, const Vec3d& v2, const SphericalCap& h)
{
    Vec3d n(v1[1]*v2[2]-v1[2]*v2[1], v2[0]*v1[2]-v2[2]*v1[0], v2[1]*v1[0]-v2[0]*v1[1]);
    n.normalize();
    return  h.intersectsHalfSpace(n[0], n[1], n[2]);
}

class SphericalPoint : public SphericalRegion
{
public:
    SphericalPoint(const Vec3d& an) : n(an) {Q_ASSERT(std::fabs(1.-n.length())<0.0000001);}
    virtual ~SphericalPoint() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Point;}
    virtual OctahedronPolygon getOctahedronPolygon() const;
    virtual double getArea() const {return 0.;}
    virtual bool isEmpty() const {return false;}
    virtual Vec3d getPointInside() const {return n;}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(n, 1);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const {out << n;}

    // Contain and intersect
    virtual bool contains(const Vec3d& p) const {return n==p;}
    virtual bool contains(const SphericalPolygon&) const {return false;}
    virtual bool contains(const SphericalConvexPolygon&) const {return false;}
    virtual bool contains(const SphericalCap&) const {return false;}
    virtual bool contains(const SphericalPoint& r) const {return n==r.n;}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalPolygon&) const;
    virtual bool intersects(const SphericalConvexPolygon&) const;
    virtual bool intersects(const SphericalCap& r) const {return r.contains(n);}
    virtual bool intersects(const SphericalPoint& r) const {return n==r.n;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

    static SphericalRegionP deserialize(QDataStream& in);

    Vec3d n;
};

class AllSkySphericalRegion : public SphericalRegion
{
public:
    virtual ~AllSkySphericalRegion() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::AllSky;}
    virtual OctahedronPolygon getOctahedronPolygon() const 
    {
        return OctahedronPolygon::getAllSkyOctahedronPolygon();
    }
    virtual double getArea() const {return 4.*M_PI;}
    virtual bool isEmpty() const {return false;}
    virtual Vec3d getPointInside() const {return Vec3d(1,0,0);}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(Vec3d(1,0,0), -2);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream&) const {;}

    // Contain and intersect
    virtual bool contains(const Vec3d&) const {return true;}
    virtual bool contains(const SphericalPolygon&) const {return true;}
    virtual bool contains(const SphericalConvexPolygon&) const {return true;}
    virtual bool contains(const SphericalCap&) const {return true;}
    virtual bool contains(const SphericalPoint&) const {return true;}
    virtual bool contains(const AllSkySphericalRegion&) const {return true;}
    virtual bool intersects(const SphericalPolygon&) const {return true;}
    virtual bool intersects(const SphericalConvexPolygon&) const {return true;}
    virtual bool intersects(const SphericalCap&) const {return true;}
    virtual bool intersects(const SphericalPoint&) const {return true;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

    static const SphericalRegionP staticInstance;
};

class EmptySphericalRegion : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;
    using SphericalRegion::getIntersection;
    using SphericalRegion::getUnion;
    using SphericalRegion::getSubtraction;

    EmptySphericalRegion() {;}
    virtual ~EmptySphericalRegion() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Empty;}
    virtual OctahedronPolygon getOctahedronPolygon() const 
    {
        return OctahedronPolygon::getEmptyOctahedronPolygon();
    }
    virtual double getArea() const {return 0.;}
    virtual bool isEmpty() const {return true;}
    virtual Vec3d getPointInside() const {return Vec3d(1,0,0);}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(Vec3d(1,0,0), 2);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream&) const {;}

    // Contain and intersect
    virtual bool contains(const Vec3d&) const {return false;}
    virtual bool contains(const SphericalPolygon&) const {return false;}
    virtual bool contains(const SphericalConvexPolygon&) const {return false;}
    virtual bool contains(const SphericalCap&) const {return false;}
    virtual bool contains(const SphericalPoint&) const {return false;}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalPolygon&) const {return false;}
    virtual bool intersects(const SphericalConvexPolygon&) const {return false;}
    virtual bool intersects(const SphericalCap&) const {return false;}
    virtual bool intersects(const SphericalPoint&) const {return false;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return false;}

    static const SphericalRegionP staticInstance;
};


class SphericalPolygon : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;
    using SphericalRegion::getIntersection;
    using SphericalRegion::getUnion;
    using SphericalRegion::getSubtraction;

    SphericalPolygon() {;}
    SphericalPolygon(const QVector<QVector<Vec3d> >& contours) : octahedronPolygon(contours) {;}
    SphericalPolygon(const QVector<Vec3d>& contour) : octahedronPolygon(contour) {;}
    SphericalPolygon(const OctahedronPolygon& octContour) : octahedronPolygon(octContour) {;}
    SphericalPolygon(const QList<OctahedronPolygon>& octContours) : octahedronPolygon(octContours) {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Polygon;}
    virtual OctahedronPolygon getOctahedronPolygon() const 
    {
        return octahedronPolygon;
    }

    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const;

    virtual SphericalCap getBoundingCap() const;

    virtual bool contains(const Vec3d& p) const {return octahedronPolygon.contains(p);}
    virtual bool contains(const SphericalPolygon& r) const {return octahedronPolygon.contains(r.octahedronPolygon);}
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const {return octahedronPolygon.contains(r.getOctahedronPolygon());}
    virtual bool contains(const SphericalPoint& r) const {return octahedronPolygon.contains(r.n);}
    virtual bool contains(const AllSkySphericalRegion& r) const {return octahedronPolygon.contains(r.getOctahedronPolygon());}

    virtual bool intersects(const SphericalPolygon& r) const {return octahedronPolygon.intersects(r.octahedronPolygon);}
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& r) const {return r.intersects(*this);}
    virtual bool intersects(const SphericalPoint& r) const {return octahedronPolygon.contains(r.n);}
    virtual bool intersects(const AllSkySphericalRegion&) const {return !isEmpty();}

    virtual SphericalRegionP getIntersection(const SphericalPoint& r) const {return contains(r.n) ? SphericalRegionP(new SphericalPoint(r)) : EmptySphericalRegion::staticInstance;}
    virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& ) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    virtual SphericalRegionP getUnion(const SphericalPoint&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}
    virtual SphericalRegionP getUnion(const EmptySphericalRegion&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    virtual SphericalRegionP getSubtraction(const SphericalPoint&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}
    virtual SphericalRegionP getSubtraction(const EmptySphericalRegion&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    // Methods specific to SphericalPolygon
    void setContours(const QVector<QVector<Vec3d> >& contours) 
    {
        octahedronPolygon = OctahedronPolygon(contours);
    }

    void setContour(const QVector<Vec3d>& contour) 
    {
        octahedronPolygon = OctahedronPolygon(contour);
    }

    QVector<QVector<Vec3d> > getClosedOutlineContours() const {Q_ASSERT(0); return QVector<QVector<Vec3d> >();}

    static SphericalRegionP deserialize(QDataStream& in);

    static SphericalRegionP multiUnion(const QList<SphericalRegionP>& regions, bool optimizeByPreGrouping=false);
    
    static SphericalRegionP multiIntersection(const QList<SphericalRegionP>& regions);

private:
    OctahedronPolygon octahedronPolygon;
};


class SphericalConvexPolygon : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;

    SphericalConvexPolygon() {;}

    SphericalConvexPolygon(const QVector<QVector<Vec3d> >& contours)
        : fillVertexBufferNeedsUpdate(true)
    {
        Q_ASSERT(contours.size()==1); 
        setContour(contours.at(0));
    }

    SphericalConvexPolygon(const QVector<Vec3d>& contour) 
        : fillVertexBufferNeedsUpdate(true)
    {
        setContour(contour);
    }

    SphericalConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2) 
        : fillVertexBufferNeedsUpdate(true)
    {
        contour << e0 << e1 << e2; updateBoundingCap();
    }

    SphericalConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2, const Vec3d &e3)  
        : fillVertexBufferNeedsUpdate(true)
    {
        contour << e0 << e1 << e2 << e3; updateBoundingCap();
    }

    virtual SphericalRegionType getType() const {return SphericalRegion::ConvexPolygon;}

    virtual OctahedronPolygon getOctahedronPolygon() const 
    {
        return OctahedronPolygon(contour);
    }

    virtual const QVector<Vec3d>& getFillVertexPositions() const
    {
        return contour;
    }

    virtual PrimitiveType getFillPrimitiveType() const 
    {
        return PrimitiveType_TriangleFan;
    }

    virtual const QVector<Vec3d>& getOutlineVertexPositions() const 
    {
        return contour;
    }

    virtual PrimitiveType getOutlinePrimitiveType() const
    {
        return PrimitiveType_LineLoop;
    }

    virtual double getArea() const;
    virtual bool isEmpty() const {return contour.isEmpty();}
    virtual Vec3d getPointInside() const;
    virtual SphericalCap getBoundingCap() const {return cachedBoundingCap;}
    QVector<SphericalCap> getBoundingSphericalCaps() const;
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const {out << contour;}

    // Contain and intersect
    virtual bool contains(const Vec3d& p) const;
    virtual bool contains(const SphericalPolygon& r) const;
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const;
    virtual bool contains(const SphericalPoint& r) const {return contains(r.n);}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalCap& r) const {if (!cachedBoundingCap.intersects(r)) return false; return r.intersects(*this);}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalPoint& r) const {return contains(r.n);}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

//  virtual SphericalRegionP getIntersection(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalCap& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalPoint& r) const;
//  virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& r) const;
//  virtual SphericalRegionP getUnion(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getUnion(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getUnion(const SphericalCap& r) const;
//  virtual SphericalRegionP getUnion(const SphericalPoint& r) const;
//  virtual SphericalRegionP getUnion(const EmptySphericalRegion& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalCap& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalPoint& r) const;
//  virtual SphericalRegionP getSubtraction(const EmptySphericalRegion& r) const;

    // Methods specific to SphericalConvexPolygon
    void setContour(const QVector<Vec3d>& acontour) 
    {
        contour = acontour;
        fillVertexBufferNeedsUpdate = true;
        updateBoundingCap();
    }

    const QVector<Vec3d>& getConvexContour() const {return contour;}

    bool checkValid() const;

    static bool checkValidContour(const QVector<Vec3d>& contour);

    static SphericalRegionP deserialize(QDataStream& in);

protected:
    QVector<Vec3d> contour;

    SphericalCap cachedBoundingCap;

    bool fillVertexBufferNeedsUpdate;

    void updateBoundingCap();

    virtual void updateFillVertexBuffer(class StelRenderer* renderer, const DrawParams& params, bool handleDiscontinuity);

    virtual void drawFillVertexBuffer(class StelRenderer* renderer, class StelProjector* projector);

    virtual bool needToUpdateFillVertexBuffers() const
    {
        return fillVertexBufferNeedsUpdate;
    }

    virtual void fillVertexBuffersUpdated()
    {
        fillVertexBufferNeedsUpdate = false;
    }

    static bool areAllPointsOutsideOneSide(const Vec3d* thisContour, int nbThisContour, const Vec3d* points, int nbPoints);

    bool areAllPointsOutsideOneSide(const QVector<Vec3d>& points) const
    {
        return areAllPointsOutsideOneSide(contour.constData(), contour.size(), points.constData(), points.size());
    }

    bool containsConvexContour(const Vec3d* vertice, int nbVertex) const;
};


//class SphericalConvexPolygonSet : public SphericalRegion
//{
//public:
//  // Avoid name hiding when overloading the virtual methods.
//  using SphericalRegion::intersects;
//  using SphericalRegion::contains;
//
//  //! Default constructor.
//  SphericalConvexPolygonSet() {;}
//
//  //! Constructor from a list of contours.
//  SphericalConvexPolygonSet(const QVector<QVector<Vec3d> >& contours);
//
//  virtual SphericalRegionType getType() const {return SphericalRegion::ConvexPolygonSet;}
//  virtual OctahedronPolygon getOctahedronPolygon() const;
//  virtual StelVertexArray getFillVertexArray() const;
//  virtual StelVertexArray getOutlineVertexArray() const;
//  virtual double getArea() const;
//  virtual bool isEmpty() const;
//  virtual Vec3d getPointInside() const;
//  virtual SphericalCap getBoundingCap() const {return cachedBoundingCap;}
//  QVector<SphericalCap> getBoundingSphericalCaps() const;
//  //! Serialize the region into a QVariant map matching the JSON format.
//  //! The format is
//  //! @code["CONVEX_POLYGON_SET", [[ra,dec], [ra,dec], [ra,dec], [ra,dec]], [[ra,dec], [ra,dec], [ra,dec], [ra,dec]]]@endcode
//  //! where the coords from a list of closed convex contour, with each points defined by ra dec in degree in the ICRS frame.
//  virtual QVariantList toQVariant() const;
//  virtual void serialize(QDataStream& out) const;
//
//  // Contain and intersect
//  virtual bool contains(const Vec3d& p) const;
//  virtual bool contains(const SphericalPolygon& r) const;
//  virtual bool contains(const SphericalConvexPolygon& r) const;
//  virtual bool contains(const SphericalCap& r) const;
//  virtual bool contains(const SphericalPoint& r) const {return contains(r.n);}
//  virtual bool contains(const AllSkySphericalRegion&) const {return false;}
//  virtual bool intersects(const SphericalCap& r) const {if (!cachedBoundingCap.intersects(r)) return false; return r.intersects(*this);}
//  virtual bool intersects(const SphericalPolygon& r) const;
//  virtual bool intersects(const SphericalConvexPolygon& r) const;
//  virtual bool intersects(const SphericalPoint& r) const {return contains(r.n);}
//  virtual bool intersects(const AllSkySphericalRegion&) const {return true;}
//
//  ////////////////////////////////////////////////////////////////////
//  // Methods specific to SphericalConvexPolygonSet
//  ////////////////////////////////////////////////////////////////////
//  //! Deserialize the region. This method must allow as fast as possible deserialization.
//  static SphericalRegionP deserialize(QDataStream& in);
//
//protected:
//  QVector<SphericalConvexPolygon> contours;
//
//  //! Cache the bounding cap.
//  SphericalCap cachedBoundingCap;
//
//  //! Update the bounding cap from the vertex list.
//  void updateBoundingCap();
//};


class SphericalTexturedConvexPolygon : public SphericalConvexPolygon
{
public:
    SphericalTexturedConvexPolygon() : fillTexturedVertexBuffer(NULL) 
    {
        fillVertexBufferNeedsUpdate = true;
    }

    SphericalTexturedConvexPolygon(const QVector<Vec3d>& contour, const QVector<Vec2f>& texCoord) 
        : fillTexturedVertexBuffer(NULL)
    {
        setContour(contour, texCoord);
        fillVertexBufferNeedsUpdate = true;
    }

    SphericalTexturedConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2, const Vec3d &e3) 
        : SphericalConvexPolygon(e0,e1,e2,e3)
        , fillTexturedVertexBuffer(NULL)
    {
        textureCoords << Vec2f(0.f, 0.f) << Vec2f(1.f, 0.f) << Vec2f(1.f, 1.f) << Vec2f(0.f, 1.f);
        fillVertexBufferNeedsUpdate = true;
    }

    virtual ~SphericalTexturedConvexPolygon()
    {
        if(NULL != fillTexturedVertexBuffer)
        {
            delete fillTexturedVertexBuffer;
        }
    }

    virtual void setContour(const QVector<Vec3d>& acontour, const QVector<Vec2f>& texCoord) 
    {
        SphericalConvexPolygon::setContour(acontour); 
        textureCoords=texCoord;
        fillVertexBufferNeedsUpdate = true;
    }

    virtual QVariantList toQVariant() const;

    virtual void serialize(QDataStream& out) const {out << contour << textureCoords;}

protected:
    QVector<Vec2f> textureCoords;

    StelVertexBuffer<TexturedVertex>* fillTexturedVertexBuffer;

    virtual void updateFillVertexBuffer(class StelRenderer* renderer, const DrawParams& params, bool handleDiscontinuity);

    virtual void drawFillVertexBuffer(class StelRenderer* renderer, class StelProjector* projector);
};


Vec3d greatCircleIntersection(const Vec3d& p1, const Vec3d& p2, const Vec3d& p3, const Vec3d& p4, bool& ok);

Vec3d greatCircleIntersection(const Vec3d& p1, const Vec3d& p2, const Vec3d& nHalfSpace, bool& ok);

#endif // _STELSPHEREGEOMETRY_HPP_