BSc CSIT (TU) Science Computer Graphics (BSc CSIT, CSC209) Question Paper 2077 Nepal

Parallel and Perspective Projections in 3D Graphics

Projection transforms 3D points onto a 2D projection plane (view plane) by passing projectors (lines from object points toward the plane).

Parallel Projection

Projectors are parallel to each other (the centre of projection is at infinity).

• Preserves relative proportions and parallelism of lines; good for engineering/technical drawings.
• Does not give a realistic view (no foreshortening).
• Types: Orthographic (projectors perpendicular to the plane) and Oblique (projectors at an angle).

For orthographic projection onto the $z=0$ plane, $x_p=x,\; y_p=y,\; z_p=0$, with matrix:

Perspective Projection

Projectors all pass through a single centre of projection (COP). Objects farther from the COP appear smaller (perspective foreshortening), giving a realistic view, but parallel lines converge to vanishing points and true dimensions are not preserved.

Derivation of the Perspective Projection Matrix

Let the centre of projection be at the origin and the projection plane at $z=d$ (along the $z$-axis). Consider a 3D point $P(x,y,z)$ projected to $P'(x_p,y_p,d)$ on the plane.

Using similar triangles along the $z$-axis:

In homogeneous coordinates, represent $P=[x\;y\;z\;1]^T$. The perspective matrix is:

Multiplying:

Dividing by the homogeneous coordinate $h=z/d$ gives the Cartesian point:

which matches the similar-triangle result. The term $1/d$ in the bottom row produces the perspective division that creates foreshortening.

Z-Buffer (Depth Buffer) Algorithm

The Z-buffer algorithm is an image-space method for hidden surface removal. It uses two buffers of the same resolution as the display:

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

Algorithm

1. Initialize:
   for each pixel (x, y):
       depthBuffer[x][y] = z_max   // farthest depth (background)
       frameBuffer[x][y] = background_colour

2. For each polygon in the scene:
     For each pixel (x, y) covered by the polygon:
         Compute depth z of the polygon at (x, y)
         if z < depthBuffer[x][y]:        // nearer to viewer
             depthBuffer[x][y] = z
             frameBuffer[x][y] = surface_colour at (x, y)

The depth at successive pixels along a scan line is found incrementally. If $Ax+By+Cz+D=0$ is the plane equation, then moving one pixel in $x$:

so only an addition is needed per pixel.

Advantages

• Simple to implement (in hardware too); used in modern GPUs.
• Handles any number of polygons; no presorting of objects is required.
• Easy to handle intersecting and complex surfaces; processing time is roughly independent of scene complexity for a fixed resolution.

Limitations

• Requires large memory for the depth buffer.
• Spends time computing pixels that may later be overwritten (no early sorting); can be inefficient.
• Limited depth precision can cause z-fighting (aliasing of nearly coplanar surfaces).
• Cannot directly handle transparency and anti-aliasing without extensions.
• Resolution-dependent (image-space), so it does not produce an analytic/object-space description.

Scan-Line Polygon Fill Algorithm

This is an image-space area-filling method that fills a polygon scan line by scan line, using the odd-even (parity) rule.

Steps

1. Find $y_{min}$ and $y_{max}$ of the polygon.
2. For each scan line $y$ from $y_{min}$ to $y_{max}$:
   • Find the intersection points of the scan line with all polygon edges.
   • Sort the intersection $x$-coordinates in increasing order.
   • Pair them: $(x_1,x_2),(x_3,x_4),\dots$ and fill the pixels between each pair (inside the polygon by the odd-even rule).
3. Handle special cases:
   • Vertices: count a vertex once if it is a local min/max, otherwise twice, so parity stays correct.
   • Use an Edge Table (ET) and Active Edge Table (AET) with coherence: as $y$ increases by 1, update each intersection $x$ by $1/m$ (the inverse slope) instead of recomputing.

Example: For a triangle with vertices $(2,2),(8,2),(5,8)$, the scan line $y=4$ intersects the two sloping edges at, say, $x=3$ and $x=7$; pixels from $x=3$ to $x=7$ on that line are filled. Repeating for every scan line fills the triangle.

