MRMesh/MRBox.h

Go to the documentation of this file.

#pragma once
 
#include "MRMacros.h"
#include "MRMeshFwd.h"
#include "MRAffineXf3.h"
#include "MRVectorTraits.h"
#include <algorithm>
#include <cassert>
#include <iosfwd>
#include <limits>
#include <type_traits>
 
namespace MR
{
 
 
template <typename T>
std::array<Vector3<T>, 8> getCorners( const Box<Vector3<T>> & box );
 
template <typename V>
struct Box
{
public:
    using VTraits = VectorTraits<V>;
    using T = typename VTraits::BaseType;
    static constexpr int elements = VTraits::size;
    using Vb = typename VTraits::template ChangeBaseType<bool>; //if V is Vector3<T> then Vb is Vector3b
    using VbTraits = VectorTraits<Vb>;
 
    V min, max;
 
    const V & operator []( int e ) const { return *( &min + e ); }
          V & operator []( int e )       { return *( &min + e ); }
 
    Box() : min{ VTraits::diagonal( std::numeric_limits<T>::max() ) }, max{ VTraits::diagonal( std::numeric_limits<T>::lowest() ) } { }
    Box( const V& min, const V& max ) : min{ min }, max{ max } { }
 
    #if MR_HAS_REQUIRES
    // If the compiler supports `requires`, use that instead of `std::enable_if` here.
    // Not (only) because it looks cooler, but because of a bug in our binding generator that makes it choke on it: https://github.com/MeshInspector/mrbind/issues/19
    explicit Box( NoInit ) requires (VectorTraits<V>::supportNoInit) : min{ noInit }, max{ noInit } { }
    explicit Box( NoInit ) requires (!VectorTraits<V>::supportNoInit) { }
    #else
    template <typename VV = V, typename std::enable_if_t<VectorTraits<VV>::supportNoInit, int> = 0>
    explicit Box( NoInit ) : min{ noInit }, max{ noInit } { }
    template <typename VV = V, typename std::enable_if_t<!VectorTraits<VV>::supportNoInit, int> = 0>
    explicit Box( NoInit ) { }
    #endif
 
    // Here `V == U` doesn't seem to cause any issues in the C++ code, but we're still disabling it because it somehow gets emitted
    //   when generating the bindings, and results in duplicate functions in C#.
    template <typename U> MR_REQUIRES_IF_SUPPORTED( !std::is_same_v<V, U> )
    explicit Box( const Box<U> & a ) : min{ a.min }, max{ a.max } { }
 
    static Box fromMinAndSize( const V& min, const V& size ) { return Box{ min, V( min + size ) }; }
 
    bool valid() const
    {
        for ( int i = 0; i < elements; ++i )
            if ( VTraits::getElem( i, min ) > VTraits::getElem( i, max ) )
                return false;
        return true;
    }
 
    V center() const { assert( valid() ); return ( min + max ) / T(2); }
 
    V corner( const Vb& c ) const
    {
        V res;
        for ( int i = 0; i < elements; ++i )
            VTraits::getElem( i, res ) = VTraits::getElem( i, operator[]( VbTraits::getElem( i, c ) ) );
        return res;
    }
 
    static Vb getMinBoxCorner( const V & n )
    {
        Vb res;
        for ( int i = 0; i < elements; ++i )
            VbTraits::getElem( i, res ) = VTraits::getElem( i, n ) < 0;
        return res;
    }
 
    static Vb getMaxBoxCorner( const V & n )
    {
        return getMinBoxCorner( -n );
    }
 
    V size() const { assert( valid() ); return max - min; }
 
    T diagonal() const { return std::sqrt( sqr( size() ) ); }
 
    T volume() const
    {
        assert( valid() );
        T res{ 1 };
        for ( int i = 0; i < elements; ++i )
            res *= VTraits::getElem( i, max ) - VTraits::getElem( i, min );
        return res;
    }
 
    void include( const V & pt )
    {
        for ( int i = 0; i < elements; ++i )
        {
            if ( VTraits::getElem( i, pt ) < VTraits::getElem( i, min ) ) VTraits::getElem( i, min ) = VTraits::getElem( i, pt );
            if ( VTraits::getElem( i, pt ) > VTraits::getElem( i, max ) ) VTraits::getElem( i, max ) = VTraits::getElem( i, pt );
        }
    }
 
