BSc CSIT (TU) Science BIT Computer Graphics (BIT304) – 5th Semester (Model) Question Paper 2079 Nepal

(a) Hermite interpolation in defining a curve

A Hermite curve is a cubic parametric curve segment that is defined by two endpoints and the tangent (slope) vectors at those endpoints. Unlike pure point interpolation, Hermite interpolation matches both position and first derivative (tangent) at the boundary points, which gives precise control over the shape and direction of the curve.

For a parameter $u \in [0,1]$, the Hermite curve is

where $P_0, P_1$ are the endpoints and $T_0, T_1$ are the tangent vectors. The four Hermite blending (basis) functions are

In matrix form, $P(u) = \begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} M_H \begin{bmatrix} P_0 \\ P_1 \\ T_0 \\ T_1 \end{bmatrix}$, with the Hermite matrix

(b) Drawing the line $(2,3)$ to $(12,8)$ using DDA

Step 1 - Compute differences:

Step 2 - Number of steps $= \max(|\Delta x|, |\Delta y|) = \max(10, 5) = 10$.

Step 3 - Increments:

Step 4 - Iterate, starting at $(2, 3)$ and plotting the rounded value at each step:

These pixels form the line from $(2,3)$ to $(12,8)$.

(a) Ambient light vs Diffuse reflection

Here $k_a$ and $k_d$ are the ambient and diffuse reflection coefficients and $I_a, I_l$ are ambient and source intensities.

(b) Phong Shading algorithm

Phong shading (normal-vector interpolation shading) interpolates surface normals across a polygon and applies the illumination model at every pixel, giving smooth, realistic highlights.

Algorithm:

1. Compute the vertex normals by averaging the normals of all polygons that share each vertex.
2. For each scan line crossing the polygon, linearly interpolate the vertex normals along the polygon edges to obtain the normal at each edge intersection.
3. Along the scan line, interpolate the edge normals to compute the surface normal $\vec{N}$ at each pixel.
4. Normalize the interpolated normal $\vec{N}$ at every pixel.
5. Apply the Phong illumination model at each pixel using the interpolated normal:

where $\vec{L}$ is the light vector, $\vec{R}$ the reflection vector, $\vec{V}$ the view vector, $k_s$ the specular coefficient and $n_s$ the shininess exponent. 6. Set the pixel to the computed color/intensity $I$. 7. Repeat for all pixels of the polygon.

Because the illumination model is evaluated per pixel, Phong shading reproduces specular highlights accurately even inside a polygon, unlike Gouraud shading.

Perspective projection onto the view plane

For a center of projection at $Z_{prp}$ and a projection (view) plane at $Z_{vp}$, a point $(x, y, z)$ projects to the plane $Z_{vp}$ with the perspective scale factor

so that the projected coordinates are

Here $Z_{prp} = 20$ and $Z_{vp} = 0$, so the numerator $Z_{prp} - Z_{vp} = 20$.

Base vertices ($z = 10$): scale factor $d = \dfrac{20}{20 - 10} = \dfrac{20}{10} = 2$.

Apex ($z = 2$): scale factor $d = \dfrac{20}{20 - 2} = \dfrac{20}{18} = \dfrac{10}{9} \approx 1.111$.

Projected pyramid coordinates

All projected points lie on the view plane $z = 0$.

Given

• Resolution = $1024 \times 768$ (so number of rows = 768).
• Refresh rate = 60 frames per second.

Step 1 - Time to refresh one full frame

Step 2 - Time per row (scan line)

The frame contains 768 horizontal rows, so

Result

Approximately $21.7\ \mu s$ (about $2.17 \times 10^{-5}$ seconds) is spent scanning across each row of pixels.

Disadvantages of flat shading

Flat (constant) shading computes a single intensity for an entire polygon using one surface normal, which causes:

1. Faceted appearance - curved surfaces approximated by polygons look blocky/angular instead of smooth.
2. Mach band effect - abrupt intensity changes at polygon edges are exaggerated by the human eye, producing visible bright/dark bands.
3. Poor highlight representation - specular highlights falling inside a polygon are missed or wrongly placed because only one normal is used.
4. Inaccurate for low-polygon models - quality degrades badly unless a very large number of polygons is used.
5. Discontinuous shading - neighbouring polygons of a smooth surface show sudden intensity jumps.

How they can be eliminated

The defects are removed by using intensity-interpolation shading techniques instead of constant shading:

1. Gouraud shading - compute intensities at the vertices (using averaged vertex normals) and linearly interpolate them across the polygon, smoothing the colour transitions and reducing Mach banding.
2. Phong shading - interpolate the surface normals across the polygon and apply the illumination model per pixel, which removes faceting and correctly reproduces specular highlights inside polygons.
3. Increase polygon count / use finer mesh so each facet is smaller and the discontinuities become less noticeable.

Phong shading gives the best elimination of flat-shading defects at the cost of more computation.

Mid-point Circle Drawing Algorithm

The algorithm exploits the 8-way symmetry of a circle centred at the origin and uses an integer decision parameter to choose between two candidate pixels.

Steps:

1. Input the radius $r$ and circle centre $(x_c, y_c)$. Obtain the first point on the circle centred at the origin:

2. Initialize the decision parameter:

3. At each position $x_k$, test the sign of $p_k$:

• If $p_k < 0$, the next point is $(x_k + 1, y_k)$ and

• Else ($p_k \geq 0$), the next point is $(x_k + 1, y_k - 1)$ and

where $x_{k+1} = x_k + 1$ and $y_{k+1} = y_k$ or $y_k - 1$.

