Consider the midpoint (or Bresenham) algorithm for rasterizing lines given…
2018
Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below:
(1) Input \((x_1, y_1)\) and \((𝑥_2,𝑦_2)\)
(2) \(𝑦=𝑦_1\)
(3) \(d=f(x_1+1, y_1+1/2)\) //f is the implicit form of a line
(4) for \(x=x_1\) to \(x_2\)
(5) do
(6) plot\((x,y)\)
(7) if \((𝑑<0)\)
(8) then
(9) \( 𝑦=𝑦+1\)
(10) \(d=d+(y_1-y_2)+(x_2-x_1)\)
(11) else
(12) \(d=d+(y_1-y_2)\)
(13) end
(14) end
Which statements are true?
P: For a line with slope \(𝑚>1\), we should change the outer loop in line (4) to be over \(𝑦\)
Q: Lines (10) and (12) update the decision variable \(𝑑\) through an incremental evaluation of the line equation \(𝑓\)
R: The algorithm fails if \(𝑑\) is over 0
Choose the correct answer from the code given below:
- A.
P only
- B.
P and Q only
- C.
Q and R only
- D.
P, Q and R
Attempted by 91 students.
Show answer & explanation
Correct answer: B
Final answer: P and Q are true; R is false.
Explanation:
Why the slope statement is true: For lines with slope greater than 1 the line advances more in y than in x. To step in the dominant direction you swap the roles of x and y so the outer loop iterates over y and you adjust x conditionally. This preserves the same incremental logic but steps in the major axis.
Why the update lines implement incremental evaluation: The decision variable d is defined from the implicit line function f at a midpoint (for example f(x+1, y+1/2)). Instead of recomputing f at every candidate pixel, the algorithm updates d by adding constants that are differences of f when x or y change. Lines (10) and (12) add those precomputed constants, so the decision is done incrementally.
Why the failure claim is false: The decision variable can be positive or negative during execution; its sign only decides whether to advance the minor coordinate (for example increment y) for the next pixel. There is no inherent failure when d>0 — the algorithm simply takes the alternative branch. Therefore the statement that the algorithm fails if d is over 0 is incorrect.
Summary: change outer loop for steep lines; update lines perform incremental evaluation; d>0 does not cause failure.
A video solution is available for this question — log in and enroll to watch it.