Hidden surface determination
Encyclopedia
In 3D computer graphics
, hidden surface determination (also known as hidden surface removal (HSR), occlusion culling (OC) or visible surface determination (VSD)) is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden line removal
. Hidden surface determination is necessary to render an image correctly, so that one cannot look through walls in virtual reality.
There are many techniques for hidden surface determination. They are fundamentally an exercise in sorting
, and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by divide and conquer
.
, the clipping
, and the rasterization steps are handled differently by the following algorithms:
The advantage of culling early on the pipeline is that entire objects that are invisible do not have to be fetched, transformed, rasterized or shaded. Here are some types of culling algorithms:
is a geometric representation of the volume visible to the virtual 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 called clipping
, and the pieces that lie outside the frustum are discarded as there is no place to draw them.
es are hollow shells, not solid objects, the back side of some faces, or polygon
s, in the mesh will never face the camera. Typically, there is no reason to draw such faces. This is responsible for the effect often seen in computer and video games in which, if the camera happens to be inside a mesh, rather than seeing the "inside" surfaces of the mesh, it mostly disappears. (Some game engines continue to render any forward-facing or double-sided polygons, resulting in stray shapes appearing without the rest of the penetrated mesh.)
is too small. See Clipping plane
Hansong Zhang's dissertation "Effective Occlusion Culling for the Interactive Display of Arbitrary Models" http://www.cs.unc.edu/~zhangh/hom.html describes an occlusion culling approach.
. 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 early-rejected 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.
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
, hidden surface determination (also known as hidden surface removal (HSR), occlusion culling (OC) or visible surface determination (VSD)) is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden line removal
Hidden line removal
Hidden line removal is an extension of wireframe model rendering where lines covered by surfaces are not drawn.This is not the same as hidden face removal since this involves depth and occlusion while the other involves normals....
. Hidden surface determination is necessary to render an image correctly, so that one cannot look through walls in virtual reality.
There are many techniques for hidden surface determination. They are fundamentally an exercise in sorting
Sorting
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:# ordering: arranging items of the same kind, class, nature, etc...
, and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by divide and conquer
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
.
Hidden surface removal algorithms
Considering the rendering pipeline, the projectionGraphical projection
Graphical projection is a protocol by which an image of a three-dimensional object is projected onto a planar surface without the aid of mathematical calculation, used in technical drawing.- Overview :...
, the clipping
Clipping (computer graphics)
Any procedure which identifies that portion of a picture which is either inside or outside a picture is referred to as a clipping algorithm or clipping.The region against which an object is to be clipped is called clipping window.-Examples:...
, and the rasterization steps are handled differently by the following algorithms:
- Z-bufferingZ-bufferingIn computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
During rasterization the depth/Z value of each pixel (or sample in the case of anti-aliasing, but without loss of generality the term pixel is used) is checked against an existing depth value. If the current pixel is behind the pixel in the Z-buffer, the pixel is rejected, otherwise it is shaded and its depth value replaces the one in the Z-buffer. Z-buffering supports dynamic scenes easily, and is currently implemented efficiently in graphics hardware. This is the current standard. The cost of using Z-buffering is that it uses up to 4 bytes per pixel, and that the rasterization algorithm needs to check each rasterized sample against the z-buffer. The z-buffer can also suffer from artifacts due to precision errors (also known as z-fightingZ-fightingZ-fighting is a phenomenon in 3D rendering that occurs when two or more primitives have similar values in the z-buffer. It is particularly prevalent with coplanar polygons, where two faces occupy essentially the same space, with neither in front...
), although this is far less common now that commodity hardware supports 24-bit and higher precision buffers. - Coverage buffers (C-Buffer) and Surface buffer (S-Buffer): faster than z-buffers and commonly used in games in the Quake I era. Instead of storing the Z value per pixel, they store list of already displayed segments per line of the screen. New polygons are then cut against already displayed segments that would hide them. An S-Buffer can display unsorted polygons, while a C-Buffer require polygons to be displayed from the nearest to the furthest. C-buffer having no overdrawn, they will make the rendering a bit faster. They were commonly used with BSP trees which would give the polygon sorting.
- Sorted Active Edge List: used in Quake 1, this was storing a list of the edges of already displayed polygons. Polygons are displayed from the nearest to the furthest. New polygons are clipped against already displayed polygons' edges, creating new polygons to display then storing the additional edges. It's much harder to implement than S/C/Z buffers, but it will scale much better with the increase in resolution.
- Painter's algorithmPainter's algorithmThe painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics...
sorts polygons by their barycenterCentroidIn geometry, the centroid, geometric center, or barycenter of a plane figure or two-dimensional shape X is the intersection of all straight lines that divide X into two parts of equal moment about the line. Informally, it is the "average" of all points of X...
and draws them back to front. This produces few artifacts when applied to scenes with polygons of similar size forming smooth meshes and backface culling turned on. The cost here is the sorting step and the fact that visual artifacts can occur. - Binary space partitioningBinary space partitioningIn computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
(BSP) divides a scene along planes corresponding to polygon boundaries. The subdivision is constructed in such a way as to provide an unambiguous depth ordering from any point in the scene when the BSP tree is traversed. The disadvantage here is that the BSP tree is created with an expensive pre-process. This means that it is less suitable for scenes consisting of dynamic geometry. The advantage is that the data is pre-sorted and error free, ready for the previously mentioned algorithms. Note that the BSP is not a solution to HSR, only a help. - Ray tracing attempts to model the path of light rays to a viewpoint by tracing rays from the viewpoint into the scene. Although not a hidden surface removal algorithm as such, it implicitly solves the hidden surface removal problem by finding the nearest surface along each view-ray. Effectively this is equivalent to sorting all the geometry on a per pixel basis.
- The Warnock algorithmWarnock algorithmThe Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics.It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are obtained that are trivial to compute...
divides the screen into smaller areas and sorts triangles within these. If there is ambiguity (i.e., polygons overlap in depth extent within these areas), then further subdivision occurs. At the limit, subdivision may occur down to the pixel level.
Culling and VSD
A related area to VSD is culling, which usually happens before VSD in a rendering pipeline. Primitives or batches of primitives can be rejected in their entirety, which usually reduces the load on a well-designed system.The advantage of culling early on the pipeline is that entire objects that are invisible do not have to be fetched, transformed, rasterized or shaded. Here are some types of culling algorithms:
Viewing frustum culling
The viewing frustumViewing frustum
In 3D computer graphics, the viewing frustum or view frustum is the region of space in the modeled world that may appear on the screen; it is the field of view of the notional camera. The exact shape of this region varies depending on what kind of camera lens is being simulated, but typically it is...
is a geometric representation of the volume visible to the virtual 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 called clipping
Clipping (computer graphics)
Any procedure which identifies that portion of a picture which is either inside or outside a picture is referred to as a clipping algorithm or clipping.The region against which an object is to be clipped is called clipping window.-Examples:...
, and the pieces that lie outside the frustum are discarded as there is no place to draw them.
Backface culling
Since meshWire frame model
A wire frame model is a visual presentation of a three dimensional or physical object used in 3D computer graphics. It is created by specifying each edge of the physical object where two mathematically continuous smooth surfaces meet, or by connecting an object's constituent vertices using straight...
es are hollow shells, not solid objects, the back side of some faces, or polygon
Polygon (computer graphics)
Polygons are used in computer graphics to compose images that are three-dimensional in appearance. Usually triangular, polygons arise when an object's surface is modeled, vertices are selected, and the object is rendered in a wire frame model. This is quicker to display than a shaded model; thus...
s, in the mesh will never face the camera. Typically, there is no reason to draw such faces. This is responsible for the effect often seen in computer and video games in which, if the camera happens to be inside a mesh, rather than seeing the "inside" surfaces of the mesh, it mostly disappears. (Some game engines continue to render any forward-facing or double-sided polygons, resulting in stray shapes appearing without the rest of the penetrated mesh.)
Contribution culling
Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen projection3D projection
3D projection is any method of mapping three-dimensional points to a two-dimensional plane. As most current methods for displaying graphical data are based on planar two-dimensional media, the use of this type of projection is widespread, especially in computer graphics, engineering and drafting.-...
is too small. See Clipping plane
Occlusion culling
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 high depth complexity. There are several types of occlusion culling approaches:- Potentially visible setPotentially visible setPotentially Visible Sets are used to accelerate the rendering of 3D environments. This is a form of occlusion culling, whereby a candidate set of potentially visible polygons are pre-computed, then indexed at run-time in order to quickly obtain an estimate of the visible geometry...
or PVS rendering, divides a scene into regions and pre-computes visibility for them. These visibility sets are then indexed at run-time to obtain high quality visibility sets (accounting for complex occluder interactions) quickly. - Portal renderingPortal renderingIn computer-generated imagery and real-time 3D computer graphics, portal rendering is an algorithm for visibility determination. For example, consider a 3D computer game environment, which may contain many polygons, only a few of which may be visible on screen at a given time...
divides a scene into cells/sectors (rooms) and portals (doors), and computes which sectors are visible by clipping them against portals.
Hansong Zhang's dissertation "Effective Occlusion Culling for the Interactive Display of Arbitrary Models" http://www.cs.unc.edu/~zhangh/hom.html describes an occlusion culling approach.
Divide and conquer
A popular theme in the VSD literature is divide and conquerDivide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
. The Warnock algorithm
Warnock algorithm
The Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics.It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are obtained that are trivial to compute...
pioneered dividing the screen. Beam tracing
Beam tracing
Beam tracing is an algorithm to simulate wave propagation.It was developed in the context of computer graphics to render 3D scenes,but it has been also used in other similar areas such as acoustics andelectromagnetism simulations....
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 early-rejected 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
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
and the kd-tree
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
). 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.