HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_RTreeBox.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_RTreeBox.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_RTreeBox_H__
12 #define __UT_RTreeBox_H__
13 
14 #include "UT_Vector3.h"
15 #include "UT_BoundingBox.h"
16 #include "UT_Format.h"
17 
18 #include <type_traits>
19 
20 // UT_BoxT represents either an axis-aligned box or the empty set.
21 // UT_BoxT is closed as a set; all operations assume that
22 // the boundary is included.
23 // FT is the number type used to represent the box coordinates,
24 // for example, float or double.
25 
26 // Named constructor tags
27 struct UT_BoxCT
28 {
32 };
33 
34 template< typename FT > class UT_BoxT;
35 
36 // Forward declare friends:
37 template< typename FT > inline void setEmpty( UT_BoxT< FT >& t );
38 
39 template< typename FT >
40 class UT_BoxT
41 {
42 public:
43  using CT = UT_BoxCT;
44  using Scalar = FT;
46 
47  // Default construct: the empty set
48  constexpr UT_BoxT();
49 
50  // Construct box containing a single point position,
51  // which is represented by its array of three coordinates.
52  template< typename U >
53  constexpr explicit UT_BoxT( const U p[3] );
54 
55  template< typename U >
56  constexpr explicit UT_BoxT( const UT_Vector3T< U >& p );
57 
58  constexpr explicit UT_BoxT( const UT_BoundingBox& a );
59 
60  // Construct a bounding box from points in an array-like type 'l_x'
61  // Starting with the empty box,
62  // for each l in [ 0, size ), absorb the point l_x[ l ] in the bounding box.
63  // size == 0 results in the empty set.
64  template< typename POINT_ARRAY >
65  constexpr UT_BoxT( const CT::BoundPointArrayType, POINT_ARRAY&& l_x, const exint size );
66 
67  // Construct a bounding box from points in an array-like type 'l_x'
68  // Starting with the empty box,
69  // for each iterator cit in the half-open range [ begin, end ),
70  // absorb the point l_x[ *cit ] in the bounding box.
71  // end == begin results in the empty set.
72  template< typename CIT, typename POINT_ARRAY >
73  constexpr UT_BoxT( const CT::BoundIndirectRangePointArrayType, POINT_ARRAY&& l_x, const CIT begin, const CIT end );
74 
75  // Construct a bounding box using points given by
76  // a generator function object
77  // Starting with the empty box,
78  // for each l in [ 0, size ), absorb generator( l ) in the bounding box.
79  // size == 0 results in the empty set.
80  template< typename POINT_GENERATOR >
81  constexpr UT_BoxT( const CT::BoundPointGeneratorType, POINT_GENERATOR&& generator, const exint size );
82 
83  UT_BoxT( const UT_BoxT& ) = default;
84  UT_BoxT& operator=( const UT_BoxT& ) = default;
85 
86  // Return whether this represents the empty set
87  constexpr bool isEmpty() const;
88 
89  // Make a box that's a single point
90  template< typename U >
91  void assignPoint(const U p[3]);
92  template< typename U >
93  void assignPoint( const UT_Vector3T<U> p) { assignPoint(p.vec); }
94 
95  // Expand the box just enough so that it contains a point p
96  template< typename U >
97  void absorbPoint(const U p[3]);
98  template< typename U >
99  void absorbPoint( const UT_Vector3T<U> p) { absorbPoint(p.vec); }
100 
101  // Expand the box just enough so that it contains a box b
102  void absorbBox(const UT_BoxT<FT>& b);
103  void absorbBox(const UT_BoundingBox &b);
104 
105  // Expand in the directions of the axes:
106  // In case this is the empty set, the result is still the empty set
107  // This is equivalent to making *this the union of all cubes with
108  // radius l placed at points of the original set.
109  void expandDistance(const FT l);
110 
111  // Get minimum coordinate for given standard axis
112  // Assumes this is not empty!
113  FT getMin(const int c) const;
114 
115  // Get maximum coordinate for given standard axis
116  // Assumes this is not empty!
117  FT getMax(const int c) const;
118 
119  FT3 getSize() const
120  {
121  UT_ASSERT_P( ! isEmpty() );
122 
123  return FT3(
124  (myMax[0]-myMin[0]),
125  (myMax[1]-myMin[1]),
126  (myMax[2]-myMin[2])
127  );
128  }
129 
130  FT getRadius2() const
131  {
132  UT_ASSERT_P( ! isEmpty() );
133 
134  const FT3 h(
135  (myMax[0]-myMin[0]) / 2,
136  (myMax[1]-myMin[1]) / 2,
137  (myMax[2]-myMin[2]) / 2
138  );
139 
140  return h.length2();
141  }
142 
143  FT3 getCenter() const
144  {
145  UT_ASSERT_P( ! isEmpty() );
146 
147  return FT3(
148  (myMin[0]+myMax[0])/2,
149  (myMin[1]+myMax[1])/2,
150  (myMin[2]+myMax[2])/2
151  );
152  }
153 
154  // Return whether a point is contained in the closed set
155  bool contains(const FT p[3]) const;
156 
157  // Return the axis in which the box is the widest.
158  // For the empty set, this always returns axis 0
159  int getLargestAxis() const;
160 
161 private:
162  // This represents set of all points x
163  // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
164  FT myMin[ 3 ];
165  FT myMax[ 3 ];
166 
167  friend void setEmpty <>( UT_BoxT< FT >& t );
168 
169  friend bool intersects( const UT_BoxT< float >& a, const UT_BoxT< float >& b );
170  friend bool intersects( const UT_BoxT< double >& a, const UT_BoxT< double >& b );
171 };
172 
173 // Overload for custom formatting of UT_BoxT with UTformat.
174 template< typename FT >
175 size_t format( char* buffer, size_t buffer_size, const UT_BoxT< FT >& a )
176 {
177  UT::Format::Writer writer( buffer, buffer_size );
179  return f.format(
180  writer, "min[{0}, {1}, {2}]], max[{3}, {4}, {5}]",
181  {
182  a.getMin( 0 ),
183  a.getMin( 1 ),
184  a.getMin( 2 ),
185  a.getMax( 0 ),
186  a.getMax( 1 ),
187  a.getMax( 2 )
188  }
189  );
190 }
191 
192 //TODO: Move below code into UT_RTreeBoxImpl.h
193 
194 namespace UT
195 {
196 
197 // TODO: Move definitions of FT_Least and FT_Greatest
198 // to a separate header and include it here:
199 
200 // Primary template defined for built-in floating point types:
201 // Map type 'FT' to the least possible value of that type
202 template< typename FT >
203 struct FT_Least
204 {
205  constexpr auto operator()() { return std::numeric_limits< FT >::lowest(); }
206 };
207 
208 //template< typename FT > constexpr auto FT_Least_v = FT_Least< FT >{}();
209 
210 // Primary template defined for built-in floating point types:
211 // Map type 'FT' to the greatest possible value of that type
212 template< typename FT >
214 {
215  constexpr auto operator()() { return std::numeric_limits< FT >::max(); }
216 };
217 
218 //template< typename FT > constexpr auto FT_Greatest_v = FT_Greatest< FT >{}();
219 
220 //
221 // Use class specialization on AssignCopyFT3
222 // to make copy-assignment work for UT_BoxT
223 // when the underlying type FT has a deleted copy assignment operator
224 // This is the case, types FT used in $SC and $CLO.
225 // Such types must support "setCopy( dest, source )" instead.
226 //
227 
230 
231 template< typename FT >
232 struct AssignCopyFT3< FT, true >
233 {
234  void operator()( FT ts[ 3 ], const FT as[ 3 ] )
235  {
236  ts[ 0 ] = as[ 0 ];
237  ts[ 1 ] = as[ 1 ];
238  ts[ 2 ] = as[ 2 ];
239  }
240 };
241 
242 template< typename FT >
243 struct AssignCopyFT3< FT, false >
244 {
245  void operator()( FT ts[ 3 ], const FT as[ 3 ] )
246  {
247  setCopy( ts[ 0 ], as[ 0 ] );
248  setCopy( ts[ 1 ], as[ 1 ] );
249  setCopy( ts[ 2 ], as[ 2 ] );
250  }
251 };
252 
255 
256 template< typename FT >
257 struct AssignCoordinatesFT3< FT, true >
258 {
259  void operator()( FT ts[ 3 ], const FT a0, const FT a1, const FT a2 )
260  {
261  ts[ 0 ] = a0;
262  ts[ 1 ] = a1;
263  ts[ 2 ] = a2;
264  }
265 };
266 
267 template< typename FT >
268 struct AssignCoordinatesFT3< FT, false >
269 {
270  void operator()( FT ts[ 3 ], const FT a0, const FT a1, const FT a2 )
271  {
272  setCopy( ts[ 0 ], a0 );
273  setCopy( ts[ 1 ], a1 );
274  setCopy( ts[ 2 ], a2 );
275  }
276 };
277 
278 }
279 // namespace UT
280 
281 template< typename FT >
283  myMin{
287  },
288  myMax{
289  UT::FT_Least< FT >{}(),
290  UT::FT_Least< FT >{}(),
292  }
293 {
294 }
295 
296 template< typename FT >
297 template< typename U >
298 constexpr UT_BoxT< FT >::UT_BoxT( const U p[ 3 ] ) :
299  myMin{
300  FT( p[ 0 ] ),
301  FT( p[ 1 ] ),
302  FT( p[ 2 ] )
303  },
304  myMax{
305  FT( p[ 0 ] ),
306  FT( p[ 1 ] ),
307  FT( p[ 2 ] )
308  }
309 {
310 }
311 
312 template< typename FT >
313 template< typename U >
314 constexpr UT_BoxT< FT >::UT_BoxT( const UT_Vector3T< U >& p ) :
315  myMin{
316  FT( p[ 0 ] ),
317  FT( p[ 1 ] ),
318  FT( p[ 2 ] )
319  },
320  myMax{
321  FT( p[ 0 ] ),
322  FT( p[ 1 ] ),
323  FT( p[ 2 ] )
324  }
325 {
326 }
327 
328 template< typename FT >
329 constexpr UT_BoxT< FT >::UT_BoxT( const UT_BoundingBox& a ) :
330  myMin{
331  a.xmin(),
332  a.ymin(),
333  a.zmin()
334  },
335  myMax{
336  a.xmax(),
337  a.ymax(),
338  a.zmax()
339  }
340 {
341 }
342 
343 template< typename FT >
344 template< typename POINT_ARRAY >
345 constexpr UT_BoxT< FT >::UT_BoxT(
347  POINT_ARRAY&& l_x,
348  const exint size
349 ) :
350  myMin{
354  },
355  myMax{
356  UT::FT_Least< FT >{}(),
357  UT::FT_Least< FT >{}(),
359  }
360 {
361  for( int l = 0; l != size; ++l )
362  {
363  absorbPoint( l_x[ l ] );
364  }
365 }
366 
367 template< typename FT >
368 template< typename CIT, typename POINT_ARRAY >
369 constexpr UT_BoxT< FT >::UT_BoxT(
371  POINT_ARRAY&& l_x,
372  const CIT begin, const CIT end
373 ) :
374  myMin{
378  },
379  myMax{
380  UT::FT_Least< FT >{}(),
381  UT::FT_Least< FT >{}(),
383  }
384 {
385  for( auto cit = begin; cit != end; ++cit )
386  {
387  absorbPoint( l_x[ *cit ] );
388  }
389 }
390 
391 template< typename FT >
392 template< typename POINT_GENERATOR >
393 constexpr UT_BoxT< FT >::UT_BoxT( const CT::BoundPointGeneratorType, POINT_GENERATOR&& generator, const exint size ) :
394  myMin{
398  },
399  myMax{
400  UT::FT_Least< FT >{}(),
401  UT::FT_Least< FT >{}(),
403  }
404 {
405  for( int l = 0; l != size; ++l )
406  {
407  absorbPoint( generator( l ) );
408  }
409 }
410 
411 
412 
413 template< typename FT >
414 constexpr bool UT_BoxT< FT >::isEmpty() const
415 {
416  return(
417  ( myMax[ 0 ] < myMin[ 0 ] ) ||
418  ( myMax[ 1 ] < myMin[ 1 ] ) ||
419  ( myMax[ 2 ] < myMin[ 2 ] )
420  );
421 }
422 
423 template< typename T >
424 template< typename U >
425 inline void UT_BoxT<T>::assignPoint(const U p[3])
426 {
427  myMin[0] = p[0];
428  myMin[1] = p[1];
429  myMin[2] = p[2];
430 
431  myMax[0] = p[0];
432  myMax[1] = p[1];
433  myMax[2] = p[2];
434 }
435 
436 template< typename T >
437 template< typename U >
438 inline void UT_BoxT<T>::absorbPoint(const U p[3])
439 {
440  myMin[0] = (myMin[0] > p[0]) ? p[0] : myMin[0];
441  myMin[1] = (myMin[1] > p[1]) ? p[1] : myMin[1];
442  myMin[2] = (myMin[2] > p[2]) ? p[2] : myMin[2];
443 
444  myMax[0] = (myMax[0] < p[0]) ? p[0] : myMax[0];
445  myMax[1] = (myMax[1] < p[1]) ? p[1] : myMax[1];
446  myMax[2] = (myMax[2] < p[2]) ? p[2] : myMax[2];
447 }
448 
449 template< typename T >
450 inline void UT_BoxT<T>::absorbBox(const UT_BoxT<T>& b)
451 {
452  myMin[0] = (myMin[0] > b.myMin[0]) ? b.myMin[0] : myMin[0];
453  myMin[1] = (myMin[1] > b.myMin[1]) ? b.myMin[1] : myMin[1];
454  myMin[2] = (myMin[2] > b.myMin[2]) ? b.myMin[2] : myMin[2];
455 
456  myMax[0] = (myMax[0] < b.myMax[0]) ? b.myMax[0] : myMax[0];
457  myMax[1] = (myMax[1] < b.myMax[1]) ? b.myMax[1] : myMax[1];
458  myMax[2] = (myMax[2] < b.myMax[2]) ? b.myMax[2] : myMax[2];
459 }
460 
461 template< typename T >
462 inline void UT_BoxT<T>::absorbBox(const UT_BoundingBox &b)
463 {
464  myMin[0] = (myMin[0] > b.xmin()) ? b.xmin() : myMin[0];
465  myMin[1] = (myMin[1] > b.ymin()) ? b.ymin() : myMin[1];
466  myMin[2] = (myMin[2] > b.zmin()) ? b.zmin() : myMin[2];
467 
468  myMax[0] = (myMax[0] < b.xmax()) ? b.xmax() : myMax[0];
469  myMax[1] = (myMax[1] < b.ymax()) ? b.ymax() : myMax[1];
470  myMax[2] = (myMax[2] < b.zmax()) ? b.zmax() : myMax[2];
471 }
472 
473 template< typename T >
474 inline void UT_BoxT<T>::expandDistance(const T l)
475 {
476  if( isEmpty() )
477  return;
478 
479  myMin[0] -= l;
480  myMin[1] -= l;
481  myMin[2] -= l;
482 
483  myMax[0] += l;
484  myMax[1] += l;
485  myMax[2] += l;
486 }
487 
488 template< typename T >
489 inline T UT_BoxT<T>::getMin(const int c) const
490 {
491  UT_ASSERT_P( (0 <= c) && (c < 3) );
492  UT_ASSERT_P( !isEmpty() );
493 
494  return myMin[c];
495 }
496 
497 template< typename T >
498 inline T UT_BoxT<T>::getMax(const int c) const
499 {
500  UT_ASSERT_P( (0 <= c) && (c < 3) );
501  UT_ASSERT_P( !isEmpty() );
502 
503  return myMax[c];
504 }
505 
506 
507 template< typename T >
508 inline bool UT_BoxT<T>::contains(const T p[3]) const
509 {
510  return ( (myMin[0] <= p[0]) && (p[0] <= myMax[0]) &&
511  (myMin[1] <= p[1]) && (p[1] <= myMax[1]) &&
512  (myMin[2] <= p[2]) && (p[2] <= myMax[2]) );
513 }
514 
515 template< typename T >
516 inline int UT_BoxT<T>::getLargestAxis() const
517 {
518  if( isEmpty() )
519  {
520  return 0;
521  }
522 
523  int max_axis(0);
524  T max_length(myMax[0] - myMin[0]);
525 
526  T length(0);
527 
528  length = myMax[1] - myMin[1];
529  if( length > max_length )
530  {
531  max_length = length;
532  max_axis = 1;
533  }
534 
535  length = myMax[2] - myMin[2];
536  if( length > max_length )
537  {
538  max_length = length;
539  max_axis = 2;
540  }
541 
542  return max_axis;
543 }
544 
545 template< typename FT >
546 inline void setEmpty( UT_BoxT< FT >& t )
547 {
549  t.myMin,
553  );
554 
556  t.myMax,
557  UT::FT_Least< FT >{}(),
558  UT::FT_Least< FT >{}(),
560  );
561 }
562 
563 inline bool intersects( const UT_BoxT< double >& a, const UT_BoxT< double >& b )
564 {
565  return (
566  ( SYSmax( a.myMin[0], b.myMin[0] ) <= SYSmin( a.myMax[0], b.myMax[0] ) ) &&
567  ( SYSmax( a.myMin[1], b.myMin[1] ) <= SYSmin( a.myMax[1], b.myMax[1] ) ) &&
568  ( SYSmax( a.myMin[2], b.myMin[2] ) <= SYSmin( a.myMax[2], b.myMax[2] ) )
569  );
570 }
571 
572 inline bool intersects( const UT_BoxT< float >& a, const UT_BoxT< float >& b )
573 {
574  // We have to load from the wrong vector & swizzle or
575  // we risk reading past a page boundary, triggering a fault,
576  // even though we don't use the results of the w() component.
577  v4uf tmax( &a.myMin[2] );
578  v4uf tmin( &a.myMin[0] );
579  tmax = tmax.swizzle<1, 2, 3, 0>();
580 
581  v4uf bmax( &b.myMin[2] );
582  v4uf bmin( &b.myMin[0] );
583  bmax = bmax.swizzle<1, 2, 3, 0>();
584 
585  tmin = vmax(tmin, bmin);
586  tmax = vmin(tmax, bmax);
587  v4uu valid = tmin <= tmax;
588 
589  int validmask;
590  validmask = signbits(valid);
591 
592  return ((validmask & 0x7) == 0x7);
593 }
594 
595 // Return
596 // -1 if center(a)[ axis ] > center(b)[ axis ]
597 // 0 if center(a)[ axis ] == center(b)[ axis ]
598 // 1 if center(a)[ axis ] < center(b)[ axis ]
599 template< typename FT >
600 inline int signAxisCenterComparison(
601  const int axis,
602  const UT_BoxT< FT >& a,
603  const UT_BoxT< FT >& b
604 )
605 {
606  return SYSsignum(
607  ( b.getMin( axis ) + b.getMax( axis ) )
608  -
609  ( a.getMin( axis ) + a.getMax( axis ) )
610  );
611 }
612 
613 #endif
614 
void absorbPoint(const U p[3])
constexpr SYS_FORCE_INLINE T length2() const noexcept
Definition: UT_Vector3.h:356
#define SYSmax(a, b)
Definition: SYS_Math.h:1570
BoundPointArrayType
Definition: UT_RTreeBox.h:29
FT getRadius2() const
Definition: UT_RTreeBox.h:130
constexpr auto operator()()
Definition: UT_RTreeBox.h:205
void operator()(FT ts[3], const FT a0, const FT a1, const FT a2)
Definition: UT_RTreeBox.h:270
void assignPoint(const U p[3])
GLsizei const GLfloat * value
Definition: glcorearb.h:824
constexpr bool isEmpty() const
void absorbPoint(const UT_Vector3T< U > p)
Definition: UT_RTreeBox.h:99
T vec[tuple_size]
Definition: UT_Vector3.h:774
int64 exint
Definition: SYS_Types.h:125
void assignPoint(const UT_Vector3T< U > p)
Definition: UT_RTreeBox.h:93
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
GLuint GLsizei GLsizei * length
Definition: glcorearb.h:795
3D Vector class.
BoundIndirectRangePointArrayType
Definition: UT_RTreeBox.h:30
FT Scalar
Definition: UT_RTreeBox.h:44
constexpr UT_BoxT()
Definition: UT_RTreeBox.h:282
FT3 getCenter() const
Definition: UT_RTreeBox.h:143
GLfloat f
Definition: glcorearb.h:1926
constexpr auto operator()()
Definition: UT_RTreeBox.h:215
Definition: core.h:760
FT getMax(const int c) const
UT_BoxT & operator=(const UT_BoxT &)=default
bool contains(const FT p[3]) const
Definition: VM_SIMD.h:48
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
GLuint GLuint end
Definition: glcorearb.h:475
void setEmpty(UT_BoxT< FT > &t)
Definition: VM_SIMD.h:188
constexpr int SYSsignum(const F a) noexcept
Definition: SYS_Math.h:176
FT getMin(const int c) const
void expandDistance(const FT l)
void operator()(FT ts[3], const FT a0, const FT a1, const FT a2)
Definition: UT_RTreeBox.h:259
void absorbBox(const UT_BoxT< FT > &b)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
size_t format(char *buffer, size_t buffer_size, const UT_BoxT< FT > &a)
Definition: UT_RTreeBox.h:175
GLdouble t
Definition: glad.h:2397
GLsizeiptr size
Definition: glcorearb.h:664
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2002
friend bool intersects(const UT_BoxT< float > &a, const UT_BoxT< float > &b)
UT_Vector3T< FT > FT3
Definition: UT_RTreeBox.h:45
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
Type-safe formatting, modeled on the Python str.format function.
SYS_FORCE_INLINE v4uf swizzle() const
Definition: VM_SIMD.h:335
void operator()(FT ts[3], const FT as[3])
Definition: UT_RTreeBox.h:245
size_t format(W &writer, const char *format, std::initializer_list< ArgValue > args)
void operator()(FT ts[3], const FT as[3])
Definition: UT_RTreeBox.h:234
#define SYSmin(a, b)
Definition: SYS_Math.h:1571
BoundPointGeneratorType
Definition: UT_RTreeBox.h:31
friend void setEmpty(UT_BoxT< FT > &t)
FT3 getSize() const
Definition: UT_RTreeBox.h:119
int getLargestAxis() const
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:558