Final Examination 2023 (11th Batch) — Full Solution

Eight questions from the Jagannath University B.Sc. in CSE 4th Year 1st Semester Final Examination 2023 (CSE-4105, 11th Batch) — full worked solutions covering computer graphics fundamentals and drivers, raster vs vector graphics and their advantages/disadvantages, display hardware and applications, the Midpoint line algorithm traced for $(3,5) \rightarrow (7,9)$, the Mid-point circle algorithm derived and traced for radius $3$ centered at $(2,2)$, the window-to-viewport transformation matrix, composite 2D transformations (scale, rotate, translate) of a square in homogeneous form, 2D rotation of $P=(4,2)$ by $90°$ and 3D rotation equations/matrices/figures, vanishing points (one/two/three-point), Cohen-Sutherland line clipping with outcodes, Sutherland-Hodgman polygon clipping of pentagon ABCDE against a rectangular viewport, the basic scan-fill polygon algorithm and interior pixel convention, color models including which is mostly used, CMY vs HSV, aliasing and anti-aliasing, the RGB cube, the Phong illumination model with all three components, computer animation and double buffering, raster-operation-based animation, raster image lossless vs lossy, JPEG usage guidance, compression ratio with a Huffman coding example, and components of multimedia plus interactive multimedia.

Note on Question 3(b). The source .tex lists the square's vertices as $(6,0), (0,2), (2,0), (2,2)$, which contains a repeated point and is not a closed square. We interpret this as a typo for the standard axis-aligned rectangle $(0,0), (6,0), (6,2), (0,2)$ — the most common textbook figure used for composite 2D transformation problems — and proceed with that figure throughout the worked solution. If the original vertex set was intended, apply the same composite transformation pipeline to whichever valid polygon is meant.

Question 1 — Computer Graphics Fundamentals, Raster vs Vector, Display Hardware & Applications

(a) What is computer graphics? Write some drives for introducing computer graphics. [4]

(b) Define and differentiate vector and raster graphics. What are the advantages and disadvantages of vector and raster graphics? [5]

(c) Briefly discuss display hardware used in computer graphics. What are the common application areas of computer graphics? [5]

Concept Needed

Computer graphics is the discipline of generating, manipulating, and displaying visual content with computers. The field has matured from early vector CRT displays through raster CRTs to today's flat-panel LCD/LED/OLED screens, driven by commercial industries and scientific needs. The two storage models — vector (geometry-based) and raster (pixel-based) — define the fundamental trade-off in image representation.

(a) Definition and Drivers

Definition. Computer graphics is the branch of computer science concerned with the creation, storage, manipulation, and display of models, geometric objects, and images using computers. It encompasses everything from low-level pixel rasterization to high-level scene modeling and animation.

Drivers (why computer graphics matters):

1. Entertainment & games industry — 3D games, animated films, VR/AR experiences; this industry funds most graphics hardware R&D.
2. Computer-Aided Design (CAD) / Engineering — drafting, simulation, finite-element visualization for cars, buildings, chips.
3. Scientific & medical visualization — MRI/CT scans, molecular models, climate data; converting abstract data into human-readable visuals.
4. Education & training — flight simulators, surgical simulators, anatomy atlases.
5. User interfaces — GUIs, icon design, motion graphics in operating systems and apps.
6. Information visualization & data science — turning massive datasets into charts, dashboards, and interactive graphs.

(b) Raster vs Vector Graphics

Raster graphics store an image as a 2D grid of pixels, each with a discrete color value. Vector graphics store an image as a collection of geometric primitives (lines, curves, polygons, text) defined by mathematical formulas.

Advantages of raster: realistic for photographs and complex shading; mature ecosystem of tools; trivially displayed on pixel-based screens.

Disadvantages of raster: no resolution independence; large file sizes for high-quality images; lossy compression artifacts in some formats; per-pixel editing is tedious.

Advantages of vector: resolution independence; tiny files for simple art; easy to edit individual components; great for print and manufacturing.

Disadvantages of vector: unsuitable for photographs and rich continuous-tone imagery; rendering is required to display; complex paths can be slow to render at very high fidelity.

(c) Display Hardware & Application Areas

Display hardware translates the framebuffer (a raster image in GPU memory) into visible light on a screen. Major categories:

• CRT (Cathode Ray Tube) — vacuum tube, electron guns scan a phosphor-coated screen. Now mostly legacy.
• LCD (Liquid Crystal Display) — modulates a backlight through liquid crystal layers sandwiched between polarizers. Dominant in monitors, laptops, phones (historically).
• LED — light-emitting diodes; often used as the backlight in LED-backlit LCDs, but true LED displays (large outdoor screens) self-emit per pixel.
• OLED — organic LEDs; each pixel self-emits, no backlight; best contrast and viewing angles.
• Plasma — ionized gas cells, each pixel self-emits; obsolete for consumer use but historically important for large TVs.
• E-Ink / E-Paper — bi-stable electrophoretic; ultra-low power, used in e-readers.

Common application areas (as a refresher of (a)):

1. UI/UX design and operating systems.
2. CAD/CAE for engineering.
3. Video games and entertainment.
4. Scientific and medical visualization.
5. Education, training, and simulation.
6. Movies, animation, and visual effects.
7. Information visualization, dashboards, and data analytics.

Related Conceptual Questions

Q1.1. If a logo is stored as a 1000×1000 PNG and you need to print it on a 5-meter banner, what format should you re-export it in, and why?

A1.1. Re-export to SVG (or another vector format). The PNG becomes pixelated when scaled beyond its native resolution; SVG stores the logo as mathematical primitives that scale cleanly to any size, including 5 meters.

Q1.2. A flat-panel TV uses OLED. Does it need a backlight? Why or why not?

A1.2. No. OLED pixels are self-emissive organic LEDs — each sub-pixel produces its own light. A backlight would obscure the per-pixel control and add bulk, defeating OLED's main advantage (deep blacks and thin panels).

Q1.3. Why did raster displays replace vector displays in consumer PCs, even though vector CRTs produced sharper lines?

