UT/UT_BoundingBox.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Mark Elendt
 *      Side Effects Software Inc.
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-366-4607
 */

#ifndef __UT_BoundingBox_h__
#define __UT_BoundingBox_h__

#include "UT_API.h"
#include "UT_Assert.h"
#include "UT_Vector3.h"
#include "UT_VectorTypes.h"
#include <iostream.h>

/// Axis-aligned bounding box (AABB).
template <typename T>
class UT_API UT_BoundingBoxT
{
public:
                 UT_BoundingBoxT() {}
                 // Default copy constructor is fine.
                 // UT_BoundingBoxT(const UT_BoundingBoxT &);
                 UT_BoundingBoxT(T axmin, T aymin, T azmin,
                                 T axmax, T aymax, T azmax)
                 {
                     setBounds(axmin, aymin, azmin, axmax, aymax, azmax);
                 }

                 UT_BoundingBoxT(const UT_Vector3T<T> &lowerbound,
                                 const UT_Vector3T<T> &upperbound)
                 {
                     vals[0][0] = lowerbound.vec[0];
                     vals[0][1] = upperbound.vec[0];
                     vals[1][0] = lowerbound.vec[1];
                     vals[1][1] = upperbound.vec[1];
                     vals[2][0] = lowerbound.vec[2];
                     vals[2][1] = upperbound.vec[2];
                 }

                 template <typename S>
                 UT_BoundingBoxT(const UT_BoundingBoxT<S> &bbox)
                 {
                     vals[0][0] = bbox.vals[0][0];
                     vals[0][1] = bbox.vals[0][1];
                     vals[1][0] = bbox.vals[1][0];
                     vals[1][1] = bbox.vals[1][1];
                     vals[2][0] = bbox.vals[2][0];
                     vals[2][1] = bbox.vals[2][1];
                 }

    template <typename S>
    UT_BoundingBoxT &operator=(const UT_BoundingBoxT<S> &bbox)
                 {
                     vals[0][0] = bbox.vals[0][0];
                     vals[0][1] = bbox.vals[0][1];
                     vals[1][0] = bbox.vals[1][0];
                     vals[1][1] = bbox.vals[1][1];
                     vals[2][0] = bbox.vals[2][0];
                     vals[2][1] = bbox.vals[2][1];
                     return *this;
                 }

    T            operator()(unsigned m, unsigned n) const
                 {
                     UT_ASSERT_P( m < 3 && n < 2 );
                     return vals[m][n];
                 }
    T           &operator()(unsigned m, unsigned n)
                 {
                     UT_ASSERT_P( m < 3 && n < 2 );
                     return vals[m][n];
                 }
    bool         operator==(const UT_BoundingBoxT<T> &bbox) const
                 {
                     return vals[0][0] == bbox.vals[0][0] &&
                            vals[0][1] == bbox.vals[0][1] &&
                            vals[1][0] == bbox.vals[1][0] &&
                            vals[1][1] == bbox.vals[1][1] &&
                            vals[2][0] == bbox.vals[2][0] &&
                            vals[2][1] == bbox.vals[2][1];
                 }
    bool         operator!=(const UT_BoundingBoxT<T> &bbox) const
                 {
                     return !(*this == bbox);
                 }
    bool         isEqual(const UT_BoundingBoxT<T> &bbox,
                         T tol = SYS_FTOLERANCE_R) const
                 {
                     return SYSisEqual(vals[0][0], bbox.vals[0][0], tol) &&
                            SYSisEqual(vals[0][1], bbox.vals[0][1], tol) &&
                            SYSisEqual(vals[1][0], bbox.vals[1][0], tol) &&
                            SYSisEqual(vals[1][1], bbox.vals[1][1], tol) &&
                            SYSisEqual(vals[2][0], bbox.vals[2][0], tol) &&
                            SYSisEqual(vals[2][1], bbox.vals[2][1], tol);
                 }

    T            xmin() const   { return vals[0][0]; }
    T            xmax() const   { return vals[0][1]; }
    T            ymin() const   { return vals[1][0]; }
    T            ymax() const   { return vals[1][1]; }
    T            zmin() const   { return vals[2][0]; }
    T            zmax() const   { return vals[2][1]; }

    UT_Vector3T<T>  minvec() const 
                 { return UT_Vector3T<T>(vals[0][0], vals[1][0], vals[2][0]); }
    UT_Vector3T<T>  maxvec() const 
                 { return UT_Vector3T<T>(vals[0][1], vals[1][1], vals[2][1]); }

    int          isInside(const UT_Vector3T<T> &pt) const;
    int          isInside(const UT_Vector4T<T> &pt) const;
    int          isInside(T x, T y, T z) const;

    /// Am I totally enclosed in the bounding box passed in
    /// ("intersects" method tests for partially inside)
    int          isInside(const UT_BoundingBoxT<T> &bbox) const;

    /// Determine whether a line intersects the box.  v0 is one endpoint of
    /// the line, and idir is the inverse direction vector along the line.
    int          isLineInside(const UT_Vector3T<T> &v0,
                              const UT_Vector3T<T> &idir) const;

