## Binary Space Partitioning Trees Octrees and Regular Spatial Partitioning

We mentioned in Chapter 4 the correctness and visibility aspects of VSD algorithms. The binary space partitioning (BSP) tree and octree algorithms are VSD algorithms which address both the correctness and efficiency issues of VSD. First, let's cover BSP trees; later, we'll look at octrees. The two algorithms are quite similar.

The BSP tree divides space hierarchically into regions in a time-consuming, one-time preprocessing step, then later allows determination of a correct back-to-front or front-to-back polygon ordering, for any viewpoint, without sorting the polygons (in contrast to the simple painter's algorithm). Since the construction of the BSP tree takes a lot of time, the BSP tree algorithm is generally best suited for scenes where most of the polygons do not move because moving polygons would force a recomputation of at least part of the tree. (There are ways of incorporating movement into BSP trees, but they are a bit tricky; see Bruce Naylor's article "A Tutorial on Binary Space Partitioning Trees" for details on so-called "tree merging." [NAYL98])

The BSP tree is based upon a very simple idea. Consider a space. Concretely, you can think of this "space" as a huge box large enough to contain all geometry in your virtual world. Then, consider a plane with arbitrary orientation located somewhere within this space. As we have seen, a plane is infinitely wide and high, has a front side, and has a back side. Thus, we can think of the plane as dividing the space into two regions: the region in front of the plane and the region behind the plane. (We can also consider the region exactly on the surface of the plane to be a third region, or we can assign it arbitrarily to the front or back side.) Figure 5-1: A plane divides space into two regions—three, if we count the surface of the plane itself.

We use the term halfspace to describe each region that results from the splitting of a space by a plane. Then, given a half space, we can again choose a splitting plane within this half space, which again results in two half spaces. We can continue this splitting process indefinitely. Figure 5-2: Each half space can be split again by a plane. Figure 5-3: The process of half space splitting can be extended to an arbitrary number of levels.

Thus, we are using planes to hierarchically slice space into smaller and smaller regions. We can store such a hierarchical space division in memory as a tree data structure. Each internal node of the tree contains a plane, and has two child nodes: one for the half space on the front side and one for the half space on the back side of the plane. Each node of the tree also represents the small region of space which remains after being sliced by all parent nodes along the path to the node. This tree is the BSP tree: it is a binary partition of space. It is binary because a plane has two sides, a front and a back; it is a space partition, because we use the plane to split or partition the space into exactly two pieces. Let us use the convention that the left child of a BSP tree node represents the space behind the partitioning plane of the parent, and the right child is the space in front of the partitioning plane.

Notice that we thought of the original space as a huge bounding box enclosing all of the geometry in our world. For any size of geometry, it is always possible to make a bigger bounding box to enclose all of it. Thus, we can always think of the entire world space as being a huge box. A box is convex; it has no concave dents or holes in it. And when repeatedly slicing a convex shape with a plane, the resulting pieces are also always convex. This is because each plane is infinitely wide and high, and slices all geometry along its way, within the space or half space it divides. To understand this geometrically, take a piece of paper and a pair of scissors. The paper represents the original space. Cut the paper in two, using only one straight cut. Notice that each piece is still convex. Continue cutting each half piece in two, again using only straight cuts that go all the way from one side of the paper to the other, forming two pieces. You'll notice that you can never produce a concave piece by slicing in this manner; this is because each slice goes straight through the entire piece, preserving convexity.

The question remains as to why we want to partition space in this manner. Consider a set of polygons located within a space. If we can partition the polygons into two disjointed spaces, called A and B, then this partitioning encodes a viewpoint-independent visibility relationship between A and B. Note that if any polygons cross the boundary between A and B, they must be split into two parts, one completely in A and one completely in B. Essentially, the partition states "A is separate from B." This is also the reason that polygons must be split if they cross the partition boundary: the regions must be separate. Then, given this separation of regions, we can use the camera position combined with the partitioning to determine the relative visibility of A and B. If the camera is in A, then no polygon in B can obscure any polygon in A. Similarly, if the camera is in B, then no polygon in A can obscure any polygon in B [SCHU69]. The partitioning, combined with the camera position, gives us a visibility ordering among the regions of space; using the painter's algorithm, we can draw the far space first, then the near space. Then, within each smaller half space, we again use the camera position with respect to the half space's partitioning plane to determine the ordering of the sub-half-spaces within each half space. We continue recursively all the way down to the polygon level (exactly how polygons fit into the scheme is covered in the next section), which gives us a visibility ordering for all polygons within the scene—without the need for sorting the polygons.

Figure 5-4: A set of polygons within a space.  Figure 5-5: The space has been partitioned into two regions. If the camera is in region A, we know that no objects from region B can obscure any objects from region A. Similarly, if the camera is in region B, we know that no objects from region A can obscure any objects from region B. Note that one polygon, which crossed the splitting plane, had to be split into two pieces. If each smaller region is further subdivided, we apply the same visibility ordering principle recursively.

Figure 5-5: The space has been partitioned into two regions. If the camera is in region A, we know that no objects from region B can obscure any objects from region A. Similarly, if the camera is in region B, we know that no objects from region A can obscure any objects from region B. Note that one polygon, which crossed the splitting plane, had to be split into two pieces. If each smaller region is further subdivided, we apply the same visibility ordering principle recursively.