3c4e78f2 |
1 | // Created on: 2013-12-20 |
2 | // Created by: Denis BOGOLEPOV |
d5f74e42 |
3 | // Copyright (c) 2013-2014 OPEN CASCADE SAS |
3c4e78f2 |
4 | // |
5 | // This file is part of Open CASCADE Technology software library. |
6 | // |
d5f74e42 |
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 |
3c4e78f2 |
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 | |
f5b72419 |
19 | #include <BVH_Constants.hxx> |
3c4e78f2 |
20 | #include <BVH_Types.hxx> |
bc73b006 |
21 | #include <Standard_Macro.hxx> |
0904aa63 |
22 | #include <Standard_Dump.hxx> |
bc73b006 |
23 | #include <Standard_ShortReal.hxx> |
3c4e78f2 |
24 | |
0bb09048 |
25 | #include <limits> |
26 | |
2b5a58a3 |
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 | |
679d3878 |
100 | //! Defines axis aligned bounding box (AABB) based on BVH vectors. |
101 | //! \tparam T Numeric data type |
102 | //! \tparam N Vector dimension |
3c4e78f2 |
103 | template<class T, int N> |
2b5a58a3 |
104 | class BVH_Box : public BVH_BaseBox<T, N, BVH_Box> |
3c4e78f2 |
105 | { |
106 | public: |
107 | |
3a7a7013 |
108 | typedef typename BVH::VectorType<T, N>::Type BVH_VecNt; |
3c4e78f2 |
109 | |
110 | public: |
111 | |
112 | //! Creates uninitialized bounding box. |
679d3878 |
113 | BVH_Box() : myIsInited (Standard_False) {} |
3c4e78f2 |
114 | |
115 | //! Creates bounding box of given point. |
116 | BVH_Box (const BVH_VecNt& thePoint) |
679d3878 |
117 | : myMinPoint (thePoint), |
118 | myMaxPoint (thePoint), |
119 | myIsInited (Standard_True) {} |
3c4e78f2 |
120 | |
3c4e78f2 |
121 | //! Creates bounding box from corner points. |
122 | BVH_Box (const BVH_VecNt& theMinPoint, |
123 | const BVH_VecNt& theMaxPoint) |
679d3878 |
124 | : myMinPoint (theMinPoint), |
125 | myMaxPoint (theMaxPoint), |
126 | myIsInited (Standard_True) {} |
3c4e78f2 |
127 | |
128 | public: |
129 | |
130 | //! Clears bounding box. |
e28f12b3 |
131 | void Clear() { myIsInited = Standard_False; } |
3c4e78f2 |
132 | |
133 | //! Is bounding box valid? |
e28f12b3 |
134 | Standard_Boolean IsValid() const { return myIsInited; } |
3c4e78f2 |
135 | |
136 | //! Appends new point to the bounding box. |
e28f12b3 |
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 | } |
3c4e78f2 |
151 | |
152 | //! Combines bounding box with another one. |
e28f12b3 |
153 | void Combine (const BVH_Box& theBox); |
3c4e78f2 |
154 | |
155 | //! Returns minimum point of bounding box. |
e28f12b3 |
156 | const BVH_VecNt& CornerMin() const { return myMinPoint; } |
3c4e78f2 |
157 | |
158 | //! Returns maximum point of bounding box. |
e28f12b3 |
159 | const BVH_VecNt& CornerMax() const { return myMaxPoint; } |
3c4e78f2 |
160 | |
161 | //! Returns minimum point of bounding box. |
e28f12b3 |
162 | BVH_VecNt& CornerMin() { return myMinPoint; } |
3c4e78f2 |
163 | |
164 | //! Returns maximum point of bounding box. |
e28f12b3 |
165 | BVH_VecNt& CornerMax() { return myMaxPoint; } |
3c4e78f2 |
166 | |
167 | //! Returns surface area of bounding box. |
0bb09048 |
168 | //! If the box is degenerated into line, returns the perimeter instead. |
3c4e78f2 |
169 | T Area() const; |
170 | |
171 | //! Returns diagonal of bounding box. |
e28f12b3 |
172 | BVH_VecNt Size() const { return myMaxPoint - myMinPoint; } |
3c4e78f2 |
173 | |
174 | //! Returns center of bounding box. |
e28f12b3 |
175 | BVH_VecNt Center() const { return (myMinPoint + myMaxPoint) * static_cast<T> (0.5); } |
3c4e78f2 |
176 | |
679d3878 |
177 | //! Returns center of bounding box along the given axis. |
178 | T Center (const Standard_Integer theAxis) const; |
179 | |
0904aa63 |
180 | //! Dumps the content of me into the stream |
bc73b006 |
181 | void DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth = -1) const |
0904aa63 |
182 | { |
183 | (void)theDepth; |
bc73b006 |
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 | } |
0904aa63 |
202 | } |
203 | |
7c1a8210 |
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 | |
3c4e78f2 |
285 | protected: |
286 | |
679d3878 |
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? |
3c4e78f2 |
290 | |
291 | }; |
292 | |
679d3878 |
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 | { |
0bb09048 |
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; |
679d3878 |
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 | { |
0bb09048 |
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; |
679d3878 |
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 | { |
0bb09048 |
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; |
679d3878 |
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 | |
e28f12b3 |
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 | } |
3c4e78f2 |
513 | |
514 | #endif // _BVH_Box_Header |