Graphics Reference
In-Depth Information
There are of course many other useful intersection queries, such as the capsule-
box intersection from the collision detection example. For an application in which
a particular intersection query occurs very frequently and affects the performance
of the entire system, it may be a good idea to implement a data structure designed
for that particular query.
In other cases, it may make more sense to perform intersection computations
in two passes. In that case, the first pass leverages a general spatial data structure
from a library to conservatively find intersections against some proxy geometry.
The second pass then performs exhaustive and precise intersection testing against
only the primitives returned from the first query. For the right kinds of queries, this
combines the performance of the sophisticated data structure with the simplicity
of list iteration.
For example, dynamics systems often step through short time intervals com-
pared to the velocities involved, so the capsule swept by a moving ball may in
fact not be significantly larger than the original ball. It can thus be reasonably
approximated by a ball that encloses the entire capsule, as shown in Figure 37.4.
A generic ball-box intersection finds all boxes that are near the capsule, includ-
ing some that may not actually intersect the capsule. If there are few boxes
returned from this query, simply iterating through that set is efficient. In fact, the
two-pass operation may be
more
efficient than a single-pass query on a special-
purpose data structure for capsule-box intersection. This is because the geometric
simplicity of a ball may allow optimizations within the data structure that a cap-
sule may not admit.
Figure 37.4: Approximating a
short capsule (dashed line) with
a bounding ball (solid line). To
satisfy persistence of vision, the
rendering frame rate for an ani-
mation is usually chosen so that
objects move only a fraction of
their own extent between frames.
In this case, a static bounding
ball around the path of a dynamic
ball is not too conservative.
Like a ball, an axis-aligned box and a ray have particularly simple geome-
try. Thus, while our three sample intersection query methods motivate the design
patterns that could be applied to alternative query geometry, they are often good
choices in themselves.
Some careful choices in the specifications of intersection query methods can
make the implementation and the application particularly convenient. We now
detail a particular specification as an example of a useful one for general appli-
cation. Consider this as a small case study of some issues that can arise when
designing spatial data structures, and add the solutions to your mental program-
mer's toolbox.
You may follow the exact specification given here at some point, but more
likely you will apply these ideas to a slightly different specification of your own.
You will also likely someday find yourself using someone else's spatial data struc-
ture API. That API will probably follow a different specification. Your first task
will be to understand how it addresses the same issues under that specification,
and how the differences affect performance and convenience.
Method
getBallIntersection
,
1
2
3
void
getBallIntersection
(
const
Ball
& ball,
std::vector<
Value
*
>& result)
const
;
appends all primitives that overlap (intersect) the ball onto the result array.
2
It does
not return the strict intersection itself, which would require clipping primitives to
the ball in the general case.
2. In this chapter, “array” denotes a dynamic array data structure (e.g.,
std::vector
in
C++) to distinguish that concept from geometric vectors.
