BE Computer Engineering (IOE, TU) Computer Graphics (IOE, CT 605 / ENCT 201) Question Paper 2078 Nepal

(a) Bresenham's line algorithm, decision parameter (slope 0 < m < 1) [7]

We want to scan-convert a line from $(x_0,y_0)$ to $(x_1,y_1)$ with $0<m<1$. Since $m<1$, $x$ is the fast (driving) axis: we step $x$ by 1 each iteration and decide whether $y$ stays the same or increases by 1.

The line equation is $y = mx + c$, where $m = \dfrac{\Delta y}{\Delta x}$, $\Delta x = x_1-x_0$, $\Delta y = y_1-y_0$.

At step $k$ the current pixel is $(x_k, y_k)$. The next $x$ is $x_{k}+1$; the candidates are the lower pixel $(x_k+1, y_k)$ and the upper pixel $(x_k+1, y_k+1)$. The true line at $x_k+1$ has $y = m(x_k+1)+c$.

Let $d_1$ and $d_2$ be the vertical distances from the true line down to $y_k$ and up to $y_k+1$:

$$d_1 = y - y_k = m(x_k+1)+c - y_k$$ $$d_2 = (y_k+1) - y = y_k+1 - m(x_k+1) - c$$

We choose the lower pixel if $d_1 < d_2$, i.e. if $d_1 - d_2 < 0$:

$$d_1 - d_2 = 2m(x_k+1) - 2y_k + 2c - 1$$

Substitute $m=\Delta y/\Delta x$ and multiply by $\Delta x$ (positive, so the sign is preserved) to keep everything in integer arithmetic. Define the decision parameter:

$$p_k = \Delta x\,(d_1-d_2) = 2\Delta y\,x_k - 2\Delta x\,y_k + (2\Delta y + \Delta x(2c-1))$$

The constant terms collect into $2\Delta y - \Delta x$, giving the initial value:

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

Decision rule:

• If $p_k < 0$: choose lower pixel $(x_k+1,\,y_k)$, and $p_{k+1} = p_k + 2\Delta y$.
• If $p_k \ge 0$: choose upper pixel $(x_k+1,\,y_k+1)$, and $p_{k+1} = p_k + 2\Delta y - 2\Delta x$.

These recurrences use only integer additions of the precomputed constants $2\Delta y$ and $2\Delta y-2\Delta x$ — no multiplication or floating point per step.

Generalisation to arbitrary slope

The derivation above assumes $0<m<1$ and $x_1>x_0$. For a general line:

1. $|m|>1$ (steep lines): swap roles of $x$ and $y$ — step $y$ by 1 and decide on $x$. The decision parameter becomes $p_0 = 2\Delta x - \Delta y$ with $\Delta x,\Delta y$ roles interchanged.
2. Negative slope: if $\Delta y<0$ (or $\Delta x<0$) the chosen pixel is decremented instead of incremented along that axis.
3. Direction: if the endpoints are given in the wrong order, swap them so we always march in the positive driving direction.

Thus, by choosing the driving axis as the one with the larger absolute change and adjusting the increment signs, the same integer decision logic handles all eight octants.

(a) Homogeneous coordinates and reflection about y = x + 2 [8]

Why homogeneous coordinates? In 2D, a point $(x,y)$ is written as $(x,y,1)$, i.e. an extra coordinate is appended. The reasons are:

• Translation becomes a matrix multiplication. Translation is additive in Cartesian form and cannot be expressed as a $2\times2$ matrix; in homogeneous form it is a $3\times3$ matrix, so it can be combined uniformly with rotation, scaling, etc.
• Composite transformations can be pre-multiplied into a single matrix, so a sequence of operations is applied with one matrix-vector product per point.
• They also allow representation of points at infinity (w = 0) and unify affine and projective (perspective) transformations.

Reflection about the line $y = x + 2$: The line has slope 1 and y-intercept 2. We reduce it to reflection about the line $y=x$ (which passes through the origin) by the sequence:

1. Translate so the line passes through the origin. The line crosses the y-axis at $(0,2)$; translate by $(0,-2)$:

$$T_1=\begin{bmatrix}1&0&0\\0&1&-2\\0&0&1\end{bmatrix}$$

Now the line becomes $y=x$.

