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

UNIT 3: COMPUTER GRAPHICS & MULTIMEDIA - EXAM-DRIVEN NOTES

I. DISPLAY SYSTEMS & INPUT DEVICES

A. Raster Scan vs. Random Scan (Vector) Displays

Block Diagram (Raster Scan): CPU → Display Controller → Frame Buffer (Memory) → Video Amplifier → CRT

B. Direct View Storage Tube (DVST)

• Working Principle: Uses a storage mesh (thin wire grid) behind phosphor coating. Electron beam writes image onto mesh, which retains charge pattern. A separate, low-power flood gun illuminates the entire screen, making the stored charge pattern glow. No refresh needed for static images.

• Diagram: [Write Gun] → [Storage Mesh] ← [Flood Gun] → [Phosphor]

• Advantages:

  • No frame buffer → Very high resolution (no pixel grid).

  • No flicker (static image).

  • Low cost (no high-speed memory).

• Disadvantages:

  • Cannot display dynamic/color graphics easily (erasing/modifying is slow).

  • No intensity variation (only on/off).

  • Overlay problem: New drawings must be carefully managed.

C. Interactive Input Devices

D. Interaction Techniques

• Rubber Band Technique: While dragging a mouse, a temporary line (like a stretched rubber band) is drawn from the starting point to the current cursor position. Used for interactive line drawing, rectangle selection, and positioning objects.

  • Example: To draw a line, click start point → drag (line follows cursor) → release at end point.

• Positioning Constraints: Forces cursor/object movement along specific paths.

  • Orthogonal Constraint: Cursor snaps to horizontal/vertical lines (e.g., Shift key in drawing apps).

  • Polar Constraint: Cursor snaps to specific angles (e.g., 30°, 45° increments).

II. FUNDAMENTAL DRAWING ALGORITHMS

A. Line Drawing Algorithms

1. DDA (Digital Differential Analyzer) Algorithm

• Concept: Uses floating-point arithmetic to incrementally plot points based on the line's slope.

• Equations:

  • If |dx| >= |dy| (slope ≤ 1): x_{i+1} = x_i + 1, y_{i+1} = y_i + m (where m = dy/dx)

  • If |dy| > |dx| (slope > 1): y_{i+1} = y_i + 1, x_{i+1} = x_i + (1/m)

• Steps:

  1. Calculate dx = x2 - x1, dy = y2 - y1.

  2. Determine number of steps N = max(|dx|, |dy|).

  3. Calculate increments x_inc = dx/N, y_inc = dy/N.

  4. Start at (x1, y1), round to nearest pixel, plot.

  5. For i=1 to N-1: x = x + x_inc, y = y + y_inc, plot (round(x), round(y)).

• Example (1,1) to (5,5): dx=4, dy=4, N=4, x_inc=1, y_inc=1. Points: (1,1), (2,2), (3,3), (4,4), (5,5).

2. Bresenham's Line Algorithm (for 0 < m < 1)

• Concept: Uses integer arithmetic only. Decision parameter p determines whether to move East (E) or North-East (NE).

• Derivation: Line equation: y = mx + c. For pixel at (x_i, y_i), decision variable p_i = dy * (x_i + 1) - dx * (y_i + 0.5). If p_i < 0, next pixel is E; else NE.

• Initialization: p_0 = 2*dy - dx.

• Algorithm Steps:

  1. Input endpoints, calculate dx, dy.

  2. p = 2*dy - dx.

  3. Plot initial point.

  4. For i=1 to dx:

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

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

     • Plot (x, y).

• Example (0,0) to (5,3): dx=5, dy=3, p0=1. Points: (0,0), (1,1), (2,1), (3,2), (4,2), (5,3).

B. Circle Drawing Algorithms

Midpoint Circle Algorithm

• Concept: Uses symmetry (8 octants). Decision parameter p at midpoint between candidate pixels.

• For Octant (x,y) where x <= y (0° to 45°):

  • Initial point: (0, r)

  • Initial decision: p_0 = 1 - r

