bbox.h File Reference

‎//*****************************************************************************
// Copyright 1986, 2016 NVIDIA Corporation. All rights reserved.
//*****************************************************************************
//*****************************************************************************

#ifndef MI_MATH_BBOX_H
#define MI_MATH_BBOX_H

#include <mi/base/types.h>
#include <mi/math/assert.h>
#include <mi/math/function.h>
#include <mi/math/vector.h>
#include <mi/math/matrix.h>

namespace mi {

namespace math {

//------- POD struct that provides storage for bbox elements ----------

template <typename T, Size DIM>
struct Bbox_struct
{
    Vector_struct< T, DIM> 
               min;  
    Vector_struct< T, DIM> 
               max;  
};


template <typename T, Size DIM>
class Bbox
{
public:
    typedef math::Vector< T, DIM> 
               Vector;         
    typedef Bbox_struct< T, DIM>  
               Pod_type;       
    typedef Vector         
               value_type;          
    typedef Size           
               size_type;           
    typedef Difference     
               difference_type;     
    typedef Vector *       pointer;             
    typedef const Vector * const_pointer;       
    typedef Vector &       reference;           
    typedef const Vector & const_reference;     

    static const Size 
               DIMENSION = DIM;          
    static const Size 
               SIZE      = 2;            

    static inline Size 
               size()     { return SIZE; }

    static inline Size 
               max_size() { return SIZE; }

    enum Uninitialized_tag {
        UNINITIALIZED_TAG
    };

    Vector 
               min;  
    Vector 
               max;  

    inline void clear()
    {
        for( Size i = 0; i < DIM; i++) {
            min[i] =  base::numeric_traits< T>::max 
               MI_PREVENT_MACRO_EXPAND ();
            max[i] =  base::numeric_traits< T>::negative_max();
        }
    }

    inline Bbox() { clear(); }

    inline explicit Bbox( Uninitialized_tag) { }

    inline Bbox( const Bbox_struct< T, DIM>& bbox_struct )
    {
        min = bbox_struct.min;
        max = bbox_struct.max;
    }

    inline explicit Bbox(
        const Vector& point)    
    {
        min = point;
        max = point;
    }

    inline Bbox(
        const Vector& nmin,     
        const Vector& nmax)     
    {
        min = nmin;
        max = nmax;
    }

    inline Bbox(
        T min_x,                
        T max_x)                
    {
        mi_static_assert(DIM == 1);
        min = Vector( min_x);
        max = Vector( max_x);
    }

    inline Bbox(
        T min_x,                
        T min_y,                
        T max_x,                
        T max_y)                
    {
        mi_static_assert(DIM == 2);
        min = Vector( min_x, min_y);
        max = Vector( max_x, max_y);
    }

    inline Bbox(
        T min_x,                
        T min_y,                
        T min_z,                
        T max_x,                
        T max_y,                
        T max_z)                
    {
        mi_static_assert(DIM == 3);
        min = Vector( min_x, min_y, min_z);
        max = Vector( max_x, max_y, max_z);
    }

    template <typename InputIterator>
    Bbox(
        InputIterator first,
        InputIterator last);

    template <typename T2>
    inline explicit Bbox( const Bbox< T2, DIM>& other)
    {
        min = Vector( other.min);
        max = Vector( other.max);
    }

    inline Bbox& operator=( const Bbox& other)
    {
        min = other.min;
        max = other.max;
        return *this;
    }

    inline Bbox& operator=( const Bbox_struct< T, DIM>& other)
    {
        min = other.min;
        max = other.max;
        return *this;
    }

    inline operator Bbox_struct< T, DIM>() const
    {
        Bbox_struct< T, DIM> result;
        result.min = min;
        result.max = max;
        return result;
    }

    inline Vector* begin() { return &min; }

    inline const Vector* begin() const { return &min; }

    inline Vector* end() { return begin() + SIZE; }

    inline const Vector* end() const { return begin() + SIZE; }

