Graphics Reference
In-Depth Information
not intersect. If they do intersect, well, then we will have to bite the bullet and check
out the original objects.
Definition.
A
bounding object
for an object
A
is any object
B
that contains
A
.
This section looks at some common types of bounding objects. Keep in mind the
following three desirable properties that bounding objects should possess:
(1) They should be easy to compute.
(2) It should be easy to tell if they intersect.
(3) They should “fit” an object fairly closely.
The motivation behind property (3) is that we are trying to detect disjointness quickly,
and the bigger that bounding objects are the more they will intersect, forcing us into
lengthy computations we are trying to avoid. For an analysis as to whether bounding
objects are really worth it see [SuHH99] and [ZhoS99].
A
box
in
R
n
is any subset of the form
Definition.
[
]
¥
[
]
¥¥
[
]
ab
,
a b
,
...
a
nn
,
,
11
2 2
where a
i
, b
i
Œ
R
. (It is convenient here to think of [a
i
,b
i
] as
segments
and not require
that a
i
£ b
i
.) A
bounding box
for an object is a box that contains the object.
Figure 6.1(a) shows a bounding box. It is easy to check for intersections of bound-
ing boxes. For example, two segments [a
1
,b
1
] and [a
2
,b
2
] intersect if and only if
(
(
)
(
)
)
£
(
(
)
(
)
)
max min
ab
,
, min
a b
,
min max
ab
,
, max
a b
,
,
11
2 2
11
2 2
and if they intersect, then the intersection is the
interval
[
(
(
)
(
)
)
(
(
)
(
)
)
]
max min
ab
,
, min
a b
,
, min max
ab
,
, max
a b
,
.
11
2 2
11
2 2
Notice how this formula shows that [1,5] « [2,7] = [2,5] and [1,5] « [7,9] = f. In
general, we have
Figure 6.1.
Bounding boxes.
