Binary Space Partitioning Trees:Visibility Orderings.

Visibility Orderings

Visibility orderings are used in image synthesis for visible surface determination (hidden surface removal), shadow computations, ray tracing, beam tracing, and radio sity. For a given center of projection, such as the position of a viewer or of a light source, they provide an ordering of geometric entities, such as objects or faces of objects, consistent with the order in which any ray originating at the center might intersect the entities. Loosely speaking, a visibility ordering assigns a priority to each object or face so that closer objects have priority over objects further away. Any ray emanating from the center or projection that intersects two objects or faces, will always intersect the surface with higher priority first. The simplest use of visibility orderings is with the “Painter’s Algorithm” for solving the hidden surface problem. Faces are drawn into a frame-buffer in far-to-near order (low-to-high priority), so that the image of nearer objects/polygons over-writes those of more distant ones.

A visibility ordering can be generated using a single hyper plane; however, each geometric entity or “object” (polyhedron, polygon, line, point) must lie completely on one side of the hyper plane, i.e. no objects are allowed to cross the hyper plane. This requirement can always be induced by partitioning objects by the desired hyperplane into two “halves”. The objects on the side containing the viewer are said to have visibility priority over objects on the opposite side; that is, any ray emanating from the viewer that intersects two objects on opposite sides of the hyper plane will always intersect the near side object before it intersects the far side object. See Figures 20.7 and 20.8.

Total Ordering of a Collection of Objects

A single hyper plane cannot order objects lying on the same side, and so cannot provide a total visibility ordering. Consequently, in order to exploit this idea, we must extend it somehow so that a visibility ordering for the entire set of objects can be generated. One way to do this would be to create a unique separating hyper plane for every pair of objects. However, for n objects this would require n2 hyper planes, which is too many.

The required number of separating hyper planes can be reduced to as little as n by using the geometric version of recursive subdivision (divide and conquer). If the subdivision is performed using hyperplanes whose position and orientation is unrestricted, then the result is a BSP Tree. The objects are first separated into two groups by some appropriately chosen hyper plane (Figure 20.9). Then each of the two groups is independently partitioned into two sub-groups (for a total now of 4 sub-groups). The recursive subdivision continues in a similar fashion until each object, or piece of an object, is in a separate cell of the partitioning. This process of partitioning space by hyper planes is naturally represented as a binary tree (Figure 20.10).

Visibility Ordering as Tree Traversal

How can this tree be used to generate a visibility ordering on the collection of objects? For any given viewing position, we first determine on which side of the root hyper plane the viewer lies. From this we know that all objects in the near-side sub tree have higher priority than all objects in the far-side sub tree; and we have made this determination with only a constant amount of computation (in fact, only a dot product). We now need to order the near-side objects, followed by an ordering of the far-side objects. Since we have a recursively defined structure, any sub tree has the same form computationally as the whole tree. Therefore, we simply apply this technique for ordering sub trees recursively, going left or right first at each node, depending upon which side of the node’s hyperplane the viewer lies. This results in a traversal of the entire tree, in near-to-far order, using only O(n) operations, which is optimal (this analysis is correct only if no objects have been split; otherwise it is > n).

Intra-Object Visibility

The schema we have just described is only for inter-object visibility, i.e. between individual objects. And only when the objects are both convex and separable by a hyper plane is the schema a complete method for determining visibility. To address the general unrestricted case, we need to solve intra-object visibility, i.e. correctly ordering the faces of a single object. BSP Trees can solve this problem as well. To accomplish this, we need to change our focus from convex cells containing objects to the idea of hyper planes containing faces. Let us return to the analysis of visibility with respect to a hyper plane. If instead of ordering objects, we wish to order faces, we can exploit the fact that not only can faces lie on each side of a hyper plane as objects do, but they can also lie on the hyper plane itself. This gives us a 3-way ordering of: near → on → far (Figure 20.11).

If we choose hyper planes by which to partition space that always contain a face of an

object, then we can build a BSP Tree by applying this schema recursively as before, until every face lies in some partitioning hyperplane contained in the tree. To generate a visibility ordering of the faces in this intra-object tree, we use the method above with one extension: faces lying on hyper planes are included in the ordering, i.e. at each node, we generate the visibility ordering of near-sub tree → on-faces → far-sub tree. Using visibility orderings provides an alternative to z-buffer based algorithms. They obviate the need for computing and comparing z-values, which is very susceptible to numerical error because of the perspective projection. In addition, they eliminate the need for z-buffer memory itself, which can be substantial (80Mbytes) if used at a sub-pixel resolution of 4x4 to provide anti-aliasing. More importantly, visibility orderings permit unlimited use of transparency (non-refractive) with no additional computational effort, since the visibility ordering gives the correct order for compositing faces using alpha blending. And in addition, if a near-to-far ordering is used, then rendering completely occluded objects/faces can be eliminated, such as when a wall occludes the rest of a building, using a beam-tracing based algorithm.