UNIT 5: Computer Graphics & Multimedia - Exam-Focused Notes

I. Display Systems and Input Devices

Raster Scan vs. Random Scan Displays

Direct View Storage Tube (DVST)

• Working: Uses a storage mesh behind phosphor. Electron beam writes image onto mesh, which retains charge pattern, continuously illuminating phosphor. No refresh needed.

• Advantages:

  • No frame buffer → low cost.

  • Flicker-free display (no refresh).

  • High resolution, stable image.

• Disadvantages:

  • Cannot modify displayed graphics selectively (must erase entire screen).

  • No animation or dynamic updates.

  • No color (typically monochrome).

Cathode Ray Tube (CRT)

• Principle: Electron gun emits beam, deflected by magnetic/electrostatic fields, strikes phosphor-coated screen to produce light.

• Key Components:

  1. Electron Gun (Cathode, Control Grid, Focusing/Accelerating Anodes)

  2. Deflection System (Magnetic: yoke coils; Electrostatic: plates)

  3. Phosphor Screen (P1-green, P4-white for BW; RGB dots for color)

• Types: Random scan (vector), Raster scan.

Interactive Input Devices

Rubber Band Techniques

• Concept: Interactive technique where a line segment appears to stretch between a fixed starting point and the current cursor position, like a rubber band, until the user clicks to fix the endpoint.

• Use Case: Drawing lines, selecting rectangular regions, creating shapes in graphics editors.

• Implementation: Continuously redraw the line from (x_start, y_start) to (current_x, current_y) on mouse motion events.

[!TIP] Exam Focus: DVST advantages/disadvantages and CRT components are frequent short notes. Rubber band is often asked with other interactive techniques.

II. Primitive Generation Algorithms

Line Drawing Algorithms

1. DDA (Digital Differential Analyzer)

• Principle: Uses line equation y = mx + c. For each x, compute y = y + m (if |m| ≤ 1) or x = x + 1/m (if |m| > 1).

• Algorithm:

  
  dx = x2 - x1, dy = y2 - y1
  
  steps = max(|dx|, |dy|)
  
  xinc = dx/steps, yinc = dy/steps
  
  x = x1, y = y1
  
  plot(round(x), round(y))
  
  for i=1 to steps:
  
      x += xinc; y += yinc
  
      plot(round(x), round(y))
  
  

• Complexity: O(n), where n = number of pixels.

• Drawback: Uses floating-point → slower; cumulative rounding error.

2. Bresenham's Line Algorithm

• Principle: Uses integer arithmetic only. Decision parameter p determines next pixel.

• For slope 0 ≤ m ≤ 1:

  • dx = x2-x1, dy = y2-y1

  • p = 2dy - dx (initial)

  • For each x:

    • If p < 0: x++, p += 2dy

    • Else: x++, y++, p += 2(dy-dx)

• Example: Line from (1,1) to (5,5):

  • dx=4, dy=4, p0=2*4-4=4

  • p0=4≥0 → (2,2), p1=4+2(4-4)=4

  • p1=4≥0 → (3,3), p2=4+0=4

  • ... → points: (1,1), (2,2), (3,3), (4,4), (5,5).

• Complexity: O(n), faster than DDA.

Circle Drawing: Midpoint Circle Algorithm

• Principle: Uses circle equation x² + y² = r². For first octant (x≥y), decision parameter p at midpoint (x+1, y-0.5).

• Algorithm:

  
  x = 0, y = r
  
  p = 1 - r   // initial p
  
  plot(x,y) and symmetric points
  
  while x < y:
  
      x++
  
      if p < 0:
  
          p += 2x + 1
  
      else:
  
          y--; p += 2(x-y) + 1
  
      plot(x,y) and symmetric points
  
  

• Example: r=5.

  • (0,5), p0=1-5=-4<0 → (1,5), p1=-4+2*1+1=-1

  • p1=-1<0 → (2,5), p2=-1+2*2+1=4

  • p2=4≥0 → (3,4), p3=4+2(2-4)+1=1

  • ... → points: (0,5),(1,5),(2,5),(3,4),(4,3),(5,0).

