NVIDIA Iray: Math API Home  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 1986, 2016 NVIDIA Corporation. All rights reserved.
3 //*****************************************************************************
10 //*****************************************************************************
11 
12 #ifndef MI_MATH_BBOX_H
13 #define MI_MATH_BBOX_H
14 
15 #include <mi/base/types.h>
16 #include <mi/math/assert.h>
17 #include <mi/math/function.h>
18 #include <mi/math/vector.h>
19 #include <mi/math/matrix.h>
20 
21 namespace mi {
22 
23 namespace math {
24 
37 //------- POD struct that provides storage for bbox elements ----------
38 
47 template <typename T, Size DIM>
48 struct Bbox_struct
49 {
52 };
53 
54 
74 template <typename T, Size DIM>
75 class Bbox
76 {
77 public:
80  typedef Vector value_type;
81  typedef Size size_type;
83  typedef Vector * pointer;
84  typedef const Vector * const_pointer;
85  typedef Vector & reference;
86  typedef const Vector & const_reference;
87 
88  static const Size DIMENSION = DIM;
89  static const Size SIZE = 2;
90 
92  static inline Size size() { return SIZE; }
93 
95  static inline Size max_size() { return SIZE; }
96 
103  };
104 
107 
114  inline void clear()
115  {
116  for( Size i = 0; i < DIM; i++) {
119  }
120  }
121 
128  inline Bbox() { clear(); }
129 
131  inline explicit Bbox( Uninitialized_tag) { }
132 
134  inline Bbox( const Bbox_struct<T,DIM>& bbox_struct )
135  {
136  min = bbox_struct.min;
137  max = bbox_struct.max;
138  }
139 
141  inline explicit Bbox(
142  const Vector& point)
143  {
144  min = point;
145  max = point;
146  }
147 
149  inline Bbox(
150  const Vector& nmin,
151  const Vector& nmax)
152  {
153  min = nmin;
154  max = nmax;
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 
224  inline Bbox& operator=( const Bbox& other)
225  {
226  min = other.min;
227  max = other.max;
228  return *this;
229  }
230 
232  inline Bbox& operator=( const Bbox_struct<T,DIM>& other)
233  {
234  min = other.min;
235  max = other.max;
236  return *this;
237  }
238 
240  inline operator Bbox_struct<T,DIM>() const
241  {
242  Bbox_struct<T,DIM> result;
243  result.min = min;
244  result.max = max;
245  return result;
246  }
247 
249  inline Vector* begin() { return &min; }
250 
252  inline const Vector* begin() const { return &min; }
253 
257  inline Vector* end() { return begin() + SIZE; }
258 
262  inline const Vector* end() const { return begin() + SIZE; }
263 
265  inline Vector& operator[]( Size i)
266  {
267  mi_math_assert_msg( i < SIZE, "precondition");
268  return begin()[i];
269  }
270 
272  inline const Vector& operator[]( Size i) const
273  {
274  mi_math_assert_msg( i < SIZE, "precondition");
275  return begin()[i];
276  }
277 
281  inline bool empty() const
282  {
283  for( Size i = 0; i < DIM; i++) {
285  return false;
287  return false;
288  }
289  return true;
290  }
291 
298  inline Size rank() const
299  {
300  Size rank = 0;
301  for( Size i = 0; i < DIM; i++)
302  rank += (min[i] < max[i]);
303  return rank;
304  }
305 
307  inline bool is_point() const { return min == max; }
308 
312  inline bool is_line() const { return rank() == 1u; }
313 
317  inline bool is_plane() const { return rank() == 2u; }
318 
322  inline bool is_volume() const { return rank() == 3u; }
323 
325  inline bool contains( const Vector& vec) const
326  {
327  for( Size i = 0; i < DIM; i++) {
328  if( vec[i] < min[i] || vec[i] > max[i])
329  return false;
330  }
331  return true;
332  }
333 
336  inline bool intersects( const Bbox& other) const
337  {
338  for( Size i = 0; i < DIM; i++) {
339  if( min[i] > (other.max)[i] || max[i] < (other.min)[i])
340  return false;
341  }
342  return true;
343  }
344 
346  inline void insert( const Bbox& other)
347  {
348  min = elementwise_min( min, (other.min));
349  max = elementwise_max( max, (other.max));
350  }
351 
353  inline void insert( const Vector& point)
354  {
355  min = elementwise_min( min, point);
356  max = elementwise_max( max, point);
357  }
358 
366  template <typename InputIterator>
367  void insert(
368  InputIterator first,
369  InputIterator last);
370 
371 
380  const Bbox& vbox,
381  T t) const
382  {
383  mi_math_assert_msg( ! empty(), "precondition");
384  mi_math_assert_msg( ! vbox.empty(), "precondition");
385  return t < 0 ? Bbox(min + (vbox.max) * t, max + (vbox.min) * t) //-V547 PVS
386  : Bbox(min + (vbox.min) * t, max + (vbox.max) * t);
387  }
388 
394  inline void push_back( const Bbox& other)
395  {
396  return insert( other);
397  }
398 
408  void robust_grow( T eps = T(1.0e-5f));
409 
411  inline T volume() const
412  {
413  Vector diag = max - min;
414  T vol = base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[0]);
415  for( Size i = 1; i < DIM; i++)
416  vol *= base::max MI_PREVENT_MACRO_EXPAND ( T(0), diag[i]);
417  return vol;
418  }
419 
423  inline T diagonal_length() const
424  {
425  mi_math_assert_msg( !empty(), "precondition");
426  Vector diag = max - min;
427  return length( diag);
428  }
429 
432  inline Size largest_extent_index() const
433  {
434  Vector diag = max - min;
435  T maxval = diag[0];
436  Size maxidx = 0;
437  for( Size i = 1; i < DIM; i++) {
438  if (maxval < diag[i]) {
439  maxval = diag[i];
440  maxidx = i;
441  }
442  }
443  return maxidx;
444  }
445 
447  inline Vector center() const { return (max + min) * T(0.5);}
448 
449 };
450 
451 //------ Operator declarations for Bbox ---------------------------------------
452 
457 template <typename T, Size DIM>
458 inline Bbox<T,DIM> operator+( const Bbox<T,DIM>& bbox, T value)
459 {
460  mi_math_assert_msg( !bbox.empty(), "precondition");
462  for( Size i = 0; i < DIM; i++) {
463  (result.min)[i] = (bbox.min)[i] - value;
464  (result.max)[i] = (bbox.max)[i] + value;
465  }
466  return result;
467 }
468 
473 template <typename T, Size DIM>
474 inline Bbox<T,DIM> operator-( const Bbox<T,DIM>& bbox, T value)
475 {
476  mi_math_assert_msg( !bbox.empty(), "precondition");
478  for( Size i = 0; i < DIM; i++) {
479  (result.min)[i] = (bbox.min)[i] + value;
480  (result.max)[i] = (bbox.max)[i] - value;
481  }
482  return result;
483 }
484 
489 template <typename T, Size DIM>
490 inline Bbox<T,DIM> operator*( const Bbox<T,DIM>& bbox, T factor)
491 {
492  mi_math_assert_msg( !bbox.empty(), "precondition");
494  for( Size i = 0; i < DIM; i++) {
495  (result.min)[i] = (bbox.min)[i] * factor;
496  (result.max)[i] = (bbox.max)[i] * factor;
497  }
498  return result;
499 }
500 
505 template <typename T, Size DIM>
506 inline Bbox<T,DIM> operator/( const Bbox<T,DIM>& bbox, T divisor)
507 {
508  mi_math_assert_msg( !bbox.empty(), "precondition");
509  mi_math_assert_msg( divisor != T(0), "precondition");
511  for( Size i = 0; i < DIM; i++) {
512  (result.min)[i] = (bbox.min)[i] / divisor;
513  (result.max)[i] = (bbox.max)[i] / divisor;
514  }
515  return result;
516 }
517 
522 template <typename T, Size DIM>
523 inline Bbox<T,DIM>& operator+=( Bbox<T,DIM>& bbox, T value)
524 {
525  mi_math_assert_msg( !bbox.empty(), "precondition");
526  for( Size i = 0; i < DIM; i++) {
527  (bbox.min)[i] -= value;
528  (bbox.max)[i] += value;
529  }
530  return bbox;
531 }
532 
537 template <typename T, Size DIM>
538 inline Bbox<T,DIM>& operator-=( Bbox<T,DIM>& bbox, T value)
539 {
540  mi_math_assert_msg( !bbox.empty(), "precondition");
541  for( Size i = 0; i < DIM; i++) {
542  (bbox.min)[i] += value;
543  (bbox.max)[i] -= value;
544  }
545  return bbox;
546 }
547 
551 template <typename T, Size DIM>
552 inline Bbox<T,DIM>& operator*=( Bbox<T,DIM>& bbox, T factor)
553 {
554  mi_math_assert_msg( !bbox.empty(), "precondition");
555  for( Size i = 0; i < DIM; i++) {
556  (bbox.min)[i] *= factor;
557  (bbox.max)[i] *= factor;
558  }
559  return bbox;
560 }
561 
565 template <typename T, Size DIM>
566 inline Bbox<T,DIM>& operator/=( Bbox<T,DIM>& bbox, T divisor)
567 {
568  mi_math_assert_msg( !bbox.empty(), "precondition");
569  mi_math_assert_msg( divisor != T(0), "precondition");
570  for( Size i = 0; i < DIM; i++) {
571  (bbox.min)[i] /= divisor;
572  (bbox.max)[i] /= divisor;
573  }
574  return bbox;
575 }
576 
578 template <typename T, Size DIM>
579 inline bool operator==(const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
580 {
581  return (lhs.min) == (rhs.min) && (lhs.max) == (rhs.max);
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 
594 template <typename T, Size DIM>
595 inline bool operator< ( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
596 {
597  for( Size i(0u); i < DIM; ++i) {
598  if( (lhs.min)[i] < (rhs.min)[i])
599  return true;
600  if( (lhs.min)[i] > (rhs.min)[i])
601  return false;
602  }
603  return lexicographically_less( lhs.max, rhs.max);
604 }
605 
609 template <typename T, Size DIM>
610 inline bool operator<=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
611 {
612  for( Size i(0u); i < DIM; ++i) {
613  if( (lhs.min)[i] < (rhs.min)[i])
614  return true;
615  if( (lhs.min)[i] > (rhs.min)[i])
616  return false;
617  }
618  return lexicographically_less_or_equal( lhs.max, rhs.max);
619 }
620 
624 template <typename T, Size DIM>
625 inline bool operator>( const Bbox<T,DIM> & lhs, const Bbox<T,DIM> & rhs)
626 {
627  for( Size i(0u); i < DIM; ++i) {
628  if( (lhs.min)[i] > (rhs.min)[i])
629  return true;
630  if( (lhs.min)[i] < (rhs.min)[i])
631  return false;
632  }
633  return lexicographically_greater( lhs.max, rhs.max);
634 }
635 
639 template <typename T, Size DIM>
640 inline bool operator>=( const Bbox<T,DIM>& lhs, const Bbox<T,DIM>& rhs)
641 {
642  for( Size i(0u); i < DIM; ++i) {
643  if( (lhs.min)[i] > (rhs.min)[i])
644  return true;
645  if( (lhs.min)[i] < (rhs.min)[i])
646  return false;
647  }
648  return lexicographically_greater_or_equal( lhs.max, rhs.max);
649 }
650 
651 
652 //------ Free Functions for Bbox ----------------------------------------------
653 
654 
659 template <typename T, Size DIM>
661  const Bbox<T,DIM> &bbox1,
662  const Bbox<T,DIM> &bbox2,
663  T t)
664 {
665  mi_math_assert_msg( !bbox1.empty(), "precondition");
666  mi_math_assert_msg( !bbox2.empty(), "precondition");
667  T t2 = T(1) - t;
668  return Bbox<T,DIM>( (bbox1.min)*t2 + (bbox2.min)*t, (bbox1.max)*t2 + (bbox2.max)*t);
669 }
670 
671 
674 template <typename T, Size DIM>
676  const Bbox<T,DIM> &bbox1,
677  const Bbox<T,DIM> &bbox2)
678 {
680  for( Size i = 0; i < DIM; i++) {
681  result.min[i] = base::max MI_PREVENT_MACRO_EXPAND (bbox1.min[i], bbox2.min[i]);
682  result.max[i] = base::min MI_PREVENT_MACRO_EXPAND (bbox1.max[i], bbox2.max[i]);
683  if (result.max[i] < result.min[i]) { // the bbox is empty
684  result.clear();
685  return result;
686  }
687  }
688 
689  return result;
690 }
691 
704 template <typename TT, typename T>
705 Bbox<T,3> transform_point( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
706 
707 
716 template <typename TT, typename T>
717 Bbox<T,3> transform_vector( const Matrix<TT,4,4>& mat, const Bbox<T,3>& bbox);
718 
719 
720 
721 //------ Definitions of non-inline function -----------------------------------
722 
723 #ifndef MI_FOR_DOXYGEN_ONLY
724 
725 template <typename T, Size DIM>
726 template <typename InputIterator>
727 void Bbox<T,DIM>::insert( InputIterator first, InputIterator last)
728 {
729  for( ; first != last; ++first)
730  insert( *first);
731 }
732 
733 template <typename T, Size DIM>
734 template <typename InputIterator>
735 Bbox<T,DIM>::Bbox( InputIterator first, InputIterator last)
736 {
737  clear();
738  insert( first, last);
739 }
740 
741 template <typename T, Size DIM>
742 void Bbox<T, DIM>::robust_grow( T eps)
743 {
744  // Just enlarging the bounding box by epsilon * (largest box extent) is not sufficient, since
745  // there may be cancelation errors if the box is far away from the origin. Hence we take into
746  // account the distance of the box from the origin: the further the box is away, the larger we
747  // have to make it. We just add the two contributions. If we are very far away, then distance
748  // will dominate. For very large boxes, the extent will dominate. We neglect exact weight
749  // factors. We are just a bit less generous with the epsilon to compensate for the extra stuff
750  // we added. If we have objects that in some direction are several orders of magnitude larger
751  // than in the others, this method will not be perfect.
752  //
753  // compute size heuristic for each dimension
754  Vector dist;
755  for( Size i = 0; i < DIM; i++)
756  dist[i] = base::abs(min[i]) + base::abs(max[i])
757  + base::abs(max[i] - min[i]);
758  // compute the grow factor
759  T max_dist = T(0);
760  for( Size i = 0; i < DIM; i++)
761  max_dist = base::max MI_PREVENT_MACRO_EXPAND (max_dist, dist[i]);
762  const T margin = max_dist * eps;
763  // grow the bounding box
764  *this += margin;
765 }
766 
767 #endif // MI_FOR_DOXYGEN_ONLY
768 
769 template <typename TT, typename T>
771 {
772  if( bbox.empty())
773  return bbox;
774 
775  // Transforms all eight corner points, and finds then the bounding box of these eight points.
776  // The corners are computed in an optimized manner which factorizes computations.
777  //
778  // The transformation is decomposed into the transformation of (min,1) and the transformation of
779  // 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).
780  // The transformation of max is the sum of all 4 transformed vectors. The division by the
781  // homogeneous w is deferred to the end.
782  Vector<T,3> corners[8];
783  corners[0] = transform_vector( mat, bbox.min);
784  corners[0].x += T(mat.wx);
785  corners[0].y += T(mat.wy);
786  corners[0].z += T(mat.wz);
787 
788  // difference vectors between min and max
789  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
790  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
791  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
792 
793  corners[1] = corners[0] + dz; // vertex 001
794  corners[2] = corners[0] + dy; // vertex 010
795  corners[3] = corners[0] + dy + dz; // vertex 011
796  corners[4] = corners[0] + dx; // vertex 100
797  corners[5] = corners[0] + dx + dz; // vertex 101
798  corners[6] = corners[0] + dx + dy; // vertex 110
799  corners[7] = corners[0] + dx + dy + dz; // vertex 110
800 
801  // compute the w-coordinates separately. This is done to avoid copying from 4D to 3D vectors.
802  // Again, the computation is decomposed.
803  //
804  // w-coordinate for difference vectors between min and max
805  T wx = T( mat.xw * ((bbox.max).x - (bbox.min).x));
806  T wy = T( mat.yw * ((bbox.max).y - (bbox.min).y));
807  T wz = T( mat.zw * ((bbox.max).z - (bbox.min).z));
808  // w-coordinate for corners
809  T w[8];
810  w[0] = T(mat.xw * (bbox.min).x + mat.yw * (bbox.min).y + mat.zw * (bbox.min).z + mat.ww);
811  w[1] = w[0] + wz; // vertex 001
812  w[2] = w[0] + wy; // vertex 010
813  w[3] = w[0] + wy + wz; // vertex 011
814  w[4] = w[0] + wx; // vertex 100
815  w[5] = w[0] + wx + wz; // vertex 101
816  w[6] = w[0] + wx + wy; // vertex 110
817  w[7] = w[0] + wx + wy + wz; // vertex 111
818 
819  // divide the other coordinates (x,y,z) by w to obtain 3D coordinates
820  for( unsigned int i=0; i<8; ++i) {
821  if( w[i]!=0 && w[i]!=1) {
822  T inv = T(1) / w[i];
823  corners[i].x *= inv;
824  corners[i].y *= inv;
825  corners[i].z *= inv;
826  }
827  }
828  Bbox<T,3> result( corners, corners+8);
829  return result;
830 }
831 
832 template <typename TT, typename T>
834 {
835  // See transform_point() above for implementation notes.
836  if( bbox.empty())
837  return bbox;
838 
839  Vector<T,3> corners[8];
840  corners[0] = transform_vector( mat, (bbox.min));
841 
842  Vector<T,3> dx = transform_vector( mat, Vector<T,3>( (bbox.max).x - (bbox.min).x, 0, 0));
843  Vector<T,3> dy = transform_vector( mat, Vector<T,3>( 0, (bbox.max).y - (bbox.min).y, 0));
844  Vector<T,3> dz = transform_vector( mat, Vector<T,3>( 0, 0, (bbox.max).z - (bbox.min).z));
845 
846  corners[1] = corners[0] + dz;
847  corners[2] = corners[0] + dy;
848  corners[3] = corners[0] + dy + dz;
849  corners[4] = corners[0] + dx;
850  corners[5] = corners[0] + dx + dz;
851  corners[6] = corners[0] + dx + dy;
852  corners[7] = corners[0] + dx + dy + dz;
853 
854  Bbox<T,3> result( corners, corners+8);
855  return result;
856 }
857  // end group mi_math_bbox
859 
860 } // namespace math
861 
862 } // namespace mi
863 
864 #endif // MI_MATH_BBOX_H