Graphics Reference
In-Depth Information
Again, these methods have largely been studied in conjunction with autopartitioning
and not with general dividing planes.
Certain evaluation criteria, such as balancing, naturally tend to avoid the reselec-
tion of dividing planes. Even so, it may still be useful to include an explicit mechanism
for avoiding reselection of a dividing plane that has already been used. When autopar-
titioning, reselection is easily avoided by tagging polygons as their supporting planes
are selected and then not selecting supporting planes of marked polygons. In other
cases, a history list of previously selected planes works as a simple solution.
8.3.3
Classifying Polygons with Respect to a Plane
As part of the BSP tree construction, after a dividing plane has been selected all
polygons must be partitioned with respect to this plane into one of the following
four categories.
Polygons that lie in front of the dividing plane.
●
Polygons that lie behind the dividing plane.
●
Polygons straddling the dividing plane.
●
Polygons coincident with the dividing plane.
●
Although theoretically straightforward, there is a problem with this classification
when working with floating-point arithmetic. The problem is that points computed
to lie on a given plane typically do not end up exactly on the plane but some small
distance away from the plane. This slight deviation from the plane means that when
a polygon is split by a dividing plane the resulting pieces do not necessarily classify
as one lying in front of the dividing plane and one lying behind it. For example,
inaccuracies in the computed intersection points could have both pieces straddling
the dividing plane even though the splitting operation conceptually created the two
pieces to lie on different sides of the plane. Addressing the floating-point issue is
necessary for robust classification of polygons into these four categories.
A practical solution to this problem is to work with
thick
planes, meaning that all
points within a small distance from the plane are considered lying on the plane. More
specifically, instead of working with a plane defined as
n
·
−
=
(
X
P
)
0 points are
considered on the plane if they satisfy
n
P
)
<ε
·
−
ε
. The following
function shows how the classification of a point to a thick plane can be implemented.
(
X
for some
// Classify point p to a plane thickened by a given thickness epsilon
int ClassifyPointToPlane(Point p, Plane plane)
{
