source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.h @ 3318

#ifndef _AxisAlignedBox3_H__
#define _AxisAlignedBox3_H__


#include "Matrix4x4.h"
#include "Vector3.h"
#include "common.h"


namespace CHCDemoEngine
{

struct Triangle3;
class Plane3;
class Polygon3;
class Polyhedron;


/** A very simple ray structure.
*/
struct SimpleRay
{
        SimpleRay() {}

        SimpleRay(const Vector3 &o, const Vector3 &d): mOrigin(o), mDirection(d) {}

        Vector3 Extrap(float t) const 
        {
                return mOrigin + mDirection * t;
        }


        //////////////7
        
        Vector3 mOrigin;
        Vector3 mDirection;

};


/** Axis alignedd box class.
    This is a box in 3-space, defined by min and max
        corner vectors. Many useful operations are defined.
*/
class AxisAlignedBox3
{

public:

        ///////////
        //-- Constructors.

        /** Default constructor creating an existing box.
                The user has to call Initialize once in order
                to be able to use the box.
        */
        AxisAlignedBox3();
        /** Constructor taking the minimum and maximum as parameters.
        */
        AxisAlignedBox3(const Vector3 &nMin, const Vector3 &nMax);
        /** initialization to the non existing bounding box
        */
        void Initialize();
        /** The center of the box
        */
        Vector3 Center() const;
        /** The diagonal of the box
        */
        Vector3 Diagonal() const;
        /** Computes the mid point in the given axis.
        */
        float Center(int axis) const;
        /** The vertex of the box with the smallest values in all dimensions.
        */
        float Min(int axis) const;
        /** The vertex of the box with the largest values in all dimensions.
        */
        float Max(int axis) const;
        /** The extent of the box in the given axis.
        */
        float Size(int axis) const;
        /** Returns axis where box has largest extent.
        */
        int MajorAxis() const;
        /** Read-only const access tomMin and max vectors using references
        */
        const Vector3& Min() const;
        /** See Min
        */
        const Vector3& Max() const;
        /** Enlarges box in all dimensions by adding with the given value.
        */
        void Enlarge(const Vector3 &v);
        /** If the box is degenerate, this function enlarges the box
                to the minimum valid size.
        */
        void EnlargeToMinSize();
        /** Sets a new minimum of the box.
        */
        void SetMin(const Vector3 &v);
        /** Sets a new maximum of the box.
        */
        void SetMax(const Vector3 &v);
        /** Sets the minimum for one dimension.
        */
        void SetMin(int axis, float value);
        /** Sets the maximum for one dimension.
        */
        void SetMax(int axis, float value);
        /** Decrease box by given splitting plane
        */
        void Reduce(int axis, int right, float value); 
        /** Returns true if the box intersects the line given by the end
                vertices.
        */
        bool Intersects(const Vector3 &lStart, const Vector3 &lEnd) const;
        /** The size of the box along all the axes
        */
        Vector3 Size() const;
        /** The diagonal radius of the box.
        */
        float Radius() const;
        /** The square radius.
        */
        float SqrRadius() const;
        /** Return whether the box is unbounded.  Unbounded boxes appear
                when unbounded objects such as quadric surfaces are included.
        */
        bool Unbounded() const;

        /** Expand the axis-aligned box to include the given object.
        */
        void Include(const Vector3 &newpt);
        void Include(const AxisAlignedBox3 &bbox);
        void Include(const Polygon3 &newpoly);
        void Include(const PolygonContainer &polys);
        
