bbox.h

Go to the documentation of this file.

/***************************************************************************************************
 * Copyright 2022 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 //-V690 PVS
{
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) { }
 
#if (__cplusplus >= 201103L)
    Bbox( const Bbox<T,DIM>& other ) = default;
#endif
 
    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);
    }
 
    template <typename T2>
    inline explicit Bbox( const Bbox_struct<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++) //-V1008 PVS
            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++) { //-V1008 PVS
            if (maxval < diag[i]) {
                maxval = diag[i];
                maxidx = i;
            }
        }
        return maxidx;
    }
 
    inline Vector center() const { return Vector((max + min) * 0.5);}
 
    inline Vector extent() const { return max - min; }
 
};
 
//------ 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 cancellation 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