src/BVH/BVH_Box.hxx

   1 // Created on: 2013-12-20
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef _BVH_Box_Header
  17 #define _BVH_Box_Header
  18
  19 #include <BVH_Constants.hxx>
  20 #include <BVH_Types.hxx>
  21 #include <Standard_ShortReal.hxx>
  22 #include <Standard_Dump.hxx>
  23
  24 #include <limits>
  25
  26 //! Defines axis aligned bounding box (AABB) based on BVH vectors.
  27 //! \tparam T Numeric data type
  28 //! \tparam N Vector dimension
  29 template<class T, int N>
  30 class BVH_Box
  31 {
  32 public:
  33
  34   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
  35
  36 public:
  37
  38   //! Creates uninitialized bounding box.
  39   BVH_Box() : myIsInited (Standard_False) {}
  40
  41   //! Creates bounding box of given point.
  42   BVH_Box (const BVH_VecNt& thePoint)
  43   : myMinPoint (thePoint),
  44     myMaxPoint (thePoint),
  45     myIsInited (Standard_True) {}
  46
  47   //! Creates copy of another bounding box.
  48   BVH_Box (const BVH_Box& theBox)
  49   : myMinPoint (theBox.myMinPoint),
  50     myMaxPoint (theBox.myMaxPoint),
  51     myIsInited (theBox.myIsInited) {}
  52
  53   //! Creates bounding box from corner points.
  54   BVH_Box (const BVH_VecNt& theMinPoint,
  55            const BVH_VecNt& theMaxPoint)
  56   : myMinPoint (theMinPoint),
  57     myMaxPoint (theMaxPoint),
  58     myIsInited (Standard_True) {}
  59
  60 public:
  61
  62   //! Clears bounding box.
  63   void Clear() { myIsInited = Standard_False; }
  64
  65   //! Is bounding box valid?
  66   Standard_Boolean IsValid() const { return myIsInited; }
  67
  68   //! Appends new point to the bounding box.
  69   void Add (const BVH_VecNt& thePoint)
  70   {
  71     if (!myIsInited)
  72     {
  73       myMinPoint = thePoint;
  74       myMaxPoint = thePoint;
  75       myIsInited = Standard_True;
  76     }
  77     else
  78     {
  79       myMinPoint = myMinPoint.cwiseMin (thePoint);
  80       myMaxPoint = myMaxPoint.cwiseMax (thePoint);
  81     }
  82   }
  83
  84   //! Combines bounding box with another one.
  85   void Combine (const BVH_Box& theBox);
  86
  87   //! Returns minimum point of bounding box.
  88   const BVH_VecNt& CornerMin() const { return myMinPoint; }
  89
  90   //! Returns maximum point of bounding box.
  91   const BVH_VecNt& CornerMax() const { return myMaxPoint; }
  92
  93   //! Returns minimum point of bounding box.
  94   BVH_VecNt& CornerMin() { return myMinPoint; }
  95
  96   //! Returns maximum point of bounding box.
  97   BVH_VecNt& CornerMax() { return myMaxPoint; }
  98
  99   //! Returns surface area of bounding box.
 100   //! If the box is degenerated into line, returns the perimeter instead.
 101   T Area() const;
 102
 103   //! Returns diagonal of bounding box.
 104   BVH_VecNt Size() const { return myMaxPoint - myMinPoint; }
 105
 106   //! Returns center of bounding box.
 107   BVH_VecNt Center() const { return (myMinPoint + myMaxPoint) * static_cast<T> (0.5); }
 108
 109   //! Returns center of bounding box along the given axis.
 110   T Center (const Standard_Integer theAxis) const;
 111
 112   //! Dumps the content of me into the stream
 113   void DumpJson (Standard_OStream& theOStream, const Standard_Integer theDepth = -1) const
 114   {
 115     (void)theDepth;
 116     DUMP_CLASS_BEGIN (theOStream, BVH_Box);
 117     DUMP_FIELD_VALUE_NUMERICAL (theOStream, IsValid());
 118   }
 119
 120 public:
 121
 122   //! Checks if the Box is out of the other box.
 123   Standard_Boolean IsOut (const BVH_Box<T, N>& theOther) const
 124   {
 125     if (!theOther.IsValid())
 126       return Standard_True;
 127
 128     return IsOut (theOther.myMinPoint, theOther.myMaxPoint);
 129   }
 130
 131   //! Checks if the Box is out of the other box defined by two points.
 132   Standard_Boolean IsOut (const BVH_VecNt& theMinPoint,
 133                           const BVH_VecNt& theMaxPoint) const
 134   {
 135     if (!IsValid())
 136       return Standard_True;
 137
 138     int n = Min (N, 3);
 139     for (int i = 0; i < n; ++i)
 140     {
 141       if (myMinPoint[i] > theMaxPoint[i] ||
 142           myMaxPoint[i] < theMinPoint[i])
 143         return Standard_True;
 144     }
 145     return Standard_False;
 146   }
 147
 148   //! Checks if the Box fully contains the other box.
 149   Standard_Boolean Contains (const BVH_Box<T, N>& theOther,
 150                              Standard_Boolean& hasOverlap) const
 151   {
 152     hasOverlap = Standard_False;
 153     if (!theOther.IsValid())
 154       return Standard_False;
 155
 156     return Contains (theOther.myMinPoint, theOther.myMaxPoint, hasOverlap);
 157   }
 158
 159   //! Checks if the Box is fully contains the other box.
 160   Standard_Boolean Contains (const BVH_VecNt& theMinPoint,
 161                              const BVH_VecNt& theMaxPoint,
 162                              Standard_Boolean& hasOverlap) const
 163   {
 164     hasOverlap = Standard_False;
 165     if (!IsValid())
 166       return Standard_False;
 167
 168     Standard_Boolean isInside = Standard_True;
 169
 170     int n = Min (N, 3);
 171     for (int i = 0; i < n; ++i)
 172     {
 173       hasOverlap = (myMinPoint[i] <= theMaxPoint[i] &&
 174                     myMaxPoint[i] >= theMinPoint[i]);
 175       if (!hasOverlap)
 176         return Standard_False;
 177
 178       isInside = isInside && (myMinPoint[i] <= theMinPoint[i] &&
 179                               myMaxPoint[i] >= theMaxPoint[i]);
 180     }
 181     return isInside;
 182   }
 183
 184   //! Checks if the Point is out of the box.
 185   Standard_Boolean IsOut (const BVH_VecNt& thePoint) const
 186   {
 187     if (!IsValid())
 188       return Standard_True;
 189
 190     int n = Min (N, 3);
 191     for (int i = 0; i < n; ++i)
 192     {
 193       if (thePoint[i] < myMinPoint[i] ||
 194           thePoint[i] > myMaxPoint[i])
 195         return Standard_True;
 196     }
 197     return Standard_False;
 198   }
 199
 200
 201 protected:
 202
 203   BVH_VecNt        myMinPoint; //!< Minimum point of bounding box
 204   BVH_VecNt        myMaxPoint; //!< Maximum point of bounding box
 205   Standard_Boolean myIsInited; //!< Is bounding box initialized?
 206
 207 };
 208
 209 namespace BVH
 210 {
 211   //! Tool class for calculating box center along the given axis.
 212   //! \tparam T Numeric data type
 213   //! \tparam N Vector dimension
 214   template<class T, int N>
 215   struct CenterAxis
 216   {
 217     // Not implemented
 218   };
 219
 220   template<class T>
 221   struct CenterAxis<T, 2>
 222   {
 223     static T Center (const BVH_Box<T, 2>& theBox, const Standard_Integer theAxis)
 224     {
 225       if (theAxis == 0)
 226       {
 227         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 228       }
 229       else if (theAxis == 1)
 230       {
 231         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 232       }
 233       return static_cast<T> (0.0);
 234     }
 235   };
 236
 237   template<class T>
 238   struct CenterAxis<T, 3>
 239   {
 240     static T Center (const BVH_Box<T, 3>& theBox, const Standard_Integer theAxis)
 241     {
 242       if (theAxis == 0)
 243       {
 244         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 245       }
 246       else if (theAxis == 1)
 247       {
 248         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 249       }
 250       else if (theAxis == 2)
 251       {
 252         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
 253       }
 254       return static_cast<T> (0.0);
 255     }
 256   };
 257
 258   template<class T>
 259   struct CenterAxis<T, 4>
 260   {
 261     static T Center (const BVH_Box<T, 4>& theBox, const Standard_Integer theAxis)
 262     {
 263       if (theAxis == 0)
 264       {
 265         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 266       }
 267       else if (theAxis == 1)
 268       {
 269         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 270       }
 271       else if (theAxis == 2)
 272       {
 273         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
 274       }
 275       return static_cast<T> (0.0);
 276     }
 277   };
 278
 279   //! Tool class for calculating surface area of the box.
 280   //! \tparam T Numeric data type
 281   //! \tparam N Vector dimension
 282   template<class T, int N>
 283   struct SurfaceCalculator
 284   {
 285     // Not implemented
 286   };
 287
 288   template<class T>
 289   struct SurfaceCalculator<T, 2>
 290   {
 291     static T Area (const typename BVH_Box<T, 2>::BVH_VecNt& theSize)
 292     {
 293       const T anArea = theSize.x() * theSize.y();
 294
 295       if (anArea < std::numeric_limits<T>::epsilon())
 296       {
 297         return theSize.x() + theSize.y();
 298       }
 299
 300       return anArea;
 301     }
 302   };
 303
 304   template<class T>
 305   struct SurfaceCalculator<T, 3>
 306   {
 307     static T Area (const typename BVH_Box<T, 3>::BVH_VecNt& theSize)
 308     {
 309       const T anArea = ( theSize.x() * theSize.y() +
 310                          theSize.x() * theSize.z() +
 311                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
 312
 313       if (anArea < std::numeric_limits<T>::epsilon())
 314       {
 315         return theSize.x() +
 316                theSize.y() +
 317                theSize.z();
 318       }
 319
 320       return anArea;
 321     }
 322   };
 323
 324   template<class T>
 325   struct SurfaceCalculator<T, 4>
 326   {
 327     static T Area (const typename BVH_Box<T, 4>::BVH_VecNt& theSize)
 328     {
 329       const T anArea = ( theSize.x() * theSize.y() +
 330                          theSize.x() * theSize.z() +
 331                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
 332
 333       if (anArea < std::numeric_limits<T>::epsilon())
 334       {
 335         return theSize.x() +
 336                theSize.y() +
 337                theSize.z();
 338       }
 339
 340       return anArea;
 341     }
 342   };
 343
 344   //! Tool class for calculate component-wise vector minimum
 345   //! and maximum (optimized version).
 346   //! \tparam T Numeric data type
 347   //! \tparam N Vector dimension
 348   template<class T, int N>
 349   struct BoxMinMax
 350   {
 351     typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
 352
 353     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 354     {
 355       theVec1.x() = Min (theVec1.x(), theVec2.x());
 356       theVec1.y() = Min (theVec1.y(), theVec2.y());
 357       theVec1.z() = Min (theVec1.z(), theVec2.z());
 358     }
 359
 360     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 361     {
 362       theVec1.x() = Max (theVec1.x(), theVec2.x());
 363       theVec1.y() = Max (theVec1.y(), theVec2.y());
 364       theVec1.z() = Max (theVec1.z(), theVec2.z());
 365     }
 366   };
 367
 368   template<class T>
 369   struct BoxMinMax<T, 2>
 370   {
 371     typedef typename BVH::VectorType<T, 2>::Type BVH_VecNt;
 372
 373     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 374     {
 375       theVec1.x() = Min (theVec1.x(), theVec2.x());
 376       theVec1.y() = Min (theVec1.y(), theVec2.y());
 377     }
 378
 379     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 380     {
 381       theVec1.x() = Max (theVec1.x(), theVec2.x());
 382       theVec1.y() = Max (theVec1.y(), theVec2.y());
 383     }
 384   };
 385 }
 386
 387 // =======================================================================
 388 // function : Combine
 389 // purpose  :
 390 // =======================================================================
 391 template<class T, int N>
 392 void BVH_Box<T, N>::Combine (const BVH_Box& theBox)
 393 {
 394   if (theBox.myIsInited)
 395   {
 396     if (!myIsInited)
 397     {
 398       myMinPoint = theBox.myMinPoint;
 399       myMaxPoint = theBox.myMaxPoint;
 400       myIsInited = Standard_True;
 401     }
 402     else
 403     {
 404       BVH::BoxMinMax<T, N>::CwiseMin (myMinPoint, theBox.myMinPoint);
 405       BVH::BoxMinMax<T, N>::CwiseMax (myMaxPoint, theBox.myMaxPoint);
 406     }
 407   }
 408 }
 409
 410 // =======================================================================
 411 // function : Area
 412 // purpose  :
 413 // =======================================================================
 414 template<class T, int N>
 415 T BVH_Box<T, N>::Area() const
 416 {
 417   return !myIsInited ? static_cast<T> (0.0) : BVH::SurfaceCalculator<T, N>::Area (myMaxPoint - myMinPoint);
 418 }
 419
 420 // =======================================================================
 421 // function : Center
 422 // purpose  :
 423 // =======================================================================
 424 template<class T, int N>
 425 T BVH_Box<T, N>::Center (const Standard_Integer theAxis) const
 426 {
 427   return BVH::CenterAxis<T, N>::Center (*this, theAxis);
 428 }
 429
 430 #endif // _BVH_Box_Header