Graphics Reference
In-Depth Information
distance from the plane are still misclassified, the misclassification no longer affects
the robustness of polygon splitting, in that computed intersection points correctly
classify as lying on the thick plane.
Traditional methods for splitting a polygon to a plane must be changed slightly to
deal with a thick plane. These changes are discussed next.
8.3.4 Splitting Polygons Against a Plane
During BSP tree construction, when a polygon is found straddling a dividing plane
it must be split in two. One piece is then sent down one side of the plane, and the
other piece down the other side. To see why polygons must be split, consider the
illustration in Figure 8.11. Here, two splits have been made, dividing the world into
the three areas A , B , and C . The triangle T overlaps regions A and B , and thus should
be referenced in those leaves. However, if T is not split the following happens. First,
T is found straddling plane 1 and is sent down both sides. On the right side, T is now
tested against plane 2 and again sent down both sides. At this point all leaves have
been reached and T ends up in all of them!
When T is split against plane 1, only the small piece on the right side of the plane
goes down the right side of the tree. This piece lies fully on one side of plane 2,
and thus nothing goes into the leaf for region C . In other words, it is important to
perform clipping of polygons during tree construction. Such clipping limits polygons
from ending up in leaves whose associated spatial volume they did not intersect in
the first place.
An alternative is to maintain the spatial volumes corresponding to the leaves and
to perform polygon-convex-polyhedron tests to determine if a polygon should be
added to a leaf. Maintaining such volumes is only practically feasible for axis-aligned
BSP trees for which the leaf volumes are AABBs. In other cases, it is cheaper to split
the polygons during construction.
The act of clipping the polygon against a plane is commonly performed using the
Sutherland-Hodgman clipping algorithm [Sutherland74]. The algorithm proceeds
1
B
A
2
T
C
Figure 8.11 If T is not split by the first dividing plane, T straddles the second dividing plane
and a copy ends up in the leaf for C , which otherwise would have remained empty.
Search WWH ::




Custom Search