Graphics Reference
In-Depth Information
5
5a
5b
2
3
1
4
(a)
5
back
4
3
3
back
front
back
front
back
3
2
4
1
2
5a
4
5b
front
back
front
5a
1
5b
1
back
after 1 level
of recursion
2
complete tree
(b)
(c)
Figure 7.4.
A BSP example.
Consider the example shown in Figure 7.4. There are five polygons numbered from 1
to 5 in Figure 7.4(a). The arrows are supposed to indicate the side containing the view-
point. (In this example, the chosen directions do not correspond to a possible situa-
tion.) We assume that polygon 3 is the one chosen first, then 2 and finally 4. The stages
of the BSP tree are shown in Figure 7.4(b). Note that choice of polygons can greatly
influence the outcome. Figure 7.4(c) shows the tree that we would get if the polygons
were chosen in the following order 5, 4, 3, 1, and 2.
Once the BSP tree is generated, it is easy to generate the view by traversing the
tree in in-order fashion. At each node of the tree determine whether the eye is in front
or in back of the current root polygon. Traverse the opposite side of the tree, output
the root polygon to the frame buffer, and then traverse the remaining side.
Algorithm 7.5.1 is a more precise description of how the BSP tree is built and tra-
versed. It was originally feared that the BSP tree would be significantly larger than
the input polygon list, but this did not turn out to be the case in practice. To cut down
on the number of polygons that are split, the following heuristic was used: Select that
polygon to be the root of the next subtree that cuts the fewest other polygons. It was
discovered that it was not necessary to look over
all
of the remaining polygons. Rather,