    /// Determine the minimum distance of the box to a line segment, or 0
    /// if the line segment overlaps the box.  v0 is one endpoint of the
    /// line, and dir is the direction vector along the line.  This method
    /// conservatively underestimates the distance, so the true line/box
    /// distance may be greater than the reported value.
    T            approxLineDist2(const UT_Vector3T<T> &v0,
                                 const UT_Vector3T<T> &dir) const;

    /// Check whether the bounding box contains at least one point.
    bool         isValid() const;
    void         makeInvalid()  { initBounds(); }

    void         setBounds(T x_min, T y_min, T z_min,
                           T x_max, T y_max, T z_max)
                 {
                     vals[0][0] = x_min;
                     vals[1][0] = y_min;
                     vals[2][0] = z_min;
                     vals[0][1] = x_max;
                     vals[1][1] = y_max;
                     vals[2][1] = z_max;
                 }

    /// @{
    /// Set/Get bounds in "serialized" fashion.  The serialized order is
    /// (xmin, xmax, ymin, ymax, zmin, zmax).
    void        setSerialized(const fpreal32 floats[6])
                {
                    for (int i = 0; i < 6; ++i)
                        myFloats[i] = floats[i];
                }
    void        setSerialized(const fpreal64 floats[6])
                {
                    for (int i = 0; i < 6; ++i)
                        myFloats[i] = floats[i];
                }
    const T     *getSerialized() const  { return myFloats; }
    /// @}

    /// Initialize the box to the largest size
    void         initMaxBounds();

    /// Initialize the box such that
    /// - No points are contained in the box
    /// - The box occupies no position in space
    void         initBounds();
    void         initBounds(const UT_Vector3T<T> &min,
                            const UT_Vector3T<T> &max);
    void         initBounds(const UT_Vector3T<T> &pt);
    void         initBounds(const UT_Vector4T<T> &pt);
    void         initBounds(T x, T y, T z);
    void         initBounds(const fpreal32 *v)
                    { initBounds(v[0], v[1], v[2]); }
    void         initBounds(const fpreal64 *v)
                    { initBounds(v[0], v[1], v[2]); }
    void         initBounds(const UT_BoundingBoxT<T> &box);

    void         enlargeBounds(const UT_Vector3T<T> &min,
                               const UT_Vector3T<T> &max);
    void         enlargeBounds(const UT_Vector3T<T> &pt);
    void         enlargeBounds(const UT_Vector4T<T> &pt);
    void         enlargeBounds(T x, T y, T z);
    void         enlargeBounds(const fpreal32 *v)
                    { enlargeBounds(v[0], v[1], v[2]); }
    void         enlargeBounds(const fpreal64 *v)
                    { enlargeBounds(v[0], v[1], v[2]); }
    void         enlargeBounds(const UT_BoundingBoxT<T> &box);
    void         enlargeBounds(T percent = 0.001, T min = 0.001);
    void         expandBounds(T dltx, T dlty, T dlyz);

    /// Perform a minimal enlargement of the floating point values in this
    /// bounding box.  This enlargement guarantees that the new floating
    /// point values are always different from the prior ones.  The number
    /// of mantissa bits to be changed can be adjusted using the bits
    /// parameter, and a minimum enlargement amount can be specified in min.
    void         enlargeFloats(int bits = 1, T min = 1e-5);

    /// Find the intersections of two bounding boxes
    void         clipBounds(const UT_BoundingBoxT<T> &box);

    /// Splits a box into two disjoint subboxes at the given splitting
    /// point.  This box is set to the left subbox for splitLeft() and the
    /// right subbox for splitRight().
    void         splitLeft(UT_BoundingBoxT<T> &box, int axis, T split)
                 {
                     box = *this;
                     box.vals[axis][0] = split;
                     vals[axis][1] = split;
                 }
    void         splitRight(UT_BoundingBoxT<T> &box, int axis, T split)
                 {
                     box = *this;
                     box.vals[axis][1] = split;
                     vals[axis][0] = split;
                 }

    template <typename S>
    void         transform(const UT_Matrix4T<S> &mat);
    template <typename S>
    void         transform(const UT_Matrix4T<S> &mat, 
                           UT_BoundingBoxT<T> &newbbox) const;

    /// Adds the given translate to each component of the bounding box.
    void         translate(const UT_Vector3T<T> &delta);
                                  
    T            xsize() const { return sizeX(); }
    T            ysize() const { return sizeY(); }
    T            zsize() const { return sizeZ(); }
    T            sizeX() const { return vals[0][1] - vals[0][0]; }
    T            sizeY() const { return vals[1][1] - vals[1][0]; }
    T            sizeZ() const { return vals[2][1] - vals[2][0]; }

    UT_Vector3T<T>  size() const 
                 { return UT_Vector3T<T>(vals[0][1] - vals[0][0],
                                         vals[1][1] - vals[1][0],
                                         vals[2][1] - vals[2][0]); }
    T            sizeAxis(int axis) const 
                 {
                     UT_ASSERT(axis >= 0 && axis < 3);
                     return vals[axis][1] - vals[axis][0];
                 }

