UNIT 1: Computer Graphics & Multimedia

I. Display Systems & Color Models

Raster Scan vs. Random Scan Displays

Cathode Ray Tube (CRT)

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

• Components: Electron gun (cathode, control grid, focusing anode), deflection yoke, phosphor screen, shadow mask (color CRT).

• Refresh: Persistence of phosphor requires periodic redrawing.

[!TIP] CRT is an analog device; modern displays (LCD, LED) are digital and don't use electron beams.

Direct View Storage Tube (DVST)

• Principle: Stores image as charge pattern on a special mesh; beam only refreshes stored pattern, not redrawn.

• Advantages:

  • No frame buffer needed → cheaper.

  • No flicker (constant display).

  • High resolution possible.

• Disadvantages:

  • Cannot modify stored image easily (selective erase difficult).

  • No animation or dynamic updates.

  • No color (typically monochrome).

  • Low brightness compared to CRT.

[!TIP] DVST is obsolete; replaced by raster systems with frame buffers.

Color Models

• Conversion Example (RGB to HSV):

$$ H = \cos^{-1} \left( \frac{(R-G) + (R-B)}{2\sqrt{(R-G)^2 + (R-B)(G-B)}} \right) $$

$$ S = \frac{\max(R,G,B) - \min(R,G,B)}{\max(R,G,B)} $$

$$ V = \max(R,G,B) $$

II. Input Devices & Interaction Techniques

Interactive Input Devices

• Keyboard: Text input, command entry.

• Mouse: 2D position, buttons → cursor control, selection.

• Joystick: 2D/3D position, force feedback → gaming, navigation.

• Trackball: Stationary mouse alternative → ergonomic.

• Touch Screen: Direct touch input → smartphones, kiosks.

• Light Pen: Detects electron beam → direct screen drawing (historical).

• Digitizer: Tablet + stylus → precise 2D input (CAD).

• Scanner: Converts physical image to digital.

• Microphone: Audio input.

• 3D Input: Spaceball (6-DOF), data glove.

Rubber Band Techniques

• Concept: Visual feedback during interactive drawing/positioning.

• Example: Dragging a rectangle: as mouse moves, a temporary "rubber band" rectangle stretches from start point to current cursor, updating in real-time.

• Implementation: Use XOR drawing (old) or double buffering (modern) to draw temporary shape without disturbing underlying image.

[!TIP] Rubber banding provides immediate visual feedback; essential for GUI widgets (selection boxes, sliders).

III. Fundamental Drawing Algorithms

Line Drawing Algorithms

DDA (Digital Differential Analyzer)

• Principle: Use line equation $$\displaystyle y = mx + c $$. For each $x$, compute $y$.

• Algorithm:

  1. Calculate $$\displaystyle dx = x_2 - x_1 $$, $$\displaystyle dy = y_2 - y_1 $$.

  2. Determine steps: $$\displaystyle N = \max(|dx|, |dy|) $$.

  3. $$\displaystyle x_{inc} = dx/N $$, $$\displaystyle y_{inc} = dy/N $$.

  4. Start at $$\displaystyle (x_1, y_1) $$, increment by $$\displaystyle (x_{inc}, y_{inc}) $$ for $N$ steps, rounding to nearest pixel.

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

  $$\displaystyle dx=4, dy=4, N=4, x_{inc}=1, y_{inc}=1 $$ → pixels: (1,1), (2,2), (3,3), (4,4), (5,5).

• Drawback: Uses floating-point, rounding errors accumulate.

Bresenham's Line Algorithm

• Principle: Uses integer arithmetic; decision parameter based on error term.

• For $$\displaystyle |m| < 1 $$ (mild slope):

  • $$\displaystyle d = 2dy - dx $$ (initial decision parameter).

  • For each $x$:

    • If $$\displaystyle d < 0 $$: $x++$, $$\displaystyle d += 2dy $$ (E move).

    • Else: $x++, y++$, $$\displaystyle d += 2(dy - dx) $$ (NE move).

