1 // Copyright 2009-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3 
4 #pragma once
5 
6 #include "vec2.h"
7 #include "vec3.h"
8 
9 namespace embree
10 {
11   namespace internal {
12 
divideByTwo(const T & v)13     template <typename T> __forceinline T divideByTwo(const T& v) { return v / T(2); }
14     template <> __forceinline float divideByTwo<float>(const float& v) { return v * 0.5f; }
15     template <> __forceinline double divideByTwo<double>(const double& v) { return v * 0.5; }
16 
17   } // namespace internal
18   template<typename T>
19   struct BBox
20   {
21     T lower, upper;
22 
23     ////////////////////////////////////////////////////////////////////////////////
24     /// Construction
25     ////////////////////////////////////////////////////////////////////////////////
26 
BBoxBBox27     __forceinline BBox           ( )                   { }
28     template<typename T1>
BBoxBBox29     __forceinline BBox           ( const BBox<T1>& other ) : lower(other.lower), upper(other.upper) {}
30     __forceinline BBox& operator=( const BBox& other ) { lower = other.lower; upper = other.upper; return *this; }
31 
BBoxBBox32     __forceinline BBox ( const T& v                     ) : lower(v), upper(v) {}
BBoxBBox33     __forceinline BBox ( const T& lower, const T& upper ) : lower(lower), upper(upper) {}
34 
35     ////////////////////////////////////////////////////////////////////////////////
36     /// Extending Bounds
37     ////////////////////////////////////////////////////////////////////////////////
38 
extendBBox39     __forceinline const BBox& extend(const BBox& other) { lower = min(lower,other.lower); upper = max(upper,other.upper); return *this; }
extendBBox40     __forceinline const BBox& extend(const T   & other) { lower = min(lower,other      ); upper = max(upper,other      ); return *this; }
41 
42     /*! tests if box is empty */
emptyBBox43     __forceinline bool empty() const { for (int i=0; i<T::N; i++) if (lower[i] > upper[i]) return true; return false; }
44 
45     /*! computes the size of the box */
sizeBBox46     __forceinline T size() const { return upper - lower; }
47 
48     /*! computes the center of the box */
centerBBox49     __forceinline T center() const { return internal::divideByTwo<T>(lower+upper); }
50 
51     /*! computes twice the center of the box */
center2BBox52     __forceinline T center2() const { return lower+upper; }
53 
54     /*! merges two boxes */
mergeBBox55     __forceinline static const BBox merge (const BBox& a, const BBox& b) {
56       return BBox(min(a.lower, b.lower), max(a.upper, b.upper));
57     }
58 
59      /*! enlarge box by some scaling factor */
enlarge_byBBox60     __forceinline BBox enlarge_by(const float a) const {
61       return BBox(lower - T(a)*abs(lower), upper + T(a)*abs(upper));
62     }
63 
64     ////////////////////////////////////////////////////////////////////////////////
65     /// Constants
66     ////////////////////////////////////////////////////////////////////////////////
67 
BBoxBBox68     __forceinline BBox( EmptyTy ) : lower(pos_inf), upper(neg_inf) {}
BBoxBBox69     __forceinline BBox( FullTy  ) : lower(neg_inf), upper(pos_inf) {}
BBoxBBox70     __forceinline BBox( FalseTy ) : lower(pos_inf), upper(neg_inf) {}
BBoxBBox71     __forceinline BBox( TrueTy  ) : lower(neg_inf), upper(pos_inf) {}
BBoxBBox72     __forceinline BBox( NegInfTy ): lower(pos_inf), upper(neg_inf) {}
BBoxBBox73     __forceinline BBox( PosInfTy ): lower(neg_inf), upper(pos_inf) {}
74   };
75 
empty()76   template<> __forceinline bool BBox<float>::empty() const {
77     return lower > upper;
78   }
79 
80 #if defined(__SSE__)
empty()81   template<> __forceinline bool BBox<Vec3fa>::empty() const {
82     return !all(le_mask(lower,upper));
83   }
empty()84   template<> __forceinline bool BBox<Vec3fx>::empty() const {
85     return !all(le_mask(lower,upper));
86   }
87 #endif
88 
89   /*! tests if box is finite */
isvalid(const BBox<Vec3fa> & v)90   __forceinline bool isvalid( const BBox<Vec3fa>& v ) {
91     return all(gt_mask(v.lower,Vec3fa_t(-FLT_LARGE)) & lt_mask(v.upper,Vec3fa_t(+FLT_LARGE)));
92   }
93 
94   /*! tests if box is finite and non-empty*/
isvalid_non_empty(const BBox<Vec3fa> & v)95   __forceinline bool isvalid_non_empty( const BBox<Vec3fa>& v ) {
96     return all(gt_mask(v.lower,Vec3fa_t(-FLT_LARGE)) & lt_mask(v.upper,Vec3fa_t(+FLT_LARGE)) & le_mask(v.lower,v.upper));
97   }
98 
99   /*! tests if box has finite entries */
is_finite(const BBox<Vec3fa> & b)100   __forceinline bool is_finite( const BBox<Vec3fa>& b) {
101     return is_finite(b.lower) && is_finite(b.upper);
102   }
103 
104   /*! test if point contained in box */
inside(const BBox<Vec3fa> & b,const Vec3fa & p)105   __forceinline bool inside ( const BBox<Vec3fa>& b, const Vec3fa& p ) { return all(ge_mask(p,b.lower) & le_mask(p,b.upper)); }
106 
107   /*! computes the center of the box */
center2(const BBox<T> & box)108   template<typename T> __forceinline const T center2(const BBox<T>& box) { return box.lower + box.upper; }
center(const BBox<T> & box)109   template<typename T> __forceinline const T center (const BBox<T>& box) { return internal::divideByTwo<T>(center2(box)); }
110 
111   /*! computes the volume of a bounding box */
volume(const BBox<Vec3fa> & b)112   __forceinline float volume    ( const BBox<Vec3fa>& b ) { return reduce_mul(b.size()); }
safeVolume(const BBox<Vec3fa> & b)113   __forceinline float safeVolume( const BBox<Vec3fa>& b ) { if (b.empty()) return 0.0f; else return volume(b); }
114 
115   /*! computes the volume of a bounding box */
volume(const BBox<Vec3f> & b)116   __forceinline float volume( const BBox<Vec3f>& b )  { return reduce_mul(b.size()); }
117 
118   /*! computes the surface area of a bounding box */
area(const BBox<Vec2<T>> & b)119   template<typename T> __forceinline const T area( const BBox<Vec2<T> >& b ) { const Vec2<T> d = b.size(); return d.x*d.y; }
120 
halfArea(const BBox<Vec3<T>> & b)121   template<typename T> __forceinline const T halfArea( const BBox<Vec3<T> >& b ) { return halfArea(b.size()); }
area(const BBox<Vec3<T>> & b)122   template<typename T> __forceinline const T     area( const BBox<Vec3<T> >& b ) { return T(2)*halfArea(b); }
123 
halfArea(const BBox<Vec3fa> & b)124   __forceinline float halfArea( const BBox<Vec3fa>& b ) { return halfArea(b.size()); }
area(const BBox<Vec3fa> & b)125   __forceinline float     area( const BBox<Vec3fa>& b ) { return 2.0f*halfArea(b); }
126 
halfArea(const BBox<Vec3fx> & b)127   __forceinline float halfArea( const BBox<Vec3fx>& b ) { return halfArea(b.size()); }
area(const BBox<Vec3fx> & b)128   __forceinline float     area( const BBox<Vec3fx>& b ) { return 2.0f*halfArea(b); }
129 
safeArea(const BBox<Vec> & b)130   template<typename Vec> __forceinline float safeArea( const BBox<Vec>& b ) { if (b.empty()) return 0.0f; else return area(b); }
131 
expectedApproxHalfArea(const BBox<T> & box)132   template<typename T> __forceinline float expectedApproxHalfArea(const BBox<T>& box) {
133     return halfArea(box);
134   }
135 
136   /*! merges bounding boxes and points */
merge(const BBox<T> & a,const T & b)137   template<typename T> __forceinline const BBox<T> merge( const BBox<T>& a, const       T& b ) { return BBox<T>(min(a.lower, b    ), max(a.upper, b    )); }
merge(const T & a,const BBox<T> & b)138   template<typename T> __forceinline const BBox<T> merge( const       T& a, const BBox<T>& b ) { return BBox<T>(min(a    , b.lower), max(a    , b.upper)); }
merge(const BBox<T> & a,const BBox<T> & b)139   template<typename T> __forceinline const BBox<T> merge( const BBox<T>& a, const BBox<T>& b ) { return BBox<T>(min(a.lower, b.lower), max(a.upper, b.upper)); }
140 
141   /*! Merges three boxes. */
merge(const BBox<T> & a,const BBox<T> & b,const BBox<T> & c)142   template<typename T> __forceinline const BBox<T> merge( const BBox<T>& a, const BBox<T>& b, const BBox<T>& c ) { return merge(a,merge(b,c)); }
143 
144   /*! Merges four boxes. */
merge(const BBox<T> & a,const BBox<T> & b,const BBox<T> & c,const BBox<T> & d)145   template<typename T> __forceinline BBox<T> merge(const BBox<T>& a, const BBox<T>& b, const BBox<T>& c, const BBox<T>& d) {
146     return merge(merge(a,b),merge(c,d));
147   }
148 
149   /*! Comparison Operators */
150   template<typename T> __forceinline bool operator==( const BBox<T>& a, const BBox<T>& b ) { return a.lower == b.lower && a.upper == b.upper; }
151   template<typename T> __forceinline bool operator!=( const BBox<T>& a, const BBox<T>& b ) { return a.lower != b.lower || a.upper != b.upper; }
152 
153   /*! scaling */
154   template<typename T> __forceinline BBox<T> operator *( const float& a, const BBox<T>& b ) { return BBox<T>(a*b.lower,a*b.upper); }
155   template<typename T> __forceinline BBox<T> operator *( const     T& a, const BBox<T>& b ) { return BBox<T>(a*b.lower,a*b.upper); }
156 
157   /*! translations */
158   template<typename T> __forceinline BBox<T> operator +( const BBox<T>& a, const BBox<T>& b ) { return BBox<T>(a.lower+b.lower,a.upper+b.upper); }
159   template<typename T> __forceinline BBox<T> operator -( const BBox<T>& a, const BBox<T>& b ) { return BBox<T>(a.lower-b.lower,a.upper-b.upper); }
160   template<typename T> __forceinline BBox<T> operator +( const BBox<T>& a, const      T & b ) { return BBox<T>(a.lower+b      ,a.upper+b      ); }
161   template<typename T> __forceinline BBox<T> operator -( const BBox<T>& a, const      T & b ) { return BBox<T>(a.lower-b      ,a.upper-b      ); }
162 
163   /*! extension */
enlarge(const BBox<T> & a,const T & b)164   template<typename T> __forceinline BBox<T> enlarge(const BBox<T>& a, const T& b) { return BBox<T>(a.lower-b, a.upper+b); }
165 
166   /*! intersect bounding boxes */
intersect(const BBox<T> & a,const BBox<T> & b)167   template<typename T> __forceinline const BBox<T> intersect( const BBox<T>& a, const BBox<T>& b ) { return BBox<T>(max(a.lower, b.lower), min(a.upper, b.upper)); }
intersect(const BBox<T> & a,const BBox<T> & b,const BBox<T> & c)168   template<typename T> __forceinline const BBox<T> intersect( const BBox<T>& a, const BBox<T>& b, const BBox<T>& c ) { return intersect(a,intersect(b,c)); }
intersect(const BBox<T> & a,const BBox<T> & b,const BBox<T> & c,const BBox<T> & d)169   template<typename T> __forceinline const BBox<T> intersect( const BBox<T>& a, const BBox<T>& b, const BBox<T>& c, const BBox<T>& d ) { return intersect(intersect(a,b),intersect(c,d)); }
170 
171   /*! subtract bounds from each other */
subtract(const BBox<T> & a,const BBox<T> & b,BBox<T> & c,BBox<T> & d)172   template<typename T> __forceinline void subtract(const BBox<T>& a, const BBox<T>& b, BBox<T>& c, BBox<T>& d)
173   {
174     c.lower = a.lower;
175     c.upper = min(a.upper,b.lower);
176     d.lower = max(a.lower,b.upper);
177     d.upper = a.upper;
178   }
179 
180   /*! tests if bounding boxes (and points) are disjoint (empty intersection) */
disjoint(const BBox<T> & a,const BBox<T> & b)181   template<typename T> __inline bool disjoint( const BBox<T>& a, const BBox<T>& b ) { return intersect(a,b).empty(); }
disjoint(const BBox<T> & a,const T & b)182   template<typename T> __inline bool disjoint( const BBox<T>& a, const       T& b ) { return disjoint(a,BBox<T>(b)); }
disjoint(const T & a,const BBox<T> & b)183   template<typename T> __inline bool disjoint( const       T& a, const BBox<T>& b ) { return disjoint(BBox<T>(a),b); }
184 
185   /*! tests if bounding boxes (and points) are conjoint (non-empty intersection) */
conjoint(const BBox<T> & a,const BBox<T> & b)186   template<typename T> __inline bool conjoint( const BBox<T>& a, const BBox<T>& b ) { return !intersect(a,b).empty(); }
conjoint(const BBox<T> & a,const T & b)187   template<typename T> __inline bool conjoint( const BBox<T>& a, const       T& b ) { return conjoint(a,BBox<T>(b)); }
conjoint(const T & a,const BBox<T> & b)188   template<typename T> __inline bool conjoint( const       T& a, const BBox<T>& b ) { return conjoint(BBox<T>(a),b); }
189 
190   /*! subset relation */
subset(const BBox<T> & a,const BBox<T> & b)191   template<typename T> __inline bool subset( const BBox<T>& a, const BBox<T>& b )
192   {
193     for ( size_t i = 0; i < T::N; i++ ) if ( a.lower[i] < b.lower[i] ) return false;
194     for ( size_t i = 0; i < T::N; i++ ) if ( a.upper[i] > b.upper[i] ) return false;
195     return true;
196   }
197 
subset(const BBox<Vec3fa> & a,const BBox<Vec3fa> & b)198   template<> __inline bool subset( const BBox<Vec3fa>& a, const BBox<Vec3fa>& b ) {
199     return all(ge_mask(a.lower,b.lower)) & all(le_mask(a.upper,b.upper));
200   }
201 
subset(const BBox<Vec3fx> & a,const BBox<Vec3fx> & b)202   template<> __inline bool subset( const BBox<Vec3fx>& a, const BBox<Vec3fx>& b ) {
203     return all(ge_mask(a.lower,b.lower)) & all(le_mask(a.upper,b.upper));
204   }
205 
206   /*! blending */
207   template<typename T>
lerp(const BBox<T> & b0,const BBox<T> & b1,const float t)208     __forceinline BBox<T> lerp(const BBox<T>& b0, const BBox<T>& b1, const float t) {
209     return BBox<T>(lerp(b0.lower,b1.lower,t),lerp(b0.upper,b1.upper,t));
210   }
211 
212   /*! output operator */
213   template<typename T> __forceinline embree_ostream operator<<(embree_ostream cout, const BBox<T>& box) {
214     return cout << "[" << box.lower << "; " << box.upper << "]";
215   }
216 
217   /*! default template instantiations */
218   typedef BBox<float> BBox1f;
219   typedef BBox<Vec2f> BBox2f;
220   typedef BBox<Vec2fa> BBox2fa;
221   typedef BBox<Vec3f> BBox3f;
222   typedef BBox<Vec3fa> BBox3fa;
223   typedef BBox<Vec3fx> BBox3fx;
224   typedef BBox<Vec3ff> BBox3ff;
225 }
226 
227 ////////////////////////////////////////////////////////////////////////////////
228 /// SSE / AVX / MIC specializations
229 ////////////////////////////////////////////////////////////////////////////////
230 
231 #if defined __SSE__
232 #include "../simd/sse.h"
233 #endif
234 
235 #if defined __AVX__
236 #include "../simd/avx.h"
237 #endif
238 
239 #if defined(__AVX512F__)
240 #include "../simd/avx512.h"
241 #endif
242 
243 namespace embree
244 {
245   template<int N>
246     __forceinline BBox<Vec3<vfloat<N>>> transpose(const BBox3fa* bounds);
247 
248   template<>
249     __forceinline BBox<Vec3<vfloat4>> transpose<4>(const BBox3fa* bounds)
250   {
251     BBox<Vec3<vfloat4>> dest;
252 
253     transpose((vfloat4&)bounds[0].lower,
254               (vfloat4&)bounds[1].lower,
255               (vfloat4&)bounds[2].lower,
256               (vfloat4&)bounds[3].lower,
257               dest.lower.x,
258               dest.lower.y,
259               dest.lower.z);
260 
261     transpose((vfloat4&)bounds[0].upper,
262               (vfloat4&)bounds[1].upper,
263               (vfloat4&)bounds[2].upper,
264               (vfloat4&)bounds[3].upper,
265               dest.upper.x,
266               dest.upper.y,
267               dest.upper.z);
268 
269     return dest;
270   }
271 
272 #if defined(__AVX__)
273   template<>
274     __forceinline BBox<Vec3<vfloat8>> transpose<8>(const BBox3fa* bounds)
275   {
276     BBox<Vec3<vfloat8>> dest;
277 
278     transpose((vfloat4&)bounds[0].lower,
279               (vfloat4&)bounds[1].lower,
280               (vfloat4&)bounds[2].lower,
281               (vfloat4&)bounds[3].lower,
282               (vfloat4&)bounds[4].lower,
283               (vfloat4&)bounds[5].lower,
284               (vfloat4&)bounds[6].lower,
285               (vfloat4&)bounds[7].lower,
286               dest.lower.x,
287               dest.lower.y,
288               dest.lower.z);
289 
290     transpose((vfloat4&)bounds[0].upper,
291               (vfloat4&)bounds[1].upper,
292               (vfloat4&)bounds[2].upper,
293               (vfloat4&)bounds[3].upper,
294               (vfloat4&)bounds[4].upper,
295               (vfloat4&)bounds[5].upper,
296               (vfloat4&)bounds[6].upper,
297               (vfloat4&)bounds[7].upper,
298               dest.upper.x,
299               dest.upper.y,
300               dest.upper.z);
301 
302     return dest;
303   }
304 #endif
305 
306   template<int N>
307     __forceinline BBox3fa merge(const BBox3fa* bounds);
308 
309   template<>
310     __forceinline BBox3fa merge<4>(const BBox3fa* bounds)
311   {
312     const Vec3fa lower = min(min(bounds[0].lower,bounds[1].lower),
313                              min(bounds[2].lower,bounds[3].lower));
314     const Vec3fa upper = max(max(bounds[0].upper,bounds[1].upper),
315                              max(bounds[2].upper,bounds[3].upper));
316     return BBox3fa(lower,upper);
317   }
318 
319 #if defined(__AVX__)
320   template<>
321     __forceinline BBox3fa merge<8>(const BBox3fa* bounds)
322   {
323     const Vec3fa lower = min(min(min(bounds[0].lower,bounds[1].lower),min(bounds[2].lower,bounds[3].lower)),
324                              min(min(bounds[4].lower,bounds[5].lower),min(bounds[6].lower,bounds[7].lower)));
325     const Vec3fa upper = max(max(max(bounds[0].upper,bounds[1].upper),max(bounds[2].upper,bounds[3].upper)),
326                              max(max(bounds[4].upper,bounds[5].upper),max(bounds[6].upper,bounds[7].upper)));
327     return BBox3fa(lower,upper);
328   }
329 #endif
330 }
331 
332