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

Parallel and Perspective Projections in 3D Graphics

Projection maps 3D points onto a 2D view (projection) plane along projectors (projection lines).

Parallel Projection

The projectors are parallel to one another; the centre of projection is at infinity.

• Preserves relative proportions and parallelism of lines; no foreshortening with distance.
• Good for engineering / CAD drawings where true dimensions matter.
• Sub-types: Orthographic (projectors perpendicular to the plane) and Oblique (projectors at an oblique angle).

Perspective Projection

All projectors converge to a single point called the centre of projection (COP).

• Objects farther from the viewer appear smaller (perspective foreshortening).
• Parallel lines (not parallel to the view plane) converge at vanishing points.
• Produces realistic images, as in photographs and the human eye.
• Classified by number of vanishing points: one-point, two-point, three-point.

Derivation of the Perspective Projection Matrix

Let the centre of projection be at the origin and the projection plane at $z = d$ (distance $d$ from the eye), with a point $P = (x, y, z)$ to be projected onto $P' = (x_p, y_p, d)$.

Using similar triangles along the line from the COP through $P$ to the plane:

In homogeneous coordinates $(x, y, z, 1)$, this division by $z/d$ is captured by placing $1/d$ in the matrix so that the homogeneous $w$-coordinate becomes $z/d$:

Dividing through by the homogeneous coordinate $w = z/d$ gives the projected point:

which is exactly the perspective relation derived above. As $d \to \infty$ the term $1/d \to 0$ and the matrix reduces to the orthographic (parallel) projection, showing parallel projection is the limiting case of perspective projection.

Z-Buffer (Depth Buffer) Algorithm

The Z-buffer is an image-space hidden surface removal method. Along with the frame buffer (which stores colour/intensity for each pixel) it maintains a depth (Z) buffer that stores the $z$-value (distance from the viewer) of the closest surface seen so far at each pixel.

Algorithm

1. Initialize:
     for each pixel (x, y):
         depth_buffer[x][y] = z_max   // farthest value (background)
         frame_buffer[x][y] = background_color

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 < depth_buffer[x][y]:        // closer to the viewer
             depth_buffer[x][y] = z
             frame_buffer[x][y] = surface_color at (x, y)

The depth $z$ at successive pixels along a scan line is computed incrementally: if the plane of the polygon is $Ax + By + Cz + D = 0$, then moving one pixel in $x$ changes $z$ by a constant $-A/C$, avoiding a full recompute per pixel.

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

Advantages

• Simple to implement and easy to do in hardware (used in modern GPUs).
• Processes polygons in any order; no pre-sorting of surfaces is required.
• Handles arbitrary scene complexity and intersecting/penetrating surfaces correctly.
• Time is roughly linear in the number of polygons.

Limitations

• Requires large memory for the depth buffer (one depth value per pixel).
• Resolves visibility only at pixel resolution → aliasing; finite depth precision causes z-fighting between close surfaces.
• Performs work even for hidden surfaces (writes then overwrites pixels).
• Does not directly support transparency or anti-aliasing without extra techniques.

Scan-Line Polygon Fill Algorithm

Fills a polygon by processing the image one horizontal scan line at a time, colouring spans between pairs of edge intersections.

Steps

1. Find y_min and y_max of the polygon.
2. For each scan line y from y_min to y_max:
     a. Find all intersections of the scan line with polygon edges.
     b. Sort the intersection x-values in increasing order.
     c. Form pairs (x1,x2), (x3,x4), ... and fill pixels between
        each pair (odd-even / parity rule).

• An Edge Table (ET) and an Active Edge Table (AET) are used for efficiency: the AET holds only edges crossing the current scan line, updated incrementally.
• Each edge's $x$ is updated per scan line by $x_{new} = x_{old} + 1/m$ (where $m$ is the slope), so no full recomputation is needed.
• Vertex rule: a vertex is counted as two intersections if it is a local max/min, otherwise once, so spans pair correctly.

Example: For a triangle with vertices $(2,1), (8,1), (5,7)$, the scan line $y = 4$ intersects the two slanted edges at, say, $x = 3.5$ and $x = 6.5$; pixels from $x=4$ to $x=6$ are filled.

