1 | |
2 | // |
3 | // This source file is part of appleseed. |
4 | // Visit http://appleseedhq.net/ for additional information and resources. |
5 | // |
6 | // This software is released under the MIT license. |
7 | // |
8 | // Copyright (c) 2010-2013 Francois Beaune, Jupiter Jazz Limited |
9 | // Copyright (c) 2014-2017 Francois Beaune, The appleseedhq Organization |
10 | // |
11 | // Permission is hereby granted, free of charge, to any person obtaining a copy |
12 | // of this software and associated documentation files (the "Software"), to deal |
13 | // in the Software without restriction, including without limitation the rights |
14 | // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
15 | // copies of the Software, and to permit persons to whom the Software is |
16 | // furnished to do so, subject to the following conditions: |
17 | // |
18 | // The above copyright notice and this permission notice shall be included in |
19 | // all copies or substantial portions of the Software. |
20 | // |
21 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
22 | // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
23 | // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
24 | // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
25 | // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
26 | // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
27 | // THE SOFTWARE. |
28 | // |
29 | |
30 | #ifndef APPLESEED_FOUNDATION_MATH_AABB_H |
31 | #define APPLESEED_FOUNDATION_MATH_AABB_H |
32 | |
33 | // appleseed.foundation headers. |
34 | #include "foundation/math/minmax.h" |
35 | #include "foundation/math/scalar.h" |
36 | #include "foundation/math/vector.h" |
37 | |
38 | // Imath headers. |
39 | #ifdef APPLESEED_ENABLE_IMATH_INTEROP |
40 | #include "foundation/platform/exrheaderguards.h" |
41 | BEGIN_EXR_INCLUDES |
42 | #include "OpenEXR/ImathBox.h" |
43 | END_EXR_INCLUDES |
44 | #endif |
45 | |
46 | // Standard headers. |
47 | #include <algorithm> |
48 | #include <cassert> |
49 | #include <cmath> |
50 | #include <cstddef> |
51 | #include <limits> |
52 | |
53 | namespace foundation |
54 | { |
55 | |
56 | // |
57 | // N-dimensional axis-aligned bounding box [min, max] class and operations. |
58 | // The boundary of the bounding box is considered to belong to the bounding box. |
59 | // |
60 | |
61 | template <typename T, size_t N> |
62 | class AABB |
63 | { |
64 | public: |
65 | // Value, vector and AABB types. |
66 | typedef T ValueType; |
67 | typedef Vector<T, N> VectorType; |
68 | typedef AABB<T, N> AABBType; |
69 | |
70 | // Dimension. |
71 | static const size_t Dimension = N; |
72 | |
73 | // Bounds. |
74 | VectorType min, max; |
75 | |
76 | // Constructors. |
77 | AABB(); // leave all components uninitialized |
78 | AABB( |
79 | const VectorType& min, // lower bound |
80 | const VectorType& max); // upper bound |
81 | |
82 | // Construct a bounding box from another bounding box of a different type. |
83 | template <typename U> |
84 | AABB(const AABB<U, N>& rhs); |
85 | |
86 | #ifdef APPLESEED_ENABLE_IMATH_INTEROP |
87 | |
88 | // Implicit construction from an Imath::Box. |
89 | AABB(const Imath::Box<typename ImathVecEquivalent<T, N>::Type>& rhs); |
90 | |
91 | // Reinterpret this bounding box as an Imath::Box. |
92 | operator Imath::Box<typename ImathVecEquivalent<T, N>::Type>&(); |
93 | operator const Imath::Box<typename ImathVecEquivalent<T, N>::Type>&() const; |
94 | |
95 | #endif |
96 | |
97 | // Return an invalidated bounding box. |
98 | static AABBType invalid(); |
99 | |
100 | // Compute the intersection between two bounding boxes. |
101 | static AABBType intersect(const AABBType& a, const AABBType& b); |
102 | |
103 | // Return true if two bounding boxes overlap. |
104 | static bool overlap(const AABBType& a, const AABBType& b); |
105 | |
106 | // Return the amount of overlapping between two bounding boxes. |
107 | // Returns 0.0 if the bounding boxes are disjoint, 1.0 if one |
108 | // is contained in the other. |
109 | static ValueType overlap_ratio(const AABBType& a, const AABBType& b); |
110 | |
111 | // Return the ratio of the extent of a to the extent of b. |
112 | static ValueType extent_ratio(const AABBType& a, const AABBType& b); |
113 | |
114 | // Unchecked array subscripting. [0] is min, [1] is max. |
115 | VectorType& operator[](const size_t i); |
116 | const VectorType& operator[](const size_t i) const; |
117 | |
118 | // Invalidate the bounding box (give it a negative volume). |
119 | void invalidate(); |
120 | |
121 | // Insert a point or another bounding box into the bounding box. |
122 | void insert(const VectorType& v); |
123 | void insert(const AABBType& b); |
124 | |
125 | // Grow the bounding box by a fixed amount in every dimension. |
126 | void grow(const VectorType& v); |
127 | |
128 | // Robustly grow the bounding box by a given epsilon factor. |
129 | void robust_grow(const ValueType eps); |
130 | |
131 | // Translate the bounding box. |
132 | void translate(const VectorType& v); |
133 | |
134 | // Return true if the extent of the bounding box is positive or |
135 | // null along all dimensions. |
136 | bool is_valid() const; |
137 | |
138 | // Return the rank of the bounding box (the number of dimensions |
139 | // along which the bounding box has a strictly positive extent). |
140 | size_t rank() const; |
141 | |
142 | // Compute the center of the bounding box. |
143 | VectorType center() const; |
144 | ValueType center(const size_t dim) const; |
145 | |
146 | // Compute the extent of the bounding box. |
147 | VectorType extent() const; |
148 | ValueType extent(const size_t dim) const; |
149 | |
150 | // Return the diameter of the bounding box. |
151 | ValueType diameter() const; |
152 | |
153 | // Return the radius of the bounding box. |
154 | ValueType radius() const; |
155 | |
156 | // Return the volume of the bounding box. |
157 | T volume() const; |
158 | |
159 | // Compute the 2^N corner points of the bounding box. |
160 | size_t get_corner_count() const; |
161 | VectorType compute_corner(const size_t i) const; |
162 | |
163 | // Return true if the bounding box contains a given point. |
164 | bool contains(const VectorType& v) const; |
165 | }; |
166 | |
167 | // Exact inequality and equality tests. |
168 | template <typename T, size_t N> bool operator!=(const AABB<T, N>& lhs, const AABB<T, N>& rhs); |
169 | template <typename T, size_t N> bool operator==(const AABB<T, N>& lhs, const AABB<T, N>& rhs); |
170 | |
171 | // Approximate equality tests. |
172 | template <typename T, size_t N> bool feq(const AABB<T, N>& lhs, const AABB<T, N>& rhs); |
173 | template <typename T, size_t N> bool feq(const AABB<T, N>& lhs, const AABB<T, N>& rhs, const T eps); |
174 | |
175 | // Bounding box arithmetic. |
176 | template <typename T, size_t N> AABB<T, N> operator+ (const AABB<T, N>& lhs, const AABB<T, N>& rhs); |
177 | template <typename T, size_t N> AABB<T, N> operator* (const AABB<T, N>& lhs, const T rhs); |
178 | template <typename T, size_t N> AABB<T, N> operator* (const T lhs, const AABB<T, N>& rhs); |
179 | template <typename T, size_t N> AABB<T, N>& operator+=(AABB<T, N>& lhs, const AABB<T, N>& rhs); |
180 | template <typename T, size_t N> AABB<T, N>& operator*=(AABB<T, N>& lhs, const T rhs); |
181 | |
182 | // Compute the surface area of a 3D bounding box. |
183 | template <typename T> T half_surface_area(const AABB<T, 3>& bbox); |
184 | template <typename T> T surface_area(const AABB<T, 3>& bbox); |
185 | |
186 | |
187 | // |
188 | // Full specializations for 1D, 2D, 3D and 4D vectors of type int, float and double. |
189 | // |
190 | |
191 | typedef AABB<int, 1> AABB1i; |
192 | typedef AABB<size_t, 1> AABB1u; |
193 | typedef AABB<float, 1> AABB1f; |
194 | typedef AABB<double, 1> AABB1d; |
195 | |
196 | typedef AABB<int, 2> AABB2i; |
197 | typedef AABB<size_t, 2> AABB2u; |
198 | typedef AABB<float, 2> AABB2f; |
199 | typedef AABB<double, 2> AABB2d; |
200 | |
201 | typedef AABB<int, 3> AABB3i; |
202 | typedef AABB<size_t, 3> AABB3u; |
203 | typedef AABB<float, 3> AABB3f; |
204 | typedef AABB<double, 3> AABB3d; |
205 | |
206 | typedef AABB<int, 4> AABB4i; |
207 | typedef AABB<size_t, 4> AABB4u; |
208 | typedef AABB<float, 4> AABB4f; |
209 | typedef AABB<double, 4> AABB4d; |
210 | |
211 | |
212 | // |
213 | // N-dimensional axis-aligned bounding box class and operations. |
214 | // |
215 | |
216 | template <typename T, size_t N> |
217 | inline AABB<T, N>::AABB() |
218 | { |
219 | } |
220 | |
221 | template <typename T, size_t N> |
222 | inline AABB<T, N>::AABB( |
223 | const VectorType& min_, |
224 | const VectorType& max_) |
225 | : min(min_) |
226 | , max(max_) |
227 | { |
228 | } |
229 | |
230 | template <typename T, size_t N> |
231 | template <typename U> |
232 | inline AABB<T, N>::AABB(const AABB<U, N>& rhs) |
233 | : min(VectorType(rhs.min)) |
234 | , max(VectorType(rhs.max)) |
235 | { |
236 | } |
237 | |
238 | #ifdef APPLESEED_ENABLE_IMATH_INTEROP |
239 | |
240 | template <typename T, size_t N> |
241 | inline AABB<T, N>::AABB(const Imath::Box<typename ImathVecEquivalent<T, N>::Type>& rhs) |
242 | : min(rhs.min) |
243 | , max(rhs.max) |
244 | { |
245 | } |
246 | |
247 | template <typename T, size_t N> |
248 | inline AABB<T, N>::operator Imath::Box<typename ImathVecEquivalent<T, N>::Type>&() |
249 | { |
250 | return reinterpret_cast<Imath::Box<typename ImathVecEquivalent<T, N>::Type>&>(*this); |
251 | } |
252 | |
253 | template <typename T, size_t N> |
254 | inline AABB<T, N>::operator const Imath::Box<typename ImathVecEquivalent<T, N>::Type>&() const |
255 | { |
256 | return reinterpret_cast<const Imath::Box<typename ImathVecEquivalent<T, N>::Type>&>(*this); |
257 | } |
258 | |
259 | #endif |
260 | |
261 | template <typename T, size_t N> |
262 | inline AABB<T, N> AABB<T, N>::invalid() |
263 | { |
264 | AABB<T, N> bbox; |
265 | bbox.invalidate(); |
266 | return bbox; |
267 | } |
268 | |
269 | template <typename T, size_t N> |
270 | inline AABB<T, N> AABB<T, N>::intersect(const AABBType& a, const AABBType& b) |
271 | { |
272 | assert(a.is_valid()); |
273 | assert(b.is_valid()); |
274 | |
275 | AABBType intersection; |
276 | |
277 | for (size_t i = 0; i < N; ++i) |
278 | { |
279 | intersection.min[i] = std::max(a.min[i], b.min[i]); |
280 | intersection.max[i] = std::min(a.max[i], b.max[i]); |
281 | } |
282 | |
283 | return intersection; |
284 | } |
285 | |
286 | template <typename T, size_t N> |
287 | inline bool AABB<T, N>::overlap(const AABBType& a, const AABBType& b) |
288 | { |
289 | assert(a.is_valid()); |
290 | assert(b.is_valid()); |
291 | |
292 | for (size_t i = 0; i < N; ++i) |
293 | { |
294 | if (a.min[i] > b.max[i] || a.max[i] < b.min[i]) |
295 | return false; |
296 | } |
297 | |
298 | return true; |
299 | } |
300 | |
301 | template <typename T, size_t N> |
302 | inline T AABB<T, N>::overlap_ratio(const AABBType& a, const AABBType& b) |
303 | { |
304 | assert(a.is_valid()); |
305 | assert(b.is_valid()); |
306 | |
307 | T ratio = T(1.0); |
308 | |
309 | for (size_t i = 0; i < N; ++i) |
310 | { |
311 | const T amin = a.min[i]; |
312 | const T amax = a.max[i]; |
313 | const T bmin = b.min[i]; |
314 | const T bmax = b.max[i]; |
315 | |
316 | const T overlap = std::min(amax, bmax) - std::max(amin, bmin); |
317 | |
318 | if (overlap <= T(0.0)) |
319 | return T(0.0); |
320 | |
321 | ratio *= overlap / std::min(amax - amin, bmax - bmin); |
322 | } |
323 | |
324 | return ratio; |
325 | } |
326 | |
327 | template <typename T, size_t N> |
328 | inline T AABB<T, N>::extent_ratio(const AABBType& a, const AABBType& b) |
329 | { |
330 | assert(a.is_valid()); |
331 | assert(b.is_valid()); |
332 | |
333 | const VectorType ea = a.extent(); |
334 | const VectorType eb = b.extent(); |
335 | |
336 | T ratio = T(1.0); |
337 | |
338 | for (size_t i = 0; i < N; ++i) |
339 | { |
340 | if (ea[i] != eb[i]) |
341 | ratio *= ea[i] / eb[i]; |
342 | } |
343 | |
344 | return ratio; |
345 | } |
346 | |
347 | template <typename T, size_t N> |
348 | inline Vector<T, N>& AABB<T, N>::operator[](const size_t i) |
349 | { |
350 | assert(i < 2); |
351 | return (&min)[i]; |
352 | } |
353 | |
354 | template <typename T, size_t N> |
355 | inline const Vector<T, N>& AABB<T, N>::operator[](const size_t i) const |
356 | { |
357 | assert(i < 2); |
358 | return (&min)[i]; |
359 | } |
360 | |
361 | template <typename T, size_t N> |
362 | inline void AABB<T, N>::invalidate() |
363 | { |
364 | for (size_t i = 0; i < N; ++i) |
365 | { |
366 | min[i] = std::numeric_limits<T>::max(); |
367 | max[i] = signed_min<T>(); |
368 | } |
369 | } |
370 | |
371 | template <typename T, size_t N> |
372 | inline void AABB<T, N>::insert(const VectorType& v) |
373 | { |
374 | for (size_t i = 0; i < N; ++i) |
375 | { |
376 | if (min[i] > v[i]) |
377 | min[i] = v[i]; |
378 | if (max[i] < v[i]) |
379 | max[i] = v[i]; |
380 | } |
381 | } |
382 | |
383 | template <typename T, size_t N> |
384 | inline void AABB<T, N>::insert(const AABBType& b) |
385 | { |
386 | for (size_t i = 0; i < N; ++i) |
387 | { |
388 | if (min[i] > b.min[i]) |
389 | min[i] = b.min[i]; |
390 | if (max[i] < b.max[i]) |
391 | max[i] = b.max[i]; |
392 | } |
393 | } |
394 | |
395 | template <typename T, size_t N> |
396 | inline void AABB<T, N>::grow(const VectorType& v) |
397 | { |
398 | assert(is_valid()); |
399 | |
400 | min -= v; |
401 | max += v; |
402 | } |
403 | |
404 | template <typename T, size_t N> |
405 | inline void AABB<T, N>::robust_grow(const ValueType eps) |
406 | { |
407 | assert(is_valid()); |
408 | |
409 | const VectorType c = ValueType(0.5) * (min + max); |
410 | const VectorType e = max - min; |
411 | |
412 | for (size_t i = 0; i < N; ++i) |
413 | { |
414 | const ValueType dominant_factor = |
415 | foundation::max( // needs full qualification |
416 | std::abs(c[i]), |
417 | e[i], |
418 | ValueType(1.0)); |
419 | |
420 | const ValueType delta = dominant_factor * eps; |
421 | |
422 | min[i] -= delta; |
423 | max[i] += delta; |
424 | } |
425 | } |
426 | |
427 | template <typename T, size_t N> |
428 | inline void AABB<T, N>::translate(const VectorType& v) |
429 | { |
430 | assert(is_valid()); |
431 | |
432 | min += v; |
433 | max += v; |
434 | } |
435 | |
436 | template <typename T, size_t N> |
437 | inline bool AABB<T, N>::is_valid() const |
438 | { |
439 | for (size_t i = 0; i < N; ++i) |
440 | { |
441 | // Return false if NaN values creep in. |
442 | if (!(min[i] <= max[i])) |
443 | return false; |
444 | } |
445 | |
446 | return true; |
447 | } |
448 | |
449 | template <typename T, size_t N> |
450 | inline size_t AABB<T, N>::rank() const |
451 | { |
452 | size_t r = 0; |
453 | |
454 | for (size_t i = 0; i < N; ++i) |
455 | { |
456 | if (min[i] < max[i]) |
457 | ++r; |
458 | } |
459 | |
460 | return r; |
461 | } |
462 | |
463 | template <typename T, size_t N> |
464 | inline Vector<T, N> AABB<T, N>::center() const |
465 | { |
466 | assert(is_valid()); |
467 | |
468 | return ValueType(0.5) * (min + max); |
469 | } |
470 | |
471 | template <typename T, size_t N> |
472 | inline T AABB<T, N>::center(const size_t dim) const |
473 | { |
474 | assert(is_valid()); |
475 | |
476 | return ValueType(0.5) * (min[dim] + max[dim]); |
477 | } |
478 | |
479 | template <typename T, size_t N> |
480 | inline Vector<T, N> AABB<T, N>::extent() const |
481 | { |
482 | assert(is_valid()); |
483 | |
484 | return max - min; |
485 | } |
486 | |
487 | template <typename T, size_t N> |
488 | inline T AABB<T, N>::extent(const size_t dim) const |
489 | { |
490 | assert(is_valid()); |
491 | |
492 | return max[dim] - min[dim]; |
493 | } |
494 | |
495 | template <typename T, size_t N> |
496 | inline T AABB<T, N>::diameter() const |
497 | { |
498 | assert(is_valid()); |
499 | |
500 | return norm(extent()); |
501 | } |
502 | |
503 | template <typename T, size_t N> |
504 | inline T AABB<T, N>::radius() const |
505 | { |
506 | assert(is_valid()); |
507 | |
508 | return T(0.5) * diameter(); |
509 | } |
510 | |
511 | template <typename T, size_t N> |
512 | T AABB<T, N>::volume() const |
513 | { |
514 | assert(is_valid()); |
515 | |
516 | const VectorType e = max - min; |
517 | |
518 | ValueType volume = e[0]; |
519 | |
520 | for (size_t i = 1; i < N; ++i) |
521 | volume *= e[i]; |
522 | |
523 | return volume; |
524 | } |
525 | |
526 | template <typename T, size_t N> |
527 | inline size_t AABB<T, N>::get_corner_count() const |
528 | { |
529 | return 1 << N; |
530 | } |
531 | |
532 | template <typename T, size_t N> |
533 | Vector<T, N> AABB<T, N>::compute_corner(const size_t i) const |
534 | { |
535 | assert(is_valid()); |
536 | |
537 | VectorType p; |
538 | |
539 | for (size_t d = 0; d < N; ++d) |
540 | p[d] = i & (size_t(1) << d) ? max[d] : min[d]; |
541 | |
542 | return p; |
543 | } |
544 | |
545 | template <typename T, size_t N> |
546 | inline bool AABB<T, N>::contains(const VectorType& v) const |
547 | { |
548 | assert(is_valid()); |
549 | |
550 | for (size_t i = 0; i < N; ++i) |
551 | { |
552 | if (v[i] < min[i] || v[i] > max[i]) |
553 | return false; |
554 | } |
555 | |
556 | return true; |
557 | } |
558 | |
559 | template <typename T, size_t N> |
560 | inline bool operator!=(const AABB<T, N>& lhs, const AABB<T, N>& rhs) |
561 | { |
562 | return lhs.min != rhs.min || lhs.max != rhs.max; |
563 | } |
564 | |
565 | template <typename T, size_t N> |
566 | inline bool operator==(const AABB<T, N>& lhs, const AABB<T, N>& rhs) |
567 | { |
568 | return !(lhs != rhs); |
569 | } |
570 | |
571 | template <typename T, size_t N> |
572 | inline bool feq(const AABB<T, N>& lhs, const AABB<T, N>& rhs) |
573 | { |
574 | return feq(lhs.min, rhs.min) && feq(lhs.max, rhs.max); |
575 | } |
576 | |
577 | template <typename T, size_t N> |
578 | inline bool feq(const AABB<T, N>& lhs, const AABB<T, N>& rhs, const T eps) |
579 | { |
580 | return feq(lhs.min, rhs.min, eps) && feq(lhs.max, rhs.max, eps); |
581 | } |
582 | |
583 | template <typename T, size_t N> |
584 | inline AABB<T, N> operator+(const AABB<T, N>& lhs, const AABB<T, N>& rhs) |
585 | { |
586 | return AABB<T, N>(lhs.min + rhs.min, lhs.max + rhs.max); |
587 | } |
588 | |
589 | template <typename T, size_t N> |
590 | inline AABB<T, N> operator*(const AABB<T, N>& lhs, const T rhs) |
591 | { |
592 | return AABB<T, N>(lhs.min * rhs, lhs.max * rhs); |
593 | } |
594 | |
595 | template <typename T, size_t N> |
596 | inline AABB<T, N> operator*(const T lhs, const AABB<T, N>& rhs) |
597 | { |
598 | return AABB<T, N>(lhs * rhs.min, lhs * rhs.max); |
599 | } |
600 | |
601 | template <typename T, size_t N> |
602 | inline AABB<T, N>& operator+=(AABB<T, N>& lhs, const AABB<T, N>& rhs) |
603 | { |
604 | lhs.min += rhs.min; |
605 | lhs.max += rhs.max; |
606 | return lhs; |
607 | } |
608 | |
609 | template <typename T, size_t N> |
610 | inline AABB<T, N>& operator*=(AABB<T, N>& lhs, const T rhs) |
611 | { |
612 | lhs.min *= rhs; |
613 | lhs.max *= rhs; |
614 | return lhs; |
615 | } |
616 | |
617 | template <typename T> |
618 | inline T half_surface_area(const AABB<T, 3>& bbox) |
619 | { |
620 | assert(bbox.is_valid()); |
621 | |
622 | const Vector<T, 3> e = bbox.max - bbox.min; |
623 | |
624 | return e[0] * e[1] + e[0] * e[2] + e[1] * e[2]; |
625 | } |
626 | |
627 | template <typename T> |
628 | inline T surface_area(const AABB<T, 3>& bbox) |
629 | { |
630 | const T h = half_surface_area(bbox); |
631 | return h + h; |
632 | } |
633 | |
634 | } // namespace foundation |
635 | |
636 | #endif // !APPLESEED_FOUNDATION_MATH_AABB_H |
637 | |