BE Computer Engineering (Pokhara University) Computer Graphics (PU, CMP 234) Question Paper 2078 Nepal

(a) Raster-scan display architecture and comparison

Architecture (block diagram, described): The CPU sends graphics commands to the display controller / graphics processor. The image is stored as an array of intensity values in the frame buffer (refresh buffer) in system or video memory. A video controller reads the frame buffer pixel-by-pixel, in scan-line order, converts the digital values to analog voltages through a DAC, and drives the electron gun of the CRT. Horizontal and vertical deflection circuits sweep the beam across the screen.

CPU --> Display Processor --> Frame Buffer --> Video Controller --> DAC --> CRT (electron gun + deflection)

The beam scans the entire screen left-to-right, top-to-bottom (raster), turning each pixel on/off according to the frame-buffer value, then retraces. The screen is redrawn (refreshed) typically 60-80 times per second.

Raster vs Random (Vector) scan:

(b) Frame buffer size and access rate

Resolution $= 1280 \times 1024 = 1{,}310{,}720$ pixels. Color depth $= 24$ bits $= 3$ bytes/pixel.

$$\text{Frame buffer} = 1280 \times 1024 \times 3 = 3{,}932{,}160 \text{ bytes} = \frac{3{,}932{,}160}{1024 \times 1024} = 3.75 \text{ MB}$$

At 60 Hz, total pixels read per second $= 1{,}310{,}720 \times 60 = 78{,}643{,}200$ pixels/s.

$$\text{Time per pixel} = \frac{1}{78{,}643{,}200} \approx 1.27 \times 10^{-8}\,\text{s} \approx 12.7\,\text{ns}$$

Frame buffer = 3.75 MB; access rate ≈ 12.7 ns per pixel.

(c) Aspect ratio and persistence

• Aspect ratio: the ratio of the horizontal extent (width) to the vertical extent (height) of the displayed image, e.g. $4:3$. It fixes the proportion of horizontal to vertical pixels needed to draw equal-length lines.
• Persistence: the time taken for the emitted light of a CRT phosphor to decay to $1/10$ (10%) of its initial intensity after the electron beam is removed.

Importance: Persistence determines the minimum refresh rate needed to avoid flicker. A short-persistence phosphor decays quickly and must be refreshed at a higher rate; a long-persistence phosphor holds the image longer (good for static images) but smears moving images. Persistence therefore directly governs flicker, refresh-rate design, and suitability for animation.

(a) Bresenham's line algorithm decision parameter (0 < m < 1)

Assumptions: the line is drawn from $(x_0,y_0)$ to $(x_1,y_1)$ with slope $0 < m < 1$; $x$ is the fast (unit-increment) axis. Endpoints are integers. At each step $x$ increases by 1 and we must decide whether $y$ stays the same or increases by 1.

The line equation: $y = mx + c$ with $m = \Delta y/\Delta x$. Rewrite as the implicit form

$$F(x,y) = \Delta y \cdot x - \Delta x \cdot y + c\,\Delta x = 0.$$

After plotting $(x_k, y_k)$, the candidates are the lower pixel $(x_k+1, y_k)$ and the upper pixel $(x_k+1, y_k+1)$. Let $d_{lower}$ and $d_{upper}$ be the vertical distances from the true line at $x_k+1$ to these pixels. Define the decision parameter

$$p_k = \Delta x\,(d_{lower} - d_{upper}).$$

Working this out gives

$$p_k = 2\Delta y\,x_k - 2\Delta x\,y_k + c'.$$

Initial value: $p_0 = 2\Delta y - \Delta x.$

Incremental update (the two pixel choices):

• If $p_k < 0$: the lower pixel is closer. Choose $y_{k+1} = y_k$ and

$$p_{k+1} = p_k + 2\Delta y.$$

• If $p_k \ge 0$: the upper pixel is closer. Choose $y_{k+1} = y_k + 1$ and

$$p_{k+1} = p_k + 2\Delta y - 2\Delta x.$$

Only integer additions are used, so the algorithm is fast and avoids floating-point.

(b) Midpoint circle algorithm, r = 8, centre origin

Decision parameter starts at $p_0 = 1 - r = 1 - 8 = -7$. Begin at $(0, 8)$ and step $x$ in the first octant until $x \ge y$.