Curves

Bézier Curves

• Definition: Parametric curves defined by control points P0, P1, ..., Pn. Curve lies within convex hull.

• Linear (n=1): B(t) = (1-t)P0 + tP1

• Quadratic (n=2): B(t) = (1-t)²P0 + 2(1-t)tP1 + t²P2

• Cubic (n=3): B(t) = (1-t)³P0 + 3(1-t)²tP1 + 3(1-t)t²P2 + t³P3

• Properties:

  • Endpoint interpolation: B(0)=P0, B(1)=Pn.

  • Tangent at endpoints: B'(0) ∝ (P1-P0), B'(1) ∝ (Pn-Pn-1).

  • Affine invariance.

• Midpoint: t=0.5 gives midpoint on curve.

B-spline Curves

• Definition: Piecewise polynomial curve defined by control points and knot vector. Degree d controlled by knot multiplicity.

• Key Properties:

  • Local control: Moving a control point affects only nearby curve segments.

  • Smoothness: C^{d-1} continuity at join points.

  • Convex hull property.

  • Does not necessarily pass through endpoints (except for special knot vectors).

• Cubic B-spline (d=3, uniform):

  • Basis functions: N_{i,3}(t) defined recursively (Cox-de Boor).

  • Curve: C(t) = Σ_{i=0}^{n} P_i N_{i,3}(t).

[!TIP] Exam Focus: Bresenham's and Midpoint Circle algorithms must include a worked example. Bézier equations for cubic are essential. B-spline's local control vs. Bézier's global control is a key difference.

III. Geometric Transformations

2D Transformations (Homogeneous Coordinates)

Use 3×3 matrices for points (x,y,1).

Rotation about Arbitrary Point (x_r, y_r)

1. Translate point to origin: T(-x_r, -y_r)

2. Rotate: R(θ)

3. Translate back: T(x_r, y_r)

• Composite Matrix: M = T(x_r,y_r) * R(θ) * T(-x_r,-y_r)

• Example: Rotate triangle A(0,0), B(2,2), C(4,2) about P(-2,-2) by 45°.

  • Translate by (2,2), rotate 45°, translate back (-2,-2).

3D Transformations (Overview)

• Use 4×4 homogeneous matrices.

• Basic: Translation, Rotation (about x,y,z axes), Scaling.

• Rotation matrices:

  • $$\displaystyle R_x(θ) = \begin{bmatrix}1&0&0&0\\0&\cosθ&-\sinθ&0\\0&\sinθ&\cosθ&0\\0&0&0&1\end{bmatrix} $$

  • Similarly for R_y, R_z.

Viewing Transformation

• Purpose: Transform world coordinates to device coordinates (normalized device coordinates, NDC).

• Steps:

  1. Modeling Transformation: Object coordinates → World coordinates.

  2. Viewing Transformation: World coordinates → Eye coordinates (camera at origin, looking down -Z). Uses gluLookAt().

  3. Projection Transformation: Eye coordinates → Clip coordinates (via parallel or perspective projection matrix).

  4. Viewport Transformation: Clip coordinates → Window/Device coordinates.

[!TIP] Exam Focus: Rotation about arbitrary point is a guaranteed 7-mark question. Always show the composite matrix and apply to all vertices.

IV. Clipping

Line Clipping: Cohen-Sutherland Algorithm

• Principle: Uses region codes (4-bit outcodes) for line endpoints relative to clipping window.

  • Bits: left(1), right(2), bottom(4), top(8).

• Algorithm:

  1. Compute outcodes c1, c2 for endpoints.

  2. Trivial Accept: c1 == 0 && c2 == 0 → keep line.

  3. Trivial Reject: (c1 & c2) != 0 → discard line.

  4. Else: Clip line against window edge where outcode indicates outside.

     • Find intersection with boundary line (e.g., x = x_min if left bit set).

     • Replace endpoint, recompute outcode.

     • Repeat until accept/reject.

