Today

• Visibility / occlusion
  • Z-buffering
• Shading
  • Illumination & Shading
  • Graphics Pipeline

Painter’s Algorithm

• Inspired by how painters paint
• Paint from back to front, overwrite in the framebuffer
• Requires sorting in depth ($O(n\log n)$ for $n$ triangles)
• Can have unresolvable depth order

Z-Buffer

• This is the algorithm that eventually won
• Idea:
  • Store current min. z-value for each sample (pixel)
  • Needs an additional buffer for depth values
    • frame buffer stores color values
    • depth buffer (z-buffer) stores depth
• Important: For simplicity we suppose $z$ is always positive (smaller $z$ → closer, larger $z$ → farther)

Z-Buffer algorithm

• Initialize depth buffer to $\infty$
• During rasterization:

for (each triangle T)
	for (each sample (x, y, z) in T)
		if (z < zbuffer[x, y])          // closest sample so far
			framebuffer[x, y] = rgb;      // update color
			zbuffer[x, y] = z;            // update depth
		else
			;                  // do nothing, this sample is occluded

Z-Buffer Complexity

• Complexity
  • $O(n)$ for $n$ triangles (assuming constant coverage)
  • How is it possible to sort $n$ triangles in linear time?
• Drawing triangles in different orders?
  • 没影响（假设没有两个图形上同样$(x, y)$的点z也相同）
• Most important visibility algorithm
  • Implemented in hardware for all GPUs