Hidden Surface Removal

When a 3D scene containing multiple objects is projected onto a 2D screen, some surfaces of objects are naturally hidden behind other surfaces just as in the real world, where you cannot see through solid objects. 

If a graphics system were to draw every surface without determining which ones are visible, the final image would be incorrect background surfaces would appear to bleed through foreground ones, producing a visually broken, unrealistic result. 

The problem of determining which surfaces are visible from a given viewpoint, and suppressing those that are not, is called the Hidden Surface Removal (HSR) problem, also sometimes called Visible Surface Determination (VSD). 

This post provides a thorough introduction to the problem itself, its mathematical basis, classification of methods, and key concepts before diving into individual algorithms.

What is the Hidden Surface Removal Problem?

Imagine a scene containing a cube in front of a sphere. From the viewer's position, parts of the sphere are occluded by the cube they are hidden behind it. 

If both objects are simply projected onto the screen without any visibility testing, the sphere's surfaces might be drawn over the cube's surfaces (or vice versa), depending on the drawing order producing a result that looks incorrect. 

The HSR problem asks: for every pixel on the screen, which surface is closest to the viewer and therefore visible?

Hidden surface removal is one of the most fundamental problems in 3D computer graphics, and an enormous amount of research and engineering effort has gone into solving it efficiently, because real-time rendering (as in video games) must solve it for millions of pixels, hundreds of times per second.

Why is it Non-Trivial?

At first glance, the problem may seem simple just find the closest surface and draw it. But several factors make it difficult in practice:

1. Large number of surfaces: A realistic 3D scene may contain millions of triangles (polygon surfaces). Testing every surface against every other surface for occlusion is computationally intractable without clever algorithms.
2. Partial occlusion: An object may be partially visible some of its surfaces visible and some hidden. The boundary between visible and hidden regions may cut across individual polygons, requiring precise geometric computation.
3. Transparent and semi-transparent surfaces: If objects are transparent or semi-transparent, multiple surfaces along the same line of sight contribute to the final pixel color, requiring special handling (this is one motivation for the A-Buffer algorithm).
4. Dynamic scenes: In animations and interactive applications, objects and the camera move continuously, so visibility must be recomputed every frame.

Key Terminology

• Visible Surface: A surface that can be seen from the current viewpoint it is not occluded by any other opaque surface closer to the viewer.
• Hidden Surface: A surface that lies behind another opaque surface from the viewer's perspective.
• Occlusion: The relationship where one surface blocks the view of another surface behind it.
• Depth (Z-value): The distance of a surface point from the viewer, measured along the viewing direction (the Z-axis, after the scene is set up in a view coordinate system). Smaller depth = closer to viewer.
• Projection Plane: The 2D surface (the screen) onto which the 3D scene is projected.
• View Volume / Viewing Frustum: The region of 3D space that is actually visible from the camera a pyramid-shaped volume (frustum) bounded by near and far clipping planes.

Classification of Hidden Surface Removal Methods

HSR algorithms are broadly classified into two categories based on where in the coordinate space they operate:

1. Object-Space Methods

These algorithms work in 3D world/object coordinates, comparing objects and surfaces against each other geometrically before projection. 

They determine visibility analytically by testing surfaces against other surfaces.

Characteristics:

• Operate on actual geometric data (3D coordinates).
• Resolution-independent: the same computation works regardless of output image size.
• Generally more expensive for complex scenes, but produce exact results.
• Better suited to scenes with a small, well-organized number of objects.

Examples: Back-Face Culling, Painter's Algorithm, BSP Tree method.

2. Image-Space Methods

These algorithms work in 2D screen/pixel coordinates (image space), determining visibility pixel-by-pixel after projection. They test which surface contributes to each pixel of the final image.

Characteristics:

• Operate per-pixel, after projection.
• Resolution-dependent: more pixels = more computation.
• Generally well-suited to hardware implementation (GPU pipelines).
• Can handle arbitrary scene complexity with bounded per-pixel cost.

Examples: Z-Buffer algorithm, A-Buffer algorithm, Scan-Line method, Ray Casting.

