Hi,

I am trying to find an implementation of Oriented Bounding Box. Would be nice if its implemented like AlignedBox (template with Scalar and Dim).
Any one knows one?

Im aware of this post viewtopic.php?f=74&t=111329&p=265713&hilit=oriented+box#p265713 but as far as i can find its never been published.

Im looking methods for intersection and containsPoint tests.

if you can help me a bit on this methods i am willing to do/publish rest of the work If there is no such a implementation.

Thanks a lot!

Now i have this which is probably not the best Eigen way of implementing it. I tried to implement ideas in http://stackoverflow.com/questions/7328424/point-in-obb-oriented-bounding-box-algorithm and http://www.flipcode.com/archives/2D_OBB_Intersection.shtml and i dont know how to apply for N dimensions and maybe Eigen has better routines to implement this?

Code: Select all

template<typename ScalarT_, int DimT_>
   class OrientedBox
   {};

   template<typename ScalarT_>
   class OrientedBox<ScalarT_, 2>
   {
   
   public:

      typedef ScalarT_   Scalar;
      typedef Eigen::AlignedBox<ScalarT_, 2>   AlignedBoxType;
      typedef Eigen::Matrix<ScalarT_, 2, 1, Eigen::DontAlign, 2, 1>   VectorType;

      enum
      {
         Dim      = 2,
         Corners   = 4,
         Axis   = 2,
      };

   public:

      OrientedBox()
         :angle( 0 )
         ,sizes( VectorType::Zero() )
         ,center( VectorType::Zero() )
      {};

      OrientedBox( const AlignedBoxType & alignedBox, const Scalar & angle_ )
         :angle( angle_ )
         ,sizes( alignedBox.sizes() )
         ,center( alignedBox.sizes().array() * 0.5 )
      {
         create();
      };

      OrientedBox( const VectorType & sizes_, const Scalar & angle_ )
         :angle( angle_ )
         ,sizes( sizes_ )
         ,center( sizes_.array() * 0.5 )
      {
         create();
      };

   public:

      bool overlaps( const OrientedBox & other )
      {
         return overlaps1Way( other ) && other.overlaps1Way( *this );
      };

      bool contains( const VectorType & value )
      {
         Scalar newy = sinf(angle) * (value(1) - center(1)) + cosf(angle) * (value(0) - center(0));
         Scalar newx = cosf(angle) * (value(0) - center(0)) - sinf(angle) * (value(1) - center(1));

         return   (newy > center(1) - sizes(1) / 2) && (newy < center(1) + sizes(1) / 2) &&
               (newx > center(0) - sizes(0) / 2) && (newx < center(0) + sizes(0) / 2);
      };

      const VectorType & getSizes() const
      {
         return sizes;
      };

      const VectorType & getCenter() const
      {
         return center;
      };

      const Scalar & getAngle() const
      {
         return angle;
      };

   private:

      inline void create()
      {
         VectorType   xVal( cosf( angle ) * sizes( 0 ) * 0.5f, sinf( angle ) * sizes( 0 ) * 0.5f );
         VectorType   yVal( -sinf( angle ) * sizes( 1 ) * 0.5f, cos( angle ) * sizes( 1 ) * 0.5f );

         corners[0]   = center - xVal - yVal;
         corners[1]   = center + xVal - yVal;
         corners[2]   = center + xVal + yVal;
         corners[3]   = center - xVal + yVal;

         axis[0]      = ( corners[1] - corners[0] );
         axis[1]      = ( corners[3] - corners[0] );

         axis[0].normalize();
         axis[1].normalize();

         origin( 0 )   = corners[0].dot( axis[0] );
         origin( 1 )   = corners[0].dot( axis[1] );
      };

      void overlaps1Way( const OrientedBox & other )
      {
         for (int i = 0; i < 2; ++i )
         {
            Scalar t      = other.corners[0].dot( axis[i] );

            Scalar tMin      = t;
            Scalar tMax      = t;

            for ( int j = 1; j < 4; ++j )
            {
               t         = other.corners[j].dot( axis[i] );

               if( t < tMin )
               {
                  tMin   = t;
               }

               if( t > tMax )
               {
                  tMax   = t;
               }
            }

            if( ( tMin > 1 + origin( i ) ) ||
               ( tMax < origin( i ) ) )
            {
               return false;
            }
         }
         
         return true;
      };

   private:

      Scalar      angle;
      VectorType   sizes;
      VectorType   center;

      VectorType   corners[Corners];
      VectorType   axis[Axis];
      VectorType   origin;
   };


What about implementing it as an aggregate of an AxisAlignedBox and a rotation matrix? You could even add a third template parameter to let the user choose its own representation of rotation with a Matrix<> as default parameter. In 3D, one might typically use a Quaternion to get a more compact representation.

