Graphics Reference
In-Depth Information
reasonably certain that the objects in fact intersected. By associating bounding boxes
to objects, a quick test for whether two objects intersect is to check if their associated
bounding boxes intersect. Finding the intersection of two boxes is easy, but since
bounding boxes get used a lot in computer graphics, it is worthwhile to use some
especially efficient algorithms for doing this. This section describes such algorithms
using the results from Sections 17.2 and 17.3.
Interval Intersections.
Assume that we are given a set I of n intervals. We want to
determine those that intersect a given interval [a,b]. This problem can be reduced to
two searches:
Step 1:
Find those intervals which contain a.
Step 2:
Find those intervals whose left endpoint belongs to [a,b].
For Step 1 we can use an interval tree. This approach would take O(n) space. It takes
O(n log
2
n) time to build the tree and O(log
2
+ k) time for each query that has k
answers. We could also use a segment tree but that takes more space, namely,
O(n log
2
n). Step 2 is just a one-dimensional range query problem that can be solved
with a balanced binary search tree built from the left endpoints of the intervals in I.
It has the same space and time complexity as the interval tree for Step 1.
Rectangle Intersections.
Assume that we are given a set R of n axis-parallel rec-
tangles in the plane. We want to determine those that intersect a given rectangle or
window [a,b] ¥ [c,d]. One approach to solving this problem is to use interval trees for
the segments that make up the boundary of the rectangles. The only rectangles that
will be missed are ones that either contain the window or are disjoint from it. One
can check for these rectangles separately in time O(n) by checking if the vertices are
either all inside or all outside the rectangle. It follows that the k intersecting rectan-
gles can be reported in time O(log
2
2
n + k) using a data structure that uses O(n log
2
n)
space and which can be built in time O(n log
2
n). Segment trees could also be used at
the cost of somewhat higher storage requirement (O(n log
2
2
n)).
Box Intersections.
Assume that we are given a set B of n axis-parallel boxes in
R
3
.
We want to determine those that intersect a given box [a,b] ¥ [c,d] ¥ [e,f]. This problem
can also be solved by reducing it to a lower-dimensional problem. By considering the
rectangle faces of the boxes, we can think of it as three two-dimensional problems
with an extra dimension that is handled with a balanced binary search tree. This
would lead to a query complexity of O(log
3
2
n + k). A slightly faster O(log
2
2
n + k) algo-
rithm is obtained with a sweep algorithm. We sketch this approach next. For more
details see [Hoff89].
Box Intersections Based on Sweeping.
We sweep a plane parallel to the x-y plane
in a positive direction along the z-axis. Every box intersection will then show up as a
rectangle intersection in one of these planes. See Figure 17.6. As one moves the sweep
plane at height z the only time anything changes with respect to one of the boxes [x
1
,
x
2
] ¥ [y
1
, y
2
] ¥ [z
1
, z
2
] is when one passes the top or bottom face of this box, that is,
z passes the values z
1
and z
2
. Let R(z) denote the set of rectangles that are the inter-
sections of all the boxes with the sweep plane at level z. Thought of as rectangles in
