## 3.7 Bounding Boxes

Many parts of the system operate on axis-aligned regions of space. For example, multi-threading in pbrt is implemented by subdividing the image into 2D rectangular tiles that can be processed independently, and the bounding volume hierarchy in Section 7.3 uses 3D boxes to bound geometric primitives in the scene. The Bounds2 and Bounds3 template classes are used to represent the extent of these sorts of regions. Both are parameterized by a type T that is used to represent the coordinates of their extents. As with the earlier vector math types, we will focus here on the 3D variant, Bounds3, since Bounds2 is effectively a subset of it.

<<Bounds2 Definition>>=
template <typename T> class Bounds2 { public: <<Bounds2 Public Methods>>
PBRT_CPU_GPU Bounds2() { T minNum = std::numeric_limits<T>::lowest(); T maxNum = std::numeric_limits<T>::max(); pMin = Point2<T>(maxNum, maxNum); pMax = Point2<T>(minNum, minNum); } PBRT_CPU_GPU explicit Bounds2(Point2<T> p) : pMin(p), pMax(p) {} PBRT_CPU_GPU Bounds2(Point2<T> p1, Point2<T> p2) : pMin(Min(p1, p2)), pMax(Max(p1, p2)) {} template <typename U> PBRT_CPU_GPU explicit Bounds2(const Bounds2<U> &b) { if (b.IsEmpty()) // Be careful about overflowing float->int conversions and the // like. *this = Bounds2<T>(); else { pMin = Point2<T>(b.pMin); pMax = Point2<T>(b.pMax); } } PBRT_CPU_GPU Vector2<T> Diagonal() const { return pMax - pMin; } PBRT_CPU_GPU T Area() const { Vector2<T> d = pMax - pMin; return d.x * d.y; } PBRT_CPU_GPU bool IsEmpty() const { return pMin.x >= pMax.x || pMin.y >= pMax.y; } PBRT_CPU_GPU bool IsDegenerate() const { return pMin.x > pMax.x || pMin.y > pMax.y; } PBRT_CPU_GPU int MaxDimension() const { Vector2<T> diag = Diagonal(); if (diag.x > diag.y) return 0; else return 1; } PBRT_CPU_GPU Point2<T> operator[](int i) const { DCHECK(i == 0 || i == 1); return (i == 0) ? pMin : pMax; } PBRT_CPU_GPU Point2<T> &operator[](int i) { DCHECK(i == 0 || i == 1); return (i == 0) ? pMin : pMax; } PBRT_CPU_GPU bool operator==(const Bounds2<T> &b) const { return b.pMin == pMin && b.pMax == pMax; } PBRT_CPU_GPU bool operator!=(const Bounds2<T> &b) const { return b.pMin != pMin || b.pMax != pMax; } PBRT_CPU_GPU Point2<T> Corner(int corner) const { DCHECK(corner >= 0 && corner < 4); return Point2<T>((*this)[(corner & 1)].x, (*this)[(corner & 2) ? 1 : 0].y); } PBRT_CPU_GPU Point2<T> Lerp(Point2f t) const { return Point2<T>(pbrt::Lerp(t.x, pMin.x, pMax.x), pbrt::Lerp(t.y, pMin.y, pMax.y)); } PBRT_CPU_GPU Vector2<T> Offset(Point2<T> p) const { Vector2<T> o = p - pMin; if (pMax.x > pMin.x) o.x /= pMax.x - pMin.x; if (pMax.y > pMin.y) o.y /= pMax.y - pMin.y; return o; } PBRT_CPU_GPU void BoundingSphere(Point2<T> *c, Float *rad) const { *c = (pMin + pMax) / 2; *rad = Inside(*c, *this) ? Distance(*c, pMax) : 0; } std::string ToString() const { return StringPrintf("[ %s - %s ]", pMin, pMax); }
<<Bounds2 Public Members>>
Point2<T> pMin, pMax;
};

<<Bounds3 Definition>>=
template <typename T> class Bounds3 { public: <<Bounds3 Public Methods>>
Bounds3() { T minNum = std::numeric_limits<T>::lowest(); T maxNum = std::numeric_limits<T>::max(); pMin = Point3<T>(maxNum, maxNum, maxNum); pMax = Point3<T>(minNum, minNum, minNum); } explicit Bounds3(Point3<T> p) : pMin(p), pMax(p) {} Bounds3(Point3<T> p1, Point3<T> p2) : pMin(Min(p1, p2)), pMax(Max(p1, p2)) {} Point3<T> operator[](int i) const { return (i == 0) ? pMin : pMax; } Point3<T> &operator[](int i) { return (i == 0) ? pMin : pMax; } Point3<T> Corner(int corner) const { return Point3<T>((*this)[(corner & 1)].x, (*this)[(corner & 2) ? 1 : 0].y, (*this)[(corner & 4) ? 1 : 0].z); } Vector3<T> Diagonal() const { return pMax - pMin; } T SurfaceArea() const { Vector3<T> d = Diagonal(); return 2 * (d.x * d.y + d.x * d.z + d.y * d.z); } T Volume() const { Vector3<T> d = Diagonal(); return d.x * d.y * d.z; } int MaxDimension() const { Vector3<T> d = Diagonal(); if (d.x > d.y && d.x > d.z) return 0; else if (d.y > d.z) return 1; else return 2; } Point3f Lerp(Point3f t) const { return Point3f(pbrt::Lerp(t.x, pMin.x, pMax.x), pbrt::Lerp(t.y, pMin.y, pMax.y), pbrt::Lerp(t.z, pMin.z, pMax.z)); } Vector3f Offset(Point3f p) const { Vector3f o = p - pMin; if (pMax.x > pMin.x) o.x /= pMax.x - pMin.x; if (pMax.y > pMin.y) o.y /= pMax.y - pMin.y; if (pMax.z > pMin.z) o.z /= pMax.z - pMin.z; return o; } void BoundingSphere(Point3<T> *center, Float *radius) const { *center = (pMin + pMax) / 2; *radius = Inside(*center, *this) ? Distance(*center, pMax) : 0; } bool IsEmpty() const { return pMin.x >= pMax.x || pMin.y >= pMax.y || pMin.z >= pMax.z; } bool IsDegenerate() const { return pMin.x > pMax.x || pMin.y > pMax.y || pMin.z > pMax.z; } template <typename U> PBRT_CPU_GPU explicit Bounds3(const Bounds3<U> &b) { if (b.IsEmpty()) // Be careful about overflowing float->int conversions and the // like. *this = Bounds3<T>(); else { pMin = Point3<T>(b.pMin); pMax = Point3<T>(b.pMax); } } PBRT_CPU_GPU bool operator==(const Bounds3<T> &b) const { return b.pMin == pMin && b.pMax == pMax; } PBRT_CPU_GPU bool operator!=(const Bounds3<T> &b) const { return b.pMin != pMin || b.pMax != pMax; } PBRT_CPU_GPU bool IntersectP(Point3f o, Vector3f d, Float tMax = Infinity, Float *hitt0 = nullptr, Float *hitt1 = nullptr) const; PBRT_CPU_GPU bool IntersectP(Point3f o, Vector3f d, Float tMax, Vector3f invDir, const int dirIsNeg) const; std::string ToString() const { return StringPrintf("[ %s - %s ]", pMin, pMax); }
<<Bounds3 Public Members>>
Point3<T> pMin, pMax;
};

We use the same shorthand as before to define names for commonly used bounding types.

<<Bounds[fi] Definitions>>=
using Bounds2f = Bounds2<Float>; using Bounds2i = Bounds2<int>; using Bounds3f = Bounds3<Float>; using Bounds3i = Bounds3<int>;

There are a few possible representations for these sorts of bounding boxes; pbrt uses axis-aligned bounding boxes (AABBs), where the box edges are mutually perpendicular and aligned with the coordinate system axes. Another possible choice is oriented bounding boxes (OBBs), where the box edges on different sides are still perpendicular to each other but not necessarily coordinate-system aligned. A 3D AABB can be described by one of its vertices and three lengths, each representing the distance spanned along the , , and coordinate axes. Alternatively, two opposite vertices of the box can describe it. We chose the two-point representation for pbrt’s Bounds2 and Bounds3 classes; they store the positions of the vertex with minimum coordinate values and of the one with maximum coordinate values. A 2D illustration of a bounding box and its representation is shown in Figure 3.9.

<<Bounds3 Public Members>>=
Point3<T> pMin, pMax;

The default constructors create an empty box by setting the extent to an invalid configuration, which violates the invariant that pMin.x <= pMax.x (and similarly for the other dimensions). By initializing two corner points with the largest and smallest representable number, any operations involving an empty box (e.g., Union()) will yield the correct result.

<<Bounds3 Public Methods>>=
Bounds3() { T minNum = std::numeric_limits<T>::lowest(); T maxNum = std::numeric_limits<T>::max(); pMin = Point3<T>(maxNum, maxNum, maxNum); pMax = Point3<T>(minNum, minNum, minNum); }

It is also useful to be able to initialize bounds that enclose just a single point:

<<Bounds3 Public Methods>>+=
explicit Bounds3(Point3<T> p) : pMin(p), pMax(p) {}

If the caller passes two corner points (p1 and p2) to define the box, the constructor needs to find their component-wise minimum and maximum values since it is not necessarily the case that p1.x <= p2.x, and so on.

<<Bounds3 Public Methods>>+=
Bounds3(Point3<T> p1, Point3<T> p2) : pMin(Min(p1, p2)), pMax(Max(p1, p2)) {}

It can be useful to use array indexing to select between the two points at the corners of the box. Assertions in the debug build, not shown here, check that the provided index is either 0 or 1.

<<Bounds3 Public Methods>>+=
Point3<T> operator[](int i) const { return (i == 0) ? pMin : pMax; } Point3<T> &operator[](int i) { return (i == 0) ? pMin : pMax; }

The Corner() method returns the coordinates of one of the eight corners of the bounding box. Its logic calls the operator[] method with a zero or one value for each dimension that is based on one of the low three bits of corner and then extracts the corresponding component. It is worthwhile to verify that this method returns the positions of all eight corners when passed values from 0 to 7 if that is not immediately evident.

<<Bounds3 Public Methods>>+=
Point3<T> Corner(int corner) const { return Point3<T>((*this)[(corner & 1)].x, (*this)[(corner & 2) ? 1 : 0].y, (*this)[(corner & 4) ? 1 : 0].z); }

Given a bounding box and a point, the Union() function returns a new bounding box that encompasses that point as well as the original bounds.

<<Bounds3 Inline Functions>>=
template <typename T> Bounds3<T> Union(const Bounds3<T> &b, Point3<T> p) { Bounds3<T> ret; ret.pMin = Min(b.pMin, p); ret.pMax = Max(b.pMax, p); return ret; }

One subtlety that applies to this and some of the following functions is that it is important that the pMin and pMax members of ret be set directly here, rather than passing the values returned by Min() and Max() to the Bounds3 constructor. The detail stems from the fact that if the provided bounds are both degenerate, the returned bounds should be degenerate as well. If a degenerate extent is passed to the constructor, then it will sort the coordinate values, which in turn leads to what is essentially an infinite bound.

It is similarly possible to construct a new box that bounds the space encompassed by two other bounding boxes. The definition of this function is similar to the earlier Union() method that takes a Point3f; the difference is that the pMin and pMax of the second box are used for the Min() and Max() tests, respectively.

<<Bounds3 Inline Functions>>+=
template <typename T> Bounds3<T> Union(const Bounds3<T> &b1, const Bounds3<T> &b2) { Bounds3<T> ret; ret.pMin = Min(b1.pMin, b2.pMin); ret.pMax = Max(b1.pMax, b2.pMax); return ret; }

The intersection of two bounding boxes can be found by computing the maximum of their two respective minimum coordinates and the minimum of their maximum coordinates. (See Figure 3.10.)

<<Bounds3 Inline Functions>>+=
template <typename T> Bounds3<T> Intersect(const Bounds3<T> &b1, const Bounds3<T> &b2) { Bounds3<T> b; b.pMin = Max(b1.pMin, b2.pMin); b.pMax = Min(b1.pMax, b2.pMax); return b; }

We can also determine if two bounding boxes overlap by seeing if their extents overlap in all of , , and :

<<Bounds3 Inline Functions>>+=
template <typename T> bool Overlaps(const Bounds3<T> &b1, const Bounds3<T> &b2) { bool x = (b1.pMax.x >= b2.pMin.x) && (b1.pMin.x <= b2.pMax.x); bool y = (b1.pMax.y >= b2.pMin.y) && (b1.pMin.y <= b2.pMax.y); bool z = (b1.pMax.z >= b2.pMin.z) && (b1.pMin.z <= b2.pMax.z); return (x && y && z); }

Three 1D containment tests determine if a given point is inside a bounding box.

<<Bounds3 Inline Functions>>+=
template <typename T> bool Inside(Point3<T> p, const Bounds3<T> &b) { return (p.x >= b.pMin.x && p.x <= b.pMax.x && p.y >= b.pMin.y && p.y <= b.pMax.y && p.z >= b.pMin.z && p.z <= b.pMax.z); }

The InsideExclusive() variant of Inside() does not consider points on the upper boundary to be inside the bounds. It is mostly useful with integer-typed bounds.

<<Bounds3 Inline Functions>>+=
template <typename T> bool InsideExclusive(Point3<T> p, const Bounds3<T> &b) { return (p.x >= b.pMin.x && p.x < b.pMax.x && p.y >= b.pMin.y && p.y < b.pMax.y && p.z >= b.pMin.z && p.z < b.pMax.z); }

DistanceSquared() returns the squared distance from a point to a bounding box or zero if the point is inside it. The geometric setting of the computation is shown in Figure 3.11. After the distance from the point to the box is computed in each dimension, the squared distance is found by summing the squares of each of the 1D distances.

<<Bounds3 Inline Functions>>+=
template <typename T, typename U> auto DistanceSquared(Point3<T> p, const Bounds3<U> &b) { using TDist = decltype(T{} - U{}); TDist dx = std::max<TDist>({0, b.pMin.x - p.x, p.x - b.pMax.x}); TDist dy = std::max<TDist>({0, b.pMin.y - p.y, p.y - b.pMax.y}); TDist dz = std::max<TDist>({0, b.pMin.z - p.z, p.z - b.pMax.z}); return Sqr(dx) + Sqr(dy) + Sqr(dz); }

It is easy to compute the distance from a point to a bounding box, though some indirection is needed to be able to determine the correct return type using TupleLength.

<<Bounds3 Inline Functions>>+=
template <typename T, typename U> auto Distance(Point3<T> p, const Bounds3<U> &b) { auto dist2 = DistanceSquared(p, b); using TDist = typename TupleLength<decltype(dist2)>::type; return std::sqrt(TDist(dist2)); }

The Expand() function pads the bounding box by a constant factor in all dimensions.

<<Bounds3 Inline Functions>>+=
template <typename T, typename U> Bounds3<T> Expand(const Bounds3<T> &b, U delta) { Bounds3<T> ret; ret.pMin = b.pMin - Vector3<T>(delta, delta, delta); ret.pMax = b.pMax + Vector3<T>(delta, delta, delta); return ret; }

Diagonal() returns the vector along the box diagonal from the minimum point to the maximum point.

<<Bounds3 Public Methods>>+=
Vector3<T> Diagonal() const { return pMax - pMin; }

Methods for computing the surface area of the six faces of the box and the volume inside of it are also useful. (This is a place where Bounds2 and Bounds3 diverge: these methods are not available in Bounds2, though it does have an Area() method.)

<<Bounds3 Public Methods>>+=
T SurfaceArea() const { Vector3<T> d = Diagonal(); return 2 * (d.x * d.y + d.x * d.z + d.y * d.z); }

<<Bounds3 Public Methods>>+=
T Volume() const { Vector3<T> d = Diagonal(); return d.x * d.y * d.z; }

The Bounds3::MaxDimension() method returns the index of which of the three axes is longest. This is useful, for example, when deciding which axis to subdivide when building some of the ray-intersection acceleration structures.

<<Bounds3 Public Methods>>+=
int MaxDimension() const { Vector3<T> d = Diagonal(); if (d.x > d.y && d.x > d.z) return 0; else if (d.y > d.z) return 1; else return 2; }

Lerp() linearly interpolates between the corners of the box by the given amount in each dimension.

<<Bounds3 Public Methods>>+=
Point3f Lerp(Point3f t) const { return Point3f(pbrt::Lerp(t.x, pMin.x, pMax.x), pbrt::Lerp(t.y, pMin.y, pMax.y), pbrt::Lerp(t.z, pMin.z, pMax.z)); }

Offset() is effectively the inverse of Lerp(). It returns the continuous position of a point relative to the corners of the box, where a point at the minimum corner has offset , a point at the maximum corner has offset , and so forth.

<<Bounds3 Public Methods>>+=
Vector3f Offset(Point3f p) const { Vector3f o = p - pMin; if (pMax.x > pMin.x) o.x /= pMax.x - pMin.x; if (pMax.y > pMin.y) o.y /= pMax.y - pMin.y; if (pMax.z > pMin.z) o.z /= pMax.z - pMin.z; return o; }

Bounds3 also provides a method that returns the center and radius of a sphere that bounds the bounding box. In general, this may give a far looser fit than a sphere that bounded the original contents of the Bounds3 directly, although for some geometric operations it is easier to work with a sphere than a box, in which case the worse fit may be an acceptable trade-off.

<<Bounds3 Public Methods>>+=
void BoundingSphere(Point3<T> *center, Float *radius) const { *center = (pMin + pMax) / 2; *radius = Inside(*center, *this) ? Distance(*center, pMax) : 0; }

Straightforward methods test for empty and degenerate bounding boxes. Note that “empty” means that a bounding box has zero volume but does not necessarily imply that it has zero surface area.

<<Bounds3 Public Methods>>+=
bool IsEmpty() const { return pMin.x >= pMax.x || pMin.y >= pMax.y || pMin.z >= pMax.z; } bool IsDegenerate() const { return pMin.x > pMax.x || pMin.y > pMax.y || pMin.z > pMax.z; }

Finally, for integer bounds, there is an iterator class that fulfills the requirements of a C++ forward iterator (i.e., it can only be advanced). The details are slightly tedious and not particularly interesting, so the code is not included in the book. Having this definition makes it possible to write code using range-based for loops to iterate over integer coordinates in a bounding box:

Bounds2i b = ...; for (Point2i p : b) { // … }

As implemented, the iteration goes up to but does not visit points equal to the maximum extent in each dimension.