Z-Buffer
A screen is flat and a scene is not, so something has to decide which surface a pixel shows when several are behind one another. The old answer was to sort the shapes back to front and paint them in that order, which works until two shapes pass through each other and no single order is right. The depth buffer answers it per pixel instead: alongside each pixel's colour it keeps how far away that colour came from, and a new pixel is only allowed in if it is nearer. Then nothing needs sorting at all, and this page checks that rather than asserting it, by rendering every order and comparing the results byte for byte.
New to drawing in three dimensions? Start here
A screen is flat and a scene is not, so something has to decide which surface a pixel shows when several are behind one another. The old answer was to sort the shapes back to front and paint them in that order, which works until two shapes overlap in a way no single order can resolve.
The depth buffer answers it per PIXEL instead of per shape. Alongside the colour of each pixel it keeps how far away that colour came from, and a new pixel is only allowed in if it is nearer. Nothing needs sorting, which is the property this page is about.
A grid of dots on a clock
A screen is a grid of coloured dots, redrawn from top to bottom on a fixed beat. Everything drawn on it is a decision about which dots and what colour, made before the beat arrives.
The clock is the part that makes this hard. It does not wait, and it does not care whether the drawing was finished, so a picture that took too long is shown half-done. Most of the machines in this topic exist because of that deadline rather than because of the picture.
The machine for this idea on its own is Eight Sprites, if you would rather press it than read about it.
Machines here that come first: Bresenham.
Draw them in any order and every pixel keeps the nearest
1 Triangles with a depth, drawn into a buffer that remembers the nearest so far
Three triangles with a depth at each corner, so a triangle can be nearer at one end and further at the other. Pick a scene: in one they sit at flat depths, in the other they pass through each other.
2 Each pixel tested against what is already there, and kept or thrown away
Every pixel tested against what is already there, and kept only if it is nearer. The counts below are what the buffer did, not an estimate of what it would do.
| order | pixels tested | kept | drawn then covered |
|---|
3 The same triangles submitted in a different order, and the two images compared
The same triangles submitted in every possible order, and the framebuffers compared. Not an impression of sameness: every one of the 1,536 pixels, against the first.
| order | identical | drawn then covered |
|---|
4 What it costs: the pixels that were drawn and then covered over
And what sorting whole shapes does with the same scene. Where the triangles do not interlock it is right everywhere and cheaper; where they do, no ordering exists that works.
| claim | held | measured |
|---|---|---|
| every order of the triangles gives a byte-identical image, in both scenes | yes | stacked: 6 orders, pierced: 6 orders. Compared pixel by pixel, not by looking |
| sorting whole shapes gets 68 pixels wrong on the interlocking scene | yes | 9% of the 755 drawn pixels. No ordering of whole triangles can fix it: each one is nearer at one end and further at the other |
| and gets every pixel right on the scene where the shapes do not interlock | yes | sorting is cheaper when it works, which is why it was the method before depth buffers were affordable |
| the cost is overdraw, and the order changes it even though the image does not | yes | between 53 and 448 pixels were drawn and then covered, depending on the order. The picture is identical; the work is not |
| the depths are exact here, and a real depth buffer's are not | yes | this uses double-precision depths on a 48 by 32 grid. Hardware stores depth in limited precision, usually non-linearly, and that is where z-fighting comes from -- a real effect this page does not reproduce and does not pretend to |
| 1974 is right and the single name usually attached to it is not | yes | Catmull's Utah dissertation is the usual citation; Strasser described the same idea in his TU Berlin thesis the same year and probably earlier. Independent. This page names both |
What is real here, and what is not
The depths here are exact, and a real one's are not
This keeps depth in double precision on a 48 by 32 grid. Hardware stores it in limited precision and usually non-linearly, which is where z-fighting comes from: two surfaces close enough that their stored depths collide, and the pixel flickers between them as the camera moves. That is a real effect, it is the main practical difficulty with depth buffers, and this page does not reproduce it.
1974 twice, and the usual single name is not the whole story
Edwin Catmull's Utah dissertation is the citation everyone gives. Wolfgang Strasser described the same idea in his TU Berlin thesis the same year and, by most accounts, some months earlier. The two were independent. This page names both and calls neither first, because the evidence for the ordering is secondary and the page has not seen the theses.
Sorting is not the worse algorithm
On the scene where the shapes do not interlock, painting back to front gets every pixel right and does less work: no depth buffer to allocate, no test per pixel. It was the method for a reason. What it cannot do is the other scene, and no amount of better sorting fixes that, because the fault is in sorting whole shapes at all.
Overdraw is counted, not modelled
The figure is the number of pixels that were written and then written over, which the buffer knows exactly. It is not a cost in time or in memory bandwidth, which is what overdraw actually costs on hardware and what this page has no way to measure.
Three triangles, and every order really is every order
Three shapes have six orderings and the page renders all six. That is exhaustive here and would not be at any real scale, where the claim has to rest on the argument rather than the enumeration. The argument is that the test compares depths and not arrival times, so nothing about the order can reach it.
Sources
- Edwin Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, University of Utah PhD dissertation, December 1974, as filed with the Defense Technical Information Center (ADA004968) — the usual citation for the depth buffer. DTIC's own copy answers 200 and serves a maintenance page, so this is the archived one that is actually readable.
- The attribution, including Wolfgang Strasser's TU Berlin thesis of the same year — secondary, which is why the ledger above declines to say which came first.
- Logical Art, the studio this belongs to.