• If $p_k < 0$: next pixel $(x_{k+1}, y_k)$, $p_{k+1} = p_k + 2x_{k+1} + 1$.
• If $p_k \ge 0$: next pixel $(x_{k+1}, y_k - 1)$, $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$.

First-octant pixels: $(0,8),(1,8),(2,8),(3,7),(4,7),(5,6),(6,6)$.

Eight-way symmetry: for every computed point $(x,y)$ in one octant, the remaining seven pixels are obtained by reflecting across the axes and the lines $y=\pm x$:

$$(x,y),(y,x),(-x,y),(-y,x),(x,-y),(y,-x),(-x,-y),(-y,-x).$$

Thus only $1/8$ of the circle is computed; the rest is plotted by symmetry (offset by the centre), saving computation.

(a) Parallel vs Perspective projection

Orthographic parallel projection: projectors are perpendicular to the view plane (e.g. front, top, side views). Lengths parallel to the plane are preserved.

Oblique parallel projection: projectors are parallel but strike the view plane at an oblique (non-90°) angle, so one face is shown true-size while depth is shown along an inclined direction (e.g. Cavalier, Cabinet projections).

Definitions:

• Centre of projection (COP): the point from which all projectors emanate (the eye/camera position in perspective).
• Vanishing point: the point on the view plane where projected parallel lines (not parallel to the plane) appear to converge.
• View plane (projection plane): the plane onto which the 3D scene is projected to form the 2D image.

(b) Perspective projection matrix onto z = 0, COP at (0,0,-d)

A point $(x,y,z)$ is projected by a line from the COP $(0,0,-d)$ to the point, intersecting the plane $z=0$. By similar triangles the projected coordinates are

$$x_p = \frac{x}{1 + z/d}, \qquad y_p = \frac{y}{1 + z/d}, \qquad z_p = 0.$$

In homogeneous coordinates this is achieved by

$$M_{per} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & \tfrac{1}{d} & 1 \end{bmatrix}.$$

Applying it: $M_{per}\,[x\ y\ z\ 1]^T = [x\ y\ 0\ (z/d+1)]^T$. Dividing by the homogeneous coordinate $w = z/d + 1$ gives $x_p = x/(1+z/d)$, $y_p = y/(1+z/d)$, as required.

(c) Homogeneous coordinates

Homogeneous coordinates represent a 3D point $(x,y,z)$ as a 4-tuple $(x,y,z,1)$. They are used because translation cannot be expressed as a $3\times3$ matrix multiplication — it is additive. Embedding points in 4D lets translation, rotation, scaling, and projection all be written as $4\times4$ matrix multiplications. Because matrix multiplication is associative, a sequence of operations $T, S, R$ can be pre-multiplied once into a single composite matrix

$$M = T \cdot R \cdot S,$$

and every vertex is then transformed by a single multiplication $P' = M\,P$, which is far more efficient than applying each transform separately.

(a) Cohen–Sutherland line clipping algorithm

The algorithm clips a line against a rectangular window using 4-bit region (outcodes). The plane is divided into 9 regions by extending the window edges. Each endpoint gets a 4-bit code (TBRL = Top, Bottom, Right, Left):

• bit 1 (Top): set if $y > y_{max}$
• bit 2 (Bottom): set if $y < y_{min}$
• bit 3 (Right): set if $x > x_{max}$
• bit 4 (Left): set if $x < x_{min}$

Tests using logical operations:

• Trivial accept: if both codes are 0000 (logical OR of the two codes = 0), the line is wholly inside — accept it.
• Trivial reject: if the logical AND of the two codes ≠ 0, both endpoints lie outside the same side, so the line is entirely outside — reject it.
• Otherwise: the line crosses a boundary. Pick an endpoint that is outside, find its intersection with the corresponding window edge, replace that endpoint with the intersection point, recompute its outcode, and repeat until trivial accept or reject.

Intersection with a vertical edge $x = x_e$: $y = y_1 + m(x_e - x_1)$. With a horizontal edge $y = y_e$: $x = x_1 + (y_e - y_1)/m$.

(b) Clipping P1(0,3)–P2(11,6) against window (1,1)–(9,8)

Slope $m = \dfrac{6-3}{11-0} = \dfrac{3}{11}.$

Outcodes:

