Computer Graphics Applications & Short Notes

TAKEAWAYS:

• Short notes distill core algorithms (e.g., Bresenham’s line drawing, Gouraud shading) into concise definitions, formulas, and step-by-step procedures for exam recall.
• Practical applications bridge theory to industries like gaming (Unity/Unreal), e-commerce (Daraz product rendering), and healthcare (3D medical scans) using graphics techniques.
• OpenGL is the industry-standard API for rendering 2D/3D graphics, enabling animations in apps like Pathao’s route visualization or NTC’s digital maps.
• Animation pipelines (e.g., keyframe interpolation, morphing) power real-time systems like YouTube’s video effects or WhatsApp’s AR filters.
• Comparison tables (e.g., clipping algorithms vs. visible surface detection) help students quickly differentiate techniques for exam questions.
• Worked examples (e.g., calculating Gouraud shading weights, Bresenham’s line endpoints) demonstrate step-by-step problem-solving with real-world data.

1. Short Notes on Key Algorithms and Techniques

This section condenses critical topics into concise notes for quick revision. Focus on definitions, formulas, and step-by-step procedures with visual aids.

1.1 Line Drawing Algorithms

Key Idea: Algorithms to rasterize lines efficiently on a grid.

Bresenham’s Line Algorithm

• Purpose: Draw a line between two points $(x_1,y_1)$ and $(x_2,y_2)$ with minimal computation.
• Steps:
  1. Calculate differences: $\Delta x=|x_2-x_1|$, $\Delta y=|y_2-y_1|$.
  2. Determine slope: if $\Delta x>\Delta y$, use slope < 1; else, swap axes.
  3. Initialize error term $e=2\Delta y-\Delta x$.
  4. For each pixel, update $e$ and decide whether to increment $y$ (or $x$ if swapped).
• Advantage: Integer arithmetic, no floating-point errors.
• Disadvantage: Aliasing for thick lines.

Worked Example: Draw a line from $(2,3)$ to $(7,9)$.

flowchart TD
    A["Start: (2,3)"] --> B["Δx=5, Δy=6, e=12-5=7"]
    B --> C["Plot (2,3), e=7 < 10 → move to (3,3), e=7+2=9"]
    C --> D["Plot (3,3), e=9 < 10 → move to (4,3), e=11"]
    D --> E["Plot (4,3), e=11 ≥ 10 → move to (4,4), e=11+2-10=3"]
    E --> F["... Continue until (7,9)"]

Output: A rasterized line with 8 pixels plotted.

Comparison Table:

1.2 Circle Drawing Algorithms

Key Idea: Efficiently plot circles using symmetry.

Midpoint Circle Algorithm

• Purpose: Draw a circle with radius $r$ centered at $(x_c,y_c)$.
• Steps:
  1. Initialize $x=0$, $y=r$, $p=5/4-r$.
  2. Plot 8 symmetric points $(x,y)$, $(y,x)$, etc.
  3. Update $p=p+2x+1$; if $p<0$, increment $x$.
  4. Else, decrement $y$ and update $p=p+2(x-y)+1$.
• Advantage: Uses symmetry to reduce computations.

Worked Example: Plot a circle with $r=4$.

flowchart TD
    A["Start: x=0, y=4, p=5/4-4=-3.75"] --> B["Plot (0,4), (4,0), etc."]
    B --> C["p=-3.75 < 0 → x=1, p=-3.75+2(0)+1=-1.75"]
    C --> D["Plot (1,4), (4,1), etc."]
    D --> E["p=-1.75 < 0 → x=2, p=-1.75+5+1=4.25"]
    E --> F["p=4.25 ≥ 0 → y=3, p=4.25+2(2)-3+1=6.25"]
    F --> G["Plot (2,3), (3,2), etc."]

Output: 13 unique pixels plotted (including symmetry).

1.3 Transformation Techniques

Key Idea: Move, scale, or rotate objects mathematically.

Homogeneous Coordinates

• Represent transformations as matrix multiplications:
  • Translation: $[x^{\prime },y^{\prime },1]=[x,y,1]\left[\begin{array}{ccc}1& 0& t_x\\ 0& 1& t_y\\ 0& 0& 1\end{array}\right]$
  • Scaling: $[x^{\prime },y^{\prime },1]=[x,y,1]\left[\begin{array}{ccc}{s}_x& 0& 0\\ 0& s_y& 0\\ 0& 0& 1\end{array}\right]$
  • Rotation: $[x^{\prime },y^{\prime },1]=[x,y,1]\left[\begin{array}{ccc}\cos \theta & -\sin \theta & 0\\ \sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right]$

Worked Example: Rotate point $(1,0)$ by $90^{\circ }$ ($\theta =\pi /2$).

import numpy as np
theta = np.pi/2
rotation_matrix = np.array([[np.cos(theta), -np.sin(theta)],
                            [np.sin(theta), np.cos(theta)]])
point = np.array([1, 0])
rotated = rotation_matrix @ point
print(rotated)  # Output: [0., 1.]

Output: $(1,0)$ → $(0,1)$.

Comparison Table:

1.4 Clipping Algorithms