Hi,

Thanks a lot.

Do you mean something like this?

template<typename Scalar, typename RotationMatrix, int Dim>
OrientedBox: public AxisAlignedBox<Scalar, Dim>
{
bool isIntersect( const OrientedBox<Scalar, RotationMatrix, Dim> & other )
bool contains( const Matrix<Scalar, Dim, 1, DontAlign, Dim, 1> & vec )
};

Also how one can implement generic Separating Axis Theorem function to test intersection between two OrientedBox<Scalar, Ndim>? As far as i know in 2d we need to use edge normals but in 3d face normals. Is it good a idea to specialise OrientedBox for 2 and 3 dimension? Im trying to figure this function design. Any tip for this?

I haven't fully tested yet (did a quick one with 2d) but i managed to implement generalized test for intersection and contains methods.

I am trying to follow the optimized version of SAT http://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf

Still not sure if its correct for 3D or not.

Any help/test/suggestion would be appreciated.

Code: Select all

using namespace Eigen;

   template<typename _Scalar, int _Dim, typename _RotationMatrixT>
   class OrientedBox: public AlignedBox<_Scalar, _Dim>
   {

   public:

      typedef _Scalar                                 Scalar;
      typedef _RotationMatrixT                        RotationMatrix;
      typedef AlignedBox<Scalar, _Dim>                  Base;
      typedef Matrix<Scalar, _Dim, 1, DontAlign, _Dim, 1>      VectorType;

      enum
      {
         Dim   = _Dim,
      };

   public:

      template<typename OtherVectorType1, typename OtherVectorType2>
      OrientedBox(   const OtherVectorType1 & _min,
                  const OtherVectorType2 & _max,
                  const RotationMatrix & _rotation )

                  :Base( _min, _max )
                  ,rotation( _rotation )
      {};

      template<typename OtherRotation>
      void setRotation( const OtherRotation & value )
      {
         rotation   = value;
      };

      RotationMatrix getRotation() const
      {
         return rotation;
      };

      bool containsOriented( const VectorType & value ) const
      {
         return   contains( rotation.inverse() * value );
      };

      VectorType cornerOriented( const Base::CornerType & value ) const
      {
         return rotation * corner( value );
      };

      bool intersects( const OrientedBox & other ) const
      {

         // This

         const VectorType minRotatedThis      = rotation * min();
         const VectorType maxRotatedThis      = rotation * max();
         const VectorType centerThis         = ( minRotatedThis + maxRotatedThis ) / 2;

         const VectorType halfSizeThis      = sizes() / 2;

         // Other

         const VectorType minRotatedOther   = other.getRotation() * other.min();
         const VectorType maxRotatedOther   = other.getRotation() * other.max();
         const VectorType centerOther      = ( minRotatedOther + maxRotatedOther ) / 2;

         const VectorType halfSizeOther      = other.sizes() / 2;

         // Center

         const VectorType centersVector      = centerOther - centerThis;      

         // Create Axis Vectors

         VectorType      axisThis[Dim];
         VectorType      axisOther[Dim];

         for( int i = 0; i < Dim; ++i )
         {
            VectorType   cornerThis         = minRotatedThis;
            VectorType   cornerOther         = minRotatedOther;

            cornerThis( i )               = maxRotatedThis( i );
            cornerOther( i )            = maxRotatedOther( i );

            axisThis[ i ]               = ( cornerThis - minRotatedThis ).normalized();
            axisOther[ i ]               = ( cornerOther - minRotatedOther ).normalized();
         }

         // Test This & Other

         for( int i = 0; i < Dim; ++i )
         {
            Scalar   rhsThis      = halfSizeThis( i );
            Scalar   rhsOther   = halfSizeOther( i );

            for( int j = 0; j < Dim; ++j )
            {
               rhsThis         += abs( ( halfSizeOther( j ) * axisOther[ j ] ).dot( axisThis[ i ] ) );
               rhsOther      += abs( ( halfSizeThis( j ) * axisThis[ j ] ).dot( axisOther[ i ] ) );
            }

            if( abs( centersVector.dot( axisThis[ i ] ) ) > rhsThis ||
               abs( centersVector.dot( axisOther[ i ] ) ) > rhsOther
               )
            {
               return false;
            }
         };

         return true;
      };

   private:

      RotationMatrix   rotation;

   };

As far as I learned from SAT docs and tutorials there is no easy way to implement generalized (and simplified) method for testing 2d, 3d. All docs I have found are suggesting different optimisations for each case.

For this reason I went back to implement 2d and 3d in different specializations. Now 2d is tested and working. Im just getting compiler error for containsOriented method. Error is

Code: Select all

