10 - Hidden Surface Removal

Why hidden surface removal?

Each part goes through the pipeline independently, so without HSR whatever is drawn last wins. Show only front surfaces and skip work on hidden ones.

Back-face culling

On a closed object, drop faces pointing away from the viewer early in the pipeline.

How much does back-face culling save?

Roughly half the polygons, up to about half the rendering time.

Back-face test with v = look direction (look-at - eye)

Back face if n . v > 0.

Back-face test with v = polygon to eye

Back face if n . v < 0.

Back-face culling exam trap

The sign depends on which way v points. Always say how v is defined.

Is back-face culling full HSR?

No. Only fully works for a single convex object; with several or concave objects, front faces can still overlap.

Painter's algorithm

Sort triangles back to front and draw from the back, so nearer ones paint over farther ones.

Painter's algorithm problems

Cyclic overlaps (can't sort without splitting), O(n log n) sorting, wasted drawing of covered things.

Z-buffer setup

Same resolution as the screen; initialize every entry to the farthest value (far plane).

Z-buffer per-pixel rule

If the new z' is closer than the stored value, write the colour and update the buffer; otherwise ignore it.

How does the z-buffer get depth inside a polygon?

Interpolates z' from the projected vertices during rasterization.

Z-buffer vs painter's

Z-buffer handles cyclic overlaps, needs no sorting. Costs buffer memory and overdraw. Simple and in hardware.

Z-buffer bins

Stores integers (e.g. 32 bits = 2^32 values), so depth is cut into B bins; two z in the same bin look identical.

Orthographic z bin size

Delta z = (f - n) / B, linear.

Z-fighting

Two surfaces closer than one depth bin (especially co-planar) get the same depth; the buffer can't tell which is in front, so pixels flicker between both.

Why perspective makes z-fighting worse

z' = n + f - fn/z is non-linear: precision bunched near the near plane, bins grow with distance.

Perspective bin size at distance z

Delta z_world ~ (z^2 / fn) Delta z'. At z = f it's about (f/n) Delta z'.

Should you set n = 0?

Never. Bins blow up.

Avoiding z-fighting

Bracket the scene tightly (n as large as possible, f no bigger than needed, small f/n), avoid co-planar overlapping polygons, use more depth bits or a float depth buffer.

Z-fighting (review Q)

Finite depth precision: surfaces closer than one bin get the same stored depth and flicker. Worse with perspective. Fix with tight n/f (large n, never 0), no co-planar overlaps, more depth bits.

BSP tree idea

Each polygon's plane f(p) = 0 splits space into + and - sides. Eye on + side: draw - side, then the polygon, then + side.

BSP tree structure

Binary tree; each node holds a polygon and its plane. Plus subtree = polygons on its + side, minus subtree = - side.

BSP big win

Independent of eye position: build once, draw correctly from anywhere. No z-buffer needed (Doom used it).

BSP draw, eye on minus side

draw(plus), draw poly, draw(minus).

BSP draw, eye on plus side

draw(minus), draw poly, draw(plus).

Which side of a plane is a point on?

Plug it into the plane equation: f(p) > 0 is the + side, < 0 the - side.

BSP mini-example

Plane x + 2y + 2z - 2 = 0, eye (1, 0, 1): f = 1 > 0, eye on + side, draw negative side first.

BSP construction

Pick a root, insert the rest: all vertices positive -> plus subtree, all negative -> minus subtree, recursively.

BSP straddling polygon

Split it and insert each piece on its side. A polygon in the plane can go either side.

BSP efficiency

Tree size (display visits every node). Minimize splits, which depends on insertion order.

Choosing BSP root polygons

No efficient optimal algorithm. Pick randomly, or try ~5 random candidates and use the one with fewest splits.

BSP downside

Splitting can increase the polygon count a lot.