• Example (from Jun 2025 paper):

  • Window: x∈[0,340], y∈[0,340].

  • Line AB: A(-170,595), B(170,255).

    • c_A = top(8) + left(1) = 9, c_B = 0 → not trivial.

    • A is top-left. Clip against y=340 (top edge).

      • Parametric: x = -170 + t*(340), y = 595 + t*(-340)

      • Set y=340: 595 - 340t = 340 → t = 0.75

      • New A' = (-170+0.75*340, 340) = (85, 340)

      • Recompute c_A' = 0 → accept line A'B.

  • Line CD: C(425,85), D(595,595).

    • c_C = right(2), c_D = right(2)+top(8)=10 → c_C & c_D = 2 → reject.

Other Line Clipping: Liang-Barsky

• Principle: Parametric line representation x = x1 + t·dx, y = y1 + t·dy, 0≤t≤1.

• Compute t values for intersections with each window edge:

  • For left: t_L = (x_min - x1)/dx

  • For right: t_R = (x_max - x1)/dx

  • For bottom: t_B = (y_min - y1)/dy

  • For top: t_T = (y_max - y1)/dy

• Set t1 = max(0, t_L, t_B), t2 = min(1, t_R, t_T).

• If t1 < t2 → clip from t1 to t2; else reject.

• Advantage: Fewer calculations than Cohen-Sutherland for lines that cross window.

Polygon Clipping: Cyrus-Beck Algorithm

• Principle: Parametric clipping for convex polygons. Works on polygon edges.

• Steps:

  1. For each edge i of convex clipping window, define inward normal n_i.

  2. For each vertex P of polygon, compute t values where edge P->P_next enters/exits half-plane of window edge.

     • t_E = (n_i·(P_i - P)) / (n_i·(P_next - P)) (where P_i is a point on window edge i).

  3. Find t_enter = max(0, all t_E) and t_exit = min(1, all t_L).

  4. If t_enter < t_exit → polygon is partially/fully inside; clip segment between these t values.

• Key: Only works for convex clipping windows.

[!TIP] Exam Focus: Cohen-Sutherland must include region code table and step-by-step clipping. Cyrus-Beck explanation must include inward normals and t_enter/t_exit logic.

V. 3D Rendering and Projections

Projections

Hidden Surface Removal

1. Back-face Detection

• Principle: For convex polyhedra, if normal vector N and view vector V satisfy N·V > 0, face is back-facing (away from viewer) → can be removed.

• Application: Efficient for closed objects. Must be combined with Z-buffer or Painter's for complex scenes.

• Formula: For face with vertices ordered CCW (viewed from outside), N = (V1-V0) × (V2-V0). V = (eye - any vertex).

2. Z-buffer (Depth Buffer) Technique

• Algorithm:

  1. Initialize depth_buffer[x,y] = ∞, frame_buffer[x,y] = background.

  2. For each polygon:

     • For each pixel (x,y) in polygon's projection:

       • Compute depth z at (x,y).

       • If z < depth_buffer[x,y]:

         • depth_buffer[x,y] = z

         • frame_buffer[x,y] = polygon's color

• Complexity: O(n) per pixel, where n = number of polygons.

• Pros: Simple, handles any polygon order.

• Cons: Requires extra memory (depth buffer), no transparency.

3. Painter's Algorithm

• Principle: Sort polygons by average depth (or farthest depth) from viewer. Draw farthest first.

• Steps:

  1. Sort polygons by z_max (or centroid z).

  2. Draw in sorted order (back to front).

• Problems:

  • Cyclic overlap (A overlaps B, B overlaps C, C overlaps A) → fails.

  • Requires splitting polygons in such cases.

• Use: Often combined with depth sorting and area subdivision.

Shading and Reflection

1. Diffuse Reflection (Lambertian)

• Light scattered equally in all directions.

