Image/Object Space; Back-Face, Z-Buffer, A-Buffer, Scan-Line
Open in the Padhaiko app5.1 Image Space and Object Space Techniques
In three-dimensional computer graphics, realistic scene rendering requires identifying which surfaces and line segments are visible to an observer from a chosen viewpoint, and removing those occluded by closer opaque objects. This fundamental problem is known as visible-surface determination or hidden-surface removal (HSR).
Visible-surface determination algorithms are broadly classified into two categories based on the coordinate space in which visibility sorting and intersection testing occur: object-space methods and image-space methods.
Object-Space and Image-Space Methods
- Object-Space Methods: Operate directly in the physical coordinate system of the scene (world coordinates or viewing coordinates) where objects and polygonal primitives are defined. Visibility decisions compare geometric primitives (vertices, edges, polygons) against one another before projection.
- Image-Space Methods: Operate in the two-dimensional discrete projection plane (screen coordinate space / pixel grid) where the scene is viewed. Visibility is resolved point-by-point or pixel-by-pixel at each display position during or after scan conversion.
Fundamental Differences and Complexity
Consider a scene modeled with geometric polygon primitives displayed on a screen with pixels (where typically to pixels):
- Computational Complexity:
- An object-space algorithm performs pairwise comparisons between primitives. For polygons, worst-case complexity scales as . If spatial partitioning (such as octrees or BSP trees) is employed, average complexity can be reduced to .
- An image-space algorithm examines each of the pixels to determine which of the polygons is closest to the viewing position. In the worst case, testing every polygon against every pixel yields operations. With scan-conversion bounding boxes and depth buffers, the per-pixel cost is nearly constant after rasterization, resulting in practical linear scaling with primitive count.
- Precision and Device Dependence:
- Object-space calculations utilize continuous floating-point coordinates. The results are resolution-independent and remain valid even if the image is zoomed or printed at very high resolutions.
- Image-space calculations are constrained to the discrete pixel grid of the target display device. Precision is bounded by screen resolution and depth buffer bit-depth.
| Aspect | Object-Space Methods | Image-Space Methods |
|---|---|---|
| Operating Coordinate Domain | 3D object / world / viewing coordinate space (continuous) | 2D projection screen raster space (discrete pixels) |
| Computational Complexity | naive pairwise comparison; with spatial partitioning | worst-case; with hardware buffers |
| Resolution Dependence | Resolution-independent (continuous vector geometry) | Resolution-dependent (tied to screen grid ) |
| Sorting Criterion | Compares geometric surfaces against each other | Compares depth values of surfaces covering pixel |
| Memory Requirement | Proportional to primitive count | Proportional to screen resolution and depth bit-depth |
| Representative Algorithms | Back-face culling, Painter's algorithm (depth-sort), BSP trees | Z-buffer (depth-buffer), A-buffer, Ray casting |
Surface Coherence
Visible-surface algorithms achieve computational efficiency by exploiting coherence—the property that adjacent parts of a scene or image exhibit similar properties:
| Coherence Type | Description | Exploited By |
|---|---|---|
| Object Coherence | If an entire object is completely separated in depth from another, their internal polygons need not be compared against one another. | Hierarchical bounding volumes, octrees |
| Face Coherence | A surface polygon is continuous; properties vary smoothly across its surface without abrupt depth jumps. | Incremental plane equation evaluation |
| Edge Coherence | An edge of a polygon changes visibility only when it intersects another edge or crosses behind another polygon silhouette. | Scan-line algorithm, Roberts algorithm |
| Scan-Line Coherence | Consecutive pixels along a horizontal scanline usually belong to the same polygon span with predictable depth changes. | Scan-line visible surface determination, Z-buffer |
| Area Coherence | A cluster of adjacent pixels across several scanlines is frequently covered by a single polygon face. | Warnock area-subdivision, quadtree methods |
| Depth Coherence | At pixel , adjacent points on a planar facet have linear depth relationships derived from the plane equation. | Incremental depth calculation in Z-buffer |
| Frame Coherence | In an animation sequence, small viewpoint or object motions create minimal frame-to-frame visibility changes. | Real-time graphics pipelines, temporal anti-aliasing |
5.2 Visible Surface Detection Algorithms
Back-Face Detection (Back-Face Culling)
Back-face detection is an object-space visibility technique designed for completely enclosed solid polyhedral objects. For any closed opaque polyhedron, polygon faces on the rear side of the object face away from the observer and are completely occluded by the front-facing polygons. Identifying and discarding these rear faces before rasterization eliminates approximately of the scene's polygon primitives from subsequent processing stages.
Back-Face Test Formulation
Each polygon face on a polyhedron lies in a plane characterized by the standard Cartesian plane equation:
where is the outward-pointing unit normal vector of the polygon, oriented such that it points toward the exterior of the solid object when vertices are specified in counterclockwise order when viewed from the outside:
Let be the viewing vector directed from the surface polygon toward the viewer (camera position). In a right-handed viewing coordinate system where the line of sight looks down along the negative axis, the viewer is located at , so the viewing vector toward the camera is :
- Front-Facing Condition:
The outward normal has a positive -component directed toward the camera; the polygon is visible.
- Back-Facing Condition:
The outward normal has a zero or negative -component pointing away from the camera; the polygon is occluded and is culled.
Limitations of Back-Face Culling
- Back-face culling works strictly for closed solid polyhedra. If an object has openings or is modeled as an open thin-walled surface (e.g. an open box or sheet), interior surfaces must remain visible.
- It cannot resolve occlusion between different separate objects (e.g. an entire front object occluding a rear object).
- For non-convex polyhedra, a front face can be occluded by another front face located closer to the camera. Thus, back-face culling serves as an early pruning stage rather than a complete visible-surface solution.
Z-Buffer (Depth-Buffer) Algorithm
The Z-buffer algorithm, developed by Edwin Catmull, is the most widely implemented image-space visible-surface determination method. It operates at the pixel level during the scan-conversion (rasterization) stage of the graphics pipeline.
Z-Buffer Algorithm
The Z-buffer method employs two two-dimensional arrays matching the display resolution ( pixels):
- Depth Buffer (
depth[x, y]): Stores the smallest depth value (-distance) from the viewing plane to the closest polygon fragment observed so far at pixel . - Color Buffer (
color[x, y]): Stores the RGB color/intensity of the surface currently visible at pixel .
Algorithm Steps:
- Initialization: For all display pixels and :
- Rasterization and Depth Testing: For each polygon in the scene:
- Scan-convert the polygon across all intersecting horizontal scanlines.
- For each covered pixel , calculate the depth of the polygon surface.
- Depth Comparison:
- Output: When all polygons have been rasterized,
color[x, y]contains the finished visible-surface rendering.
Incremental Depth Calculation
Directly solving the plane equation for depth:
requires multiple multiplications and a division per pixel. By exploiting depth coherence, can be computed using simple additions:
Advantages and Limitations of the Z-Buffer Method
Advantages:
- Simplicity: Polygons can be processed in completely arbitrary order; no presorting of primitives is required.
- Hardware Integration: Implemented directly on modern graphics hardware (GPUs) with dedicated high-speed depth-caching memory.
- Scene Independence: Handles complex interpenetrating and overlapping geometry seamlessly.
Limitations:
- High Memory Footprint: Requires dedicated memory for the depth buffer (). For at 24-bit depth, this requires over of high-speed memory.
- Inability to Render Transparency: Standard Z-buffering overwrites color data; it cannot blend semi-transparent surfaces without sorting passes.
- Z-Fighting: Finite numerical precision in depth buffers (typically 16-bit or 24-bit fixed point) causes depth values of coplanar or nearly coplanar surfaces to oscillate, causing flickering artifacts.
- Silhouette Aliasing: Point-sampling without sub-pixel area averaging produces jagged edges along polygon silhouettes.
A-Buffer (Accumulation Buffer) Method
The A-buffer method, developed by Loren Carpenter at Lucasfilm, is an image-space visible-surface algorithm that extends the Z-buffer to support anti-aliasing, surface transparency, and sub-pixel area averaging.
A-Buffer Architecture
In the A-buffer, each pixel in the screen grid corresponds to a single-word memory location that can store either a direct depth-color record or a pointer to a linked list of surface fragments:
Pixel Array Entry:
+-------------------+
| Flag | Data/Ptr |
+-------------------+
- Most Significant Bit (Flag Bit):
- Non-negative (): Exactly one opaque surface covers the entire pixel area. The word directly stores the depth value and color index of that surface (identical to standard Z-buffer behavior).
- Negative (): Multiple surfaces intersect the pixel, or one or more surfaces are semi-transparent. The word stores an integer pointer to a linked list of surface fragment records.
Each surface fragment record in the linked list contains:
- Depth value (): Minimum and maximum depth () of the fragment within the pixel.
- Color / Intensity: RGB color components.
- Area Coverage Mask: A 16-bit or 32-bit binary bitmap (such as a subpixel grid) indicating which sub-pixel regions are covered by the polygon.
- Surface Identifier / Tag: Pointer to the source geometric primitive.
- Opacity / Alpha factor (): Transparency parameter ranging from (fully transparent) to (fully opaque).
- Next Fragment Pointer: Pointer to the next fragment record in the pixel's linked list.
Visibility Resolution and Anti-Aliasing
When all polygons in the scene have been processed:
- Fragments in each linked list are sorted in ascending order of depth (front-to-back from the camera).
- The area coverage masks are composited using bitwise operations:
- A running coverage accumulator tracks subpixel occlusion.
- For transparent fragments, light transmission is attenuated according to and blended with underlying layers.
- Final pixel color is calculated as the area-weighted sum of all visible fragment contributions, eliminating silhouette jaggies and correctly displaying transparent layers.
Scan-Line Method
The scan-line method is a hybrid visible-surface algorithm that combines object-space edge sorting with image-space scanline rasterization. Instead of allocating a full-screen depth buffer, the scan-line algorithm determines visibility for one horizontal scanline at a time.
Scan-Line Visibility Algorithm
The algorithm maintains three coordinated data structures across the rendering process:
- Edge Table (ET): Contains all non-horizontal polygon edges, sorted into buckets by their minimum -coordinate (). Each edge entry stores:
- : Upper scanline limit of the edge.
- : -coordinate at .
- : Inverse slope ().
- Polygon ID: Identifier of the polygon to which the edge belongs.
- Active Edge List (AEL): Contains all edges that intersect the current scanline , sorted in increasing order of their current -intersections.
- Polygon Table (PT): Contains an entry for each polygon in the scene storing its plane equation coefficients , surface shading parameters, and an In/Out Flag (a boolean initialized to
false).
Scanline Processing Loop:
- As the scanline sweeps from left to right along :
- When an edge of polygon is crossed, its in/out flag is toggled:
- Span Visibility Evaluation:
- For pixel spans where no polygon flag is
true, the background color is displayed. - When exactly one polygon flag is
true, that polygon is visible across the span up to the next edge intersection. - When multiple polygon flags are simultaneously
true(overlapping surfaces), the depth is evaluated for each active polygon at the current . The polygon with the minimum is visible.
- For pixel spans where no polygon flag is
- Incremental updates: Depth across the span is updated using , edge -intercepts are updated using , and edges reaching are purged from the AEL.
| Property | Z-Buffer | Scan-Line Method | A-Buffer |
|---|---|---|---|
| Classification | Image-space | Hybrid (Object-space sort + Image-space span) | Image-space |
| Memory Buffer | Full screen depth () + color | Scanline buffer () + Edge/Polygon tables | Full screen pixel array + dynamic fragment heap |
| Transparency Handling | No (requires depth sorting pass) | Handled across active spans | Yes (sub-pixel coverage & alpha compositing) |
| Anti-Aliasing | No (point sampled) | Possible at span boundaries | Yes (integrated subpixel masks) |
| Hardware Suitability | Native to all standard GPUs | Historically software-driven | Hardware/software hybrid pipelines |
Worked Examples
5.1
A 3D solid tetrahedron in a right-handed viewing coordinate system has four triangular faces with outward-oriented vertices given below. For a viewer observing along the negative axis (), determine which faces are visible (front faces) and which faces are culled (back faces):
- Face 1 (): , ,
- Face 2 (): , ,
- Face 3 (): , ,
- Face 4 (): , ,
Evaluating surface normal and plane coefficients for Face 1 (): Form edge vectors from :
Compute the outward normal vector via cross product:
The plane coefficients are .
Applying the back-face visibility test for Face 1: For viewing vector directed toward the camera:
Since , Face 1 has an outward normal directed toward the viewer and is classified as a front face (visible).
Evaluating Face 2 () and Face 3 (): For Face 2 with vertices :
Here . Since , Face 2 is seen edge-on and is classified as a back face (culled).
For Face 3 with vertices :
Here . Since , Face 3 is also edge-on and is classified as a back face (culled).
Evaluating Face 4 (): For Face 4 with vertices :
Here . Since , Face 4 faces away from the camera and is classified as a back face (culled).
- Face 1 (): Visible (Front Face)
- Face 2 (): Culled (Edge-on / Back Face)
- Face 3 (): Culled (Edge-on / Back Face)
- Face 4 (): Culled (Back Face)
5.2
A polygon surface lies on the plane . During scan conversion using the Z-buffer algorithm, the polygon covers pixels along horizontal scanline from to :
- Determine the depth expression and the horizontal incremental depth step .
- Compute the exact depth values at pixels and .
- If the depth buffer currently holds for , state which pixels are updated by this polygon.
Deriving depth function and incremental step : The plane equation is with . Solving for depth :
The horizontal incremental depth step is:
Evaluating depth along scanline : At , the constant offset is . Thus:
- At :
- At :
- At :
- At :
- At :
Comparing with existing depth buffer values:
- For : Updated (new depth ).
- For : Updated (new depth ).
- For : Updated (new depth ).
- For : Not Updated (retains ).
- For : Updated (new depth ).
- , with incremental step .
- Calculated depth values: , , , , .
- Updated pixels: , and . Pixel is occluded by an existing closer surface.
5.3
A graphics system renders scenes at Full HD resolution ( pixels) using a true-color frame buffer with per pixel ( per RGB channel) and a per pixel depth buffer (Z-buffer):
- Calculate the total number of pixels on the screen.
- Calculate the memory required for the frame buffer in megabytes () and mebibytes ().
- Calculate the memory required for the depth buffer in mebibytes ().
- Calculate the combined memory footprint of both buffers in mebibytes ().
Evaluating pixel count:
Calculating frame buffer memory: Each pixel stores .
Converting to decimal megabytes ():
Converting to binary mebibytes ():
Calculating depth buffer memory: Each pixel stores .
Converting to mebibytes:
Evaluating combined memory requirement:
- Total pixels: .
- Frame buffer memory: ().
- Depth buffer memory: ().
- Combined buffer memory: .
Exercises
Visible Surface Determination Exercises
Differentiate between image-space and object-space methods for hidden surface removal with respect to coordinate system, computational complexity, device dependence, and typical algorithms.
Contrasting operating domains and sorting spaces:
- Object-space methods operate in the continuous three-dimensional physical coordinate system (object or world coordinates) where geometric primitives are defined. Visibility decisions compare geometric elements directly against one another.
- Image-space methods operate in the discrete two-dimensional projection coordinate system (raster screen coordinates) of the display grid. Visibility is determined pixel-by-pixel at each point on the viewing plane.
Comparing complexity, resolution dependence, and algorithms:
- Computational Complexity: Object-space methods compare primitives against each other, scaling as without spatial sorting. Image-space methods compare primitives across display pixels, scaling as worst-case or with depth buffers.
- Device Dependence: Object-space methods are resolution-independent; results remain valid under arbitrary zooming. Image-space methods are tied directly to screen resolution .
- Algorithms: Object-space includes back-face culling and Painter's algorithm; image-space includes Z-buffer and A-buffer.
Object-space methods operate on continuous 3D world geometry with complexity independent of display resolution (e.g. Back-Face Culling). Image-space methods operate on discrete 2D screen pixels with complexity tied directly to display resolution (e.g. Z-Buffer).
A triangular polygon in a right-handed viewing coordinate system has vertices , , and . Assuming the viewer is looking along the negative axis with viewing vector directed toward the camera , test whether the polygon is a front face or a back face.
Computing edge vectors:
Evaluating the outward surface normal:
The unit normal is . The plane coefficients are .
Applying the visibility condition:
Since , the outward normal has a positive -component pointing toward the observer.
Because , the polygon normal points toward the camera; the polygon is a front face (visible).
Two overlapping polygons and cover pixel . The plane equation for is , and the plane equation for is .
- Compute the depth for both polygons at pixel .
- Determine which polygon is visible at this pixel under the Z-buffer algorithm.
- Compute the incremental depth step for along scanline .
Evaluating depth of Polygon at : From :
At :
Evaluating depth of Polygon at : From :
At :
Determining visibility and incremental step: Comparing depths:
Polygon is closer to the viewing plane and is visible. The incremental horizontal depth step for is:
- At : , .
- Polygon is visible ().
- Incremental depth step for : .
Explain the A-Buffer method for visible-surface detection. How does it handle semi-transparent surfaces and anti-aliasing compared to the standard Z-buffer?
A-Buffer data organization: The A-buffer replaces the single scalar depth buffer of the Z-buffer with an array of word entries:
- If the MSB is , the pixel is covered by a single opaque surface, storing depth and color directly.
- If the MSB is , the word stores a pointer to a linked list of surface fragment records.
Fragment linked list and anti-aliasing mechanism: Each fragment node records depth interval (), color, opacity , a sub-pixel coverage mask (e.g. bitmap), and a next pointer.
- For anti-aliasing, the coverage masks of boundary fragments are combined bitwise to determine exact sub-pixel area weighting.
- For transparency, fragments are sorted front-to-back, and colors are composited using alpha blending: .
The A-buffer extends the Z-buffer by using linked lists of surface fragments containing subpixel area coverage masks and opacity values (). This allows front-to-back alpha compositing for transparency and area-weighted filtering for anti-aliasing, overcoming the Z-buffer's point-sampling and opaque-only limitations.
Describe the scan-line method for visible-surface determination. What are the key data structures employed, and how is span coherence utilized?
Primary data structures in the scan-line method:
- Edge Table (ET): Stores all non-horizontal edges sorted by , recording , , inverse slope , and polygon ID.
- Active Edge List (AEL): Holds edges currently intersecting scanline , sorted by current -intersection.
- Polygon Table (PT): Stores plane coefficients , color, and an In/Out boolean flag for each polygon.
Span coherence and depth evaluation: As the scanline advances along :
- Crossing an edge toggles the corresponding polygon's In/Out flag.
- Across spans between edge intersections where only one flag is active, that polygon's color is filled directly without per-pixel depth comparisons.
- If multiple flags are active, depth is evaluated only at the span boundary to determine the visible surface, and incremental depth tracks depth along the span.
The scan-line method determines visibility one scanline at a time using an Edge Table, Active Edge List, and Polygon Table. It utilizes span coherence by determining visibility at edge intersections and rendering entire pixel spans without recalculating visibility at every pixel.
A planar surface has plane equation .
- Express depth as a function of .
- Calculate the incremental depth steps and .
- Along scanline , calculate the depth values at pixels .
Solving for depth :
Calculating incremental depth steps:
Evaluating depth along scanline : At :
- At :
- At :
- At :
- .
- , .
- At : , , .