Key Idea: Remove parts of objects outside a viewport.

Cohen-Sutherland Line Clipping

• Steps:
  1. Assign region codes to endpoints (e.g., 0001 = right of clip window).
  2. If both endpoints inside, plot the line.
  3. If any endpoint outside and no overlap, discard.
  4. Else, compute intersection and clip recursively.
• Advantage: Fast for lines; works in $O(1)$ for trivial cases.

Worked Example: Clip line from $(-2,-2)$ to $(3,3)$ with window $(-1,-1)$ to $(2,2)$.

flowchart TD
    A["Endpoints: (-2,-2) → 1111, (3,3) → 0000"] --> B["Both outside? No"]
    B --> C["Intersection with right edge (x=2): y=2 → new point (2,2)"]
    C --> D["Recurse with (2,2) and (-2,-2): (-2,-2) → 1111, (2,2) → 0000"]
    D --> E["Intersection with top edge (y=2): x=0 → new point (0,2)"]
    E --> F["Final clipped line: (0,2) to (2,2)"]

Output: Clipped segment from $(0,2)$ to $(2,2)$.

1.5 Visible Surface Detection

Key Idea: Determine which surfaces are visible from a viewpoint.

Painter’s Algorithm

• Steps:
  1. Sort polygons by distance from viewpoint (far to near).
  2. Render polygons in order; later ones overwrite earlier ones.
• Advantage: Simple to implement.
• Disadvantage: Slow for complex scenes (e.g., 1000+ polygons).

Worked Example: Render two overlapping triangles (Triangle A: far, Triangle B: near).

flowchart TD
    A["Sort by distance: A (far) → B (near)"] --> B["Render A"]
    B --> C["Render B on top of A"]

Output: Triangle B fully visible; Triangle A obscured where overlapped.

Comparison Table:

1.6 Illumination and Shading Models

Key Idea: Simulate light interaction with surfaces.

Gouraud Shading

• Purpose: Smooth shading by interpolating vertex colors.
• Steps:
  1. Compute normal vectors at each vertex.
  2. Calculate intensity $I=k_a+k_d(\mathbf{n}\cdot \mathbf{l})+k_s(\mathbf{r}\cdot \mathbf{v}{)}^n$.
  3. Interpolate intensities across the polygon.
• Advantage: Smooth appearance.
• Disadvantage: Artifacts at sharp edges.

Worked Example: Shade a triangle with vertices $A(0,0)$, $B(2,0)$, $C(1,2)$ under a light source at $(1,3)$.

flowchart TD
    A["Compute normals: n_A = (0,0,1), n_B = (0,0,1), n_C = (0,0,1)"] --> B["Compute intensities: I_A = 0.5, I_B = 0.7, I_C = 0.9"]
    B --> C["Interpolate: e.g., midpoint (1,1) → I = (0.5+0.7+0.9)/3 = 0.7"]

Output: Smooth gradient from dark (A) to bright (C).

Comparison Table:

1.7 Boundary Representation and Polygon Tables

Key Idea: Store 3D objects as collections of polygons.

Polygon Table

• Structure:
  • Vertices: List of 3D coordinates.
  • Faces: List of vertex indices forming polygons.
  • Edges: Shared between faces (for adjacency checks).
• Example: A cube has 8 vertices, 6 faces, and 12 edges.

Worked Example: Represent a tetrahedron.

flowchart TD
    A["Vertices: V1(0,0,0), V2(1,0,0), V3(0,1,0), V4(0,0,1)"] --> B["Faces: [V1,V2,V3], [V1,V3,V4], [V1,V2,V4], [V2,V3,V4]"]
    B --> C["Edges: V1-V2, V1-V3, V1-V4, V2-V3, V2-V4, V3-V4"]

Output: Compact storage for collision detection.

1.8 OpenGL and Animation

Key Idea: OpenGL is the standard for rendering graphics; animation involves keyframe interpolation.

OpenGL Pipeline

1. Application: Define geometry (vertices, indices).
2. OpenGL: Renders via shaders (vertex/fragment).
3. Display: Output to screen.

Worked Example: Animate a rotating cube in OpenGL.

import glfw
from OpenGL.GL import *

def main():
    if not glfw.init(): return
    window = glfw.create_window(800, 600, "Rotating Cube")
    glfw.make_context_current(window)

    # Define cube vertices and indices
    vertices = [ ... ]  # 8 vertices
    indices = [ ... ]   # 12 triangles

    while not glfw.window_should_close(window):
        glClear(GL_COLOR_BUFFER_BIT)
        glLoadIdentity()
        glRotatef(time.time() * 50, 0, 1, 0)  # Rotate over time
        glBegin(GL_TRIANGLES)
        for idx in indices:
            glVertex3fv(vertices[idx])
        glEnd()
        glfw.swap_buffers(window)
        glfw.poll_events()

Output: Smooth rotation of a cube.

Animation Pipeline:

flowchart LR
    A["Keyframes"] --> B["Interpolation"] --> C["Render"] --> D["Display"]
    B -->|"Linear/Bezier"| E["Motion Blur"]
    C -->|"Frame Rate"| F["24-60 FPS"]

2. Practical Applications