• Intensity: I_diffuse = k_d * I_light * (N·L)

  • k_d: diffuse reflection coefficient (0-1)

  • I_light: light source intensity

  • N: surface normal (unit)

  • L: direction to light (unit)

• Note: (N·L) must be >0; else 0.

2. Specular Reflection

• Mirror-like reflection. Intensity depends on view direction.

• Phong Model: I_specular = k_s * I_light * (R·V)^n

  • k_s: specular coefficient

  • R: reflection of L about N (R = 2(N·L)N - L)

  • V: direction to viewer (unit)

  • n: shininess exponent (higher → smaller highlight)

• Alternative: (N·H)^n where H = (L+V)/|L+V| (halfway vector).

Shading Models

Color Models

[!TIP] Exam Focus: Differentiate parallel vs. perspective with diagram. Phong vs. Gouraud shading comparison is common. Z-buffer algorithm steps must be memorized.

VI. Multimedia Systems

Introduction to Multimedia

• Definition: Integration of multiple media types (text, graphics, audio, video, animation) in a computer-controlled interactive environment.

• Applications:

  • Education (e-learning, simulations)

  • Entertainment (games, VR)

  • Business (presentations, web, advertising)

  • Medicine (imaging, telemedicine)

  • Engineering (CAD, visualization)

Multimedia System Architecture (Detailed)

Five-Layer Model:

1. Capture/Production Layer: Input devices (scanner, mic, camera), authoring tools.

2. Storage Layer: Multimedia databases, file systems (RAID, NAS), compression storage.

3. Processing Layer: CPU/GPU, codecs (compression/decompression), rendering engines.

4. Network Layer: Transmission (streaming protocols: RTP/RTCP, RTSP), QoS management.

5. Presentation Layer: Output devices (display, speakers), synchronization, user interface.

Key Challenges:

• High data rates (especially video/audio).

• Storage requirements (uncompressed video: ~1.5 Gbps for HD).

• Real-time delivery (audio/video need constant rate).

• Synchronization (lip-sync, timeline).

• Interoperability (standards: MPEG, JPEG).

Multimedia Databases

• Purpose: Store, manage, retrieve large volumes of multimedia data (images, video, audio).

• Challenges:

  • Content-based retrieval (query by example, color, shape, motion).

  • Metadata management (descriptive, structural, administrative).

  • High storage & bandwidth.

  • Indexing high-dimensional feature vectors.

• Techniques:

  • Feature extraction (color histograms, texture, shape descriptors).

  • Similarity measures (Euclidean, Mahalanobis).

  • Multidimensional indexing (R-trees, k-d trees).

Multimedia File Formats & Standards

Compression Techniques

Lossless Compression

• Principle: Original data can be exactly reconstructed.

• Algorithms:

  • Run-Length Encoding (RLE): Good for simple graphics (BMP, PCX).

  • Huffman Coding: Variable-length codes based on symbol frequency.

  • LZW (Lempel-Ziv-Welch): Dictionary-based (GIF, TIFF).

  • Arithmetic Coding: More efficient than Huffman (JPEG, H.264).

• Use Case: Text, executable files, medical images, where fidelity is critical.

• Compression Ratio: Typically 2:1 to 5:1.

Lossy Compression

• Principle: Irreversible; removes perceptually less important data.

• Algorithms:

  • Transform Coding: DCT (JPEG, MPEG), Wavelet (JPEG2000).

  • Predictive Coding: DPCM (difference encoding).

  • Motion Compensation (video): Exploit temporal redundancy (MPEG).

• Use Case: Images, audio, video where slight loss acceptable.

• Compression Ratio: 10:1 to 100:1 (video up to 200:1).

• Standards:

  • JPEG: Still images, DCT-based, lossy.

  • MPEG-1/2/4: Video with audio, inter-frame prediction.

  • H.26x: Video conferencing (H.261, H.263, H.264/AVC, H.265/HEVC).

Animation

• Definition: Technique of creating illusion of motion by displaying sequence of still images (frames) rapidly (typically 24-60 fps).

