Computer Graphics & Multimedia (IT-601) - Unit 2 Short Notes

I. Display Systems & Input Hardware

Raster Scan vs. Random Scan Displays

Block Diagram (Raster Scan):

DiagramCANVAS: Show CRT, display controller, frame buffer, video amplifier, and deflection yoke. Arrow from frame buffer to CRT via controller/amplifier.

Direct View Storage Tube (DVST)

• Working: Uses a storage mesh (charged wire grid) behind phosphor. A write gun draws vectors, altering charge on mesh. A flood gun constantly illuminates entire screen; only charged areas (from write gun) glow. No refresh needed.

• Advantages: No flicker, no frame buffer needed (cheap), high resolution.

• Limitations: Cannot erase/alter individual lines easily (requires full erase), no color, no animation.

Cathode Ray Tube (CRT)

• Basic Construction: Electron gun (cathode, control grid, focusing anode) → Deflection system (magnetic/electrostatic) → Phosphor-coated screen.

• Operation: Heated cathode emits electrons. Grid controls beam intensity. Anodes focus/accelerate beam. Deflection coils/plates steer beam to specific (x,y) on screen, exciting phosphor to emit light.

Interactive Input Devices

Input Techniques

• Rubber Band Technique: While dragging (e.g., to draw a line), a temporary line from fixed start point to current cursor position is displayed, "stretching" like a rubber band.

• Positioning & Constraint: Constrain cursor to horizontal/vertical lines (45° increments) or specific grid points for precise placement.

II. Primitive Generation Algorithms

Line Drawing Algorithms

• DDA (Digital Differential Analyzer):

$$dx = x_2 - x_1, \quad dy = y_2 - y_1$$

$$steps = \max(|dx|, |dy|)$$

$$x_{inc} = dx/steps, \quad y_{inc} = dy/steps$$

Plot `(round(x), round(y))` starting from `(x1, y1)` and incrementing by `(x_inc, y_inc)` for `steps`.

*   *Example:* Line (1,1) to (5,5): `dx=4, dy=4, steps=4, x_inc=y_inc=1`. Points: (1,1), (2,2), (3,3), (4,4), (5,5).

*   **Drawback:** Uses floating-point; rounding errors accumulate.

• Bresenham's Line Algorithm (for |m| ≤ 1):

  • Decision Parameter: $$\displaystyle p_k = 2dy \cdot y_k - 2dx \cdot x_k + c $$

  • Initial: $$\displaystyle p_0 = 2dy - dx $$

  • Update:

    • If $$\displaystyle p_k < 0 $$: $$\displaystyle p_{k+1} = p_k + 2dy $$ (E: move East)

    • If $$\displaystyle p_k \geq 0 $$: $$\displaystyle p_{k+1} = p_k + 2dy - 2dx $$ (NE: move North-East)

  • Advantages: Only integer arithmetic; fast; no rounding error accumulation.

Circle Drawing: Midpoint Circle Algorithm

• For radius r, center (x_c, y_c): Start (0, r). Decision parameter $$\displaystyle p_0 = 1 - r $$.

• Update (for x from 0 to y):

  • If $$\displaystyle p_k < 0 $$: $$\displaystyle p_{k+1} = p_k + 2x + 3 $$

  • If $$\displaystyle p_k \geq 0 $$: $$\displaystyle p_{k+1} = p_k + 2(x-y) + 5 $$; decrement y.

• Plot 8 symmetric points per calculated (x,y).

• Example (r=5):

  DiagramCANVAS: Show step-by-step table for r=5: k, x, y, p_k, next p. Final points: (0,5),(1,5),(2,5),(3,4),(4,3),(5,0) and symmetries.

Curve Representation

• Bezier Curve (Degree n, n+1 control points):

  • Definition: Parametric polynomial curve $$\displaystyle P(t) = \sum_{i=0}^{n} B_{i,n}(t) P_i $$, $0 \leq t \leq 1$.

  • Bernstein Basis: $$\displaystyle B_{i,n}(t) = \binom{n}{i} t^i (1-t)^{n-i} $$.

  • Properties: Interpolates endpoints ($$\displaystyle P(0)=P_0, P(1)=P_n $$), convex hull property, variation diminishing.

  • Midpoint (t=0.5): For cubic (4 points): $$\displaystyle M = \frac{1}{8}(P_0 + 3P_1 + 3P_2 + P_3) $$.

  • Example: Given P0(2,1), P1(3,2), P2(5,0), P3(6,2). Cubic Bezier.

    $$\displaystyle P(0.5) = \frac{1}{8}[(2,1) + 3(3,2) + 3(5,0) + (6,2)] = \frac{1}{8}(2+9+15+6, 1+6+0+2) = \frac{1}{8}(32,9) = (4, 1.125) $$.

