Boundary Representation & Polygon Tables: Wireframes, Clipping & Shading

TAKEAWAYS:

• Boundary Representation (B-rep) stores 3D objects as connected vertices, edges, and faces (polygons) for efficient rendering and manipulation.
• Polygon tables organize vertex, edge, and face data to define the shape and topology of an object (e.g., a cube has 8 vertices, 12 edges, and 6 faces).
• Wireframe models display only edges (no faces), useful for debugging or skeletal animations (e.g., game character rigging).
• Polygon clipping (e.g., Sutherland-Hodgman) removes parts of polygons outside a view window to optimize rendering.
• Shading models (Gouraud/Phong) interpolate colors across polygons to simulate lighting effects (e.g., a shiny metal vs. matte surface).
• OpenGL uses polygon tables to define and render 3D objects via glBegin()/glEnd() or modern vertex buffers.

---

1. Boundary Representation (B-rep): The "DNA" of 3D Objects

B-rep is the most common way to store 3D models in CAD, games, and animations. It defines an object by its boundaries:

• Vertices: Corner points (e.g., a cube has 8).
• Edges: Lines connecting vertices (12 for a cube).
• Faces: Polygons bounded by edges (6 squares for a cube).

Why B-rep?

• Precise topology: Unlike voxel grids (e.g., Minecraft blocks), B-rep uses exact coordinates and connections.
• Efficient rendering: Only visible faces are processed.
• Easy editing: Modify vertices/edges to deform objects (e.g., morphing in animations).

How B-rep Stores Data

A polygon table organizes this data into three linked lists:

1. Vertex Table: Stores (x, y, z) coordinates of each vertex.
2. Edge Table: Lists edges as pairs of vertex indices + face adjacency.
3. Face Table: Defines polygons as ordered vertex/edge loops (e.g., Face 1: Vertices [0,1,2,3]).

---

Example: A triangle face with vertices A(0,0,0), B(1,0,0), C(0,1,0):

---

---

2. Wireframe Representation: The Skeleton of 3D

Wireframes show only edges (no filled faces). Used for:

• Debugging: Checking model topology in CAD (e.g., Blender, AutoCAD).
• Skeletal animations: Game characters (e.g., GTA V’s cars) move by deforming wireframe bones.
• Low-poly art: Style in games like Minecraft or No Man’s Sky.

How to Draw a Wireframe in OpenGL

glBegin(GL_LINES); // Start drawing lines
    glVertex3f(0,0,0); // Vertex A
    glVertex3f(1,0,0); // Vertex B
    glVertex3f(1,0,0); // Vertex B
    glVertex3f(1,1,0); // Vertex C
    // ... add all edges
glEnd();

Real-World Example:

• Pathao’s Driver App: Shows real-time wireframe routes (edges) for delivery paths, clipped to the city map (like polygon clipping).
• NTC’s Railway Track Maps: Display tracks as wireframes overlaid on satellite images.

---

---

3. Polygon Clipping: Cropping Out-of-View Geometry

Before rendering, polygons outside the view window (or viewport) are clipped to save computation. The Sutherland-Hodgman algorithm clips a polygon against a rectangular window.

How It Works

1. Define the window: A rectangle with edges x_min, x_max, y_min, y_max.
2. Clip against each edge: For each polygon edge, compute intersections with the window boundary.
3. Output: A new polygon with only visible edges.

---

Worked Example: Clip this triangle to a window [0,2] x [0,2]: Vertices: P1(0,0), P2(3,1), P3(1,3).

1. Clip vs. Left Edge (x=0):
   • P1 is inside (keep).
   • P2 is outside → intersect with x=0: (0, 1/3).
   • P3 is outside → intersect: (0, 3). New vertices: [P1, (0,1/3), (0,3)].
2. Clip vs. Bottom Edge (y=0):
   • P1 is on edge (keep).
   • (0,1/3) is above → keep.
   • (0,3) is above → keep. No change.
3. Clip vs. Right Edge (x=2):
   • P1 is inside.
   • (0,1/3) → intersect: (2, 2/3).
   • (0,3) → outside → intersect: (2,6) (but y_max=2 → discard). New vertices: [P1, (0,1/3), (2,2/3)].
4. Clip vs. Top Edge (y=2):
   • P1 is below.
   • (0,1/3) is below.
   • (2,2/3) is below → keep. Final clipped polygon: [P1, (0,1/3), (2,2/3)].

---

Real-World Example:

• Daraz’s Product Images: When you zoom into a product (e.g., a phone), the 3D model’s polygons are clipped to the visible screen area to render only what you see.
• NEPSE Stock Charts: Price graphs clip data points outside the visible window for real-time updates.

---

4. Shading Models: Simulating Light on Surfaces

Shading adds color and lighting to polygons. Two key models:

A. Gouraud Shading (Flat Interpolation)

• How it works:
  1. Calculate the normal vector at each vertex (direction of surface).
  2. Compute the color at each vertex using the Phong reflection model: $$I=k_a{I}_a+k_d(L\cdot N)I_d+k_s(R\cdot V{)}^n{I}_s$$
     • $k_a$: Ambient (constant light).
     • $k_d$: Diffuse (scatters light).
     • $k_s$: Specular (mirror-like highlight).
  3. Interpolate colors across the polygon (linear gradient).