    inline Vector& operator[]( Size i)
    {
        mi_math_assert_msg( i < SIZE, "precondition");
        return begin()[i];
    }

    inline const Vector& operator[]( Size i) const
    {
        mi_math_assert_msg( i < SIZE, "precondition");
        return begin()[i];
    }

    inline bool empty() const
    {
        for( Size i = 0; i < DIM; i++) {
            if( min[i] !=  base::numeric_traits< T>::max 
               MI_PREVENT_MACRO_EXPAND())
                return false;
            if( max[i] !=  base::numeric_traits< T>::negative_max())
                return false;
        }
        return true;
    }

    inline Size 
               rank() const
    {
        Size 
               rank = 0;
        for( Size i = 0; i < DIM; i++)
            rank += (min[i] < max[i]);
        return rank;
    }

    inline bool is_point() const { return min == max; }

    inline bool is_line() const { return rank() == 1u; }

    inline bool is_plane() const { return rank() == 2u; }

    inline bool is_volume() const { return rank() == 3u; }

    inline bool contains( const Vector& vec) const
    {
        for( Size i = 0; i < DIM; i++) {
            if( vec[i] < min[i] || vec[i] > max[i])
                return false;
        }
        return true;
    }

    inline bool intersects( const Bbox& other) const
    {
        for( Size i = 0; i < DIM; i++) {
            if( min[i] > (other.max)[i] || max[i] < (other.min)[i])
                return false;
        }
        return true;
    }

    inline void insert( const Bbox& other)
    {
        min = elementwise_min( min, (other.min));
        max = elementwise_max( max, (other.max));
    }

    inline void insert( const Vector& point)
    {
        min = elementwise_min( min, point);
        max = elementwise_max( max, point);
    }

    template <typename InputIterator>
    void insert(
        InputIterator first,
        InputIterator last);


    inline Bbox 
               add_motionbox(
        const Bbox& vbox,
        T           t) const
    {
        mi_math_assert_msg( ! empty(),      "precondition");
        mi_math_assert_msg( ! vbox.empty(), "precondition");
        return t < 0 ? Bbox(min + (vbox.max) * t, max + (vbox.min) * t) //-V547 PVS
                     : Bbox(min + (vbox.min) * t, max + (vbox.max) * t);
    }

    inline void push_back( const Bbox& other)
    {
        return insert( other);
    }

    void robust_grow( T eps = T(1.0e-5f)); 

    inline T volume() const
    {
        Vector diag = max - min;
        T vol = base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[0]);
        for( Size i = 1; i < DIM; i++)
            vol *= base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[i]);
        return vol;
    }

    inline T diagonal_length() const
    {
        mi_math_assert_msg( !empty(), "precondition");
        Vector diag = max - min;
        return length( diag);
    }

    inline Size 
               largest_extent_index() const
    {
        Vector diag = max - min;
        T maxval = diag[0];
        Size  maxidx = 0;
        for( Size i = 1; i < DIM; i++) {
            if (maxval < diag[i]) {
                maxval = diag[i];
                maxidx = i;
            }
        }
        return maxidx;
    }

    inline Vector 
               center() const { return (max + min) * T(0.5);}

};

//------ Operator declarations for Bbox ---------------------------------------

