MDL SDK API nvidia_logo_transpbg.gif Up
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
bbox.h
Go to the documentation of this file.
1 /***************************************************************************************************
2  * Copyright 2022 NVIDIA Corporation. All rights reserved.
3  **************************************************************************************************/
9 
10 #ifndef MI_MATH_BBOX_H
11 #define MI_MATH_BBOX_H
12 
13 #include <mi/base/types.h>
14 #include <mi/math/assert.h>
15 #include <mi/math/function.h>
16 #include <mi/math/vector.h>
17 #include <mi/math/matrix.h>
18 
19 namespace mi {
20 
21 namespace math {
22 
35 //------- POD struct that provides storage for bbox elements ----------
36 
45 template <typename T, Size DIM>
46 struct Bbox_struct
47 {
48  Vector_struct<T,DIM> min;
49  Vector_struct<T,DIM> max;
50 };
51 
52 
72 template <typename T, Size DIM>
73 class Bbox //-V690 PVS
74 {
75 public:
76  typedef math::Vector<T,DIM> Vector;
77  typedef Bbox_struct<T,DIM> Pod_type;
78  typedef Vector value_type;
79  typedef Size size_type;
80  typedef Difference difference_type;
81  typedef Vector * pointer;
82  typedef const Vector * const_pointer;
83  typedef Vector & reference;
84  typedef const Vector & const_reference;
85 
86  static const Size DIMENSION = DIM;
87  static const Size SIZE = 2;
88 
90  static inline Size size() { return SIZE; }
91 
93  static inline Size max_size() { return SIZE; }
94 
97  enum Uninitialized_tag {
100  UNINITIALIZED_TAG
101  };
102 
103  Vector min;
104  Vector max;
105 
112  inline void clear()
113  {
114  for( Size i = 0; i < DIM; i++) {
115  min[i] = base::numeric_traits<T>::max MI_PREVENT_MACRO_EXPAND ();
116  max[i] = base::numeric_traits<T>::negative_max();
117  }
118  }
119 
126  inline Bbox() { clear(); }
127 
129  inline explicit Bbox( Uninitialized_tag) { }
130 
131 #if (__cplusplus >= 201103L)
132  Bbox( const Bbox<T,DIM>& other ) = default;
134 #endif
135 
137  inline Bbox( const Bbox_struct<T,DIM>& bbox_struct )
138  {
139  min = bbox_struct.min;
140  max = bbox_struct.max;
141  }
142 
144  inline explicit Bbox(
145  const Vector& point) : min(point), max(point)
146  {
147  }
148 
150  inline Bbox(
151  const Vector& nmin,
152  const Vector& nmax)
153  : min( nmin), max( nmax)
154  {
155  }
156 
161  inline Bbox(
162  T min_x,
163  T max_x)
164  {
165  mi_static_assert(DIM == 1);
166  min = Vector( min_x);
167  max = Vector( max_x);
168  }
169 
174  inline Bbox(
175  T min_x,
176  T min_y,
177  T max_x,
178  T max_y)
179  {
180  mi_static_assert(DIM == 2);
181  min = Vector( min_x, min_y);
182  max = Vector( max_x, max_y);
183  }
184 
189  inline Bbox(
190  T min_x,
191  T min_y,
192  T min_z,
193  T max_x,
194  T max_y,
195  T max_z)
196  {
197  mi_static_assert(DIM == 3);
198  min = Vector( min_x, min_y, min_z);
199  max = Vector( max_x, max_y, max_z);
200  }
201 
209  template <typename InputIterator>
210  Bbox(
211  InputIterator first,
212  InputIterator last);
213 
216  template <typename T2>
217  inline explicit Bbox( const Bbox<T2,DIM>& other)
218  {
219  min = Vector( other.min);
220  max = Vector( other.max);
221  }
222 
225  template <typename T2>
226  inline explicit Bbox( const Bbox_struct<T2,DIM>& other)
227  {
228  min = Vector( other.min);
229  max = Vector( other.max);
230  }
231 
233  inline Bbox& operator=( const Bbox& other)
234  {
235  min = other.min;
236  max = other.max;
237  return *this;
238  }
239 
241  inline Bbox& operator=( const Bbox_struct<T,DIM>& other)
242  {
243  min = other.min;
244  max = other.max;
245  return *this;
246  }
247 
249  inline operator Bbox_struct<T,DIM>() const
250  {
251  Bbox_struct<T,DIM> result;
252  result.min = min;
253  result.max = max;
254  return result;
255  }
256 
258  inline Vector* begin() { return &min; }
259 
261  inline const Vector* begin() const { return &min; }
262 
266  inline Vector* end() { return begin() + SIZE; }
267 
271  inline const Vector* end() const { return begin() + SIZE; }
272 
274  inline Vector& operator[]( Size i)
275  {
276  mi_math_assert_msg( i < SIZE, "precondition");
277  return begin()[i];
278  }
279 
281  inline const Vector& operator[]( Size i) const
282  {
283  mi_math_assert_msg( i < SIZE, "precondition");
284  return begin()[i];
285  }
286 
290  inline bool empty() const
291  {
292  for( Size i = 0; i < DIM; i++) {
293  if( min[i] != base::numeric_traits<T>::max MI_PREVENT_MACRO_EXPAND())
294  return false;
295  if( max[i] != base::numeric_traits<T>::negative_max())
296  return false;
297  }
298  return true;
299  }
300 
307  inline Size rank() const
308  {
309  Size rank = 0;
310  for( Size i = 0; i < DIM; i++)
311  rank += (min[i] < max[i]);
312  return rank;
313  }
314 
316  inline bool is_point() const { return min == max; }
317 
321  inline bool is_line() const { return rank() == 1u; }
322 
326  inline bool is_plane() const { return rank() == 2u; }
327 
331  inline bool is_volume() const { return rank() == 3u; }
332 
334  inline bool contains( const Vector& vec) const
335  {
336  for( Size i = 0; i < DIM; i++) {
337  if( vec[i] < min[i] || vec[i] > max[i])
338  return false;
339  }
340  return true;
341  }
342 
345  inline bool intersects( const Bbox& other) const
346  {
347  for( Size i = 0; i < DIM; i++) {
348  if( min[i] > (other.max)[i] || max[i] < (other.min)[i])
349  return false;
350  }
351  return true;
352  }
353 
355  inline void insert( const Bbox& other)
356  {
357  min = elementwise_min( min, (other.min));
358  max = elementwise_max( max, (other.max));
359  }
360 
362  inline void insert( const Vector& point)
363  {
364  min = elementwise_min( min, point);
365  max = elementwise_max( max, point);
366  }
367 
375  template <typename InputIterator>
376  void insert(
377  InputIterator first,
378  InputIterator last);
379 
380 
388  inline Bbox add_motionbox(
389  const Bbox& vbox,
390  T t) const
391  {
392  mi_math_assert_msg( ! empty(), "precondition");
393  mi_math_assert_msg( ! vbox.empty(), "precondition");
394  return t < 0 ? Bbox(min + (vbox.max) * t, max + (vbox.min) * t) //-V547 PVS
395  : Bbox(min + (vbox.min) * t, max + (vbox.max) * t);
396  }
397 
403  inline void push_back( const Bbox& other)
404  {
405  return insert( other);
406  }
407 
417  void robust_grow( T eps = T(1.0e-5f));
418 
420  inline T volume() const
421  {
422  Vector diag = max - min;
423  T vol = base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[0]);
424  for( Size i = 1; i < DIM; i++) //-V1008 PVS
425  vol *= base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[i]);
426  return vol;
427  }
428 
432  inline T diagonal_length() const
433  {
434  mi_math_assert_msg( !empty(), "precondition");
435  Vector diag = max - min;
436  return length( diag);
437  }
438 
441  inline Size largest_extent_index() const
442  {
443  Vector diag = max - min;
444  T maxval = diag[0];
445  Size maxidx = 0;
446  for( Size i = 1; i < DIM; i++) { //-V1008 PVS
447  if (maxval < diag[i]) {
448  maxval = diag[i];
449  maxidx = i;
450  }
451  }
452  return maxidx;
453  }
454 
456  inline Vector center() const { return Vector((max + min) * 0.5);}
457 
459  inline Vector extent() const { return max - min; }
460 
461 };
462 
463 //------ Operator declarations for Bbox ---------------------------------------
464 
469 template <typename T, Size DIM>
470 inline Bbox<T,DIM> operator+( const Bbox<T,DIM>& bbox, T value)
471 {
472  mi_math_assert_msg( !bbox.empty(), "precondition");
473  Bbox<T,DIM> result( Bbox<T,DIM>::UNINITIALIZED_TAG);
474  for( Size i = 0; i < DIM; i++) {
475  (result.min)[i] = (bbox.min)[i] - value;
476  (result.max)[i] = (bbox.max)[i] + value;
477  }
478  return result;
479 }
480 
485 template <typename T, Size DIM>
486 inline Bbox<T,DIM> operator-( const Bbox<T,DIM>& bbox, T value)
487 {
488  mi_math_assert_msg( !bbox.empty(), "precondition");
489  Bbox<T,DIM> result( Bbox<T,DIM>::UNINITIALIZED_TAG);
490  for( Size i = 0; i < DIM; i++) {
491  (result.min)[i] = (bbox.min)[i] + value;
492  (result.max)[i] = (bbox.max)[i] - value;
493  }
494  return result;
495 }
496 
501 template <typename T, Size DIM>
502 inline Bbox<T,DIM> operator*( const Bbox<T,DIM>& bbox, T factor)
503 {
504  mi_math_assert_msg( !bbox.empty(), "precondition");
505  Bbox<T,DIM> result( Bbox<T,DIM>::UNINITIALIZED_TAG);
506  for( Size i = 0; i < DIM; i++) {
507  (result.min)[i] = (bbox.min)[i] * factor;
508  (result.max)[i] = (bbox.max)[i] * factor;
509  }
510  return result;
511 }
512 
517 template <typename T, Size DIM>
518 inline Bbox<T,DIM> operator/( const Bbox<T,DIM>& bbox, T divisor)
519 {
520  mi_math_assert_msg( !bbox.empty(), "precondition");
521  mi_math_assert_msg( divisor != T(0), "precondition");
522  Bbox<T,DIM> result( Bbox<T,DIM>::UNINITIALIZED_TAG);
523  for( Size i = 0; i < DIM; i++) {
524  (result.min)[i] = (bbox.min)[i] / divisor;
525  (result.max)[i] = (bbox.max)[i] / divisor;
526  }
527  return result;
528 }
529 
534 template <typename T, Size DIM>
535 inline Bbox<T,DIM>& operator+=( Bbox<T,DIM>& bbox, T value)
536 {
537  mi_math_assert_msg( !bbox.empty(), "precondition");
538  for( Size i = 0; i < DIM; i++) {
539  (bbox.min)[i] -= value;
540  (bbox.max)[i] += value;
541  }
542  return bbox;
543 }
544 
549 template <typename T, Size DIM>
550 inline Bbox<T,DIM>& operator-=( Bbox<T,DIM>& bbox, T value)
551 {
552  mi_math_assert_msg( !bbox.empty(), "precondition");
553  for( Size i = 0; i < DIM; i++) {
554  (bbox.min)[i] += value;
555  (bbox.max)[i] -= value;
556  }
557  return bbox;
558 }
559 
563 template <typename T, Size DIM>
564 inline Bbox<T,DIM>& operator*=( Bbox<T,DIM>& bbox, T factor)
565 {
566  mi_math_assert_msg( !bbox.empty(), "precondition");
567  for( Size i = 0; i < DIM; i++) {
568  (bbox.min)[i] *= factor;
569  (bbox.max)[i] *= factor;
570  }
571  return bbox;
572 }
573 
577 template <typename T, Size DIM>
578 inline Bbox<T,DIM>& operator/=( Bbox<T,DIM>& bbox, T divisor)
579 {
580  mi_math_assert_msg( !bbox.empty(), "precondition");
581  mi_math_assert_msg( divisor != T(0), "precondition");
582  for( Size i = 0; i < DIM; i++) {
583  (bbox.min)[i] /= divisor;
584  (bbox.max)[i] /= divisor;
585  }
586  return bbox;
587 }
588 
590 template <typename T, Size DIM>
591 inline bool operator==(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
592 {
593  return (lhs.min) == (rhs.min) && (lhs.max) == (rhs.max);
594 }
595 
597 template <typename T, Size DIM>
598 inline bool operator!=(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
599 {
600  return (lhs.min) != (rhs.min) || (lhs.max) != (rhs.max);
601 }
602 
606 template <typename T, Size DIM>
607 inline bool operator< ( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
608 {
609  for( Size i(0u); i < DIM; ++i) {
610  if( (lhs.min)[i] < (rhs.min)[i])
611  return true;
612  if( (lhs.min)[i] > (rhs.min)[i])
613  return false;
614  }
615  return lexicographically_less( lhs.max, rhs.max);
616 }
617 
621 template <typename T, Size DIM>
622 inline bool operator<=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
623 {
624  for( Size i(0u); i < DIM; ++i) {
625  if( (lhs.min)[i] < (rhs.min)[i])
626  return true;
627  if( (lhs.min)[i] > (rhs.min)[i])
628  return false;
629  }
630  return lexicographically_less_or_equal( lhs.max, rhs.max);
631 }
632 
636 template <typename T, Size DIM>
637 inline bool operator>( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
638 {
639  for( Size i(0u); i < DIM; ++i) {
640  if( (lhs.min)[i] > (rhs.min)[i])
641  return true;
642  if( (lhs.min)[i] < (rhs.min)[i])
643  return false;
644  }
645  return lexicographically_greater( lhs.max, rhs.max);
646 }
647 
651 template <typename T, Size DIM>
652 inline bool operator>=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
653 {
654  for( Size i(0u); i < DIM; ++i) {
655  if( (lhs.min)[i] > (rhs.min)[i])
656  return true;
657  if( (lhs.min)[i] < (rhs.min)[i])
658  return false;
659  }
660  return lexicographically_greater_or_equal( lhs.max, rhs.max);
661 }
662 
663 
664 //------ Free Functions for Bbox ----------------------------------------------
665 
666 
671 template <typename T, Size DIM>
672 inline Bbox<T,DIM> lerp(
673  const Bbox<T,DIM> &bbox1,
674  const Bbox<T,DIM> &bbox2,
675  T t)
676 {
677  mi_math_assert_msg( !bbox1.empty(), "precondition");
678  mi_math_assert_msg( !bbox2.empty(), "precondition");
679  T t2 = T(1) - t;
680  return Bbox<T,DIM>( (bbox1.min)*t2 + (bbox2.min)*t, (bbox1.max)*t2 + (bbox2.max)*t);
681 }
682 
683 
686 template <typename T, Size DIM>
687 inline Bbox<T,DIM> clip(
688  const Bbox<T,DIM> &bbox1,
689  const Bbox<T,DIM> &bbox2)
690 {
691  Bbox<T,DIM> result( Bbox<T,DIM>::UNINITIALIZED_TAG);
692  for( Size i = 0; i < DIM; i++) {
693  result.min[i] = base::max MI_PREVENT_MACRO_EXPAND (bbox1.min[i], bbox2.min[i]);
694  result.max[i] = base::min MI_PREVENT_MACRO_EXPAND (bbox1.max[i], bbox2.max[i]);
695  if (result.max[i] < result.min[i]) { // the bbox is empty
696  result.clear();
697  return result;
698  }
699  }
700 
701  return result;
702 }
703 
716 template <typename TT, typename T>
717 Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
718 
719 
728 template <typename TT, typename T>
729 Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
730 
731 
732 
733 //------ Definitions of non-inline function -----------------------------------
734 
735 #ifndef MI_FOR_DOXYGEN_ONLY
736 
737 template <typename T, Size DIM>
738 template <typename InputIterator>
739 void Bbox<T,DIM>::insert( InputIterator first, InputIterator last)
740 {
741  for( ; first != last; ++first)
742  insert( *first);
743 }
744 
745 template <typename T, Size DIM>
746 template <typename InputIterator>
747 Bbox<T,DIM>::Bbox( InputIterator first, InputIterator last)
748 {
749  clear();
750  insert( first, last);
751 }
752 
753 template <typename T, Size DIM>
754 void Bbox<T, DIM>::robust_grow( T eps)
755 {
756  // Just enlarging the bounding box by epsilon * (largest box extent) is not sufficient, since
757  // there may be cancellation errors if the box is far away from the origin. Hence we take into
758  // account the distance of the box from the origin: the further the box is away, the larger we
759  // have to make it. We just add the two contributions. If we are very far away, then distance
760  // will dominate. For very large boxes, the extent will dominate. We neglect exact weight
761  // factors. We are just a bit less generous with the epsilon to compensate for the extra stuff
762  // we added. If we have objects that in some direction are several orders of magnitude larger
763  // than in the others, this method will not be perfect.
764  //
765  // compute size heuristic for each dimension
766  Vector dist;
767  for( Size i = 0; i < DIM; i++)
768  dist[i] = base::abs(min[i]) + base::abs(max[i])
769  + base::abs(max[i] - min[i]);
770  // compute the grow factor
771  T max_dist = T(0);
772  for( Size i = 0; i < DIM; i++)
773  max_dist = base::max MI_PREVENT_MACRO_EXPAND (max_dist, dist[i]);
774  const T margin = max_dist * eps;
775  // grow the bounding box
776  *this += margin;
777 }
778 
779 #endif // MI_FOR_DOXYGEN_ONLY
780 
781 template <typename TT, typename T>
782 Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox)
783 {
784  if( bbox.empty())
785  return bbox;
786 
787  // Transforms all eight corner points, and finds then the bounding box of these eight points.
788  // The corners are computed in an optimized manner which factorizes computations.
789  //
790  // The transformation is decomposed into the transformation of (min,1) and the transformation of
791  // bounding box difference vectors (max.x-min.x,0,0,0),(0, max.y-min.y,0,0),(0,0,max.z-min.z,0).
792  // The transformation of max is the sum of all 4 transformed vectors. The division by the
793  // homogeneous w is deferred to the end.
794  Vector<T,3> corners[8];
795  corners[0] = transform_vector( mat, bbox.min);
796  corners[0].x += T(mat.wx);
797  corners[0].y += T(mat.wy);
798  corners[0].z += T(mat.wz);
799 
800  // difference vectors between min and max
801  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
802  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
803  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
804 
805  corners[1] = corners[0] + dz; // vertex 001
806  corners[2] = corners[0] + dy; // vertex 010
807  corners[3] = corners[0] + dy + dz; // vertex 011
808  corners[4] = corners[0] + dx; // vertex 100
809  corners[5] = corners[0] + dx + dz; // vertex 101
810  corners[6] = corners[0] + dx + dy; // vertex 110
811  corners[7] = corners[0] + dx + dy + dz; // vertex 110
812 
813  // compute the w-coordinates separately. This is done to avoid copying from 4D to 3D vectors.
814  // Again, the computation is decomposed.
815  //
816  // w-coordinate for difference vectors between min and max
817  T wx = T( mat.xw * ((bbox.max).x - (bbox.min).x));
818  T wy = T( mat.yw * ((bbox.max).y - (bbox.min).y));
819  T wz = T( mat.zw * ((bbox.max).z - (bbox.min).z));
820  // w-coordinate for corners
821  T w[8];
822  w[0] = T(mat.xw * (bbox.min).x + mat.yw * (bbox.min).y + mat.zw * (bbox.min).z + mat.ww);
823  w[1] = w[0] + wz; // vertex 001
824  w[2] = w[0] + wy; // vertex 010
825  w[3] = w[0] + wy + wz; // vertex 011
826  w[4] = w[0] + wx; // vertex 100
827  w[5] = w[0] + wx + wz; // vertex 101
828  w[6] = w[0] + wx + wy; // vertex 110
829  w[7] = w[0] + wx + wy + wz; // vertex 111
830 
831  // divide the other coordinates (x,y,z) by w to obtain 3D coordinates
832  for( unsigned int i=0; i<8; ++i) {
833  if( w[i]!=0 && w[i]!=1) {
834  T inv = T(1) / w[i];
835  corners[i].x *= inv;
836  corners[i].y *= inv;
837  corners[i].z *= inv;
838  }
839  }
840  Bbox<T,3> result( corners, corners+8);
841  return result;
842 }
843 
844 template <typename TT, typename T>
845 Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox)
846 {
847  // See transform_point() above for implementation notes.
848  if( bbox.empty())
849  return bbox;
850 
851  Vector<T,3> corners[8];
852  corners[0] = transform_vector( mat, (bbox.min));
853 
854  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
855  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
856  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
857 
858  corners[1] = corners[0] + dz;
859  corners[2] = corners[0] + dy;
860  corners[3] = corners[0] + dy + dz;
861  corners[4] = corners[0] + dx;
862  corners[5] = corners[0] + dx + dz;
863  corners[6] = corners[0] + dx + dy;
864  corners[7] = corners[0] + dx + dy + dz;
865 
866  Bbox<T,3> result( corners, corners+8);
867  return result;
868 }
869  // end group mi_math_bbox
871 
872 } // namespace math
873 
874 } // namespace mi
875 
876 #endif // MI_MATH_BBOX_H