2. Reflect about $y=x$ (swap x and y):

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

3. Translate back by $(0,+2)$:

$$T_2=\begin{bmatrix}1&0&0\\0&1&2\\0&0&1\end{bmatrix}$$

The composite matrix (applied right-to-left to a column point) is:

$$M = T_2\cdot R_{y=x}\cdot T_1$$

Computing $R_{y=x}\cdot T_1 = \begin{bmatrix}0&1&-2\\1&0&0\\0&0&1\end{bmatrix}$, then pre-multiplying by $T_2$:

$$\boxed{M=\begin{bmatrix}0&1&-2\\1&0&2\\0&0&1\end{bmatrix}}$$

Check: a point on the line, say $(0,2)$, maps to $(0\cdot0+1\cdot2-2,\;0+0+2)=(0,2)$ — fixed, as expected.

(b) Rotate triangle 90° anticlockwise about (4, 2) [4]

Procedure: translate pivot to origin, rotate $90^\circ$ CCW $(x,y)\to(-y,x)$, translate back.

With pivot $(4,2)$, a point $(x,y)$ maps to $\big(4-(y-2),\;2+(x-4)\big)$.

Result: $A'(4,0),\;B'(4,4),\;C'(0,2)$.

(a) Parallel vs perspective projection; perspective matrix; vanishing points [8]

Distinction:

Derivation of the perspective matrix: Let the projection plane be $z=0$ and the centre of projection lie on the z-axis at $(0,0,-d)$ (so the plane is at distance $d$ from the COP). Consider a point $P(x,y,z)$. The projector from the COP through $P$ meets the plane $z=0$ at $P'(x_p,y_p,0)$.

Using similar triangles along the projector:

$$\frac{x_p}{x}=\frac{d}{z+d}\quad\Rightarrow\quad x_p=\frac{x}{1+z/d}$$ $$y_p=\frac{y}{1+z/d}$$

In homogeneous coordinates this division by $(1+z/d)$ is produced by placing $1/d$ in the matrix and dividing by the homogeneous coordinate $w$:

$$\begin{bmatrix}x_p'\\y_p'\\z_p'\\w\end{bmatrix}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&0\\0&0&\tfrac{1}{d}&1\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}=\begin{bmatrix}x\\y\\0\\\tfrac{z}{d}+1\end{bmatrix}$$

Dividing by $w=\frac{z}{d}+1$ gives $x_p=\dfrac{x}{1+z/d},\;y_p=\dfrac{y}{1+z/d}$, confirming the result.

Vanishing points: Lines that are parallel in the scene but not parallel to the projection plane appear to converge to a common point called a vanishing point. The number of principal vanishing points (one, two, or three) equals the number of the three principal axes that pierce the projection plane, giving one-, two-, and three-point perspective. This convergence is what produces the sense of depth.

(b) Rotation about an axis parallel to z through (x0, y0, 0) by θ [4]

Translate the axis to the z-axis, rotate about z, translate back:

$$R = T(x_0,y_0,0)\cdot R_z(\theta)\cdot T(-x_0,-y_0,0)$$ $$R=\begin{bmatrix}\cos\theta & -\sin\theta & 0 & x_0(1-\cos\theta)+y_0\sin\theta\\ \sin\theta & \cos\theta & 0 & y_0(1-\cos\theta)-x_0\sin\theta\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{bmatrix}$$

The $z$-coordinate is unchanged because the axis is parallel to the z-axis.

(a) Cohen–Sutherland line clipping algorithm [7]

The algorithm clips a line against an axis-aligned rectangular window with bounds $x_{min},x_{max},y_{min},y_{max}$. The plane is divided into nine regions, and each endpoint is assigned a 4-bit region code (outcode):

Bit 1 (8) : y > ymax   (Top)
Bit 2 (4) : y < ymin   (Bottom)
Bit 3 (2) : x > xmax   (Right)
Bit 4 (1) : x < xmin   (Left)

A bit is 1 when the point lies on that side of the window; the central (inside) region has code 0000.

1001 | 1000 | 1010
-----+------+-----
0001 | 0000 | 0010
-----+------+-----
0101 | 0100 | 0110

Significance of outcodes: they let us test acceptance/rejection with cheap bit operations:

