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:
“Someone in the crowd said to him, “Teacher, tell my brother to divide the family inheritance with me.” But he said to him, “Friend, who set me to be a judge or arbitrator over you?””
—Bible: New Testament, Luke 12:13,14.
Jesus.
“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)