Graphics Reference
In-Depth Information
CB
and
BD
must be clipped.
CB
intersects the plane at
F
CB
, subtly different from
F
BC
(the errors of the intersection points have been exaggerated to better illustrate the
point). As can be seen from the illustration, this clearly introduces a crack between
the clipped faces.
To robustly deal with this case, the clipping code must always intersect the given
edge consistently as
either BC
or
CB
, but not
both
. Fortunately, the change is trivial:
because an edge is only clipped when its endpoints lie on different sides of the plane,
the edge can always be intersected as if it were ordered going from in front of the
plane to behind the plane (or vice versa).
For the clipping code of the previous section, the only change required
is thus swapping the edge endpoints for the arguments to the first call to
IntersectEdgeAgainstPlane()
, as follows.
...
if (bSide == POINT_IN_FRONT_OF_PLANE) {
if (aSide == POINT_BEHIND_PLANE) {
// Edge (a, b) straddles, output intersection point to both sides.
// Consistently clip edge as ordered going from in front -> behind
Point i = IntersectEdgeAgainstPlane(b, a, plane);
...
}
...
Figure 8.15c illustrates the result of using a correct clipping procedure: the crack
between the triangles exists no longer.
8.3.6
Tuning BSP Tree Performance
Tuning various BSP tree parameters to achieve best possible performance is a difficult
problem. Is splitting strategy
A
better than strategy
B
? At what depth should tree
construction stop? What is the most appropriate value of the variable
K
in the function
PickSplittingPlane()
?
To help evaluate different settings of various parameters, a good approach is to
build a reference database of queries that occur at runtime, for example by player or
enemies. These are logged during a normal run and saved along with the world col-
lision geometry used. Because this database can be used to perform identical queries
against different spatial partitionings of the collision geometry, it now becomes easy
to compare different parameter settings, allowing the creation of a good spatial parti-
tioning. If desired, tuning of the parameters themselves can be easily automated
through a hill-climbing-like mechanism (such as simulated annealing or genetic
algorithms).