Boundary Fill Algorithm

Fills a region bounded by a known boundary colour, starting from a seed point inside it.

Steps (4-connected)

boundaryFill(x, y, fill_color, boundary_color):
    current = getPixel(x, y)
    if current != boundary_color and current != fill_color:
        setPixel(x, y, fill_color)
        boundaryFill(x+1, y, fill_color, boundary_color)
        boundaryFill(x-1, y, fill_color, boundary_color)
        boundaryFill(x, y+1, fill_color, boundary_color)
        boundaryFill(x, y-1, fill_color, boundary_color)

• 4-connected spreads to up/down/left/right neighbours; 8-connected also includes diagonals (fills regions that 4-connected would leak through or miss at thin diagonal boundaries).
• Recursion stops when a pixel is already the boundary colour or already filled.

Example: Given a closed circle drawn in red (boundary colour) and a seed pixel at its centre, the algorithm recursively colours every interior pixel with the fill colour until it reaches the red boundary on all sides.

Comparison

Window-to-Viewport Transformation

The window is a rectangular region in world coordinates selecting the part of a scene to display; the viewport is a rectangular region on the device/screen where that window is mapped. Window-to-viewport mapping (viewing transformation) converts a point $(x_w, y_w)$ in the window to a point $(x_v, y_v)$ in the viewport while preserving relative position.

If the window spans $[x_{wmin}, x_{wmax}] \times [y_{wmin}, y_{wmax}]$ and the viewport spans $[x_{vmin}, x_{vmax}] \times [y_{vmin}, y_{vmax}]$, the relative position must be equal:

Solving gives the mapping:

where the scale factors are

If $s_x \ne s_y$ the image is distorted; choosing $s_x = s_y$ preserves the aspect ratio. The process is equivalent to translate (window to origin) → scale → translate (to viewport).

Parallel vs Perspective Projection

In short, parallel projection keeps measurements accurate, whereas perspective projection sacrifices measurement accuracy to gain visual realism.

Working of a CRT (Cathode Ray Tube)

A CRT is a vacuum tube that produces images by directing a beam of electrons onto a phosphor-coated screen.

Main components

• Electron gun – contains a heated cathode (filament) that emits electrons (thermionic emission) and a control grid that controls beam intensity (brightness).
• Focusing system – electrostatic/magnetic lenses converge the electrons into a fine beam so the spot stays sharp.
• Deflection system – horizontal and vertical deflection plates/coils steer the beam to any point on the screen.
• Phosphor-coated screen – glows when struck by electrons.

Diagram (described in words)

Left to right: Cathode (filament) → Control grid → Accelerating & focusing anodes → Horizontal and vertical deflection plates → Phosphor screen at the front. A connector at the rear supplies the heater and grid voltages; the wide front face is the viewing screen.

Operation

1. The heated cathode emits electrons; the control grid regulates how many pass (controls brightness).
2. The focusing system forms a narrow beam, accelerated by high-voltage anodes.
3. The deflection system positions the beam at the required $(x, y)$ location.
4. The beam strikes the phosphor, which fluoresces and emits light at that point.
5. Because phosphor glow fades, the image must be refreshed (redrawn) typically 60–80 times per second to avoid flicker. Persistence is the time the phosphor keeps glowing after excitation.

Object-Space vs Image-Space Hidden Surface Removal

Object-space methods work best for scenes with few objects, while image-space methods scale better for scenes with many complex objects since work is bounded by screen resolution.

Spline

A spline is a smooth curve constructed piecewise from low-degree polynomial segments that join with continuity conditions, defined by a set of control points. The name comes from the flexible draftsman's strip used to draw smooth curves. Splines are used to model curves and surfaces (e.g., Bézier, B-spline, NURBS).

The degree of smoothness at the joins is described by continuity: $C^0$ (positional), $C^1$ (first derivative / tangent), $C^2$ (second derivative / curvature) — or the geometric equivalents $G^0, G^1, G^2$.

Interpolation vs Approximation Splines

In short, an interpolation spline is forced through the control points, whereas an approximation spline merely approximates their shape.