• Algorithm Steps:

  1. x = 0, y = r, p = 1 - r.

  2. Plot 8 symmetric points.

  3. While x < y:

     • x = x + 1

     • If p < 0: p = p + 2*x + 1

     • Else: y = y - 1, p = p + 2*(x - y) + 1

     • Plot 8 symmetric points (±x, ±y), (±y, ±x).

• Example (Radius 5, Center Origin):

  • p0 = 1 - 5 = -4

  • Points: (0,5), (1,5), (2,5), (3,4), (4,3), (5,0) in first octant → reflect.

C. Curve Representations

Bezier Curves

• Bernstein Basis: Bezier curve of degree n with control points P_i is:

$$B(t) = \sum_{i=0}^{n} P_i \cdot B_{i,n}(t), \quad 0 \le t \le 1$$

where 

$$B_{i,n}(t) = \binom{n}{i} t^i (1-t)^{n-i}$$

• Geometric Interpretation: Weighted average of control points using Bernstein polynomials as weights.

• Properties:

  • Endpoint Interpolation: B(0)=P_0, B(1)=P_n.

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

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

  • Affine Invariance: Transformations applied to control points transform curve.

• Example (Cubic, 4 points): P0(2,1), P1(3,2), P2(5,0), P3(6,2)

  • B(t) = (1-t)^3 P0 + 3t(1-t)^2 P1 + 3t^2(1-t) P2 + t^3 P3

  • Calculate B(0.5) for midpoint.

  • Midpoint t=0.5: B(0.5) = 0.125*P0 + 0.375*P1 + 0.375*P2 + 0.125*P3 = (4.125, 1.125).

B-spline Curves (Short Note)

• Basis Functions (Cox-de Boor Recursion):

$$N_{i,0}(t) = \begin{cases} 1 & \text{if } t_i \le t < t_{i+1} \\ 0 & \text{otherwise} \end{cases}$$

$$N_{i,k}(t) = \frac{t - t_i}{t_{i+k} - t_i} N_{i,k-1}(t) + \frac{t_{i+k+1} - t}{t_{i+k+1} - t_{i+1}} N_{i+1,k-1}(t)$$

• Properties:

  • Local Control: Moving a control point affects only k+1 curve segments.

  • Smoothness: C^{k-1} continuity for degree k.

  • Degree: Curve degree is independent of number of control points (unlike Bezier).

• vs. Bezier: Bezier is global (all points affect entire curve). B-spline has local control and can represent more complex shapes without high degree.

III. GEOMETRIC TRANSFORMATIONS

A. 2D & 3D Transformations

• Use Homogeneous Coordinates (add w component) to represent translation as matrix multiplication.

  • 2D point (x,y) → (x, y, 1)

  • 3D point (x,y,z) → (x, y, z, 1)

• Transformation Matrices (3x3 for 2D, 4x4 for 3D):

  • Translation T(tx, ty):

$$\begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}$$

*   **Rotation** `R(θ)` (counter-clockwise about origin):

$$\begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

*   **Scaling** `S(sx, sy)`:

$$\begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

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

  • θ=45°, cosθ=sinθ=√2/2 ≈ 0.7071

  • B' = (2*0.7071 - 2*0.7071, 2*0.7071 + 2*0.7071) = (0, 2.828)

  • Similarly for A, C.

B. Viewing Transformation: Window-to-Viewport

• Concept: Map a portion of the world coordinate scene (defined by a window) to a device coordinate viewport (on screen/plotter).

• Mapping Equations (for x-coordinate):

$$x_{vp} = \left( \frac{x_w - x_{wmin}}{x_{wmax} - x_{wmin}} \right) \times (x_{vpmax} - x_{vpmin}) + x_{vpmin}$$

Same for `y`. This performs **scaling** (to fit aspect ratio) and **translation**.

• Process: World Coords → Window → Normalized Device Coords (0-1) → Viewport → Device Coords.

IV. CLIPPING

A. General Approaches

1. Exhaustive Testing: Test each point against all boundaries (inefficient).

2. Parametric: Represent line as P(t) = P1 + t(P2-P1), find t values where it crosses clipping boundaries.

3. Region-Based (Cohen-Sutherland): Divide space into regions, assign codes, use trivial accept/reject.

B. Cohen-Sutherland Line Clipping Algorithm

