Graphics Reference
In-Depth Information
8.3.2
Evaluating Dividing Planes
Many general strategies have been suggested for evaluating splitting planes (see,
for example, [James99]). A majority of these are based on the assumption of a node-
storing tree, such as selecting the supporting plane of the face with the largest number
of coplanar faces or of the face with the largest area. Storing these faces in the node
would thus remove from further consideration a large number of faces (in the first
case) or a face with a high likelihood of being split (in the second case).
Two strategies particularly relevant to collision detection are to pick planes so as
to minimize splitting of geometry and to attempt to balance the geometry equally
on both sides of the splitting plane. The former
least-crossed
strategy attempts to
minimize the duplication of geometry due to splitting. Worst case, when starting
with
n
polygons each split can introduce
n
additional polygons through splitting.
Thus, it is possible to end up with
O
(
n
2
) polygons in the final result. Because dividing
planes with few straddling polygons are usually found at the periphery of a scene, used
in isolation the least-crossed strategy is therefore likely to produce very unbalanced
trees. On the other hand, balancing cuts — although they produce nicely structured
trees — are likely to cause an excessive amount of split geometry because they tend to
cut straight down the middle of a scene and its objects. A weighted linear combination
of the two is therefore used in practice. Reducing splitting is often weighted much
higher than balancing. Figure 8.8 illustrates a split intended to minimize straddling
polygons, a split to achieve balance of the number of polygons on either side of the
splitting plane, and a split intended as a compromise between minimizing straddling
and balancing of polygons.
The following code fragment illustrates a very basic autopartitioning selection of a
splitting plane. Here, all supporting planes of the set of polygons are considered for
splitting. A weighted linear combination between the conflicting goals of trying to
reduce splitting and attempting to increase balancing is used to evaluate the planes.
C
A
B
Figure 8.8
Part of a city grid split to minimize straddling polygons (
A
), balance the number
of polygons on either side of the dividing plane (
B
), and compromise between minimizing
straddling and balancing of polygons (
C
).