• Trivial acceptance: both endpoints have code 0000 (logical OR = 0). The whole line lies inside; draw it.
• Trivial rejection: the bitwise AND of the two codes is non-zero. Both endpoints lie outside the same boundary, so the line cannot cross the window; discard it.
• Otherwise (OR ≠ 0 and AND = 0): the line may cross the window. Pick the endpoint that is outside (non-zero code), compute its intersection with one violated boundary, replace that endpoint with the intersection, recompute its outcode, and repeat until trivial accept or reject.

Intersections use the line's slope $m=\dfrac{y_2-y_1}{x_2-x_1}$:

• 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 + \dfrac{y_e - y_1}{m}$.

(b) Clip P1(−10, 30) → P2(40, 5), window (0,0)–(30,30) [5]

Slope $m = \dfrac{5-30}{40-(-10)} = \dfrac{-25}{50} = -0.5$.

Outcodes:

• P1(−10, 30): $x<0$ → Left bit; $y=30$ is on edge (not > 30), $y$ ok ⇒ code 0001.
• P2(40, 5): $x=40>30$ → Right bit; $y$ ok ⇒ code 0010.

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

Clip P1 against Left edge $x=0$:

$$y = 30 + (-0.5)(0-(-10)) = 30 - 5 = 25 \Rightarrow P_1' = (0, 25)$$

New outcode of $(0,25)$ = 0000 (inside).

Clip P2 against Right edge $x=30$:

$$y = 30 + (-0.5)(30-(-10)) = 30 - 20 = 10 \Rightarrow P_2' = (30, 10)$$

New outcode of $(30,10)$ = 0000 (inside).

Both endpoints now inside ⇒ trivial acceptance.

Clipped segment: from (0, 25) to (30, 10).

Z-buffer (depth-buffer) algorithm

The Z-buffer is an image-space hidden-surface removal method. Two buffers of the same resolution as the frame buffer are maintained:

• a depth buffer storing, for each pixel, the depth (z) of the closest surface seen so far, and
• the frame buffer storing the corresponding colour.

Algorithm:

Initialise depth_buffer[x][y] = z_max (farthest)  for all pixels
Initialise frame_buffer[x][y] = background colour
for each polygon:
    for each pixel (x, y) covered by the polygon:
        compute z = depth of the polygon at (x, y)
        if z < depth_buffer[x][y]:        // nearer than stored
            depth_buffer[x][y] = z
            frame_buffer[x][y] = surface colour at (x, y)

Depth across a polygon is found incrementally: $z_{x+1}=z_x-\dfrac{a}{c}$ along a scan line, so no per-pixel plane evaluation is needed.

Advantage: simple, handles any number of polygons in arbitrary order, easily hardware-accelerated. Disadvantage: requires a large extra depth buffer and writes every covered pixel (high memory/over-draw); limited z-precision can cause z-fighting.

Comparison with back-face detection

Back-face detection removes polygons whose outward normal $\mathbf{N}$ points away from the viewer, i.e. where $\mathbf{N}\cdot\mathbf{V} > 0$ (equivalently $z$-component of $\mathbf{N} \le 0$ in view space). It is an object-space test.

Phong illumination model

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

$$I = \underbrace{k_a I_a}_{\text{ambient}} \;+\; \underbrace{k_d I_l (\mathbf{N}\cdot\mathbf{L})}_{\text{diffuse}} \;+\; \underbrace{k_s I_l (\mathbf{R}\cdot\mathbf{V})^{n}}_{\text{specular}}$$

where:

• $I_a$ = ambient light intensity, $I_l$ = point-source intensity;

• $k_a, k_d, k_s$ = ambient, diffuse and specular reflection coefficients;

• $\mathbf{N}$ = unit surface normal, $\mathbf{L}$ = unit direction to the light, $\mathbf{R}$ = direction of perfect reflection of $\mathbf{L}$ about $\mathbf{N}$, $\mathbf{V}$ = direction to the viewer;

• $n$ = specular (shininess) exponent — larger $n$ gives a smaller, sharper highlight.

• Ambient models uniform background light (no direction).