• B-spline Curves:

  • Definition: Piecewise polynomial curve defined by control points and knot vector. Degree p (order p+1).

  • Basis Functions (Cox-de Boor): Recursive definition. Non-zero over limited interval (local control).

  • Key Differences from Bezier:

    | Bezier | B-spline | | :--- | :--- | | Interpolates endpoints | Generally does not interpolate endpoints | | Global control (move one point affects entire curve) | Local control (move point affects only nearby segments) | | Curve lies within convex hull of all control points | Curve lies within convex hull of few nearby control points |

III. Geometric Transformations & Projections

2D/3D Transformations (Matrix Form)

• Translation (2D): $$\displaystyle P' = P + T = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} $$

• Scaling (2D): $$\displaystyle P' = S \cdot P = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} $$

• Rotation about Origin (2D, θ CCW): $$\displaystyle P' = R \cdot P = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} $$

• Rotation about Arbitrary Point (x_r, y_r): $$\displaystyle P' = T(x_r,y_r) \cdot R(\theta) \cdot T(-x_r,-y_r) \cdot P $$

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

    • About origin: Apply R(45°) matrix to each point.

    • About P(-2,-2): Translate by T(2,2), rotate by 45°, translate back by T(-2,-2).

Viewing Transformation Pipeline

World Coordinates → Modeling Transformation → Viewing Coordinates (Eye at origin, looking down -Z) → Projection Transformation → Projection Coordinates → Viewport Transformation → Device Coordinates.

Projection Techniques

IV. Clipping & Hidden Surface Removal

Line Clipping: Cohen-Sutherland Algorithm

• Region Codes: 4-bit code for 9 regions around window. Bits: Top, Bottom, Right, Left.

  
  Top:    1000
  
  Bottom: 0100
  
  Right:  0010
  
  Left:   0001
  
  Inside: 0000
  
  

• Steps:

  1. Assign codes to endpoints.

  2. If both codes 0000 → accept.

  3. If AND of codes ≠ 0000 → reject (trivial reject).

  4. Else, clip against an edge where code differs. Repeat.

• Example (Window: P(0,0), Q(340,340). Line AB[(-170,595),(170,255)]):

  • A(-170,595): Top & Left → 1001. B(170,255): Inside → 0000. AND ≠ 0? 1001 & 0000 = 0000 → not trivial reject.

  • Clip against Top edge (y=340). Find intersection: $$\displaystyle y = 340, x = x_1 + (340-y_1)(x_2-x_1)/(y_2-y_1) = -170 + (340-595)(340)/(255-595) = 85 $$. New point A1(85,340) → code 0000. Segment A1B fully inside → visible.

Cyrus-Beck Algorithm (Parametric Line Clipping)

• Principle: For a convex polygon clipping window, represent line parametrically: $$\displaystyle P(t) = P_0 + t(P_1 - P_0), 0 \leq t \leq 1 $$.

• For each edge $i$ with inward normal $$\displaystyle \vec{n_i} $$ and a point $$\displaystyle P_{ei} $$ on edge:

$$t_i = \frac{(P_{ei} - P_0) \cdot \vec{n_i}}{(P_1 - P_0) \cdot \vec{n_i}}$$

• Entering/Leaving: Denominator $$\displaystyle < 0 $$ → entering ($$\displaystyle t_E = \max $$ of such $$\displaystyle t_i $$). Denominator $$\displaystyle > 0 $$ → leaving ($$\displaystyle t_L = \min $$ of such $$\displaystyle t_i $$).

• Visible if: $$\displaystyle t_E < t_L $$ and $$\displaystyle 0 \leq t_E \leq 1 $$, $$\displaystyle 0 \leq t_L \leq 1 $$. Clipped segment: $$\displaystyle P(t_E) $$ to $$\displaystyle P(t_L) $$.

