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

(a) Derivation of Bresenham's decision parameter ($0<m<1$) [8]

Consider a line $y = mx + c$ with slope $m = \dfrac{dy}{dx}$ where $dy = y_2-y_1$, $dx = x_2-x_1$ and $0<m<1$. Since the slope is less than 1, $x$ is the fast (driving) axis: at every step we increment $x$ by 1 and decide whether $y$ stays the same or increases by 1.

Suppose pixel $(x_k, y_k)$ has just been plotted. At the next column $x_{k+1}=x_k+1$ the true line is at $y = m(x_k+1)+c$. The two candidate pixels are the lower $(x_k+1,\;y_k)$ and the upper $(x_k+1,\;y_k+1)$.

Let $d_{lower}$ and $d_{upper}$ be the vertical distances from the true line to these candidates:

$$d_{lower} = y - y_k = m(x_k+1)+c - y_k$$ $$d_{upper} = (y_k+1) - y = y_k+1 - m(x_k+1) - c$$

The difference decides the closer pixel:

$$d_{lower}-d_{upper} = 2m(x_k+1) - 2y_k + 2c - 1$$

Substituting $m = dy/dx$ and multiplying by $dx\;(>0)$ so the test stays integer, define the decision parameter:

$$p_k = dx\,(d_{lower}-d_{upper}) = 2\,dy\cdot x_k - 2\,dx\cdot y_k + b$$

where $b = 2\,dy + dx(2c-1)$ is constant. Because $dx>0$, the sign of $p_k$ equals the sign of $(d_{lower}-d_{upper})$:

• If $p_k < 0$ → lower pixel is closer → choose $(x_k+1,\;y_k)$.
• If $p_k \ge 0$ → upper pixel is closer → choose $(x_k+1,\;y_k+1)$.

Incremental update. Writing $p_{k+1}-p_k = 2\,dy(x_{k+1}-x_k) - 2\,dx(y_{k+1}-y_k)$ and $x_{k+1}-x_k=1$:

$$p_{k+1} = p_k + 2\,dy - 2\,dx\,(y_{k+1}-y_k)$$

• If $p_k<0$ (lower, $y$ unchanged): $\boxed{p_{k+1}=p_k+2\,dy}$
• If $p_k\ge 0$ (upper, $y$ increases): $\boxed{p_{k+1}=p_k+2\,dy-2\,dx}$

Initial parameter. Starting at $(x_1,y_1)$ on the line ($c = y_1 - m x_1$), substitution gives the simple integer start:

$$\boxed{p_0 = 2\,dy - dx}$$

Only integer additions are used, which is why Bresenham's algorithm is fast.

(b) Trace from $A(2,3)$ to $B(9,8)$ [4]

$dx = 9-2 = 7,\quad dy = 8-3 = 5,\quad m=5/7\;(0<m<1).$

Constants: $2dy = 10,\quad 2(dy-dx)=2(5-7)=-4,\quad p_0 = 2dy-dx = 10-7 = 3.$

Pixels plotted: $(2,3),(3,4),(4,4),(5,5),(6,6),(7,7),(8,7),(9,8)$ — terminating correctly at $B(9,8)$.

(a) Rotation of $90^\circ$ CCW about $P(2,2)$ [8]

Rotation about an arbitrary point is a composite transformation: translate the pivot to the origin, rotate, then translate back:

$$M = T(2,2)\cdot R(90^\circ)\cdot T(-2,-2)$$

With $\theta=90^\circ$, $\cos\theta=0,\;\sin\theta=1$:

$$T(-2,-2)=\begin{bmatrix}1&0&-2\\0&1&-2\\0&0&1\end{bmatrix},\;\; R(90^\circ)=\begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix},\;\; T(2,2)=\begin{bmatrix}1&0&2\\0&1&2\\0&0&1\end{bmatrix}$$

Composite matrix:

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

(giving $x' = -y+4,\; y' = x$). Applying to each vertex $\begin{bmatrix}x&y&1\end{bmatrix}^T$:

Transformed triangle: $A'(3,1),\;B'(3,4),\;C'(1,2)$.

(b) Why homogeneous coordinates [4]

A point $(x,y)$ is represented as $(x,y,1)$, i.e. a 2D point becomes a 3-component vector.

• Reason: Rotation, scaling and shearing are linear and can be written as $2\times2$ matrix multiplications, but translation is additive ($x'=x+t_x$) and cannot be expressed as a $2\times2$ multiplication. By adding a third coordinate, translation becomes a $3\times3$ matrix multiplication, so all transformations are uniform $3\times3$ matrices and can be composed by simple matrix multiplication.

• Translation in matrix form:

$$\begin{bmatrix}x'\\y'\\1\end{bmatrix}=\begin{bmatrix}1&0&t_x\\0&1&t_y\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}=\begin{bmatrix}x+t_x\\y+t_y\\1\end{bmatrix}$$

