## 2.6 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 rectangular tiles that can be processed independently, and the bounding volume hierarchy in Section 4.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 its extents.

<<Bounds Declarations>>=
template <typename T> class Bounds2 { public: <<Bounds2 Public Methods>>
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); } Bounds2(const Point2<T> &p) : pMin(p), pMax(p) { } Bounds2(const Point2<T> &p1, const Point2<T> &p2) { pMin = Point2<T>(std::min(p1.x, p2.x), std::min(p1.y, p2.y)); pMax = Point2<T>(std::max(p1.x, p2.x), std::max(p1.y, p2.y)); } template <typename U> explicit operator Bounds2<U>() const { return Bounds2<U>((Point2<U>)pMin, (Point2<U>)pMax); } Vector2<T> Diagonal() const { return pMax - pMin; } T Area() const { Vector2<T> d = pMax - pMin; return (d.x * d.y); } int MaximumExtent() const { Vector2<T> diag = Diagonal(); if (diag.x > diag.y) return 0; else return 1; } inline const Point2<T> & operator[](int i) const { Assert(i == 0 || i == 1); return (i == 0) ? pMin : pMax; } inline Point2<T> &operator[](int i) { Assert(i == 0 || i == 1); return (i == 0) ? pMin : pMax; } bool operator==(const Bounds2<T> &b) const { return b.pMin == pMin && b.pMax == pMax; } bool operator!=(const Bounds2<T> &b) const { return b.pMin != pMin || b.pMax != pMax; } Point2<T> Lerp(const Point2f &t) const { return Point2<T>(::Lerp(t.x, pMin.x, pMax.x), ::Lerp(t.y, pMin.y, pMax.y)); } Vector2<T> Offset(const 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; } void BoundingSphere(Point2<T> *c, Float *rad) const { *c = (pMin + pMax) / 2; *rad = Inside(*c, *this) ? Distance(*c, pMax) : 0; }
<<Bounds2 Public Data>>
Point2<T> pMin, pMax;
};

<<Bounds Declarations>>+=
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); } Bounds3(const Point3<T> &p) : pMin(p), pMax(p) { } Bounds3(const Point3<T> &p1, const Point3<T> &p2) : pMin(std::min(p1.x, p2.x), std::min(p1.y, p2.y), std::min(p1.z, p2.z)), pMax(std::max(p1.x, p2.x), std::max(p1.y, p2.y), std::max(p1.z, p2.z)) { } const Point3<T> &operator[](int i) const; Point3<T> &operator[](int i); bool operator==(const Bounds3<T> &b) const { return b.pMin == pMin && b.pMax == pMax; } bool operator!=(const Bounds3<T> &b) const { return b.pMin != pMin || b.pMax != 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 MaximumExtent() 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; } Point3<T> Lerp(const Point3f &t) const { return Point3<T>(::Lerp(t.x, pMin.x, pMax.x), ::Lerp(t.y, pMin.y, pMax.y), ::Lerp(t.z, pMin.z, pMax.z)); } Vector3<T> Offset(const Point3<T> &p) const { Vector3<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; 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; } template <typename U> explicit operator Bounds3<U>() const { return Bounds3<U>((Point3<U>)pMin, (Point3<U>)pMax); } bool IntersectP(const Ray &ray, Float *hitt0 = nullptr, Float *hitt1 = nullptr) const; inline bool IntersectP(const Ray &ray, const Vector3f &invDir, const int dirIsNeg) const;
<<Bounds3 Public Data>>
Point3<T> pMin, pMax;
};

<<Bounds Declarations>>+=
typedef Bounds2<Float> Bounds2f; typedef Bounds2<int> Bounds2i; typedef Bounds3<Float> Bounds3f; typedef Bounds3<int> Bounds3i;

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 2.8.

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); }

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

It is also useful to be able to initialize a Bounds3 to enclose a single point:

<<Bounds3 Public Methods>>+=
Bounds3(const 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 p1 and p2 are not necessarily chosen so that p1.x <= p2.x, and so on.

<<Bounds3 Public Methods>>+=
Bounds3(const Point3<T> &p1, const Point3<T> &p2) : pMin(std::min(p1.x, p2.x), std::min(p1.y, p2.y), std::min(p1.z, p2.z)), pMax(std::max(p1.x, p2.x), std::max(p1.y, p2.y), std::max(p1.z, p2.z)) { }

In some cases, it’s also useful to use array indexing to select between the two points at the corners of the box. The implementations of these methods select between pMin and pMax based on the value of i.

<<Bounds3 Public Methods>>+=
const Point3<T> &operator[](int i) const; Point3<T> &operator[](int i);

The Corner() method returns the coordinates of one of the eight corners of the bounding box.

<<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 box.

<<Geometry Inline Functions>>+=
template <typename T> Bounds3 <T> Union(const Bounds3<T> &b, const Point3<T> &p) { return Bounds3<T>(Point3<T>(std::min(b.pMin.x, p.x), std::min(b.pMin.y, p.y), std::min(b.pMin.z, p.z)), Point3<T>(std::max(b.pMax.x, p.x), std::max(b.pMax.y, p.y), std::max(b.pMax.z, p.z))); }

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 std::min() and std::max() tests, respectively.

<<Geometry Inline Functions>>+=
template <typename T> Bounds3<T> Union(const Bounds3<T> &b1, const Bounds3<T> &b2) { return Bounds3<T>(Point3<T>(std::min(b1.pMin.x, b2.pMin.x), std::min(b1.pMin.y, b2.pMin.y), std::min(b1.pMin.z, b2.pMin.z)), Point3<T>(std::max(b1.pMax.x, b2.pMax.x), std::max(b1.pMax.y, b2.pMax.y), std::max(b1.pMax.z, b2.pMax.z))); }

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 2.9.)

<<Geometry Inline Functions>>+=
template <typename T> Bounds3<T> Intersect(const Bounds3<T> &b1, const Bounds3<T> &b2) { return Bounds3<T>(Point3<T>(std::max(b1.pMin.x, b2.pMin.x), std::max(b1.pMin.y, b2.pMin.y), std::max(b1.pMin.z, b2.pMin.z)), Point3<T>(std::min(b1.pMax.x, b2.pMax.x), std::min(b1.pMax.y, b2.pMax.y), std::min(b1.pMax.z, b2.pMax.z))); }

We are able to determine if two bounding boxes overlap by seeing if their extents overlap in all of , , and :

<<Geometry 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 the bounding box:

<<Geometry Inline Functions>>+=
template <typename T> bool Inside(const 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() doesn’t consider points on the upper boundary to be inside the bounds. It is mostly useful with integer-typed bounds.

<<Geometry Inline Functions>>+=
template <typename T> bool InsideExclusive(const 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 Expand() function pads the bounding box by a constant factor in all dimensions.

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

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 frequently useful.

<<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::MaximumExtent() 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 MaximumExtent() 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; }

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

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

Offset() 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>>+=
Vector3<T> Offset(const Point3<T> &p) const { Vector3<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; 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 it is a useful method to have available.

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

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 isn’t 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 doesn’t visit points equal to the maximum extent in each dimension.