Editing Hidden-surface determination (section)

== Divide and conquer ==
A popular theme in the visible surface determination literature is [[divide-and-conquer algorithm|divide and conquer]]. The [[Warnock algorithm]] pioneered dividing the screen. [[Beam tracing]] is a ray-tracing approach that divides the visible volumes into beams. Various screen-space subdivision approaches reduce 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. Z-buffer hardware may typically include a coarse "hi-Z", against which primitives can be rejected early without rasterization. Such an approach is a form of occlusion culling.

[[Bounding volume hierarchy#Scene-graph and bounding volume hierarchies .28BVHs.29|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 approach allows visibility determination to be performed hierarchically: 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 needs 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.