• Diffuse (Lambert's cosine law) depends on the angle between $\mathbf{N}$ and $\mathbf{L}$; viewpoint-independent.

• Specular produces the shiny highlight; depends on the angle between $\mathbf{R}$ and $\mathbf{V}$.

With multiple light sources the diffuse and specular terms are summed over all sources, and the term is clamped to non-negative values.

Gouraud vs Phong shading

Bezier curves

A Bezier curve is a parametric curve defined by a set of $n+1$ control points $P_0,P_1,\dots,P_n$. The curve is a weighted blend of the control points using Bernstein basis polynomials:

$$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},\quad 0\le u\le 1$$

Important properties

1. The curve passes through the first and last control points ($P(0)=P_0,\;P(1)=P_n$) but generally not the intermediate ones.
2. It lies entirely within the convex hull of its control points.
3. It is tangent to $P_0P_1$ at the start and to $P_{n-1}P_n$ at the end.
4. The basis functions are non-negative and sum to 1 (partition of unity) ⇒ affine invariance.
5. The curve has the same degree structure but offers only global control — moving any control point changes the whole curve.
6. It is invariant under affine transformations (transform the control points, not the curve).

Point at u = 0.5 (cubic, n = 3)

Cubic Bezier: $P(u)=(1-u)^3P_0+3(1-u)^2u\,P_1+3(1-u)u^2P_2+u^3P_3$.

At $u=0.5$ the blending weights are $0.125,\,0.375,\,0.375,\,0.125$.

x: $0.125(1)+0.375(2)+0.375(5)+0.125(6)=0.125+0.75+1.875+0.75=3.5$

y: $0.125(1)+0.375(4)+0.375(4)+0.125(1)=0.125+1.5+1.5+0.125=3.25$

$$\boxed{P(0.5)=(3.5,\;3.25)}$$

Scan-line polygon fill algorithm

The algorithm fills a polygon by processing the image one horizontal scan line at a time. For a given scan line $y$, it finds all points where the scan line crosses polygon edges, sorts these x-intersections, and fills the spans between pairs of intersections (odd–even / parity rule).

Steps:

1. Build the Edge Table (ET).
2. For y from y_min to y_max:
   a. Move edges whose y_min == y from ET into the Active Edge List (AEL).
   b. Remove edges from AEL whose y_max == y.
   c. Sort AEL by current x.
   d. Fill pixels between successive pairs of x: (x1,x2),(x3,x4),...
   e. For each edge in AEL, update x += 1/m  (incremental: x_{next}=x+inverse slope).

Edge Table (ET): a list bucketed by the smaller y (y_min) of each edge. Each entry stores: $y_{max}$ of the edge, the $x$ at $y_{min}$, and the inverse slope $1/m=\Delta x/\Delta y$. Horizontal edges are excluded. The ET tells the algorithm when each edge becomes relevant.

Active Edge List (AEL): the set of edges that the current scan line actually intersects. As $y$ increases, edges are added from the ET (when $y=y_{min}$) and deleted (when $y=y_{max}$). The AEL is kept sorted by $x$ so that consecutive entries form fill spans.

Handling vertices (local minima / maxima)

A vertex shared by two edges can wrongly count as one or two intersections, breaking the parity rule. Convention:

• At a vertex where the two edges go in the same y-direction (a local minimum or maximum, the edges form a 'spike'), count the vertex as two intersections.
• At a vertex where the edges go in opposite y-directions (the polygon simply passes through), count it as one intersection.

In practice this is implemented by shortening one of the two edges by one scan line (decrement its $y_{max}$ or adjust the endpoint) at a monotone vertex so that exactly one intersection is recorded; at a true extremum both edges are kept, yielding two. This guarantees correct odd–even spans.

Sutherland–Hodgeman polygon clipping

This algorithm clips an arbitrary polygon against a convex clipping window by clipping the entire polygon successively against each window boundary, one at a time (e.g. left, then right, then bottom, then top). The output polygon (list of vertices) produced after clipping against one boundary becomes the input for the next boundary. This is the divide-and-conquer on edges approach.

For a single boundary, the polygon's vertices are processed as a sequence of edges $(S \to E)$, where $S$ is the previous vertex and $E$ the current one. Each vertex is classified as inside or outside the boundary, giving four cases:

Four cases for an edge against one boundary

Let the boundary divide the plane into an inside half (window side) and outside half. For edge from start point $S$ to end point $E$:

Diagram (described): imagine a vertical clip line, inside to its left.