Boundary Fill Algorithm

This is a seed-fill (object-space, recursive) method. Given an interior seed point, it fills outward until the polygon boundary colour is reached.

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

• 4-connected fill checks up/down/left/right; 8-connected also checks the four diagonals (needed for shapes with thin diagonal boundaries).

Example: A circle drawn in red (boundary colour) with a seed pixel at its centre is filled blue; recursion stops at the red ring.

Comparison

• Scan-line fill needs the polygon's edge list and works well for solid polygons; boundary fill needs only a seed point and a known boundary colour but can be memory/stack-heavy and is suited to interactive/region filling.

Window-to-Viewport Transformation

A window is the rectangular region selected in world coordinates that is to be displayed. A viewport is the rectangular region on the device/screen where the window's contents are mapped. Window-to-viewport transformation (viewing transformation) maps each point in the window to a corresponding point in the viewport while preserving relative position.

Let a window point be $(x_w, y_w)$ with window limits $(xw_{min}, xw_{max}, yw_{min}, yw_{max})$ and the viewport limits $(xv_{min}, xv_{max}, yv_{min}, yv_{max})$. The mapped point $(x_v, y_v)$ is found by keeping the relative position equal:

where the scaling factors are

If $s_x \ne s_y$, the displayed image is distorted (stretched); equal factors preserve the aspect ratio. The process is equivalent to: translate window to origin, scale by $(s_x,s_y)$, then translate to the viewport position.

Parallel vs Perspective Projection

In short, parallel projection preserves shape and size for accurate measurement, whereas perspective projection sacrifices accuracy to give a realistic depth cue.

Working of a Cathode Ray Tube (CRT)

A CRT is the basic display device used in older monitors. It is an evacuated glass tube with the following main parts:

• Electron gun – contains a heated cathode (filament) that emits electrons by thermionic emission, and a control grid that controls the number of electrons (beam intensity/brightness).
• Focusing system – electrostatic/magnetic lenses that converge the electrons into a fine, sharp beam.
• Deflection system – horizontal and vertical deflection plates/coils that steer the beam to the desired position on the screen.
• Phosphor-coated screen – the front face; when the high-energy electron beam strikes it, the phosphor glows (fluoresces) and emits light at that spot.

Operation

Electrons emitted by the heated cathode are accelerated by a positive accelerating anode toward the screen, focused into a narrow beam, and deflected to a specific $(x,y)$ position. Where the beam hits, the phosphor emits a spot of light. Because the glow fades quickly (persistence), the picture must be redrawn many times per second (refreshing, typically 60 Hz or more) to avoid flicker.

Diagram (described): a horizontal tube with the electron gun (cathode, control grid, accelerating anode) at the narrow rear end, a focusing system, then vertical and horizontal deflection plates, opening out to the wide phosphor-coated screen at the front, with the electron beam shown travelling left to right and striking the screen.

Object-Space vs Image-Space Methods (Hidden Surface Removal)

Object-space methods are accurate but become expensive for many objects, whereas image-space methods scale with screen resolution and are simpler to implement in hardware.

Spline; Interpolation vs Approximation Splines

Spline

A spline is a smooth curve constructed to pass through or near a set of given points called control points. The term originates from a flexible strip (mechanical spline) bent through points. Mathematically a spline is a piecewise polynomial curve (e.g. cubic) joined so that it is continuous and smooth (positional, tangent, and sometimes curvature continuity, denoted $C^0, C^1, C^2$) at the joints. Common splines: Bezier, B-spline, Hermite.

Interpolation vs Approximation Splines

In short, an interpolation spline reproduces the data exactly by passing through the points, while an approximation spline trades exactness for a smoother, more controllable curve that merely approximates the control points.

Key Frame System in Computer Animation

A key frame is a frame that defines the important/extreme positions (the start and end points of a movement) of an object in an animation. In a key frame system, the animator (or lead) specifies only these key frames, and the computer automatically generates the in-between frames by a process called in-betweening or tweening.

Working

