Featured

# Depth Sorting Algorithm

Depth Sorting Algorithm :

This algorithm is also called Painters algorithms.  This  algorithm is a combination of both image space algorithm and object space approach.

In this algorithm we perform following two basic functions :

(a). Surface are sorted in order of decreasing depth.  Sorting can be done either in image space or in object space.  By sorting, we assign priorities to various surfaces which determines the order of scan conversion of polygon.  Due to this reason it is called priority algorithm.

(b). Scan convert the surface order, starting with surface of greatest depth. This function is always performed in image space.

In this algorithm we use the concept of extent of polygons.  The x-extent of polygon is difference between maximum value of x-coordinate and minimum value of x-coordinate of polygon.  Similarly we can define y and z extent.

For example :  Consider the polygon shown in

Minimum value of x-coordinate among A,B,C,D vertices in 2 (of A).

Maximum value of X-coordinate among vertices A,B,C & D is 10 (off B).

Hence x-extent = 10 - 2 = 8.
similarly, y-extent = 5 - 1 = 4.
and  z-extent = 8 - 1 = 7.
In painters algorithm, we perform following test to check whether one polygon overlaps other polygon or not.  If any of following test is true then one polygon do not overlap other polygon.

Test :

1. z-extent of polygon P and Q do not overlap.
2. x-extent of P and Q do not overlap.
3. y-extent of P and Q do not overlap.
4. All vertices of P lie on same side of plane containing.
5. Projection of polygon P and Q on view plane do not overlap.
If polygon do not overlap other polygon, then we set the intensity of farthest polygon in frame buffer.  If two polygons overlap than we swap the polygons and perform the tests again.