• Region Codes (Outcodes): 4-bit code for 9 regions (inside=0000).

  • Bit 1 (top), Bit 2 (bottom), Bit 3 (right), Bit 4 (left).

  • Example: Point left of window & above → 1001.

• Trivial Accept: Both endpoints have code 0000 → line entirely inside.

• Trivial Reject: Logical AND of endpoint codes ≠ 0000 → line entirely outside.

• Algorithm Steps:

  1. Assign region codes to endpoints P1, P2.

  2. While not trivially accepted/rejected:

     • Choose an endpoint with non-zero code.

     • Find edge of window that the point is outside.

     • Compute intersection P of line with that window edge.

     • Replace the outside endpoint with P, update its code.

  3. If accepted, draw line segment between final P1, P2.

• Example: Window [xmin=0, ymin=0, xmax=340, ymax=340].

  • Line AB[(-170,595),(170,255)]: A code=1001 (left+top), B code=0000. Reject? AND=0000 → not trivial reject. Clip A against top edge y=340 → new A'. Repeat.

  • Line CD[(425,85),(595,595)]: C code=0100 (right), D code=1001 (left+top). AND=0000 → not trivial reject. Clip C against right edge x=340 → C'. Clip D against top edge y=340 → D'. Result C'D' is visible.

• Advantages: Simple, fast for many trivial rejects.

• Limitations: Inefficient for lines completely inside but with one endpoint outside (multiple iterations). Only for rectangular windows.

C. Cyrus-Beck (Parametric) Algorithm

• Principle: For a convex polygon clipping window, represent line parametrically: P(t) = P1 + t(P2-P1), 0 ≤ t ≤ 1. Find t_enter and t_exit where line enters and leaves the polygon.

• For each edge i with inward normal n_i and vertex Pi:

$$t_i = \frac{(P_i - P1) \cdot n_i}{(P2 - P1) \cdot n_i}$$

*   If denominator `> 0`: `t` is potential **leaving** point (`t_exit = min(t_i)`).

*   If denominator `< 0`: `t` is potential **entering** point (`t_enter = max(t_i)`).

*   If denominator `= 0`: Line parallel to edge. Ignore if outside.

• Visible if: t_enter < t_exit and 0 ≤ t_enter ≤ 1, 0 ≤ t_exit ≤ 1. Visible segment: P(t_enter) to P(t_exit).

• Works for any convex polygon (not just rectangle).

D. Other Clipping Algorithms (Brief)

• Liang-Barsky: Parametric version optimized for rectangular windows. Uses 4 inequalities (for left, right, bottom, top) to compute t_enter, t_exit directly. More efficient than Cohen-Sutherland for non-trivial cases.

• Sutherland-Hodgman: For polygon clipping against a convex clipping window. Process polygon edges one clip boundary at a time. Outputs a polygon (may have more vertices).

V. PROJECTIONS

A. Parallel Projection

• Projectors are parallel (center of projection at infinity).

• Orthographic: Projectors perpendicular to projection plane.

  • Multi-view: Front, top, side (true dimensions).

  • Axonometric: Single view with rotation.

    • Isometric: Equal foreshortening (α=β=γ), angles 120°.

    • Dimetric: Two equal foreshortenings.

    • Trimetric: All foreshortenings different.

• Oblique: Projectors not perpendicular.

  • Cavalier: Projection vector makes 45° with plane. Foreshortening f=1.

  • Cabinet: Projection vector makes 45° with plane. Foreshortening f=0.5 (more realistic).

B. Perspective Projection

• Projectors converge at Center of Projection (COP) or "eye".

• Principle: x_p = x * (d/z), y_p = y * (d/z) where d is distance from COP to projection plane. Size varies with depth z.

• Types:

  • One-point: One set of parallel lines is perpendicular to view plane → one vanishing point.

  • Two-point: Two sets of parallel lines are oblique → two vanishing points.

  • Three-point: All three sets oblique → three vanishing points.

C. Detailed Comparison

VI. VISIBILITY & RENDERING

A. Hidden Surface Removal

1. Z-Buffer (Depth Buffer) Algorithm

• Principle: For each pixel on screen, store the closest depth (z-value) in a depth buffer and corresponding color in frame buffer.

