UT_RTreeBox.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.
 *
 * NAME:        UT_RTreeBox.h (UT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __UT_RTreeBox_H__
#define __UT_RTreeBox_H__

#include "UT_Vector3.h"
#include "UT_BoundingBox.h"
#include "UT_Format.h"

#include <type_traits>

// UT_BoxT represents either an axis-aligned box or the empty set.
// UT_BoxT is closed as a set; all operations assume that 
// the boundary is included.
// FT is the number type used to represent the box coordinates,
// for example, float or double.

// Named constructor tags
struct UT_BoxCT
{
    enum BoundPointArrayType { BOUND_POINT_ARRAY };
    enum BoundIndirectRangePointArrayType { BOUND_INDIRECT_RANGE_POINT_ARRAY };
    enum BoundPointGeneratorType { BOUND_POINT_GENERATOR };
};

template< typename FT > class UT_BoxT;

// Forward declare friends:
template< typename FT > inline void setEmpty( UT_BoxT< FT >& t );

template< typename FT >
class UT_BoxT
{
public:
    using CT = UT_BoxCT;
    using Scalar = FT;
    using FT3 = UT_Vector3T< FT >;

    // Default construct: the empty set
    constexpr UT_BoxT();

    // Construct box containing a single point position,
    // which is represented by its array of three coordinates.
    template< typename U >
    constexpr explicit UT_BoxT( const U p[3] );

    template< typename U >
    constexpr explicit UT_BoxT( const UT_Vector3T< U >& p );

    constexpr explicit UT_BoxT( const UT_BoundingBox& a );
    
    // Construct a bounding box from points in an array-like type 'l_x'
    // Starting with the empty box,
    // for each l in [ 0, size ), absorb the point l_x[ l ] in the bounding box.
    // size == 0 results in the empty set.
    template< typename POINT_ARRAY >
    constexpr UT_BoxT( const CT::BoundPointArrayType, POINT_ARRAY&& l_x, const exint size );

    // Construct a bounding box from points in an array-like type 'l_x'
    // Starting with the empty box,
    // for each iterator cit in the half-open range [ begin, end ),
    // absorb the point l_x[ *cit ] in the bounding box.
    // end == begin results in the empty set.
    template< typename CIT, typename POINT_ARRAY >
    constexpr UT_BoxT( const CT::BoundIndirectRangePointArrayType, POINT_ARRAY&& l_x, const CIT begin, const CIT end );

    // Construct a bounding box using points given by
    // a generator function object
    // Starting with the empty box,
    // for each l in [ 0, size ), absorb generator( l ) in the bounding box.
    // size == 0 results in the empty set.
    template< typename POINT_GENERATOR >
    constexpr UT_BoxT( const CT::BoundPointGeneratorType, POINT_GENERATOR&& generator, const exint size );

    UT_BoxT( const UT_BoxT& ) = default;
    UT_BoxT& operator=( const UT_BoxT& ) = default;

    // Return whether this represents the empty set
    constexpr bool isEmpty() const;

    // Make a box that's a single point
    template< typename U >
    void assignPoint(const U p[3]);
    template< typename U >
    void assignPoint( const UT_Vector3T<U> p) { assignPoint(p.vec); }
    
    // Expand the box just enough so that it contains a point p
    template< typename U >
    void absorbPoint(const U p[3]);
    template< typename U >
    void absorbPoint( const UT_Vector3T<U> p) { absorbPoint(p.vec); }
    
    // Expand the box just enough so that it contains a box b
    void absorbBox(const UT_BoxT<FT>& b);
    void absorbBox(const UT_BoundingBox &b);
    
    // Expand in the directions of the axes:
    // In case this is the empty set, the result is still the empty set
    // This is equivalent to making *this the union of all cubes with
    // radius l placed at points of the original set.
    void expandDistance(const FT l);

    // Get minimum coordinate for given standard axis
    // Assumes this is not empty!
    FT getMin(const int c) const;

    // Get maximum coordinate for given standard axis
    // Assumes this is not empty!
    FT getMax(const int c) const;

    FT3 getSize() const
    {
        UT_ASSERT_P( ! isEmpty() );

        return FT3(
           (myMax[0]-myMin[0]),
           (myMax[1]-myMin[1]),
           (myMax[2]-myMin[2])
        );
    }

    FT getRadius2() const
    {
        UT_ASSERT_P( ! isEmpty() );

        const FT3 h(
           (myMax[0]-myMin[0]) / 2,
           (myMax[1]-myMin[1]) / 2,
           (myMax[2]-myMin[2]) / 2
        );

        return h.length2();
    }

    FT3 getCenter() const
    {
        UT_ASSERT_P( ! isEmpty() );

        return FT3(
            (myMin[0]+myMax[0])/2,
            (myMin[1]+myMax[1])/2,
            (myMin[2]+myMax[2])/2
        );
    }

    // Return whether a point is contained in the closed set
    bool contains(const FT p[3]) const;

    // Return the axis in which the box is the widest.
    // For the empty set, this always returns axis 0
    int getLargestAxis() const;

private:
    // This represents set of all points x
    // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
    FT myMin[ 3 ];
    FT myMax[ 3 ];

    friend void setEmpty <>( UT_BoxT< FT >& t );

    friend bool intersects( const UT_BoxT< float >& a, const UT_BoxT< float >& b );
    friend bool intersects( const UT_BoxT< double >& a, const UT_BoxT< double >& b );
};

// Overload for custom formatting of UT_BoxT with UTformat.
template< typename FT >
size_t format( char* buffer, size_t buffer_size, const UT_BoxT< FT >& a )
{
    UT::Format::Writer writer( buffer, buffer_size );
    UT::Format::Formatter f;
    return f.format(
        writer, "min[{0}, {1}, {2}]], max[{3}, {4}, {5}]",
        {
            a.getMin( 0 ),
            a.getMin( 1 ),
            a.getMin( 2 ),
            a.getMax( 0 ),
            a.getMax( 1 ),
            a.getMax( 2 )
        }
    );
}

//TODO: Move below code into UT_RTreeBoxImpl.h

namespace UT
{

// TODO: Move definitions of FT_Least and FT_Greatest
// to a separate header and include it here:

// Primary template defined for built-in floating point types:
// Map type 'FT' to the least possible value of that type
template< typename FT >
struct FT_Least
{
    constexpr auto operator()() { return std::numeric_limits< FT >::lowest(); }
};

//template< typename FT > constexpr auto FT_Least_v = FT_Least< FT >{}();

// Primary template defined for built-in floating point types:
// Map type 'FT' to the greatest possible value of that type
template< typename FT >
struct FT_Greatest
{
    constexpr auto operator()() { return std::numeric_limits< FT >::max(); }
};

//template< typename FT > constexpr auto FT_Greatest_v = FT_Greatest< FT >{}();

//
// Use class specialization on AssignCopyFT3 
// to make copy-assignment work for UT_BoxT
// when the underlying type FT has a deleted copy assignment operator
// This is the case, types FT used in $SC and $CLO.
// Such types must support "setCopy( dest, source )" instead.
//

template< typename FT, bool a = std::is_copy_assignable< FT >::value >
struct AssignCopyFT3;

template< typename FT >
struct AssignCopyFT3< FT, true >
{
    void operator()( FT ts[ 3 ], const FT as[ 3 ] )
    {
        ts[ 0 ] = as[ 0 ];
        ts[ 1 ] = as[ 1 ];
        ts[ 2 ] = as[ 2 ];
    }
};

template< typename FT >
struct AssignCopyFT3< FT, false >
{
    void operator()( FT ts[ 3 ], const FT as[ 3 ] )
    {
        setCopy( ts[ 0 ], as[ 0 ] );
        setCopy( ts[ 1 ], as[ 1 ] );
        setCopy( ts[ 2 ], as[ 2 ] );
    }
};

template< typename FT, bool a = std::is_copy_assignable< FT >::value >
struct AssignCoordinatesFT3;

template< typename FT >
struct AssignCoordinatesFT3< FT, true >
{
    void operator()( FT ts[ 3 ], const FT a0, const FT a1, const FT a2 )
    {
        ts[ 0 ] = a0;
        ts[ 1 ] = a1;
        ts[ 2 ] = a2;
    }
};

template< typename FT >
struct AssignCoordinatesFT3< FT, false >
{
    void operator()( FT ts[ 3 ], const FT a0, const FT a1, const FT a2 )
    {
        setCopy( ts[ 0 ], a0 );
        setCopy( ts[ 1 ], a1 );
        setCopy( ts[ 2 ], a2 );
    }
};

}
// namespace UT

template< typename FT >
constexpr UT_BoxT< FT >::UT_BoxT() :
    myMin{
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}()
    },
    myMax{
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}()
    }
{
}