(a) Parallel vs Perspective projection + perspective matrix [8]

Derivation (projection onto $z=0$, COP at $(0,0,-d)$ on the negative z-axis).

Let a 3D point be $P(x,y,z)$. The projector is the line joining the COP $C(0,0,-d)$ to $P$. We find where this line meets the plane $z=0$. Parametrically a point on the line is

$$X = 0 + t(x-0),\quad Y = t\,y,\quad Z = -d + t(z+d).$$

Set $Z=0$: $\;t = \dfrac{d}{z+d}$. Then

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

In homogeneous coordinates this division by $(1+z/d)$ is captured by:

$$\begin{bmatrix}x_h\\y_h\\z_h\\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 through by $w = \tfrac{z}{d}+1$ recovers $x_p = \dfrac{x}{1+z/d}$, $y_p=\dfrac{y}{1+z/d}$, $z_p=0$. The non-zero entry $\tfrac1d$ in the bottom row is what produces perspective foreshortening; if $d\to\infty$ that entry vanishes and the matrix degenerates to a parallel (orthographic) projection.

(b) Scaling about an arbitrary fixed point $(x_f,y_f,z_f)$ in 3D [4]

$$M = T(x_f,y_f,z_f)\cdot S(s_x,s_y,s_z)\cdot T(-x_f,-y_f,-z_f)$$ $$M=\begin{bmatrix}s_x&0&0&x_f(1-s_x)\\0&s_y&0&y_f(1-s_y)\\0&0&s_z&z_f(1-s_z)\\0&0&0&1\end{bmatrix}$$

(a) Cohen–Sutherland line clipping [8]

The plane is divided into 9 regions by extending the window edges; each region has a 4-bit outcode $b_3b_2b_1b_0 =$ (Top, Bottom, Right, Left):

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

Algorithm: compute outcodes for both endpoints.

1. If both codes are $0000$ → trivially accept (line wholly inside).
2. If logical AND of the codes $\ne 0000$ → trivially reject (both on same outside side).
3. Otherwise pick an endpoint that is outside, find its intersection with the corresponding window edge, replace the endpoint with the intersection, recompute its outcode, and repeat until accept or reject.

Intersections use: for a vertical edge $x=x_e$, $y = y_1 + m(x_e-x_1)$; for a horizontal edge $y=y_e$, $x = x_1 + (y_e-y_1)/m$.

Given: $P_1(40,15)$, $P_2(75,45)$, window $(50,10)$–$(80,40)$. Slope $m=\dfrac{45-15}{75-40}=\dfrac{30}{35}=\dfrac{6}{7}$.

• Outcode($P_1$): $x=40<50$ → Left = 0001.
• Outcode($P_2$): $y=45>40$ → Top = 1000.
• AND $=0000$ → not trivially rejected; not both zero → clip.

Clip $P_1$ against left edge $x=50$:

$$y = 15 + \tfrac{6}{7}(50-40)=15+\tfrac{60}{7}=15+8.57=23.57.$$

New $P_1'=(50,\,23.57)$, outcode $0000$ (inside).

Clip $P_2$ against top edge $y=40$:

$$x = 40 + \tfrac{40-15}{6/7}=40+\tfrac{25\cdot7}{6}=40+29.17=69.17.$$

New $P_2'=(69.17,\,40)$, outcode $0000$.

Both endpoints now inside → accept.

Clipped segment: from $(50,\;23.57)$ to $(69.17,\;40)$.

(b) Limitation of Sutherland–Hodgeman with a concave polygon [4]

The Sutherland–Hodgeman algorithm clips the polygon successively against each window edge, treating the output as a single connected vertex list. For a concave polygon this can produce extraneous connecting edges: when the clipped result should split into two or more separate pieces, the algorithm instead joins them with a spurious line that runs along the window boundary, giving an incorrect filled region. The remedy is to split the concave polygon into convex pieces first, or to use the Weiler–Atherton algorithm, which handles concave polygons correctly.

Midpoint Circle Drawing Algorithm [6]

For a circle of radius $r$ centred at the origin the implicit function is

$$f_{circle}(x,y) = x^2 + y^2 - r^2,$$

which is $<0$ inside, $=0$ on, and $>0$ outside the circle. The algorithm works in the second octant (from $(0,r)$ to the $45^\circ$ line), where $x$ is the driving axis. After plotting $(x_k,y_k)$ we test the midpoint $M=(x_k+1,\;y_k-\tfrac12)$ between the two candidate pixels $E=(x_k+1,y_k)$ and $SE=(x_k+1,y_k-1)$:

$$p_k = f_{circle}\!\left(x_k+1,\;y_k-\tfrac12\right) = (x_k+1)^2 + \left(y_k-\tfrac12\right)^2 - r^2.$$

• If $p_k<0$ → midpoint inside → choose $E$ ($y$ unchanged).
• If $p_k\ge0$ → midpoint outside → choose $SE$ ($y$ decreases).

Incremental updates:

• if $p_k<0$: $\;p_{k+1}=p_k+2x_{k+1}+1$
• if $p_k\ge0$: $\;p_{k+1}=p_k+2x_{k+1}+1-2y_{k+1}$

Initial value at $(0,r)$: $\;p_0 = \tfrac54 - r \approx 1 - r$.

Eight-way symmetry: each computed $(x,y)$ gives 8 pixels: $(\pm x,\pm y)$ and $(\pm y,\pm x)$, so only one octant need be computed.

Trace for $r=8$ (first octant, $p_0 = 1-8 = -7$)

First-octant pixels: $(0,8),(1,8),(2,8),(3,7),(4,7),(5,6),(6,5)$ (computation stops when $x\ge y$).

Bézier Curve [6]

Definition. A Bézier curve of degree $n$ is a parametric curve defined by $n+1$ control points $P_0,P_1,\dots,P_n$ as a weighted blend of those points using Bernstein basis polynomials, for $t\in[0,1]$:

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

Cubic Bézier ($n=3$) blending functions:

$$B_{0,3}(t)=(1-t)^3,\quad B_{1,3}(t)=3t(1-t)^2,\quad B_{2,3}(t)=3t^2(1-t),\quad B_{3,3}(t)=t^3$$

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

Three important properties:

1. Endpoint interpolation – the curve passes exactly through the first and last control points: $P(0)=P_0$, $P(1)=P_3$.
2. Convex-hull property – the curve lies entirely within the convex hull of its control points (since the Bernstein basis is non-negative and sums to 1).
3. Tangency at endpoints – the curve is tangent to $P_0P_1$ at the start and to $P_{n-1}P_n$ at the end, which makes smooth joining of segments easy. (Also: affine invariance and no local control.)

Z-Buffer (Depth-Buffer) Algorithm [6]

The Z-buffer is an image-space hidden-surface removal method using two buffers of the same resolution as the frame buffer:

• Frame (colour) buffer – stores the colour of each pixel.
• Depth (Z) buffer – stores the $z$ (depth) of the nearest surface seen so far at each pixel.

Algorithm:

Initialise depth-buffer[x][y] = z_max (far)  for all pixels
Initialise frame-buffer[x][y] = background colour
for each polygon:
    for each pixel (x,y) it covers:
        compute depth z of the polygon at (x,y)   // by interpolation
        if z < depth-buffer[x][y]:                // nearer than stored
            depth-buffer[x][y] = z
            frame-buffer[x][y] = surface colour at (x,y)

The depth across a polygon is found incrementally: $z' = z - \dfrac{a}{c}$ moving one pixel in $x$ (where $ax+by+cz+d=0$ is the plane), so no per-pixel division is needed.

Advantages (vs scan-line):

• Very simple to implement; handles any number of polygons in arbitrary order (no presorting).
• Easily implemented in hardware → standard in GPUs.
• Time is roughly linear in the number of polygons.

Disadvantages (vs scan-line):

• Requires large extra memory for the depth buffer.
• Finite depth precision causes z-fighting (aliasing of close/coplanar surfaces).
• Wastes work rendering pixels later overwritten; does not handle transparency or anti-aliasing directly, whereas the scan-line method processes one scan line at a time using much less memory.

Phong Illumination Model [6]

The Phong model computes the reflected intensity at a surface point as the sum of three components — ambient + diffuse + 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 $\mathbf N$ = surface normal, $\mathbf L$ = direction to light, $\mathbf R$ = mirror-reflection direction of $\mathbf L$ about $\mathbf N$, $\mathbf V$ = direction to viewer (all unit vectors), and $I_a,I_l$ are ambient and source intensities.

1. Ambient term ($k_a I_a$). Models the uniform background light scattered many times in the scene. It is constant and independent of light/viewer direction, ensuring that surfaces facing away from the light are not completely black. $k_a$ is the ambient reflection coefficient.

2. Diffuse term ($k_d I_l(\mathbf N\cdot\mathbf L)$). Models Lambertian (matte) reflection scattered equally in all directions. Its brightness depends only on the angle between $\mathbf N$ and $\mathbf L$ (i.e. $\cos\theta=\mathbf N\cdot\mathbf L$), being maximum when the light hits head-on and zero when grazing. It is view-independent; $k_d$ is the diffuse coefficient (surface colour). If $\mathbf N\cdot\mathbf L<0$ the term is clamped to 0.

