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"
41BEGIN_EXR_INCLUDES
42#include "OpenEXR/ImathBox.h"
43END_EXR_INCLUDES
44#endif
45
46// Standard headers.
47#include <algorithm>
48#include <cassert>
49#include <cmath>
50#include <cstddef>
51#include <limits>
52
53namespace 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
61template <typename T, size_t N>
62class 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.
168template <typename T, size_t N> bool operator!=(const AABB<T, N>& lhs, const AABB<T, N>& rhs);
169template <typename T, size_t N> bool operator==(const AABB<T, N>& lhs, const AABB<T, N>& rhs);
170
171// Approximate equality tests.
172template <typename T, size_t N> bool feq(const AABB<T, N>& lhs, const AABB<T, N>& rhs);
173template <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.
176template <typename T, size_t N> AABB<T, N> operator+ (const AABB<T, N>& lhs, const AABB<T, N>& rhs);
177template <typename T, size_t N> AABB<T, N> operator* (const AABB<T, N>& lhs, const T rhs);
178template <typename T, size_t N> AABB<T, N> operator* (const T lhs, const AABB<T, N>& rhs);
179template <typename T, size_t N> AABB<T, N>& operator+=(AABB<T, N>& lhs, const AABB<T, N>& rhs);
180template <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.
183template <typename T> T half_surface_area(const AABB<T, 3>& bbox);
184template <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
191typedef AABB<int, 1> AABB1i;
192typedef AABB<size_t, 1> AABB1u;
193typedef AABB<float, 1> AABB1f;
194typedef AABB<double, 1> AABB1d;
195
196typedef AABB<int, 2> AABB2i;
197typedef AABB<size_t, 2> AABB2u;
198typedef AABB<float, 2> AABB2f;
199typedef AABB<double, 2> AABB2d;
200
201typedef AABB<int, 3> AABB3i;
202typedef AABB<size_t, 3> AABB3u;
203typedef AABB<float, 3> AABB3f;
204typedef AABB<double, 3> AABB3d;
205
206typedef AABB<int, 4> AABB4i;
207typedef AABB<size_t, 4> AABB4u;
208typedef AABB<float, 4> AABB4f;
209typedef AABB<double, 4> AABB4d;
210
211
212//
213// N-dimensional axis-aligned bounding box class and operations.
214//
215
216template <typename T, size_t N>
217inline AABB<T, N>::AABB()
218{
219}
220
221template <typename T, size_t N>
222inline AABB<T, N>::AABB(
223 const VectorType& min_,
224 const VectorType& max_)
225 : min(min_)
226 , max(max_)
227{
228}
229
230template <typename T, size_t N>
231template <typename U>
232inline 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
240template <typename T, size_t N>
241inline AABB<T, N>::AABB(const Imath::Box<typename ImathVecEquivalent<T, N>::Type>& rhs)
242 : min(rhs.min)
243 , max(rhs.max)
244{
245}
246
247template <typename T, size_t N>
248inline 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
253template <typename T, size_t N>
254inline 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
261template <typename T, size_t N>
262inline AABB<T, N> AABB<T, N>::invalid()
263{
264 AABB<T, N> bbox;
265 bbox.invalidate();
266 return bbox;
267}
268
269template <typename T, size_t N>
270inline 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
286template <typename T, size_t N>
287inline 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
301template <typename T, size_t N>
302inline 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
327template <typename T, size_t N>
328inline 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
347template <typename T, size_t N>
348inline Vector<T, N>& AABB<T, N>::operator[](const size_t i)
349{
350 assert(i < 2);
351 return (&min)[i];
352}
353
354template <typename T, size_t N>
355inline const Vector<T, N>& AABB<T, N>::operator[](const size_t i) const
356{
357 assert(i < 2);
358 return (&min)[i];
359}
360
361template <typename T, size_t N>
362inline 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
371template <typename T, size_t N>
372inline 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
383template <typename T, size_t N>
384inline 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
395template <typename T, size_t N>
396inline void AABB<T, N>::grow(const VectorType& v)
397{
398 assert(is_valid());
399
400 min -= v;
401 max += v;
402}
403
404template <typename T, size_t N>
405inline 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
427template <typename T, size_t N>
428inline void AABB<T, N>::translate(const VectorType& v)
429{
430 assert(is_valid());
431
432 min += v;
433 max += v;
434}
435
436template <typename T, size_t N>
437inline 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
449template <typename T, size_t N>
450inline 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
463template <typename T, size_t N>
464inline Vector<T, N> AABB<T, N>::center() const
465{
466 assert(is_valid());
467
468 return ValueType(0.5) * (min + max);
469}
470
471template <typename T, size_t N>
472inline 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
479template <typename T, size_t N>
480inline Vector<T, N> AABB<T, N>::extent() const
481{
482 assert(is_valid());
483
484 return max - min;
485}
486
487template <typename T, size_t N>
488inline T AABB<T, N>::extent(const size_t dim) const
489{
490 assert(is_valid());
491
492 return max[dim] - min[dim];
493}
494
495template <typename T, size_t N>
496inline T AABB<T, N>::diameter() const
497{
498 assert(is_valid());
499
500 return norm(extent());
501}
502
503template <typename T, size_t N>
504inline T AABB<T, N>::radius() const
505{
506 assert(is_valid());
507
508 return T(0.5) * diameter();
509}
510
511template <typename T, size_t N>
512T 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
526template <typename T, size_t N>
527inline size_t AABB<T, N>::get_corner_count() const
528{
529 return 1 << N;
530}
531
532template <typename T, size_t N>
533Vector<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
545template <typename T, size_t N>
546inline 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
559template <typename T, size_t N>
560inline 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
565template <typename T, size_t N>
566inline bool operator==(const AABB<T, N>& lhs, const AABB<T, N>& rhs)
567{
568 return !(lhs != rhs);
569}
570
571template <typename T, size_t N>
572inline 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
577template <typename T, size_t N>
578inline 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
583template <typename T, size_t N>
584inline 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
589template <typename T, size_t N>
590inline 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
595template <typename T, size_t N>
596inline 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
601template <typename T, size_t N>
602inline 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
609template <typename T, size_t N>
610inline 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
617template <typename T>
618inline 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
627template <typename T>
628inline 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