Polytope.h

Go to the documentation of this file.

/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
 *
 * This library is open source and may be redistributed and/or modified under
 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
 * (at your option) any later version.  The full license is in LICENSE file
 * included with this distribution, and on the openscenegraph.org website.
 *
 * 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
 * OpenSceneGraph Public License for more details.
*/

#ifndef OSG_POLYTOPE
#define OSG_POLYTOPE 1

#include <osg/Plane>
#include <osg/fast_back_stack>

namespace osg {


class OSG_EXPORT Polytope
{

    public:

        typedef unsigned int                    ClippingMask;
        typedef std::vector<Plane>              PlaneList;
        typedef std::vector<Vec3>               VertexList;
        typedef fast_back_stack<ClippingMask>   MaskStack;

        inline Polytope() {setupMask();}

        inline Polytope(const Polytope& cv) :
            _maskStack(cv._maskStack),
            _resultMask(cv._resultMask),
            _planeList(cv._planeList),
            _referenceVertexList(cv._referenceVertexList) {}

        inline Polytope(const PlaneList& pl) : _planeList(pl) {setupMask();}

        inline ~Polytope() {}

        inline void clear() { _planeList.clear(); setupMask(); }

        inline Polytope& operator = (const Polytope& cv)
        {
            if (&cv==this) return *this;
            _maskStack = cv._maskStack;
            _resultMask = cv._resultMask;
            _planeList = cv._planeList;
            _referenceVertexList = cv._referenceVertexList;
            return *this;
        }

        void setToUnitFrustum(bool withNear=true, bool withFar=true)
        {
            _planeList.clear();
            _planeList.push_back(Plane(1.0,0.0,0.0,1.0)); // left plane.
            _planeList.push_back(Plane(-1.0,0.0,0.0,1.0)); // right plane.
            _planeList.push_back(Plane(0.0,1.0,0.0,1.0)); // bottom plane.
            _planeList.push_back(Plane(0.0,-1.0,0.0,1.0)); // top plane.
            if (withNear) _planeList.push_back(Plane(0.0,0.0,1.0,1.0)); // near plane
            if (withFar) _planeList.push_back(Plane(0.0,0.0,-1.0,1.0)); // far plane
            setupMask();
        }

        void setToBoundingBox(const BoundingBox& bb)
        {
            _planeList.clear();
            _planeList.push_back(Plane(1.0,0.0,0.0,-bb.xMin())); // left plane.
            _planeList.push_back(Plane(-1.0,0.0,0.0,bb.xMax())); // right plane.
            _planeList.push_back(Plane(0.0,1.0,0.0,-bb.yMin())); // bottom plane.
            _planeList.push_back(Plane(0.0,-1.0,0.0,bb.yMax())); // top plane.
            _planeList.push_back(Plane(0.0,0.0,1.0,-bb.zMin())); // near plane
            _planeList.push_back(Plane(0.0,0.0,-1.0,bb.zMax())); // far plane
            setupMask();
        }

        inline void setAndTransformProvidingInverse(const Polytope& pt, const osg::Matrix& matrix)
        {
            _referenceVertexList = pt._referenceVertexList;

            unsigned int resultMask = pt._maskStack.back();
            if (resultMask==0)
            {
                _maskStack.back() = 0;
                _resultMask = 0;
                _planeList.clear();
                return;
            }

            ClippingMask selector_mask = 0x1;

            unsigned int numActivePlanes = 0;

            // count number of active planes.
            PlaneList::const_iterator itr;
            for(itr=pt._planeList.begin();
                itr!=pt._planeList.end();
                ++itr)
            {
                if (resultMask&selector_mask) ++numActivePlanes;
                selector_mask <<= 1;
            }

            _planeList.resize(numActivePlanes);
            _resultMask = 0;
            selector_mask = 0x1;
            unsigned int index = 0;
            for(itr=pt._planeList.begin();
                itr!=pt._planeList.end();
                ++itr)
            {
                if (resultMask&selector_mask)
                {
                     _planeList[index] = *itr;
                     _planeList[index++].transformProvidingInverse(matrix);
                    _resultMask = (_resultMask<<1) | 1;
                }
                selector_mask <<= 1;
            }

            _maskStack.back() = _resultMask;
        }

        inline void set(const PlaneList& pl) { _planeList = pl; setupMask(); }


        inline void add(const osg::Plane& pl) { _planeList.push_back(pl); setupMask(); }

        inline void flip()
        {
            for(PlaneList::iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                itr->flip();
            }
        }

        inline bool empty() const { return _planeList.empty(); }

        inline PlaneList& getPlaneList() { return _planeList; }

        inline const PlaneList& getPlaneList() const { return _planeList; }