• Principles of Animation (12 principles by Disney):

  1. Squash and stretch

  2. Anticipation

  3. Staging

  4. Straight ahead action & pose to pose

  5. Follow through & overlapping action

  6. Slow in & slow out

  7. Arcs

  8. Secondary action

  9. Timing

  10. Exaggeration

  11. Solid drawing

  12. Appeal

Evolving Technologies for Multimedia

• Cloud Computing: On-demand storage/processing (AWS, Azure). Enables scalable streaming, collaborative editing.

• AI/ML: Content analysis (object detection in video, speech recognition), generative (deepfakes, AI art), recommendation systems.

• VR/AR/MR: Immersive multimedia. VR (fully virtual), AR (overlay on real world), MR (interactive blend).

• 5G/6G: High bandwidth, low latency for real-time streaming, cloud gaming.

• IoT: Multimedia from sensors (cameras, mics) for smart environments.

• Blockchain: Rights management, provenance for digital media.

Visualization

• Definition: Use of computer-generated images/animations to represent abstract data for understanding.

• Applications:

  • Scientific: Weather, fluid dynamics, molecular structures.

  • Engineering: Finite element analysis, CFD.

  • Medical: MRI/CT scan 3D reconstruction.

  • Business: Financial trends, social networks.

  • Information: Hierarchical data (tree maps), networks (graph viz).

• High-Dimension Data Visualization:

  • Parallel Coordinates: Each dimension = vertical axis, data points = polylines.

  • Scatterplot Matrix: Pairwise scatterplots of all dimensions.

  • Dimensionality Reduction: PCA (Principal Component Analysis), t-SNE, UMAP → project to 2D/3D.

  • Glyphs/Stars: Each dimension represented by ray length/angle.

  • Hyperbox/Boxplot extensions.

Authoring Tools

• Definition: Software for creating multimedia applications without low-level programming.

• Types:

  • Presentation-based: PowerPoint, Keynote (linear slides).

  • Icon-based/Storyboard: Authorware, Director (visual flow).

  • Time-based: Flash (timeline animation), Video editors (Premiere, DaVinci).

  • Page-based: ToolBook (book metaphor).

  • Programming-based: Unity, Unreal Engine (game dev), HTML5/JavaScript (web).

• Features: Media import, timeline, interactivity (buttons, triggers), scripting, publishing to multiple formats.

[!TIP] Exam Focus: Multimedia architecture layers must be explained with examples. Compression: know JPEG (DCT) vs. MPEG (motion compensation) difference. Visualization: parallel coordinates and PCA for high-dim data. Authoring tools: distinguish types with examples.

VII. Additional Short Note Topics (Integrated Above)

• CRT: Covered under Display Systems (Section I).

• B-spline Curve: Covered under Curves (Section II).

• Reflection/Shading: Covered under 3D Rendering (Section V).

• Authoring Tools: Covered under Multimedia Systems (Section VI).

• Painter's Algorithm: Covered under Hidden Surface Removal (Section V).

• Viewing Transformation: Covered under Geometric Transformations (Section III).

• High-Dimension Data Visualization: Covered under Visualization (Section VI).

• Applications of Visualization: Covered under Visualization (Section VI).

Final Exam Strategy:

1. For 7-mark questions: Always include definition, working/algorithm steps, example/diagram, advantages/disadvantages where applicable.

2. For 3-4 mark short notes: Be concise: 1-2 sentence definition + 3-4 key points.

3. Diagrams: For raster/random scan, DVST, CRT, projections, clipping windows, shading models – draw neat labeled diagrams if asked.

4. Formulas: Memorize key ones: Bresenham's p, Midpoint Circle p, Bézier cubic, Reflection I_diffuse, I_specular.

5. Comparisons: Always use tables for parallel vs. perspective, lossless vs. lossy, Gouraud vs. Phong.

\boxed{\text{Revise all worked examples from past papers (especially Cohen-Sutherland, Bresenham's, Midpoint Circle, Rotation about arbitrary point).}}