Graphics Reference
In-Depth Information
(a)
(b)
Figure 8.6
(a) A configuration of 12 faces wherein all possible autopartitioned dividing
planes end up splitting four faces. (b) Using arbitrary splits can allow the configuration to
be partitioned in such a way that the problem disappears or is reduced.
B
A
A
A
B
B
D
E
F
C
C
C
(a)
(b)
(c)
Figure 8.7
(a) An autopartitioned BSP tree for a polygonal sphere has worst-case
O
(
n
) height.
(b) Allowing arbitrary cuts across the sphere, tree height is reduced to
O
(log
n
). (c) Nay-
lor's hybrid approach of alternating autopartitioning and general cuts also allows a boundary
representation of the sphere to have
O
(log
n
) height, additionally providing early outs.
single polygon is left in the leaves, at which point its supporting plane is selected as
the dividing plane. The drawback with this approach is that
all
leaves are now at an
O
(log
n
) depth, and thus there are no early outs for queries such as those well outside
the sphere.
A better option is suggested by [Naylor93]. He proposes using a hybrid approach
of alternating autopartitioning and general cuts to get both an
O
(log
n
) tree height
and potential early outs. A set of autopartitioning planes is first selected to separate
the sphere from the surrounding empty space, forming a tetrahedron surrounding
