The hidden surface removal is the procedure used to find which surfaces are not visible from a certain view. A hidden surface removal algorithm is a solution to the visibility issue, which was one of the first key issues in the field of three dimensional graphics. The procedure of hidden surface identification is called as hiding, and such an algorithm is called a ‘hider’. Hidden surface identification is essential to render a 3D image properly, so that one cannot see through walls in virtual reality.

Hidden surface identification is a method by which surfaces which should not be visible to the user are prohibited from being rendered. In spite of benefits in hardware potential there is still a requirement for difficult rendering algorithms. The accountability of a rendering engine is to permit for bigger world spaces and as the world’s size approaches infinity the rendering engine should not slow down but maintain at constant speed.

There are many methods for hidden surface identification. They are basically a work out in sorting, and generally vary in the order in which the sort is executed and how the problem is subdivided. Sorting more values of graphics primitives is generally done by divide.

1. Z - Buffer Algorithm

In Z-buffering, the depth of ‘Z’value is verified against available depth value. If the present pixel is behind the pixel in the Z-buffer, the pixel is eliminated, or else it is shaded and its depth value changes the one in the Z-buffer. Z-buffering helps dynamic visuals easily, and is presently introduced effectively in graphics hardware.

• Depth buffering is one of the easiest hidden surface algorithms
• It keeps follow of the space to nearest object at every pixel position.
• Initialized to most negative z value.
• When image being drawn, if its z coordinate at a position is higher than z buffer value, it is drawn, and new z coordinate value is stored; or else, it is not drawn
• If a line in three dimensional is being drawn, then the middle z values are interpolated: linear interpolation for polygons, and can calculate z for more difficult surfaces.

Algorithm

loop on y;
loop on x;
zbuf[x,y] = infinity;
loop on objects
{
    loop on y within y range of this object
  {
    loop on x within x range of this scan line of this object
    {
      if z(x,y) < zbuf[x,y] compute z of this object at this pixel & test 
      zbuf[x,y] = z(x,y) update zbuffer
      image[x,y] = shade(x,y) update image (typically RGB)
    }
  }
}

Basic operations

1. Compute y range of an object
2. Compute x range of a given scan line of an object
3. Calculate intersection point of a object with ray through pixel position (x,y)

2. Painter’salgorithm

The painter's algorithm is called as a priority fill, is one of the easiest results to the visibility issue in three dimensional graphics. When projecting a 3D view onto a 2D screen, it is essential at various points to be finalized which polygons are visible, and which polygons are hidden.

The ‘painter's algorithm’shows to the method employed by most of the painters of painting remote parts of a scene before parts which are close thereby hiding some areas of distant parts. The painter's algorithm arranges all the polygons in a view by their depth and then paints them in this order, extreme to closest. It will paint over the existing parts that are usually not visible hence solving the visibility issue at the cost of having painted invisible areas of distant objects. The ordering used by the algorithm is referred a 'depth order', and does not have to respect the distances to the parts of the scene: the important characteristics of this ordering is, somewhat, that if one object has ambiguous part of another then the first object is painted after the object that it is ambiguous. Thus, a suitable ordering can be explained as a topological ordering of a directed acyclic graph showing between objects.

Algorithm

sort objects by depth, splitting if necessary to handle intersections; loop on objects (drawing
from back to front)
{
  loop on y within y range of this object
  {
      loop on x within x range of this scan line of this object
    {
        image[x,y] = shade(x,y);
  }
    }
}

Basic operations

1. Compute ‘y’range of an object

2. Compute ‘x’range of a given scan line of an object

3. Compute intersection point of a given object with ray via pixel point (x,y).

4. Evaluate depth of two objects, determine if a is in front of b, or b is in front of a, if they don’t overlap in xy, or if they intersect

5. Divide one object by another object

Advantage of painter's algorithm is the inner loops are quite easy and limitation is sorting operation.

3. Warnock Algorithm

The Warnock algorithm is a hidden surface algorithm developed by John Warnock that is classically used in the area of graphics. It explains the issues of rendering a difficult image by recursive subdivision of a view until regions are attained that is trivial to evaluate. Similarly, if the view is simple to compute effectively then it is rendered; else it is split into tiny parts which are likewise evaluated for simplicity. This is a algorithm with run-time of O(np), where p is the number of pixels in the viewport and n is the number of polygons.

The inputs for Warnock algorithm are detail of polygons and a viewport. The good case is that if the detail of polygons is very simple then creates the polygons in the viewport. The continuous step is to divide the viewport into four equally sized quadrants and to recursively identify the algorithm for each quadrant, with a polygon list changed such that it contains polygons that are detectable in that quadrant.

1. Initialize the region.

2. Generate list of polygons by sorting them with their z values.

3. Remove polygons which are outside the area.

4. Identify relationship of each polygon.

5. Execute visibility decision analysis:

$\quad$ a) Fill area with background color if all polygons are disjoint,

$\quad$ b) Fill entire area with background color and fill part of polygon contained in area with color of polygon if there is only one contained polygon,

$\quad$ c) If there is a single surrounding polygon but not contained then fill area with color of surrounding polygon.

$\quad$ d) Set pixel to the color of polygon which is closer to view if region of the pixel (x,y) and if neither of (a) to (d) applies calculate z- coordinate at pixel (x,y) of polygons.

1. If none of above is correct then subdivide the area and Go to Step 2.