Graphics Reference
In-Depth Information
Here, the variable
K
controlling the blending of the least-crossed and balancing
strategies is given as a constant. In practice, it can be made to vary with the depth of
the current node during construction.
Because most collision queries will only traverse tree nodes to visit the one (or a
few) leaves of the tree overlapped by the query object, a well-balanced tree means
that all leaves are roughly at the same depth and worst-case behavior is avoided.
However, to improve average-case behavior dividing planes should not be selected
for balancing but instead to provide short traversal paths to areas that have a high
probability of being subject to query. As an illustration, consider the configuration
shown in Figure 8.9. In illustration (a) a dividing plane splits the space in half,
achieving perfect balance through an equal number of polygons on both sides of
the plane. Assuming point queries uniformly distributed over the space, the expected
number of polygons that would have to be tested is in this case 0. 5
5.
In illustration (b), the plane has instead been selected to divide the space into a 2/3
ratio, with two polygons on one side and eight on the other. The expected number
of polygons tested by the same uniform point query is now 2/3
·
5
+
0. 5
·
5
=
4, one
less than before. Instead of just assuming a uniform distribution of queries, as was
done here, statistics of query locations from actual runs could be used to determine
accurate probability values in these calculations.
In general, research indicates that not very many splitting planes must be con-
sidered for good results. Fuchs et al. point out that for the least-crossed criterion
near-minimal trees were obtained from just randomly selecting five candidate poly-
gons at each level and testing these against the other polygons [Fuchs80]. This result
is corroborated in [James99]. However, it should be noted that both results were
obtained using autopartitioning and node-storing trees. (In fact, a majority of the-
oretical results on BSP trees are based on using autopartitioning and node-storing
trees, thus differing greatly from typical practical use.)
More sophisticated evaluation methods have also been suggested, including
con-
flict minimization
[Fuchs80] and
conflict neutralization
[James00]. These approaches
consider two or more consecutive dividing planes at a time, selecting the plane at
the current level of the tree so as to reduce conflicts as much as possible (wherein
a conflict is the splitting of one or more faces by a possible future dividing plane).
·
2
+
1/3
·
8
=
(a)
(b)
Figure 8.9
(a) A balancing split. (b) A split to minimize expected query cost.
