 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
| Three-dimensional (3D) computer graphics |
|---|
 |
| Fundamentals |
| Primary uses |
| Related topics |
In3D computer graphics,hidden-surface determination (also known asshown-surface determination,hidden-surface removal (HSR),occlusion culling (OC) orvisible-surface determination (VSD)) is the process of identifying whatsurfaces and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determinationalgorithm is a solution to thevisibility problem, which was one of the first major problems in the field of 3D computer graphics.[citation needed] The process of hidden-surface determination is sometimes calledhiding, and such an algorithm is sometimes called ahider.[citation needed] When referring to line rendering it is known ashidden-line removal.[citation needed] Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.
Hidden-surface determination is a process that identifies which surfaces are not visible to the user (for example, because they lie behind opaque objects such as walls). Despite advances in hardware capability,rendering algorithms require substantial computational resources. By deciding that certain surfaces do not need to be rendered because they are not visible, rendering engines can improve efficiency, allowing the rendering of large world spaces.
There are many techniques for hidden-surface determination, but they generally rely onsorting the surfaces based on their distance from the viewer. Sorting large quantities of graphics primitives can be computationally-expensive and is usually done bydivide and conquer. The different hidden-surface determination techniques differ, in part, through the way in which the space is partitioned prior to sorting.
Arendering pipeline typically entails the following steps:projection,clipping, andrasterization.
Some algorithms used in rendering include:
A related area to visible-surface determination isculling, which usually happens before visible-surface determination in a rendering pipeline. Primitives or batches of primitives can be rejected in their entirety, whichusually reduces the computational load in a rendering system.Types of culling algorithms include:
Theviewing frustum is a geometric representation of the volume visible to thevirtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process calledclipping, and the pieces that lie outside the frustum are discarded as there is no place to draw them.
With 3D objects, some of the object's surface is facing the camera, and the rest is facing away from the camera, i.e. is on the backside of the object, hindered by the front side. If the object is completely opaque, those surfaces never need to be drawn. These surfaces are determined by the vertex winding order: if the triangle drawn has its vertices in clockwise order on the projection plane when facing the camera, they switch into counter-clockwise order when the surface turns away from the camera.
Incidentally, this approach also makes the objects completely transparent when the viewpoint camera is located inside them, because then all the surfaces of the object are facing away from the camera and are culled by the renderer. To prevent this artifact, the object must be set as double-sided (i.e. no back-face culling is done) or have separate inside surfaces.
Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screenprojection is too small. SeeClipping plane.
Objects that are entirely behind other opaque objects may be culled. This is a very popular mechanism to speed up the rendering of large scenes that have a moderate to highdepth complexity. There are several types of occlusion culling approaches:
Hansong Zhang's dissertation "Effective Occlusion Culling for the Interactive Display of Arbitrary Models"[1] describes an occlusion culling approach.
A popular theme in the visible surface determination literature isdivide and conquer. TheWarnock 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 hierarchies (BVHs) are often used to subdivide the scene's space (examples are theBSP tree, theoctree and thekd-tree). This approach allows visibility determination to be performed hierarchically: if a node in the tree is considered to beinvisible, 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 consideredvisible, 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.