template< typename FT >
template< typename U >
constexpr UT_BoxT< FT >::UT_BoxT( const U p[ 3 ] ) :
    myMin{
        FT( p[ 0 ] ),
        FT( p[ 1 ] ),
        FT( p[ 2 ] )
    },
    myMax{
        FT( p[ 0 ] ),
        FT( p[ 1 ] ),
        FT( p[ 2 ] )
    }
{
}

template< typename FT >
template< typename U >
constexpr UT_BoxT< FT >::UT_BoxT( const UT_Vector3T< U >& p ) :
    myMin{
        FT( p[ 0 ] ),
        FT( p[ 1 ] ),
        FT( p[ 2 ] )
    },
    myMax{
        FT( p[ 0 ] ),
        FT( p[ 1 ] ),
        FT( p[ 2 ] )
    }
{
}

template< typename FT >
constexpr UT_BoxT< FT >::UT_BoxT( const UT_BoundingBox& a ) :
    myMin{
        a.xmin(),
        a.ymin(),
        a.zmin()
    },
    myMax{
        a.xmax(),
        a.ymax(),
        a.zmax()
    }
{
}

template< typename FT >
template< typename POINT_ARRAY >
constexpr UT_BoxT< FT >::UT_BoxT(
    const CT::BoundPointArrayType,
    POINT_ARRAY&& l_x,
    const exint size
) :
    myMin{
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}()
    },
    myMax{
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}()
    }
{
    for( int l = 0; l != size; ++l )
    {
        absorbPoint( l_x[ l ] );
    }
}

