Divide and Conquer
A popular theme in the VSD literature is divide and conquer. The Warnock algorithm pioneered dividing the screen. Beam tracing is a ray-tracing approach which divides the visible volumes into beams. Various screen-space subdivision approaches reducing the number of primitives considered per region, e.g. tiling, or screen-space BSP clipping. Tiling may be used as a preprocess to other techniques. ZBuffer hardware may typically include a coarse 'hi-Z' against which primitives can be rejected early without rasterization, this is a form of occlusion culling.
Bounding volume hierarchies (BVHs) are often used to subdivide the scene's space (examples are the BSP tree, the octree and the kd-tree). This allows visibility determination to be performed hierarchically: effectively, if a node in the tree is considered to be invisible then all of its child nodes are also invisible, and no further processing is necessary (they can all be rejected by the renderer). If a node is considered visible, then each of its children need to be evaluated. This traversal is effectively a tree walk where invisibility/occlusion or reaching a leaf node determines whether to stop or whether to recurse respectively.
Read more about this topic: Hidden Surface Determination
Famous quotes containing the words divide and/or conquer:
“Everything necessarily is or is not, and will be or will not be; but one cannot divide and say that one or the other is necessary. I mean, for example: it is necessary for there to be or not to be a sea-battle tomorrow; but it is not necessary for a sea-battle to take place tomorrow, or for one not to take place—though it is necessary for one to take place or not to take place.”
—Aristotle (384–322 B.C.)
“It was not reason that besieged Troy; it was not reason that sent forth the Saracen from the desert to conquer the world; that inspired the crusades; that instituted the monastic orders; it was not reason that produced the Jesuits; above all, it was not reason that created the French Revolution. Man is only great when he acts from the passions; never irresistible but when he appeals to the imagination.”
—Benjamin Disraeli (1804–1881)