Painter’s Algorithm for Hidden Surface Removal

Painter’s Algorithm uses both image space and object space operations. The basic idea of the algorithm is surfacing in the scene is converted or painted in the frame buffer in order of decreasing distance from the viewpoint.

Painter's Algorithm for Hidden Surface Removal

The visibility order or depth priority list of the surface is first set using depth sort. Starting with a polygon of maximum depth more distant polygons are painted first and then the nearer polygons are painted over the distant polygons, partially or obscuring them from view.

Painter’s Algorithm

Painter’s Algorithm:

The logical steps of the algorithm are as follows:

1. Assuming we are viewing along the Z direction polygons are sorted by points on the surface having maximum depth or minimum z coordinate.
Thus zmin for each polygon is the sort key. A preliminary depth priority list is established where the first polygon, say P is the one with the smallest zmin

2. For each other polygon q in the list.
a. Compare Q with P to determine whether there are any overlaps in depth. It means that
if Qzmin≤Pzmax

    i. If there is no overlap then P doesn’t obscure Q and P is compared with the next Q. If there is no depth overlap with any Q in the list then P is unambiguously the rearmost polygon and hence P is scan converted.
    ii. If an overlap is found then check whether P obscures q or not by performing the following tests in the order listed. The order is set according to the increasing difficulty of performing the tests.
1. Do the polygons x-extent overlap?
2. Do the polygons y-extent overlap?

b. If the answer is No to any of the tests in (ii) then the remaining tests become redundant, so skipped. P is scan converted as being unambiguously the rearmost polygon.

c. If the is yes to all the tests then it implies P can obscure Q and hence P can’t be scan converted ahead of Q.

d. Swap P and Q in the list flagging Q as swapped. Repeat the tests of (ii).

e. If an attempt is made to swap Q again, a cyclical overlap exists. Split P in two parts P1 & P2 along the plane of Q, replace P with P1 & P2 in sorted order in the list. Repeat tests with the new list.