Digital Differential Analyzer (DDA) and Bresenham's Line Drawing

Part 1: What is DDA?

A Digital Differential Analyzer (DDA) is an incremental scan-conversion line drawing algorithm. It computes points along a line by sampling the line at unit intervals in one coordinate and calculating the corresponding value of the other coordinate using the line's slope. It uses floating-point arithmetic and rounding.

Drawing a line using DDA

For endpoints $(x_1, y_1)$ and $(x_2, y_2)$:

1. Compute $dx = x_2 - x_1$, $dy = y_2 - y_1$.
2. Determine steps: $$\text{steps} = \max(|dx|, |dy|)$$
3. Compute increments: $$x_{inc} = \frac{dx}{\text{steps}}, \quad y_{inc} = \frac{dy}{\text{steps}}$$
4. Start at $(x_1, y_1)$. Repeatedly add increments: $$x = x + x_{inc}, \quad y = y + y_{inc}$$
5. Plot $(\text{round}(x), \text{round}(y))$ at each step until all steps done.

DDA is simple but slower and prone to rounding error accumulation because of floating-point operations.

Part 2: Bresenham's Line Drawing Algorithm

Bresenham's algorithm uses only integer addition, subtraction and comparison, avoiding floating point. It chooses the next pixel using a decision parameter.

For a line with $0 \le m \le 1$:

1. $dx = x_2 - x_1$, $dy = y_2 - y_1$
2. Initial decision parameter: $p_0 = 2dy - dx$
3. Plot $(x_1, y_1)$
4. At each step:
   • If $p_k < 0$: $x_{k+1} = x_k + 1$, $y_{k+1} = y_k$, and $p_{k+1} = p_k + 2dy$
   • If $p_k \ge 0$: $x_{k+1} = x_k + 1$, $y_{k+1} = y_k + 1$, and $p_{k+1} = p_k + 2dy - 2dx$
5. Repeat $dx$ times.

Part 3: Tracing A(1,3) to B(6,7) using Bresenham

Given

• $(x_1, y_1) = (1, 3)$
• $(x_2, y_2) = (6, 7)$

Step 1: Compute dx, dy

$$dx = 6 - 1 = 5, \quad dy = 7 - 3 = 4$$

Slope $m = 4/5 = 0.8$, so $0 \le m \le 1$; step along x. Total steps $= dx = 5$.

Step 2: Initial decision parameter

$$p_0 = 2dy - dx = 2(4) - 5 = 8 - 5 = 3$$

Step 3: Constants

$$2dy = 8, \quad 2dy - 2dx = 8 - 10 = -2$$

Step 4: Iteration table

Plot starting point $(1,3)$.

Step 5: Final plotted points

$$\boxed{(1,3),\ (2,4),\ (3,5),\ (4,5),\ (5,6),\ (6,7)}$$

Six pixels are plotted, ending exactly at B(6,7). ✓

Grid visualization

7 |                     * B(6,7)
6 |                *
5 |         *   *
4 |     *
3 | * A(1,3)
  +----------------------
    1   2   3   4   5   6

The verification confirms the endpoint (6,7) is reached correctly.

Parallel vs Perspective Projection and Window-to-Viewport Transformation

Part 1: Parallel Projection vs Perspective Projection

Definition

Parallel Projection: In parallel projection, the projectors (lines of projection) are parallel to each other and perpendicular (or at an angle) to the projection plane. The center of projection is at infinity.

Perspective Projection: In perspective projection, the projectors converge at a single point called the center of projection (eye point or viewpoint). Objects farther away appear smaller, giving a realistic view.

Diagram

Parallel Projection

Object         Projection Plane
  A ---------> A'
  B ---------> B'       (parallel lines)
  C ---------> C'
  
  Projectors are parallel to each other

Perspective Projection

                        Projection Plane
  A  \                      A'
  B   \----> Center  -----> B'
  C  /    of Projection     C'
  
  Projectors converge at one point (eye)

Differences Between Parallel and Perspective Projection

Transformation Matrix

Parallel Projection onto the xy-plane:

$$M_{parallel} = \begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix}$$

The z-coordinate is simply dropped (set to 0).

Perspective Projection (with center of projection at distance d along z-axis):

$$M_{perspective} = \begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 1/d & 0 \end{bmatrix}$$

The projected coordinates are:

$$x_p = \frac{x}{z/d}, \quad y_p = \frac{y}{z/d}$$

Part 2: Window to Viewport Transformation

Definitions

• Window: A rectangular region in the world coordinate system that defines what part of the scene is to be viewed.
• Viewport: A rectangular region on the display/screen device where the window contents are mapped and displayed.

Diagram

World Coordinate System          Screen/Device Coordinate System
                                 
  yw_max +--------+              yv_max +----------+
         |        |                    |          |
         | WINDOW |    ========>       | VIEWPORT |
         |        |                    |          |
  yw_min +--------+              yv_min +----------+
         xw_min  xw_max                xv_min    xv_max

