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