Graphics Reference
In-Depth Information
Velocity vector
Position at time
t
0
Position at time
t
1
Bounding capsule for the ball on the interval [
t
0
,
t
1
]
Figure 37.2: During any time interval, a sphere moving with constant velocity traces the
volume of a capsule. If the intersection of the capsule and the boxes is not empty during a
time interval, a collision occurred during that interval.
• The intersection of a ball
1
around a light source with a scene to determine
which objects receive significant direct illumination from it
• The intersection of a ball with a set of stored incoming photon paths to
estimate radiance in photon mapping
In the dynamics example of a scene with three boxes and a single moving
sphere, it would be reasonable to compute the capsule at each time step and then
iterate through all boxes testing for intersections with it. That strategy for colli-
sion detection would not scale to a scene with millions of geometric primitives.
Informally, to scale well, we require an algorithm that can detect a collision in
fewer than a linear number of operations in the number of primitives,
n
. We expect
that using data structures such as trees can reduce the intersection-testing costs to
O(log
n
)
in the average case, for example. The best asymptotic time performance
that an algorithm could exhibit in a nontrivial case is
O(
m
)
for
m
actual intersec-
tions, since the intersections themselves must be enumerated. This is achievable
if we place spatial distribution constraints on the input; for example, accepting an
upper bound on the spatial density of primitives [SHH99]. Note that even with
such constraints,
m
=
n
in the worst case, so any spatial intersection query neces-
sarily exhibits worst-case
O(
n
)
time complexity. Furthermore, obtaining optimal
performance might require more storage space or algorithmic complexity than an
implementation is able to support.
There is no “best” spatial data structure. Different ones are appropriate for dif-
ferent data and queries. For example, finding capsule-box intersections in a scene
with four primitives lends itself to a different data structure than ray-triangle inter-
sections in a scene with millions of rays and triangles. This is the same principle
1. A ball is the volume inside the sphere; technically, a geometric sphere
S
k
is the
(
k
−
1
)
dimensional surface and not the
k
-dimensional volume within it. However, beware
that intersections with balls are casually referred to as “sphere intersections” by most
practitioners.