        inline void setReferenceVertexList(VertexList& vertices) { _referenceVertexList=vertices; }

        inline VertexList& getReferenceVertexList() { return _referenceVertexList; }

        inline const VertexList& getReferenceVertexList() const { return _referenceVertexList; }


        inline void setupMask()
        {
            _resultMask = 0;
            for(unsigned int i=0;i<_planeList.size();++i)
            {
                _resultMask = (_resultMask<<1) | 1;
            }
            _maskStack.push_back(_resultMask);
        }

        inline ClippingMask& getCurrentMask() { return _maskStack.back(); }

        inline ClippingMask getCurrentMask() const { return _maskStack.back(); }

        inline void setResultMask(ClippingMask mask) { _resultMask=mask; }

        inline ClippingMask getResultMask() const { return _resultMask; }

        MaskStack& getMaskStack() { return _maskStack; }

        const MaskStack& getMaskStack() const { return _maskStack; }


        inline void pushCurrentMask()
        {
            _maskStack.push_back(_resultMask);
        }

        inline void popCurrentMask()
        {
            _maskStack.pop_back();
        }

        inline bool contains(const osg::Vec3& v) const
        {
            if (!_maskStack.back()) return true;

            unsigned int selector_mask = 0x1;
            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) return false;
                selector_mask <<= 1;
            }
            return true;
        }

        inline bool contains(const std::vector<Vec3>& vertices)
        {
            if (!_maskStack.back()) return true;

            _resultMask = _maskStack.back();

            for(std::vector<Vec3>::const_iterator vitr = vertices.begin();
                vitr != vertices.end();
                ++vitr)
            {
                const osg::Vec3& v = *vitr;
                bool outside = false;
                ClippingMask selector_mask = 0x1;
                for(PlaneList::const_iterator itr=_planeList.begin();
                    itr!=_planeList.end() && !outside;
                    ++itr)
                {
                    if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) outside = true;
                    selector_mask <<= 1;
                }

                if (!outside) return true;
            }
            return false;
        }

        inline bool contains(const osg::BoundingSphere& bs)
        {
            if (!_maskStack.back()) return true;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;

            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    int res=itr->intersect(bs);
                    if (res<0) return false; // outside clipping set.
                    else if (res>0) _resultMask ^= selector_mask; // subsequent checks against this plane not required.
                }
                selector_mask <<= 1;
            }
            return true;
        }

        inline bool contains(const osg::BoundingBox& bb)
        {
            if (!_maskStack.back()) return true;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;

            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    int res=itr->intersect(bb);
                    if (res<0) return false; // outside clipping set.
                    else if (res>0) _resultMask ^= selector_mask; // subsequent checks against this plane not required.
                }
                selector_mask <<= 1;
            }
            return true;
        }

        inline bool containsAllOf(const std::vector<Vec3>& vertices)
        {
            if (!_maskStack.back()) return false;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;

            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    int res=itr->intersect(vertices);
                    if (res<1) return false;  // intersects, or is below plane.
                    _resultMask ^= selector_mask; // subsequent checks against this plane not required.
                }
                selector_mask <<= 1;
            }
            return true;
        }

        inline bool containsAllOf(const osg::BoundingSphere& bs)
        {
            if (!_maskStack.back()) return false;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;

            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    int res=itr->intersect(bs);
                    if (res<1) return false;  // intersects, or is below plane.
                    _resultMask ^= selector_mask; // subsequent checks against this plane not required.
                }
                selector_mask <<= 1;
            }
            return true;
        }

        inline bool containsAllOf(const osg::BoundingBox& bb)
        {
            if (!_maskStack.back()) return false;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;

            for(PlaneList::const_iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    int res=itr->intersect(bb);
                    if (res<1) return false;  // intersects, or is below plane.
                    _resultMask ^= selector_mask; // subsequent checks against this plane not required.
                }
                selector_mask <<= 1;
            }
            return true;
        }


        inline void transform(const osg::Matrix& matrix)
        {
            osg::Matrix inverse;
            inverse.invert(matrix);
            transformProvidingInverse(inverse);
        }

        inline void transformProvidingInverse(const osg::Matrix& matrix)
        {
            if (!_maskStack.back()) return;

            _resultMask = _maskStack.back();
            ClippingMask selector_mask = 0x1;
            for(PlaneList::iterator itr=_planeList.begin();
                itr!=_planeList.end();
                ++itr)
            {
                if (_resultMask&selector_mask)
                {
                    itr->transformProvidingInverse(matrix);
                    selector_mask <<= 1;
                }
            }
        }

    protected:


        MaskStack                           _maskStack;
        ClippingMask                        _resultMask;
        PlaneList                           _planeList;
        VertexList                          _referenceVertexList;

};

}    // end of namespace

#endif