The Painter's Algorithm

Before modern graphics hardware, drawing a 3D scene on a flat screen was a genuine puzzle: how do you make a nearer object hide the one behind it?

The answer invented in 1972 by Newell, Newell and Sancha borrows from the art studio: a painter laying down oil paint works back to front. The background goes on first; foreground strokes cover whatever lies beneath. The final layer wins by simply sitting on top.

Translated to polygons, the rule is: sort all surfaces by depth, then draw the farthest first. Each polygon painted afterwards automatically covers whatever is farther away, so no special bookkeeping is needed. For decades this was fast, elegant, and — in most scenes — entirely correct.

The crack appears when three polygons overlap in a cycle: $A$ partly covers $B$, $B$ partly covers $C$, and $C$ partly covers $A$. No single ordering of three elements can satisfy all three covering relationships at once. The painter's algorithm has no answer for this; it needs help.

The three triangles below overlap in a cycle: the red one partly covers the green one, the green partly covers the blue one, and the blue partly covers the red one. No back-to-front ordering can make all three look correct simultaneously.

<!-- {{c_intro}} -->
<div class="hint-box">{{hint_para}}</div>
<canvas id="scene" width="380" height="260"></canvas>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="btn-orders" type="button">{{btn_orders}}</button>
  <button id="btn-split" type="button">{{btn_split}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_style}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint-box { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
canvas { display: block; border-radius: 10px; border: 1px solid #cdd9e3;
         background: #f4f7fa; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .45rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557;
         color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Try all 6 orders to see every possible drawing order for the three polygons, and watch how each one produces a visible error on one edge. Press Split & fix to see the classic remedy: cut one polygon along the overlap boundary so the cycle breaks, creating an ordering that works.

How hard is the painter's algorithm, really?

• The happy path is cheap. If no polygon overlaps another in depth, sorting $n$ polygons by their farthest $z$-coordinate runs in $O(n \log n)$ time. Drawing them back to front after that is a single linear pass.
• Cyclic overlaps require splitting. When three or more polygons form a coverage cycle, there is no valid draw order. The standard fix is to cut one polygon along the plane of another, breaking the cycle. Each split adds a new polygon fragment, and in the worst case a scene of $n$ polygons can require $O(n^2)$ fragments.
• BSP trees automate the splitting. A Binary Space Partition (BSP) tree pre-splits every polygon so the depth ordering becomes a simple in-order tree traversal — correct for any viewpoint. Building the tree is expensive upfront, but rendering is $O(n)$ per frame after that.
• The z-buffer sidesteps the problem entirely. Modern GPUs keep a depth value for every pixel. Drawing polygons in any order, each pixel is written only if its polygon is the closest so far. No sorting, no splitting — just $O(n)$ plus $O(\text{pixels})$ — at the cost of a full-resolution depth buffer in memory.

The painter's algorithm is the ancestor of both approaches. Its failure case — the cyclic overlap — is what forced the field to invent better tools.

The painter's algorithm is not just history — its ideas permeate modern rendering:

• Transparent surfaces: hardware z-buffers handle opaque geometry perfectly, but semi-transparent surfaces must still be drawn back to front so blending works correctly. Every game engine does a painter-style pass for glass, water, and particles.
• BSP trees in early 3D games: Doom (1993) and Quake pre-split geometry into a BSP tree at level-load time. At runtime, traversing the tree in back-to-front order gave a pixel-perfect painter's ordering — no z-buffer hardware required.
• CSS and SVG stacking: the browser's rendering pipeline is essentially the painter's algorithm. Elements are sorted by stacking context and drawn back to front; z-index is the user-facing control on that ordering.
• Vector graphics: SVG and PDF render layers in document order, exactly like a painter. Overlapping paths later in the file cover earlier ones.

Understanding why the painter's algorithm fails on cyclic overlaps is also understanding why the halting problem and other undecidability results matter: sometimes there is genuinely no correct ordering, and you must change the representation rather than search harder for an answer.

The painter's algorithm encodes a beautiful intuition: far things go down first, near things on top. For most scenes it works flawlessly and runs in $O(n \log n)$ time.

Three cyclically overlapping polygons shatter that intuition. No permutation of three elements can satisfy a circular covering relation, and no amount of cleverer sorting changes that fact. The only exits are splitting polygons (BSP trees), abandoning order entirely (z-buffers), or restructuring the scene so the cycle cannot arise.

That gap — between "sort and draw" and "there is no valid order" — is a small but perfect example of the difference between problems that admit a greedy solution and those that require a fundamentally different representation. The next time a transparent surface glitches in a video game, you are likely watching a painter's ordering fail, just as Newell, Newell and Sancha predicted in 1972.