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>>
We use the same shorthand as before to define names for commonly used
bounding types.
<<Bounds[23][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;
Figure 3.9: An Axis-Aligned Bounding Box. The Bounds2 and
Bounds3 classes store only
the coordinates of the minimum and maximum points of the box; the other
box corners are implicit in this representation.
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.
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.
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.
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.
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.
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.)
Figure 3.10: Intersection of Two Bounding Boxes.
Given two bounding boxes with pMin and pMax points
denoted by open circles, the bounding box of their area of intersection
(shaded region) has a minimum point (lower left filled circle) with coordinates given by the maximum
of the coordinates of the minimum points of the two boxes in each
dimension. Similarly, its maximum point (upper right filled circle) is given by the minimums of the
boxes’ maximum coordinates.
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.
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.
Figure 3.11: Computing the Squared Distance from a Point to an Axis-Aligned
Bounding Box.
We first find the distance from the point to the box in each dimension.
Here, the point represented by an empty circle on the upper left is above to the left of
the box, so its and distances are respectively pMin.x - p.x
and pMin.y - p.y.
The other point represented by an empty circle is to the right of the box but
overlaps its extent in the dimension, giving it respective distances of
p.x - pMax.x and zero.
The logic in Bounds3::DistanceSquared() computes these distances by
finding the maximum of zero and the distances to the minimum and maximum
points in each dimension.
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.
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.)
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.
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 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.
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.
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.