Steps of Window to Viewport Transformation

The transformation is done in three steps (composite transformation):

Step 1: Translate window to origin

Move the lower-left corner of the window to the origin.

$$T_1 = T(-x_{w_{min}},\ -y_{w_{min}})$$

Step 2: Scale to viewport size

Scale the window so it matches the size of the viewport.

$$S = S(S_x,\ S_y)$$

Where the scaling factors are:

$$S_x = \frac{x_{v_{max}} - x_{v_{min}}}{x_{w_{max}} - x_{w_{min}}}$$

$$S_y = \frac{y_{v_{max}} - y_{v_{min}}}{y_{w_{max}} - y_{w_{min}}}$$

Step 3: Translate to viewport position

Move the scaled object to the viewport's actual position on screen.

$$T_2 = T(x_{v_{min}},\ y_{v_{min}})$$

Composite Transformation Matrix

$$T_{wv} = T(x_{v_{min}},\ y_{v_{min}}) \cdot S(S_x,\ S_y) \cdot T(-x_{w_{min}},\ -y_{w_{min}})$$

The final mapping equations for any point $(x_w, y_w)$ in the window to $(x_v, y_v)$ in the viewport:

$$\boxed{x_v = x_{v_{min}} + (x_w - x_{w_{min}}) \cdot S_x}$$

$$\boxed{y_v = y_{v_{min}} + (y_w - y_{w_{min}}) \cdot S_y}$$

Numerical Example

Given:

• Window: $x_{w_{min}} = 20,\ x_{w_{max}} = 80,\ y_{w_{min}} = 10,\ y_{w_{max}} = 60$
• Viewport: $x_{v_{min}} = 0,\ x_{v_{max}} = 40,\ y_{v_{min}} = 0,\ y_{v_{max}} = 30$
• Point in window: $P_w = (50, 40)$

Step 1: Calculate scaling factors

$$S_x = \frac{40 - 0}{80 - 20} = \frac{40}{60} = 0.667$$

$$S_y = \frac{30 - 0}{60 - 10} = \frac{30}{50} = 0.6$$

Step 2: Apply the mapping equations to $P_w = (50, 40)$

$$x_v = x_{v_{min}} + (x_w - x_{w_{min}}) \cdot S_x = 0 + (50 - 20) \times 0.667 = 30 \times 0.667 = 20.0$$

$$y_v = y_{v_{min}} + (y_w - y_{w_{min}}) \cdot S_y = 0 + (40 - 10) \times 0.6 = 30 \times 0.6 = 18.0$$

$$\boxed{P_v = (20,\ 18)}$$

Conclusion

The point $(50, 40)$ in the window maps to $(20, 18)$ in the viewport. This is exactly the composite transformation described above: translate the window's lower-left corner to the origin, scale by the ratio of viewport size to window size (here $S_x = 0.667$, $S_y = 0.6$, since the viewport is smaller than the window in both dimensions), then translate to the viewport's actual position on the screen. Because $S_x \neq S_y$ in this example, the mapping is a non-uniform scale, so shapes in the window are stretched differently along x and y once displayed in the viewport.

Short Notes

a. OpenGL (2.5 marks)

OpenGL (Open Graphics Library) is a software interface (API) that allows a programmer to communicate with graphics hardware for rendering 2D and 3D graphics. It provides a common set of commands that can be used to manage graphics across different applications and multiple platforms.

Key Features:

• Vendor-independent: It was the first vendor-independent API for development of graphics applications.
• Free to use: There is no need to license it.
• Hardware accelerated: Designed to use the graphics card where possible to improve performance.
• Language flexible: Originally based on a state machine, procedural model; thus it can be used with a wide variety of programming languages.

Common OpenGL Commands:

• Drawing polygons
• Assigning colors to shapes
• Zooming in and out
• Rotating objects

Color Models:

OpenGL supports two color models:

1. RGBA mode - color specified by Red, Green, Blue intensities and an optional Alpha (transparency) value. Values range from 0.0 (absent) to 1.0 (saturated).
2. Color Index mode

GLUT (OpenGL Utility Toolkit):

GLUT aids in the development of more complicated 3D objects such as a sphere, a torus, and a teapot. It uses callback functions - functions that the GLUT library calls when it needs to process an event (e.g., glutKeyboardFunc for key press events).

b. Flynn's Classification (2.5 marks)

Flynn's Classification (proposed by Michael J. Flynn, 1966) classifies computer architectures based on the number of concurrent instruction streams and data streams.

Diagram:

                    Data Streams
                  Single    Multiple
Instruction  Single | SISD  |  SIMD |
Streams     Multiple| MISD  |  MIMD |

Summary:

• SISD - conventional computers
• SIMD - parallel array processors
• MISD - pipeline processors (debated)
• MIMD - modern multicore and distributed systems (most common today)

Flynn's classification is widely used as a fundamental framework for understanding and comparing parallel computer architectures.