Painter's Algorithm: Depth Sorting, Back-to-Front Rendering and Failure Cases

An arbitrary 3-D polygon order can let a distant surface overwrite a nearer one, even when the projection is correct. Painter's Algorithm uses a canvas idea: draw the farthest opaque surface first, then let nearer surfaces cover it. Three opaque rectangles establish the correct paint trace; crossing and cyclic overlaps show where whole-polygon sorting fails and geometry must be split.

Our convention is an orthographic view along positive z: smaller positive z is nearer, larger z is farther, and the main example is opaque; the UGC NET preparation catalogue places this Computer Graphics idea within broader preparation.

Painter's Algorithm turns visibility into a back-to-front ordering problem

The input is projected polygons plus enough 3-D depth information to compare them. Write A -> B when A is behind B in their overlap and must be painted first. A valid sequence respects every such relation.

Projection places a polygon on screen, depth ordering decides which surface is behind, and rasterisation fills pixels in that order. Painter's Algorithm does not calculate perspective projection.

For constant-depth polygons, sort in descending z because smaller z is nearer. Depths 11, 7, 4, 2 produce 11 -> 7 -> 4 -> 2. UGC NET Computer Science Syllabus Areas: Paper 2 is a wider subject-planning map.

The basic algorithm: calculate keys, sort, test and paint

for each polygon P:
    calculate [z_min(P), z_max(P)] and its projected bounds
form an initial far-to-near order from a depth key
for relevant polygon pairs:
    skip the pair if projected regions do not overlap
    prove which polygon is behind across the overlap
    order or swap the pair when one relation is valid
    split geometry when neither whole-polygon order is valid
rasterise the resolved pieces from far to near

For A at [10,12] and B at [4,7], z_min(A)=10 > z_max(B)=7. Every point of A is farther, so A can be painted first. If intervals overlap but projected x-y bounds are disjoint, either order produces the same pixels.

Average or centroid depth is only a candidate key. A tilted polygon can be nearer in one part of the overlap and farther in another, so it needs plane-side reasoning.

Worked example: sort and paint three opaque rectangles

Project these rectangles by dropping z:

• Blue A: (0,0,12), (6,0,12), (6,5,12), (0,5,12)

• Green B: (1,1,7), (5,1,7), (5,4,7), (1,4,7)

• Red C: (3,0,3), (7,0,3), (7,3,3), (3,3,3)

The keys are 12, 7, and 3, so descending depth gives A -> B -> C.

At P3, A makes the pixel blue, B overwrites it with green, and C overwrites it with red. Every write moves from larger z to smaller z, hence nearer. With C -> B -> A, distant blue A would be written last and incorrectly hide both nearer surfaces.

How to decide whether two polygons have a whole-object order

Use this ladder:

1. Compare their depth intervals.

2. Reject pairs whose projected bounding boxes do not overlap.

3. For overlapping projections, test each polygon against the other's plane or calculate depth over the overlap.

4. If one surface is consistently farther, add its behind-before edge.

5. If the relation changes, split the geometry instead of guessing.

Bounding-box overlap means more testing is required, not that polygons intersect.

Let D cover 0 <= x <= 4, 0 <= y <= 2 with z_D=9+0.5x. Its range is 9+0.5(0)=9 to 9+0.5(4)=11. E covers the same projection at z_E=6. D is always greater than 6, so it is wholly farther and the order is D -> E.

Plane equations, signed-side tests, and interpolation provide the machinery. Ask whether the sign of z_D-z_E stays the same throughout the overlap.

Crossing and cyclic overlaps: when sorting alone cannot work

F and G share 0 <= x <= 6, 1 <= y <= 4. F has corners (0,1,2), (6,1,8), (6,4,8), (0,4,2), so z_F=2+x. G has constant z_G=5. Their average depths are both 5, yet the order reverses at x=3.

At (1,2), z_F=2+1=3 < 5, so F is nearer and the order is G -> F. At (5,2), z_F=2+5=7 > 5, so F is farther and the order is F -> G. No whole-polygon order works. Split at x=3, where z_F=2+3=5=z_G: paint G then F on the left, and F then G on the right. The equality line is the geometric intersection, not an arbitrary tie.

A cycle is another failure. The A-B overlap has z_A=8, z_B=5, hence A -> B; B-C has z_B=9, z_C=6, hence B -> C; C-A has z_C=7, z_A=4, hence C -> A. The cycle A -> B -> C -> A has no topological order. Swapping cannot fix it, so at least one polygon must be split.

Opaque overdraw, transparency and the comparison with a Z-buffer

Opaque rendering works because each nearer fragment overwrites a farther fragment. Comparison sorting costs O(n log n) for n polygons, plus raster work for every painted fragment. Overdraw shades pixels repeatedly, and splitting increases polygon count. The method stores geometry and order rather than a per-pixel depth array.

Transparency also exposes order. Over white C0=(1,1,1), paint far blue B=(0,0,1) at alpha=0.5:

C1=0.5B+0.5C0=(0.5,0.5,1).

Now paint near red R=(1,0,0) at alpha=0.5:

C2=0.5R+0.5C1=(0.75,0.25,0.5).

Reversing them gives red over white, (1,0.5,0.5), then blue over it, (0.5,0.25,0.75). The results differ, so source-over composition is not commutative.

A Z-buffer compares depth per fragment and handles many opaque crossings without globally sorting polygons. Its depth storage is O(W x H) for a W by H buffer. A plain nearest-fragment Z-buffer does not preserve every transparent layer's blending order. Painter's Algorithm suits ordered layers, but sorting and splitting are its weakness.

Traps and exam-style questions: use one solving routine

Nearest-to-farthest painting lets distant surfaces overwrite near ones, so write “far first.” Mixed camera conventions reverse comparisons, so declare which depth is nearer. Centroid sorting misses crossings, so test overlaps. Disjoint projections need no edge. A cycle needs a split, not endless swaps.

Use four steps on an objective or numerical problem:

1. Write the view and depth convention.

2. Create behind-before directed edges.

3. Topologically order the graph if it is acyclic.

4. Simulate requested pixels, or state where splitting is required.

Practise three checks: sort 4, 11, 7, 2 into 11, 7, 4, 2, recover the five sample colours, and explain why equal average depth does not order F and G. Use UGC NET Computer Science High-Yield Topics for adjacent planning and NTA-UGC-NET Paper - 2 for structured coverage containing the relevant Computer Graphics area.

Painter's Algorithm in one minute: order what you can, split what you cannot

Define the depth convention, derive behind-before relations only in overlaps, paint far to near for an acyclic graph, and split polygons when order reverses or cycles. A(z=12) -> B(z=7) -> C(z=3) is clean; F and G need the x=3 split.

Now redraw the three rectangles, process C -> B -> A, and explain why P3 incorrectly finishes blue. Then rebuild the correct order from the depths without looking. For broader structured Computer Science coverage whose live course page includes Computer Graphics, continue with ZERO TO HERO.