orientedbox.h(77): error C2666: 'Eigen::Rotation2D<float>::operator *' : 2 overloads have similar conversions
 could be 'Eigen::Matrix<float,2,1,0,2,1> Eigen::Rotation2D<float>::operator *(const Eigen::Matrix<float,2,1,0,2,1> &) const'
or       'Eigen::Rotation2D<float> Eigen::Rotation2D<float>::operator *(const Eigen::Rotation2D<float> &) const'
or       'Eigen::Transform<float,2,1,0> Eigen::RotationBase<Eigen::Rotation2D<float>,2>::operator *(const Eigen::Translation<float,2> &) const'
or       'Eigen::Matrix<float,2,2,0,2,2> Eigen::RotationBase<Eigen::Rotation2D<float>,2>::operator *(const Eigen::UniformScaling<float> &) const'
or       'Eigen::Transform<float,2,2,0> Eigen::RotationBase<Eigen::Rotation2D<float>,2>::operator *(const Eigen::DiagonalMatrix<float,2,2> &,const Derived &)' [found using argument-dependent lookup]


Current implementation :

Code: Select all

using namespace Eigen;

   template<typename _Scalar, int _Dim, typename _RotationMatrixT>
   class OrientedBox
   {};

   template<typename _Scalar, typename _RotationMatrixT>
   class OrientedBox<_Scalar, 2, _RotationMatrixT>: public AlignedBox<_Scalar, 2>
   {

   public:

      enum
      {
         Dim   = 2,
      };

      typedef _Scalar                                 Scalar;
      typedef _RotationMatrixT                        RotationMatrix;
      typedef AlignedBox<Scalar, Dim>                     Base;
      typedef Matrix<Scalar, Dim, 1, DontAlign, Dim, 1>      VectorType;

   public:

      template<typename OtherVectorType1, typename OtherVectorType2>
      OrientedBox(   const OtherVectorType1 & _min,
                  const OtherVectorType2 & _max,
                  const RotationMatrix & _rotation )

                  :Base( _min, _max )
                  ,rotation( _rotation )
      {};

      template<typename OtherRotation>
      void setRotation( const OtherRotation & value )
      {
         rotation   = value;
      };

      RotationMatrix getRotation() const
      {
         return rotation;
      };

      bool containsOriented( const VectorType & value ) const
      {
         return   contains( rotation.inverse() * value );
      };

      VectorType cornerOriented( const typename Base::CornerType & value ) const
      {
         return rotation * corner( value );
      };

      bool intersects( const OrientedBox & other ) const
      {
         const VectorType centerThis         = ( rotation * min() + rotation * max() ) / 2;
         const VectorType halfSizeThis      = sizes() / 2;

         const VectorType centerOther      = ( other.getRotation() * other.min() + other.getRotation() * other.max() ) / 2;
         const VectorType halfSizeOther      = other.sizes() / 2;

         const VectorType centersVector      = centerOther - centerThis;      

         // Create Axis Vectors

         VectorType      axisThis[Dim];
         VectorType      axisOther[Dim];

         axisThis[0]            = ( cornerOriented( TopRight ) - cornerOriented( TopLeft ) ).normalized();
         axisThis[1]            = ( cornerOriented( BottomLeft ) - cornerOriented( TopLeft ) ).normalized();

         axisOther[0]         = ( other.cornerOriented( TopRight ) - other.cornerOriented( TopLeft ) ).normalized();
         axisOther[1]         = ( other.cornerOriented( BottomLeft ) - other.cornerOriented( TopLeft ) ).normalized();

         // Test This & Other

         for( int i = 0; i < Dim; ++i )
         {
            Scalar   rhsThis      = halfSizeThis( i );
            Scalar   rhsOther   = halfSizeOther( i );

            for( int j = 0; j < Dim; ++j )
            {
               rhsThis         += abs( ( halfSizeOther( j ) * axisOther[ j ] ).dot( axisThis[ i ] ) );
               rhsOther      += abs( ( halfSizeThis( j ) * axisThis[ j ] ).dot( axisOther[ i ] ) );
            }

            if( abs( centersVector.dot( axisThis[ i ] ) ) > rhsThis ||
               abs( centersVector.dot( axisOther[ i ] ) ) > rhsOther
               )
            {
               return false;
            }
         };

         return true;
      };

   private:

      RotationMatrix   rotation;

   };


I managed to test and implement 2d version. Intersection and contains point functions are working. Will be implementing 3d version in the next couple days. I replaced rotations with transforms and now class is called TransformedBox.

Let me know what you think

Edit : Added default constructor

Code: Select all

