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

Bresenham's Line Drawing Algorithm

Bresenham's algorithm is an incremental, integer-only scan-conversion method. At each step it chooses the pixel closest to the true line using a decision parameter computed with only integer addition/subtraction, avoiding floating-point arithmetic.

Derivation (for slope $0 \le m \le 1$)

Let the line go from $(x_1, y_1)$ to $(x_2, y_2)$ with $\Delta x = x_2 - x_1$, $\Delta y = y_2 - y_1$. We step one unit in $x$ each time and decide whether $y$ stays the same or increments by 1. The decision parameter is:

Update rule at each step:

• If $p_k < 0$: choose lower pixel, $\;p_{k+1} = p_k + 2\Delta y$
• If $p_k \ge 0$: choose upper pixel ($y$ increments), $\;p_{k+1} = p_k + 2\Delta y - 2\Delta x$

Algorithm

dx = x2 - x1 ;  dy = y2 - y1
p  = 2*dy - dx
x  = x1 ;  y = y1
plot(x, y)
while x < x2:
    x = x + 1
    if p < 0:
        p = p + 2*dy
    else:
        y = y + 1
        p = p + 2*dy - 2*dx
    plot(x, y)

Comparison with DDA

Drawing line from (2, 3) to (10, 8)

$\Delta x = 10 - 2 = 8$, $\;\Delta y = 8 - 3 = 5$. Slope $m = 5/8 < 1$, so step in $x$.

$p_0 = 2\Delta y - \Delta x = 2(5) - 8 = 2$.

Constants: $2\Delta y = 10$, $\;2\Delta y - 2\Delta x = 10 - 16 = -6$.

Pixels: (2,3), (3,4), (4,4), (5,5), (6,6), (7,6), (8,7), (9,7), (10,8).

Polygon Mesh

A polygon mesh is a collection of connected polygons (usually triangles or quadrilaterals) that together approximate the surface of a 3D object. It is defined by vertices, edges, and faces, and is the most common boundary representation for surfaces in graphics because polygons are simple to render and transform.

Types of Polygon Mesh

1. Triangle Strip – a sequence of triangles where each new vertex (after the first two) forms a triangle with the previous two. $n$ triangles need only $n+2$ vertices.
2. Triangle Fan – all triangles share one common (central) vertex; $n$ triangles need $n+2$ vertices.
3. Quadrilateral Mesh – a grid of four-sided polygons, convenient for regular surfaces.
4. General/Explicit Polygon Mesh – arbitrary polygons stored explicitly as lists of vertices, edges, and faces.

Meshes are commonly stored using three tables: a vertex table (coordinates), an edge table (pairs of vertices), and a polygon (surface) table (the edges/vertices bounding each face).

Cube of side 2 with one vertex at origin

Vertices (vertex table):

Edge Table (12 edges)

Polygon (Surface) Table (6 faces)

The three tables together fully describe the cube: vertices give geometry, edges give connectivity, and the polygon table groups edges into the six faces.

Painter's Algorithm (Depth-Sort)

The Painter's algorithm is an object-space visible-surface method that mimics how a painter works: distant objects are drawn first and nearer objects are painted over them.

Steps

1. Sort all polygons by depth, using the farthest z (or z of a
   representative point) — farthest first.
2. Resolve ambiguous overlaps between polygons whose z-ranges
   overlap (using the standard depth-sort tests).
3. Render (scan-convert) the polygons in back-to-front order;
   nearer polygons overwrite the pixels of farther ones.

Depth-overlap (ambiguity) tests

For two polygons whose z-extents overlap, perform tests in order; if any passes, no reordering is needed:

1. Their x-extents do not overlap.
2. Their y-extents do not overlap.
3. Polygon P is entirely on the far side of Q's plane.
4. Polygon Q is entirely on the near side of P's plane.
5. Their projections on the view plane do not overlap. If all tests fail, the polygons may need to be split.

Limitations: cyclic overlaps and interpenetrating polygons require splitting; sorting cost grows with the number of polygons.

BSP (Binary Space Partitioning) Tree Method