• Example: Line (0,0) to (5,3):

  $$\displaystyle dx=5, dy=3, d=2*3-5=1 $$.

  Steps: (0,0) d=1→NE→(1,1) d=-1→E→(2,1) d=1→NE→(3,2) d=-1→E→(4,2) d=1→NE→(5,3).

• Advantage: Only integer additions/subtractions; fast.

Circle Drawing: Midpoint Circle Algorithm

• Principle: Exploit 8-way symmetry; compute points for 1/8th circle.

• Decision parameter: $$\displaystyle P_k = d_{lower} + d_{upper} $$ at midpoint.

• Algorithm (radius $r$, center $$\displaystyle (x_c,y_c) $$):

  1. $$\displaystyle x=0, y=r, P_0 = 1 - r $$.

  2. While $$\displaystyle x < y $$:

     • Plot 8 symmetric points.

     • If $$\displaystyle P_k < 0 $$: $x++$, $$\displaystyle P_{k+1} = P_k + 2x + 3 $$.

     • Else: $x++, y--$, $$\displaystyle P_{k+1} = P_k + 2(x-y) + 5 $$.

• Example: $$\displaystyle r=5 $$ → points: (0,5), (1,5), (2,5), (3,4), (4,3), (5,0) in first octave.

Curve Drawing

Bezier Curves

• Definition: Parametric polynomial curve defined by control points.

• Linear: $$\displaystyle B(t) = (1-t)P_0 + tP_1 $$.

• Quadratic: $$\displaystyle B(t) = (1-t)^2P_0 + 2(1-t)tP_1 + t^2P_2 $$.

• Cubic: $$\displaystyle B(t) = (1-t)^3P_0 + 3(1-t)^2tP_1 + 3(1-t)t^2P_2 + t^3P_3 $$, $t \in [0,1]$.

• Properties:

  • Convex hull: Curve lies within convex hull of control points.

  • Endpoint interpolation: $$\displaystyle B(0)=P_0 $$, $$\displaystyle B(1)=P_n $$.

  • Variation diminishing: Curve doesn't oscillate more than control polygon.

  • Geometric invariance: Under affine transformations, transform control points.

• Midpoint: $B(0.5)$ gives midpoint.

• Example: Control points (2,1), (3,2), (5,0), (6,2). Cubic Bezier:

  $$\displaystyle B(t) = (1-t)^3(2,1) + 3(1-t)^2t(3,2) + 3(1-t)t^2(5,0) + t^3(6,2) $$.

  Midpoint $$\displaystyle t=0.5 $$: $$\displaystyle B(0.5) = (4.125, 1.375) $$.

B-spline Curves

• Definition: Piecewise polynomial curve with local control (moving one control point affects only nearby curve segments).

• Degree $k$: $k+1$ control points per segment.

• Uniform B-spline (knots equally spaced):

  • Cubic ($$\displaystyle k=3 $$) most common.

  • C² continuity (second derivative continuous).

  • Curve lies within convex hull of control points.

  • Does not necessarily pass through endpoints (unlike Bezier).

• Basis functions: Defined recursively (Cox-de Boor).

• Advantage over Bezier: Local control, smoother for many points.

IV. 2D & 3D Transformations

2D Transformations (Homogeneous Coordinates)

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

Rotation about Arbitrary Point $$\displaystyle (x_r, y_r) $$

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

2. Rotate: $R(\theta)$.

3. Translate back: $$\displaystyle T(x_r, y_r) $$.

• Composite: $$\displaystyle M = T(x_r,y_r) \cdot R(\theta) \cdot T(-x_r,-y_r) $$.

Viewing Transformation

• Window (world coordinates) → Viewport (device coordinates).

• Steps:

  1. Modeling transformation: Define object in world coordinates.

  2. View transformation: Place camera (viewpoint, view direction, up vector).

  3. Projection transformation: 3D→2D (parallel/perspective).

  4. Workstation transformation: Normalize to viewport.

• Window-to-Viewport mapping (2D):