        /** Expand the axis-aligned box to include given values in particular axis.
        */
        void Include(int axis, float newBound);
        /** Includes returns true if a includes b (completely)
        */
        bool Includes(const AxisAlignedBox3 &b) const;
        /** Returns true if this point is inside box.
        */
        virtual int IsInside(const Vector3 &v) const;
        /** Test if the box makes sense.
        */
        virtual bool IsCorrect();
        /** To answer true requires the box of real volume of non-zero value.
        */
        bool IsSingularOrIncorrect() const;
        /** When the box is not of non-zero or negative surface area.
        */
        bool IsCorrectAndNotPoint() const;
        /** Returns true when the box degenerates to a point.
        */
        bool IsPoint() const;
        /** Scales the box with the factor.
        */
        void Scale(float scale);
        /** Scale box non-uniformally
        */
        void Scale(const Vector3 &scale);
        /** Translates the box with the factor.
        */
        void Translate(const Vector3 &shift);
        /** Returns the square of the minimal and maximal distance to 
            a point on the box.
        */
        void GetSqrDistances(const Vector3 &point, 
                                 float &minDistance,
                                                 float &maxDistance) const;
        /** return random point in box.
        */
        Vector3 GetRandomPoint() const;
        /** Returns surface area of the box.
        */
        float SurfaceArea() const;
        /** Returns volume of the box.
        */
        float GetVolume() const;

        // Six faces are distuinguished by their name.
        enum EFaces {ID_Back = 0,
                                 ID_Left = 1, 
                                 ID_Bottom = 2, 
                                 ID_Front = 3,
                                 ID_Right = 4, 
                                 ID_Top = 5};

        /** Writes a brief description of the object, indenting by the given
            number of spaces first.
        */
        virtual void Describe(std::ostream& app, int ind) const;

        /** For edge .. number <0..11> returns two incident vertices
        */
        void GetEdge(int edge, Vector3 *a, Vector3 *b) const;
        /** Compute the coordinates of one vertex of the box for 0/1 in each axis
            0 .. smaller coordinates, 1 .. large coordinates
        */
        Vector3 GetVertex(int xAxis, int yAxis, int zAxis) const;
        /** Compute the vertex for number N=<0..7>, N = 4*x + 2*y + z, where
            x,y,z are either 0 or 1; (0 .. lower coordinate, 1 .. large coordinate)
           (xmin,ymin, zmin) .. N = 0, (xmax, ymax, zmax) .. N= 7
    */
        void GetVertex(int N, Vector3 &vertex) const;
        /** Convencience method that returns a vertex internally using the 
                above routine.
        */
        Vector3 GetVertex(int N) const;
        /** Uses different vertex order: vertices are chosen so that they
                only differ by one value (min or max) in the x, y, z triple
        */
        void GetVertex2(int N, Vector3 &vertex) const;
        /** get the extent of face.
        */
        float GetExtent(int face) const; 
        /** Returns 1, if the box includes on arbitrary face a given box
        */
        int IsPiercedByBox(const AxisAlignedBox3 &box, int &axis) const;

        int GetFaceVisibilityMask(const Vector3 &position) const;
        /** Returns vertex indices of edge.
        */
        void GetEdge(int edge, int  &aIdx, int &bIdx) const;
        /** Get distance of plane to vertex with specified index.
        */
        float GetDistance(int index, const Plane3 &plane) const;
        /** Returns the distance between the plane given by 'vecNearplaneNormal' and the vertex that
            is closest to it (this vertex is unequivocally identified by the direction of the vector)
        */
        float GetMinDistance(const Plane3 &near) const;
        /** Returns the distance between the plane given by 'vecNearplaneNormal' and the vertex that
            is farthest to it (this vertex is unequivocally identified by the direction of the vector)
        */
        float GetMaxDistance(const Plane3 &near) const;
        
        /** Returns cross section of the plane as a polygon.
        */
        Polygon3 *CrossSection(const Plane3 &plane) const;
        /** Returns the supporting plane of this face.
        */
        Plane3 GetPlane(int face) const;
        /** Returns 
                0 if box intersects plane
                1 if box in front of plane
                -1 if box behind plane
        */
        int Side(const Plane3 &plane) const;
        /**  Calculates the intersection of the polyhedron with the box.
        */
        Polyhedron *CalcIntersection(const Polyhedron &polyhedron) const;
        /** Tests for intersection of the ray with the box.
        */
        bool Intersects(const SimpleRay &ray, float &tnear, float &tfar) const;
        /** Extracts the box sides as polygons.
        */
        void ExtractPolygons(PolygonContainer &polys) const;
        /** Returns triangle representation of this box.
        */
        void Triangulate(std::vector<Triangle3> &triangles) const;



