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
9namespace embree
10{
11 template<typename T>
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:
24 __forceinline LBBox () {}
25
26 template<typename T1>
27 __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
34 __forceinline LBBox (EmptyTy)
35 : bounds0(EmptyTy()), bounds1(EmptyTy()) {}
36
37 __forceinline explicit LBBox ( const BBox<T>& bounds)
38 : bounds0(bounds), bounds1(bounds) { }
39
40 __forceinline LBBox ( const BBox<T>& bounds0, const BBox<T>& bounds1)
41 : bounds0(bounds0), bounds1(bounds1) { }
42
43 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>
62 __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>
102 __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>
152 __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
184 __forceinline bool empty() const {
185 return bounds().empty();
186 }
187
188 __forceinline BBox<T> bounds () const {
189 return merge(bounds0,bounds1);
190 }
191
192 __forceinline BBox<T> interpolate( const float t ) const {
193 return lerp(bounds0,bounds1,t);
194 }
195
196 __forceinline LBBox<T> interpolate( const BBox1f& dt ) const {
197 return LBBox<T>(interpolate(dt.lower),interpolate(dt.upper));
198 }
199
200 __forceinline void extend( const LBBox& other ) {
201 bounds0.extend(other.bounds0);
202 bounds1.extend(other.bounds1);
203 }
204
205 __forceinline float expectedHalfArea() const;
206
207 __forceinline float expectedHalfArea(const BBox1f& dt) const {
208 return interpolate(dt).expectedHalfArea();
209 }
210
211 __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 */
216 __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>
241 __forceinline bool isvalid( const LBBox<T>& v ) {
242 return isvalid(v.bounds0) && isvalid(v.bounds1);
243 }
244
245 template<typename T>
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>
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
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>
269 __forceinline float expectedApproxHalfArea(const LBBox<T>& box) {
270 return box.expectedApproxHalfArea();
271 }
272
273 template<typename T>
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 */
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