• Algorithm:

  1. Initialize depth buffer to ∞ (or far plane), frame buffer to background.

  2. For each polygon in scene:

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

       • Compute polygon's depth z at (x,y).

       • If z < depth_buffer[x,y]:

         • depth_buffer[x,y] = z

         • frame_buffer[x,y] = polygon_color

• Advantages: Simple, handles any polygon order, works for transparent objects (with modifications).

• Disadvantages: Requires extra memory (2 buffers). Cannot handle fragile effects like correct order for intersecting polygons without extra passes.

2. Painter's Algorithm

• Principle: Sort polygons by average or farthest depth (back to front). Draw farthest first, closer ones paint over them.

• Challenges:

  • Cyclic Overlap: Polygons A overlaps B, B overlaps C, C overlaps A → impossible order.

  • Solution: Requires polygon splitting (complex).

• Use: Simple scenes, non-intersecting polygons.

3. Back-Face Detection (Removal)

• Principle: For a convex polyhedron (closed object), if the view vector V and surface normal N have dot product V·N > 0 (angle < 90°), the face is back-facing and invisible.

• Algorithm (for polygon with vertices in CCW order):

  • Compute normal N = (V2-V1) × (V3-V1).

  • View vector V = (eye_point - any_vertex).

  • If V·N > 0 → back face → don't draw.

• Example: Cube with vertices defined CCW from outside. For front face, V points towards viewer, N points outward → V·N < 0 (visible).

B. Shading Models

• Flat Shading: Compute one normal per polygon (usually geometric normal). Single color for entire polygon. Fast, but faceted look.

• Smooth Shading:

  • Gouraud Shading: Interpolate vertex colors across polygon. Fast, but highlights may be distorted.

  • Phong Shading: Interpolate vertex normals, compute color per pixel using full Phong model. Slower, but better specular highlights.

C. Reflection Models

VII. MULTIMEDIA SYSTEMS & TECHNOLOGIES

A. Multimedia System Architecture

• Components: Capture (sensors) → Storage (disks, databases) → Processing (editing, compression) → Presentation (display, audio) → Communication (networks).

• Logical Layers:

  1. Application Layer: End-user apps (player, editor).

  2. Middleware: OS, drivers, codecs, synchronization tools.

  3. System Layer: Hardware (CPU, GPU, I/O).

  4. Hardware Layer: Physical devices.

• Characteristics: Integrated (text, audio, video, graphics), Dynamic (time-based), Interactive (user control).

B. Multimedia Databases

• Need: Store & retrieve large volumes of non-textual data (images, video, audio).

• Challenges:

  • Volume: Gigabytes/terabytes.

  • Variety: Different formats, structures.

  • Content-based Query: "Find images similar to this" (requires feature extraction: color histogram, texture, shape).

  • Temporal Constraints: Video/audio synchronization.

• Characteristics: Support for content-based retrieval, indexing (e.g., R-trees for spatial data, signature files), query by example.

C. Multimedia Data File Formats & Standards

D. Compression Techniques

• Lossless: Original data perfectly reconstructed.

  • Run-Length Encoding (RLE): AAABBBCC → 3A3B2C. Good for simple graphics.

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

  • LZW: Dictionary-based. Used in GIF, TIFF, PDF.

  • Arithmetic Coding: More efficient than Huffman, but complex.

• Lossy: Irreversible, higher compression.

  • Transform Coding (DCT): JPEG, MPEG. Blocks → Discrete Cosine Transform → quantize → encode.

  • Vector Quantization: Cluster similar data, represent by codebook index.

• Standards:

  • JPEG: Still images. Uses DCT + Huffman.

  • MPEG: Video. Uses motion compensation + DCT.

  • MP3: Audio. Uses psychoacoustic model + sub-band coding.

E. Evolving Technologies

• Virtual Reality (VR): Immersive, computer-generated environment. Head-mounted displays, motion trackers.

• Augmented Reality (AR): Overlay digital info on real world (via phone/glasses). e.g., Pokémon GO.

• Interactive Television: Two-way communication, VOD, t-commerce.

• Digital Broadcasting: DVB, ATSC. Efficient spectrum use.