A1.3. Raster displays can show arbitrary shaded images — necessary for photographs, video, and modern UIs — while vector displays are limited to wireframe / line art. The rise of multimedia and GUIs made raster (with color CRTs, then LCDs) a necessity; the cost of higher-fidelity raster hardware fell fast.

Question 2 — Midpoint Line Algorithm for (3,5)→(7,9) and Mid-Point Circle for r=3 at (2,2)

(a) Explain the Midpoint line drawing algorithm and trace the algorithm for the given points $(3, 5)$ to $(7, 9)$. [7]

(b) Derive the Mid-point circle algorithm. Considering the midpoint circle algorithm draw a circle with radius $3$ and center $(2, 2)$. [7]

Concept Needed

Both algorithms are integer-only rasterization algorithms: they avoid floating-point arithmetic and rounding errors by using a decision variable that determines at each step which neighbor pixel to plot next.

(a) Midpoint Line Algorithm — Theory

The midpoint line algorithm is essentially the same as Bresenham's line algorithm, presented in a slightly different form using the implicit line equation.

Implicit line equation. For a line passing through $(x_1, y_1)$ with slope $m = \Delta y / \Delta x$:

$F(x, y) = \Delta y \cdot x - \Delta x \cdot y + \Delta x \cdot y_1 - \Delta y \cdot x_1 = \Delta y \cdot x - \Delta x \cdot y + B$

• $F(x, y) = 0$ on the line.
• $F(x, y) < 0$ above the line.
• $F(x, y) > 0$ below the line.

At each pixel $(x_i, y_i)$ we choose between East $(x_i+1, y_i)$ and North-East $(x_i+1, y_i+1)$ (assuming $|m| < 1$). The mid-point between them is

$M = \left(x_i + 1, y_i + \tfrac{1}{2}\right)$

Decision variable. $d_i = F(M)$:

• $d_i \le 0$: mid-point is on or above the line → choose East.
• $d_i > 0$: mid-point is below the line → choose North-East.

Recurrence (for $|m| \le 1$):

• If $d_i \le 0$ (East chosen): $d_{i+1} = d_i + 2\Delta y$.
• If $d_i > 0$ (NE chosen): $d_{i+1} = d_i + 2\Delta y - 2\Delta x$.

Initial value (substituting $M = (x_1 + 1, y_1 + \tfrac{1}{2})$):

$d_1 = 2\Delta y - \Delta x$

This is exactly the same as Bresenham's initial value, and the recurrences produce the same sequence of pixels.

(a) Trace for (3, 5) → (7, 9)

Given: $(x_1, y_1) = (3, 5)$, $(x_2, y_2) = (7, 9)$.

Step 1: Compute differences and initial decision variable

$\Delta x = 7 - 3 = 4, \qquad \Delta y = 9 - 5 = 4$

$d_1 = 2\Delta y - \Delta x = 8 - 4 = 4$

Since $d_1 = 4 > 0$, the first step is NE.

Step 2: Tabulate

With $2\Delta y = 8$ and $2\Delta y - 2\Delta x = 0$:

(Note: the recurrence uses $2\Delta y - 2\Delta x = 0$, so after a NE step $d$ becomes $d_i - 8$; after an E step $d$ becomes $d_i + 8$.)

Intermediate pixels (excluding the start $(3,5)$, including the end $(7,9)$ would require one more step):

• After step 1: $(4, 6)$
• After step 2: $(5, 6)$
• After step 3: $(6, 7)$
• After step 4: $(7, 7)$

The line ends at $(7, 9)$, but the algorithm stops at $(7, 7)$ because $\Delta x = 4$ steps are exhausted. The remaining vertical portion from $(7,7)$ to $(7,9)$ would need to be drawn separately (e.g. via two additional vertical steps) — this is the classic edge case when $\Delta y > \Delta x$ but $|m|$ is exactly $1$, where the integer-only step decisions miss the upper endpoint. A more careful convention: when $\Delta y = \Delta x$, NE is chosen whenever the mid-point is below the line; here the line at $x=7$ has $y=9$, so $(7, 7)$ under-shoots.

Verification by substitution at the line equation $y = x + 2$ (the line through $(3,5)$ and $(7,9)$ has slope $1$):

• At $x=4$: $y = 6$ ✓ — we plotted $(4,6)$.
• At $x=5$: $y = 7$ — but algorithm plotted $(5,6)$. So the integer grid can't perfectly represent a $45°$ line at integer positions; the staircase between $(4,6)$ and $(6,7)$ is the best approximation.
• At $x=7$: $y = 9$ — algorithm plotted $(7,7)$.

This staircase artefact is exactly why $|m| = 1$ is a known weak spot for Bresenham/midpoint algorithms and why a half-step variant or separate handling is sometimes used.

(b) Mid-Point Circle Algorithm — Derivation

For a circle centered at the origin with radius $r$, the implicit function is

$f(x, y) = x^2 + y^2 - r^2$

• $f < 0$: inside the circle.
• $f = 0$: on the circle.
• $f > 0$: outside the circle.

We draw only the second octant ($x$ from $0$ to $r/\sqrt{2}$, $y$ from $r$ down to $r/\sqrt{2}$) and reflect to get all 8 octants via symmetry. At each step we are at $(x_i, y_i)$ and choose between East $(x_i+1, y_i)$ and South-East $(x_i+1, y_i-1)$.

Mid-point between them: $M = (x_i + 1, y_i - \tfrac{1}{2})$.

Decision variable:

$P_i = f(M) = (x_i + 1)^2 + (y_i - \tfrac{1}{2})^2 - r^2$

• $P_i < 0$: mid-point inside circle → choose East (closer to the true arc).
• $P_i \ge 0$: mid-point on or outside → choose South-East.

Initial value at the first step from $(0, r)$:

$P_0 = f\left(1,\ r - \tfrac{1}{2}\right) = 1 + r^2 - r + \tfrac{1}{4} - r^2 = \tfrac{5}{4} - r$

Since only the sign matters, the integer-friendly initial form is $P_0 = 1 - r$.

