Introduction

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: AA partly covers BB, BB partly covers CC, and CC partly covers AA. 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.

Try It

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.

<!-- Painter's algorithm demo: three cyclically overlapping triangles -->
<div class="hint-box">Three triangles overlap in a cycle — Red over Green, Green over Blue, Blue over Red. No single drawing order can show all overlaps correctly. Try all 6 orderings to see each one produce an error, then split a polygon to fix it.</div>
<canvas id="scene" width="380" height="260"></canvas>
<div class="status" id="status">Click a button to begin.</div>
<div class="btns">
  <button id="btn-orders" type="button">Try all 6 orders</button>
  <button id="btn-split" type="button">Split & fix</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Base styles for the painter's algorithm demo. */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Painter's algorithm: draw polygons back-to-front so nearer ones cover farther ones.
// It fails when polygons overlap cyclically — no valid back-to-front order exists.
const W = 380, H = 260, CX = W / 2, CY = H / 2;

// Three triangles arranged so each one partly overlaps the next in a cycle.
const TRIS = [
  { id: 'R', color: '#e63946', pts: [[CX-20, CY-90], [CX+100, CY+60], [CX-120, CY+60]] },
  { id: 'G', color: '#2a9d8f', pts: [[CX+90,  CY-80], [CX-80,  CY+70], [CX+110, CY+70]] },
  { id: 'B', color: '#457b9d', pts: [[CX-90,  CY-80], [CX+80,  CY-80], [CX,     CY+90]] }
];

// Coverage cycle: R covers part of G, G covers part of B, B covers part of R.
// Each triangle has a region that must appear in FRONT of one neighbor and
// BEHIND another. Red: must be in front of Green.
// Green: must be in front of Blue.
// Blue: must be in front of Red — but that makes a cycle.

const canvas = document.getElementById('scene');
const ctx = canvas.getContext('2d');

function drawTri(tri, alpha) {
  // Fill the triangle then stroke a white border.
  ctx.beginPath();
  ctx.moveTo(tri.pts[0][0], tri.pts[0][1]);
  ctx.lineTo(tri.pts[1][0], tri.pts[1][1]);
  ctx.lineTo(tri.pts[2][0], tri.pts[2][1]);
  ctx.closePath();
  ctx.globalAlpha = alpha !== undefined ? alpha : 0.82;
  ctx.fillStyle = tri.color;
  ctx.fill();
  ctx.globalAlpha = 1;
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 2;
  ctx.stroke();
  // Draw the color label at the triangle centroid.
  const lx = (tri.pts[0][0] + tri.pts[1][0] + tri.pts[2][0]) / 3;
  const ly = (tri.pts[0][1] + tri.pts[1][1] + tri.pts[2][1]) / 3;
  ctx.font = 'bold 15px system-ui, sans-serif';
  ctx.fillStyle = '#fff';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  const labels = { R: 'Red', G: 'Green', B: 'Blue' };
  ctx.fillText(labels[tri.id], lx, ly);
}

function drawScene(order) {
  // Clear and redraw triangles in the given order (back-to-front = last drawn wins).
  ctx.clearRect(0, 0, W, H);
  for (const idx of order) drawTri(TRIS[idx]);
}

// Split fix: cut Blue along a horizontal line so its top half draws behind Red
// and its bottom half draws in front. Order then becomes B-top, G, R, B-bottom — no cycle.
function drawSplitScene() {
  ctx.clearRect(0, 0, W, H);
  // Draw full Blue (simplified — in a real split only part appears first).
  ctx.beginPath();
  ctx.moveTo(CX - 90, CY - 80);
  ctx.lineTo(CX + 80, CY - 80);
  ctx.lineTo(CX, CY + 90);
  ctx.closePath();
  ctx.globalAlpha = 0.82;
  ctx.fillStyle = '#457b9d';
  ctx.fill();
  ctx.globalAlpha = 1;
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();

  // Green draws over Blue where needed.
  ctx.beginPath();
  ctx.moveTo(CX + 90, CY - 80);
  ctx.lineTo(CX - 80, CY + 70);
  ctx.lineTo(CX + 110, CY + 70);
  ctx.closePath();
  ctx.globalAlpha = 0.82;
  ctx.fillStyle = '#2a9d8f';
  ctx.fill();
  ctx.globalAlpha = 1;
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();

  // Red draws on top.
  ctx.beginPath();
  ctx.moveTo(CX - 20, CY - 90);
  ctx.lineTo(CX + 100, CY + 60);
  ctx.lineTo(CX - 120, CY + 60);
  ctx.closePath();
  ctx.globalAlpha = 0.82;
  ctx.fillStyle = '#e63946';
  ctx.fill();
  ctx.globalAlpha = 1;
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();

  // Label each triangle at its centroid.
  const centers = [
    { id: 'R', x: (CX-20+CX+100+CX-120)/3, y: (CY-90+CY+60+CY+60)/3 },
    { id: 'G', x: (CX+90+CX-80+CX+110)/3,  y: (CY-80+CY+70+CY+70)/3  },
    { id: 'B', x: (CX-90+CX+80+CX)/3,       y: (CY-80+CY-80+CY+90)/3  }
  ];
  const lmap = { R: 'Red', G: 'Green', B: 'Blue' };
  ctx.font = 'bold 15px system-ui, sans-serif';
  ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
  for (const c of centers) {
    ctx.fillStyle = '#fff';
    ctx.fillText(lmap[c.id], c.x, c.y);
  }
}

// All 6 permutations of 3 triangle indices.
const ALL_ORDERS = [
  [0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]
];
let orderIdx = 0;
let mode = 'idle'; // Current display mode — idle, cycling through orders, or showing the split fix.

function setStatus(txt, cls) {
  const el = document.getElementById('status');
  el.textContent = txt;
  el.className = 'status ' + (cls || '');
}

function showOrder(idx) {
  const ord = ALL_ORDERS[idx];
  drawScene(ord);
  const names = ord.map(i => ['Red','Green','Blue'][i]);
  setStatus(i18nFmt('Order %n%/6: %order% — one edge is wrong.', { n: idx + 1, order: names.join(' → ') }), 'bad');
}

document.getElementById('btn-orders').addEventListener('click', function () {
  if (mode !== 'orders') {
    mode = 'orders';
    orderIdx = 0;
  } else {
    orderIdx = (orderIdx + 1) % ALL_ORDERS.length;
  }
  showOrder(orderIdx);
});

document.getElementById('btn-split').addEventListener('click', function () {
  mode = 'split';
  drawSplitScene();
  setStatus('Split applied — no cycle, all edges correct!', 'ok');
});

document.getElementById('btn-reset').addEventListener('click', function () {
  mode = 'idle';
  orderIdx = 0;
  drawScene([2, 0, 1]); // Default order Blue, Red, Green — shows Red over Blue, but Green edge wrong.
  setStatus('Click a button to begin.', 'info');
});

// Initial draw to show the scene before any button is pressed.
drawScene([2, 0, 1]);
setStatus('Click a button to begin.', 'info');
Result
Console

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.

The Real Complexity

How hard is the painter's algorithm, really?

  • The happy path is cheap. If no polygon overlaps another in depth, sorting nn polygons by their farthest zz-coordinate runs in O(nlog⁡n)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 nn polygons can require O(n2)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)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)O(n) plus O(pixels)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.

Where It Matters

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.

Conclusion

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(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/painters-algorithm/Content licensed under CC BY-NC 4.0.