W5: Hidden Surfaces

CSCI 3090 - Hidden Surface

Instructor: Shima RezasoltaniDepartment: Faculty of Science, Ontario Tech

Goals

By the end of today’s class, you will be equipped to:

  • Describe the algorithms used to eliminate hidden surfaces in computer graphics.

Rendering Process

The rendering process is crucial in generating visual representations of 3D models, consisting of three standard steps:

  1. Viewing and Projection: The process of determining how the 3D scene will be viewed from a specific camera position and orientation, often involving perspective or orthographic projection methods.

  2. Hidden Surface Removal: This step eliminates surfaces that are not visible to the viewer to improve rendering efficiency and performance.

  3. Determining Surface Colour: After surface visibility is established, the next task is to compute the color and lighting effects on the visible surfaces using illumination models.

These processes are applicable in both photo-realistic and non-photorealistic rendering approaches.

Rendering Pipeline

The rendering pipeline consists of various steps that transform a 3D model into a 2D image, including:

  • Modelling of Geometry: Creating the 3D shapes and structures that make up the scene.

  • Transformation into World Coordinates: Positioning models in the 3D space defined by world coordinates.

  • Placement of Cameras and Light Sources: Defining the viewpoint and illumination settings to affect how objects are rendered.

  • Backface Culling: Discarding non-visible polygons to improve efficiency.

  • Projection: This involves projecting the 3D coordinates onto a 2D plane.

  • Clipping with Respect to View Volume: Removing parts of objects that lie outside the camera's view.

  • Hidden Surface Removal (HSR): Utilizing algorithms to ensure only visible surfaces are rendered.

  • Rasterization: Converting vector graphics into raster images for display on screens.

  • Illumination and Shading: Applying light models to calculate how objects will appear under given lighting conditions.

  • Transformation into Camera Coordinates: Adjusting the coordinates to align with the camera's perspective.

Hidden Surface Removal: Motivation

Hidden surface removal (HSR) is essential as it allows models to be processed independently in the rendering pipeline while highlighting only the visible surfaces. This approach significantly reduces computational load and improves rendering speed by eliminating unnecessary polygons early in the process.

Back Face Culling

  • Definition: Backface culling is a technique used to remove polygons facing away from the camera to reduce the rendering load.

  • Efficiency: By culling back faces, the polygon count can be cut down by approximately half for closed objects, which contributes to a faster rendering time.

  • Calculation: A polygon is discarded if the dot product of its surface normal (n) and the viewing direction (v) is greater than 0, indicating that it is a back face (i.e., if v < 0, then n • v > 0).

Back Face Culling Considerations

  • The correct signs to test depend on how the viewing direction is defined, and back faces typically have a dot product greater than 0, although definitions can vary.

  • It is advised to be cautious regarding view direction definitions, especially in complex scenes.

Validity of Dot Product Method

  • The dot product of vectors is influenced by cosine values, with positive values indicating angles between -90° to 90° relative to the viewing direction.

  • If the cosine is greater than 0, the viewer is looking at a back face, and if less than 0, they are looking at a front face.

Back Face Culling Limitations

  • This technique is not entirely effective if multiple objects within a scene overlap; it works best in scenarios with a single convex object where polygons do not cross each other.

  • The rendering sequence is crucial when handling overlapping objects, as it can dictate which surfaces are visible.

Advantages of Back Face Culling

  • By effectively removing about half of the non-visible triangles, backface culling significantly lowers the number of polygons rendered, thereby reducing rendering time by roughly 50%.

Hidden Surface Elimination Techniques

Most hidden surface elimination techniques are now implemented in hardware, although exceptions exist in high-quality film rendering environments where software solutions are still used. The main algorithm classes for hidden surface removal include:

  1. Painter’s Algorithm

  2. Z Buffer Algorithms

  3. BSP Tree Algorithms

Painter's Algorithm

  • Description: This algorithm addresses hidden surface removal by rendering triangles from back to front, ensuring that closer triangles obscure further ones.

  • Challenges: It faces challenges like cyclic overlaps, performance issues associated with O(n log n) sorting complexity, and the potential for rendering non-visible surfaces.

Z-Buffer Algorithms

  • Description: The Z-buffer (or depth buffer) algorithm is widely used in hardware graphics rendering. It retains pixel depth information (z') along with (x,y) coordinates, which represent the distance of surfaces from the viewer.

  • Handling Z-Values: The Z-values are non-linear, typically monotonically arranged from the near (n) to far (f) planes of view, necessitating proper initialization and repeated updates during rendering.

Z-Buffer Initialization and Updates

  • Process: The Z-buffer is initialized to match the screen resolution with all buffer values set to maximum depth (f). During rendering, each pixel's Z-value is checked and updated only if a new z' is found closer than the current value.

Efficiency of Z-Buffer

  • While the Z-buffer may necessitate multiple writes to pixels, the final output retains only the closest object to the viewer, thereby maximizing rendering efficiency. The simplicity of hardware implementation often compensates for its inefficiencies.

Comparison to Painter's Algorithm

  • Cyclic Overlaps: The Z-buffer effectively addresses cyclic overlaps without the need for sorting, which enhances performance.

  • Performance: The Z-buffer also simplifies hidden surface handling significantly.

Implementation Issues

  • Precision Challenges: Digital precision limitations can impact the Z-buffer's effectiveness. Current graphics systems often utilize 32 or 64-bit integers, necessitating a strategy for scaling z-values effectively.

  • Orthographic Projection: In these cases, z-values vary linearly from n to f, and careful consideration of each bin is crucial for preserving precision.

Example of Z-buffering Issues

  • An example highlighting the implications of Z-buffer precision involves the choice of near (n) and far (f) distances. If precision bin sizes lead to overlapping and indistinguishable z-values, this could adversely affect rendering quality.

Avoiding Z-fighting

  • Selecting the smallest possible depth values for n and f is essential to maximize depth range precision while avoiding excessively large values for 'f'.

Z-Fighting in Perspective Projection

  • The relationship between viewing distance (zw) and z-buffer values shows that precision is typically greater for objects that are closer to the viewer, but this leads to diminished detail for further objects due to reduced resolution.

BSP Tree Algorithms

  • This approach involves constructing a Binary Space Partitioning (BSP) tree to manage polygon sorting for rendering, ensuring the correct order based on viewing planes.

BSP Algorithm Mechanics

  • Polygons are positioned according to the viewer's location and drawn based on the sequence generated from plane equations used to partition the space effectively.

Advantages of BSP Trees

  • The accuracy of drawn images is not dependent on viewer location once a BSP tree is constructed. This approach is suitable for multiple display setups and can be applied to other geometric algorithms as well.

Constructing BSP Trees

  • Constructing a BSP tree involves ensuring that polygons do not intersect. A root polygon is selected, and subsequent polygons are evaluated for their positioning according to the signs of plane equations—this may require splitting when vertices cross the plane.

Efficiency of BSP Algorithm

  • The emphasis is on minimizing polygon splits to maintain a compact tree structure, supported by careful selection of root polygons and insertion sequences to avoid excess splits.

Summary of Algorithms for Hidden Surface Removal

In summary, the discussed techniques for hidden surface removal include:

  • Back-face culling

  • Z-Buffer Algorithms

  • Painter’s Algorithm

  • BSP Trees

Next Class

Looking ahead, the next class will cover lighting and illumination models in computer graphics, detailing how light interacts with surfaces to create realism in rendering.