Material Definition Language 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 2020 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>
47 {
50 };
51 
52 
72 template <typename T, Size DIM>
73 class Bbox
74 {
75 public:
78  typedef Vector value_type;
79  typedef Size size_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 
101  };
102 
105 
112  inline void clear()
113  {
114  for( Size i = 0; i < DIM; i++) {
117  }
118  }
119 
126  inline Bbox() { clear(); }
127 
129  inline explicit Bbox( Uninitialized_tag) { }
130 
132  inline Bbox( const Bbox_struct<T,DIM>& bbox_struct )
133  {
134  min = bbox_struct.min;
135  max = bbox_struct.max;
136  }
137 
139  inline explicit Bbox(
140  const Vector& point) : min(point), max(point)
141  {
142  }
143 
145  inline Bbox(
146  const Vector& nmin,
147  const Vector& nmax)
148  : min(nmin), max(nmax)
149  {
150  }
151 
156  inline Bbox(
157  T min_x,
158  T max_x)
159  {
160  mi_static_assert(DIM == 1);
161  min = Vector( min_x);
162  max = Vector( max_x);
163  }
164 
169  inline Bbox(
170  T min_x,
171  T min_y,
172  T max_x,
173  T max_y)
174  {
175  mi_static_assert(DIM == 2);
176  min = Vector( min_x, min_y);
177  max = Vector( max_x, max_y);
178  }
179 
184  inline Bbox(
185  T min_x,
186  T min_y,
187  T min_z,
188  T max_x,
189  T max_y,
190  T max_z)
191  {
192  mi_static_assert(DIM == 3);
193  min = Vector( min_x, min_y, min_z);
194  max = Vector( max_x, max_y, max_z);
195  }
196 
204  template <typename InputIterator>
205  Bbox(
206  InputIterator first,
207  InputIterator last);
208 
211  template <typename T2>
212  inline explicit Bbox( const Bbox<T2,DIM>& other)
213  {
214  min = Vector( other.min);
215  max = Vector( other.max);
216  }
217 
220  template <typename T2>
221  inline explicit Bbox( const Bbox_struct<T2,DIM>& other)
222  {
223  min = Vector( other.min);
224  max = Vector( other.max);
225  }
226 
228  inline Bbox& operator=( const Bbox& other)
229  {
230  min = other.min;
231  max = other.max;
232  return *this;
233  }
234 
236  inline Bbox& operator=( const Bbox_struct<T,DIM>& other)
237  {
238  min = other.min;
239  max = other.max;
240  return *this;
241  }
242 
244  inline operator Bbox_struct<T,DIM>() const
245  {
246  Bbox_struct<T,DIM> result;
247  result.min = min;
248  result.max = max;
249  return result;
250  }
251 
253  inline Vector* begin() { return &min; }
254 
256  inline const Vector* begin() const { return &min; }
257 
261  inline Vector* end() { return begin() + SIZE; }
262 
266  inline const Vector* end() const { return begin() + SIZE; }
267 
269  inline Vector& operator[]( Size i)
270  {
271  mi_math_assert_msg( i < SIZE, "precondition");
272  return begin()[i];
273  }
274 
276  inline const Vector& operator[]( Size i) const
277  {
278  mi_math_assert_msg( i < SIZE, "precondition");
279  return begin()[i];
280  }
281 
285  inline bool empty() const
286  {
287  for( Size i = 0; i < DIM; i++) {
289  return false;
291  return false;
292  }
293  return true;
294  }
295 
302  inline Size rank() const
303  {
304  Size rank = 0;
305  for( Size i = 0; i < DIM; i++)
306  rank += (min[i] < max[i]);
307  return rank;
308  }
309 
311  inline bool is_point() const { return min == max; }
312 
316  inline bool is_line() const { return rank() == 1u; }
317 
321  inline bool is_plane() const { return rank() == 2u; }
322 
326  inline bool is_volume() const { return rank() == 3u; }
327 
329  inline bool contains( const Vector& vec) const
330  {
331  for( Size i = 0; i < DIM; i++) {
332  if( vec[i] < min[i] || vec[i] > max[i])
333  return false;
334  }
335  return true;
336  }
337 
340  inline bool intersects( const Bbox& other) const
341  {
342  for( Size i = 0; i < DIM; i++) {
343  if( min[i] > (other.max)[i] || max[i] < (other.min)[i])
344  return false;
345  }
346  return true;
347  }
348 
350  inline void insert( const Bbox& other)
351  {
352  min = elementwise_min( min, (other.min));
353  max = elementwise_max( max, (other.max));
354  }
355 
357  inline void insert( const Vector& point)
358  {
359  min = elementwise_min( min, point);
360  max = elementwise_max( max, point);
361  }
362 
370  template <typename InputIterator>
371  void insert(
372  InputIterator first,
373  InputIterator last);
374 
375 
384  const Bbox& vbox,
385  T t) const
386  {
387  mi_math_assert_msg( ! empty(), "precondition");
388  mi_math_assert_msg( ! vbox.empty(), "precondition");
389  return t < 0 ? Bbox(min + (vbox.max) * t, max + (vbox.min) * t) //-V547 PVS
390  : Bbox(min + (vbox.min) * t, max + (vbox.max) * t);
391  }
392 
398  inline void push_back( const Bbox& other)
399  {
400  return insert( other);
401  }
402 
412  void robust_grow( T eps = T(1.0e-5f));
413 
415  inline T volume() const
416  {
417  Vector diag = max - min;
418  T vol = base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[0]);
419  for( Size i = 1; i < DIM; i++)
420  vol *= base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[i]);
421  return vol;
422  }
423 
427  inline T diagonal_length() const
428  {
429  mi_math_assert_msg( !empty(), "precondition");
430  Vector diag = max - min;
431  return length( diag);
432  }
433 
436  inline Size largest_extent_index() const
437  {
438  Vector diag = max - min;
439  T maxval = diag[0];
440  Size maxidx = 0;
441  for( Size i = 1; i < DIM; i++) {
442  if (maxval < diag[i]) {
443  maxval = diag[i];
444  maxidx = i;
445  }
446  }
447  return maxidx;
448  }
449 
451  inline Vector center() const { return Vector((max + min) * 0.5);}
452 
454  inline Vector extent() const { return max - min; }
455 
456 };
457 
458 //------ Operator declarations for Bbox ---------------------------------------
459 
464 template <typename T, Size DIM>
465 inline Bbox<T,DIM> operator+( const Bbox<T,DIM>& bbox, T value)
466 {
467  mi_math_assert_msg( !bbox.empty(), "precondition");
469  for( Size i = 0; i < DIM; i++) {
470  (result.min)[i] = (bbox.min)[i] - value;
471  (result.max)[i] = (bbox.max)[i] + value;
472  }
473  return result;
474 }
475 
480 template <typename T, Size DIM>
481 inline Bbox<T,DIM> operator-( const Bbox<T,DIM>& bbox, T value)
482 {
483  mi_math_assert_msg( !bbox.empty(), "precondition");
485  for( Size i = 0; i < DIM; i++) {
486  (result.min)[i] = (bbox.min)[i] + value;
487  (result.max)[i] = (bbox.max)[i] - value;
488  }
489  return result;
490 }
491 
496 template <typename T, Size DIM>
497 inline Bbox<T,DIM> operator*( const Bbox<T,DIM>& bbox, T factor)
498 {
499  mi_math_assert_msg( !bbox.empty(), "precondition");
501  for( Size i = 0; i < DIM; i++) {
502  (result.min)[i] = (bbox.min)[i] * factor;
503  (result.max)[i] = (bbox.max)[i] * factor;
504  }
505  return result;
506 }
507 
512 template <typename T, Size DIM>
513 inline Bbox<T,DIM> operator/( const Bbox<T,DIM>& bbox, T divisor)
514 {
515  mi_math_assert_msg( !bbox.empty(), "precondition");
516  mi_math_assert_msg( divisor != T(0), "precondition");
518  for( Size i = 0; i < DIM; i++) {
519  (result.min)[i] = (bbox.min)[i] / divisor;
520  (result.max)[i] = (bbox.max)[i] / divisor;
521  }
522  return result;
523 }
524 
529 template <typename T, Size DIM>
530 inline Bbox<T,DIM>& operator+=( Bbox<T,DIM>& bbox, T value)
531 {
532  mi_math_assert_msg( !bbox.empty(), "precondition");
533  for( Size i = 0; i < DIM; i++) {
534  (bbox.min)[i] -= value;
535  (bbox.max)[i] += value;
536  }
537  return bbox;
538 }
539 
544 template <typename T, Size DIM>
545 inline Bbox<T,DIM>& operator-=( Bbox<T,DIM>& bbox, T value)
546 {
547  mi_math_assert_msg( !bbox.empty(), "precondition");
548  for( Size i = 0; i < DIM; i++) {
549  (bbox.min)[i] += value;
550  (bbox.max)[i] -= value;
551  }
552  return bbox;
553 }
554 
558 template <typename T, Size DIM>
559 inline Bbox<T,DIM>& operator*=( Bbox<T,DIM>& bbox, T factor)
560 {
561  mi_math_assert_msg( !bbox.empty(), "precondition");
562  for( Size i = 0; i < DIM; i++) {
563  (bbox.min)[i] *= factor;
564  (bbox.max)[i] *= factor;
565  }
566  return bbox;
567 }
568 
572 template <typename T, Size DIM>
573 inline Bbox<T,DIM>& operator/=( Bbox<T,DIM>& bbox, T divisor)
574 {
575  mi_math_assert_msg( !bbox.empty(), "precondition");
576  mi_math_assert_msg( divisor != T(0), "precondition");
577  for( Size i = 0; i < DIM; i++) {
578  (bbox.min)[i] /= divisor;
579  (bbox.max)[i] /= divisor;
580  }
581  return bbox;
582 }
583 
585 template <typename T, Size DIM>
586 inline bool operator==(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
587 {
588  return (lhs.min) == (rhs.min) && (lhs.max) == (rhs.max);
589 }
590 
592 template <typename T, Size DIM>
593 inline bool operator!=(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
594 {
595  return (lhs.min) != (rhs.min) || (lhs.max) != (rhs.max);
596 }
597 
601 template <typename T, Size DIM>
602 inline bool operator< ( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
603 {
604  for( Size i(0u); i < DIM; ++i) {
605  if( (lhs.min)[i] < (rhs.min)[i])
606  return true;
607  if( (lhs.min)[i] > (rhs.min)[i])
608  return false;
609  }
610  return lexicographically_less( lhs.max, rhs.max);
611 }
612 
616 template <typename T, Size DIM>
617 inline bool operator<=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
618 {
619  for( Size i(0u); i < DIM; ++i) {
620  if( (lhs.min)[i] < (rhs.min)[i])
621  return true;
622  if( (lhs.min)[i] > (rhs.min)[i])
623  return false;
624  }
625  return lexicographically_less_or_equal( lhs.max, rhs.max);
626 }
627 
631 template <typename T, Size DIM>
632 inline bool operator>( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
633 {
634  for( Size i(0u); i < DIM; ++i) {
635  if( (lhs.min)[i] > (rhs.min)[i])
636  return true;
637  if( (lhs.min)[i] < (rhs.min)[i])
638  return false;
639  }
640  return lexicographically_greater( lhs.max, rhs.max);
641 }
642 
646 template <typename T, Size DIM>
647 inline bool operator>=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
648 {
649  for( Size i(0u); i < DIM; ++i) {
650  if( (lhs.min)[i] > (rhs.min)[i])
651  return true;
652  if( (lhs.min)[i] < (rhs.min)[i])
653  return false;
654  }
655  return lexicographically_greater_or_equal( lhs.max, rhs.max);
656 }
657 
658 
659 //------ Free Functions for Bbox ----------------------------------------------
660 
661 
666 template <typename T, Size DIM>
668  const Bbox<T,DIM> &bbox1,
669  const Bbox<T,DIM> &bbox2,
670  T t)
671 {
672  mi_math_assert_msg( !bbox1.empty(), "precondition");
673  mi_math_assert_msg( !bbox2.empty(), "precondition");
674  T t2 = T(1) - t;
675  return Bbox<T,DIM>( (bbox1.min)*t2 + (bbox2.min)*t, (bbox1.max)*t2 + (bbox2.max)*t);
676 }
677 
678 
681 template <typename T, Size DIM>
683  const Bbox<T,DIM> &bbox1,
684  const Bbox<T,DIM> &bbox2)
685 {
687  for( Size i = 0; i < DIM; i++) {
688  result.min[i] = base::max MI_PREVENT_MACRO_EXPAND (bbox1.min[i], bbox2.min[i]);
689  result.max[i] = base::min MI_PREVENT_MACRO_EXPAND (bbox1.max[i], bbox2.max[i]);
690  if (result.max[i] < result.min[i]) { // the bbox is empty
691  result.clear();
692  return result;
693  }
694  }
695 
696  return result;
697 }
698 
711 template <typename TT, typename T>
712 Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
713 
714 
723 template <typename TT, typename T>
724 Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
725 
726 
727 
728 //------ Definitions of non-inline function -----------------------------------
729 
730 #ifndef MI_FOR_DOXYGEN_ONLY
731 
732 template <typename T, Size DIM>
733 template <typename InputIterator>
734 void Bbox<T,DIM>::insert( InputIterator first, InputIterator last)
735 {
736  for( ; first != last; ++first)
737  insert( *first);
738 }
739 
740 template <typename T, Size DIM>
741 template <typename InputIterator>
742 Bbox<T,DIM>::Bbox( InputIterator first, InputIterator last)
743 {
744  clear();
745  insert( first, last);
746 }
747 
748 template <typename T, Size DIM>
749 void Bbox<T, DIM>::robust_grow( T eps)
750 {
751  // Just enlarging the bounding box by epsilon * (largest box extent) is not sufficient, since
752  // there may be cancellation errors if the box is far away from the origin. Hence we take into
753  // account the distance of the box from the origin: the further the box is away, the larger we
754  // have to make it. We just add the two contributions. If we are very far away, then distance
755  // will dominate. For very large boxes, the extent will dominate. We neglect exact weight
756  // factors. We are just a bit less generous with the epsilon to compensate for the extra stuff
757  // we added. If we have objects that in some direction are several orders of magnitude larger
758  // than in the others, this method will not be perfect.
759  //
760  // compute size heuristic for each dimension
761  Vector dist;
762  for( Size i = 0; i < DIM; i++)
763  dist[i] = base::abs(min[i]) + base::abs(max[i])
764  + base::abs(max[i] - min[i]);
765  // compute the grow factor
766  T max_dist = T(0);
767  for( Size i = 0; i < DIM; i++)
768  max_dist = base::max MI_PREVENT_MACRO_EXPAND (max_dist, dist[i]);
769  const T margin = max_dist * eps;
770  // grow the bounding box
771  *this += margin;
772 }
773 
774 #endif // MI_FOR_DOXYGEN_ONLY
775 
776 template <typename TT, typename T>
778 {
779  if( bbox.empty())
780  return bbox;
781 
782  // Transforms all eight corner points, and finds then the bounding box of these eight points.
783  // The corners are computed in an optimized manner which factorizes computations.
784  //
785  // The transformation is decomposed into the transformation of (min,1) and the transformation of
786  // 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).
787  // The transformation of max is the sum of all 4 transformed vectors. The division by the
788  // homogeneous w is deferred to the end.
789  Vector<T,3> corners[8];
790  corners[0] = transform_vector( mat, bbox.min);
791  corners[0].x += T(mat.wx);
792  corners[0].y += T(mat.wy);
793  corners[0].z += T(mat.wz);
794 
795  // difference vectors between min and max
796  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
797  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
798  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
799 
800  corners[1] = corners[0] + dz; // vertex 001
801  corners[2] = corners[0] + dy; // vertex 010
802  corners[3] = corners[0] + dy + dz; // vertex 011
803  corners[4] = corners[0] + dx; // vertex 100
804  corners[5] = corners[0] + dx + dz; // vertex 101
805  corners[6] = corners[0] + dx + dy; // vertex 110
806  corners[7] = corners[0] + dx + dy + dz; // vertex 110
807 
808  // compute the w-coordinates separately. This is done to avoid copying from 4D to 3D vectors.
809  // Again, the computation is decomposed.
810  //
811  // w-coordinate for difference vectors between min and max
812  T wx = T( mat.xw * ((bbox.max).x - (bbox.min).x));
813  T wy = T( mat.yw * ((bbox.max).y - (bbox.min).y));
814  T wz = T( mat.zw * ((bbox.max).z - (bbox.min).z));
815  // w-coordinate for corners
816  T w[8];
817  w[0] = T(mat.xw * (bbox.min).x + mat.yw * (bbox.min).y + mat.zw * (bbox.min).z + mat.ww);
818  w[1] = w[0] + wz; // vertex 001
819  w[2] = w[0] + wy; // vertex 010
820  w[3] = w[0] + wy + wz; // vertex 011
821  w[4] = w[0] + wx; // vertex 100
822  w[5] = w[0] + wx + wz; // vertex 101
823  w[6] = w[0] + wx + wy; // vertex 110
824  w[7] = w[0] + wx + wy + wz; // vertex 111
825 
826  // divide the other coordinates (x,y,z) by w to obtain 3D coordinates
827  for( unsigned int i=0; i<8; ++i) {
828  if( w[i]!=0 && w[i]!=1) {
829  T inv = T(1) / w[i];
830  corners[i].x *= inv;
831  corners[i].y *= inv;
832  corners[i].z *= inv;
833  }
834  }
835  Bbox<T,3> result( corners, corners+8);
836  return result;
837 }
838 
839 template <typename TT, typename T>
841 {
842  // See transform_point() above for implementation notes.
843  if( bbox.empty())
844  return bbox;
845 
846  Vector<T,3> corners[8];
847  corners[0] = transform_vector( mat, (bbox.min));
848 
849  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
850  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
851  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
852 
853  corners[1] = corners[0] + dz;
854  corners[2] = corners[0] + dy;
855  corners[3] = corners[0] + dy + dz;
856  corners[4] = corners[0] + dx;
857  corners[5] = corners[0] + dx + dz;
858  corners[6] = corners[0] + dx + dy;
859  corners[7] = corners[0] + dx + dy + dz;
860 
861  Bbox<T,3> result( corners, corners+8);
862  return result;
863 }
864  // end group mi_math_bbox
866 
867 } // namespace math
868 
869 } // namespace mi
870 
871 #endif // MI_MATH_BBOX_H