Key-Frame System in Computer Animation

A key frame is a frame in which the position, shape, or other attributes of an object are explicitly defined by the animator at a specific point in time. A key-frame system generates the in-between frames automatically.

Working

1. The animator (or chief artist) specifies the key frames — usually at the start and end of a motion and at important moments where the action changes.
2. The system computes the intermediate frames, called in-betweens (or tweens), by interpolating the object parameters between successive key frames.
3. Linear interpolation gives uniform spacing; non-linear / spline interpolation (e.g., ease-in / ease-out) gives more natural acceleration and deceleration.

For a parameter $P$ with values $P_k$ at key frame $k$ and $P_{k+1}$ at key frame $k+1$, an in-between at fraction $t \in [0,1]$ is:

Related techniques

• Morphing: transforming one object shape into another smoothly between key frames.
• Motion specification via parameters such as position, rotation, scale, and colour, each interpolated independently.

Advantage

The animator defines only a few key frames; the computer fills in the rest, greatly reducing manual effort while keeping motion smooth and controllable.

Raster Scan vs Random (Vector) Scan Display

Raster Scan Display

• The screen is a grid of dots called pixels; the picture is a pixmap stored in a frame buffer (refresh buffer).
• The electron beam sweeps the screen horizontally one row at a time, from top-left to bottom-right (line by line), turning each pixel on/off according to the frame buffer.
• After completing the screen the beam returns to the top (vertical retrace) and the image is refreshed (e.g., 60 Hz).
• Can display filled areas, shading, and realistic colour images.
• Resolution is limited by frame-buffer size; suffers from staircasing/aliasing on slanted lines.

Random (Vector / Stroke) Scan Display

• The electron beam is deflected directly from one endpoint to another, drawing only the line segments that make up the picture (stored in a display file / display list).
• Refreshes by retracing each stored line; the beam visits points in any order, not row by row.
• Produces smooth, high-resolution lines with no jaggedness — excellent for line drawings and CAD.
• Cannot easily display shaded or filled solid areas; refresh time grows with the number of lines, so complex pictures flicker.

Key difference

A raster display stores and refreshes every pixel (good for realistic images), while a vector display stores and traces only the line endpoints (good for sharp wireframe line art).

DDA (Digital Differential Analyzer) Line Drawing Algorithm

DDA is an incremental scan-conversion method that computes successive pixel positions of a line using the line's slope.

For a line from $(x_1, y_1)$ to $(x_2, y_2)$, let $\Delta x = x_2 - x_1$, $\Delta y = y_2 - y_1$.

Algorithm

steps = max(|dx|, |dy|)
x_inc = dx / steps
y_inc = dy / steps
x = x1 ;  y = y1
plot(round(x), round(y))
for i = 1 to steps:
    x = x + x_inc
    y = y + y_inc
    plot(round(x), round(y))

Dividing by steps (the larger of $|\Delta x|, |\Delta y|$) guarantees unit movement along the dominant axis and a fractional step along the other, so no gaps appear.

Advantages

• Simple and easy to implement.
• Faster than the direct line equation $y = mx + c$ because it avoids a multiplication per point, using only addition.
• Works for lines of any slope and direction.

Disadvantages

• Uses floating-point arithmetic and rounding, which is slower and costly in hardware.
• Accumulated round-off error can cause the plotted line to drift from the true line over long segments.
• Rounding each point makes it slower than the integer-only Bresenham's algorithm, which is generally preferred.

Rotation about an Arbitrary Point in 2D

The basic 2D rotation matrix rotates about the origin by angle $\theta$. To rotate a point about an arbitrary pivot $(x_p, y_p)$, we compose three transformations:

1. Translate the pivot to the origin: $T(-x_p, -y_p)$.
2. Rotate about the origin by $\theta$: $R(\theta)$.
3. Translate back so the pivot returns to $(x_p, y_p)$: $T(x_p, y_p)$.

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

In homogeneous coordinates:

Multiplying these gives:

So the rotated point $(x', y')$ is:

When $(x_p, y_p) = (0, 0)$, $M$ reduces to the standard origin rotation matrix, confirming the result.