3. Specular term ($k_s I_l(\mathbf R\cdot\mathbf V)^n$). Models the shiny highlight of glossy surfaces. It is strongest when the viewer looks along the reflection direction ($\mathbf R\approx\mathbf V$) and falls off with the shininess exponent $n$ — large $n$ gives a small, sharp highlight; small $n$ a broad, dull one. It is view-dependent; $k_s$ is the specular coefficient.

For multiple lights the diffuse and specular contributions are summed over all sources.

Gouraud vs Phong Shading [6]

Procedure (Gouraud): compute a normal at each vertex (average of adjacent face normals), apply the illumination model to get a colour at each vertex, then bilinearly interpolate those colours along edges and scan lines.

Procedure (Phong): interpolate the normal vectors across the polygon (re-normalising each), and apply the full illumination model at each pixel.

Which renders specular highlights correctly → Phong shading.

Why: A specular highlight is a small, sharply varying bright spot. In Gouraud shading the highlight is sampled only at the vertices; if the highlight falls in the interior of a polygon (between vertices), the vertex intensities are low and linear colour interpolation simply averages them, so the highlight is missed or smeared. Phong shading interpolates the normals and recomputes the $(\mathbf R\cdot\mathbf V)^n$ term per pixel, so the peak of the highlight is captured wherever it occurs on the surface.

Boundary-Fill and Flood-Fill [6]

Both are seed-fill algorithms: starting from an interior seed pixel they recursively spread the fill colour to neighbouring pixels.

Boundary-fill. Used when the region is defined by a specific boundary colour. Starting at a seed inside the region, set it to the fill colour and recurse to neighbours, stopping when a pixel is the boundary colour or already filled.

boundaryFill(x, y, fillColour, boundaryColour):
    c = getPixel(x, y)
    if c != boundaryColour and c != fillColour:
        setPixel(x, y, fillColour)
        // 4-connected neighbours
        boundaryFill(x+1, y, ...); boundaryFill(x-1, y, ...)
        boundaryFill(x, y+1, ...); boundaryFill(x, y-1, ...)

Flood-fill. Used when a region is defined by a single interior colour (no defined boundary). It replaces all connected pixels having the old interior colour with the new colour, stopping when a pixel no longer matches the old colour.

floodFill(x, y, oldColour, newColour):
    if getPixel(x, y) == oldColour:
        setPixel(x, y, newColour)
        floodFill on the 4 (or 8) neighbours

4-connected vs 8-connected:

• 4-connected: recurse to the 4 edge neighbours only — right, left, up, down. Simpler, but it cannot pass through regions connected only diagonally, so thin diagonal gaps in a boundary leave parts unfilled.
• 8-connected: recurse to all 8 neighbours — the 4 edge plus 4 diagonal (corner) pixels. It fills more completely and handles diagonally connected regions, but a single-pixel diagonal boundary may leak the fill outside the intended area.

Diagrams (described):

 4-connected:        8-connected:
      N                NW  N  NE
   W  P  E              W  P  E
      S                SW  S  SE

The centre pixel $P$ reaches only N/S/E/W in the 4-connected case, and additionally the four diagonal corners in the 8-connected case.

(a) Sutherland–Hodgeman polygon clipping [4]

The polygon is clipped against the four window edges one at a time (left, right, bottom, top); the output vertex list from one edge becomes the input to the next. For each edge, each polygon edge $V_i \to V_{i+1}$ is examined and 0, 1 or 2 vertices are output according to four cases (in = inside the clip edge, out = outside):

After all four edges are processed, the remaining vertex list is the clipped polygon. (It works correctly for convex polygons; concave ones may need splitting.)

(b) Text clipping strategies [2]

• All-or-none string clipping: the whole string is kept only if its entire bounding box lies inside the window; otherwise the whole string is discarded.
• All-or-none character clipping: each character is kept or rejected as a unit based on whether its bounding box is fully inside.
• Character (component) clipping: individual characters are clipped at the boundary — outline (stroke) text is clipped like line/curve primitives, and bitmap text is clipped pixel by pixel, so partially visible characters appear cut off at the window edge.

Local Control of a Curve [6]

Local control means that moving (or editing) a single control point changes only a limited, nearby portion of the curve, leaving the rest of the curve unchanged. The opposite is global control, where every control point influences the entire curve.

B-spline vs Bézier

Summary: Bézier curves are simple and interpolate their endpoints but lack local control and give only manual continuity; B-spline curves provide local control and built-in higher-order continuity, making them better for complex, editable curves and surfaces.