template< typename FT >
template< typename CIT, typename POINT_ARRAY >
constexpr UT_BoxT< FT >::UT_BoxT(
    const CT::BoundIndirectRangePointArrayType,
    POINT_ARRAY&& l_x,
    const CIT begin, const CIT end
) :
    myMin{
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}()
    },
    myMax{
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}()
    }
{
    for( auto cit = begin; cit != end; ++cit )
    {
        absorbPoint( l_x[ *cit ] );
    }
}

template< typename FT >
template< typename POINT_GENERATOR >
constexpr UT_BoxT< FT >::UT_BoxT( const CT::BoundPointGeneratorType, POINT_GENERATOR&& generator, const exint size ) :
    myMin{
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}()
    },
    myMax{
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}()
    }
{
    for( int l = 0; l != size; ++l )
    {
        absorbPoint( generator( l ) );
    }
}



template< typename FT >
constexpr bool UT_BoxT< FT >::isEmpty() const
{
    return(
        ( myMax[ 0 ] < myMin[ 0 ] ) ||
        ( myMax[ 1 ] < myMin[ 1 ] ) ||
        ( myMax[ 2 ] < myMin[ 2 ] )
    );
}

template< typename T >
template< typename U >
inline void UT_BoxT<T>::assignPoint(const U p[3])
{
    myMin[0] = p[0];
    myMin[1] = p[1];
    myMin[2] = p[2];

    myMax[0] = p[0];
    myMax[1] = p[1];
    myMax[2] = p[2];
}

template< typename T >
template< typename U >
inline void UT_BoxT<T>::absorbPoint(const U p[3])
{
    myMin[0] = (myMin[0] > p[0]) ? p[0] : myMin[0];
    myMin[1] = (myMin[1] > p[1]) ? p[1] : myMin[1];
    myMin[2] = (myMin[2] > p[2]) ? p[2] : myMin[2];

    myMax[0] = (myMax[0] < p[0]) ? p[0] : myMax[0];
    myMax[1] = (myMax[1] < p[1]) ? p[1] : myMax[1];
    myMax[2] = (myMax[2] < p[2]) ? p[2] : myMax[2];
}

template< typename T >
inline void UT_BoxT<T>::absorbBox(const UT_BoxT<T>& b)
{
    myMin[0] = (myMin[0] > b.myMin[0]) ? b.myMin[0] : myMin[0];
    myMin[1] = (myMin[1] > b.myMin[1]) ? b.myMin[1] : myMin[1];
    myMin[2] = (myMin[2] > b.myMin[2]) ? b.myMin[2] : myMin[2];

    myMax[0] = (myMax[0] < b.myMax[0]) ? b.myMax[0] : myMax[0];
    myMax[1] = (myMax[1] < b.myMax[1]) ? b.myMax[1] : myMax[1];
    myMax[2] = (myMax[2] < b.myMax[2]) ? b.myMax[2] : myMax[2];
}

