DDA vs Bresenham's Algorithm & Numerical Illustration

---

Major Differences between DDA and Bresenham's Algorithm

Feature	DDA Algorithm	Bresenham's Algorithm
Computation	Uses floating-point arithmetic	Uses only integer arithmetic
Speed	Slower due to floating-point operations	Faster due to integer operations only
Rounding	Requires rounding off at each step	No rounding needed
Accuracy	Less accurate due to rounding errors	More accurate
Operations	Uses multiplication and division	Uses only addition and subtraction
Decision Parameter	No decision parameter used	Uses a decision parameter ($p_k$)
Efficiency	Less efficient	More efficient
Cost	More expensive in computation	Less expensive
Complexity	Simpler to implement	Slightly more complex logic
Hardware	Difficult to implement in hardware	Easy to implement in hardware

---

Bresenham's Line Algorithm: From (10, 6) to (12, 1)

Given: $(x_1, y_1) = (10, 6)$ and $(x_2, y_2) = (12, 1)$

Step A: Calculate parameters

• $dx = x_2 - x_1 = 12 - 10 = 2$
• $dy = y_2 - y_1 = 1 - 6 = -5$
• $|dx| = 2$, $|dy| = 5$

Since $|dy| > |dx|$, the slope is steep (|m| > 1). We drive the algorithm along the y-axis (y is incremented each step).

Here, y decreases (from 6 to 1), so y steps by -1 each iteration. We need to decide whether x increments or stays same at each step.

Step B: Reformulate for steep line (driving along y-axis)

• Steps = $|dy| = 5$
• $dx = 2$ (x increases since $x_2 > x_1$)
• $|dy| = 5$

Initial decision parameter:

$$p_0 = 2|dx| - |dy| = 2(2) - 5 = -1$$

Decision rule (driving along y-axis):

• If $p_k < 0$: next point $(x_k, y_{k+1})$, and $p_{k+1} = p_k + 2|dx|$
• If $p_k \geq 0$: next point $(x_k + 1, y_{k+1})$, and $p_{k+1} = p_k + 2|dx| - 2|dy|$

Where $y_{k+1} = y_k - 1$ (since y is decreasing)

Constants:

• $2|dx| = 4$
• $2|dx| - 2|dy| = 4 - 10 = -6$

Step C: Iteration Table

Step $k$	$p_k$	Condition	Point $(x, y)$	Next $p_{k+1}$
0	-1	$p_0 < 0$	(10, 6)	$-1 + 4 = 3$
1	3	$p_1 \geq 0$	(11, 5)	$3 + (-6) = -3$
2	-3	$p_2 < 0$	(11, 4)	$-3 + 4 = 1$
3	1	$p_3 \geq 0$	(12, 3)	$1 + (-6) = -5$
4	-5	$p_4 < 0$	(12, 2)	$-5 + 4 = -1$
5	—	—	(12, 1)	—

Step D: Final Plotted Points

The pixels plotted are:

• (10, 6) → (11, 5) → (11, 4) → (12, 3) → (12, 2) → (12, 1)

---

Conclusion

Bresenham's algorithm is superior to DDA as it avoids floating-point arithmetic entirely, making it faster and more suitable for hardware implementation. The algorithm efficiently determines the closest pixel positions using only integer addition and a simple decision parameter.