• P1(0,3): $x=0 < x_{min}=1$ ⇒ Left bit set ⇒ 0001.
• P2(11,6): $x=11 > x_{max}=9$ ⇒ Right bit set ⇒ 0010.

OR = 0011 ≠ 0 (not trivially accepted); AND = 0000 (not trivially rejected) ⇒ must clip.

Clip P1 against left edge $x=1$:

$$y = 3 + \tfrac{3}{11}(1-0) = 3 + \tfrac{3}{11} = \tfrac{36}{11} \approx 3.27.$$

New P1 $= (1,\ 3.27)$, outcode 0000 (inside).

Clip P2 against right edge $x=9$:

$$y = 3 + \tfrac{3}{11}(9-0) = 3 + \tfrac{27}{11} = \tfrac{60}{11} \approx 5.45.$$

New P2 $= (9,\ 5.45)$, outcode 0000 (inside).

Both endpoints now inside ⇒ trivial accept.

Clipped visible segment: from $(1,\ 3.27)$ to $(9,\ 5.45)$.

Reflection of triangle about the line y = x

Reflection about $y=x$ swaps the $x$ and $y$ coordinates: $(x,y) \to (y,x)$.

Transformation matrix (homogeneous form):

$$R_{y=x} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

New vertices:

Verification of vertex B(6, 2):

$$\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 6 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ 1 \end{bmatrix} \Rightarrow B'(2,6). \checkmark$$

Thus $A'(2,2),\ B'(2,6),\ C'(6,4)$.

Rotation by θ about an arbitrary pivot (x_p, y_p)

Rotation matrices are defined about the origin only, so the pivot must first be moved to the origin. The required sequence is:

1. Translate the pivot to the origin: $T(-x_p,-y_p)$.
2. Rotate by $\theta$ about the origin: $R(\theta)$.
3. Translate back: $T(x_p,y_p)$.

Composite matrix (applied right-to-left to a point):

$$M = T(x_p,y_p)\cdot R(\theta)\cdot T(-x_p,-y_p)$$ $$M = \begin{bmatrix} \cos\theta & -\sin\theta & x_p(1-\cos\theta)+y_p\sin\theta \\ \sin\theta & \cos\theta & y_p(1-\cos\theta)-x_p\sin\theta \\ 0 & 0 & 1 \end{bmatrix}$$

Why order matters: matrix multiplication is not commutative ($AB \neq BA$). The transformations must be applied in the correct sequence (translate-to-origin, rotate, translate-back). Reversing the order — e.g. rotating before translating the pivot to the origin — rotates the object about the origin instead of the pivot, giving a wrong result.

Bézier curve

A Bézier curve is a parametric curve defined by a set of $n+1$ control points $P_0, P_1, \dots, P_n$, where the curve is a weighted blend of the control points using Bernstein polynomials as blending functions, with parameter $u \in [0,1]$:

$$P(u) = \sum_{i=0}^{n} P_i\, B_{i,n}(u), \qquad B_{i,n}(u) = \binom{n}{i} u^i (1-u)^{n-i}.$$

Cubic Bézier (4 control points, n = 3) blending functions:

$$\begin{aligned} B_{0,3}(u) &= (1-u)^3 \\ B_{1,3}(u) &= 3u(1-u)^2 \\ B_{2,3}(u) &= 3u^2(1-u) \\ B_{3,3}(u) &= u^3 \end{aligned}$$

so $P(u) = (1-u)^3 P_0 + 3u(1-u)^2 P_1 + 3u^2(1-u) P_2 + u^3 P_3.$

Key geometric properties:

• Endpoint interpolation: the curve passes through the first and last control points, $P(0)=P_0$ and $P(1)=P_3$.
• Convex hull: the curve lies entirely within the convex hull of its control points (since the blending functions are non-negative and sum to 1).
• Tangent (endpoint) conditions: the tangent at the start is along $P_1 - P_0$ and at the end along $P_3 - P_2$; i.e. $P'(0)=3(P_1-P_0)$, $P'(1)=3(P_3-P_2)$.

Interpolation vs Approximation splines

• Interpolation spline: the curve passes through all the given control points; the control points lie on the curve (e.g. natural cubic spline, Catmull-Rom). Used when the path must hit specific data points.
• Approximation spline: the curve is guided by but does not necessarily pass through all control points; the points act as a control polygon that pulls the curve toward them (e.g. B-spline, Bézier interior points). Gives smoother, more controllable shapes.

