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_HeaderFile
17 #define BVH_Box_HeaderFile
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.
Transform(const NCollection_Mat4<T> & theTransform)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.
Transformed(const NCollection_Mat4<T> & theTransform) const65   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.
BVH_Box()113   BVH_Box() : myIsInited (Standard_False) {}
114 
115   //! Creates bounding box of given point.
BVH_Box(const BVH_VecNt & thePoint)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.
BVH_Box(const BVH_VecNt & theMinPoint,const BVH_VecNt & theMaxPoint)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.
Clear()131   void Clear() { myIsInited = Standard_False; }
132 
133   //! Is bounding box valid?
IsValid() const134   Standard_Boolean IsValid() const { return myIsInited; }
135 
136   //! Appends new point to the bounding box.
Add(const BVH_VecNt & thePoint)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.
CornerMin() const156   const BVH_VecNt& CornerMin() const { return myMinPoint; }
157 
158   //! Returns maximum point of bounding box.
CornerMax() const159   const BVH_VecNt& CornerMax() const { return myMaxPoint; }
160 
161   //! Returns minimum point of bounding box.
CornerMin()162   BVH_VecNt& CornerMin() { return myMinPoint; }
163 
164   //! Returns maximum point of bounding box.
CornerMax()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.
Size() const172   BVH_VecNt Size() const { return myMaxPoint - myMinPoint; }
173 
174   //! Returns center of bounding box.
Center() const175   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
DumpJson(Standard_OStream & theOStream,Standard_Integer theDepth=-1) const181   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     else 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     else 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   //! Inits the content of me from the stream
InitFromJson(const Standard_SStream & theSStream,Standard_Integer & theStreamPos)205   Standard_Boolean InitFromJson (const Standard_SStream& theSStream, Standard_Integer& theStreamPos)
206   {
207     Standard_Integer aPos = theStreamPos;
208 
209     Standard_Integer anIsInited = 0;
210     TCollection_AsciiString aStreamStr = Standard_Dump::Text (theSStream);
211 
212     OCCT_INIT_FIELD_VALUE_INTEGER (aStreamStr, aPos, anIsInited);
213     myIsInited = anIsInited != 0;
214 
215     int n = Min (N, 3);
216     if (n == 1)
217     {
218       Standard_Real aValue;
219       OCCT_INIT_FIELD_VALUE_REAL (aStreamStr, aPos, aValue);
220       myMinPoint[0] = (T)aValue;
221     }
222     else if (n == 2)
223     {
224       Standard_Real aValue1, aValue2;
225       OCCT_INIT_VECTOR_CLASS (aStreamStr, "MinPoint", aPos, n, &aValue1, &aValue2);
226       myMinPoint[0] = (T)aValue1;
227       myMinPoint[1] = (T)aValue2;
228 
229       OCCT_INIT_VECTOR_CLASS (aStreamStr, "MaxPoint", aPos, n, &aValue1, &aValue2);
230       myMaxPoint[0] = (T)aValue1;
231       myMaxPoint[1] = (T)aValue2;
232     }
233     else if (n == 3)
234     {
235       Standard_Real aValue1, aValue2, aValue3;
236       OCCT_INIT_VECTOR_CLASS (aStreamStr, "MinPoint", aPos, n, &aValue1, &aValue2, &aValue3);
237       myMinPoint[0] = (T)aValue1;
238       myMinPoint[1] = (T)aValue2;
239       myMinPoint[2] = (T)aValue3;
240 
241       OCCT_INIT_VECTOR_CLASS (aStreamStr, "MaxPoint", aPos, n, &aValue1, &aValue2, &aValue3);
242       myMaxPoint[0] = (T)aValue1;
243       myMaxPoint[1] = (T)aValue2;
244       myMaxPoint[2] = (T)aValue3;
245     }
246 
247     theStreamPos = aPos;
248     return Standard_True;
249   }
250 
251 public:
252 
253   //! Checks if the Box is out of the other box.
IsOut(const BVH_Box<T,N> & theOther) const254   Standard_Boolean IsOut (const BVH_Box<T, N>& theOther) const
255   {
256     if (!theOther.IsValid())
257       return Standard_True;
258 
259     return IsOut (theOther.myMinPoint, theOther.myMaxPoint);
260   }
261 
262   //! Checks if the Box is out of the other box defined by two points.
IsOut(const BVH_VecNt & theMinPoint,const BVH_VecNt & theMaxPoint) const263   Standard_Boolean IsOut (const BVH_VecNt& theMinPoint,
264                           const BVH_VecNt& theMaxPoint) const
265   {
266     if (!IsValid())
267       return Standard_True;
268 
269     int n = Min (N, 3);
270     for (int i = 0; i < n; ++i)
271     {
272       if (myMinPoint[i] > theMaxPoint[i] ||
273           myMaxPoint[i] < theMinPoint[i])
274         return Standard_True;
275     }
276     return Standard_False;
277   }
278 
279   //! Checks if the Box fully contains the other box.
Contains(const BVH_Box<T,N> & theOther,Standard_Boolean & hasOverlap) const280   Standard_Boolean Contains (const BVH_Box<T, N>& theOther,
281                              Standard_Boolean& hasOverlap) const
282   {
283     hasOverlap = Standard_False;
284     if (!theOther.IsValid())
285       return Standard_False;
286 
287     return Contains (theOther.myMinPoint, theOther.myMaxPoint, hasOverlap);
288   }
289 
290   //! Checks if the Box is fully contains the other box.
Contains(const BVH_VecNt & theMinPoint,const BVH_VecNt & theMaxPoint,Standard_Boolean & hasOverlap) const291   Standard_Boolean Contains (const BVH_VecNt& theMinPoint,
292                              const BVH_VecNt& theMaxPoint,
293                              Standard_Boolean& hasOverlap) const
294   {
295     hasOverlap = Standard_False;
296     if (!IsValid())
297       return Standard_False;
298 
299     Standard_Boolean isInside = Standard_True;
300 
301     int n = Min (N, 3);
302     for (int i = 0; i < n; ++i)
303     {
304       hasOverlap = (myMinPoint[i] <= theMaxPoint[i] &&
305                     myMaxPoint[i] >= theMinPoint[i]);
306       if (!hasOverlap)
307         return Standard_False;
308 
309       isInside = isInside && (myMinPoint[i] <= theMinPoint[i] &&
310                               myMaxPoint[i] >= theMaxPoint[i]);
311     }
312     return isInside;
313   }
314 
315   //! Checks if the Point is out of the box.
IsOut(const BVH_VecNt & thePoint) const316   Standard_Boolean IsOut (const BVH_VecNt& thePoint) const
317   {
318     if (!IsValid())
319       return Standard_True;
320 
321     int n = Min (N, 3);
322     for (int i = 0; i < n; ++i)
323     {
324       if (thePoint[i] < myMinPoint[i] ||
325           thePoint[i] > myMaxPoint[i])
326         return Standard_True;
327     }
328     return Standard_False;
329   }
330 
331 
332 protected:
333 
334   BVH_VecNt        myMinPoint; //!< Minimum point of bounding box
335   BVH_VecNt        myMaxPoint; //!< Maximum point of bounding box
336   Standard_Boolean myIsInited; //!< Is bounding box initialized?
337 
338 };
339 
340 namespace BVH
341 {
342   //! Tool class for calculating box center along the given axis.
343   //! \tparam T Numeric data type
344   //! \tparam N Vector dimension
345   template<class T, int N>
346   struct CenterAxis
347   {
348     // Not implemented
349   };
350 
351   template<class T>
352   struct CenterAxis<T, 2>
353   {
CenterBVH::CenterAxis354     static T Center (const BVH_Box<T, 2>& theBox, const Standard_Integer theAxis)
355     {
356       if (theAxis == 0)
357       {
358         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
359       }
360       else if (theAxis == 1)
361       {
362         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
363       }
364       return static_cast<T> (0.0);
365     }
366   };
367 
368   template<class T>
369   struct CenterAxis<T, 3>
370   {
CenterBVH::CenterAxis371     static T Center (const BVH_Box<T, 3>& theBox, const Standard_Integer theAxis)
372     {
373       if (theAxis == 0)
374       {
375         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
376       }
377       else if (theAxis == 1)
378       {
379         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
380       }
381       else if (theAxis == 2)
382       {
383         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
384       }
385       return static_cast<T> (0.0);
386     }
387   };
388 
389   template<class T>
390   struct CenterAxis<T, 4>
391   {
CenterBVH::CenterAxis392     static T Center (const BVH_Box<T, 4>& theBox, const Standard_Integer theAxis)
393     {
394       if (theAxis == 0)
395       {
396         return (theBox.CornerMin().x() + theBox.CornerMax().x()) * static_cast<T> (0.5);
397       }
398       else if (theAxis == 1)
399       {
400         return (theBox.CornerMin().y() + theBox.CornerMax().y()) * static_cast<T> (0.5);
401       }
402       else if (theAxis == 2)
403       {
404         return (theBox.CornerMin().z() + theBox.CornerMax().z()) * static_cast<T> (0.5);
405       }
406       return static_cast<T> (0.0);
407     }
408   };
409 
410   //! Tool class for calculating surface area of the box.
411   //! \tparam T Numeric data type
412   //! \tparam N Vector dimension
413   template<class T, int N>
414   struct SurfaceCalculator
415   {
416     // Not implemented
417   };
418 
419   template<class T>
420   struct SurfaceCalculator<T, 2>
421   {
AreaBVH::SurfaceCalculator422     static T Area (const typename BVH_Box<T, 2>::BVH_VecNt& theSize)
423     {
424       const T anArea = theSize.x() * theSize.y();
425 
426       if (anArea < std::numeric_limits<T>::epsilon())
427       {
428         return theSize.x() + theSize.y();
429       }
430 
431       return anArea;
432     }
433   };
434 
435   template<class T>
436   struct SurfaceCalculator<T, 3>
437   {
AreaBVH::SurfaceCalculator438     static T Area (const typename BVH_Box<T, 3>::BVH_VecNt& theSize)
439     {
440       const T anArea = ( theSize.x() * theSize.y() +
441                          theSize.x() * theSize.z() +
442                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
443 
444       if (anArea < std::numeric_limits<T>::epsilon())
445       {
446         return theSize.x() +
447                theSize.y() +
448                theSize.z();
449       }
450 
451       return anArea;
452     }
453   };
454 
455   template<class T>
456   struct SurfaceCalculator<T, 4>
457   {
AreaBVH::SurfaceCalculator458     static T Area (const typename BVH_Box<T, 4>::BVH_VecNt& theSize)
459     {
460       const T anArea = ( theSize.x() * theSize.y() +
461                          theSize.x() * theSize.z() +
462                          theSize.z() * theSize.y() ) * static_cast<T> (2.0);
463 
464       if (anArea < std::numeric_limits<T>::epsilon())
465       {
466         return theSize.x() +
467                theSize.y() +
468                theSize.z();
469       }
470 
471       return anArea;
472     }
473   };
474 
475   //! Tool class for calculate component-wise vector minimum
476   //! and maximum (optimized version).
477   //! \tparam T Numeric data type
478   //! \tparam N Vector dimension
479   template<class T, int N>
480   struct BoxMinMax
481   {
482     typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
483 
CwiseMinBVH::BoxMinMax484     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
485     {
486       theVec1.x() = Min (theVec1.x(), theVec2.x());
487       theVec1.y() = Min (theVec1.y(), theVec2.y());
488       theVec1.z() = Min (theVec1.z(), theVec2.z());
489     }
490 
CwiseMaxBVH::BoxMinMax491     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
492     {
493       theVec1.x() = Max (theVec1.x(), theVec2.x());
494       theVec1.y() = Max (theVec1.y(), theVec2.y());
495       theVec1.z() = Max (theVec1.z(), theVec2.z());
496     }
497   };
498 
499   template<class T>
500   struct BoxMinMax<T, 2>
501   {
502     typedef typename BVH::VectorType<T, 2>::Type BVH_VecNt;
503 
CwiseMinBVH::BoxMinMax504     static void CwiseMin (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
505     {
506       theVec1.x() = Min (theVec1.x(), theVec2.x());
507       theVec1.y() = Min (theVec1.y(), theVec2.y());
508     }
509 
CwiseMaxBVH::BoxMinMax510     static void CwiseMax (BVH_VecNt& theVec1, const BVH_VecNt& theVec2)
511     {
512       theVec1.x() = Max (theVec1.x(), theVec2.x());
513       theVec1.y() = Max (theVec1.y(), theVec2.y());
514     }
515   };
516 }
517 
518 // =======================================================================
519 // function : Combine
520 // purpose  :
521 // =======================================================================
522 template<class T, int N>
Combine(const BVH_Box & theBox)523 void BVH_Box<T, N>::Combine (const BVH_Box& theBox)
524 {
525   if (theBox.myIsInited)
526   {
527     if (!myIsInited)
528     {
529       myMinPoint = theBox.myMinPoint;
530       myMaxPoint = theBox.myMaxPoint;
531       myIsInited = Standard_True;
532     }
533     else
534     {
535       BVH::BoxMinMax<T, N>::CwiseMin (myMinPoint, theBox.myMinPoint);
536       BVH::BoxMinMax<T, N>::CwiseMax (myMaxPoint, theBox.myMaxPoint);
537     }
538   }
539 }
540 
541 // =======================================================================
542 // function : Area
543 // purpose  :
544 // =======================================================================
545 template<class T, int N>
546 T BVH_Box<T, N>::Area() const
547 {
548   return !myIsInited ? static_cast<T> (0.0) : BVH::SurfaceCalculator<T, N>::Area (myMaxPoint - myMinPoint);
549 }
550 
551 // =======================================================================
552 // function : Center
553 // purpose  :
554 // =======================================================================
555 template<class T, int N>
556 T BVH_Box<T, N>::Center (const Standard_Integer theAxis) const
557 {
558   return BVH::CenterAxis<T, N>::Center (*this, theAxis);
559 }
560 
561 #endif // _BVH_Box_Header
562