• Multimedia over IP: Streaming (progressive download, RTSP), Webcasting, IPTV.

F. Applications of Multimedia

• Education & Training: Computer-Based Instruction (CBI), simulations (flight, medical).

• Entertainment: Video games, special effects in movies, interactive movies.

• Business: Presentations (PPT), kiosks, videoconferencing, webinars.

• Medicine: Medical imaging (CT, MRI), telemedicine, surgical simulation.

VIII. ANIMATION & VISUALIZATION

A. Animation

• Definition: Creating illusion of motion by displaying sequence of still images (frames) rapidly.

• Keyframe Animation: Define key poses (keyframes), system interpolates in-betweens.

• Motion Specification: Paths, trajectories, physics-based (gravity, collisions).

• Principles (12 Classic by Disney): Squash & stretch, Anticipation, Staging, Straight Ahead & Pose-to-Pose, Follow Through & Overlapping Action, Slow In & Slow Out, Arcs, Secondary Action, Timing, Exaggeration, Solid Drawing, Appeal.

• Types: 2D (cel, vector), 3D (CGI), Stop-motion (clay, puppets), Morphing (shape transition).

B. Visualization (Short Note)

• High-Dimensional Data Visualization:

  • Parallel Coordinates: Each dimension is a vertical axis, data points are polylines.

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

  • Glyphs: Use shape/size/color of icons to represent multi-variate data at a point.

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

• Applications:

  • Scientific: Fluid flow (streamlines), molecular structures, weather models.

  • Information: Web structure, social networks, business dashboards.

  • Medical: 3D reconstructions from CT/MRI slices.

IX. COLOR MODELS & DISPLAY HARDWARE

A. Color Models

B. CRT (Cathode Ray Tube)

• Working Principle:

  1. Electron Gun: Heated cathode emits electrons, focused into beam.

  2. Deflection: Magnetic (yoke) or electrostatic plates steer beam horizontally/vertically.

  3. Phosphor Coating: Inside screen glows when struck by electrons. Different phosphors emit different colors (RGB stripes/dots for color CRT).

• Advantages: Wide viewing angle, good color reproduction, fast response (historically).

• Disadvantages: Bulky, heavy, high voltage, power-hungry, emits EM radiation, geometric distortion (especially at corners), flicker at low refresh rates.

X. AUTHORING TOOLS

• Definition: Software for creating multimedia applications without low-level programming. Integrate media, define interactivity, sequence events.

• Key Features:

  • Media Integration: Import/ edit text, graphics, audio, video, animation.

  • Timeline/Score: Visual layout of media over time (like video editor).

  • Interactivity: Define hotspots, buttons, navigation (branching).

  • Scripting: Built-in language (Lingo in Director, ActionScript in Flash) for complex logic.

• Examples:

  • Adobe Director (Shockwave): Powerful, timeline + Lingo. For CD-ROMs, kiosks.

  • Macromedia Flash: Vector-based, timeline + ActionScript. For web animations, games, RIAs.

  • ToolBook: Book metaphor (pages, objects). For e-learning.

  • Authorware: Icon-based flowchart paradigm. For CBT.

EXAM TIPS & COMMON PITFALLS:

• Clipping: For Cohen-Sutherland, always show region codes and step-by-step clipping. Remember: Trivial Reject = AND of codes ≠ 0.

• Bresenham vs DDA: Bresenham uses integers only, DDA uses floats. Bresenham is faster & more accurate.

• Bezier: Remember endpoint interpolation and convex hull. For cubic, B(0)=P0, B(1)=P3.

• Transformations: Order matters! Scaling then translating ≠ translating then scaling. Use homogeneous matrices.

• Projections: Parallel = no vanishing points, Perspective = vanishing points. Orthographic is a subset of parallel.

• Z-Buffer: Requires depth buffer (z-values) and frame buffer (colors). Memory = width * height * (bits for z + bits for color).

• Multimedia Compression: JPEG = image (DCT), MPEG = video (motion compensation + DCT), MP3 = audio (psychoacoustic).

• Color Models: RGB is additive (light), CMY is subtractive (pigment). YUV separates luminance (brightness) from chrominance (color).