Parametric continuity (C)

Measured by matching parametric derivatives at the join of two segments:

• C0: the two segments meet (same position at the join) — positional continuity only.
• C1: C0 and equal first parametric derivatives (same tangent vector, both magnitude and direction).
• C2: C1 and equal second parametric derivatives (same curvature behaviour).

Geometric continuity (G)

Requires only that the directions of derivatives match (magnitudes may differ):

• G0: the segments meet (same position) — identical to C0.
• G1: the tangent directions are equal at the join, but their magnitudes may differ. (Hence C1 ⇒ G1, but G1 does not imply C1.)

Geometric continuity is a less strict condition than parametric continuity and is often visually sufficient for smooth-looking joins.

Z-buffer (depth-buffer) algorithm

The Z-buffer is an image-space hidden-surface-removal method that resolves visibility at each pixel by comparing depth ($z$) values.

Two buffers required:

1. Frame (refresh) buffer — stores the colour/intensity of each pixel.
2. Depth (Z) buffer — stores the depth $z$ of the closest surface seen so far at each pixel.

Algorithm:

1. Initialise depth buffer to maximum depth (e.g. z = far/∞) for all pixels.
   Initialise frame buffer to background colour.
2. For each polygon in the scene:
     For each pixel (x, y) covered by the polygon:
        Compute the depth z of the polygon at (x, y).
        If z is closer than depthBuffer[x][y]:
              depthBuffer[x][y] = z
              frameBuffer[x][y] = colour of polygon at (x, y)
3. Display the frame buffer.

Depth across a polygon is computed incrementally from the plane equation, so only an addition is needed per pixel along a scan line.