$$ x_{vp} = x_{min}^{vp} + \frac{(x_w - x_{min}^w)}{(x_{max}^w - x_{min}^w)} \cdot (x_{max}^{vp} - x_{min}^{vp}) $$

$$ y_{vp} = y_{min}^{vp} + \frac{(y_w - y_{min}^w)}{(y_{max}^w - y_{min}^w)} \cdot (y_{max}^{vp} - y_{min}^{vp}) $$

where $w$=window, $vp$=viewport.

V. Clipping

Cohen-Sutherland Line Clipping

• Region Codes: 4-bit code for each endpoint based on window boundaries (left, right, bottom, top).

  • Bit 1: left, 2: right, 3: below, 4: above.

• Algorithm:

  1. Compute region codes $$\displaystyle C_1, C_2 $$ for endpoints.

  2. Trivial accept: $$\displaystyle C_1 = C_2 = 0 $$ → line entirely inside.

  3. Trivial reject: $$\displaystyle C_1 \& C_2 \neq 0 $$ → line entirely outside.

  4. Else: Clip against one window edge where code differs.

     • Find intersection with boundary (parametric line equation).

     • Replace endpoint outside with intersection point.

     • Recompute code, repeat.

• Example: Window $P(0,0), Q(340,0), R(340,340), S(0,340)$.

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

  • $$\displaystyle C_A $$: above → 1000 (binary), $$\displaystyle C_B $$: inside → 0000.

  • Not trivial accept/reject. Clip against top edge ($$\displaystyle y=340 $$).

  Parametric: $$\displaystyle x = -170 + 340t $$, $$\displaystyle y = 595 - 340t $$. Set $$\displaystyle y=340 $$ → $$\displaystyle t=0.75 $$, $$\displaystyle x=85 $$.

  New point $A'(85,340)$. Recompute: inside → 0000. Now both inside → accept segment $A'B$.

  Similarly for CD: $C(425,85)$, $D(595,595)$.

  • $$\displaystyle C_C $$: right → 0010, $$\displaystyle C_D $$: right+above → 1010 → reject (common bit 0010).

  Entirely outside.

Cyrus-Beck Parametric Clipping (Polygons)

• Principle: Parametric line form $$\displaystyle P(t) = P_0 + t(P_1 - P_0) $$, $t \in [0,1]$.

• For convex polygon with inward normals $$\displaystyle \mathbf{n}_i $$:

  • For each edge $i$: compute $$\displaystyle t_i = \frac{(\mathbf{p}_i - P_0) \cdot \mathbf{n}_i}{(P_1 - P_0) \cdot \mathbf{n}_i} $$.

  • If $$\displaystyle (P_1 - P_0) \cdot \mathbf{n}_i < 0 $$ → potential entering point ($$\displaystyle t_E = \max(t_i) $$).

  • If $$\displaystyle (P_1 - P_0) \cdot \mathbf{n}_i > 0 $$ → potential leaving point ($$\displaystyle t_L = \min(t_i) $$).

• Accept if $$\displaystyle t_E < t_L $$; clipped segment $$\displaystyle P(t_E) $$ to $$\displaystyle P(t_L) $$.

• For polygons: Apply to each edge sequentially.

Other Line Clipping Approaches

[!TIP] Cohen-Sutherland is most common in exams; know region codes and iterative clipping steps.

VI. 3D Rendering, Projections & Hidden Surface Removal

Projections

Shading Models

• Diffuse Reflection (Lambertian):

  • Light scattered equally in all directions.

  • Intensity $$\displaystyle I = I_l \cdot k_d \cdot (\mathbf{L} \cdot \mathbf{N}) $$, where $\mathbf{L}$=light dir, $\mathbf{N}$=normal.

  • Independent of viewer position.

• Specular Reflection (Phong):

  • Mirror-like highlight.

  • Intensity $$\displaystyle I = I_l \cdot k_s \cdot (\mathbf{R} \cdot \mathbf{V})^n $$, where $\mathbf{R}$=reflection dir, $\mathbf{V}$=viewer dir, $n$=shininess.

  • Viewer-dependent; sharp highlight for high $n$.