        ////////////
        //-- friend functions

        /// Overlap returns 1 if the two axis-aligned boxes overlap .. even weakly
        friend inline bool Overlap(const AxisAlignedBox3 &, const AxisAlignedBox3 &);

        /// Overlap returns 1 if the two axis-aligned boxes overlap .. only strongly
        friend inline bool OverlapS(const AxisAlignedBox3 &,const AxisAlignedBox3 &);

        /** Overlap returns 1 if the two axis-aligned boxes overlap for a given epsilon. 
        If eps > 0.0, then the boxes has to have the real intersection
        box, if eps < 0.0, then the boxes need not intersect really, they
        can be at eps distance in the projection.
        */
        friend inline bool Overlap(const AxisAlignedBox3 &,     const AxisAlignedBox3 &, float eps);


        // Returns the smallest axis-aligned box that includes all points
        // inside the two given boxes.
        friend inline AxisAlignedBox3 Union(const AxisAlignedBox3 &x,
                                                const AxisAlignedBox3 &y);

        // Returns the intersection of two axis-aligned boxes.
        friend inline AxisAlignedBox3 Intersect(const AxisAlignedBox3 &x,
                                                    const AxisAlignedBox3 &y);

        // Given 4x4 matrix, transform the current box to new one.
        friend inline AxisAlignedBox3 Transform(const AxisAlignedBox3 &box,
                                                    const Matrix4x4 &tform);


        // returns true when two boxes are completely equal
        friend inline int operator== (const AxisAlignedBox3 &A, 
                                          const AxisAlignedBox3 &B);

        // input and output operator with stream
        friend std::ostream& operator<<(std::ostream &s, const AxisAlignedBox3 &A);
        friend std::istream& operator>>(std::istream &s, AxisAlignedBox3 &A);



        // The vertices that form boundaries of the projected bounding box
        // for all the regions possible, number of regions is 3^3 = 27,
        // since two parallel sides of bbox forms three disjoint spaces
        // the vertices are given in anti-clockwise order .. stopped by -1 elem.
        static const int bvertices[27][9];

        // The list of all faces visible from a given region (except region 13)
        // the faces are identified by triple: (axis, min-vertex, max-vertex),
        // that is maximaly three triples are defined. axis = 0 (x-axis),
        // axis = 1 (y-axis), axis = 2 (z-axis), -1 .. terminator. Is is always
        // true that: min-vertex < max-vertex for all coordinates excluding axis
        static const int bfaces[27][10];

        // The correct corners indexed starting from entry face to exit face
        // first index determines entry face, second index exit face, and
        // the two numbers (indx, inc) determines: ind = the index on the exit
        // face, when starting from the vertex 0 on entry face, 'inc' is
        // the increment when we go on entry face in order 0,1,2,3 to create
        // convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
        static const int pairFaceRects[6][6][2];

        // The vertices that form CLOSEST points with respect to the region
        // for all the regions possible, number of regions is 3^3 = 27,
        // since two parallel sides of bbox forms three disjoint spaces.
        // The vertices are given in anti-clockwise order, stopped by -1 elem,
        // at most 8 points, at least 1 point.
        static const int cvertices[27][9];
        static const int csvertices[27][6];

        // The vertices that form FARTHEST points with respect to the region
        // for all the regions possible, number of regions is 3^3 = 27,
        // since two parallel sides of bbox forms three disjoint spaces.
        // The vertices are given in anti-clockwise order, stopped by -1 elem,
        // at most 8 points, at least 1 point.
        static const int fvertices[27][9];  
        static const int fsvertices[27][9];

        /** Returns the vertex index nearest from the plane specified by the normal.
        */
        static int GetIndexNearestVertex(const Vector3 &vecPlaneNormal);
        /** Returns the vertwx index farthest from the plane specified by the normal.
        */
        static int GetIndexFarthestVertex(const Vector3 &vecPlaneNormal);



protected:

        Vector3 mMin, mMax;
};



/////////////////////////////////////////////////////////
//-- Implementation of inline (member) functions


inline float AxisAlignedBox3::Radius() const 
{ 
        return 0.5f * Magnitude(Size()); 
}


inline float AxisAlignedBox3::SqrRadius() const 
{ 
        return 0.5f * SqrMagnitude(Size()); 
}


inline bool Overlap(const AxisAlignedBox3 &x,
                                        const AxisAlignedBox3 &y)
{
        if (x.mMax.x < y.mMin.x ||
                x.mMin.x > y.mMax.x ||
                x.mMax.y < y.mMin.y ||
                x.mMin.y > y.mMax.y ||
                x.mMax.z < y.mMin.z ||
                x.mMin.z > y.mMax.z)
        {
                        return false;
        }

        return true;
}


inline bool OverlapS(const AxisAlignedBox3 &x, 
                                         const AxisAlignedBox3 &y)
{
        if (x.mMax.x <= y.mMin.x ||
                x.mMin.x >= y.mMax.x ||
                x.mMax.y <= y.mMin.y ||
                x.mMin.y >= y.mMax.y ||
                x.mMax.z <= y.mMin.z ||
                x.mMin.z >= y.mMax.z) 
        {
                        return false;
        }

        return true;
}


inline bool Overlap(const AxisAlignedBox3 &x,
                                        const AxisAlignedBox3 &y,
                                        float eps)
{
        if ((x.mMax.x - eps) < y.mMin.x ||
                (x.mMin.x + eps) > y.mMax.x ||
                (x.mMax.y - eps) < y.mMin.y ||
                (x.mMin.y + eps) > y.mMax.y ||
                (x.mMax.z - eps) < y.mMin.z ||
                (x.mMin.z + eps) > y.mMax.z ) 
        {
                        return false;
        }

        return true;
}


inline AxisAlignedBox3 Intersect(const AxisAlignedBox3 &x,
                                                                 const AxisAlignedBox3 &y)
{
        if (x.Unbounded()) 
        {
                return y;
        }
        else
        {
                if (y.Unbounded()) return x;
        }

        AxisAlignedBox3 ret = x;

        if (Overlap(ret, y)) 
        {
                Maximize(ret.mMin, y.mMin);
                Minimize(ret.mMax, y.mMax);

                return ret;
        }
        else // Null intersection
        {
                return AxisAlignedBox3(Vector3(0), Vector3(0));
        }
}


inline AxisAlignedBox3 Union(const AxisAlignedBox3 &x, 
                                                         const AxisAlignedBox3 &y)
{
        Vector3 min = x.mMin;
        Vector3 max = x.mMax;

        Minimize(min, y.mMin);
        Maximize(max, y.mMax);

        return AxisAlignedBox3(min, max);
}


inline AxisAlignedBox3 Transform(const AxisAlignedBox3 &box, 
                                                                 const Matrix4x4 &tform)
{
        const Vector3 mmin(MAXFLOAT);
        const Vector3 mmax(-MAXFLOAT);
        
        AxisAlignedBox3 ret(mmin, mmax);
        
        ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMin.z));
        ret.Include(tform * Vector3(box.mMin.x, box.mMin.y, box.mMax.z));
        ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMin.z));
        ret.Include(tform * Vector3(box.mMin.x, box.mMax.y, box.mMax.z));
        ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMin.z));
        ret.Include(tform * Vector3(box.mMax.x, box.mMin.y, box.mMax.z));
        ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMin.z));
        ret.Include(tform * Vector3(box.mMax.x, box.mMax.y, box.mMax.z));
        
        return ret;
}


inline float RatioOfOverlap(const AxisAlignedBox3 &box1,
                                                        const AxisAlignedBox3 &box2)
{
        // return ratio of intersection to union
        const AxisAlignedBox3 bisect = Intersect(box1, box2);
        const AxisAlignedBox3 bunion = Union(box1, box2);

        return bisect.GetVolume() / bunion.GetVolume();
}


inline int operator==(const AxisAlignedBox3 &A, 
                                          const AxisAlignedBox3 &B)
{
        return (A.mMin == B.mMin) && (A.mMax == B.mMax);
}


}


#endif