• Case 1: both $S$ and $E$ on the left → keep $E$.
• Case 2: $S$ on left, $E$ on right → the edge crosses the line; output only the crossing point $I$.
• Case 3: both on the right → the edge is fully outside; output nothing.
• Case 4: $S$ on right, $E$ on left → the edge re-enters; output the crossing point $I$ first, then $E$.

The intersection $I$ is found by line–boundary intersection (parametric or slope form). After all four boundaries are processed, the accumulated vertex list is the clipped polygon. Limitation: for concave polygons it may produce spurious connecting edges, which require post-processing or the Weiler–Atherton algorithm.

Raster scan vs Random (Vector) scan

Aspect ratio

The aspect ratio is the ratio of the screen's (or image's) horizontal extent to its vertical extent, $\text{aspect} = \dfrac{\text{width}}{\text{height}}$ (e.g. 4:3, 16:9). Equivalently it can be stated as the ratio of vertical to horizontal points needed to draw equal-length lines; if pixels are not square, the aspect ratio must be accounted for so that circles do not appear as ellipses.

Frame buffer

The frame buffer (refresh buffer) is a dedicated block of memory that holds the intensity (and colour) value of every pixel of a raster display. The display controller scans the frame buffer in synchronism with the beam to refresh the screen. Its size is $\text{width}\times\text{height}\times \text{bits-per-pixel}$; the bits per pixel (bit depth) determine the number of representable colours/intensities (e.g. 8 bits → 256 levels).

B-spline curve

A B-spline (Basis-spline) is a piecewise polynomial parametric curve defined by control points $P_0,\dots,P_n$ and a set of basis functions $N_{i,k}(u)$ of order $k$ (degree $k-1$):

$$P(u)=\sum_{i=0}^{n} P_i\,N_{i,k}(u)$$

The basis functions are built from a knot vector $\{u_0,u_1,\dots\}$ via the Cox–de Boor recurrence. Crucially, the curve's degree $(k-1)$ is independent of the number of control points, unlike a Bezier curve whose degree is fixed by the point count.

Local control

Each basis function $N_{i,k}(u)$ is non-zero only over a limited span of $k$ knot intervals. Therefore each control point $P_i$ influences only a small portion of the curve. Moving one control point alters only the segment(s) within that point's support, leaving the rest of the curve unchanged — this is local control. (A Bezier curve has global control: moving any point reshapes the whole curve.)

Two advantages of B-splines over Bezier curves

1. Local control: editing one control point affects only a local region, not the entire curve.
2. Degree independent of control-point count: you can add control points to refine the shape without raising the polynomial degree, keeping computation stable; B-splines also join segments with built-in continuity ($C^{k-2}$). (NURBS, a rational B-spline, can additionally represent exact conics such as circles.)

Depth-sorting (Painter's) algorithm

The Painter's algorithm is an object-space visible-surface method that draws polygons in order of decreasing depth — farthest first, nearest last — so that nearer surfaces paint over farther ones, just as a painter lays down background before foreground.

Steps:

1. Sort all polygons by their largest depth (z) value — farthest from viewer first.
2. Resolve any ambiguities/overlaps among polygons with overlapping z-extents.
3. Scan-convert (draw) the polygons in this back-to-front order into the frame buffer.

When simple depth ordering fails

Simply sorting by depth is not always sufficient. For two polygons P (front in the list) and Q, after the initial sort a series of overlap tests must hold; trouble arises when:

• Their z-extents overlap and we cannot tell which is in front;
• Polygons cyclically overlap (P is in front of Q, Q in front of R, R in front of P) — no valid ordering exists;
• Polygons interpenetrate (pierce each other).

Resolution

For each pair whose depth ranges overlap, perform up to five tests in order; if any succeeds the order is fine:

1. Their x-extents (bounding boxes) do not overlap.
2. Their y-extents do not overlap.
3. P is entirely on the far side of Q's plane.
4. Q is entirely on the near side of P's plane.
5. Their projections onto the view plane do not overlap.

If all tests fail, swap the two polygons and retry. For genuine cyclic overlap or interpenetration, split one polygon along the plane of the other so that the resulting pieces can be unambiguously ordered, then continue. (When robust handling of such cases is required, a Z-buffer is often preferred.)