template<typename _Scalar, int _Dim, typename _Transform>
   class TransformedBox
   {};

   template<typename _Scalar, typename _Transform>
   class TransformedBox<_Scalar, 2, _Transform>
   {

   public:

      enum
      {
         Dim   = 2,
      };

      typedef _Scalar                              Scalar;
      typedef _Transform                           TransformType;
      typedef AlignedBox<Scalar, Dim>                  AlignedBoxType;
      typedef Matrix<Scalar, Dim, 1, DontAlign, Dim, 1>   VectorType;

   public:

TransformedBox()

                  :aligned()
                  ,transform( TransformType::Identity() )
                  ,invTransform( TransformType::Identity() )
      {};

      template<   typename OtherVectorType1,
               typename OtherVectorType2,
               typename OtherTransformType>
      TransformedBox(   const OtherVectorType1 & _min,
                  const OtherVectorType2 & _max,
                  const OtherTransformType & _transform )

                  :aligned( _min, _max )
                  ,transform( _transform )
                  ,invTransform( transform.inverse() )
      {};

      template<typename OtherTransformType>
      TransformedBox( const AlignedBoxType & _alignedBox,
                  const OtherTransformType & _transform )

                  :aligned( _alignedBox )
                  ,transform( _transform )
                  ,invTransform( transform.inverse() )
      {};

      TransformedBox( const AlignedBoxType & _alignedBox )

                  :aligned( _alignedBox )
                  ,transform( TransformType::Identity() )
                  ,invTransform( TransformType::Identity() )
      {};

      template<typename OtherTransform>
      void setTransform( const OtherTransform & value )
      {
         transform      = value;
         invTransform   = transform.inverse();
      };

      template<typename OtherTransformType>
      TransformedBox transformed( const OtherTransformType & _transform )
      {
          return TransformedBox( aligned, _transform * transform );
      };

      TransformType getTransform() const
      {
         return transform;
      };

      const AlignedBoxType & inverse() const
      {
         return aligned;
      };

      AlignedBoxType bounds() const
      {
         VectorType   p1   = corner( AlignedBoxType::TopLeft );
         VectorType   p2   = corner( AlignedBoxType::TopRight );
         VectorType   p3   = corner( AlignedBoxType::BottomLeft );
         VectorType   p4   = corner( AlignedBoxType::BottomRight );

         return AlignedBoxType(   VectorType( p1.array().min( p2.array().min( p3.array().min( p4.array() ) ) ) ),
                           VectorType( p1.array().max( p2.array().max( p3.array().max( p4.array() ) ) ) )
                        );
      };

      bool contains( const VectorType & value ) const
      {
         return aligned.contains( invTransform * (TransformType::VectorType)value );
      };

      VectorType corner( const typename AlignedBoxType::CornerType & value ) const
      {
         return transform * aligned.corner( value );
      };

      bool intersects( const TransformedBox & other ) const
      {
         const VectorType halfSizeThis      = aligned.sizes() / 2;
         const VectorType halfSizeOther      = other.aligned.sizes() / 2;

         const VectorType centerThis         = ( transform * aligned.min() + transform * aligned.max() ) / 2;
         const VectorType centerOther      = ( other.getTransform() * other.aligned.min() + other.getTransform() * other.aligned.max() ) / 2;
         
         const VectorType centersVector      = centerOther - centerThis;      

         // Create Axis Vectors

         VectorType      axisThis[Dim];
         VectorType      axisOther[Dim];

         axisThis[0]                     = ( corner( AlignedBoxType::TopRight ) - corner( AlignedBoxType::TopLeft ) ).normalized();
         axisThis[1]                     = ( corner( AlignedBoxType::BottomLeft ) - corner( AlignedBoxType::TopLeft ) ).normalized();

         axisOther[0]                  = ( other.corner( AlignedBoxType::TopRight ) - other.corner( AlignedBoxType::TopLeft ) ).normalized();
         axisOther[1]                  = ( other.corner( AlignedBoxType::BottomLeft ) - other.corner( AlignedBoxType::TopLeft ) ).normalized();

         // Test This & Other

         for( int i = 0; i < Dim; ++i )
         {
            Scalar   rhsThis      = halfSizeThis( i );
            Scalar   rhsOther   = halfSizeOther( i );

            for( int j = 0; j < Dim; ++j )
            {
               rhsThis         += std::abs( ( halfSizeOther( j ) * axisOther[ j ] ).dot( axisThis[ i ] ) );
               rhsOther      += std::abs( ( halfSizeThis( j ) * axisThis[ j ] ).dot( axisOther[ i ] ) );
            }

            if( std::abs( centersVector.dot( axisThis[ i ] ) ) > rhsThis ||
               std::abs( centersVector.dot( axisOther[ i ] ) ) > rhsOther
               )
            {
               return false;
            }
         };

         return true;
      };

   private:

      AlignedBoxType   aligned;
      TransformType   transform;
      TransformType   invTransform;
   };