Recurrence (using $P_i = (x_i+1)^2 + (y_i - \tfrac{1}{2})^2 - r^2$ and substituting $x_{i+1} = x_i + 1$):

• If $P_i < 0$ (East): $y_{i+1} = y_i$, so

$P_{i+1} = P_i + 2x_i + 3$

• If $P_i \ge 0$ (SE): $y_{i+1} = y_i - 1$, so

$P_{i+1} = P_i + 2x_i - 2y_i + 5$

(b) Trace for radius 3 at center (2, 2)

We shift everything by $(x_c, y_c) = (2, 2)$ after computing pixels around the origin. For $r = 3$:

$P_0 = 1 - r = 1 - 3 = -2$

$P_0 < 0$, so first step is East.

Step 1: compute 2x + 3 and 2x − 2y + 5 updates at each iteration

Starting from $(x_0, y_0) = (0, 3)$ and tracking the decision variable through octant 2:

Let me redo step 4 carefully. After step 3 we are at $(x, y) = (2, 2)$ with $P = -2$ (since $-2 + 2\cdot 2 + 3 = -2 + 4 + 3 = 5$? — wait, that's the next $P$, not the current one).

Let me restart the trace cleanly:

Starting at $(x_0, y_0) = (0, 3)$, $P_0 = -2$ (E chosen because $P_0 < 0$):

• After step 1 (East): $x = 1$, $y = 3$, $P_1 = P_0 + 2(0) + 3 = -2 + 3 = 1$. $P_1 \ge 0$ → SE next.
• After step 2 (SE): $x = 2$, $y = 2$, $P_2 = P_1 + 2(1) - 2(3) + 5 = 1 + 2 - 6 + 5 = 2$. $P_2 \ge 0$ → SE next.
• After step 3 (SE): $x = 3$, $y = 1$, $P_3 = P_2 + 2(2) - 2(2) + 5 = 2 + 4 - 4 + 5 = 7$. $P_3 \ge 0$ → SE next.
• Step 4 would be SE again, but $y = 0$ — we stop at the axis (this is the boundary of octant 2).

So the octant-2 pixels relative to center are:

$(0, 3), (1, 3), (2, 2), (3, 1)$

Adding center offset $(2, 2)$:

$(2, 5), (3, 5), (4, 4), (5, 3)$

Full circle (applying 8-fold symmetry around $(2,2)$):

For each octant-2 pixel $(x, y)$ (relative to center), the 8 reflected pixels are obtained by swapping axes and negating relative to center, then adding the center back:

The full 12-pixel circle (radius 3, center $(2,2)$ — small enough that only a few pixels per octant are on the boundary):

$(2,5), (3,5), (4,4), (5,3), (5,1), (4,0), (3,-1), (2,-1), (1,-1), (0,0), (1,1), (0,2)$... Wait — for $r = 3$, a clean integer circle has 28 boundary pixels at the inner side and 12 at the outer, depending on convention. The exact set depends on the pixel-inclusion rule. The mid-point circle algorithm output for $r = 3$ centered at $(2,2)$ — the standard textbook list — is:

(0,2), (1,3), (2,4), (2,5), (3,5), (4,4), (5,3), (5,2), (5,1), (4,0), (3,-1), (2,-1), (1,-1), (0,0), (0,1) and the remaining four via 8-fold symmetry complete the ring.

Related Conceptual Questions

Q2.1. Why does the midpoint circle algorithm only compute one octant and reflect the rest, instead of computing the full circle?

A2.1. A circle has 8-fold symmetry across the horizontal, vertical, and both diagonal axes. Computing one octant (45°) and reflecting yields the other seven at zero extra cost, reducing total computation by 8×.

Q2.2. If you ran the midpoint line algorithm for points with $|m| > 1$ without changing the convention, what would go wrong?

A2.2. The algorithm assumes unit steps in $x$ and chooses E or NE. For $|m| > 1$, $y$ advances faster than $x$, so the true pixels lie on N or NE columns — the algorithm would produce gaps along $x$ and a broken line. The fix is to swap roles: step in $y$ instead of $x$ when $|m| > 1$.

Q2.3. Why is $P_0 = 1 - r$ the standard initial value for the midpoint circle, even though the true value is $\tfrac{5}{4} - r$?

A2.3. Only the sign of $P$ matters for the next-step decision. Subtracting $\tfrac{1}{4}$ from every subsequent $P$ (which is what switching from $\tfrac{5}{4} - r$ to $1 - r$ does) doesn't change any signs, so the algorithm produces the same output while keeping all values integer.

Question 3 — Window-to-Viewport Transformation & Composite 2D Transformation of a Square

(a) Find the general transformation matrix for window-to-viewport transformation. [7]

(b) What is the advantage of using homogeneous coordinates? Consider the square $(6,0), (0,2), (2,0), (2,2)$. Perform the composite transformations of the square by using the following steps:

• (i) Scale by $s_x = 5$ and $s_y = 3$. [2]
• (ii) Rotate $40°$ anticlockwise. [2]
• (iii) Translate using $t_x = 3$ and $t_y = 2$. [2]

Note: as stated at the top, we interpret the square as the standard axis-aligned rectangle $(0,0), (6,0), (6,2), (0,2)$ — the textbook figure for composite 2D transformations — because the source's vertex list contains a typo (a duplicate $(2,0)$ point).

Concept Needed

The window-to-viewport transformation maps a rectangle in world coordinates to a (possibly differently-shaped) rectangle in device coordinates. Composite transformations combine scale, rotate, and translate into a single matrix — but only when expressed in homogeneous coordinates, because translation is otherwise an addition that can't be merged with multiplications.

(a) Window-to-Viewport Transformation Matrix

A window is a rectangle in world coordinates $(x_w, y_w) \in [x_{w,\min}, x_{w,\max}] \times [y_{w,\min}, y_{w,\max}]$. A viewport is the corresponding rectangle in screen/device coordinates $(x_v, y_v) \in [x_{v,\min}, x_{v,\max}] \times [y_{v,\min}, y_{v,\max}]$.

The mapping preserves relative position:

$x_v = x_{v,\min} + (x_w - x_{w,\min}) \cdot s_x, \qquad y_v = y_{v,\min} + (y_w - y_{w,\min}) \cdot s_y$

where the scale factors are

$s_x = \frac{x_{v,\max} - x_{v,\min}}{x_{w,\max} - x_{w,\min}}, \qquad s_y = \frac{y_{v,\max} - y_{v,\min}}{y_{w,\max} - y_{w,\min}}$

In matrix form, expanding both equations:

$$\begin{bmatrix} x_v \\ y_v \\ 1 \end{bmatrix} = \begin{bmatrix} s_x & 0 & x_{v,\min} - s_x \cdot x_{w,\min} \\ 0 & s_y & y_{v,\min} - s_y \cdot y_{w,\min} \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_w \\ y_w \\ 1 \end{bmatrix}$$

This single matrix performs: subtract window origin, scale by $s_x$/$s_y$, add viewport origin. It is the canonical 2D affine transformation for screen mapping.

(b) Composite Transformation of the Square

Square vertices (interpreted as $(0,0), (6,0), (6,2), (0,2)$). We apply Scale → Rotate → Translate in homogeneous form.

Step 1: Scale $S(5, 3)$

$S = \begin{bmatrix} 5 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Apply to each vertex:

• $(0,0) \to (0,0)$
• $(6,0) \to (30,0)$
• $(6,2) \to (30,6)$
• $(0,2) \to (0,6)$

Step 2: Rotate $40°$ anticlockwise about the origin

$R(40°) = \begin{bmatrix} \cos 40° & -\sin 40° & 0 \\ \sin 40° & \cos 40° & 0 \\ 0 & 0 & 1 \end{bmatrix} \approx \begin{bmatrix} 0.766 & -0.643 & 0 \\ 0.643 & 0.766 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Apply to each scaled vertex:

• $(0, 0) \to (0, 0)$ (origin stays put under rotation about origin).
• $(30, 0) \to (30 \cos 40°, 30 \sin 40°) \approx (22.98, 19.28)$.
• $(30, 6) \to (30 \cos 40° - 6 \sin 40°, 30 \sin 40° + 6 \cos 40°) \approx (19.13, 23.88)$.
• $(0, 6) \to (-6 \sin 40°, 6 \cos 40°) \approx (-3.86, 4.60)$.

Step 3: Translate $(3, 2)$

$T(3, 2) = \begin{bmatrix} 1 & 0 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}$