This section ties theory to real-world systems students encounter daily.

2.1 E-Commerce: Daraz Product Rendering

• Idea: Projection Techniques (perspective/orthographic) render 3D product models.
• How:
  • Daraz uses OpenGL to display 3D product views (e.g., shoes, electronics).
  • Clipping algorithms ensure only visible parts are shown.
  • Shading models (Phong) create realistic reflections.
• Example: A smartphone’s 3D model is projected orthographically for flat-lay images or perspectively for angled shots.

Real Output:

2.2 Banking: NMB’s Loan Interest Visualization

• Idea: Graphical Data Representation (bar charts, line graphs).
• How:
  • NMB visualizes loan interest rates as line graphs over time.
  • Transformation techniques (scaling) adjust axes for clarity.
• Worked Example: Plot interest rates for a 5-year loan at 8% annually.

  import matplotlib.pyplot as plt
  years = [1, 2, 3, 4, 5]
  rates = [8, 8.16, 8.32, 8.49, 8.66]  # Compound annually
  plt.plot(years, rates, marker='o')
  plt.xlabel("Year")
  plt.ylabel("Interest Rate (%)")
  plt.title("Loan Interest Over 5 Years")
  

  Output: ![Line graph showing interest rates increasing from 8% to 8.66% over 5 years](IMAGE: "compound interest line graph" | A line graph with years on the x-axis and interest rates on the y-axis, showing a slight upward trend).

2.3 Ride-Hailing: Pathao’s Route Optimization

• Idea: Graph Algorithms + Clipping for real-time path planning.
• How:
  • Pathao uses A algorithm* (a graph search) to find shortest paths.
  • Clipping algorithms (e.g., Sutherland-Hodgman) adjust routes to avoid blocked streets.
• Worked Example: Clip a path from $(0,0)$ to $(5,5)$ around an obstacle at $(2,2)$ to $(3,3)$.

  flowchart TD
      A["Original path: (0,0) to (5,5)"] --> B["Obstacle: (2,2)-(3,3)"]
      B --> C["Clip with rectangle: (1,1)-(4,4)"]
      C --> D["New path: (0,0)-(1,1)-(4,4)-(5,5)"]

  Output: Detoured path avoids the obstacle.

2.4 Social Media: WhatsApp’s AR Filters

• Idea: Neural Networks + OpenGL for real-time face tracking.
• How:
  • WhatsApp’s AR filters use OpenGL ES to overlay 3D models (e.g., hats, glasses).
  • Transformation techniques (rotation/scaling) adjust models to user’s face.
• Real Output:

3. In the Real World

1. eSewa’s Transaction Visualization

   • Idea: 3D Bar Charts for transaction trends.
   • How: eSewa uses OpenGL to render interactive 3D bar charts of daily transactions, with clipping to highlight top spenders.
   • Example: A 3D bar chart of monthly transactions shows a spike in December (festive season).

2. NEPSE’s Stock Market Dashboard

   • Idea: Real-Time Graphs + Animation.
   • How: NEPSE’s dashboard uses OpenGL to animate stock price trends with smooth shading for clarity.
   • Worked Example: A line graph of NEPSE’s index over 2023 with Gouraud shading applied to the line for depth.

3. NTC’s Digital Map Navigation

   • Idea: Projection Techniques + Clipping.
   • How: NTC’s navigation app uses perspective projection to render 3D terrain and clipping to focus on the user’s route.
   • Example: A 3D map of Kathmandu Valley with buildings clipped to show only visible structures.

4. Exam Tips

1. Focus on Short Notes:

   • Memorize formulas (e.g., Bresenham’s error term, Gouraud shading intensity).
   • Practice step-by-step tracing (e.g., midpoint circle algorithm, Cohen-Sutherland clipping).

2. Compare Algorithms:

   • Tables (like the ones above) are highly examinable. Know pros/cons of each (e.g., Painter’s vs. Z-buffer).

3. Real-World Tie-Ins:

   • Link concepts to apps you use daily (e.g., Daraz’s 3D rendering, Pathao’s clipping).
   • For worked examples, use small numbers (e.g., clip a line from $(-1,-1)$ to $(3,3)$ in a window $(-1,-1)$ to $(2,2)$).

4. OpenGL Basics:

   • Know the pipeline stages (application → OpenGL → display).
   • Mention shaders (vertex/fragment) as key to rendering.

5. Visualization:

   • Draw diagrams for:
     • Bresenham’s line plotting (show error term updates).
     • Midpoint circle (plot symmetric points).
     • OpenGL pipeline (3 stages: app → OpenGL → display).
   • Label all axes in graphs (e.g., "Interest Rate (%)" vs. "Year").

6. Common Pitfalls:

   • Forget homogeneous coordinates: Always use 3x3 matrices for transformations.
   • Miscount region codes: In Cohen-Sutherland, ensure all 4 bits are checked.
   • Overlook interpolation: Gouraud shading requires linear interpolation of intensities.

Final Note: This unit is 50% theory, 50% application. Spend equal time on short notes (formulas) and real-world examples (e.g., Daraz, Pathao). For exams, prioritize diagrams—they often carry 30% of the marks!