template <typename T, Size DIM>
inline Bbox< T, DIM>  
               operator+( const Bbox< T, DIM>& bbox, T value)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    Bbox< T, DIM> result( Bbox< T, DIM>::UNINITIALIZED_TAG);
    for( Size i = 0; i < DIM; i++) {
        (result.min)[i] = (bbox.min)[i] - value;
        (result.max)[i] = (bbox.max)[i] + value;
    }
    return result;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>  
               operator-( const Bbox< T, DIM>& bbox, T value)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    Bbox< T, DIM> result( Bbox< T, DIM>::UNINITIALIZED_TAG);
    for( Size i = 0; i < DIM; i++) {
        (result.min)[i] = (bbox.min)[i] + value;
        (result.max)[i] = (bbox.max)[i] - value;
    }
    return result;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>  
               operator*( const Bbox< T, DIM>& bbox, T factor)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    Bbox< T, DIM> result( Bbox< T, DIM>::UNINITIALIZED_TAG);
    for( Size i = 0; i < DIM; i++) {
        (result.min)[i] = (bbox.min)[i] * factor;
        (result.max)[i] = (bbox.max)[i] * factor;
    }
    return result;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>  
               operator/( const Bbox< T, DIM>& bbox, T divisor)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    mi_math_assert_msg( divisor != T(0), "precondition");
    Bbox< T, DIM> result( Bbox< T, DIM>::UNINITIALIZED_TAG);
    for( Size i = 0; i < DIM; i++) {
        (result.min)[i] = (bbox.min)[i] / divisor;
        (result.max)[i] = (bbox.max)[i] / divisor;
    }
    return result;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>& operator+=( Bbox< T, DIM>& bbox, T value)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    for( Size i = 0; i < DIM; i++) {
        (bbox.min)[i] -= value;
        (bbox.max)[i] += value;
    }
    return bbox;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>& operator-=( Bbox< T, DIM>& bbox, T value)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    for( Size i = 0; i < DIM; i++) {
        (bbox.min)[i] += value;
        (bbox.max)[i] -= value;
    }
    return bbox;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>& operator*=( Bbox< T, DIM>& bbox, T factor)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    for( Size i = 0; i < DIM; i++) {
        (bbox.min)[i] *= factor;
        (bbox.max)[i] *= factor;
    }
    return bbox;
}

template <typename T, Size DIM>
inline Bbox< T, DIM>& operator/=( Bbox< T, DIM>& bbox, T divisor)
{
    mi_math_assert_msg( !bbox.empty(), "precondition");
    mi_math_assert_msg( divisor != T(0), "precondition");
    for( Size i = 0; i < DIM; i++) {
        (bbox.min)[i] /= divisor;
        (bbox.max)[i] /= divisor;
    }
    return bbox;
}

template <typename T, Size DIM>
inline bool  operator==(const Bbox< T, DIM>& lhs, const Bbox< T, DIM>& rhs)
{
    return (lhs.min) == (rhs.min) && (lhs.max) == (rhs.max);
}

template <typename T, Size DIM>
inline bool  operator!=(const Bbox< T, DIM>& lhs, const Bbox< T, DIM>& rhs)
{
    return (lhs.min) != (rhs.min) || (lhs.max) != (rhs.max);
}

template <typename T, Size DIM>
inline bool operator< ( const Bbox<T,DIM> & lhs, const Bbox< T, DIM> & rhs)
{
    for( Size i(0u); i < DIM; ++i) {
        if( (lhs.min)[i] < (rhs.min)[i])
            return true;
        if( (lhs.min)[i] > (rhs.min)[i])
            return false;
    }
    return lexicographically_less( lhs.max, rhs.max);
}

template <typename T, Size DIM>
inline bool operator<=( const Bbox<T,DIM>& lhs, const Bbox< T, DIM>& rhs)
{
    for( Size i(0u); i < DIM; ++i) {
        if( (lhs.min)[i] < (rhs.min)[i])
            return true;
        if( (lhs.min)[i] > (rhs.min)[i])
            return false;
    }
    return lexicographically_less_or_equal( lhs.max, rhs.max);
}

template <typename T, Size DIM>
inline bool operator>( const Bbox< T, DIM> & lhs, const Bbox< T, DIM> & rhs)
{
    for( Size i(0u); i < DIM; ++i) {
        if( (lhs.min)[i] > (rhs.min)[i])
            return true;
        if( (lhs.min)[i] < (rhs.min)[i])
            return false;
    }
    return lexicographically_greater( lhs.max, rhs.max);
}

template <typename T, Size DIM>
inline bool operator>=( const Bbox< T, DIM>& lhs, const Bbox< T, DIM>& rhs)
{
    for( Size i(0u); i < DIM; ++i) {
        if( (lhs.min)[i] > (rhs.min)[i])
            return true;
        if( (lhs.min)[i] < (rhs.min)[i])
            return false;
    }
    return lexicographically_greater_or_equal( lhs.max, rhs.max);
}


