1 // Copyright 2009-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3 
4 #pragma once
5 
6 #include "bbox.h"
7 #include "range.h"
8 
9 namespace embree
10 {
11   template<typename T>
globalLinear(const std::pair<T,T> & v,const BBox1f & dt)12     __forceinline std::pair<T,T> globalLinear(const std::pair<T,T>& v, const BBox1f& dt)
13   {
14     const float rcp_dt_size = float(1.0f)/dt.size();
15     const T g0 = lerp(v.first,v.second,-dt.lower*rcp_dt_size);
16     const T g1 = lerp(v.first,v.second,(1.0f-dt.lower)*rcp_dt_size);
17     return std::make_pair(g0,g1);
18   }
19 
20   template<typename T>
21   struct LBBox
22   {
23   public:
LBBoxLBBox24     __forceinline LBBox () {}
25 
26     template<typename T1>
LBBoxLBBox27     __forceinline LBBox ( const LBBox<T1>& other )
28     : bounds0(other.bounds0), bounds1(other.bounds1) {}
29 
30     __forceinline LBBox& operator= ( const LBBox& other ) {
31       bounds0 = other.bounds0; bounds1 = other.bounds1; return *this;
32     }
33 
LBBoxLBBox34     __forceinline LBBox (EmptyTy)
35       : bounds0(EmptyTy()), bounds1(EmptyTy()) {}
36 
LBBoxLBBox37     __forceinline explicit LBBox ( const BBox<T>& bounds)
38       : bounds0(bounds), bounds1(bounds) { }
39 
LBBoxLBBox40     __forceinline LBBox ( const BBox<T>& bounds0, const BBox<T>& bounds1)
41       : bounds0(bounds0), bounds1(bounds1) { }
42 
LBBoxLBBox43     LBBox ( const avector<BBox<T>>& bounds )
44     {
45       assert(bounds.size());
46       BBox<T> b0 = bounds.front();
47       BBox<T> b1 = bounds.back();
48       for (size_t i=1; i<bounds.size()-1; i++) {
49         const float f = float(i)/float(bounds.size()-1);
50         const BBox<T> bt = lerp(b0,b1,f);
51         const T dlower = min(bounds[i].lower-bt.lower,T(zero));
52         const T dupper = max(bounds[i].upper-bt.upper,T(zero));
53         b0.lower += dlower; b1.lower += dlower;
54         b0.upper += dupper; b1.upper += dupper;
55       }
56       bounds0 = b0;
57       bounds1 = b1;
58     }
59 
60     /*! calculates the linear bounds of a primitive for the specified time range */
61     template<typename BoundsFunc>
LBBoxLBBox62     __forceinline LBBox(const BoundsFunc& bounds, const BBox1f& time_range, float numTimeSegments)
63     {
64       const float lower = time_range.lower*numTimeSegments;
65       const float upper = time_range.upper*numTimeSegments;
66       const float ilowerf = floor(lower);
67       const float iupperf = ceil(upper);
68       const int ilower = (int)ilowerf;
69       const int iupper = (int)iupperf;
70 
71       const BBox<T> blower0 = bounds(ilower);
72       const BBox<T> bupper1 = bounds(iupper);
73 
74       if (iupper-ilower == 1) {
75         bounds0 = lerp(blower0, bupper1, lower-ilowerf);
76         bounds1 = lerp(bupper1, blower0, iupperf-upper);
77         return;
78       }
79 
80       const BBox<T> blower1 = bounds(ilower+1);
81       const BBox<T> bupper0 = bounds(iupper-1);
82       BBox<T> b0 = lerp(blower0, blower1, lower-ilowerf);
83       BBox<T> b1 = lerp(bupper1, bupper0, iupperf-upper);
84 
85       for (int i = ilower+1; i < iupper; i++)
86       {
87         const float f = (float(i)/numTimeSegments - time_range.lower) / time_range.size();
88         const BBox<T> bt = lerp(b0, b1, f);
89         const BBox<T> bi = bounds(i);
90         const T dlower = min(bi.lower-bt.lower, T(zero));
91         const T dupper = max(bi.upper-bt.upper, T(zero));
92         b0.lower += dlower; b1.lower += dlower;
93         b0.upper += dupper; b1.upper += dupper;
94       }
95 
96       bounds0 = b0;
97       bounds1 = b1;
98     }
99 
100     /*! calculates the linear bounds of a primitive for the specified time range */
101     template<typename BoundsFunc>
LBBoxLBBox102     __forceinline LBBox(const BoundsFunc& bounds, const BBox1f& time_range_in, const BBox1f& geom_time_range, float geom_time_segments)
103     {
104       /* normalize global time_range_in to local geom_time_range */
105       const BBox1f time_range((time_range_in.lower-geom_time_range.lower)/geom_time_range.size(),
106                               (time_range_in.upper-geom_time_range.lower)/geom_time_range.size());
107 
108       const float lower = time_range.lower*geom_time_segments;
109       const float upper = time_range.upper*geom_time_segments;
110       const float ilowerf = floor(lower);
111       const float iupperf = ceil(upper);
112       const float ilowerfc = max(0.0f,ilowerf);
113       const float iupperfc = min(iupperf,geom_time_segments);
114       const int   ilowerc = (int)ilowerfc;
115       const int   iupperc = (int)iupperfc;
116       assert(iupperc-ilowerc > 0);
117 
118       /* this larger iteration range guarantees that we process borders of geom_time_range is (partially) inside time_range_in */
119       const int ilower_iter = max(-1,(int)ilowerf);
120       const int iupper_iter = min((int)iupperf,(int)geom_time_segments+1);
121 
122       const BBox<T> blower0 = bounds(ilowerc);
123       const BBox<T> bupper1 = bounds(iupperc);
124       if (iupper_iter-ilower_iter == 1) {
125         bounds0 = lerp(blower0, bupper1, max(0.0f,lower-ilowerfc));
126         bounds1 = lerp(bupper1, blower0, max(0.0f,iupperfc-upper));
127         return;
128       }
129 
130       const BBox<T> blower1 = bounds(ilowerc+1);
131       const BBox<T> bupper0 = bounds(iupperc-1);
132       BBox<T> b0 = lerp(blower0, blower1, max(0.0f,lower-ilowerfc));
133       BBox<T> b1 = lerp(bupper1, bupper0, max(0.0f,iupperfc-upper));
134 
135       for (int i = ilower_iter+1; i < iupper_iter; i++)
136       {
137         const float f = (float(i)/geom_time_segments - time_range.lower) / time_range.size();
138         const BBox<T> bt = lerp(b0, b1, f);
139         const BBox<T> bi = bounds(i);
140         const T dlower = min(bi.lower-bt.lower, T(zero));
141         const T dupper = max(bi.upper-bt.upper, T(zero));
142         b0.lower += dlower; b1.lower += dlower;
143         b0.upper += dupper; b1.upper += dupper;
144       }
145 
146       bounds0 = b0;
147       bounds1 = b1;
148     }
149 
150     /*! calculates the linear bounds of a primitive for the specified time range */
151     template<typename BoundsFunc>
LBBoxLBBox152     __forceinline LBBox(const BoundsFunc& bounds, const range<int>& time_range, int numTimeSegments)
153     {
154       const int ilower = time_range.begin();
155       const int iupper = time_range.end();
156 
157       BBox<T> b0 = bounds(ilower);
158       BBox<T> b1 = bounds(iupper);
159 
160       if (iupper-ilower == 1)
161       {
162         bounds0 = b0;
163         bounds1 = b1;
164         return;
165       }
166 
167       for (int i = ilower+1; i<iupper; i++)
168       {
169         const float f = float(i - time_range.begin()) / float(time_range.size());
170         const BBox<T> bt = lerp(b0, b1, f);
171         const BBox<T> bi = bounds(i);
172         const T dlower = min(bi.lower-bt.lower, T(zero));
173         const T dupper = max(bi.upper-bt.upper, T(zero));
174         b0.lower += dlower; b1.lower += dlower;
175         b0.upper += dupper; b1.upper += dupper;
176       }
177 
178       bounds0 = b0;
179       bounds1 = b1;
180     }
181 
182   public:
183 
emptyLBBox184     __forceinline bool empty() const {
185       return bounds().empty();
186     }
187 
boundsLBBox188     __forceinline BBox<T> bounds () const {
189       return merge(bounds0,bounds1);
190     }
191 
interpolateLBBox192     __forceinline BBox<T> interpolate( const float t ) const {
193       return lerp(bounds0,bounds1,t);
194     }
195 
interpolateLBBox196     __forceinline LBBox<T> interpolate( const BBox1f& dt ) const {
197       return LBBox<T>(interpolate(dt.lower),interpolate(dt.upper));
198     }
199 
extendLBBox200     __forceinline void extend( const LBBox& other ) {
201       bounds0.extend(other.bounds0);
202       bounds1.extend(other.bounds1);
203     }
204 
205     __forceinline float expectedHalfArea() const;
206 
expectedHalfAreaLBBox207     __forceinline float expectedHalfArea(const BBox1f& dt) const {
208       return interpolate(dt).expectedHalfArea();
209     }
210 
expectedApproxHalfAreaLBBox211     __forceinline float expectedApproxHalfArea() const {
212       return 0.5f*(halfArea(bounds0) + halfArea(bounds1));
213     }
214 
215     /* calculates bounds for [0,1] time range from bounds in dt time range */
globalLBBox216     __forceinline LBBox global(const BBox1f& dt) const
217     {
218       const float rcp_dt_size = 1.0f/dt.size();
219       const BBox<T> b0 = interpolate(-dt.lower*rcp_dt_size);
220       const BBox<T> b1 = interpolate((1.0f-dt.lower)*rcp_dt_size);
221       return LBBox(b0,b1);
222     }
223 
224     /*! Comparison Operators */
225     //template<typename TT> friend __forceinline bool operator==( const LBBox<TT>& a, const LBBox<TT>& b ) { return a.bounds0 == b.bounds0 && a.bounds1 == b.bounds1; }
226     //template<typename TT> friend __forceinline bool operator!=( const LBBox<TT>& a, const LBBox<TT>& b ) { return a.bounds0 != b.bounds0 || a.bounds1 != b.bounds1; }
227     friend __forceinline bool operator==( const LBBox& a, const LBBox& b ) { return a.bounds0 == b.bounds0 && a.bounds1 == b.bounds1; }
228     friend __forceinline bool operator!=( const LBBox& a, const LBBox& b ) { return a.bounds0 != b.bounds0 || a.bounds1 != b.bounds1; }
229 
230     /*! output operator */
231     friend __forceinline embree_ostream operator<<(embree_ostream cout, const LBBox& box) {
232       return cout << "LBBox { " << box.bounds0 << "; " << box.bounds1 << " }";
233     }
234 
235   public:
236     BBox<T> bounds0, bounds1;
237   };
238 
239   /*! tests if box is finite */
240   template<typename T>
isvalid(const LBBox<T> & v)241     __forceinline bool isvalid( const LBBox<T>& v ) {
242     return isvalid(v.bounds0) && isvalid(v.bounds1);
243   }
244 
245   template<typename T>
isvalid_non_empty(const LBBox<T> & v)246     __forceinline bool isvalid_non_empty( const LBBox<T>& v ) {
247     return isvalid_non_empty(v.bounds0) && isvalid_non_empty(v.bounds1);
248   }
249 
250   template<typename T>
expectedArea(const T & a0,const T & a1,const T & b0,const T & b1)251     __forceinline T expectedArea(const T& a0, const T& a1, const T& b0, const T& b1)
252   {
253     const T da = a1-a0;
254     const T db = b1-b0;
255     return a0*b0+(a0*db+da*b0)*T(0.5f) + da*db*T(1.0f/3.0f);
256   }
257 
expectedHalfArea()258   template<> __forceinline float LBBox<Vec3fa>::expectedHalfArea() const
259   {
260     const Vec3fa d0 = bounds0.size();
261     const Vec3fa d1 = bounds1.size();
262     return reduce_add(expectedArea(Vec3fa(d0.x,d0.y,d0.z),
263                                    Vec3fa(d1.x,d1.y,d1.z),
264                                    Vec3fa(d0.y,d0.z,d0.x),
265                                    Vec3fa(d1.y,d1.z,d1.x)));
266   }
267 
268   template<typename T>
expectedApproxHalfArea(const LBBox<T> & box)269   __forceinline float expectedApproxHalfArea(const LBBox<T>& box) {
270     return box.expectedApproxHalfArea();
271   }
272 
273   template<typename T>
merge(const LBBox<T> & a,const LBBox<T> & b)274   __forceinline LBBox<T> merge(const LBBox<T>& a, const LBBox<T>& b) {
275     return LBBox<T>(merge(a.bounds0, b.bounds0), merge(a.bounds1, b.bounds1));
276   }
277 
278    /*! subset relation */
subset(const LBBox<T> & a,const LBBox<T> & b)279   template<typename T> __inline bool subset( const LBBox<T>& a, const LBBox<T>& b ) {
280     return subset(a.bounds0,b.bounds0) && subset(a.bounds1,b.bounds1);
281   }
282 
283   /*! default template instantiations */
284   typedef LBBox<float> LBBox1f;
285   typedef LBBox<Vec2f> LBBox2f;
286   typedef LBBox<Vec3f> LBBox3f;
287   typedef LBBox<Vec3fa> LBBox3fa;
288   typedef LBBox<Vec3fx> LBBox3fx;
289 }
290