3.2. Representing Objects with BSPs

BSPs offer a nice way to represent volumetric polygonal objects, i. e., closed objects. In other words, their border is represented by polygons and they have an inside and an outside. Such a BSP representation of an object is just like an ordinary BSP for the set of polygons (we can, for instance, build an auto-partition), except that here we stop the construction process (see Definition 3.1) only when the set is empty. These leaves represent homogeneous convex cells of the space partitioningthey are completely in our out.

Figure 3.4 shows an example of such a BSP representation. In this section, we will follow the convention that normals point to the outside, and that the right child of a BSP node lies in the positive half-space and the left child in the negative half-space. So, in a real implementation that adheres to these conventions, we can still stop the construction when only one polygon is left, because we know that the left child of such a pseudo-leaf will be in and the right one will be out.

Figure 3.4: Each leaf cell of the BSP representation of an object is completely inside or completely outside.

Given such a representation, it is very easy and efficient, for instance, to determine whether a given a point is inside an object. We just filter the point down through the BSP until we reach a leaf.

In the next section, we will describe an algorithm for solving a slightly more difficult problem.