Hidden surface determination
From Wikipedia, the free encyclopedia
In 3D computer graphics, hidden surface determination (also known as Hidden Surface Removal (HSR), 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, as parts of the image that are not visible should not be drawn.
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.
Contents |
[edit] Culling & 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. (e.g. Sony's PS2 was unusual in that Backface Culling was a slowdown in most circumstances) VSD is usually closely tied to rasterization - for example in the Scanline and Z-Buffer algorithms. Raytracing and portal rendering do not use any of these as they lead to artifacts with mirrors.
[edit] Types of Culling
- Viewing frustum culling (necessary)
- The viewing frustum 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.
- Backface culling (common)
- Since meshes are hollow shells, not solid objects, the back side of some faces, or polygons, 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 disappears completely (all faces are seen from behind, and are culled).
- Contribution culling (exotic)
- Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen projection is too small. This is typically used for detail objects superimposed on some broader landscape.
- Occlusion culling (exotic)
- Occlusion culling is the process of determining which objects are hidden by other objects from a given viewpoint. It can also be used to trivially reject entire primitives. Various HSR algorithms can be used at a more approximate object level to achieve occlusion culling, reducing the number of primitives submitted to exact pixel-level HSR. Examples of this are comparing bounding volumes against hierarchical Z, or traversing Portals connecting rooms containing objects.
Though hidden surface determination is most often used to determine what is visible in the final image, it also has other applications, such as determining which parts of objects are in shadow - e.g. raytraced shadows, or shadowbuffers using common realtime z-buffer hardware.
[edit] Hidden Surface Removal algorithms
The following are the main methods of performing exact hidden surface removal. Each results in the set of visible pixels in an image. Each will have various strengths and weaknesses. These include: handling of dynamic vs static scenes; preprocessing time & additional datastructure associated with primitives; primitive count versus image resolution; and complexity affecting their efficiency and potential for parallelism in various software or hardware solutions.
- Ray tracer : Ray tracing, which can also operate on parametric geometry, attempts to model the path of light rays into a viewpoint by tracing rays from the viewpoint into the scene. The first object the ray intersects is rendered, as it naturally is the object visible to the camera. Additional data structures used to solve this sorting problem include BSP trees and octrees.
- painter's algorithm sorts primitives and uses overdraw to hide invisible pixels. This can only produce exact results if scenes are preprocessed or primitives are clipped.
- z-buffering determines visibility by rasterizing primitives and maintaining the closest depth value for each pixel. Ubiquitous in interactive applications.
- Scanline rendering a method based on sorting primitives in screenspace, first by Y, then by X along each scanline in turn.
- 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.
- Portal rendering only works efficiently for indoor scenes. By dividing a scene into cells so granular that every polygonal face only touches one polyhedral 'room', portal traversal (similar to beam-tracing) can perform HSR.
HSR algorithms can also be divided into those that operate in 'image precision', restricted to a rasterized resolution of pixels (e.g. scanline, z-buffer, painter's); and 'Object Precision' which work exactly, capable of producing an exact geometrical description of the visible primitives independent of some arbitrary regular pixel grid. Sometimes object precision algorithms are used to produce high-quality anti-aliased images.
[edit] Hybrid approaches
Sometimes inexact versions of these are used as culling stages in a pipeline, e.g. portals may be used at the object level as an early software-reject for rendering scenes on zbuffer hardware. ZBuffer hardware may typically include a coarse 'hi-Z' against which object's bounding volumes or primitives can be early-rejected without exact rasterization.
The software renderer of Quake used a Scanline renderer for backgrounds, with the added step of emitting a z-buffer. Then moving objects were added into the image using conventional z-buffering.
