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

(a) Decision parameters for Bresenham's line algorithm ($0 < m < 1$)

For a line with slope $0 < m < 1$, $x$ is the driving axis: $x$ is incremented by 1 at each step and we decide whether $y$ stays the same or increases by 1.

Let the line be $y = mx + c$ where $m = \dfrac{\Delta y}{\Delta x} = \dfrac{y_2 - y_1}{x_2 - x_1}$.

Suppose pixel $(x_k, y_k)$ has just been plotted. The next pixel is either $E(x_k+1, y_k)$ or $NE(x_k+1, y_k+1)$. At $x = x_k + 1$ the true line ordinate is

$$y = m(x_k + 1) + c$$

Define the distances of the two candidate pixels from the true line:

$$d_{lower} = y - y_k, \qquad d_{upper} = (y_k + 1) - y$$

The decision parameter is taken proportional to $d_{lower} - d_{upper}$ (multiplied by $\Delta x$ to keep it integer):

$$p_k = \Delta x\,(d_{lower} - d_{upper}) = 2\,\Delta y\cdot x_k - 2\,\Delta x\cdot y_k + c'$$

Decision rule:

• If $p_k < 0$ → true line is closer to the lower pixel → plot $E$, $y_{k+1} = y_k$.
• If $p_k \geq 0$ → plot $NE$, $y_{k+1} = y_k + 1$.

Incremental updates (subtract successive parameters):

$$p_{k+1} - p_k = 2\,\Delta y - 2\,\Delta x\,(y_{k+1} - y_k)$$ $$\boxed{p_{k+1} = p_k + 2\,\Delta y \quad \text{if } p_k < 0}$$ $$\boxed{p_{k+1} = p_k + 2\,\Delta y - 2\,\Delta x \quad \text{if } p_k \geq 0}$$

Initial decision parameter (at the start pixel $(x_1,y_1)$, with $c$ eliminated):

$$\boxed{p_0 = 2\,\Delta y - \Delta x}$$

The algorithm uses only integer additions, which is its main advantage.

(b) Digitizing the line from $(20,10)$ to $(30,18)$

Here $\Delta x = 30-20 = 10$, $\Delta y = 18-10 = 8$, slope $m = 0.8$ (so $0<m<1$, $x$ is the driving axis).

• $2\,\Delta y = 16$
• $2\,\Delta y - 2\,\Delta x = 16 - 20 = -4$
• Initial: $p_0 = 2\,\Delta y - \Delta x = 16 - 10 = 6$

Starting pixel $(20,10)$:

Plotted pixels: $(20,10),(21,11),(22,12),(23,12),(24,13),(25,14),(26,15),(27,16),(28,16),(29,17),(30,18)$, ending exactly at the endpoint $(30,18)$.

(a) Why homogeneous coordinates?

