Hidden Surface Removal Article Index for
Hidden 		Shopping
Determination 		Website Links For
Hidden 		 

Information About

Hidden Surface Removal
  CATEGORIES ABOUT HIDDEN SURFACE DETERMINATION
   
3d computer graphics
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



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 .


HIDDEN SURFACE REMOVAL ALGORITHMS

Considering the Rendering Pipeline , the Projection , the Clipping , and the Rasterization step are handled differently by the following algorithms:
  • --- Z-buffering During rasterization the depth/Z value of each pixel (or ''sample'' in the case of anti-aliasing, but without loss of generality we use the term ''pixel'') 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 it's 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 2 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-fighting ''), although this is far less common now that commodity hardware supports 24bit and higher precision buffers.

  • --- Painter's Algorithm sorts polygons by their Barycenter 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 of course the fact that visual artifacts can occur.

  • --- Binary Space Partitioning 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.

  • --- 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 Algorithm 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 & 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).

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 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

Since Mesh 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 disappears completely (all faces are seen from behind, and are culled).


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 Projection is too small.


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 Set 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 Rendering divides a scene into cells/sectors (rooms) and portals (doors), and computes which sectors are visible by clipping them against portals.



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 similar algorithm used for ray-tracing. 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.

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.