    void include( const Box & b )
    {
        for ( int i = 0; i < elements; ++i )
        {
            if ( VTraits::getElem( i, b.min ) < VTraits::getElem( i, min ) ) VTraits::getElem( i, min ) = VTraits::getElem( i, b.min );
            if ( VTraits::getElem( i, b.max ) > VTraits::getElem( i, max ) ) VTraits::getElem( i, max ) = VTraits::getElem( i, b.max );
        }
    }
 
    bool contains( const V & pt ) const
    {
        for ( int i = 0; i < elements; ++i )
            if ( VTraits::getElem( i, min ) > VTraits::getElem( i, pt ) || VTraits::getElem( i, pt ) > VTraits::getElem( i, max ) )
                return false;
        return true;
    }
 
    bool contains( const Box& otherbox ) const
    {
        for ( int i = 0; i < elements; ++i )
            if ( VTraits::getElem( i, min ) > VTraits::getElem( i, otherbox.min ) || VTraits::getElem( i, otherbox.max ) > VTraits::getElem( i, max ) )
                return false;
        return true;
    }
 
    V getBoxClosestPointTo( const V & pt ) const
    {
        assert( valid() );
        V res;
        for ( int i = 0; i < elements; ++i )
            VTraits::getElem( i, res ) = std::clamp( VTraits::getElem( i, pt ), VTraits::getElem( i, min ), VTraits::getElem( i, max ) );
        return res;
    }
 
    bool intersects( const Box & b ) const
    {
        for ( int i = 0; i < elements; ++i )
        {
            if ( VTraits::getElem( i, b.max ) < VTraits::getElem( i, min ) || VTraits::getElem( i, b.min ) > VTraits::getElem( i, max ) )
                return false;
        }
        return true;
    }
 
    Box intersection( const Box & b ) const
    {
        Box res;
        for ( int i = 0; i < elements; ++i )
        {
            VTraits::getElem( i, res.min ) = std::max( VTraits::getElem( i, min ), VTraits::getElem( i, b.min ) );
            VTraits::getElem( i, res.max ) = std::min( VTraits::getElem( i, max ), VTraits::getElem( i, b.max ) );
        }
        return res;
    }
    Box & intersect( const Box & b ) { return *this = intersection( b ); }
 
    T getDistanceSq( const Box & b ) const
    {
        auto ibox = intersection( b );
        T distSq = 0;
        for ( int i = 0; i < elements; ++i )
            if ( VTraits::getElem( i, ibox.min ) > VTraits::getElem( i, ibox.max ) )
                distSq += sqr( VTraits::getElem( i, ibox.min ) - VTraits::getElem( i, ibox.max ) );
        return distSq;
    }
 
    T getDistanceSq( const V & pt ) const
    {
        assert( valid() );
        T res{};
        for ( int i = 0; i < elements; ++i )
        {
            if ( VTraits::getElem( i, pt ) < VTraits::getElem( i, min ) )
                res += sqr( VTraits::getElem( i, pt ) - VTraits::getElem( i, min ) );
            else
            if ( VTraits::getElem( i, pt ) > VTraits::getElem( i, max ) )
                res += sqr( VTraits::getElem( i, pt ) - VTraits::getElem( i, max ) );
        }
        return res;
    }
 
    V getProjection( const V & pt ) const
    {
        assert( valid() );
        if ( !contains( pt ) )
            return getBoxClosestPointTo( pt );
 
        T minDist = std::numeric_limits<T>::max();
        int minDistDim {};
        T minDistPos {};
 
        for ( auto dim = 0; dim < elements; ++dim )
        {
            for ( const auto& border : { min, max } )
            {
                if ( auto dist = std::abs( VTraits::getElem( dim, border ) - VTraits::getElem( dim, pt ) ); dist < minDist )
                {
                    minDist = dist;
                    minDistDim = dim;
                    minDistPos = VTraits::getElem( dim, border );
                }
            }
        }
 
        auto proj = pt;
        VTraits::getElem( minDistDim, proj ) = minDistPos;
        return proj;
    }
 
    Box expanded( const V & expansion ) const
    {
        assert( valid() );
        return Box( min - expansion, max + expansion );
    }
 
    Box insignificantlyExpanded() const
    {
        assert( valid() );
        Box res;
        for ( int i = 0; i < elements; ++i )
        {
            VTraits::getElem( i, res.min ) = std::nextafter( VTraits::getElem( i, min ), std::numeric_limits<T>::lowest() );
            VTraits::getElem( i, res.max ) = std::nextafter( VTraits::getElem( i, max ), std::numeric_limits<T>::max() );
        }
        return res;
    }
 