//------ Free Functions for Bbox ----------------------------------------------


template <typename T, Size DIM>
inline Bbox< T, DIM> 
               lerp(
    const Bbox< T, DIM> &bbox1,  
    const Bbox< T, DIM> &bbox2,  
    T          t)              
{
    mi_math_assert_msg( !bbox1.empty(), "precondition");
    mi_math_assert_msg( !bbox2.empty(), "precondition");
    T t2 = T(1) - t;
    return Bbox< T, DIM>( (bbox1.min)*t2 + (bbox2.min)*t, (bbox1.max)*t2 + (bbox2.max)*t);
}


template <typename T, Size DIM>
inline Bbox< T, DIM> 
               clip(
    const Bbox< T, DIM> &bbox1,   
    const Bbox< T, DIM> &bbox2)   
{
    Bbox< T, DIM> result( Bbox< T, DIM>::UNINITIALIZED_TAG);
    for( Size i = 0; i < DIM; i++) {
        result.min[i] = base::max MI_PREVENT_MACRO_EXPAND (bbox1.min[i], bbox2.min[i]);
        result.max[i] = base::min MI_PREVENT_MACRO_EXPAND (bbox1.max[i], bbox2.max[i]);
        if (result.max[i] < result.min[i]) { // the bbox is empty
            result.clear();
            return result;
        }
    }

    return result;
}

template <typename TT, typename T>
Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);


template <typename TT, typename T>
Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);



//------ Definitions of non-inline function -----------------------------------

#ifndef MI_FOR_DOXYGEN_ONLY

template <typename T, Size DIM>
template <typename InputIterator>
void Bbox< T, DIM>::insert( InputIterator first, InputIterator last)
{
    for( ; first != last; ++first)
        insert( *first);
}

template <typename T, Size DIM>
template <typename InputIterator>
Bbox<T,DIM>::Bbox( InputIterator first, InputIterator last)
{
    clear();
    insert( first, last);
}

template <typename T, Size DIM>
void Bbox<T, DIM>::robust_grow( T eps)
{
    // Just enlarging the bounding box by epsilon * (largest box extent) is not sufficient, since
    // there may be cancelation errors if the box is far away from the origin. Hence we take into
    // account the distance of the box from the origin: the further the box is away, the larger we
    // have to make it. We just add the two contributions. If we are very far away, then distance
    // will dominate. For very large boxes, the extent will dominate. We neglect exact weight
    // factors. We are just a bit less generous with the epsilon to compensate for the extra stuff
    // we added. If we have objects that in some direction are several orders of magnitude larger
    // than in the others, this method will not be perfect.
    //
    // compute size heuristic for each dimension
    Vector dist;
    for( Size i = 0; i < DIM; i++)
        dist[i] = base::abs(min[i]) + base::abs(max[i])
                + base::abs(max[i] - min[i]);
    // compute the grow factor
    T max_dist = T(0);
    for( Size i = 0; i < DIM; i++)
        max_dist = base::max MI_PREVENT_MACRO_EXPAND (max_dist, dist[i]);
    const T margin = max_dist * eps;
    // grow the bounding box
    *this += margin;
}

#endif // MI_FOR_DOXYGEN_ONLY