Advantages (vs painter's / depth-sort):

• Simple to implement; no sorting of polygons required.
• Handles interpenetrating and cyclically overlapping polygons correctly, which the painter's algorithm cannot.
• Polygons can be processed in any order; easily hardware-accelerated.

Limitations:

• Requires extra memory for the depth buffer.
• Limited depth precision can cause z-fighting for surfaces very close in depth.
• Does not directly handle transparency/anti-aliasing without extension.

In contrast, the painter's algorithm sorts polygons back-to-front and paints them in that order; it uses less memory but fails for overlapping/cyclic polygons and the sort is costly.

Back-face detection

Back-face detection is a hidden-surface-removal technique that identifies and removes (culls) the polygon faces of a closed solid that point away from the viewer, because such faces are hidden by the front faces and need not be rendered. This speeds up rendering by roughly halving the polygons processed.

Condition: A polygon is a back face if its outward normal makes an angle greater than 90° with the viewing direction $\mathbf{V}$, i.e.

$$\mathbf{N}\cdot\mathbf{V} > 0 \;\text{(back face, with V pointing from surface toward viewer)}.$$

For the standard case with the viewer looking along the positive z-axis and normal $\mathbf{N}=(A,B,C)$, the viewing direction is $(0,0,1)$, so

$$\mathbf{N}\cdot(0,0,1) = C.$$

Therefore the polygon is a back face (and is culled) when $C > 0$ (its normal has a positive z-component, pointing in the same direction as the viewer's line of sight, i.e. away from the viewer). If $C < 0$ it is a front face and is kept; $C = 0$ means the face is viewed edge-on.

Gouraud vs Phong shading

Why Phong renders highlights more accurately: A specular highlight is a small, sharply varying region of the intensity function. In Gouraud shading, intensity is only sampled at the vertices and linearly interpolated, so a highlight that occurs in the interior of a polygon (not at a vertex) is averaged out or lost — and large polygons show banding (Mach bands). Phong shading instead interpolates the normal vector and recomputes the full $(\mathbf{N}\cdot\mathbf{H})^n$ specular term at every pixel, so the highlight's true position and sharp falloff are captured, producing realistic, well-rounded highlights.

Phong illumination model

The Phong model expresses the reflected intensity at a surface point as the sum of three components — ambient, diffuse, and specular:

$$I = I_a k_a \;+\; I_p k_d (\mathbf{N}\cdot\mathbf{L}) \;+\; I_p k_s (\mathbf{R}\cdot\mathbf{V})^{n}$$

Terms:

• $I_a k_a$ — ambient term: background light $I_a$ reflected uniformly; $k_a$ is the ambient reflection coefficient.
• $I_p k_d (\mathbf{N}\cdot\mathbf{L})$ — diffuse (Lambertian) term: depends on the angle between the surface normal $\mathbf{N}$ and the light direction $\mathbf{L}$; $k_d$ is the diffuse coefficient. Independent of viewer position.
• $I_p k_s (\mathbf{R}\cdot\mathbf{V})^{n}$ — specular term: the shiny highlight, depending on the angle between the reflected-light direction $\mathbf{R}$ and the viewer direction $\mathbf{V}$; $k_s$ is the specular coefficient.

Here $I_p$ is the point-light intensity, and all vectors are unit vectors.

Shininess / specular exponent $n$: it controls the size and sharpness of the highlight. A large $n$ (e.g. 100+) gives a small, tight, bright highlight typical of a smooth, polished/metallic surface; a small $n$ (e.g. 1) gives a large, soft, spread-out highlight typical of a dull surface. Because $(\mathbf{R}\cdot\mathbf{V})$ is $\le 1$, raising it to a higher power makes the term fall off rapidly as $\mathbf{V}$ moves away from $\mathbf{R}$.

Sutherland–Hodgeman polygon clipping

This is a divide-and-conquer polygon-clipping algorithm. The polygon is clipped against one window edge at a time (left, right, bottom, top in turn); the output vertex list from one stage becomes the input to the next. The whole subject polygon is processed against each clip boundary, producing a new (possibly larger) vertex list.

Each edge of the polygon, from vertex $S$ (start) to vertex $P$ (end), is tested against the current clip boundary. Four cases arise (output the points marked → ):

1. Both S and P inside: the edge is fully visible → output P.
2. S inside, P outside (leaving): → output the intersection point I of edge $SP$ with the boundary.
3. S outside, P inside (entering): → output the intersection I and then P (two points).
4. Both S and P outside: the edge is fully outside → output nothing.

After all four boundaries are processed, the resulting vertex list is the clipped polygon.

Limitation for concave polygons: when a concave polygon is clipped, the algorithm can produce extraneous connecting edges (spurious lines joining separate visible regions). Because the output is a single ordered vertex list, two disjoint pieces of a clipped concave polygon get joined by an unwanted edge running along the window boundary, so the result is not rendered correctly. (Weiler–Atherton clipping is used to handle concave polygons properly.)

Short notes (any two)

(a) Boundary-fill and Flood-fill

Both are seed-fill area-filling algorithms that start from an interior seed pixel and spread to neighbours (4-connected or 8-connected).

• Boundary-fill: fills the region by recursively colouring pixels outward from the seed until a specified boundary colour is reached. It stops when it hits the boundary colour or the new fill colour. Used when the region is bounded by a single known colour.
• Flood-fill: replaces all connected pixels that have a specified old (interior) colour with the new colour, regardless of the boundary colour. Used when the interior has one colour but the boundary is multi-coloured (e.g. recolouring a region).

Key difference: boundary-fill is defined by the boundary colour, flood-fill by the interior (old) colour.

(b) Aliasing and anti-aliasing

• Aliasing: the distortion artifacts (staircase/jagged edges on lines, loss of fine detail) caused by representing continuous geometry on a discrete pixel grid with insufficient sampling.
• Anti-aliasing techniques to reduce it:
  • Supersampling (SSAA): render at higher resolution and average down.
  • Area sampling: set pixel intensity proportional to the fraction of the pixel area covered by the primitive.
  • Pixel-weighting / filtering: weight a pixel's contribution by a filter centred on it. These smooth edges by assigning intermediate intensities to boundary pixels.

(c) Scan-line polygon fill

Fills a polygon one horizontal scan line at a time:

1. For each scan line $y$, find the intersections of that line with all polygon edges.
2. Sort the intersection $x$-values left to right.
3. Pair them up (1–2, 3–4, …) and fill the pixels between each pair (odd-parity rule — pixels inside the polygon lie between an odd and even crossing). An edge table and an active-edge list make the intersection computation incremental (each new $x = x + 1/m$). Vertices are counted carefully so that local maxima/minima are not double-counted.