    bool operator == ( const Box & a ) const
        { return min == a.min && max == a.max;  }
    bool operator != ( const Box & a ) const
        { return !( *this == a ); }
 
    friend std::ostream& operator<<( std::ostream& s, const Box<V>& box )
    {
        return s << box.min << '\n' << box.max;
    }
 
    friend std::istream& operator>>( std::istream& s, Box<V>& box )
    {
        return s >> box.min >> box.max;
    }
};
 
template <typename T>
inline std::array<Vector3<T>, 8> getCorners( const Box<Vector3<T>> & box )
{
    assert( box.valid() );
    return
    {
        Vector3<T>{ box.min.x, box.min.y, box.min.z },
        Vector3<T>{ box.max.x, box.min.y, box.min.z },
        Vector3<T>{ box.min.x, box.max.y, box.min.z },
        Vector3<T>{ box.max.x, box.max.y, box.min.z },
        Vector3<T>{ box.min.x, box.min.y, box.max.z },
        Vector3<T>{ box.max.x, box.min.y, box.max.z },
        Vector3<T>{ box.min.x, box.max.y, box.max.z },
        Vector3<T>{ box.max.x, box.max.y, box.max.z }
    };
}
 
template <typename T>
inline std::array<Vector2<T>, 4> getCorners( const Box<Vector2<T>> & box )
{
    assert( box.valid() );
    return
    {
        Vector2<T>{ box.min.x, box.min.y },
        Vector2<T>{ box.max.x, box.min.y },
        Vector2<T>{ box.min.x, box.max.y },
        Vector2<T>{ box.max.x, box.max.y }
    };
}
 
template <typename V>
MinMax<typename Box<V>::T> getTouchPlanes( const Box<V> & box, const V & n )
{
    auto minCorner = box.getMinBoxCorner( n );
    auto maxCorner = minCorner;
    for ( auto & v : maxCorner )
        v = !v;
    return
    {
        dot( n, box.corner( minCorner ) ),
        dot( n, box.corner( maxCorner ) )
    };
}
 
template <typename V>
inline Box<V> transformed( const Box<V> & box, const AffineXf<V> & xf )
{
    if ( !box.valid() )
        return {};
    Box<V> res;
    for ( const auto & p : getCorners( box ) )
        res.include( xf( p ) );
    return res;
}
template <typename V>
inline Box<V> transformed( const Box<V> & box, const AffineXf<V> * xf )
{
    return xf ? transformed( box, *xf ) : box;
}
 
template <typename V>
inline auto width( const Box<V>& box )
{
    return box.max.x - box.min.x;
}
 
template <typename V>
inline auto height( const Box<V>& box )
{
    return box.max.y - box.min.y;
}
 
template <typename V>
inline auto depth( const Box<V>& box )
{
    return box.max.z - box.min.z;
}
 
template <typename V>
inline auto findSortedBoxDims( const Box<V>& box ) -> typename VectorTraits<V>::template ChangeBaseType<int>
{
    constexpr auto es = Box<V>::elements;
    auto boxDiag = box.max - box.min;
    std::pair<float, int> ps[es];
    for ( int i = 0; i < es; ++i )
        ps[i] = { boxDiag[i], i };
 
    // bubble sort (optimal for small array)
    for ( int i = 0; i + 1 < es; ++i )
        for ( int j = i + 1; j < es; ++j )
            if ( ps[j] < ps[i] )
                std::swap( ps[i], ps[j] );
 
    typename VectorTraits<V>::template ChangeBaseType<int> res( noInit );
    for ( int i = 0; i < es; ++i )
        res[i] = ps[i].second;
    return res;
}
 
template<size_t I, typename V>
constexpr const V& get( const Box<V>& box ) noexcept { return box[int( I )]; }
template<size_t I, typename V>
constexpr       V& get(       Box<V>& box ) noexcept { return box[int( I )]; }
 
 
} // namespace MR
 
namespace std
{
 
template<size_t I, typename V>
struct tuple_element<I, MR::Box<V>> { using type = V; };
 
template <typename V>
struct tuple_size<MR::Box<V>> : integral_constant<size_t, 2> {};
 
} //namespace std