The BSP tree is an object-space method that recursively divides space using polygon planes so that, from any viewpoint, a correct back-to-front (or front-to-back) ordering can be obtained by a simple tree traversal.

How it divides space

buildBSP(polygon_list):
    pick one polygon as the root; its plane splits space into
        front (same side as plane normal) and back half-spaces.
    for every other polygon:
        if it lies fully in front  -> front list
        if it lies fully behind    -> back list
        if it straddles the plane  -> split it into two pieces,
                                      one to each list
    recursively build BSP tree for front list  -> front subtree
    recursively build BSP tree for back  list  -> back subtree

How objects are organized

• Each node stores a polygon (and its plane); the front and back children hold the polygons on each side.
• The tree is built once (view-independent) and reused every frame.

Display traversal (for a given viewpoint)

At each node, decide which side the viewer is on:

• If the viewer is in front of the node's plane → traverse back subtree, draw the node's polygon, then traverse front subtree.
• Otherwise reverse the order.

This in-order traversal automatically yields the correct back-to-front painting order for that viewpoint, giving correct visibility without per-frame sorting.

Comparison

Need for Machine-Independent Graphics Languages

Early graphics programs were written directly against a particular device's hardware or driver. Such code was non-portable: changing the display, plotter, or workstation meant rewriting the program. A machine-independent (device-independent) graphics language/standard defines a fixed set of graphics functions and a model that applications call, while a device driver maps those calls to the actual hardware.

Examples of such standards: GKS (Graphical Kernel System), PHIGS, CGI/CGM, and modern APIs like OpenGL.

Why they are needed

• Hardware varies widely (resolution, colour depth, input devices); applications should not depend on these details.
• The same program must run on many devices without modification.
• Standard interfaces allow long-term maintainability as hardware evolves.

How standards benefit application developers

1. Portability – a program written to the standard runs on any conforming device; only the driver changes.
2. Reduced development effort/cost – developers learn one API instead of many device-specific interfaces.
3. Easier maintenance – hardware upgrades do not require rewriting application logic.
4. Reusability – graphics modules can be shared across projects and platforms.
5. Hardware independence – the standard hides device coordinates behind normalized/world coordinates.
6. Interoperability – graphics data (e.g., CGM files) can be exchanged between systems.

In short, machine-independent standards let developers focus on what to draw rather than how a specific device draws it.

2D Rotation in Computer Graphics

2D rotation repositions a point along a circular path about a fixed pivot (by default the origin) by an angle $\theta$ (positive = counter-clockwise). The distance from the pivot is unchanged; only the angular position changes.

Derivation of the Rotation Matrix

Let point $P(x, y)$ be at distance $r$ from the origin at angle $\phi$:

After rotating by $\theta$, the new point $P'(x', y')$ is at angle $\phi + \theta$:

In matrix form:

New coordinates of (2, 3) rotated 45° about origin

$\cos 45° = \sin 45° = \dfrac{1}{\sqrt 2} \approx 0.7071$.

New point $\approx (-0.707,\ 3.536)$.

Coordinate System to Coordinate System Transformation

When we describe a scene in one coordinate frame but need it in another (e.g., object coordinates → world coordinates, or one Cartesian frame to a rotated/translated frame), we compute a transformation matrix that re-expresses every point in the new frame.

General method

Suppose the new coordinate system has its origin at point $(x_0, y_0)$ in the old system and its axes are rotated by angle $\theta$ relative to the old axes. A point's coordinates in the new system are obtained by transforming the old frame onto the new one with:

1. Translate so the new origin coincides with the old origin: $T(-x_0, -y_0)$.
2. Rotate by $-\theta$ to align the old axes with the new axes: $R(-\theta)$.

The composite matrix is:

Example

Let the new frame have origin at $(2, 3)$ in the old system and be rotated by $\theta = 90°$ ($\cos90°=0$, $\sin90°=1$). Find the new coordinates of the point $P = (4, 3)$.

Step 1 – translate: $P_1 = (4 - 2,\ 3 - 3) = (2, 0)$.

Step 2 – rotate by $-90°$ using $x' = x\cos\theta + y\sin\theta$, $\;y' = -x\sin\theta + y\cos\theta$:

So $P$ has coordinates $(0, -2)$ in the new frame. (Check: $P$ lies 2 units along the old +x axis from the new origin; in the 90°-rotated frame that direction becomes the −y axis, confirming $(0,-2)$.)

3D Viewing Pipeline

The 3D viewing pipeline is the sequence of transformations that converts an object described in 3D world coordinates into a 2D image on the screen. It is analogous to taking a photograph: position the camera, project the scene, then map it to the output device.

Stages of the pipeline

Model/World Coords
   │ (1) Viewing transformation
   ▼
Viewing (Eye/Camera) Coords
   │ (2) Projection transformation
   ▼
Projection (clip) Coords  — also clipping to view volume
   │ (3) Normalization
   ▼
Normalized Device Coords (NDC)
   │ (4) Viewport / device mapping
   ▼
2D Device (Screen) Coords

1. Viewing (World → Viewing) transformation – place the synthetic camera using the view reference point (eye), the view-plane normal, and the view-up vector; transform world coordinates into the camera's coordinate frame.
2. Projection transformation – project 3D viewing coordinates onto the 2D view plane using parallel or perspective projection. The 3D view volume (a frustum for perspective, a box for parallel) defines what is visible.
3. Clipping – discard geometry lying outside the view volume.
4. Normalization – map the projected coordinates to a standard normalized device range for device independence.
5. Viewport transformation – map normalized coordinates to actual pixel positions in the screen viewport.

World coordinates to 2D screen (summary)

World points are first expressed relative to the camera, then projected onto the view plane (perspective division divides $x, y$ by depth $z$ so distant objects shrink), then clipped to the view volume, normalized, and finally scaled/translated into screen pixel coordinates. The net effect is that a 3D point $(x, y, z)$ becomes a 2D pixel $(x_s, y_s)$ ready for rasterization and hidden-surface removal.

Bézier Curve Point at u = 0.5

A cubic Bézier curve with control points $P_0, P_1, P_2, P_3$ is:

The Bernstein blending functions at $u = 0.5$:

(Check: $0.125 + 0.375 + 0.375 + 0.125 = 1$.)

x-coordinate

y-coordinate

Curve point at $u = 0.5$ is $(2.0,\ 1.875)$.

Rough Curve Shape

The curve starts at $P_0(0,0)$, ends at $P_3(4,0)$, is pulled toward (but does not touch) $P_1(1,2)$ and $P_2(3,3)$, and is tangent to $P_0P_1$ at the start and $P_2P_3$ at the end. It forms a smooth arch peaking near the middle.

 y
 3 |          P2(3,3)
 2 |   P1(1,2)
   |        ___...---...___
 1 |    _.-'   (2,1.875)   `-._
   |  .'                      `.
 0 +-P0----------------------P3----- x
   0   1     2     3     4

The curve lies entirely within the convex hull of the four control points.

Spatial-Partitioning Representation

Spatial-partitioning representation describes a solid by subdividing the 3D space it occupies into a set of small, non-overlapping cells and recording which cells are inside, outside, or on the boundary of the object. The object is thus represented by the volume it fills, not by its surface.

Common schemes:

• Octrees – recursively subdivide a cube into 8 octants until each is fully inside or fully outside.
• Voxel grids – a regular 3D array of cubic cells (volume elements).
• Cell decomposition / BSP – split space into simpler sub-volumes.

Boundary Representation (B-rep)

Boundary representation describes a solid only by its bounding surface — the vertices, edges, and faces (polygon mesh) that enclose it. It stores what is on the surface, not the interior volume.

Difference: Geometry Storage and Processing

In short, spatial partitioning stores and processes the filled volume (simple set operations, but heavy memory and approximate surfaces), whereas boundary representation stores only the enclosing surface (compact and exact for display, but volume queries and Boolean operations are harder).

Constant Intensity Shading

Constant intensity shading (also called flat shading) computes a single colour/intensity for an entire polygon and applies it uniformly to every pixel of that face. The intensity is calculated once, typically from the polygon's surface normal and one representative point.

It is valid (and exact) when:

• The object is a true polyhedron (not a curved-surface approximation).
• The light source and viewer are far away (constant lighting vectors).
• The polygon is small.

Advantage: very fast. Disadvantage: produces a faceted look and visible Mach-band intensity discontinuities at polygon edges on curved surfaces.

Phong Shading vs Fast Phong Shading

Summary: Phong shading interpolates normals and evaluates the lighting equation at every pixel for high realism; fast Phong shading approximates that intensity expression (e.g., with a Taylor expansion) so the same smooth highlights are obtained with far fewer per-pixel operations.

Virtual Reality (VR) in Education

Virtual Reality immerses a learner in a computer-generated 3D environment through head-mounted displays and tracked controllers, letting students explore and interact with content as if it were real. In education it turns abstract or inaccessible topics into experiences students can see, manipulate, and practise.

Uses of VR in education

• Virtual field trips – visit historical sites, distant geography, or outer space without leaving the classroom.
• Science labs & simulations – perform chemistry/physics experiments safely, including dangerous or expensive ones.
• Medical/skill training – practise surgery, anatomy, or machinery operation in a risk-free environment.
• 3D visualization – examine molecules, the human body, or engineering models from any angle.
• Language & soft-skill practice – simulated conversations and real-world scenarios.
• Special-needs and remote learning – adaptable, accessible environments for diverse learners.

How VR enhances engagement and learning outcomes

1. Immersion & presence – the feeling of "being there" focuses attention and reduces distraction.
2. Active, experiential learning – learning by doing improves understanding and retention compared with passive reading/listening.
3. Better memory retention – multisensory, spatial experiences are recalled more strongly.
4. Safe practice of risky tasks – mistakes carry no real-world cost, encouraging experimentation.
5. Motivation & curiosity – novelty and interactivity raise enthusiasm and participation.
6. Visualization of the abstract – complex 3D concepts become concrete and intuitive.
7. Personalized pace – learners repeat scenarios as needed for mastery.

Limitations to note: cost of hardware, possible motion sickness, and need for well-designed content. Overall, VR boosts engagement and learning outcomes by making lessons immersive, interactive, and memorable.

a. Lighting in OpenGL

OpenGL provides a local illumination model that computes the colour of a surface from light sources, the material properties, and surface normals. Lighting must be enabled and configured before drawing.

Key points

• Enable lighting and individual lights:

glEnable(GL_LIGHTING);
glEnable(GL_LIGHT0);           // up to GL_LIGHT0..GL_LIGHT7

• A light has ambient, diffuse, and specular components and a position:

GLfloat pos[]      = {1.0, 1.0, 1.0, 0.0};   // w=0 -> directional
GLfloat diffuse[]  = {1.0, 1.0, 1.0, 1.0};
glLightfv(GL_LIGHT0, GL_POSITION, pos);
glLightfv(GL_LIGHT0, GL_DIFFUSE,  diffuse);

• Material properties define how a surface reflects each component:

GLfloat mat[] = {0.8, 0.2, 0.2, 1.0};
glMaterialfv(GL_FRONT, GL_DIFFUSE, mat);
glMaterialf(GL_FRONT, GL_SHININESS, 50.0);   // specular exponent

• Surface normals are required; OpenGL uses them in the lighting equation, so glNormal3f(...) must be supplied (and normals should be unit length, e.g., glEnable(GL_NORMALIZE)).
• The reflected colour combines: ambient + diffuse (Lambert's cosine law) + specular (Phong highlight), summed over all enabled lights.

b. Orthographic Projection

Orthographic projection is a type of parallel projection in which the projectors are perpendicular to the projection plane. There is no perspective foreshortening — distant and near objects keep the same size — so it preserves true dimensions and parallelism.

Characteristics

• Centre of projection is at infinity.
• Object size is independent of distance from the viewer.
• Parallel lines remain parallel.
• Widely used in engineering and architectural drawings (top, front, side views).

Projection onto the xy-plane (project along z)

A point $(x, y, z)$ maps to $(x, y, 0)$:

In OpenGL it is set up with glOrtho(left, right, bottom, top, near, far), which defines a rectangular (box) view volume.