• For Polygon Clipping: Clip each polygon edge against all window edges using same principle.

Polygon Clipping: Painter's Algorithm

• Concept: Sort polygon surfaces by depth (z-coordinate of farthest point). Draw farthest first, closest last (like a painter).

• Steps:

  1. Compute depth (max z) for each polygon.

  2. Sort in decreasing depth.

  3. Draw in order.

• Limitations: Fails for cyclic overlap (A overlaps B, B overlaps C, C overlaps A). Requires polygons to be convex and non-overlapping in x-y after depth sort.

Hidden Surface Removal

• Back Face Detection:

  • Concept: For convex polyhedra, a face is back-facing if its normal $\vec{N}$ points away from viewer.

  • V·N Test: Compute $$\displaystyle \vec{V} = \text{eye} - \text{any point on face} $$. If $$\displaystyle \vec{V} \cdot \vec{N} > 0 $$ (angle < 90°), face is front-facing (visible). If $$\displaystyle \vec{V} \cdot \vec{N} < 0 $$, it's back-facing (remove).

  • Application: Simple, fast, but only for closed convex objects.

• Z-Buffer (Depth Buffer) Algorithm:

  • Data Structures: Depth Buffer[z][x] (initialized to ∞), Frame Buffer[x][y] (color).

  • For each polygon:

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

    1. Compute depth $z$.

    2. If $$\displaystyle z < DepthBuffer[x][y] $$: set DepthBuffer[x][y] = z, FrameBuffer[x][y] = polygon's color.

  • Advantages: Simple, handles arbitrary polygons, works in image space.

  • Drawbacks: Requires extra memory for depth buffer. No transparency. Can have z-fighting for nearly coplanar surfaces.

V. Shading, Reflection & Color Models

Reflection Models

• Diffuse Reflection (Lambertian):

$$I_d = I_l \cdot k_d \cdot (\vec{L} \cdot \vec{N})$$

Where $$\displaystyle I_l $$ = light intensity, $$\displaystyle k_d $$ = diffuse coefficient, $\vec{L}$ = unit vector to light, $\vec{N}$ = unit normal. **Lambert's Cosine Law:** Intensity ∝ $$\displaystyle \cos\theta = \vec{L}\cdot\vec{N} $$. Appears equally bright from all viewing angles.

• Specular Reflection (Phong Model):

$$I_s = I_l \cdot k_s \cdot (\vec{R} \cdot \vec{V})^n$$

Where $\vec{R}$ = reflection of $\vec{L}$ about $\vec{N}$, $\vec{V}$ = unit vector to viewer, $$\displaystyle k_s $$ = specular coefficient, $n$ = **shininess exponent** (higher = sharper highlight).

*   **Alternative (Blinn-Phong):** Uses half-vector $$\displaystyle \vec{H} = (\vec{L}+\vec{V})/|\vec{L}+\vec{V}| $$: $$\displaystyle I_s \propto (\vec{N}\cdot\vec{H})^n $$. Faster to compute.

Shading Techniques

Color Models

VI. Multimedia Systems & Components

Multimedia Fundamentals

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

• Characteristics: High volume, temporal (time-dependent), diverse formats, real-time requirements.

• Applications: Education (e-learning), Entertainment (games, movies), Medicine (surgery simulation), Business (presentations, web).

Multimedia System Architecture (Layered)

┌─────────────────────────────────────┐

│     Presentation & Application       │ ← Authoring Tools, Players

├─────────────────────────────────────┤

│        Integration & Synchronization│ ← SMIL, MPEG-4 BIFS

├─────────────────────────────────────┤

│          Storage & Retrieval         │ ← File Systems, DBMS

├─────────────────────────────────────┤

│      Capture & Generation            │ ← Scanners, Microphones, Cameras

├─────────────────────────────────────┤

│   Physical Hardware & OS            │ ← CPU, GPU, Storage, I/O

└─────────────────────────────────────┘

• Hardware: High-speed CPU/GPU, large RAM/Storage, specialized I/O (sound card, video capture).

• Software: OS with real-time support, drivers, codecs, authoring tools, DBMS for multimedia.

Multimedia Databases

• Need: Store/retrieve large volumes of non-traditional data (images, video, audio) with content-based queries (e.g., "find all images with red cars").