4. Determine the symmetry points in the other seven octants and plot, translating to the centre:

5. Repeat steps 3-4 until $x \geq y$.

This generates the full circle using only integer addition and comparisons (no floating point or square roots).

Bresenham's decision parameter for a line with negative slope

Consider a line with slope $m = \dfrac{\Delta y}{\Delta x}$ where the line goes downward to the right (negative slope), with $|m| < 1$. As $x$ increases by 1, $y$ either stays the same or decreases by 1.

The equation of the line: $y = mx + b$. At step $x_k$ we have plotted $(x_k, y_k)$ and must choose, at $x_{k+1} = x_k + 1$, between the two candidate pixels:

• the lower pixel $(x_k + 1,\ y_k - 1)$, and
• the same-level pixel $(x_k + 1,\ y_k)$.

True line value:

Let $d_1$ be the distance from the true line down to the upper candidate $y_k$ and $d_2$ to the lower candidate $y_k - 1$. For a negative-slope line:

Decision quantity (choose pixel by sign of $d_1 - d_2$):

Define the decision parameter $p_k$ by multiplying by $\Delta x$ (positive) to keep it integer, using $m = \Delta y / \Delta x$:

Working it out, the decision parameter is

with constant $c$. The recurrence is obtained from $p_{k+1} - p_k$:

• If $p_k < 0$: choose the lower pixel $(x_k+1, y_k-1)$ and

• Else ($p_k \geq 0$): choose the same-level pixel $(x_k+1, y_k)$ and

(The roles of the increments are swapped relative to a positive-slope line because $y$ now decrements instead of incrementing.) The initial decision parameter is

Conditions for error-free generation of a polygon table

A polygon surface is stored using three geometric tables - the vertex table, edge table and polygon (surface-facet) table - plus attribute tables. To ensure the tables are consistent and free of errors, the following consistency / validity checks must be satisfied:

1. Every vertex is listed as an endpoint of at least two edges. A vertex belonging to only one edge indicates a dangling/incomplete edge.
2. Every edge is part of at least one polygon. An edge that belongs to no polygon (or only one polygon for a closed solid) signals a missing surface.
3. Every polygon is closed - the edges of each polygon must form a complete loop (the last edge connects back to the first vertex).
4. Each edge is shared by at least two polygons (for a closed solid object); an edge appearing in only one polygon may indicate a hole or missing face.
5. Every vertex referenced in an edge appears in the vertex table, and every edge referenced in a polygon appears in the edge table (no dangling references).
6. No duplicate or coincident edges/vertices - each edge and vertex should be listed only once.
7. Each polygon has at least one shared edge so that the surface is connected.

If all these conditions hold, the polygon tables are geometrically consistent and the object can be generated without error.

Parallel projection vs Perspective projection

In short, parallel projection keeps exact dimensions for accurate drafting, while perspective projection sacrifices exact size for visual realism.

Vector (random) scan vs Raster scan systems

Thus vector systems excel at sharp line art, whereas raster systems dominate modern displays because they support realistic, filled, coloured images.

Proof: successive rotations add their angles

Let a 2D point be rotated about the origin first by angle $\theta_1$ and then by angle $\theta_2$. We show the combined effect equals a single rotation by $(\theta_1 + \theta_2)$.

Rotation matrix by angle $\theta$:

Apply two successive rotations:

Multiply the matrices:

• $(1,1)$ entry: $\cos\theta_2\cos\theta_1 - \sin\theta_2\sin\theta_1 = \cos(\theta_1+\theta_2)$
• $(1,2)$ entry: $-\cos\theta_2\sin\theta_1 - \sin\theta_2\cos\theta_1 = -\sin(\theta_1+\theta_2)$
• $(2,1)$ entry: $\sin\theta_2\cos\theta_1 + \cos\theta_2\sin\theta_1 = \sin(\theta_1+\theta_2)$
• $(2,2)$ entry: $-\sin\theta_2\sin\theta_1 + \cos\theta_2\cos\theta_1 = \cos(\theta_1+\theta_2)$

(using the trigonometric identities $\cos(A+B) = \cos A\cos B - \sin A\sin B$ and $\sin(A+B) = \sin A\cos B + \cos A\sin B$).

Therefore:

Hence two successive rotations of $\theta_1$ and $\theta_2$ are equivalent to a single rotation by $(\theta_1 + \theta_2)$, i.e. rotations are additive. (This proof also holds with $3 \times 3$ homogeneous rotation matrices.)

a. Vertex table

A vertex table is one of the three geometric data tables used to represent a polygon surface (along with the edge table and the polygon table). It stores the coordinate values $(x, y, z)$ of every vertex of the object, each identified by a unique index.

• It defines where the points of the object are located in space.
• The edge table then references vertices from this table to define edges, and the polygon table references edges/vertices to define faces.
• Storing coordinates once in the vertex table avoids duplication and makes editing easy: changing a vertex's coordinates automatically updates every edge and polygon that uses it.

Example:

b. Key frame

A key frame is a frame in computer animation that defines the important/starting and ending positions (states) of an object during a motion sequence. Key frames are drawn or specified by the animator at significant points of the action.

• The frames in between two key frames are generated automatically by interpolation - a process called in-betweening (tweening).
• Key frames define the extreme poses (e.g. the start and end of a jump), and tweening fills the smooth transition.
• This greatly reduces the animator's work, since only key frames must be created manually while intermediate frames are computed (e.g. by linear or spline interpolation of position, rotation, scale).