    /// Return the size of the largest dimension
    T            sizeMax() const;  
    /// Return the size of the largest dimension, and store the dimension
    /// index in "axis"
    T            sizeMax(int &axis) const;  
    /// Returns the minimum delta vector from the point to the bounding
    /// box or between two bounding boxes.
    UT_Vector3T<T>  minDistDelta(const UT_Vector3T<T> &p) const;
    UT_Vector3T<T>  minDistDelta(const UT_BoundingBoxT<T> &box) const;
    /// Returns minimum distance from point to bounding box squared.
    /// Returns 0 if point in bouding box.
    T            minDist2(const UT_Vector3T<T> &p) const
                 { return minDistDelta(p).length2(); }
    /// Minimum disance between two bboxes squared.
    T            minDist2(const UT_BoundingBoxT<T> &box) const
                 { return minDistDelta(box).length2(); }

    /// Returns the radius of a sphere that would fully enclose the box.
    T            getRadius() const      { return 0.5*size().length(); }

    /// Finds the out code of the point relative to this box:
    int          getOutCode(const UT_Vector3T<T> &pt) const;

    T            xcenter() const { return centerX(); }
    T            ycenter() const { return centerY(); }
    T            zcenter() const { return centerZ(); }
    T            centerX() const { return (vals[0][0] + vals[0][1])*0.5; }
    T            centerY() const { return (vals[1][0] + vals[1][1])*0.5; }
    T            centerZ() const { return (vals[2][0] + vals[2][1])*0.5; }
    T            centerAxis(int axis) const
                 { return (vals[axis][0] + vals[axis][1])*0.5; }
    UT_Vector3T<T>  center() const
                 { return UT_Vector3T<T>((vals[0][0] + vals[0][1])*0.5,
                                         (vals[1][0] + vals[1][1])*0.5,
                                         (vals[2][0] + vals[2][1])*0.5); }

    T            area() const;
    T            volume() const { return xsize()*ysize()*zsize(); }
    void         addToMin(const UT_Vector3T<T> &vec);
    void         addToMax(const UT_Vector3T<T> &vec);

    /// Scale then offset a bounding box.
    void         scaleOffset(const UT_Vector3T<T> &scale,
                             const UT_Vector3T<T> &offset);
    int          maxAxis() const;
    int          minAxis() const;

    /// Intersect a ray with the box.  Returns 0 if no intersection found.
    /// distance will be set to the intersection distance (between 0 & tmax)
    /// The normal will also be set.  The direction of the normal is
    /// indeterminant (to fix it, you might want to dot(dir, *nml) to check
    /// the orientation.
    int          intersectRay(const UT_Vector3T<T> &org,
                              const UT_Vector3T<T> &dir,
                              T tmax=1E17F,
                              T *distance=0, UT_Vector3T<T> *nml=0) const;
    int          intersectRange(const UT_Vector3T<T> &org,
                                const UT_Vector3T<T> &dir,
                                T &min, T &max) const;
    
    /// This determines if the tube, capped at distances tmin & tmax,
    /// intersects this.
    int          intersectTube(const UT_Vector3T<T> &org,
                               const UT_Vector3T<T> &dir,
                               T radius,
                               T tmin=-1E17f, T tmax=1E17f) const;

    int          intersects(const UT_BoundingBoxT<T> &box) const;

    /// Changes the bounds to be those of the intersection of this box
    /// and the supplied BBox.  Returns 1 if intersects, 0 otherwise.
    int          computeIntersection(const UT_BoundingBoxT<T> &box);

    /// Here's the data for the bounding box
    union {
        T        vals[3][2];
        T        myFloats[6];
    };

    void         getBBoxPoints(UT_Vector3T<T> (&ptarray)[8]) const; 
    template <typename S>
    int          getBBoxPoints(UT_Vector3T<T> (&ptarray)[8],
                               const UT_Matrix4T<S> &transform_matrix) const;

    /// Dump the bounding box to stderr.  The msg is printed before the bounds
    void         dump(const char *msg=0) const;
    /// Dump the bounding box geometry to a draw file
    void         dumpGeo(FILE *fp) const;

    /// @{
    /// Methods to serialize to a JSON stream.  The vector is stored as an
    /// array of 6 reals (xmin, xmax, ymin, ymax, zmin, zmax)
    bool                save(UT_JSONWriter &w) const;
    bool                save(UT_JSONValue &v) const;
    bool                load(UT_JSONParser &p);
    /// @}


protected:
    friend
    ostream     &operator<<(ostream &os, const UT_BoundingBoxT<T> &box)
                 {
                     box.outTo(os);
                     return os;
                 }

    void         outTo(ostream &os) const;
    void         enlargeBoundsByPtArray(UT_Vector3T<T> (&ptarray)[8],
                                        bool init = false);
};

typedef UT_BoundingBoxT<fpreal>     UT_BoundingBoxR;
typedef UT_BoundingBoxT<fpreal32>   UT_BoundingBoxF;
typedef UT_BoundingBoxT<fpreal64>   UT_BoundingBoxD;
typedef UT_BoundingBoxT<float>      UT_BoundingBox;     // deprecated

#endif

---