Visible Surface Detection & Illumination Models: Algorithms, Shading & Lighting

Core Concepts

1. Visible Surface Detection (Hidden Surface Removal)

The goal is to determine which surfaces in a 3D scene are visible from a given viewpoint. Methods are classified into object-space (operate on scene geometry) and image-space (operate on pixels).

Object-Space Methods

• Painter’s Algorithm

  • How it works: Sort polygons by depth (far to near) and render them in order. Overlapping polygons are automatically occluded.
  • Trace: For a scene with 3 polygons (A, B, C) where A is farthest and C is closest:

    Render order: A → B → C
    

  • Limitations: Requires perfect sorting (fails with intersecting polygons) and is inefficient for complex scenes.

• Binary Space Partitioning (BSP) Trees

  • How it works: Recursively split space with planes (e.g., polygons) into front/back regions. Traverse the tree to determine visibility.
  • Example: A room split by walls into sub-volumes. Each node stores a polygon and child nodes for front/back regions.
  • Advantages: Efficient for static scenes; enables view-dependent optimizations.
  • Disadvantages: Complex to build; dynamic scenes require frequent updates.

Image-Space Methods

• Depth Buffer (Z-Buffer) Algorithm

  • How it works: For each pixel, store the closest depth (Z-value) of intersecting polygons. Render polygons in any order, updating the buffer only if a closer surface is found.
  • Pseudocode:

    for each pixel (x,y):
        depth_buffer[x][y] = ∞
    for each polygon:
        for each pixel (x,y) in polygon:
            if polygon_depth(x,y) < depth_buffer[x][y]:
                depth_buffer[x][y] = polygon_depth(x,y)
                render_pixel(x,y)
    

  • Advantages: Simple, works for any polygon order, and handles intersecting surfaces.
  • Disadvantages: Memory-intensive (requires storage for all pixels); slower for large scenes.

• Scanline Method

  • How it works: Process the scene line-by-line (scanline). For each line, sort edges by intersection points and determine visible segments using depth comparisons.
  • Comparison with Z-Buffer:

    Feature	Scanline Method	Z-Buffer Method
    Space	Object-space	Image-space
    Complexity	Higher (edge sorting)	Lower (pixel-wise)
    Memory Usage	Low	High (O(screen resolution))
    Dynamic Scenes	Poor	Better

Sweep Representations (Bonus)

• Octree: Recursively subdivide space into 8 octants. Useful for spatial queries but not directly for visibility.
• Boundary Representations (B-rep): Define solids via faces, edges, and vertices. Used in CAD but not for real-time rendering.

2. Illumination Models

Simulate how light interacts with surfaces to produce realistic colors and shadows.

Basic Models

1. Local Illumination Models

   • Ambient: Constant light (e.g., I_a = k_a * I).
   • Diffuse: Lambertian reflection (e.g., I_d = k_d * (L·N)).
   • Specular: Highlight based on viewer position (e.g., I_s = k_s * (R·V)^n).
   • Combined (Phong Model): $$I=k_a{I}_a+k_d(L\cdot N)I_d+k_s(R\cdot V{)}^n{I}_s$$ Where:
     • L = light direction,
     • N = surface normal,
     • V = viewer direction,
     • R = reflection direction.

2. Global Illumination Models

   • Ray Tracing: Simulate light paths (reflections, refractions) recursively.
   • Radiosity: Solve for equilibrium light distribution in diffuse environments.

Shading Techniques

• Flat Shading: Single color per polygon (fast but blocky).
• Gouraud Shading:
  • Interpolate vertex colors across the polygon.
  • Advantages: Smooth shading with low computation.
  • Disadvantages: Incorrect highlights (specular errors).
• Phong Shading:
  • Interpolate normals, then compute lighting per pixel.
  • Advantages: Accurate specular highlights.
  • Disadvantages: Higher computational cost.

Comparison:

3. Color Models

• RGB: Additive model (red, green, blue) for displays.
• CMYK: Subtractive model (cyan, magenta, yellow, key) for printing.
• HSV/HSL: Intuitive for color selection (hue, saturation, value/lightness).

Example: RGB values (255, 0, 0) = red, (0, 255, 0) = green.

4. Shadow Detection

• Shadow Volume: Extrude polygon edges toward light source; classify pixels inside/outside the volume.
• Shadow Mapping: Render scene from light’s perspective; compare depths in final pass.
• Challenges:
  • Aliasing (staircase artifacts).
  • Performance (real-time shadows require optimizations like cascaded shadow maps).

5. Virtual Reality (VR) vs. Augmented Reality (AR)

Mermaid Diagrams

1. Painter’s Algorithm Workflow

flowchart TD
    A["Sort Polygons by Depth\n(Far → Near)"] --> B["Render Polygon A"]
    B --> C["Render Polygon B\n(Occluded by A if overlapping)"]
    C --> D["Render Polygon C\n(Closest, fully visible)"]
    style A fill:#f9f, B fill:#bbf, C fill:#bbf, D fill:#f96

2. BSP Tree Structure

classDiagram
    class Node {
        +Polygon plane
        +Node front
        +Node back
    }
    Node --> Node : front
    Node --> Node : back
    Node "Root" --> Node "Left Child"
    Node "Root" --> Node "Right Child"
    note for Node "Splits space into\nfront/back regions"

3. Illumination Components

mindmap
  root((Illumination))
    Local
      Ambient
      Diffuse
      Specular
    Global
      Ray Tracing
      Radiosity
    Shading
      Flat
      Gouraud
      Phong

Exam Tip

• For algorithms: Draw a simple scene (e.g., 2 overlapping triangles) and trace the steps (e.g., Painter’s order or Z-buffer updates).
• For comparisons: Use tables (e.g., Scanline vs. Z-Buffer) and highlight trade-offs (memory vs. speed).
• For shading: Memorize the Phong equation and when to use Gouraud vs. Phong.
• For VR/AR: Give concrete examples (e.g., "AR overlays digital info on real-world views").
• Shadows: Mention at least two methods (e.g., shadow mapping + one challenge like aliasing).