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.

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:

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

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 Qz_min≤Pz_max

    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 P₁ & P₂ along the plane of Q, replace P with P₁ & P₂ in sorted order in the list. Repeat tests with the new list.