TU BCA Computer Graphics Master Guide: DDA, Bresenham’s Line Algorithm & 2D Transformations (Solved Board Problems)
Author: Bhuban Subedi | Subject: Computer Graphics and Animation (CACS304) | Semester: Fifth Semester
In video game development, 3D rendering pipelines, computer-aided design (CAD), and UI rendering engines, fast pixel rasterization algorithms and homogeneous coordinate transformations form the mathematical foundation of computer graphics. In the Tribhuvan University BCA fifth semester, Computer Graphics and Animation (CACS304) tests students on scan-conversion algorithms, line clipping, and 2D/3D matrix transformations.
In the final 60-mark TU board examination, rasterization and transformation numericals account for over 25 marks. Examiners routinely ask students to trace pixels using the DDA or Bresenham’s Line Drawing Algorithm and calculate final coordinates after rotation about an arbitrary point.
In this guide, I will solve standard TU board numericals step-by-step.
1. Line Drawing: DDA vs. Bresenham’s Algorithm
+-------------------+-----------------------------------+-----------------------------------+
| Feature | DDA Algorithm | Bresenham's Line Algorithm |
+-------------------+-----------------------------------+-----------------------------------+
| **Arithmetic** | Floating-point additions | 100% Integer arithmetic |
| | ($y_{k+1} = y_k + m$). | (Fast addition & bit shifts). |
+-------------------+-----------------------------------+-----------------------------------+
| **Rounding** | Requires explicit `round()` func | No rounding operations needed |
| | at every pixel step. | (Sign of decision parameter $P_k$).|
+-------------------+-----------------------------------+-----------------------------------+
| **Hardware Speed**| Slower due to float calculations. | Highly optimized for GPU/hardware.|
+-------------------+-----------------------------------+-----------------------------------+
2. Solved TU Board Problem 1: Bresenham’s Line Drawing
Problem: Digitize a line segment with endpoints $(2, 2)$ and $(9, 6)$ using Bresenham’s Line Algorithm.
Step 1: Calculate Slope and Differences:
– $(x_1, y_1) = (2, 2)$ and $(x_2, y_2) = (9, 6)$
– $\Delta x = x_2 – x_1 = 9 – 2 = 7$
– $\Delta y = y_2 – y_1 = 6 – 2 = 4$
– Slope $m = \frac{\Delta y}{\Delta x} = \frac{4}{7} \approx 0.571 \; (0 < m < 1)$
– Compute constants:
– $2\Delta y = 2(4) = 8$
– $2\Delta y – 2\Delta x = 2(4) – 2(7) = 8 – 14 = -6$
Step 2: Initial Decision Parameter $P_0$:
$$P_0 = 2\Delta y – \Delta x = 8 – 7 = \mathbf{+1} \quad (P_0 \ge 0)$$
Step 3: Pixel Iteration Table:
+---+----------+----------+----------+--------------------+-------------------------+
| k | P_k | x_{k+1} | y_{k+1} | Next P_{k+1} Calc | Plot Pixel (x, y) |
+---+----------+----------+----------+--------------------+-------------------------+
| - | - | - | - | - | **(2, 2)** [Start] |
| 0 | +1 (>=0) | 2 + 1 = 3| 2 + 1 = 3| 1 + (-6) = -5 | **(3, 3)** |
| 1 | -5 (<0) | 3 + 1 = 4| 3 (same) | -5 + 8 = +3 | **(4, 3)** |
| 2 | +3 (>=0) | 4 + 1 = 5| 3 + 1 = 4| 3 + (-6) = -3 | **(5, 4)** |
| 3 | -3 (<0) | 5 + 1 = 6| 4 (same) | -3 + 8 = +5 | **(6, 4)** |
| 4 | +5 (>=0) | 6 + 1 = 7| 4 + 1 = 5| 5 + (-6) = -1 | **(7, 5)** |
| 5 | -1 (<0) | 7 + 1 = 8| 5 (same) | -1 + 8 = +7 | **(8, 5)** |
| 6 | +7 (>=0) | 8 + 1 = 9| 5 + 1 = 6| End | **(9, 6)** [End] |
+---+----------+----------+----------+--------------------+-------------------------+
Rasterized Pixel Sequence: $(2, 2) \to (3, 3) \to (4, 3) \to (5, 4) \to (6, 4) \to (7, 5) \to (8, 5) \to (9, 6)$
3. 2D Transformations in Homogeneous Coordinates
Using $3 \times 3$ homogeneous coordinate matrices, composite transformations can be multiplied directly:
+-------------------+---------------------------------------------------------------+
| Transformation | Matrix Representation $M$ |
+-------------------+---------------------------------------------------------------+
| **Translation** | $$\begin{pmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{pmatrix}$$ |
+-------------------+---------------------------------------------------------------+
| **Rotation ($\theta$)**| $$\begin{pmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ |
+-------------------+---------------------------------------------------------------+
| **Scaling** | $$\begin{pmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ |
+-------------------+---------------------------------------------------------------+
Solved TU Board Problem 2: 2D Rotation About an Arbitrary Point
Problem: Rotate a point $P(4, 3)$ by $\theta = 90^\circ$ counter-clockwise about an arbitrary pivot point $(x_r, y_r) = (1, 1)$.
Step 1: Composite Transformation Sequence:
$$M = T(x_r, y_r) \cdot R(\theta) \cdot T(-x_r, -y_r)$$
Step 2: Apply Pivot Rotation Formula:
$$\begin{aligned}
x’ &= x_r + (x – x_r)\cos\theta – (y – y_r)\sin\theta \
y’ &= y_r + (x – x_r)\sin\theta + (y – y_r)\cos\theta
\end{aligned}$$
Given $\theta = 90^\circ \implies \cos(90^\circ) = 0, \; \sin(90^\circ) = 1$:
$$x’ = 1 + (4 – 1)(0) – (3 – 1)(1) = 1 + 0 – 2 = \mathbf{-1}$$
$$y’ = 1 + (4 – 1)(1) + (3 – 1)(0) = 1 + 3 + 0 = \mathbf{4}$$
Final Transformed Point: $\mathbf{P’ = (-1, 4)}$
Frequently Asked Questions (FAQ)
Q1: Why are homogeneous coordinates used in computer graphics?
Homogeneous coordinates allow all geometric transformations (translation, rotation, scaling, reflection, and shearing) to be represented uniformly as matrix multiplications, enabling efficient GPU pipeline hardware chaining.
Q2: What is the Cohen-Sutherland line clipping algorithm?
The Cohen-Sutherland algorithm clips lines against a rectangular viewport by assigning 4-bit region outcodes (Top, Bottom, Right, Left) to endpoints to rapidly accept or reject line segments.
