② What kinds of scenes are worst-case scenarios for the
two acceleration structures in pbrt? (Consider specific geometric
configurations that the approaches will respectively be unable to handle
well.) Construct scenes with these characteristics, and measure the
performance of pbrt as you add more primitives. How does the worst case
for one behave when rendered with the other?
② Implement a hierarchical grid accelerator where cells
that have an excessive number of primitives overlapping them are refined to
instead hold a finer subgrid to store its geometry. (See, for example,
Jevans and Wyvill (1989) for one approach to this problem
and Ize et al. (2007) for effective methods for deciding when
refinement is worthwhile.) Compare both accelerator construction
performance and rendering performance to a non-hierarchical grid as well as
to pbrt’s built-in accelerators.
②Smarter overlap tests for building
aggregates: using objects’ bounding boxes to determine which sides of a
kd-tree split they overlap can hurt performance by causing unnecessary
intersection tests. Therefore, add a bool Overlaps(const
Bounds3f &) const method to the Shape interface that takes a rendering space
bounding box and determines if the shape truly overlaps the given bound.
A default implementation could get the rendering space bound from
the shape and use that for the test, and specialized versions could be
written for frequently used shapes. Implement this method for
Spheres and Triangles, and modify KdTreeAggregate to call
it. You may find it helpful to read Akenine-Möller’s paper
(2001) on fast triangle-box overlap testing.
Measure the change in pbrt’s overall performance caused by this change,
separately accounting for increased time spent building the acceleration
structure and reduction in ray–object intersection time due to fewer
intersections. For a variety of scenes, determine how many fewer
intersection tests are performed thanks to this improvement.
② Implement “split clipping” in pbrt’s BVH
implementation. Read one or more papers on this topic, including ones by
Ernst and Greiner (2007), Dammertz and Keller
(2008a), Stich et al. (2009), Karras and
Aila (2013), and Ganestam and Doggett
(2016), and implement one of their approaches to
subdivide primitives with large bounding boxes relative to their surface
area into multiple subprimitives for tree construction. (Doing so will
probably require modification to the Shape interface; you will
probably want to design a new interface that allows some shapes to indicate
that they are unable to subdivide themselves, so that you only need to
implement this method for triangles, for example.)
Measure the improvement for rendering actual scenes; a compelling way to
gather this data is to do the experiment that Dammertz and Keller did,
where a scene is rotated around an axis over progressive frames of an
animation. Typically, many triangles that are originally axis aligned will
have very loose bounding boxes as they rotate more, leading to a
substantial performance degradation if split clipping is not used.
② The 30-bit Morton codes used for the HLBVH construction
algorithm in the BVHAggregate may be insufficient for scenes with
large spatial extents
because they can only represent steps in each dimension.
Modify the BVHAggregate to use 64-bit integers with 63-bit Morton
codes for HLBVHs. Compare the performance of your approach to the original
one with a variety of scenes. Are there scenes where performance is
substantially improved? Are there any where there is a loss of
performance?
② Investigate alternative SAH cost functions for building
BVHs or kd-trees. How much can a poor cost function hurt its performance?
How much improvement can be had compared to the current one? (See the
discussion in the “Further Reading” section for ideas about how the SAH
may be improved.)
③ The idea of using spatial data structures for ray
intersection acceleration can be generalized to include spatial data
structures that themselves hold other spatial data structures rather than
just primitives. Not only could we have a grid that has subgrids inside
the grid cells that have many primitives in them, but we could also have
the scene organized into a hierarchical bounding volume where the leaf
nodes are grids that hold smaller collections of spatially nearby
primitives. Such hybrid techniques can bring the best of a variety of
spatial data structure–based ray intersection acceleration methods. In
pbrt, because both geometric primitives and intersection accelerators
implement the Primitive interface and thus provide the same
interface, it is easy to mix and match in this way.
Modify pbrt to build hybrid acceleration structures—for example, using
a BVH to coarsely partition the scene geometry and then uniform grids at the
leaves of the tree to manage dense, spatially local collections of
geometry. Measure the running time and memory use for rendering scenes
with this method compared to the current aggregates.
② Eisemann et al. (2007) described an
even more efficient ray–box intersection test than is used in the
BVHAggregate. It does more computation at the start for each ray but
makes up for this work with fewer computations to do tests for individual
bounding boxes. Implement their method in pbrt, and measure the change in
rendering time for a variety of scenes. Are there simple scenes where the
additional upfront work does not pay off? How does the improvement for
highly complex scenes compare to the improvement for simpler scenes?
② Although the intersection algorithm implemented in the
IntersectTriangle() function is watertight, a source of inaccuracy in
ray–triangle intersections computed in pbrt remains: because the
triangle intersection algorithm shears the vertices of the triangle, it may
no longer lie in its original bounding box. In turn, the BVH traversal
algorithm must be modified to account for this error so that valid
intersections are not missed. Read the discussion of this issue in Woop et
al.’s paper (2013) and modify pbrt to fix this issue. What
is the performance impact of your fix? Can you find any scenes where the
image changes as a result of it?
② Read the paper by Segovia and Ernst (2010) on
memory-efficient BVHs, and implement their approach in pbrt. How does
memory usage with their approach compare to that for the BVHAggregate? Compare
rendering performance with your approach to pbrt’s current
performance. Discuss how your results compare to the results reported in
their paper.
② Modify pbrt to use the “mailboxing” optimization in
the KdTreeAggregate to avoid repeated intersections with primitives
that overlap multiple kd-tree nodes. Given that pbrt is multi-threaded,
you will probably do best to consider either the hashed mailboxing approach
suggested by Benthin (2006) or the inverse mailboxing
algorithm of Shevtsov et al. (2007a). Measure the
performance change compared to the current implementation for a variety of
scenes. How does the change in running time relate to changes in reported
statistics about the number of ray–primitive intersection tests?
② Consider a scene with an animated camera that is tracking
a moving object such that there is no relative motion between the two. For
such a scene, it may be more efficient to represent it with the camera and
object being static and with a corresponding relative animated
transformation applied to the rest of the scene. In this way, ray
intersections with the tracked object will be more efficient since its
bounding box is not expanded by its motion.
Construct such a scene and then measure the performance of rendering it
with both ways of representing the motion by making corresponding changes
to the scene description file. How is performance affected by the size of
the tracked object in the image? Next, modify pbrt to automatically
perform this optimization when this situation occurs. Can you find a way
to have these benefits when the motion of the camera and some objects in
the scene are close but not exactly the same?
③ It is often possible to introduce some approximation into
the computation of shadows from very complex geometry (consider, e.g., the
branches and leaves of a tree casting a shadow). Lacewell
et al. (2008) suggested augmenting the acceleration
structure with a prefiltered directionally varying representation of
occlusion for regions of space. As shadow rays pass through these regions,
an approximate visibility probability can be returned rather than a binary
result, and the cost of tree traversal and object intersection tests is
reduced. Implement such an approach in pbrt, and compare its performance
to the current implementation. Do you see any changes in rendered images?