Visible Surface Detection: Algorithms, Methods & Hidden Surface Removal

TAKEAWAYS:

• Visible surface detection solves the "painter’s problem": deciding which of overlapping surfaces to render.
• Object-space methods (e.g., depth sorting) work on 3D coordinates before projection, while image-space methods (e.g., Z-buffer) operate on pixel-level depth after projection.
• Back-face removal eliminates hidden polygons by discarding faces oriented away from the viewer, but fails for concave objects.
• The Z-buffer algorithm guarantees correct visibility by storing and comparing depth values per pixel, but requires memory proportional to screen resolution.
• Scanline algorithms process the scene line-by-line, sorting polygons by depth along each scanline for efficient rendering.
• Hidden surface removal is critical for realism in games (e.g., Call of Duty’s occlusion culling) and VR (e.g., Meta Quest’s foveated rendering).

---

1. Why Visible Surface Detection Matters

In a 3D scene, multiple surfaces may overlap from the viewer’s perspective. Visible surface detection determines which surfaces are visible and which are hidden, ensuring correct rendering. Without it, objects would appear transparent or incorrectly layered—like seeing through walls in a video game or a 3D model.

---

2. Classification of Methods

Methods are divided into two broad categories based on when visibility is determined:

---

3. Object-Space Methods

3.1 Back-Face Removal (Back-Face Culling)

Definition: A polygon’s back face is the side not visible to the viewer. Back-face removal discards these polygons early in the rendering pipeline.

How it works:

1. For each polygon, compute its normal vector (a vector perpendicular to the polygon’s surface).
2. Compute the dot product of the normal vector and the view vector (from the polygon to the viewer).
   • If the dot product is negative, the polygon is facing away (back face) and is discarded.
   • If positive or zero, the polygon is front-facing and rendered.

Mermaid Diagram: Back-Face Detection Logic

Worked Example: Back-Face Removal in a Cube Consider a cube with vertices at $(\pm 1,\pm 1,\pm 1)$. The front face (visible) has a normal vector $(0,0,1)$. If the viewer is at $(0,0,-2)$, the view vector to any point on the front face is $(0,0,3)$. The dot product is: $$(0,0,1)\cdot (0,0,3)=3>0\text{(Front face, render)}$$ For the back face (normal $(0,0,-1)$), the dot product is $-3<0$ (discard).

Limitations:

• Fails for concave objects (e.g., a donut shape), where some back faces may still be visible.
• Requires polygon normals to be correctly oriented.

Real-World Use:

• Pathao’s Driver App: Uses back-face culling to optimize rendering of 3D maps, reducing the number of polygons processed for driver navigation screens.
• Ncell’s AR Ads: Back-face removal helps render 3D billboards in AR without showing hidden sides.

---

3.2 Depth Sorting (Painter’s Algorithm)

Definition: Sort polygons by their average depth (distance from the viewer) and render them from back to front. The last polygon rendered at a given pixel is visible.

Algorithm Steps:

1. Compute the average depth of each polygon (e.g., average of its vertices’ $z$-coordinates).
2. Sort polygons in ascending order of depth (back to front).
3. Render polygons in this order. Overlapping pixels are overwritten by later polygons.

Worked Example: Depth Sorting for Two Overlapping Squares Assume two squares:

• Square A: Vertices at $z=2,3,2,3$ (average depth $=2.5$).
• Square B: Vertices at $z=1,1,4,4$ (average depth $=2.5$). If Square A is closer to the viewer on average, it should be rendered after Square B.

Problem: If two polygons have the same average depth but overlap partially, the algorithm fails (e.g., a "tunnel" effect where neither polygon fully obscures the other).

Real-World Use:

• Daraz’s Product 3D Previews: Uses depth sorting to render layered products (e.g., a watch on a wristband) without hidden surfaces.
• NTC’s Traffic Simulation: Simulates vehicle visibility in 3D traffic models by sorting vehicles by distance from the camera.

---

4. Image-Space Methods

4.1 Z-Buffer Algorithm (Depth Buffer)

Definition: Stores the depth (z-coordinate) of the closest surface at each pixel. The surface with the smallest depth (closest to the viewer) is visible.

How it works:

1. Initialize a Z-buffer (2D array) with infinity values, matching the screen resolution.
2. For each polygon:
   • Project its vertices to screen coordinates.
   • For each pixel covered by the polygon, compute its depth ($z$).
   • If the computed depth is less than the stored depth in the Z-buffer, update the buffer and render the pixel.
3. After processing all polygons, the Z-buffer contains the visible surfaces.

Mermaid Diagram: Z-Buffer Pipeline

Worked Example: Z-Buffer for Two Triangles Consider two triangles:

• Triangle 1: Vertices at $(0,0,1)$, $(2,0,1)$, $(1,2,1)$ (depth $z=1$).
• Triangle 2: Vertices at $(1,1,2)$, $(3,1,2)$, $(2,3,2)$ (depth $z=2$). The Z-buffer starts as all infinity. After processing Triangle 1, its pixels have $z=1$. Triangle 2’s pixels have $z=2$, so they are discarded where Triangle 1 covers the same pixels.

Advantages:

• Simple to implement and works for any scene.
• Guarantees correctness for all convex and concave objects.
• Parallelizable: Different polygons can be processed independently.

Disadvantages:

• Memory-intensive: Requires a Z-buffer of size $\text{width}\times \text{height}\times \text{bits per depth}$.
• Slower for complex scenes due to per-pixel depth tests.

Real-World Use:

• Google Maps 3D: Uses Z-buffering to render buildings and terrain layers correctly in Street View.
• Khalti’s AR Payment Demo: Renders 3D payment interfaces with accurate visibility for AR glasses users.

---

4.2 Scanline Algorithm

Definition: Processes the scene line by line (scanline by scanline), sorting polygons that intersect each scanline by depth. Efficient for scenes with many polygons.

Algorithm Steps:

1. Preprocess: Sort all polygons by their minimum and maximum y-coordinates (scanline range).
2. Active List: Maintain a list of polygons that intersect the current scanline.
3. For each scanline:
   • Update the active list by adding/removing polygons whose scanline range includes the current line.
   • Sort the active polygons by their depth along the scanline.
   • Render the polygons from back to front, overwriting pixels as needed.

Worked Example: Scanline for Two Overlapping Rectangles Assume two rectangles:

• Rectangle A: $y$ range $[0,4]$, depth $z=1$.
• Rectangle B: $y$ range $[1,3]$, depth $z=2$. For scanline $y=2$:

1. Both rectangles are in the active list.
2. Sort by depth: Rectangle A ($z=1$) comes after Rectangle B ($z=2$).
3. Render Rectangle B first, then Rectangle A (overwriting where they overlap).

Advantages:

• Efficient for scenes with many polygons (avoids per-pixel Z-buffer tests).
• Memory-friendly: Does not require storing depth for every pixel.

Disadvantages:

• Complex implementation: Requires careful handling of polygon intersections.
• Slower for dynamic scenes: Must reprocess the entire scene for each frame.

Real-World Use:

• YouTube’s 3D Video Rendering: Uses scanline algorithms to optimize rendering of 3D videos with layered objects.
• NEPSE’s Stock Chart Animations: Renders animated 3D stock graphs by processing scanlines for smooth transitions.

---

5. Comparison of Methods

---

6. Advanced Topics: Hybrid Approaches

In practice, combinations of methods are used:

• Back-face removal + Z-buffer: First discard back faces, then use Z-buffer for remaining polygons.
• Octree Spatial Partitioning: Divide the scene into 3D regions (octrees) and process only visible regions.
• Level of Detail (LOD): Use simpler models for distant objects to reduce computation.

Real-World Example:

• Call of Duty’s Occlusion Culling: Uses a combination of back-face removal and Z-buffering to render only visible objects in large battlefields, improving performance.

---

## In the Real World

1. Pathao’s Driver App:

   • Idea Used: Back-face removal and depth sorting.
   • How: The app renders 3D maps of Kathmandu’s roads. Back-face removal discards hidden sides of buildings, while depth sorting ensures correct layering of vehicles and traffic signs. This reduces the number of polygons processed, making the app run smoothly on low-end phones.

2. Khalti’s AR Payment Demo:

   • Idea Used: Z-buffer algorithm.
   • How: When users view a 3D payment interface through AR glasses, the Z-buffer ensures that the virtual payment button appears correctly in front of or behind real-world objects (e.g., a table). Without Z-buffering, the button might appear transparent or misaligned.

3. Daraz’s Product 3D Previews:

   • Idea Used: Scanline algorithm for layered products.
   • How: When viewing a product like a smartphone with a case, the scanline algorithm processes each horizontal slice of the image, sorting the case and phone by depth. This ensures the case appears in front of the phone where they overlap, without requiring a full Z-buffer.

---

## Exam Tip

1. Definitions:

   • Always define visible surface detection as "the process of determining which surfaces in a 3D scene are visible to the viewer."
   • For Z-buffer, emphasize that it stores depth values per pixel and compares them to render the closest surface.

2. Algorithms:

   • For back-face removal, show the dot product calculation and explain why concave objects fail.
   • For depth sorting, highlight the "painter’s algorithm" analogy and the failure case with equal-depth polygons.
   • For Z-buffer, describe the initialization, per-pixel depth test, and final output.

3. Comparisons:

   • Exams often ask to compare object-space vs. image-space methods. Use the table above but add:
     • Object-space: Works before projection; faster but less accurate for complex scenes.
     • Image-space: Works after projection; slower but always correct.

4. Worked Examples:

   • Always show calculations for depth sorting or back-face removal. For Z-buffer, trace how a single pixel’s depth is updated.
   • Use small numbers (e.g., $z=1,2,3$) to avoid arithmetic errors.

5. Real-World Applications:

   • Link algorithms to Nepali apps (e.g., Daraz, Pathao, Khalti) or global tech (Google Maps, YouTube). For example:
     • "Like Daraz’s 3D product viewer, depth sorting ensures the watch strap appears in front of the watch face."
     • "Khalti’s AR uses Z-buffering to render virtual buttons correctly over real tables."

6. Common Pitfalls:

   • Back-face removal fails for concave objects: Always mention this in limitations.
   • Depth sorting fails for equal-depth polygons: Show a diagram where two polygons overlap at the same depth.
   • Z-buffer memory usage: Highlight that it scales with screen resolution.

7. Diagrams:

   • Draw a 3D scene with overlapping polygons and label visible/hidden faces.
   • Show a Z-buffer table with pixel coordinates, depth values, and rendered colors.
   • Trace a scanline through overlapping rectangles, showing depth sorting at each step.

---