• Challenges:

  • Content-based retrieval: Requires feature extraction (color histograms, texture, shape).

  • Temporal data: Video/audio have timing constraints.

  • Huge size: Terabytes of data.

  • Diverse formats: Need conversion/standardization.

• Data Models & Indexing: Object-relational models with BLOB support. Indexing: R-trees (spatial), k-d trees (feature vectors), MARS (Multimedia Analysis and Retrieval System).

Multimedia File Formats & Standards

• Image:

  • JPEG: Lossy DCT-based. Good for photos. .jpg

  • PNG: Lossless, supports transparency. .png

  • GIF: Lossless, limited 256 colors, supports animation. .gif

  • BMP: Uncompressed, large size. .bmp

• Audio:

  • WAV: Uncompressed PCM. Large, high quality.

  • MP3: Lossy (psychoacoustics), high compression. .mp3

  • MIDI: Not audio; control messages for synthesizers. Tiny size. .mid

• Video:

  • AVI: Container; audio/video interleaved. .avi

  • MPEG (MPEG-1/2/4): Standards with temporal (inter-frame) & spatial (DCT) compression. .mpg, .mp4

  • MOV: QuickTime container. .mov

Evolving Technologies

• VR (Virtual Reality): Fully immersive, computer-generated environment (HMD, gloves).

• AR (Augmented Reality): Overlays digital info on real world (smartphone, HoloLens).

• 360° Video: Spherical video; user looks around.

• Holography: Records light field; 3D view without glasses.

• Immersive Media: Combines VR/AR/360° for presence.

Compression Techniques

• Lossless: Exact reconstruction (PNG, ZIP, FLAC). Uses entropy coding (Huffman, Arithmetic).

• Lossy: Approximate reconstruction; higher compression. Exploits perceptual redundancy.

  • JPEG (Image): 1) Color space conversion (RGB→YCbCr), 2) DCT on 8x8 blocks, 3) Quantization (lossy), 4) Huffman coding.

  • MPEG (Video): Temporal redundancy removal via motion estimation/compensation (I, P, B frames). Spatial via DCT.

  • Audio (MP3): Psychoacoustics: Masking (simultaneous, temporal). Sub-band coding, MDCT, quantization.

Animation

• Definition: Illusion of motion by displaying sequence of still frames (≥ 12 fps).

• Types: 2D (vector/bitmap), 3D (keyframe, motion capture), Motion Graphics.

• 12 Principles of Animation (Disney):

  1. Squash & Stretch

  2. Anticipation

  3. Staging

  4. Straight Ahead & Pose to Pose

  5. Follow Through & Overlapping Action

  6. Slow In & Slow Out

  7. Arc

  8. Secondary Action

  9. Timing

  10. Exaggeration

  11. Solid Drawing

  12. Appeal

VII. Data Visualization

High Dimensional Data

• Challenges: Human perception limited to 3D. Curse of dimensionality (sparsity, distance metrics).

• Techniques:

  • Parallel Coordinates: Each dimension = vertical axis; data point = polyline across axes.

  • Scatterplot Matrix: Grid of 2D scatterplots for all dimension pairs.

  • Dimensionality Reduction:

    • PCA (Principal Component Analysis): Linear projection to maximize variance.

    • t-SNE: Non-linear, preserves local structure (good for clusters).

    • UMAP: Similar to t-SNE, faster, preserves more global structure.

Applications of Visualization

• Scientific: Climate models, fluid dynamics.

• Engineering: Finite element analysis, stress visualization.

• Business Intelligence: Dashboards, sales trends, geospatial.

• Medical Imaging: MRI/CT slice visualization, 3D reconstruction.

VIII. Authoring Tools

• Definition: Software to create multimedia presentations without low-level programming. Integrates media, sets timing, defines interactivity.

• Types & Examples:

  | Type | Principle | Example | | :--- | :--- | :--- | | Timeline-based | Media placed on tracks; timing via timeline. | Adobe Flash/Animate, Premiere. | | Icon-based/Flowchart | Visual flow of events/icons. | Authorware, Director (Lingo). | | Card/Page-based | Navigation between pages/cards. | HyperCard, ToolBook. | | Object-based | Focus on objects with behaviors/scripts. | Director (modern), Unity (game engine). |

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