1. The animator defines key frames at chosen times $t_1, t_2$ for an object's parameters (position, shape, colour, orientation).
2. The number of in-between frames is decided from the frame rate and time gap, e.g. for 1 s at 24 fps with key frames at the ends there are 22 in-betweens.
3. The system interpolates parameter values between successive key frames:

for linear interpolation; non-linear (spline) interpolation is used for smooth ease-in/ease-out motion. 4. Object shapes can be transformed between key frames by morphing, matching the number of vertices/edges in the two key shapes.

Advantages

• The animator controls only the important frames, saving large amounts of manual work.
• Smooth, consistent motion is produced automatically; timing is easy to adjust by changing key-frame positions.

Raster Scan vs Random (Vector) Scan Displays

Raster Scan Display

The screen is a grid of pixels. The electron beam sweeps the screen horizontally, one scan line at a time, from top to bottom (left-to-right on each line, then retrace). The picture intensity for every pixel is held in a frame buffer (refresh buffer) in memory; as the beam scans, the intensity is read from the frame buffer and applied. After the bottom line, the beam returns to the top (vertical retrace) and the whole screen is refreshed (typically 60 Hz).

• Suitable for realistic, filled, shaded images and photographs.
• Image quality limited by resolution (pixel count); diagonal lines show staircase/aliasing.
• Needs large frame-buffer memory.

Random (Vector / Stroke) Scan Display

The electron beam is deflected directly from one endpoint of a line to another, drawing only the line segments that make up the picture (it does not scan the whole screen). The component lines/curves are stored in a display file (refresh display list) and the beam is refreshed by re-tracing those segments (30–60 times/s).

• Produces very smooth, sharp lines (no staircasing) at high resolution.
• Good for line drawings, CAD, wireframes; cannot easily display shaded/solid areas or realistic images.
• Refresh time depends on the number of lines (complex pictures may flicker).

Key difference: raster scan plots all pixels from a frame buffer (good for filled images), while random scan plots only the line segments directly (good for crisp line art).

DDA (Digital Differential Analyzer) Line Drawing Algorithm

The DDA is an incremental scan-conversion algorithm that draws a line by sampling it at unit intervals along the axis of greater change and computing the other coordinate from the slope $m = \dfrac{y_2-y_1}{x_2-x_1}$.

Algorithm

Input: endpoints (x1, y1), (x2, y2)
dx = x2 - x1;  dy = y2 - y1
steps = max(|dx|, |dy|)        // number of sampling steps
xInc = dx / steps;  yInc = dy / steps
x = x1;  y = y1
plot(round(x), round(y))
for i = 1 to steps:
    x = x + xInc
    y = y + yInc
    plot(round(x), round(y))

If $|m|\le 1$: increment $x$ by 1 and $y$ by $m$ each step; if $|m|>1$: increment $y$ by 1 and $x$ by $1/m$. This guarantees no gaps in the line.

Advantages

• Simpler and faster than directly evaluating the line equation $y=mx+c$ at each point, because it uses only incremental addition (no repeated multiplication).
• Easy to understand and implement.

Disadvantages

• Uses floating-point arithmetic and round(), which are slow and prone to round-off accumulation, so points may drift away from the true line for long lines.
• Floating-point operations make it slower than the all-integer Bresenham's algorithm, which is generally preferred.

Rotation About an Arbitrary Point in 2D

A basic rotation matrix rotates a point only about the origin. To rotate about an arbitrary pivot point $P(x_p, y_p)$ by angle $\theta$, we perform three steps using homogeneous coordinates:

Step 1 – Translate the pivot to the origin: $T(-x_p,-y_p)$

Step 2 – Rotate about the origin by $\theta$: $R(\theta)$

Step 3 – Translate the pivot back to its original position: $T(x_p,y_p)$

Composite Matrix

The overall transformation is $M = T(x_p,y_p)\cdot R(\theta)\cdot T(-x_p,-y_p)$. Multiplying:

Thus a transformed point is given by $\begin{bmatrix}x'\\y'\\1\end{bmatrix}=M\begin{bmatrix}x\\y\\1\end{bmatrix}$, i.e.