source: GTP/trunk/Lib/Vis/Preprocessing/src/AxisAlignedBox3.h @ 1999

#ifndef _AxisAlignedBox3_H__
#define _AxisAlignedBox3_H__

#include "Rectangle3.h"
#include "Matrix4x4.h"
#include "Vector3.h"
#include "Plane3.h"
#include "Containers.h"

namespace GtpVisibilityPreprocessor {

class Ray;
class Polygon3;
class Mesh;
struct Triangle3;

/**
        CAABox class.
        This is a box in 3-space, defined by min and max
        corner vectors.  Many useful operations are defined
        on this
*/
class AxisAlignedBox3
{
protected:
        Vector3 mMin, mMax;
public:
  // Constructors.
  AxisAlignedBox3() { }
  
  AxisAlignedBox3(const Vector3 &nMin, const Vector3 &nMax)
  {
    mMin = nMin; mMax = 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;

  float Center(const int axis) const;

  float Min(const int axis) const;

  float Max(const int axis) const;

  float Size(const int axis) const;

  // Read-only const access tomMin and max vectors using references
  const Vector3& Min() const;
  const Vector3& Max() const;

  void Enlarge (const Vector3 &v);

  void SetMin(const Vector3 &v);

  void SetMax(const Vector3 &v);

  void SetMin(int axis, const float value);

  void SetMax(int axis, const float value);

  // Decrease box by given splitting plane
  void Reduce(int axis, int right, float value); 
  

  // the size of the box along all the axes
  Vector3 Size() const;
  float Radius() const { return 0.5f*Magnitude(Size()); }
  float SqrRadius() const { return 0.5f*SqrMagnitude(Size()); }
  
  // 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 Polygon3 &newpoly);
  void Include(const AxisAlignedBox3 &bbox);
  void Include (const PolygonContainer &polys);
  void Include(Mesh *mesh);

  /** Expand the axis-aligned box to include given values in particular axis.
  */
  void Include(const int &axis, const float &newBound);


  int
  Side(const Plane3 &plane) const;

  // 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 'factor' of overlap of first box with the second box. i.e., a number
        between 0 (no overlap) and 1 (same box).
  */
  friend inline float RatioOfOverlap(const AxisAlignedBox3 &, const AxisAlignedBox3 &);

  /** Includes returns true if a includes b (completely)
  */
  bool Includes(const AxisAlignedBox3 &b) const;

  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(const float scale);

  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;

  // returns true, when the sphere specified by the origin and radius
  // fully contains the box
  bool IsFullyContainedInSphere(const Vector3 &center, float radius) const;

  // returns true, when the volume of the sphere and volume of the
  // axis aligned box has no intersection
  bool HasNoIntersectionWithSphere(const Vector3 &center,
                                   float radius) const;


  // Given a sphere described by the center and radius,
  // the fullowing function returns:
  //   -1 ... the sphere and the box are completely separate
  //    0 ... the sphere and the box only partially overlap
  //    1 ... the sphere contains fully the box
  //  Note: the case when box fully contains the sphere is not reported
  //        since it was not required.
  int MutualPositionWithSphere(const Vector3 &center, float radius) const;

  // Given a cube described by the center and half-size (radius),
  // the following function returns:
  //   -1 ... the cube and the box are completely separate
  //    0 ... the cube and the box only partially overlap
  //    1 ... the cube contains fully the box
  int MutualPositionWithCube(const Vector3 &center, float halfSize) const;


  Vector3 GetRandomPoint(const Vector3 &r) const;
  Vector3 GetRandomPoint() const;
  Vector3 GetRandomSurfacePoint() const;
  Vector3 GetUniformRandomSurfacePoint() const;

  Vector3 GetPoint(const Vector3 &p) const {
    return mMin + p*Size(); 
  }

  // 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);
  
  virtual float SurfaceArea() const;
  virtual float GetVolume() const {
    return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
  }

  // 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};
  
  int
  ComputeMinMaxT(const Vector3 &origin,
                                 const Vector3 &direction,
                                 float *tmin,
                                 float *tmax) const;
        
  // Compute tmin and tmax for a ray, whenever required .. need not pierce box
  int ComputeMinMaxT(const Ray &ray, float *tmin, float *tmax) const;

  // Compute tmin and tmax for a ray, whenever required .. need not pierce box
  int ComputeMinMaxT(const Ray &ray,
                                         float *tmin,
                                         float *tmax,
                                         EFaces &entryFace,
                                         EFaces &exitFace) const;
  
  // If a ray pierces the box .. returns 1, otherwise 0.
  // Computes the signed distances for case: tmin < tmax and tmax > 0
  int GetMinMaxT(const Ray &ray, float *tmin, float *tmax) const;
  // computes the signed distances for case: tmin < tmax and tmax > 0
  int GetMinMaxT(const Ray &ray, float *tmin, float *tmax,
                 EFaces &entryFace, EFaces &exitFace) const;
  
  // Writes a brief description of the object, indenting by the given
  // number of spaces first.
  virtual void Describe(ostream& app, int ind) const;

  // For edge .. number <0..11> returns two incident vertices
  void GetEdge(const 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(const int N, Vector3 &vertex) const;

  Vector3 GetVertex(const int N) const {
    Vector3 v;
    GetVertex(N, v);
    return v;
  }

  // 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;
  int GetFaceVisibilityMask(const Rectangle3 &rectangle) const;

  Rectangle3 GetFace(const int face) const;
 
  /** Extracts plane of bounding box.
  */
  Plane3 GetPlane(const int face) const;
  
  // For a given point returns the region, where the point is located
  // there are 27 regions (0..26) .. determined by the planes embedding in the
  // sides of the bounding box (0 .. lower the position of the box,
  // 1 .. inside the box, 2 .. greater than box). The region number is given as
  // R = 9*x + 3*y + z  ; e.g. region .. inside the box is 13.
  int GetRegionID(const Vector3 &point) const;
  
  // Set the corner point of rectangle on the face of bounding box
  // given by the index number and the rectangle lying on this face
  //  void GetFaceRectCorner(const CRectLeaf2D *rect, EFaces faceIndx,
  //                     const int &cornerIndx, Vector3 &cornerPoint);

  // Project the box to a plane given a normal vector of this plane. Computes
  // the surface area of projected silhouettes for parallel projection.
  float ProjectToPlaneSA(const Vector3 &normal) const;

  // Computes projected surface area of the box to a given viewing plane
  // given a viewpoint. This corresponds the probability, the box will
  // be hit by the ray .. moreover returns .. the region number (0-26).
  // the function supposes all the points lie of the box lies in the viewing
  // frustrum !!! The positive halfspace of viewplane has to contain
  // viewpoint. "projectionType" == 0 .. perspective projection,
  // == 1 .. parallel projection.
  float ProjectToPlaneSA(const Plane3 &viewplane,
                         const Vector3 &viewpoint,
                         int *tcase,
                         const float &maxSA,
                         int projectionType) const;

  // Computes projected surface area of the box to a given viewing plane
  // and viewpoint. It clipps the area by all the planes given .. they should
  // define the viewing frustrum. Variable tclip defines, which planes are
  // used for clipping, parameter 31 is the most general, clip all the plane.
  // 1 .. clip left, 2 .. clip top, 4 .. clip right, 8 .. clip bottom,
  // 16 .. clip supporting plane(its normal towards the viewing frustrum).
  // "typeProjection" == 0 .. perspective projection,
  // == 1 .. parallel projection
  float ProjectToPlaneSA(const Plane3 &viewplane,
                         const Vector3 &viewpoint,
                         int *tcase, int &tclip,
                         const Plane3 &leftPlane,
                         const Plane3 &topPlane,
                         const Plane3 &rightPlane,
                         const Plane3 &bottomPlane,
                         const Plane3 &suppPlane,
                         const float &maxSA,
                         int typeProjection) const;

  // Projects the box to a unit sphere enclosing a given viewpoint and
  // returns the solid angle of the box projected to a unit sphere
  float ProjectToSphereSA(const Vector3 &viewpoint, int *tcase) const;

  /** Returns vertex indices of edge.
  */
  void GetEdge(const int edge, int  &aIdx, int &bIdx) const;

  /** Computes cross section of plane with box (i.e., bounds box). 
          @returns the cross section
  */
  Polygon3 *CrossSection(const Plane3 &plane) const;

  /** Computes minimal and maximal t of ray, including the object intersections.
          @returns true if ray hits the bounding box.
  */
  bool GetRaySegment(const Ray &ray, float &minT, float &maxT) const;

  /** If the boxes are intersecting on a common face, this function 
          returns the face intersection, false otherwise.
    
          @param neighbour the neighbouring box intersecting with this box.
  */
  bool GetIntersectionFace(Rectangle3 &face,
                                                   const AxisAlignedBox3 &neighbour) const;

  /** Includes the box faces to the mesh description
  */
  friend void IncludeBoxInMesh(const AxisAlignedBox3 &box, Mesh &mesh);

  /** Box faces are turned into polygons.
  */
  void ExtractPolys(PolygonContainer &polys) const;

  /** Returns true if the mesh intersects the bounding box.
  */
  bool Intersects(const Mesh &mesh) const;
   /** Returns true if the triangle intersects the bounding box.
  */
  bool Intersects(const Triangle3 &tri) const;
  /** Splits the box into two separate boxes with respect to the split plane
  */
  void Split(const int axis, 
                         const float value, 
                         AxisAlignedBox3 &left, 
                         AxisAlignedBox3 &right) const;

#define __EXTENT_HACK
  // get the extent of face
  float GetExtent(const int &face) const {
#if defined(__EXTENT_HACK) && defined(__VECTOR_HACK)
    return mMin[face];
#else
    if (face < 3)
      return mMin[face];
    else
      return mMax[face-3];
#endif
  }

  // 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];

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

protected:
  // definition of friend functions
  friend class Ray;
};

// --------------------------------------------------------------------------
// Implementation of inline (member) functions
  
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));
  // return AxisAlignedBox3(Vector3(0), Vector3(-1));
}

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)
{
  Vector3 mmin(MAXFLOAT);
  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