Graphics Reference
In-Depth Information
6.2.1
Theorem.
The boxes
=
[
]
¥
[
]
¥¥
[
]
=
[
]
¥
[
]
¥¥
[
]
X
a
,
b
a
,
b
...
a
,
b
and
Y
c
,
d
c
,
d
...
c
,
d
11
2 2
nn
11
2 2
nn
will intersect if and only if
(
(
)
(
)
)
£=
(
(
)
(
)
)
lb
=
max min
a
,
b
, min
c
,
d
ub
min max
a
,
b
, max
c
,
d
i
i
i
i
i
i
i
i
i
i
for all i. If they intersect, then
X
«=
[
]
¥
[
]
¥¥
[
]
lb
,
ub
lb
,
ub
...
lb
u
nn
,
.
11
2 2
Proof.
Easy. See Figure 6.1(b).
For obvious reasons, the intersection test in Theorem 6.2.1 is usually called the
minimax test
.
A bounding box for a polygon can be defined from the minimum and maximum
values of all the coordinates of its vertices. Looking ahead, the bounding box for a
spline curve or surface (defined in Chapters 11 and 12) is usually taken to be a bound-
ing box for its control points. (This uses the important fact that splines lie in the
convex hull of their control points.) Other objects may have to have their bounding
boxes defined by hand.
Bounding boxes are probably the most common bounding objects that are used
because it is so easy to work with them, but they are far from perfect. The main
problem is that they may be a bad fit to the object. For example, the best bounding
box for a line segment has that line segment as a diagonal. It is clearly easy to find
lots of other objects for which rectangular boxes are a bad fit. For that reason, other
bounding objects may be more appropriate for any given world of objects. There is
nothing to keep us from using different types of bounding objects within one program
to optimize fits. Unfortunately though, usually the better the fit, the more complicated
it is to compute intersections.
A natural way to generalize bounding boxes is to allow bounding faces to be
slanted and not just horizontal or vertical.
A
slab
in
R
n
is the region between two parallel hyperplanes.
Definition.
Given a
bounded
set
X
, a unit vector
n
determines a slab as follows: Starting arbi-
trarily far out on the two ends of the line through the origin with direction vector
n
,
slide two hyperplanes orthogonal to
n
towards the origin until they touch
X
.
Definition.
The region between the two touching planes is called the
slab for
X
induced by the unit vector
n
and is denoted by Slab(
X
,
n
).
See Figure 6.2(a). The two hyperplanes that bound the slab Slab(
X
,
n
) can be
written in the form
near
far
,
n•p
=
d
and
n•p
=
d
where d
near
£ d
far
. The plane that corresponds to the d
near
will be called the
near
plane
for the slab and the other one, the
far plane
. Note that if we were to project
X
orthogonally to the line through the origin with direction vector
n
, then
X
would
project
onto
the segment [d
near
n
,d
far
n
].
We can use more than one vector
n
.
