Choosing a Splitting Plane

The question still remains as to which polygon's plane, at any given point, is the best plane to choose for splitting the space. The answer depends on how we use the BSP tree. But generally, it is best to try to choose the splitting planes such that, after splitting, larger sub-spaces contain few polygons and smaller sub-spaces contain many polygons [NAYL98]. Striving for a balanced tree is usually not desirable, because the underlying geometry is usually not evenly distributed [NAYL98]. Remember that each node in the BSP tree represents a convex region formed by slicing up space by all planes along the path to the node. Furthermore, the region of a node is always large enough to contain all of the geometry beneath it in the BSP tree. By choosing the splitting planes as described above (many polygons in small spaces), the resulting BSP tree structure places volumes containing many polygons at relatively shallow levels of the tree. Assuming such groups of polygons represent local and not global features of interest in the underlying polygonal geometry (Bruce Naylor refers to this as the principle of locality [NAYL98]), then such a tree allows us to find volumes containing features of interest quickly, because we don't need to traverse the tree too deeply to find the volumes containing interesting groups of polygons representing local features of the geometry.

Figure 5-7: An arm/hand polygonal model and two different BSP trees for the same model. All vertex normals for the polygons in the hand model point outward; the splitting planes' normals point in the same direction as the corresponding polygons' normals. The BSP tree is constructed with the convention that the left child lies behind the splitting plane; the right child, in front of the plane. Note that for simplicity the BSP trees shown here are not complete, since a complete tree would require using every polygon as a splitting plane.

Figure 5-7: An arm/hand polygonal model and two different BSP trees for the same model. All vertex normals for the polygons in the hand model point outward; the splitting planes' normals point in the same direction as the corresponding polygons' normals. The BSP tree is constructed with the convention that the left child lies behind the splitting plane; the right child, in front of the plane. Note that for simplicity the BSP trees shown here are not complete, since a complete tree would require using every polygon as a splitting plane.

To understand this partitioning principle, consider the model in Figure 5-7. In this model, we have many polygons around the hand and fingers, and few polygons around the arm. The principle of locality states that the group of many polygons probably represents an interesting set of local features. Indeed it does—it represents the "hand" of our model. With a BSP tree, it is better to partition space such that the hand, containing many polygons, is in one small region, and the arm, containing few polygons, is in one large region. This is the BSP tree illustrated in the bottom left of the figure. An alternative, more balanced but poorer tree, is at the bottom right of the figure. Notice that the first splitting plane in the poorer, balanced tree splits the interesting region (the hand) into two regions.

Then, consider the question of point classification—is a particular point in the hand, or not? For instance, if you were simulating a hand catching a ball, the center point of the ball would need to be in the region of the hand in order to be caught. With the good tree on the left, as soon as we find out that the point is in the spatial region of node 3, which is the union of the children regions C and D, we know that the point cannot lie within the hand. (We classify a point in this manner by evaluating the plane equation of the splitting plane with the point's coordinates, as discussed in the introductory companion book Linux 3D Graphics Programming.) Thus, with the good tree, we can potentially know the answer to the point classification question at the first level of the BSP tree. Otherwise, if the point is in region 2, we further traverse this primarily hand-containing branch of the tree to compare the point with smaller and smaller spaces (defined by their splitting planes) until we finally know if the point is in the hand or not.

With the poor tree on the right, only region B can be excluded with certainty from the hand; and reaching region B requires us to traverse deeper in the tree to the second level. Furthermore, the interesting hand region has been split into the three regions A, C, and D, located in different sub-trees. Contrast this with the good BSP tree, where the interesting region was all in one subtree, adhering to the principle of locality. The split of the interesting region into many smaller parts means that to answer the question of point classification, we have to traverse deeper into the tree in many different branches. By using the principle of locality and trying to group large numbers of polygons into small areas, we try to make interesting regions reachable quickly through the tree for quicker point classification.

Naylor presents algorithms using expected case heuristics (rules of thumb guiding the algorithm at each stage to make a "best guess") to choose the splitting plane that most likely leads to good trees, where "good" is specified as a probability function [NAYL98]. Producing good trees requires the use of such guiding heuristics because the only known way of producing an optimal tree is by exhaustive search [NAYL98], which is far too slow.

Another possibility for choosing a splitting plane is to use the number of polygon splits as the criteria for choosing a splitting plane. We choose a few splitting planes at random, then see how many polygons would need to be split for each chosen splitting plane. The plane causing the fewest splits is then chosen [FOLE92]. However, minimizing splits does not necessarily automatically maximize the principle of locality. It is possible to construct scenes where no polygon's plane would split any other; then, if minimizing splits is the only guiding heuristic, plane selection becomes arbitrary. Combining several heuristics is generally the best way to construct good trees.

Was this article helpful?

0 0

Post a comment