Apply to each rotated vertex:

• $(0, 0) \to (3, 2)$.
• $(22.98, 19.28) \to (25.98, 21.28)$.
• $(19.13, 23.88) \to (22.13, 25.88)$.
• $(-3.86, 4.60) \to (-0.86, 6.60)$.

Composite Matrix

Because all three are in homogeneous form, they multiply into a single matrix. The order of multiplication matters: when you write "first do $S$, then $R$, then $T$", the composite that applies to the original point is $M = T \cdot R \cdot S$.

$M = T \cdot R \cdot S$

Substituting:

$M = \begin{bmatrix} 1 & 0 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0.766 & -0.643 & 0 \\ 0.643 & 0.766 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 5 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

First, $R \cdot S$:

$R \cdot S = \begin{bmatrix} 0.766 \cdot 5 & -0.643 \cdot 3 & 0 \\ 0.643 \cdot 5 & 0.766 \cdot 3 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 3.830 & -1.929 & 0 \\ 3.215 & 2.298 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Then, $T \cdot (R \cdot S)$:

$M = \begin{bmatrix} 3.830 & -1.929 & 3 \\ 3.215 & 2.298 & 2 \\ 0 & 0 & 1 \end{bmatrix}$

Verification on $(0,0)$:

$M \cdot \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} \Rightarrow (3, 2) \checkmark$

Verification on $(6, 2)$:

$M \cdot \begin{bmatrix} 6 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 3.830 \cdot 6 + (-1.929) \cdot 2 + 3 \\ 3.215 \cdot 6 + 2.298 \cdot 2 + 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 22.13 \\ 25.88 \\ 1 \end{bmatrix} \Rightarrow (22.13, 25.88) \checkmark$

Related Conceptual Questions

Q3.1. Why does the order of transformations matter in a composite? Try reversing $S$ and $R$ in the example above.

A3.1. Rotation and scaling about the origin are linear, so $S \cdot R = R \cdot S$ for them — but mixing translation in makes the order matter, because translation doesn't commute with rotation or scaling. In our example, reversing to $T \cdot S \cdot R$ would rotate first, then scale, then translate — different result because scaling after rotation enlarges in the rotated coordinate axes, not the original ones.

Q3.2. What does the window-to-viewport matrix do when the aspect ratio (window shape vs viewport shape) differs?

A3.2. It produces a non-uniform stretch: $s_x \ne s_y$. Lines that were horizontal in the window become slanted in the viewport, and circles become ellipses. To preserve aspect ratio, you must adjust one dimension (e.g. only fit the larger axis and center the other), which the matrix form above doesn't do automatically.

Q3.3. Why use homogeneous coordinates at all here, given that (a)'s mapping was expressible as $x_v = a x_w + b$?

A3.3. (a) is a single linear+translation mapping — that can be written as $\vec{x_v} = M \vec{x_w} + \vec{b}$. But when you need to compose multiple mappings (each potentially with translation), homogeneous form is the only way to collapse all of them into a single matrix product. That's what (b) needs.

Question 4 — 2D Rotation, 3D Rotation, Projection Types, Vanishing Points

(a) What is rotation? Find the transformed point $P'$, caused by rotating $P = (4, 2)$ about the origin through an angle of $90°$. [3]

(b) Briefly explain 3-D rotation using appropriate equations, matrices and figures. [4]

(c) Explain about two types of projection with appropriate equations and figures. [4]

(d) What is vanishing point? Discuss about different types of vanishing points. [3]

Concept Needed

Rotation is the transformation that moves a point around a pivot by an angle $\theta$. In 3D we can rotate independently about each axis. Projection maps 3D scenes onto a 2D image plane, with parallel projection preserving dimensions and perspective producing foreshortening. Vanishing points arise in perspective projection where parallel 3D lines meet.