• Phong Shading: Interpolate normals across polygon, compute color per pixel (smooth).

• Gouraud Shading: Interpolate colors across polygon (faster, but specular highlights may be lost).

Hidden Surface Removal

• Z-Buffer Algorithm:

  • Idea: For each pixel, store depth ($z$) of closest object.

  • Algorithm:

    1. Initialize depth buffer ($z$-buffer) to $\infty$, frame buffer to background.

    2. For each polygon:

       • Rasterize (scan conversion).

       • For each covered pixel $(x,y)$:

         • Compute depth $z$.

         • If $$\displaystyle z < z_{buffer}(x,y) $$: set $$\displaystyle z_{buffer}(x,y)=z $$, frame buffer $$\displaystyle (x,y)= $$ polygon color.

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

  • Pros: Simple, handles any polygon order.

  • Cons: Memory intensive (2 buffers), no transparency.

• Painter's Algorithm:

  • Sort polygons by average depth (far to near).

  • Draw in order (far first, near on top).

  • Fails for cyclic overlaps (A overlaps B, B overlaps C, C overlaps A).

• Back Face Detection:

  • For convex objects: remove faces with normal pointing away from viewer.

  • Compute $\mathbf{V} \cdot \mathbf{N}$ (view vector dot normal).

  • If $$\displaystyle > 0 $$ (assuming $\mathbf{N}$ outward, $\mathbf{V}$ toward viewer) → back face, don't draw.

  • Only works for single convex objects; not for scenes with overlapping objects.

VII. Multimedia Fundamentals

Definition & Characteristics

• Definition: Integration of text, graphics, audio, video, animation in an interactive digital environment.

• Characteristics:

  • Digital: Represented in binary.

  • Integrated: Multiple media types combined.

  • Interactive: User control.

  • Time-dependent: Audio/video have temporal constraints.

  • High bandwidth: Especially video/audio.

Multimedia System Architecture

Five key components:

1. Capture/Input: Devices (camera, mic, scanner).

2. Storage & Database: Large capacity, fast access (RAID, streaming).

3. Processing/Editing: CPU/GPU, software (editing tools).

4. Presentation/Output: Display, speakers, haptic devices.

5. Communication/Network: Bandwidth, QoS for streaming.

[!TIP] Multimedia databases must handle continuous media (streaming) → require real-time storage, indexing by content (e.g., color histogram), QoS guarantees.

Multimedia Databases

• Challenges:

  • Volume: High data rate (e.g., uncompressed video: 30 MB/s).

  • Variety: Different formats (JPEG, MP3, MPEG).

  • Temporal constraints: Synchronization (audio-video lip-sync).

  • Content-based retrieval: Query by example (QBE), feature extraction.

• Solutions:

  • Storage: RAID, compression, streaming servers.

  • Indexing: Multi-dimensional indexing (R-trees), metadata.

  • Synchronization: Timestamps, synchronization protocols.

File Formats & Standards

• Container formats: AVI, MP4 (store audio/video together).

Authoring Tools

• Purpose: Integrate media, define interaction, control timing.

• Types:

  • Presentation-based: PowerPoint, Keynote.

  • Time-based: Adobe Premiere, Final Cut Pro (video editing).

  • Event-based: Director, Flash (now obsolete), Unity (game engine).

  • Page-based: Dreamweaver (web).

• Features: Timeline, media library, scripting, hyperlinks.

VIII. Compression Techniques

Need for Compression

• Reduce storage space.

• Reduce transmission bandwidth.

• Enable real-time playback (especially video).

Lossless Compression

• Idea: Original data perfectly reconstructible.

• Methods:

  • Huffman Coding:

    • Variable-length codes based on symbol frequency.

    • Frequent symbols → short codes, infrequent → long codes.

    • Example: If 'a' appears 50%, 'b' 25%, 'c' 25% → codes: a=0, b=10, c=11.

    • Optimal for known probabilities.

  • Run-Length Encoding (RLE):

    • Replace consecutive identical symbols with (count, symbol).

    • Example: "AAAABBBCC" → (4,A)(3,B)(2,C).

    • Effective for simple graphics (BMP with large uniform areas).