Important Concepts Common to All HSR Methods

1. Depth / Z-Value

The most fundamental concept in hidden surface removal is depth how far a surface is from the viewer along the viewing direction. 

Given two surfaces that overlap at a pixel, the one with the smaller depth value (closer to the viewer) is the visible one. Almost all HSR algorithms, in one form or another, compare depth values to resolve visibility.

2. Coherence

HSR algorithms exploit coherence the observation that neighboring surfaces, scan lines, or pixels tend to share similar visibility properties. Using coherence avoids redundant computation. For example:

• Scan-line coherence: If a surface is visible on a scan line, it's likely visible on the next scan line too (until an edge is crossed).
• Area coherence: If an area of the screen is completely covered by one surface, it doesn't need further visibility testing.
• Depth coherence: Depth values change gradually across a surface, not abruptly (except at edges).

3. Polygon/Surface Normal

The surface normal is a vector perpendicular to a polygon surface. It plays an important role in Back-Face Culling if the angle between the surface normal and the viewing direction is less than 90° (the normal points away from the viewer), the back face is hidden and can be discarded.

4. The View Coordinate System

Before HSR processing, the scene is typically transformed into a view coordinate system (also called camera or eye coordinates), where:

• The viewer is at the origin.
• The viewing direction is along the negative Z-axis.
• The projection plane is perpendicular to the Z-axis. This simplifies depth comparisons to simple Z-value comparisons.

General Pipeline for 3D Rendering Including HSR

A typical 3D graphics pipeline processes a scene through the following stages, with HSR playing a crucial role:

1. Model the 3D scene (geometry + surfaces)
         ↓
2. Apply transformations (translate, rotate, scale)
         ↓
3. Set up the view coordinate system
         ↓
4. Back-face culling (object-space, discard back-facing polygons)
         ↓
5. Clip against the view volume (frustum clipping)
         ↓
6. Project onto 2D (perspective or parallel projection)
         ↓
7. Rasterize (convert projected surfaces to pixels)
         ↓
8. Hidden surface removal at pixel level (e.g., Z-buffer)
         ↓
9. Shading and coloring (lighting, textures)
         ↓
10. Display the final image

Note that HSR appears at two stages: once in object space (back-face culling, which cheaply eliminates surfaces definitely not visible), and once in image space (Z-buffer or similar, which resolves remaining visibility per pixel).

Overview of the Main Algorithms

1. Back-Face Culling (Object-Space)

This is a pre-filtering step that eliminates back-facing polygons polygons whose surface normal points away from the viewer before any further processing. Since the back faces of solid, closed objects are always hidden, this immediately discards roughly half of all polygons in a typical scene.

2. Z-Buffer Algorithm (Image-Space)

The most widely used HSR algorithm in hardware. It maintains a Z-buffer (a 2D array matching the screen resolution), storing the depth of the currently closest surface at each pixel. As each polygon is rasterized, its depth is compared with the stored value if the new surface is closer, both the Z-buffer and the color buffer are updated.

3. A-Buffer Algorithm (Image-Space)

An extension of the Z-buffer that handles transparent and semi-transparent surfaces properly. Instead of storing only the single closest surface per pixel, each pixel stores a linked list of all surfaces that cover it (the "accumulation buffer"), which are then composited together in front-to-back order.

4. Scan-Line Method (Image-Space)

Processes the scene one horizontal scan line at a time, determining visibility for all surfaces intersecting each scan line using an active edge table and depth comparison at each step.

Choosing Between Methods

Conclusion

Hidden surface removal is a foundational problem in 3D computer graphics without it, rendered images would be visually incorrect, with background surfaces bleeding through foreground ones. 

The two broad families of solutions (object-space and image-space) attack the problem from different angles: object-space methods work with the geometry directly, while image-space methods resolve visibility per pixel after projection. 

In practice, modern rendering pipelines combine both approaches back-face culling in object space to cheaply discard obvious non-visible surfaces, followed by Z-buffering in image space to resolve the remaining visibility per pixel.