• Pros: Fast (only 3 color calculations per polygon).
• Cons: Blurry highlights (e.g., a shiny ball looks dull).

---

---

B. Phong Shading (Smooth Interpolation)

• How it works:
  1. Interpolate normals across the polygon (not colors).
  2. Calculate the color at every pixel using the Phong model.
• Pros: Sharper highlights (e.g., metallic surfaces).
• Cons: Slower (per-pixel calculations).

---

Worked Example: Shade a red cube with:

• Ambient light: $I_a=0.2$
• Diffuse light: $I_d=0.7$, light direction $L=(0,1,0)$
• Specular light: $k_s=0.5$, view direction $V=(0,0,1)$

Vertex A (0,0,0):

• Normal $N=(0,0,1)$
• Diffuse term: $L\cdot N=0$ → $I_d=0$
• Specular term: $R=2(N\cdot L)L-L=(0,0,0)$ → $I_s=0$
• Color: $0.2\times \text{red}+0+0=\text{dark red}$

Vertex B (1,0,0):

• Normal $N=(1,0,0)$
• Diffuse term: $L\cdot N=0$ → $I_d=0$
• Specular term: $R=(1,0,0)$ → $I_s=0.5\times (1{)}^n\times I_s$
• Color: $0.2\times \text{red}+0+0.5\times I_s=\text{brighter red}$

---

Real-World Example:

• Khalti’s Payment Animation: When you swipe to pay, the 3D card uses Phong shading to show realistic reflections on the plastic.
• YouTube’s 3D Thumbnails: Video previews use Gouraud shading for quick rendering of complex scenes.

---

5. Storing 3D Data in OpenGL

OpenGL uses polygon tables to define objects. Two methods:

A. Immediate Mode (Legacy)

glBegin(GL_TRIANGLES); // Define a triangle
    glVertex3f(0,0,0); // Vertex 1
    glVertex3f(1,0,0); // Vertex 2
    glVertex3f(0,1,0); // Vertex 3
glEnd();

B. Modern Vertex Buffers (Recommended)

// Define vertices
float vertices[] = {
    0,0,0,  // Vertex 1
    1,0,0,  // Vertex 2
    0,1,0   // Vertex 3
};

// Create and bind buffer
GLuint VBO;
glGenBuffers(1, &VBO);
glBindBuffer(GL_ARRAY_BUFFER, VBO);
glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);

// Draw
glDrawArrays(GL_TRIANGLES, 0, 3);

---

Real-World Example:

• eSewa’s 3D Map: Uses OpenGL to render clipped polygons of government buildings, with Phong shading for realistic textures.
• Google Earth: Stores city models as B-rep data, clips to your view, and shades buildings based on sunlight.

---

In the Real World

1. Pathao’s Driver App:

   • Idea Used: Polygon Clipping
   • How: The app clips the delivery route (a polygon) to the city map’s viewport. If you zoom out, only major roads (edges) are shown; zoomed in, it renders detailed blocks (faces).
   • Example: A delivery from Thapathali to Lakankhel is clipped to show only the visible segment on your phone screen.

2. Ncell’s 3D Tower Visualization:

   • Idea Used: Boundary Representation + Gouraud Shading
   • How: Ncell’s network coverage maps use B-rep to store tower shapes. Gouraud shading adds ambient light to show tower heights realistically, even on low-end phones.
   • Example: A tower at Nagarkot is rendered as a polygon table with 4 vertices (base) + 4 vertices (top), shaded gray with a subtle highlight.

3. Daraz’s Product 3D Previews:

   • Idea Used: Phong Shading + Polygon Clipping
   • How: When you view a phone, Daraz’s app:
     • Clips the 3D model to your screen’s viewport.
     • Uses Phong shading to show the phone’s screen reflections and camera lens highlights.
   • Example: A Samsung Galaxy’s screen is a polygon with interpolated normals to simulate the glassy reflection.

---

Exam Tip

1. For definitions:

   • B-rep = "A 3D model stored as interconnected vertices, edges, and faces."
   • Polygon table = "Three linked lists (vertex, edge, face) defining an object’s geometry."
   • Wireframe = "A model showing only edges (no faces)."

2. For diagrams:

   • Always label vertex/edge/face tables in your answer.
   • Show clipping steps with before/after polygons (use the Sutherland-Hodgman example).

3. For shading:

   • Gouraud = "Interpolate colors."
   • Phong = "Interpolate normals, then compute per-pixel color."
   • Equation: Write the Phong reflection model but simplify for marks: $$I=k_a{I}_a+k_d(L\cdot N)I_d$$

4. For OpenGL:

   • Immediate mode: glBegin()/glEnd().
   • Modern: Vertex buffers (glGenBuffers, glDrawArrays).
   • Example: Always include a GL_TRIANGLES snippet.

5. Common pitfalls:

   • Forgetting to link edges to faces in B-rep.
   • Misclipping: Remember to clip against all 4 window edges in order.
   • Shading confusion: Gouraud is "flat" (vertex colors), Phong is "smooth" (per-pixel).

---