[Intermediate] — Deciding which surfaces the viewer can actually see: object-space versus image-space methods, the depth buffer worked by hand (including the plane-equation increment), back-face detection, the painter’s algorithm, BSP trees, the scan-line method, Warnock’s area subdivision, and ray casting.
Part 1 of the course. Note 10 covers the z-buffer as modern GPUs run it (early-Z, depth pre-pass, transparency); note 09 covers depth precision. This note is the full classical family of methods.
Before you start
You can take a dot product, and you know a plane can be written with normal .
After this note you will be able to:
- Classify a visibility method as object-space or image-space.
- Run the depth-buffer algorithm by hand in either depth convention, and update incrementally.
- Apply the back-face test, and say what it does not solve.
- Compare painter’s, BSP, scan-line, Warnock and ray casting.
The kid version
Hold up a book in front of a poster. You can’t see the part of the poster behind the book. A computer drawing the scene has to work that out itself. One way: for every dot on the screen, remember how close the nearest thing drawn there so far is, and only paint over it if something new is even closer. Another: paint the far things first and the near things last, like a painter doing the sky before the trees.
Where the analogy stops working. The painter’s trick breaks when three objects overlap each other in a circle (A over B, B over C, C over A) — there is no “back” to start from. The remember-the-closest trick doesn’t care.
Terms used in visible surface detection
- Visible surface detection: This is also known as hidden surface removal. This is working out which surfaces are visible from the viewer’s position and removing the rest, so the picture is correct.
- Object-space method: This is a method that compares objects or faces with each other in the 3D scene, independent of pixels.
- Image-space method: This is a method that decides visibility pixel by pixel on the screen.
- Depth buffer: This is also known as the z-buffer. This is an array the size of the frame buffer storing, for each pixel, the depth of the nearest surface found so far.
- Back face: This is a polygon whose outward normal points away from the viewer.
- Z-fighting: This is flicker where two surfaces are at almost the same depth and limited depth precision makes the test flip between them.
1. Two families
- Object-space methods compare objects or faces with each other: back-face detection, painter’s algorithm, BSP trees.
- Image-space methods decide visibility per pixel: depth buffer, scan-line method, area subdivision, ray casting.
2. The depth-buffer (z-buffer) method
Test the depth of every surface at every pixel, and keep the closest. Two buffers of the same size:
- The depth buffer stores a depth for each as surfaces are processed.
- The frame buffer stores the colour for each pixel (note 01).
for every pixel (x, y):
depthBuffer(x, y) = farthest value # 0 in the "larger z = nearer" convention
frameBuffer(x, y) = background colour
for each polygon (one at a time):
for each pixel (x, y) the polygon covers:
z = depth of the polygon at (x, y)
if z is nearer than depthBuffer(x, y): # z > depthBuffer(x, y) in that convention
depthBuffer(x, y) = z
frameBuffer(x, y) = surface colour at (x, y)
State your depth convention. The SSG 511 notes use depth 0 as farthest and larger as nearer, so the test is
z > depthBuffer. OpenGL and most systems do the opposite: clear to the maximum and keep the smaller . Both are correct as long as you are consistent.
Surfaces are processed one polygon at a time, and each polygon pixel by pixel — not “one pixel at a time” overall.
Getting cheaply
A polygon lies on a plane, so its depth at any pixel comes from the plane equation:
Moving one pixel right changes by ; moving one scan line down () changes it by . So is updated with one addition per pixel instead of being recomputed — the same incremental trick as Bresenham.
Worked — two polygons at one pixel
At pixel , a red polygon has and a blue one (larger = nearer, buffer cleared to 0).
- Red first: → store red, depth 0.3.
- Blue next: → replace with blue, depth 0.7.
Reverse the order: blue stores 0.7; red’s fails. Same result — the order of polygons does not matter.
Advantages and disadvantages
Advantages:
- Easy to implement, and built into graphics hardware.
- Surfaces can be processed in any order, with no sorting.
- Handles surfaces that cut through each other.
Disadvantages:
- Memory: a depth buffer as large as the frame buffer. At 1920 × 1080 with 4 bytes per depth, MB.
- Depth is computed at every covered pixel, and work is wasted on pixels that end up hidden (modern GPUs reduce this with early-Z → note 10).
- Limited precision causes z-fighting where two surfaces are almost at the same depth (the fix is in note 09). Transparency needs extra work.
3. Back-face detection
An object-space test. Each polygon has an outward normal . Let be the viewing direction (from the eye into the scene). The polygon is a back face — facing away from the viewer — if , so discard it.
For a viewer looking down the axis, and , so a back face has (edge-on when ).
For a closed solid, this removes about half the faces cheaply. It does not solve everything: front faces can still hide each other when there are several objects or the shape is concave. It is a pre-pass, not a full visibility method.
4. The other methods
| Method | Type | Idea | Weakness |
|---|---|---|---|
| Painter’s algorithm (depth sort) | Object space | Sort polygons far to near; paint back to front so nearer ones overwrite farther ones | Sorting cost; polygons that overlap in a cycle have no valid order and must be split |
| BSP trees | Object space | Split space with planes into a binary tree; then for any eye position, traverse the tree to draw back to front | Building the tree is slow, so best for static scenes (it powered Doom-era engines) |
| Scan-line method | Image space | On each scan line, find which surfaces overlap each span and show the nearest in each span | Bookkeeping of active edges and surfaces |
| Area subdivision (Warnock) | Image space | Split the window into quarters recursively until one surface is clearly visible in each area, or the area is a single pixel | Many subdivisions on complex scenes |
| Ray casting | Image space | Shoot a ray through every pixel and take the nearest surface it hits | Cost grows with pixels × objects without an acceleration structure → note 14 |
How a BSP tree gives back-to-front order
Each node holds a splitting plane (usually a polygon’s own plane). Polygons in front go in the front subtree, behind go in the back subtree, and polygons crossing the plane are split. To draw: at each node, if the eye is in front of the plane, draw the back subtree, then the node’s polygon, then the front subtree (reverse if the eye is behind). The result is a correct painter’s order for any viewpoint, with no per-frame sort.
Warnock’s four cases
For each area, every polygon is one of: surrounding (covers the whole area), intersecting, contained, or disjoint. The area is simple enough to draw directly if all polygons are disjoint (background), there is one intersecting or contained polygon, or there is a surrounding polygon in front of all others. Otherwise split into four and recurse.
Common pitfalls
- Not stating the depth convention — “nearer” is in one and in the other.
- Thinking back-face culling is enough — it isn’t, for multiple or concave objects.
- Getting the back-face sign backwards. With pointing into the scene, back faces have . (Some books use from the surface to the eye, which flips the sign — check which.)
- Calling the painter’s algorithm image-space. It sorts objects; it is object-space.
Check your understanding
- Why can the z-buffer handle two polygons that pass through each other, when the painter’s algorithm cannot without splitting?
- A plane has , , . Moving one pixel to the right, how does change?
- A single cube is viewed from a general direction. How many faces does back-face detection remove, and is anything else needed to draw it correctly?
Answers (after your attempt)
- It decides per pixel, so each pixel independently keeps whichever surface is nearer there; the painter’s algorithm needs one order for whole polygons.
- By .
- Three of the six. And nothing else is needed: a single convex object’s front faces never hide each other, so for that one case back-face detection is a complete visibility method. Add a second object, or a concave shape, and it no longer is.
Practice — independent task
Write a tiny software z-buffer in Python: a 20 × 20 grid, two overlapping triangles at constant (different) depths, and the “larger = nearer” convention. Print the frame buffer as characters. Done when swapping the order you draw the triangles gives an identical picture, and switching to “smaller = nearer” (clear to , test <) also gives the same picture once you negate the depths.
Before moving on
That ends the teaching notes of Part 1. Next: the SSG 511 question bank to test it, then Part 2 from note 08 for the modern view.
Related
- Rasterisation — the z-buffer on a GPU
- Ray Tracing — ray casting grown up
- Computer graphics map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering