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