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 2018 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)
141  {
142  min = point;
143  max = point;
144  }
145 
147  inline Bbox(
148  const Vector& nmin,
149  const Vector& nmax)
150  {
151  min = nmin;
152  max = nmax;
153  }
154 
159  inline Bbox(
160  T min_x,
161  T max_x)
162  {
163  mi_static_assert(DIM == 1);
164  min = Vector( min_x);
165  max = Vector( max_x);
166  }
167 
172  inline Bbox(
173  T min_x,
174  T min_y,
175  T max_x,
176  T max_y)
177  {
178  mi_static_assert(DIM == 2);
179  min = Vector( min_x, min_y);
180  max = Vector( max_x, max_y);
181  }
182 
187  inline Bbox(
188  T min_x,
189  T min_y,
190  T min_z,
191  T max_x,
192  T max_y,
193  T max_z)
194  {
195  mi_static_assert(DIM == 3);
196  min = Vector( min_x, min_y, min_z);
197  max = Vector( max_x, max_y, max_z);
198  }
199 
207  template <typename InputIterator>
208  Bbox(
209  InputIterator first,
210  InputIterator last);
211 
214  template <typename T2>
215  inline explicit Bbox( const Bbox<T2,DIM>& other)
216  {
217  min = Vector( other.min);
218  max = Vector( other.max);
219  }
220 
223  template <typename T2>
224  inline explicit Bbox( const Bbox_struct<T2,DIM>& other)
225  {
226  min = Vector( other.min);
227  max = Vector( other.max);
228  }
229 
231  inline Bbox& operator=( const Bbox& other)
232  {
233  min = other.min;
234  max = other.max;
235  return *this;
236  }
237 
239  inline Bbox& operator=( const Bbox_struct<T,DIM>& other)
240  {
241  min = other.min;
242  max = other.max;
243  return *this;
244  }
245 
247  inline operator Bbox_struct<T,DIM>() const
248  {
249  Bbox_struct<T,DIM> result;
250  result.min = min;
251  result.max = max;
252  return result;
253  }
254 
256  inline Vector* begin() { return &min; }
257 
259  inline const Vector* begin() const { return &min; }
260 
264  inline Vector* end() { return begin() + SIZE; }
265 
269  inline const Vector* end() const { return begin() + SIZE; }
270 
272  inline Vector& operator[]( Size i)
273  {
274  mi_math_assert_msg( i < SIZE, "precondition");
275  return begin()[i];
276  }
277 
279  inline const Vector& operator[]( Size i) const
280  {
281  mi_math_assert_msg( i < SIZE, "precondition");
282  return begin()[i];
283  }
284 
288  inline bool empty() const
289  {
290  for( Size i = 0; i < DIM; i++) {
292  return false;
294  return false;
295  }
296  return true;
297  }
298 
305  inline Size rank() const
306  {
307  Size rank = 0;
308  for( Size i = 0; i < DIM; i++)
309  rank += (min[i] < max[i]);
310  return rank;
311  }
312 
314  inline bool is_point() const { return min == max; }
315 
319  inline bool is_line() const { return rank() == 1u; }
320 
324  inline bool is_plane() const { return rank() == 2u; }
325 
329  inline bool is_volume() const { return rank() == 3u; }
330 
332  inline bool contains( const Vector& vec) const
333  {
334  for( Size i = 0; i < DIM; i++) {
335  if( vec[i] < min[i] || vec[i] > max[i])
336  return false;
337  }
338  return true;
339  }
340 
343  inline bool intersects( const Bbox& other) const
344  {
345  for( Size i = 0; i < DIM; i++) {
346  if( min[i] > (other.max)[i] || max[i] < (other.min)[i])
347  return false;
348  }
349  return true;
350  }
351 
353  inline void insert( const Bbox& other)
354  {
355  min = elementwise_min( min, (other.min));
356  max = elementwise_max( max, (other.max));
357  }
358 
360  inline void insert( const Vector& point)
361  {
362  min = elementwise_min( min, point);
363  max = elementwise_max( max, point);
364  }
365 
373  template <typename InputIterator>
374  void insert(
375  InputIterator first,
376  InputIterator last);
377 
378 
387  const Bbox& vbox,
388  T t) const
389  {
390  mi_math_assert_msg( ! empty(), "precondition");
391  mi_math_assert_msg( ! vbox.empty(), "precondition");
392  return t < 0 ? Bbox(min + (vbox.max) * t, max + (vbox.min) * t) //-V547 PVS
393  : Bbox(min + (vbox.min) * t, max + (vbox.max) * t);
394  }
395 
401  inline void push_back( const Bbox& other)
402  {
403  return insert( other);
404  }
405 
415  void robust_grow( T eps = T(1.0e-5f));
416 
418  inline T volume() const
419  {
420  Vector diag = max - min;
421  T vol = base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[0]);
422  for( Size i = 1; i < DIM; i++)
423  vol *= base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[i]);
424  return vol;
425  }
426 
430  inline T diagonal_length() const
431  {
432  mi_math_assert_msg( !empty(), "precondition");
433  Vector diag = max - min;
434  return length( diag);
435  }
436 
439  inline Size largest_extent_index() const
440  {
441  Vector diag = max - min;
442  T maxval = diag[0];
443  Size maxidx = 0;
444  for( Size i = 1; i < DIM; i++) {
445  if (maxval < diag[i]) {
446  maxval = diag[i];
447  maxidx = i;
448  }
449  }
450  return maxidx;
451  }
452 
454  inline Vector center() const { return Vector((max + min) * 0.5);}
455 
457  inline Vector extent() const { return max - min; }
458 
459 };
460 
461 //------ Operator declarations for Bbox ---------------------------------------
462 
467 template <typename T, Size DIM>
468 inline Bbox<T,DIM> operator+( const Bbox<T,DIM>& bbox, T value)
469 {
470  mi_math_assert_msg( !bbox.empty(), "precondition");
472  for( Size i = 0; i < DIM; i++) {
473  (result.min)[i] = (bbox.min)[i] - value;
474  (result.max)[i] = (bbox.max)[i] + value;
475  }
476  return result;
477 }
478 
483 template <typename T, Size DIM>
484 inline Bbox<T,DIM> operator-( const Bbox<T,DIM>& bbox, T value)
485 {
486  mi_math_assert_msg( !bbox.empty(), "precondition");
488  for( Size i = 0; i < DIM; i++) {
489  (result.min)[i] = (bbox.min)[i] + value;
490  (result.max)[i] = (bbox.max)[i] - value;
491  }
492  return result;
493 }
494 
499 template <typename T, Size DIM>
500 inline Bbox<T,DIM> operator*( const Bbox<T,DIM>& bbox, T factor)
501 {
502  mi_math_assert_msg( !bbox.empty(), "precondition");
504  for( Size i = 0; i < DIM; i++) {
505  (result.min)[i] = (bbox.min)[i] * factor;
506  (result.max)[i] = (bbox.max)[i] * factor;
507  }
508  return result;
509 }
510 
515 template <typename T, Size DIM>
516 inline Bbox<T,DIM> operator/( const Bbox<T,DIM>& bbox, T divisor)
517 {
518  mi_math_assert_msg( !bbox.empty(), "precondition");
519  mi_math_assert_msg( divisor != T(0), "precondition");
521  for( Size i = 0; i < DIM; i++) {
522  (result.min)[i] = (bbox.min)[i] / divisor;
523  (result.max)[i] = (bbox.max)[i] / divisor;
524  }
525  return result;
526 }
527 
532 template <typename T, Size DIM>
533 inline Bbox<T,DIM>& operator+=( Bbox<T,DIM>& bbox, T value)
534 {
535  mi_math_assert_msg( !bbox.empty(), "precondition");
536  for( Size i = 0; i < DIM; i++) {
537  (bbox.min)[i] -= value;
538  (bbox.max)[i] += value;
539  }
540  return bbox;
541 }
542 
547 template <typename T, Size DIM>
548 inline Bbox<T,DIM>& operator-=( Bbox<T,DIM>& bbox, T value)
549 {
550  mi_math_assert_msg( !bbox.empty(), "precondition");
551  for( Size i = 0; i < DIM; i++) {
552  (bbox.min)[i] += value;
553  (bbox.max)[i] -= value;
554  }
555  return bbox;
556 }
557 
561 template <typename T, Size DIM>
562 inline Bbox<T,DIM>& operator*=( Bbox<T,DIM>& bbox, T factor)
563 {
564  mi_math_assert_msg( !bbox.empty(), "precondition");
565  for( Size i = 0; i < DIM; i++) {
566  (bbox.min)[i] *= factor;
567  (bbox.max)[i] *= factor;
568  }
569  return bbox;
570 }
571 
575 template <typename T, Size DIM>
576 inline Bbox<T,DIM>& operator/=( Bbox<T,DIM>& bbox, T divisor)
577 {
578  mi_math_assert_msg( !bbox.empty(), "precondition");
579  mi_math_assert_msg( divisor != T(0), "precondition");
580  for( Size i = 0; i < DIM; i++) {
581  (bbox.min)[i] /= divisor;
582  (bbox.max)[i] /= divisor;
583  }
584  return bbox;
585 }
586 
588 template <typename T, Size DIM>
589 inline bool operator==(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
590 {
591  return (lhs.min) == (rhs.min) && (lhs.max) == (rhs.max);
592 }
593 
595 template <typename T, Size DIM>
596 inline bool operator!=(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
597 {
598  return (lhs.min) != (rhs.min) || (lhs.max) != (rhs.max);
599 }
600 
604 template <typename T, Size DIM>
605 inline bool operator< ( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
606 {
607  for( Size i(0u); i < DIM; ++i) {
608  if( (lhs.min)[i] < (rhs.min)[i])
609  return true;
610  if( (lhs.min)[i] > (rhs.min)[i])
611  return false;
612  }
613  return lexicographically_less( lhs.max, rhs.max);
614 }
615 
619 template <typename T, Size DIM>
620 inline bool operator<=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
621 {
622  for( Size i(0u); i < DIM; ++i) {
623  if( (lhs.min)[i] < (rhs.min)[i])
624  return true;
625  if( (lhs.min)[i] > (rhs.min)[i])
626  return false;
627  }
628  return lexicographically_less_or_equal( lhs.max, rhs.max);
629 }
630 
634 template <typename T, Size DIM>
635 inline bool operator>( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
636 {
637  for( Size i(0u); i < DIM; ++i) {
638  if( (lhs.min)[i] > (rhs.min)[i])
639  return true;
640  if( (lhs.min)[i] < (rhs.min)[i])
641  return false;
642  }
643  return lexicographically_greater( lhs.max, rhs.max);
644 }
645 
649 template <typename T, Size DIM>
650 inline bool operator>=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
651 {
652  for( Size i(0u); i < DIM; ++i) {
653  if( (lhs.min)[i] > (rhs.min)[i])
654  return true;
655  if( (lhs.min)[i] < (rhs.min)[i])
656  return false;
657  }
658  return lexicographically_greater_or_equal( lhs.max, rhs.max);
659 }
660 
661 
662 //------ Free Functions for Bbox ----------------------------------------------
663 
664 
669 template <typename T, Size DIM>
671  const Bbox<T,DIM> &bbox1,
672  const Bbox<T,DIM> &bbox2,
673  T t)
674 {
675  mi_math_assert_msg( !bbox1.empty(), "precondition");
676  mi_math_assert_msg( !bbox2.empty(), "precondition");
677  T t2 = T(1) - t;
678  return Bbox<T,DIM>( (bbox1.min)*t2 + (bbox2.min)*t, (bbox1.max)*t2 + (bbox2.max)*t);
679 }
680 
681 
684 template <typename T, Size DIM>
686  const Bbox<T,DIM> &bbox1,
687  const Bbox<T,DIM> &bbox2)
688 {
690  for( Size i = 0; i < DIM; i++) {
691  result.min[i] = base::max MI_PREVENT_MACRO_EXPAND (bbox1.min[i], bbox2.min[i]);
692  result.max[i] = base::min MI_PREVENT_MACRO_EXPAND (bbox1.max[i], bbox2.max[i]);
693  if (result.max[i] < result.min[i]) { // the bbox is empty
694  result.clear();
695  return result;
696  }
697  }
698 
699  return result;
700 }
701 
714 template <typename TT, typename T>
715 Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
716 
717 
726 template <typename TT, typename T>
727 Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
728 
729 
730 
731 //------ Definitions of non-inline function -----------------------------------
732 
733 #ifndef MI_FOR_DOXYGEN_ONLY
734 
735 template <typename T, Size DIM>
736 template <typename InputIterator>
737 void Bbox<T,DIM>::insert( InputIterator first, InputIterator last)
738 {
739  for( ; first != last; ++first)
740  insert( *first);
741 }
742 
743 template <typename T, Size DIM>
744 template <typename InputIterator>
745 Bbox<T,DIM>::Bbox( InputIterator first, InputIterator last)
746 {
747  clear();
748  insert( first, last);
749 }
750 
751 template <typename T, Size DIM>
752 void Bbox<T, DIM>::robust_grow( T eps)
753 {
754  // Just enlarging the bounding box by epsilon * (largest box extent) is not sufficient, since
755  // there may be cancellation errors if the box is far away from the origin. Hence we take into
756  // account the distance of the box from the origin: the further the box is away, the larger we
757  // have to make it. We just add the two contributions. If we are very far away, then distance
758  // will dominate. For very large boxes, the extent will dominate. We neglect exact weight
759  // factors. We are just a bit less generous with the epsilon to compensate for the extra stuff
760  // we added. If we have objects that in some direction are several orders of magnitude larger
761  // than in the others, this method will not be perfect.
762  //
763  // compute size heuristic for each dimension
764  Vector dist;
765  for( Size i = 0; i < DIM; i++)
766  dist[i] = base::abs(min[i]) + base::abs(max[i])
767  + base::abs(max[i] - min[i]);
768  // compute the grow factor
769  T max_dist = T(0);
770  for( Size i = 0; i < DIM; i++)
771  max_dist = base::max MI_PREVENT_MACRO_EXPAND (max_dist, dist[i]);
772  const T margin = max_dist * eps;
773  // grow the bounding box
774  *this += margin;
775 }
776 
777 #endif // MI_FOR_DOXYGEN_ONLY
778 
779 template <typename TT, typename T>
781 {
782  if( bbox.empty())
783  return bbox;
784 
785  // Transforms all eight corner points, and finds then the bounding box of these eight points.
786  // The corners are computed in an optimized manner which factorizes computations.
787  //
788  // The transformation is decomposed into the transformation of (min,1) and the transformation of
789  // 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).
790  // The transformation of max is the sum of all 4 transformed vectors. The division by the
791  // homogeneous w is deferred to the end.
792  Vector<T,3> corners[8];
793  corners[0] = transform_vector( mat, bbox.min);
794  corners[0].x += T(mat.wx);
795  corners[0].y += T(mat.wy);
796  corners[0].z += T(mat.wz);
797 
798  // difference vectors between min and max
799  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
800  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
801  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
802 
803  corners[1] = corners[0] + dz; // vertex 001
804  corners[2] = corners[0] + dy; // vertex 010
805  corners[3] = corners[0] + dy + dz; // vertex 011
806  corners[4] = corners[0] + dx; // vertex 100
807  corners[5] = corners[0] + dx + dz; // vertex 101
808  corners[6] = corners[0] + dx + dy; // vertex 110
809  corners[7] = corners[0] + dx + dy + dz; // vertex 110
810 
811  // compute the w-coordinates separately. This is done to avoid copying from 4D to 3D vectors.
812  // Again, the computation is decomposed.
813  //
814  // w-coordinate for difference vectors between min and max
815  T wx = T( mat.xw * ((bbox.max).x - (bbox.min).x));
816  T wy = T( mat.yw * ((bbox.max).y - (bbox.min).y));
817  T wz = T( mat.zw * ((bbox.max).z - (bbox.min).z));
818  // w-coordinate for corners
819  T w[8];
820  w[0] = T(mat.xw * (bbox.min).x + mat.yw * (bbox.min).y + mat.zw * (bbox.min).z + mat.ww);
821  w[1] = w[0] + wz; // vertex 001
822  w[2] = w[0] + wy; // vertex 010
823  w[3] = w[0] + wy + wz; // vertex 011
824  w[4] = w[0] + wx; // vertex 100
825  w[5] = w[0] + wx + wz; // vertex 101
826  w[6] = w[0] + wx + wy; // vertex 110
827  w[7] = w[0] + wx + wy + wz; // vertex 111
828 
829  // divide the other coordinates (x,y,z) by w to obtain 3D coordinates
830  for( unsigned int i=0; i<8; ++i) {
831  if( w[i]!=0 && w[i]!=1) {
832  T inv = T(1) / w[i];
833  corners[i].x *= inv;
834  corners[i].y *= inv;
835  corners[i].z *= inv;
836  }
837  }
838  Bbox<T,3> result( corners, corners+8);
839  return result;
840 }
841 
842 template <typename TT, typename T>
844 {
845  // See transform_point() above for implementation notes.
846  if( bbox.empty())
847  return bbox;
848 
849  Vector<T,3> corners[8];
850  corners[0] = transform_vector( mat, (bbox.min));
851 
852  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
853  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
854  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
855 
856  corners[1] = corners[0] + dz;
857  corners[2] = corners[0] + dy;
858  corners[3] = corners[0] + dy + dz;
859  corners[4] = corners[0] + dx;
860  corners[5] = corners[0] + dx + dz;
861  corners[6] = corners[0] + dx + dy;
862  corners[7] = corners[0] + dx + dy + dz;
863 
864  Bbox<T,3> result( corners, corners+8);
865  return result;
866 }
867  // end group mi_math_bbox
869 
870 } // namespace math
871 
872 } // namespace mi
873 
874 #endif // MI_MATH_BBOX_H