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_Macro.hxx>
  22 #include <Standard_Dump.hxx>
  23 #include <Standard_ShortReal.hxx>
  24
  25 #include <limits>
  26
  27 //! Base class for BVH_Box (CRTP idiom is used).
  28 //! @tparam T             Numeric data type
  29 //! @tparam N             Vector dimension
  30 //! @tparam TheDerivedBox Template of derived class that defined axis aligned bounding box.
  31 template <class T, int N, template <class /*T*/, int /*N*/> class TheDerivedBox>
  32 class BVH_BaseBox {};
  33
  34 // forward declaration
  35 template <class T, int N> class BVH_Box;
  36
  37 //! Partial template specialization for BVH_Box when N = 3.
  38 template <class T>
  39 class BVH_BaseBox<T, 3, BVH_Box>
  40 {
  41 public:
  42
  43   //! Transforms this box with given transformation.
  44   void Transform (const NCollection_Mat4<T>& theTransform)
  45   {
  46     if (theTransform.IsIdentity())
  47     {
  48       return;
  49     }
  50
  51     BVH_Box<T, 3> *aThis = static_cast<BVH_Box<T, 3>*>(this);
  52     if (!aThis->IsValid())
  53     {
  54       return;
  55     }
  56
  57     BVH_Box<T, 3> aBox = Transformed (theTransform);
  58
  59     aThis->CornerMin() = aBox.CornerMin();
  60     aThis->CornerMax() = aBox.CornerMax();
  61   }
  62
  63   //! Returns a box which is the result of applying the
  64   //! given transformation to this box.
  65   BVH_Box<T, 3> Transformed (const NCollection_Mat4<T>& theTransform) const
  66   {
  67     BVH_Box<T, 3> aResultBox;
  68
  69     if (theTransform.IsIdentity())
  70     {
  71       return aResultBox;
  72     }
  73
  74     const BVH_Box<T, 3> *aThis = static_cast<const BVH_Box<T, 3>*>(this);
  75     if (!aThis->IsValid())
  76     {
  77       return aResultBox;
  78     }
  79
  80     for (size_t aX = 0; aX <= 1; ++aX)
  81     {
  82       for (size_t aY = 0; aY <= 1; ++aY)
  83       {
  84         for (size_t aZ = 0; aZ <= 1; ++aZ)
  85         {
  86           typename BVH::VectorType<T, 4>::Type aPnt =
  87             theTransform * typename BVH::VectorType<T, 4>::Type (aX ? aThis->CornerMax().x() : aThis->CornerMin().x(),
  88                                                                  aY ? aThis->CornerMax().y() : aThis->CornerMin().y(),
  89                                                                  aZ ? aThis->CornerMax().z() : aThis->CornerMin().z(),
  90                                                                  static_cast<T> (1.0));
  91
  92           aResultBox.Add (aPnt.xyz());
  93         }
  94       }
  95     }
  96     return aResultBox;
  97   }
  98 };
  99
 100 //! Defines axis aligned bounding box (AABB) based on BVH vectors.
 101 //! \tparam T Numeric data type
 102 //! \tparam N Vector dimension
 103 template<class T, int N>
 104 class BVH_Box : public BVH_BaseBox<T, N, BVH_Box>
 105 {
 106 public:
 107
 108   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
 109
 110 public:
 111
 112   //! Creates uninitialized bounding box.
 113   BVH_Box() : myIsInited (Standard_False) {}
 114
 115   //! Creates bounding box of given point.
 116   BVH_Box (const BVH_VecNt& thePoint)
 117   : myMinPoint (thePoint),
 118     myMaxPoint (thePoint),
 119     myIsInited (Standard_True) {}
 120
 121   //! Creates bounding box from corner points.
 122   BVH_Box (const BVH_VecNt& theMinPoint,
 123            const BVH_VecNt& theMaxPoint)
 124   : myMinPoint (theMinPoint),
 125     myMaxPoint (theMaxPoint),
 126     myIsInited (Standard_True) {}
 127
 128 public:
 129
 130   //! Clears bounding box.
 131   void Clear() { myIsInited = Standard_False; }
 132
 133   //! Is bounding box valid?
 134   Standard_Boolean IsValid() const { return myIsInited; }
 135
 136   //! Appends new point to the bounding box.
 137   void Add (const BVH_VecNt& thePoint)
 138   {
 139     if (!myIsInited)
 140     {
 141       myMinPoint = thePoint;
 142       myMaxPoint = thePoint;
 143       myIsInited = Standard_True;
 144     }
 145     else
 146     {
 147       myMinPoint = myMinPoint.cwiseMin (thePoint);
 148       myMaxPoint = myMaxPoint.cwiseMax (thePoint);
 149     }
 150   }
 151
 152   //! Combines bounding box with another one.
 153   void Combine (const BVH_Box& theBox);
 154
 155   //! Returns minimum point of bounding box.
 156   const BVH_VecNt& CornerMin() const { return myMinPoint; }
 157
 158   //! Returns maximum point of bounding box.
 159   const BVH_VecNt& CornerMax() const { return myMaxPoint; }
 160
 161   //! Returns minimum point of bounding box.
 162   BVH_VecNt& CornerMin() { return myMinPoint; }
 163
 164   //! Returns maximum point of bounding box.
 165   BVH_VecNt& CornerMax() { return myMaxPoint; }
 166
 167   //! Returns surface area of bounding box.
 168   //! If the box is degenerated into line, returns the perimeter instead.
 169   T Area() const;
 170
 171   //! Returns diagonal of bounding box.
 172   BVH_VecNt Size() const { return myMaxPoint - myMinPoint; }
 173
 174   //! Returns center of bounding box.
 175   BVH_VecNt Center() const { return (myMinPoint + myMaxPoint) * static_cast<T> (0.5); }
 176
 177   //! Returns center of bounding box along the given axis.
 178   T Center (const Standard_Integer theAxis) const;
 179
 180   //! Dumps the content of me into the stream
 181   void DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth = -1) const
 182   {
 183     (void)theDepth;
 184     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myIsInited)
 185
 186     int n = Min (N, 3);
 187     if (n == 1)
 188     {
 189       OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMinPoint[0])
 190       OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMinPoint[0])
 191     }
 192     if (n == 2)
 193     {
 194       OCCT_DUMP_FIELD_VALUES_NUMERICAL (theOStream, "MinPoint", n, myMinPoint[0], myMinPoint[1])
 195       OCCT_DUMP_FIELD_VALUES_NUMERICAL (theOStream, "MaxPoint", n, myMaxPoint[0], myMaxPoint[1])
 196     }
 197     if (n == 3)
 198     {
 199       OCCT_DUMP_FIELD_VALUES_NUMERICAL (theOStream, "MinPoint", n, myMinPoint[0], myMinPoint[1], myMinPoint[2])
 200       OCCT_DUMP_FIELD_VALUES_NUMERICAL (theOStream, "MaxPoint", n, myMaxPoint[0], myMaxPoint[1], myMaxPoint[2])
 201     }
 202   }
 203
 204 public:
 205
 206   //! Checks if the Box is out of the other box.
 207   Standard_Boolean IsOut (const BVH_Box<T, N>& theOther) const
 208   {
 209     if (!theOther.IsValid())
 210       return Standard_True;
 211
 212     return IsOut (theOther.myMinPoint, theOther.myMaxPoint);
 213   }
 214
 215   //! Checks if the Box is out of the other box defined by two points.
 216   Standard_Boolean IsOut (const BVH_VecNt& theMinPoint,
 217                           const BVH_VecNt& theMaxPoint) const
 218   {
 219     if (!IsValid())
 220       return Standard_True;
 221
 222     int n = Min (N, 3);
 223     for (int i = 0; i < n; ++i)
 224     {
 225       if (myMinPoint[i] > theMaxPoint[i] ||
 226           myMaxPoint[i] < theMinPoint[i])
 227         return Standard_True;
 228     }
 229     return Standard_False;
 230   }
 231
 232   //! Checks if the Box fully contains the other box.
 233   Standard_Boolean Contains (const BVH_Box<T, N>& theOther,
 234                              Standard_Boolean& hasOverlap) const
 235   {
 236     hasOverlap = Standard_False;
 237     if (!theOther.IsValid())
 238       return Standard_False;
 239
 240     return Contains (theOther.myMinPoint, theOther.myMaxPoint, hasOverlap);
 241   }
 242
 243   //! Checks if the Box is fully contains the other box.
 244   Standard_Boolean Contains (const BVH_VecNt& theMinPoint,
 245                              const BVH_VecNt& theMaxPoint,
 246                              Standard_Boolean& hasOverlap) const
 247   {
 248     hasOverlap = Standard_False;
 249     if (!IsValid())
 250       return Standard_False;
 251
 252     Standard_Boolean isInside = Standard_True;
 253
 254     int n = Min (N, 3);
 255     for (int i = 0; i < n; ++i)
 256     {
 257       hasOverlap = (myMinPoint[i] <= theMaxPoint[i] &&
 258                     myMaxPoint[i] >= theMinPoint[i]);
 259       if (!hasOverlap)
 260         return Standard_False;
 261
 262       isInside = isInside && (myMinPoint[i] <= theMinPoint[i] &&
 263                               myMaxPoint[i] >= theMaxPoint[i]);
 264     }
 265     return isInside;
 266   }
 267
 268   //! Checks if the Point is out of the box.
 269   Standard_Boolean IsOut (const BVH_VecNt& thePoint) const
 270   {
 271     if (!IsValid())
 272       return Standard_True;
 273
 274     int n = Min (N, 3);
 275     for (int i = 0; i < n; ++i)
 276     {
 277       if (thePoint[i] < myMinPoint[i] ||
 278           thePoint[i] > myMaxPoint[i])
 279         return Standard_True;
 280     }
 281     return Standard_False;
 282   }
 283
 284
 285 protected:
 286
 287   BVH_VecNt        myMinPoint; //!< Minimum point of bounding box
 288   BVH_VecNt        myMaxPoint; //!< Maximum point of bounding box
 289   Standard_Boolean myIsInited; //!< Is bounding box initialized?
 290
 291 };
 292
 293 namespace BVH
 294 {
 295   //! Tool class for calculating box center along the given axis.
 296   //! \tparam T Numeric data type
 297   //! \tparam N Vector dimension
 298   template<class T, int N>
 299   struct CenterAxis
 300   {
 301     // Not implemented
 302   };
 303
 304   template<class T>
 305   struct CenterAxis<T, 2>
 306   {
 307     static T Center (const BVH_Box<T, 2>& theBox, const Standard_Integer theAxis)
 308     {
 309       if (theAxis == 0)
 310       {
 311         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 312       }
 313       else if (theAxis == 1)
 314       {
 315         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 316       }
 317       return static_cast<T> (0.0);
 318     }
 319   };
 320
 321   template<class T>
 322   struct CenterAxis<T, 3>
 323   {
 324     static T Center (const BVH_Box<T, 3>& theBox, const Standard_Integer theAxis)
 325     {
 326       if (theAxis == 0)
 327       {
 328         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 329       }
 330       else if (theAxis == 1)
 331       {
 332         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 333       }
 334       else if (theAxis == 2)
 335       {
 336         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
 337       }
 338       return static_cast<T> (0.0);
 339     }
 340   };
 341
 342   template<class T>
 343   struct CenterAxis<T, 4>
 344   {
 345     static T Center (const BVH_Box<T, 4>& theBox, const Standard_Integer theAxis)
 346     {
 347       if (theAxis == 0)
 348       {
 349         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
 350       }
 351       else if (theAxis == 1)
 352       {
 353         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
 354       }
 355       else if (theAxis == 2)
 356       {
 357         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
 358       }
 359       return static_cast<T> (0.0);
 360     }
 361   };
 362
 363   //! Tool class for calculating surface area of the box.
 364   //! \tparam T Numeric data type
 365   //! \tparam N Vector dimension
 366   template<class T, int N>
 367   struct SurfaceCalculator
 368   {
 369     // Not implemented
 370   };
 371
 372   template<class T>
 373   struct SurfaceCalculator<T, 2>
 374   {
 375     static T Area (const typename BVH_Box<T, 2>::BVH_VecNt& theSize)
 376     {
 377       const T anArea = theSize.x() * theSize.y();
 378
 379       if (anArea < std::numeric_limits<T>::epsilon())
 380       {
 381         return theSize.x() + theSize.y();
 382       }
 383
 384       return anArea;
 385     }
 386   };
 387
 388   template<class T>
 389   struct SurfaceCalculator<T, 3>
 390   {
 391     static T Area (const typename BVH_Box<T, 3>::BVH_VecNt& theSize)
 392     {
 393       const T anArea = ( theSize.x() * theSize.y() +
 394                          theSize.x() * theSize.z() +
 395                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
 396
 397       if (anArea < std::numeric_limits<T>::epsilon())
 398       {
 399         return theSize.x() +
 400                theSize.y() +
 401                theSize.z();
 402       }
 403
 404       return anArea;
 405     }
 406   };
 407
 408   template<class T>
 409   struct SurfaceCalculator<T, 4>
 410   {
 411     static T Area (const typename BVH_Box<T, 4>::BVH_VecNt& theSize)
 412     {
 413       const T anArea = ( theSize.x() * theSize.y() +
 414                          theSize.x() * theSize.z() +
 415                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
 416
 417       if (anArea < std::numeric_limits<T>::epsilon())
 418       {
 419         return theSize.x() +
 420                theSize.y() +
 421                theSize.z();
 422       }
 423
 424       return anArea;
 425     }
 426   };
 427
 428   //! Tool class for calculate component-wise vector minimum
 429   //! and maximum (optimized version).
 430   //! \tparam T Numeric data type
 431   //! \tparam N Vector dimension
 432   template<class T, int N>
 433   struct BoxMinMax
 434   {
 435     typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
 436
 437     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 438     {
 439       theVec1.x() = Min (theVec1.x(), theVec2.x());
 440       theVec1.y() = Min (theVec1.y(), theVec2.y());
 441       theVec1.z() = Min (theVec1.z(), theVec2.z());
 442     }
 443
 444     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 445     {
 446       theVec1.x() = Max (theVec1.x(), theVec2.x());
 447       theVec1.y() = Max (theVec1.y(), theVec2.y());
 448       theVec1.z() = Max (theVec1.z(), theVec2.z());
 449     }
 450   };
 451
 452   template<class T>
 453   struct BoxMinMax<T, 2>
 454   {
 455     typedef typename BVH::VectorType<T, 2>::Type BVH_VecNt;
 456
 457     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 458     {
 459       theVec1.x() = Min (theVec1.x(), theVec2.x());
 460       theVec1.y() = Min (theVec1.y(), theVec2.y());
 461     }
 462
 463     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
 464     {
 465       theVec1.x() = Max (theVec1.x(), theVec2.x());
 466       theVec1.y() = Max (theVec1.y(), theVec2.y());
 467     }
 468   };
 469 }
 470
 471 // =======================================================================
 472 // function : Combine
 473 // purpose  :
 474 // =======================================================================
 475 template<class T, int N>
 476 void BVH_Box<T, N>::Combine (const BVH_Box& theBox)
 477 {
 478   if (theBox.myIsInited)
 479   {
 480     if (!myIsInited)
 481     {
 482       myMinPoint = theBox.myMinPoint;
 483       myMaxPoint = theBox.myMaxPoint;
 484       myIsInited = Standard_True;
 485     }
 486     else
 487     {
 488       BVH::BoxMinMax<T, N>::CwiseMin (myMinPoint, theBox.myMinPoint);
 489       BVH::BoxMinMax<T, N>::CwiseMax (myMaxPoint, theBox.myMaxPoint);
 490     }
 491   }
 492 }
 493
 494 // =======================================================================
 495 // function : Area
 496 // purpose  :
 497 // =======================================================================
 498 template<class T, int N>
 499 T BVH_Box<T, N>::Area() const
 500 {
 501   return !myIsInited ? static_cast<T> (0.0) : BVH::SurfaceCalculator<T, N>::Area (myMaxPoint - myMinPoint);
 502 }
 503
 504 // =======================================================================
 505 // function : Center
 506 // purpose  :
 507 // =======================================================================
 508 template<class T, int N>
 509 T BVH_Box<T, N>::Center (const Standard_Integer theAxis) const
 510 {
 511   return BVH::CenterAxis<T, N>::Center (*this, theAxis);
 512 }
 513
 514 #endif // _BVH_Box_Header