template <typename TT, typename T>
Bbox< T, 3> 
               transform_point( const Matrix< TT, 4, 4>& mat, const Bbox< T, 3>& bbox)
{
    if( bbox.empty())
        return bbox;

    // Transforms all eight corner points, and finds then the bounding box of these eight points.
    // The corners are computed in an optimized manner which factorizes computations.
    //
    // The transformation is decomposed into the transformation of (min,1) and the transformation of
    // bounding box difference vectors (max.x-min.x,0,0,0),(0, max.y-min.y,0,0),(0,0,max.z-min.z,0).
    // The transformation of max is the sum of all 4 transformed vectors. The division by the
    // homogeneous w is deferred to the end.
    Vector< T, 3> corners[8];
    corners[0] = transform_vector( mat, bbox.min);
    corners[0].x += T(mat.wx);
    corners[0].y += T(mat.wy);
    corners[0].z += T(mat.wz);

    // difference vectors between min and max
    Vector< T, 3> dx = transform_vector( mat, Vector< T, 3>( (bbox.max).x - (bbox.min).x, 0, 0));
    Vector< T, 3> dy = transform_vector( mat, Vector< T, 3>( 0, (bbox.max).y - (bbox.min).y, 0));
    Vector< T, 3> dz = transform_vector( mat, Vector< T, 3>( 0, 0, (bbox.max).z - (bbox.min).z));

    corners[1] = corners[0] + dz;                       // vertex 001
    corners[2] = corners[0] + dy;                       // vertex 010
    corners[3] = corners[0] + dy + dz;                  // vertex 011
    corners[4] = corners[0] + dx;                       // vertex 100
    corners[5] = corners[0] + dx + dz;                  // vertex 101
    corners[6] = corners[0] + dx + dy;                  // vertex 110
    corners[7] = corners[0] + dx + dy + dz;             // vertex 110

    // compute the w-coordinates separately. This is done to avoid copying from 4D to 3D vectors.
    // Again, the computation is decomposed.
    //
    // w-coordinate for difference vectors between min and max
    T wx = T( mat.xw * ((bbox.max).x - (bbox.min).x));
    T wy = T( mat.yw * ((bbox.max).y - (bbox.min).y));
    T wz = T( mat.zw * ((bbox.max).z - (bbox.min).z));
    // w-coordinate for corners
    T w[8];
    w[0] = T(mat.xw * (bbox.min).x + mat.yw * (bbox.min).y + mat.zw * (bbox.min).z + mat.ww);
    w[1] = w[0] + wz;                                   // vertex 001
    w[2] = w[0] + wy;                                   // vertex 010
    w[3] = w[0] + wy + wz;                              // vertex 011
    w[4] = w[0] + wx;                                   // vertex 100
    w[5] = w[0] + wx + wz;                              // vertex 101
    w[6] = w[0] + wx + wy;                              // vertex 110
    w[7] = w[0] + wx + wy + wz;                         // vertex 111

    // divide the other coordinates (x,y,z) by w to obtain 3D coordinates
    for( unsigned int i=0; i<8; ++i) {
        if( w[i]!=0 && w[i]!=1) {
            T inv = T(1) / w[i];
            corners[i].x *= inv;
            corners[i].y *= inv;
            corners[i].z *= inv;
        }
    }
    Bbox< T, 3> result( corners, corners+8);
    return result;
}

template <typename TT, typename T>
Bbox< T, 3> 
               transform_vector( const Matrix< TT, 4, 4>& mat, const Bbox< T, 3>& bbox)
{
    // See transform_point() above for implementation notes.
    if( bbox.empty())
        return bbox;

    Vector< T, 3> corners[8];
    corners[0] = transform_vector( mat, (bbox.min));

    Vector< T, 3> dx = transform_vector( mat, Vector< T, 3>( (bbox.max).x - (bbox.min).x, 0, 0));
    Vector< T, 3> dy = transform_vector( mat, Vector< T, 3>( 0, (bbox.max).y - (bbox.min).y, 0));
    Vector< T, 3> dz = transform_vector( mat, Vector< T, 3>( 0, 0, (bbox.max).z - (bbox.min).z));

    corners[1] = corners[0] + dz;
    corners[2] = corners[0] + dy;
    corners[3] = corners[0] + dy + dz;
    corners[4] = corners[0] + dx;
    corners[5] = corners[0] + dx + dz;
    corners[6] = corners[0] + dx + dy;
    corners[7] = corners[0] + dx + dy + dz;

    Bbox< T, 3> result( corners, corners+8);
    return result;
}
 // end group mi_math_bbox

} // namespace math

} // namespace mi

#endif // MI_MATH_BBOX_H