• Formats: PNG (images), FLAC (audio), ZIP (general).

Lossy Compression

• Idea: Discard perceptually irrelevant data; irreversible.

• Methods:

  • JPEG (images):

    1. Color space conversion (RGB→YCbCr).

    2. Downsample chroma (4:2:0).

    3. Discrete Cosine Transform (DCT) on 8×8 blocks.

    4. Quantization (lossy step: divide by quantization table, round).

    5. Huffman encoding of quantized coefficients.

  • MPEG (video):

    • Exploits temporal redundancy (difference between frames).

    • I-frames (intra-coded, like JPEG).

    • P-frames (predictive from previous I/P).

    • B-frames (bidirectional, from past/future).

    • Motion estimation/compensation.

• Formats: JPEG, MP3, MPEG-1/2/4, H.264/265.

Compression Standards

• Images: JPEG (ISO/IEC 10918), JPEG 2000 (wavelet-based).

• Video: MPEG-1 (VCD), MPEG-2 (DVD), MPEG-4 (web), H.264/AVC (Blu-ray, streaming), H.265/HEVC (4K).

• Audio: MPEG-1 Audio (MP3), MPEG-2 AAC, Dolby Digital (AC-3).

IX. Animation

Definition

• Animation: Creating illusion of motion by displaying sequence of frames (still images) at sufficient rate (typically 24-60 fps).

Principles of Animation (Disney's 12 principles, key ones):

1. Squash and Stretch: Deform objects to show weight, flexibility.

2. Anticipation: Prepare for action (e.g., wind-up before throw).

3. Staging: Direct viewer's attention to important elements.

4. Straight Ahead vs. Pose-to-Pose: Drawing each frame sequentially vs. key frames then inbetweens.

5. Follow Through & Overlapping Action: Parts continue moving after main action stops.

6. Slow In & Slow Out (Ease In/Out): Acceleration/deceleration at motion extremes.

7. Arcs: Natural motion follows curved paths.

8. Timing: Spacing between frames conveys weight, emotion.

9. Exaggeration: Enhance actions for clarity/impact.

10. Solid Drawing: 3D form, weight, volume.

11. Appeal: Characters should be interesting.

12. Secondary Action: Supporting actions to enrich main action.

[!TIP] Squash and stretch and timing are most frequently asked.

X. Visualization & Evolving Technologies

High-Dimensional Data Visualization

• Challenge: Visualizing data with >3 dimensions.

• Techniques:

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

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

  • Dimensionality Reduction:

    • PCA (Principal Component Analysis): Project to 2D/3D preserving variance.

    • t-SNE: Nonlinear, preserves local structure.

    • UMAP: Similar to t-SNE, faster.

  • Glyphs (star plots, Chernoff faces): Encode multiple variables in shape/color.

  • Hyperdimensional widgets: Interactive brushing/linking across plots.

Applications of Visualization

• Scientific: Weather, fluid dynamics, molecular structures.

• Information: Web traffic, social networks, financial data.

• Medical: MRI/CT scans, surgical planning.

• Engineering: Finite element analysis, CAD.

• Business: Dashboards, sales trends.

Evolving Technologies for Multimedia

• Virtual Reality (VR):

  • Immersion: Fully synthetic environment via head-mounted display (HMD).

  • Interaction: Hand controllers, motion tracking.

  • Applications: Gaming, training, therapy.

• Augmented Reality (AR):

  • Overlay digital content on real world (via smartphone, HMD like HoloLens).

  • Applications: Navigation, maintenance, education.

• Mixed Reality (MR):

  • Blend real and virtual; virtual objects interact with real environment (occlusion, physics).

  • Example: Microsoft HoloLens.

• Extended Reality (XR): Umbrella term for VR/AR/MR.

• Other: 360° video, volumetric video, holography, AI-generated content (deepfakes, style transfer).

[!TIP] VR vs. AR: VR replaces reality; AR augments reality. MR allows interaction between real and virtual.