In 2D, scaling and rotation about the origin are linear operations expressible as a $2\times2$ matrix multiplication, but translation is an addition $(x'=x+t_x)$, not a matrix product. This makes it impossible to combine all transformations uniformly.

Homogeneous coordinates represent a 2D point $(x,y)$ as a triple $(x, y, 1)$ (more generally $(x_h, y_h, h)$ with $x = x_h/h$). This lets translation also be written as a $3\times3$ matrix multiplication, so any sequence of translations, rotations and scalings can be composed into a single $3\times3$ matrix by multiplication — efficient and uniform.

Matrix representations (homogeneous form):

Translation by $(t_x, t_y)$:

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

Rotation by angle $\theta$ (CCW) about origin:

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

Scaling by $(s_x, s_y)$ about origin:

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

(b) Rotate triangle by $90^\circ$ CCW about vertex $A(2,2)$

Rotation about an arbitrary point $A$ = translate $A$ to origin → rotate → translate back:

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

For $\theta = 90^\circ$: $\cos90^\circ = 0,\ \sin90^\circ = 1$, so

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

Composite matrix:

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

The general formula is $x' = -(y-2)+2 = 4-y,\ \ y' = (x-2)+2 = x$.

Transformed vertices:

• $A(2,2)\to(4-2,\,2) = (2,2)$ (fixed, as expected)
• $B(6,2)\to(4-2,\,6) = (2,6)$
• $C(4,6)\to(4-6,\,4) = (-2,4)$

Result: $A'(2,2),\ B'(2,6),\ C'(-2,4)$.

(a) Parallel vs. Perspective projection

Classification of parallel projections:

Parallel projection
├── Orthographic (projectors perpendicular to view plane)
│     ├── Multiview (front, top, side)
│     └── Axonometric (isometric, dimetric, trimetric)
└── Oblique (projectors at an angle to view plane)
      ├── Cavalier
      └── Cabinet

Diagram (described): In orthographic the projectors strike the $xy$ view plane at $90^\circ$; in oblique the projectors meet the plane at an angle $\alpha$, so $z$-edges are drawn at an angle $\phi$ with some scaling.

(b) Oblique parallel projection matrix onto $xy$-plane

A point $(x, y, z)$ is projected along a direction that makes an angle $\alpha$ with the view plane. A $z$-line of length $L$ projects onto the plane with length $L\cot\alpha$ at an angle $\phi$ to the $x$-axis. Let $L_1 = \cot\alpha$ (the projected length of a unit $z$-segment). Then the projected coordinates are

$$x_p = x + z\,L_1\cos\phi, \qquad y_p = y + z\,L_1\sin\phi$$

Oblique projection matrix (onto $z=0$ plane):

$$M_{obl} = \begin{bmatrix} 1 & 0 & L_1\cos\phi & 0 \\ 0 & 1 & L_1\sin\phi & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

Special cases:

• Cavalier projection: $\alpha = 45^\circ \Rightarrow L_1 = \cot 45^\circ = 1$. Depth ($z$) lines are drawn at full scale (no foreshortening). Typically $\phi = 30^\circ$ or $45^\circ$.
• Cabinet projection: $\tan\alpha = 2 \Rightarrow L_1 = \cot\alpha = \tfrac{1}{2}$. Depth lines are drawn at half scale, giving a more realistic look. Typically $\phi = 30^\circ$ or $45^\circ$.

Thus both are obtained from $M_{obl}$ by choosing $L_1 = 1$ (cavalier) or $L_1 = \tfrac12$ (cabinet).

(a) Cohen-Sutherland line clipping algorithm

The algorithm clips a line against a rectangular window by assigning each endpoint a 4-bit region (out) code. The plane is divided into 9 regions by extending the window edges.

Bit assignment (bit = 1 if the point is outside that edge):

• Bit 1 (MSB): Top — $y > y_{max}$
• Bit 2: Bottom — $y < y_{min}$
• Bit 3: Right — $x > x_{max}$
• Bit 4 (LSB): Left — $x < x_{min}$

Window (inside) region has code 0000.

Steps:

1. Compute outcodes $c_1, c_2$ for the two endpoints.
2. If $c_1\ \text{OR}\ c_2 = 0000$ → line is completely inside → accept (trivial accept).
3. If $c_1\ \text{AND}\ c_2 \neq 0000$ → both endpoints lie outside the same edge → line is completely outside → reject (trivial reject).
4. Otherwise the line is partially inside: pick an endpoint with a non-zero code, find its intersection with the corresponding window edge, replace that endpoint with the intersection point, recompute its code, and repeat from step 2.

Significance of the 4-bit codes: the OR test gives a fast trivial-accept, the AND test gives a fast trivial-reject, and each set bit directly indicates which window edge the line must be clipped against — avoiding expensive intersection computations for most lines.

(b) Clip $P_1(5,5)\to P_2(45,35)$, window $(10,10)$–$(40,40)$

Line slope: $m = \dfrac{35-5}{45-5} = \dfrac{30}{40} = 0.75$.

Outcodes:

• $P_1(5,5)$: $x<10$ (left=1), $y<10$ (bottom=1) → 0101
• $P_2(45,35)$: $x>40$ (right=1) → 0010

AND $= 0101\ \&\ 0010 = 0000$ → not trivially rejected; clipping needed.

Clip $P_1$ (code 0101):

• Against left $x=10$: $y = 5 + 0.75(10-5) = 5 + 3.75 = 8.75$. Point $(10, 8.75)$ — but $y=8.75 < 10$, still below window. New code 0100.
• Against bottom $y=10$: $x = 5 + (10-5)/0.75 = 5 + 6.667 = 11.67$. Point $(11.67, 10)$, code 0000 (inside). So clipped start $\approx (11.67, 10)$.

Clip $P_2$ (code 0010):

• Against right $x=40$: $y = 5 + 0.75(40-5) = 5 + 26.25 = 31.25$. Point $(40, 31.25)$, code 0000 (inside). Clipped end $= (40, 31.25)$.

Result: the visible clipped segment runs from $(11.67,\,10)$ to $(40,\,31.25)$.

Raster scan vs. Random (vector) scan

Definitions:

• Resolution: the maximum number of distinguishable points (pixels) per unit area, usually given as (horizontal × vertical) pixel count, e.g. $1920\times1080$. Higher resolution → finer detail.
• Aspect ratio: the ratio of the width to the height of the display (or of a pixel), e.g. $4{:}3$ or $16{:}9$. It is the ratio of horizontal to vertical points needed to produce equal-length lines.
• Frame buffer (refresh buffer): a dedicated block of memory that holds the intensity/color value of every pixel of the image; the display controller reads it to refresh the screen. Its size = (resolution) × (bits per pixel).

Midpoint Circle Drawing Algorithm

For a circle $x^2 + y^2 = r^2$ centred at the origin, the decision function is $f(x,y) = x^2 + y^2 - r^2$ ($f<0$ inside, $f>0$ outside). The algorithm plots the second octant ($x$ from $0$, $y$ from $r$, slope between 0 and -1) and uses symmetry for the rest.

At pixel $(x_k, y_k)$ the next pixel is $E(x_k+1, y_k)$ or $SE(x_k+1, y_k-1)$. The decision parameter is $f$ at the midpoint $(x_k+1, y_k-\tfrac12)$:

$$p_k = (x_k+1)^2 + \left(y_k-\tfrac12\right)^2 - r^2$$

• If $p_k < 0$ → midpoint inside → choose $E$: $p_{k+1} = p_k + 2x_{k+1} + 1$
• If $p_k \geq 0$ → choose $SE$: $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$

Initial value: $p_0 = \tfrac{5}{4} - r \approx 1 - r$.

Eight-way symmetry: a circle is symmetric about both axes and the two diagonals, so computing one octant $(x,y)$ gives 8 pixels: $(\pm x,\pm y)$ and $(\pm y,\pm x)$. This means only $1/8$ of the circle need be computed.

Pixels for first octant, $r = 8$

$p_0 = 1 - 8 = -7$. Start $(0, 8)$.

Stop when $x \geq y$ (here at $(6,6)$, where $x=y$).

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

Bezier Curve

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 these points using Bernstein polynomials as blending functions; it passes through the first and last control points and is pulled toward the intermediate ones.

Bernstein blending function:

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

General Bezier curve: $P(t) = \displaystyle\sum_{i=0}^{n} P_i\, B_{i,n}(t)$.

Cubic Bezier curve ($n=3$, four control points $P_0,P_1,P_2,P_3$):

$$P(t) = (1-t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1-t) P_2 + t^3 P_3,\quad 0\le t\le 1$$

Important properties:

1. Endpoint interpolation: $P(0)=P_0$ and $P(1)=P_n$; the curve passes through the first and last control points only.
2. Convex hull property: the curve lies entirely within the convex hull of its control points (since $\sum B_{i,n}(t)=1$ and each $B_{i,n}\ge0$).
3. Tangency: the curve is tangent to $P_1-P_0$ at the start and to $P_n-P_{n-1}$ at the end.
4. Affine invariance: transforming the control points transforms the curve.
5. Global control: moving any control point changes the whole curve shape.
6. Degree = (number of control points − 1).

Object-space vs. Image-space hidden surface removal

Z-buffer (depth-buffer) algorithm

Uses two buffers: a frame buffer (color of each pixel) and a Z-buffer (depth of the closest surface so far at each pixel).

Initialize: depth(x,y) = z_max (far),  color(x,y) = background
For each polygon:
  For each pixel (x,y) it covers:
    compute depth z at (x,y)
    if z < depth(x,y):        // nearer to viewer
        depth(x,y) = z
        color(x,y) = surface color at (x,y)

After all polygons are processed, the frame buffer holds the visible surfaces.

Advantage: simple to implement, no presorting of polygons needed, and it handles any number of objects of arbitrary shape (intersecting/penetrating surfaces) easily — it is hardware-friendly.

Disadvantage: requires a large amount of extra memory for the depth buffer, and it processes (and overwrites) hidden pixels too, doing redundant work; precision/aliasing issues with limited depth resolution.

Gouraud vs. Phong shading

Summary: Gouraud interpolates color (fast, lower quality), Phong interpolates normals and lights per pixel (slower, higher quality, especially for shiny/specular surfaces).

Sutherland-Hodgeman Polygon Clipping

This algorithm clips a polygon against a convex clip window by clipping it successively against each window edge, one at a time (left, right, bottom, top). The output vertex list from clipping against one edge becomes the input for the next edge.

Procedure (for one clip edge): traverse the polygon edges (each defined by current vertex $S$ → next vertex $P$) and apply four cases relative to the clip boundary:

Diagram (described): the original polygon is overlaid on the rectangular window; after clipping against the left edge, vertices outside the left edge are replaced by intersection points on that edge; repeating for right, bottom and top edges yields the final clipped polygon lying inside the window.

Major limitation: for concave polygons the algorithm can produce extraneous connecting lines — the clipped result may include spurious edges that join separate visible portions of the polygon (because the output is kept as a single vertex list). The polygon should be split into convex pieces, or a more general algorithm (e.g. Weiler-Atherton) must be used.

3D rotation matrices (homogeneous, CCW, right-handed)

About the $x$-axis (by angle $\theta$):

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

About the $y$-axis:

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

About the $z$-axis:

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

Reflection about the plane $z = 0$ (the $xy$-plane)

Reflection about $z=0$ negates the $z$-coordinate while leaving $x$ and $y$ unchanged ($x'=x,\ y'=y,\ z'=-z$):

$$M_{z=0} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

(Answer any two.)

(a) Anti-aliasing techniques

Aliasing is the staircase (jagged) appearance of lines/edges and loss of fine detail caused by sampling a continuous image onto a discrete pixel grid. Anti-aliasing reduces it:

• Super-sampling (post-filtering): render at higher resolution and average down (e.g. compute several sub-pixel samples per pixel and take their mean).
• Area sampling (pre-filtering): set each pixel's intensity proportional to the fraction of its area covered by the primitive.
• Pixel-weighting / filtering: weight sub-pixel samples by a filter (e.g. cone or Gaussian) so nearer-to-centre samples count more. The effect is smoother edges by using intermediate intensity (gray) levels along boundaries.

(b) Boundary-fill vs. Flood-fill

Both fill a connected region starting from a seed pixel, recursively spreading to 4-connected or 8-connected neighbours.

boundaryFill(x,y, fillColor, borderColor):
  c = getPixel(x,y)
  if c != borderColor and c != fillColor:
     setPixel(x,y,fillColor)
     // recurse on 4/8 neighbours

(c) Color models (RGB and CMY)

• RGB (additive): uses primaries Red, Green, Blue; colors are formed by adding light. $(0,0,0)$ = black, $(1,1,1)$ = white. Used by emissive devices — monitors, cameras, scanners.
• CMY (subtractive): uses Cyan, Magenta, Yellow (complements of RGB); colors formed by subtracting (absorbing) light from white. $(0,0,0)$ = white (paper), $(1,1,1)$ = black. Used by printers/hard-copy.
• Relationship: $\begin{bmatrix}C\\M\\Y\end{bmatrix} = \begin{bmatrix}1\\1\\1\end{bmatrix} - \begin{bmatrix}R\\G\\B\end{bmatrix}$. (In practice CMYK adds a black ink K for richer blacks.)