template< typename T >
inline void UT_BoxT<T>::absorbBox(const UT_BoundingBox &b)
{
    myMin[0] = (myMin[0] > b.xmin()) ? b.xmin() : myMin[0];
    myMin[1] = (myMin[1] > b.ymin()) ? b.ymin() : myMin[1];
    myMin[2] = (myMin[2] > b.zmin()) ? b.zmin() : myMin[2];

    myMax[0] = (myMax[0] < b.xmax()) ? b.xmax() : myMax[0];
    myMax[1] = (myMax[1] < b.ymax()) ? b.ymax() : myMax[1];
    myMax[2] = (myMax[2] < b.zmax()) ? b.zmax() : myMax[2];
}

template< typename T >
inline void UT_BoxT<T>::expandDistance(const T l)
{
    if( isEmpty() )
        return;

    myMin[0] -= l;
    myMin[1] -= l;
    myMin[2] -= l;

    myMax[0] += l;
    myMax[1] += l;
    myMax[2] += l;
}

template< typename T >
inline T UT_BoxT<T>::getMin(const int c) const
{
    UT_ASSERT_P( (0 <= c) && (c < 3) );
    UT_ASSERT_P( !isEmpty() );

    return myMin[c];
}

template< typename T >
inline T UT_BoxT<T>::getMax(const int c) const
{
    UT_ASSERT_P( (0 <= c) && (c < 3) );
    UT_ASSERT_P( !isEmpty() );

    return myMax[c];
}


template< typename T >
inline bool UT_BoxT<T>::contains(const T p[3]) const
{
    return ( (myMin[0] <= p[0]) && (p[0] <= myMax[0]) &&
             (myMin[1] <= p[1]) && (p[1] <= myMax[1]) &&
             (myMin[2] <= p[2]) && (p[2] <= myMax[2]) );
}

template< typename T >
inline int UT_BoxT<T>::getLargestAxis() const
{
    if( isEmpty() )
    {
        return 0;
    }

    int max_axis(0);
    T max_length(myMax[0] - myMin[0]);

    T length(0);

    length = myMax[1] - myMin[1];
    if( length > max_length )
    {
        max_length = length;
        max_axis = 1;
    }

    length = myMax[2] - myMin[2];
    if( length > max_length )
    {
        max_length = length;
        max_axis = 2;
    }

    return max_axis;
}

template< typename FT >
inline void setEmpty( UT_BoxT< FT >& t )
{
    UT::AssignCoordinatesFT3< FT >{}(
         t.myMin,
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}(),
         UT::FT_Greatest< FT >{}()
    );
    
    UT::AssignCoordinatesFT3< FT >{}(
         t.myMax,
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}(),
         UT::FT_Least< FT >{}()
    );
}

inline bool intersects( const UT_BoxT< double >& a, const UT_BoxT< double >& b )
{
    return (
            ( SYSmax( a.myMin[0], b.myMin[0] ) <= SYSmin( a.myMax[0], b.myMax[0] ) ) &&
            ( SYSmax( a.myMin[1], b.myMin[1] ) <= SYSmin( a.myMax[1], b.myMax[1] ) ) &&
            ( SYSmax( a.myMin[2], b.myMin[2] ) <= SYSmin( a.myMax[2], b.myMax[2] ) )
    );
}

inline bool intersects( const UT_BoxT< float >& a, const UT_BoxT< float >& b )
{
    // We have to load from the wrong vector & swizzle or
    // we risk reading past a page boundary, triggering a fault,
    // even though we don't use the results of the w() component.
    v4uf        tmax( &a.myMin[2] );
    v4uf        tmin( &a.myMin[0] );
    tmax = tmax.swizzle<1, 2, 3, 0>();

    v4uf        bmax( &b.myMin[2] );
    v4uf        bmin( &b.myMin[0] );
    bmax = bmax.swizzle<1, 2, 3, 0>();

    tmin = vmax(tmin, bmin);
    tmax = vmin(tmax, bmax);
    v4uu        valid = tmin <= tmax;

    int         validmask;
    validmask = signbits(valid);

    return ((validmask & 0x7) == 0x7);
}

// Return
// -1 if center(a)[ axis ]  > center(b)[ axis ]
//  0 if center(a)[ axis ] == center(b)[ axis ]
//  1 if center(a)[ axis ]  < center(b)[ axis ]
template< typename FT >
inline int signAxisCenterComparison(
    const int axis,
    const UT_BoxT< FT >& a, 
    const UT_BoxT< FT >& b
)
{
    return SYSsignum( 
        ( b.getMin( axis ) + b.getMax( axis ) )
        -
        ( a.getMin( axis ) + a.getMax( axis ) )
    );
}

#endif