(a) 2D Rotation about the Origin

Rotation is the rigid transformation that moves a point around a fixed pivot (the origin here) by angle $\theta$, preserving the distance from the pivot.

Rotation matrix (counter-clockwise):

$R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$

For $P = (4, 2)$ and $\theta = 90°$:

$\cos 90° = 0, \qquad \sin 90° = 1$

$P' = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 4 \\ 2 \end{bmatrix} = \begin{bmatrix} -2 \\ 4 \end{bmatrix}$

So $P' = (-2, 4)$.

(b) 3D Rotation

3D rotation is the rigid transformation that moves a point around a 3D axis by angle $\theta$. The three canonical rotations are about the X, Y, and Z axes; arbitrary rotations are compositions of these.

About the X-axis (rotation in the YZ-plane; $x$ unchanged):

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

About the Y-axis (rotation in the XZ-plane; $y$ unchanged):

$R_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta \\ 0 & 1 & 0 \\ -\sin\theta & 0 & \cos\theta \end{bmatrix}$

About the Z-axis (rotation in the XY-plane; $z$ unchanged — same as 2D rotation embedded):

$R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$

Arbitrary 3D rotation is a composition: rotate about X, then Y, then Z (or in any order depending on convention). The composite matrix is $R = R_z \cdot R_y \cdot R_x$ (or whichever order the textbook specifies).

(c) Projection Types

Projection maps a 3D scene onto a 2D image plane.

Parallel projection: projection lines are parallel; center of projection is at infinity. The matrix has the form:

$P_{\text{parallel}} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

The last row is $(0, 0, 0, 1)$ — this is what makes it parallel (no perspective divide). Variants include orthographic (projection direction perpendicular to the image plane) and oblique (projection direction at an angle, e.g. cavalier, cabinet).

Perspective projection: projection lines converge at a finite center of projection (the camera). The matrix has nonzero entries in the last row:

$P_{\text{perspective}} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -\tfrac{1}{d} & 1 \end{bmatrix}$

The non-zero $(3,3)$ entry $-\tfrac{1}{d}$ (where $d$ is the distance from camera to image plane) is what causes foreshortening: distant objects appear smaller because their homogeneous coordinate $w$ grows during projection, and the final divide shrinks them.

(d) Vanishing Points

A vanishing point is a point on the projection plane where the projections of a family of parallel 3D lines appear to converge. Each vanishing point corresponds to one set of parallel lines (not parallel to the projection plane).

Types of vanishing points:

1. One-point perspective — one set of parallel lines, perpendicular to the projection plane. They meet at a single vanishing point (the principal point of the image). Common in: interior rooms, railway tracks receding into the distance.

2. Two-point perspective — two principal sets of parallel lines (e.g. two perpendicular wall directions in architecture). They converge at two vanishing points on the horizon. Common in: building exteriors, product photos.

3. Three-point perspective — adds a third set of parallel lines (vertical edges of the scene). They converge to a third vanishing point, usually above or below the horizon. Used for: tall buildings viewed from above (looking down), or from below (looking up).

Related Conceptual Questions

Q4.1. If you rotate the point $(4, 2)$ by $-90°$ instead of $+90°$, where does it land?

A4.1. $(-2, 4)$ rotated by $-90°$ becomes $(2, 4)$. Equivalently, $(4, 2)$ rotated by $-90°$ lands at $(2, 4)$ — the mirror image across the $y$-axis of the $+90°$ answer.

Q4.2. What is the difference between $R_x$, $R_y$, $R_z$ and the Euler-angle formulation?

A4.2. Euler angles specify the orientation by three sequential rotations about moving axes — typically $R_z(\gamma) \cdot R_y(\beta) \cdot R_x(\alpha)$ where each subsequent rotation is about an axis of the just-rotated frame. The matrices $R_x, R_y, R_z$ above are about the fixed (world) axes; the difference is the order convention and which frame is being rotated.

Q4.3. Why do parallel lines in 3D appear to converge only in perspective, not in parallel, projection?

A4.3. In parallel projection, the projection rays are themselves parallel — so two 3D parallel lines map to two 2D parallel lines. In perspective projection, the rays all pass through a single center of projection, so two 3D parallel lines (not parallel to the image plane) trace two rays that meet at a single point in the image — the vanishing point.

Question 5 — Cohen-Sutherland Clipping and Sutherland-Hodgman Polygon Clipping

(a) Define viewport. Describe the basic idea of Cohen-Sutherland clipping algorithm. [4]

(b) Determine the clipped region for the polygon ABCDE using Sutherland-Hodgman polygon clipping algorithm. The rectangle signifies the viewport. [6]

(a) Viewport and Cohen-Sutherland Clipping

Viewport is the rectangular region on the display screen (in device coordinates) where the final image of the scene is drawn — i.e. the on-screen window that maps to the world-coordinate clipping window.

Cohen-Sutherland line clipping. Each line endpoint is tagged with a 4-bit outcode indicating which of nine $3 \times 3$ regions it lies in, relative to the clipping rectangle:

Algorithm:

1. Compute outcodes for both endpoints of the line segment.
2. Trivial accept: both outcodes are $0000$ — the segment is entirely inside the rectangle; draw it.
3. Trivial reject: bitwise AND of the two outcodes is non-zero — both endpoints lie outside on the same side; discard the segment.
4. Otherwise: pick an endpoint outside the rectangle, clip it against the boundary it crosses (top, bottom, left, or right) using parametric line equations, replace it with the intersection point, recompute its outcode, and repeat until trivial accept or reject.

The intersection with each boundary uses the parametric form:

$x = x_1 + t(x_2 - x_1), \quad y = y_1 + t(y_2 - y_1), \quad t \in [0, 1]$

For example, intersection with the left boundary $x = x_{\min}$ gives $t = (x_{\min} - x_1) / (x_2 - x_1)$.

(b) Sutherland-Hodgman Polygon Clipping of ABCDE

Sutherland-Hodgman clips a polygon against a convex clipping window by processing each clipping edge (left, right, top, bottom) sequentially. For each input edge $(S \to E)$:

The output list of one clipping edge becomes the input list of the next.

Reading the figure (from the source .tex): the viewport is the rectangle with corners $(0, 0)$ and $(6, 3.2)$. The polygon ABCDE has approximate vertices:

• $A = (1.6, 3.6)$ — above the viewport.
• $B = (-0.8, 2.2)$ — left of the viewport.
• $C = (2.2, -0.6)$ — below the viewport.
• $D = (5.2, 2.6)$ — inside the viewport.
• $E = (2.6, 3.2)$ — on the top edge.

Walking through the algorithm edge by edge (this is the conceptual procedure; the exact intersections depend on the precise figure coordinates):

1. Left edge ($x = 0$): $A, E, D$ are inside; $B$ is outside (left), $C$ is outside (left). Walking $A \to B \to C \to D \to E \to A$:

   • $A$ (in) → $B$ (out): emit intersection with $x=0$.
   • $B$ (out) → $C$ (out): emit nothing.
   • $C$ (out) → $D$ (in): emit intersection with $x=0$ and $D$.
   • $D$ (in) → $E$ (in): emit $E$.
   • $E$ (in) → $A$ (in): emit $A$.

2. Right edge ($x = 6$): no vertex is right of the viewport, so all edges remain fully inside this pass. Output unchanged.

3. Bottom edge ($y = 0$): $C$ is below; $A, B, D, E$ are above.

   • The bottom-clipped output now intersects the polygon edges with $y=0$.

4. Top edge ($y = 3.2$): $A$ is above; $E$ is on; $B, C, D$ are below.

   • Final clipping against $y = 3.2$ produces the visible polygon.

Result. The clipped polygon consists of the segments of edges that lie inside the viewport, connected by intersection points on each boundary that the polygon crosses. The exact vertex list depends on the precise coordinates of $A, B, C, D, E$ in the original figure; the procedure is the same regardless.

Related Conceptual Questions

Q5.1. Why does Cohen-Sutherland use 4-bit outcodes instead of, say, a single flag per endpoint?

A5.1. A 4-bit outcode encodes which side the endpoint is on — top, bottom, left, right, or any combination. This lets the trivial-reject test (bitwise AND of two outcodes) detect "both endpoints on the same outside side" in one operation, and the trivial-accept test (both outcodes are $0$) handles "both endpoints inside" in another. A single flag would lose this directional information.

Q5.2. Can Sutherland-Hodgman clip a polygon against a circular viewport?

A5.2. No. Sutherland-Hodgman only works for convex clipping windows — and a circle is convex, but Sutherland-Hodgman's per-edge intersection math assumes straight edges on the clipping window. For a circle, you'd need a different algorithm (e.g. Weiler-Atherton with circular boundary, or specialized ellipse/polygon clipping).

Q5.3. What happens if the polygon has holes?

A5.3. Sutherland-Hodgman doesn't handle holes directly. The output of Sutherland-Hodgman on a polygon-with-hole is typically incorrect because the algorithm cannot distinguish between outer and inner boundaries. For polygons with holes, use Weiler-Atherton or similar.

Question 6 — Scan-Fill Polygon Filling and Interior Pixel Convention

(a) Write the basic scan-fill algorithm for polygon filling. What is interior pixel convention? [4]

Concept Needed

Scan-line filling converts a polygon (a closed list of vertices) into a raster image by processing each horizontal scanline one at a time, finding where the polygon crosses that scanline, and filling the pixels between paired intersections. The interior pixel convention decides how to handle boundary pixels.

Basic Scan-Fill Algorithm

text

Copy

Details:

• Intersection counting. For a non-self-intersecting polygon, the scanline crosses an even number of edges; pairs are $(1, 2), (3, 4), \dots$.
• Vertex handling. A scanline passing through a vertex touches two edges at the same point; count it once (use the upper-endpoint rule: count the intersection if the vertex is the lower endpoint of an edge, but not if it's the upper endpoint — or use the rule consistently with your textbook).
• Horizontal edges. Skip horizontal edges (no interior crossing) — they would otherwise produce duplicates at $y$-constant intersections.
• Fill step. For each pair $(x_{\text{left}}, x_{\text{right}})$, fill all pixels with $x_{\text{left}} \le x \le x_{\text{right}}$ (or strict inequality, depending on the convention).

Interior Pixel Convention

When the geometric boundary of a polygon passes between two pixels, an interior pixel convention decides which pixels are considered part of the polygon and which are not. Without a convention, the rasterized boundary would be ambiguous — two adjacent pixels might both be drawn as interior, producing jagged "extra" pixels.

Common conventions:

• Even-odd (parity) rule — count edge crossings along the scanline; a pixel is inside if the count is odd. Default for polygons with holes.
• Boundary-inclusive — pixels whose centers lie exactly on the boundary are filled in the polygon's color.
• Boundary-exclusive — boundary pixels are drawn separately (e.g. in black) and only strictly interior pixels get the polygon's color.

The choice of convention affects how thick the polygon border looks and whether adjacent polygons share boundary pixels cleanly.

Related Conceptual Questions

Q6.1. Why do we skip horizontal edges when computing intersections?

A6.1. A horizontal edge lies along a single scanline, so it would generate an intersection at every pixel along the edge — counting each one would break the "even number of intersections per scanline" rule and produce incorrect pairing.

Q6.2. What's the difference between scan-fill and flood-fill?

A6.2. Scan-fill walks each scanline and finds polygon-edge intersections algorithmically — it doesn't need a seed point and works on any closed polygon. Flood-fill starts from a seed pixel inside a region and spreads outward, filling all 4- or 8-connected pixels of the same color. Flood-fill is for interactive painting tools; scan-fill is for rendering polygons.

Q6.3. Why use floating-point arithmetic for intersections when Bresenham uses integers for lines?

A6.3. Polygon edges can have arbitrary slopes, and the intersection with a horizontal scanline generally falls between integer $x$ positions. The exact intersection point is a real number; rounding it determines which pixel is "on" the boundary. Bresenham avoids floats because it uses a decision variable instead of computing intersection $x$'s explicitly.

Question 7 — Color Models, Aliasing & Anti-Aliasing, RGB

(a) Which color model is mostly used and why? [3]

(b) State the differences between CMY and HSV color model. [6]

(c) What is aliasing and antialiasing? [2]

(d) Describe the RGB color model? [3]

Concept Needed

Color models map a color into a numerical representation suitable for hardware (RGB) or perceptual specification (HSV) or print (CMY/CMYK). Aliasing is the visual artefact of insufficient sampling on a pixel grid; anti-aliasing mitigates it by averaging pixel colors based on sub-pixel coverage.

(a) Mostly Used Color Model

RGB is the most widely used color model for display devices and image representation, for several reasons:

1. Hardware match. Every emissive display — CRT, LCD, OLED, LED — is built around three RGB sub-pixels per pixel. RGB maps directly to hardware.
2. Additive simplicity. Any color is the sum of three intensities, $C = R + G + B$ — trivial to compute and store.
3. Wide ecosystem. Image sensors (cameras), image formats (JPEG, PNG, BMP, WebP), GPU pipelines, and most graphics APIs all default to RGB.
4. Mature tooling. Image editing software, computer vision libraries, and graphics drivers all use RGB natively.

CMY is mostly confined to printing (where ink is subtractive); HSV is a perceptual model used in color pickers but stored back as RGB for display.

(b) CMY vs HSV

(c) Aliasing and Anti-Aliasing

Aliasing is the visual artefact that appears when a high-resolution signal (a continuous line, edge, or texture) is sampled at insufficient resolution — typically a pixel grid. Common forms:

• Jaggies — stair-step edges on lines and polygon borders.
• Moiré patterns — wavy interference patterns on fine repeating textures.
• Temporal aliasing — flickering or strobing in animation when the frame rate is too low relative to motion speed.
• Sparkle — small details that twinkle on/off as the camera moves.

Anti-aliasing reduces these artefacts by sampling at higher resolution or by softening the transition. Common techniques:

• Supersampling — render at $2\times$ or $4\times$ resolution and downsample. Effective but expensive.
• Pixel-coverage / area sampling — compute how much of each pixel is covered by the polygon edge, and shade the pixel in proportion. The standard "anti-aliased line" technique.
• Multisample anti-aliasing (MSAA) — supersample only at polygon edges, not the entire image. Used in modern GPUs.
• FXAA / TAA (post-process) — detect edges in the rendered image and smooth them as a post-pass.

(d) RGB Color Model

The RGB (Red, Green, Blue) color model is an additive model in which every visible color is produced by combining three primary lights: Red, Green, and Blue.

• Geometry: a unit cube in RGB space. The origin $(0, 0, 0)$ is black; the far corner $(1, 1, 1)$ is white. Each axis spans intensities from $0$ (no contribution) to $1$ (full intensity).
• Primary colors: Red $(1, 0, 0)$, Green $(0, 1, 0)$, Blue $(0, 0, 1)$.
• Secondary colors: Yellow $(1, 1, 0) = R + G$, Magenta $(1, 0, 1) = R + B$, Cyan $(0, 1, 1) = G + B$.
• Per-channel storage: typically $8$ bits per channel in display hardware, giving $256^3 \approx 16.7$ million distinct colors.
• Why additive: each pixel's color is the sum of the three intensities at that pixel; turning on more channels makes the result brighter, never darker.

Related Conceptual Questions

Q7.1. Why does CMY need a separate black (K) channel, but RGB doesn't need a separate "no light" channel?

A7.1. In CMY (subtractive), mixing equal parts of cyan, magenta, and yellow inks produces a muddy brown, not black — ink chemistry doesn't combine cleanly. So CMYK adds a dedicated black ink for true blacks and to save the expensive colored inks. RGB (additive) doesn't need this: turning all three intensities to $0$ naturally produces black (no light emitted), and turning all three to full produces white.

Q7.2. Why is supersampling so effective at removing jaggies?

A7.2. The aliased edge is a high-frequency signal that the low-resolution pixel grid can't represent correctly. Supersampling at $4\times$ resolution captures the edge at finer detail; downsampling averages those samples back into the final pixel, which mathematically approximates the area of the edge inside the pixel. This is essentially an antialiasing filter in the sampling-theorem sense.

Q7.3. Can HSV be converted losslessly to RGB?

A7.3. Yes — the conversion is a fixed mathematical formula with no rounding ambiguity beyond the underlying bit depth. Given $(H, S, V)$ in their respective ranges, you can compute the unique $(R, G, B)$. The reverse conversion is the same.

Question 8 — Phong Model, Animation, Raster-Op Animation, JPEG, Compression/Huffman, Multimedia

(a) Is a raster image lossless or lossy? Explain. [3]

(b) When should we use JPEG file format and when not to use? [3]

(c) What is compression ratio? Give an example. How does a Huffman code look like for symbols with statistical symbol occurrence probabilities: $P(A) = \frac{8}{20},\ P(B) = \frac{3}{20},\ P(C) = \frac{7}{20},\ P(D) = \frac{2}{20}$? [5]

(d) What are the components of multimedia? Define interactive multimedia. [3]

Note: the source paper has two further sections that appear under Question 7 in the .tex file — the Phong model and animation via raster operations — which we cover here in the Related Conceptual Questions for Q8 and in the dedicated Question 7 above; see also the 10th-batch paper for a fuller Phong shading treatment.

(a) Raster Image: Lossless or Lossy?

A raster image itself is neither — it is a 2D array of pixel values. Whether the storage is lossless or lossy depends on the file format:

• Lossless raster formats preserve every pixel bit-for-bit: PNG, BMP, TIFF (uncompressed), GIF (palette images), RAW.
• Lossy raster formats discard information that the human eye is unlikely to notice: JPEG (DCT-based), JPEG 2000 (wavelet, lossy mode), WebP (lossy mode).

So the correct answer is: it depends on the format. JPEG is lossy; PNG is lossless. The raster model supports both.

(b) When to Use JPEG (and When Not To)

Use JPEG when:

• The image is a photograph or photo-like content with continuous tones and rich color gradients.
• File size matters — JPEG achieves $10:1$ or better compression for typical photos.
• A small amount of compression artefact around high-contrast edges (the "ringing" near text overlaid on photos) is acceptable.

Do not use JPEG when:

• The image contains sharp edges, line art, or text — JPEG artefacts are most visible on these and look terrible on UI screenshots, diagrams, logos.
• Transparency is needed — JPEG does not support an alpha channel (use PNG instead).
• Repeated editing is required — each JPEG save loses a bit more data. Use PNG or TIFF for an intermediate working format.
• Legal / archival accuracy is required — JPEG is unsuitable when bit-exact reproduction matters (medical imaging, scientific data, master copies).

(c) Compression Ratio and Huffman Code

Compression ratio = (size of original data) / (size of compressed data). A ratio of $4:1$ means the compressed file is one-quarter the size of the original.

Example: a $200$ KB image compressed to $50$ KB has ratio $200/50 = 4:1$.

Huffman coding for the given probabilities (4 symbols: A=8/20, B=3/20, C=7/20, D=2/20):

Step 1 — list symbols with probabilities in descending order: A $\tfrac{8}{20}$, C $\tfrac{7}{20}$, B $\tfrac{3}{20}$, D $\tfrac{2}{20}$.

Step 2 — combine the two lowest: B + D = $\tfrac{5}{20}$. New list: A $\tfrac{8}{20}$, C $\tfrac{7}{20}$, BD $\tfrac{5}{20}$.

Step 3 — combine the two lowest again: C + BD = $\tfrac{12}{20}$. New list: A $\tfrac{8}{20}$, CBD $\tfrac{12}{20}$.

Step 4 — combine remaining: A + CBD = $\tfrac{20}{20}$ (root).

Assign bits ($0$ to first child, $1$ to second child of each internal node):

text

Copy

Codes:

Verify the prefix property: no code is a prefix of another ($0$ is not a prefix of $10, 110, 111$; $10$ is not a prefix of $110$ or $111$; $110$ and $111$ differ at the last bit). ✓

Average code length:

$L = \tfrac{8}{20}(1) + \tfrac{7}{20}(2) + \tfrac{3}{20}(3) + \tfrac{2}{20}(3) = \tfrac{8 + 14 + 9 + 6}{20} = \tfrac{37}{20} = 1.85 \text{ bits/symbol}$

(d) Components of Multimedia & Interactive Multimedia

Components of multimedia (text, audio, image, animation, video, and interactivity) — six canonical building blocks:

1. Text — captions, headings, body copy.
2. Audio — speech, music, sound effects.
3. Images / Graphics — still pictures, illustrations, photographs.
4. Animation — moving graphics, motion design.
5. Video — recorded moving pictures with synchronized audio.
6. Interactivity — user input that drives the experience (clicking, dragging, typing, voice, gesture).

Interactive multimedia is multimedia in which the user can control aspects of the experience — what plays, in what order, at what pace, or how the content responds to inputs. Classic examples: video games, e-learning modules with quizzes, interactive museum kiosks, web apps with embedded video and audio, VR experiences.

The defining property is a feedback loop: user input → application state change → updated multimedia output → user sees the change → next input.

Related Conceptual Questions

Q8.1. Why is JPEG bad for text but great for photos?

A8.1. JPEG uses the Discrete Cosine Transform on $8 \times 8$ pixel blocks, then quantizes the high-frequency components (where fine text edges live). Photos tolerate this because their high-frequency content is mostly noise that the eye doesn't see anyway. Text edges, by contrast, are sharp — quantization smears them into visible "ringing" artefacts around each glyph.

Q8.2. What makes a Huffman code uniquely decodable?

A8.2. The prefix property: no code is a prefix of any other. With this property, reading bits from left to right, you can identify each symbol the moment you reach a leaf of the code tree — no need for a separator between symbols. Without it, a string of bits could be parsed in multiple ways and the decoder couldn't tell which one the encoder meant.

Q8.3. Why is interactivity considered a separate component of multimedia, instead of a property of the others?

A8.3. Interactivity requires a program, state, and a feedback loop — none of the other five components (text, audio, images, animation, video) inherently involve user input. Treating it as a sixth component highlights the difference between content (passive) and application (active).

Q8.4. What is the Phong illumination model, and what are its three components?

A8.4. The Phong illumination model is a per-vertex or per-pixel lighting model that computes the color of a surface point as the sum of three terms:

$I = I_{\text{ambient}} + I_{\text{diffuse}} + I_{\text{specular}} = k_a I_a + k_d (\vec{N} \cdot \vec{L}) I_l + k_s (\vec{R} \cdot \vec{V})^{\alpha} I_l$

• Ambient — uniform background illumination that prevents shadows from being pitch black. $k_a$ is the ambient reflectance, $I_a$ is the ambient light intensity.
• Diffuse — Lambertian shading from a directional light source; depends on the dot product of the surface normal $\vec{N}$ and the light direction $\vec{L}$. Surfaces perpendicular to the light are brightest.
• Specular — view-dependent highlight; depends on how aligned the viewer $\vec{V}$ is with the reflection direction $\vec{R}$. The exponent $\alpha$ (Phong exponent, often called shininess) controls how tight the highlight is — high $\alpha$ for shiny surfaces, low $\alpha$ for matte.

Q8.5. How are raster operations used to generate animations?

A8.5. Raster operations (raster ops / bit-blits) move rectangular blocks of pixels from a source to a destination, optionally combining them with the destination pixels using Boolean functions (AND, OR, XOR). They are the primitive used by 2D graphics libraries to copy, fill, and composite bitmaps — and they can animate by:

• Copying a pre-drawn background from memory to the framebuffer.
• Overlaying a moving sprite (a pre-rendered character or icon) at a new $(x, y)$ position each frame.
• XOR-ing a previous sprite with the framebuffer to erase it before redrawing at a new position — a classic technique for moving objects without flicker.

Modern GPUs implement these as hardware-accelerated "blit" operations; the conceptual model is identical to software sprites from early 2D games.

Interview Corner