BSP analytic visibility

From CGAFaq

Analytic visibility is a term which describes the list of surfaces visible from a single point in a scene. Analytic visibility is important to the architectural community because it may be necessary to obtain a visible lines only view of a building for output to a pen plotter. It is also important to the global illumination community because it makes it possible to accurately compute the form factor from a differential area to a patch. Analytic visibility is also used in a preprocessing step to speed up walkthrough renderings for large models.

BSP trees can be used to compute visible fragments of polygons in a scene in at least two different ways. Both methods involve the use of a BSP tree for front to back traversal, and a second tree which describes the visible space in the viewing volume.

Screen partitioning

This method uses a two dimensional BSP tree to partition the viewing plane into regions which have and have not been covered by previously rendered polygons. Whenever a polygon is rendered, it is inserted into the screen tree and clipped to the currently visible region. In the process, the visible region of the polygon is removed from the visible region of the screen.

Beam tree

This method clips each polygon drawn to a beam tree which defines the viewable area. The beam tree originates as a description of the viewing frustum, and is in fact a special kind of BSP tree. When a new polygon is rendered, it is first passed through the beam tree to obtain the visible fragments in a manner very similar to the union operation for boolean modelling. Each fragment is then used to describe a new beam consisting of a series of planes through the eye point and each edge of the fragment. These planes become the hyperplanes used for defining new partitions in the beam tree.